Tabrakan timestamp nanodetik itu umum terjadi

• Pada sistem modern di mana beberapa core fisik membaca jam secara bersamaan, timestamp nanodetik pun mudah bertabrakan, dan dalam pengukuran serentak pada 4 core fisik sekitar 5% dari seluruh sampel mengalami tabrakan
• Desain yang memakai timestamp mentah sebagai pengenal unik itu berisiko, dan frekuensi tabrakan berbeda tergantung sistem operasi serta cara eksekusinya
• time.Now() di Go mencatat waktu absolut dan waktu relatif berdasarkan jam monotonik secara bersamaan, sehingga selisih antar pemanggilan berurutan dan duplikasi timestamp absolut bisa diperiksa secara terpisah
• Pada Linux single-thread, waktu selalu meningkat dan kenaikan minimum adalah 32ns, tetapi ketika thread dipisah, waktu absolut yang sama dapat teramati
• Di Mac OS X, waktu absolut memiliki resolusi mikrodetik sehingga tabrakan jauh lebih sering, dan bahkan pada single-thread sering terlihat kasus ketika jam monotonik tidak meningkat

---

Frekuensi tabrakan yang terlihat saat pembacaan serentak

• Pertanyaan utamanya adalah seberapa sering tabrakan timestamp nanodetik benar-benar terjadi pada sistem modern
• Jika jam dibaca secara bersamaan pada 4 core fisik, sekitar 5% dari seluruh sampel bertabrakan
• Bahkan pada sistem 4 core, jika hanya 2 thread yang digunakan, sekitar 2% timestamp saling tumpang tindih
• Karena itu, tidak aman mengasumsikan bahwa hanya dengan timestamp nanodetik mentah bisa dibuat ID unik

Metode pengujian dan perbedaan antar sistem operasi

• Program pengujian ditulis dalam Go
• time.Now() di Go mencatat waktu absolut dan waktu relatif berdasarkan jam monotonik pada setiap pemanggilan
  • Pengujian membandingkan selisih relatif antar timestamp berurutan
  • Duplikasi pada timestamp absolut itu sendiri juga diperiksa

• Linux

  • Pada single-thread, waktu absolut dan waktu monotonik selalu meningkat
  • Kenaikan minimum pada sistem yang diukur adalah 32ns
  • Di antara thread, sekitar 5% kasus menunjukkan waktu absolut yang persis sama dengan thread lain

• Mac OS X

  • Karena waktu absolut memiliki resolusi mikrodetik, sangat banyak tabrakan terjadi pada pengujian yang sama
  • Bahkan pada single-thread, sering diamati kasus ketika jam monotonik tidak meningkat

[GN⁺]

Komentar Hacker News

• Menggunakan ID yang menggabungkan elemen waktu dan nomor urut adalah cara untuk menghindari masalah seperti ini
  Misalnya, UUIDv7 memiliki elemen waktu berbasis milidetik, ada field yang bertambah untuk setiap peristiwa dalam milidetik yang sama, dan juga bit acak yang cukup untuk membuat kemungkinan bentrok antar-ID yang dibuat di mesin berbeda menjadi sangat kecil secara astronomis
  Tentu saja jumlah bit itu terbatas, jadi jika ada terlalu banyak peristiwa dalam rentang waktu yang sama nomor urut bisa meluap, bentrok antar-mesin juga tetap bisa benar-benar terjadi, dan operasi penambahan itu sendiri mungkin memerlukan sinkronisasi CPU sehingga laju pembuatan peristiwa bisa dibatasi
  Meski begitu, pada skala kerja nyata UUIDv7 bekerja sangat baik

  • Agak kebetulan rasanya seperti jadi penjelajah waktu, tapi saya ingat sekitar setidaknya 10 tahun lalu di sebuah pertemuan teknis ada percakapan tentang seseorang yang membuat lebih dari 1000 UUID per milidetik lalu kesulitan karena masalah keunikan, dan saat itu tidak puas dengan pilihan yang tersedia
    Sulit menemukan di internet sebenarnya sudah berapa lama UUIDv7 ada
  • Dari awal saya tidak paham kenapa elemen waktu dibutuhkan
    Itu hanya memakan bit di UUID dan tidak banyak menambah entropi
  • Ini juga cocok dengan urutan pengurutan di database populer seperti PostgreSQL
    Memang belum masuk ke inti, tetapi selain memakainya langsung di level aplikasi, ada beberapa ekstensi pg yang sangat bagus yang menyediakan uuidv7
  • Masalah UUID adalah sangat sulit dibaca sepenuhnya
    Bukan cuma susah dipahami, bahkan membedakan satu dengan yang lain secara visual pun sangat sulit
    Jadi dalam beberapa kasus, identifier yang sama sekali tidak memuat informasi atau noise selain informasi minimum yang dibutuhkan itu berguna
  • Tergantung kasus penggunaan, bahkan penanganan “milidetik yang sama” pun tidak selalu diperlukan sehingga bisa menghemat beberapa siklus
    Dalam bentuk apa pun, penghitung bertambah yang bisa meluap dan sedikit bit acak biasanya sudah cukup, dan kalau dirancang dengan baik keduanya bisa dilakukan tanpa percabangan

• Terkait ini, dulu saya adalah manajer program yang menangani log peristiwa keamanan di Windows
  Pada sistem multicore, ketika sesuatu terjadi secara bersamaan atau dalam waktu yang sangat berdekatan, penjadwalan thread bisa sangat memengaruhi hasil yang diamati
  Misalnya, kuantum thread bisa habis sebelum mencapai system call untuk mengambil timestamp, atau sebelum menyerahkan buffer yang akan dipakai untuk memasukkan peristiwa ke antrean agar nanti diberi timestamp
  Pada kenyataannya, di sistem multiprosesor Windows era 2000-an, sangat umum entri log peristiwa terlihat urutannya terbalik, dan akurasi timestamp log juga tidak bisa dipercaya terlalu presisi
  Batas bawah yang aman pada dasarnya adalah 1 detik, dan saya ingat beberapa komponen bahkan memotong atau membulatkan timestamp

• Jika Anda butuh pengenal unik, gunakan UUID versi 4, yaitu UUID acak
  Peluang terjadinya bentrok kira-kira setara dengan peluang seekor dinosaurus dewasa tiba-tiba muncul di kamar tidur karena fluktuasi kuantum

  • Saya rasa saya bisa menerima risikonya
    Lebih seriusnya, kalau bisa dipakai, nilai bertambah model lama mungkin memang yang terbaik
    Cepat dan murah, terutama di database, tetapi ada masalah privasi dan keamanan karena informasi bisa ditebak dari nilai ID
    Dalam kasus seperti itu, atau saat berurusan dengan sistem terdistribusi, UUID lebih baik
  • v7 tampaknya lebih baik karena menyelesaikan masalah lokalitas v4, sementara peluang bentrok tetap jauh lebih kecil daripada peluang menang lotre
  • Saya ingin melihat bagaimana perhitungan untuk “peluang dinosaurus tiba-tiba muncul di kamar tidur” itu dibuat
  • Berarti peluang terjadinya hal buruk kira-kira naik 2 kali lipat, jadi saya tidak bisa menerimanya

• Walaupun resolusinya nanodetik, saya penasaran seberapa besar presisi jam komputer yang sebenarnya
  Sulit membayangkan itu benar-benar setingkat nanodetik, dan ini mengingatkan saya pada saat di kelas eksperimen fisika saya terus menekankan kepada mahasiswa bahwa angka terkecil yang ditampilkan alat ukur tidak sama dengan akurasinya

  • Untuk perangkat yang berjalan di atas 1GHz, sangat mungkin jamnya bertambah setiap nanodetik
    Hanya saja itu tidak berarti akurat pada tingkat tersebut, dan pada sistem multicore jam antar-core mungkin juga tidak tersinkron setepat itu
    ARMv8 menjamin jam bertambah minimal 1GHz, tetapi Intel dan ARM yang lebih lama lebih rumit
  • Memang benar-benar nanodetik

• BEAM VM di Erlang/Elixir menampilkan perbedaan ini dengan sangat jelas. Ini adalah pembedaan antara monoton meningkat dan monoton meningkat secara ketat
  https://www.erlang.org/doc/apps/erts/time_correction.html#mo...
  “Dalam urutan nilai yang meningkat secara monoton, setiap nilai yang memiliki nilai sebelumnya akan lebih besar atau sama dengan nilai sebelumnya itu”
  Ini dapat digunakan melalui fungsi https://www.erlang.org/doc/man/erlang.html#monotonic_time-0
  https://www.erlang.org/doc/apps/erts/time_correction.html#st...
  “Dalam urutan nilai yang meningkat secara monoton ketat, setiap nilai yang memiliki nilai sebelumnya akan lebih besar daripada nilai sebelumnya itu”
  Nilai monoton ketat menyiratkan adanya sinkronisasi atau koordinasi dalam bentuk tertentu, dan ada biaya performa ketika proses konkuren banyak
  Fitur ini disediakan melalui fungsi https://www.erlang.org/doc/man/erlang.html#unique_integer-1, dan dokumentasinya juga memperingatkan bahwa nilai yang meningkat secara monoton ketat pada dasarnya mahal untuk dihasilkan dan tidak skalabel, jadi modifier monotonic sebaiknya hanya diberikan saat benar-benar diperlukan

  • Bahkan nilai referensi Erlang sendiri tidak dibuat dengan generator global monoton ketat, melainkan secara internal terdiri dari pasangan pengenal monoton biasa dan PID proses yang memintanya
    Dengan kata lain, ini mirip UUIDv1 atau https://en.wikipedia.org/wiki/Snowflake_ID
    Pengenal global monoton ketat benar-benar diperlukan hanya ketika yang dibutuhkan adalah pemenang tulis pertama/terakhir yang konsisten secara langsung
    Sebaliknya, jika bisa menggunakan pemenang tulis pertama/terakhir yang konsisten secara eventual, misalnya event tulis masuk ke event store atau queue yang dilinearisasi berdasarkan ID dan di antara tulis yang “bersamaan” hanya yang memiliki prioritas ID tertinggi yang dipertahankan sementara sisanya dibuang saat pemrosesan atau saat dibaca, saya akan mempertimbangkan pasangan (nodeID, seq) yang dikompresi terlebih dahulu
    Jika perlu pengurutan peristiwa global, bentuk Snowflake ID seperti (timestampMajor, nodeID, timestampMinor, seq) patut dipertimbangkan

• FreeBSD tidak memiliki CLOCK_MONOTONIC_RAW, jadi setelah dikomentari hasilnya tampak baik-baik saja
  Saya memahami bahwa jika ada collision, beberapa timestamp seharusnya berulang, tetapi saya tidak bisa membuat collision terjadi
  clock_getres(CLOCK_REALTIME, ...)=1 ns, clock_getres(CLOCK_MONOTONIC, ...)=1 ns, dan bahkan pada 30 sampel perbedaannya terus meningkat dalam kisaran kira-kira 29~71ns

  • Penting apakah ini dijalankan secara bersamaan di 4 core seperti yang dilakukan penulis

• Pada akhirnya, sepertinya ini turun sampai ke masalah arsitektur set instruksi
  CPU yang berjalan pada 3GHz mendapat 3 siklus clock per nanodetik
  Dengan optimisasi compiler, tampaknya cukup mungkin panggilan assembly yang membaca register jam ditempatkan berurutan
  Jika pemanggilan time.Now() berturut-turut terjadi dalam 3 siklus clock, rasanya tidak adil mengharapkan presisi nanodetik yang benar-benar unik

  • x86_64 di Linux menggunakan RDTSC dan mengoreksinya dengan nilai yang dibaca dari VDSO, jadi hal ini memang bisa terjadi sangat cepat
  • Bahkan membaca register penghitung siklus pada chip modern tetap memakan kira-kira 20 siklus
    Walaupun collision agak jarang, jika itu terjadi beberapa kali sehari, itu jauh lebih buruk daripada “hampir tidak pernah terjadi”

• Ini mengingatkan pada legenda terkait Lotus Notes
  Dulu konon timestamp dengan resolusi 1 detik dipakai sebagai ID unik
  Jika terjadi collision, mereka cukup menambahkan 1 detik, dan pada akhirnya collision menjadi begitu sering sehingga item-item itu memiliki waktu di masa depan

• Waktu yang benar-benar akurat adalah masalah keamanan
  Para perancang CPU sudah sejak lama dengan sengaja menambahkan jitter jam untuk mencegah prediktabilitas penuh, bahkan sejak era Alpha dari DEC
  Di x86 juga, jika dijalankan 3~4 kali, nilainya disimpan ke register lalu dilihat setelah selesai, tampaknya kita bisa melihat bahwa selisih waktunya tidak persis sama

  • Saya penasaran apakah ada sumbernya
    Saya tidak berhasil menemukan banyak lewat pencarian, tetapi jika ini juga mencakup x86 awal, cukup mengejutkan bahwa masalah keamanan dari jam yang akurat sudah disadari sedini itu
    Secara pribadi saya rasa sampai sebelum milenium ini saya belum mengetahui masalah seperti itu, dan mungkin akan menebak bahwa jitter jam yang teramati bisa dijelaskan oleh hal seperti interrupt
    Bukan berarti saya mengatakan itu salah, saya hanya ingin tahu lebih banyak

• Saya sudah terlalu sering melihat orang terkejut oleh collision timestamp milidetik atau mikrodetik
  Tipe yang paling membekas dan paling saya benci adalah cara merakit timestamp dari dua system call
  Satu dipanggil untuk digit orde atas, yang lain untuk digit orde bawah, lalu karena preemption proses, jika setelah membaca digit orde atas digit orde bawah berpindah dari 99x ke 00x, kita bisa membuat timestamp yang lebih awal daripada penyebab sebenarnya dari entitas yang dibuat
  Ini membuat sebagian kode rusak dengan sangat spektakuler, dan saya setidaknya dua kali melihat loop tak hingga
  Jika kita tidak menghafalnya sebagai sesuatu yang harus selalu dihindari, tes akan lolos 99,5% dan kita harus bergantung pada seseorang dengan naluri pattern matching yang sangat bagus untuk menangkap bahwa “tes yang sama berubah merah sekali seminggu selama satu setengah bulan”
  Itu terlalu lama bagi bom logika untuk tetap hidup di dalam kode CI/CD sebelum diperbaiki

  • Contoh yang paling membekas adalah ketika dalam percakapan dukungan saya berkata, “sepertinya ada race condition”, lalu dijawab, “kedua peristiwa itu terjadi pada waktu yang persis sama, jadi itu tidak mungkin race condition”