Wawancara Desain Sistem: Bagaimana Cara Menggunakan Hybrid Logical Clock untuk Mengurutkan Peristiwa Antar-Node?

Konteks dan cakupan

Rancang stempel versi lintas-node untuk penyimpanan key-value tiga wilayah. Setiap node hanya memiliki wall clock lokal, dengan asumsi perbedaan waktu (skew) maksimum 50 milidetik. Jaringan dapat mengalami penundaan, pengiriman ulang, dan pengurutan ulang pesan, serta jam node dapat bergerak mundur. Penulisan memerlukan versi yang dapat dibandingkan untuk MVCC, pengurutan audit, dan diagnosis konflik.

Ini cocok untuk wawancara penyimpanan terdistribusi, database, infrastruktur, dan desain sistem. HLC adalah pasangan (physical, logical): bagian fisik tetap mendekati wall time, sedangkan bagian logis maju ketika waktu fisik tidak bergerak atau ketika stempel jarak jauh yang lebih baru teramati. Masalah ini tidak meminta Anda untuk menyimpulkan urutan peristiwa konkuren di dunia nyata dan tidak memberi Anda batasan waktu perangkat keras bergaya TrueTime.

Hal yang diuji oleh pewawancara

Pewawancara menginginkan jaminan sebelum komponen:

• Jawaban yang kuat menyatakan bahwa HLC menjaga urutan kausal, monotonisitas lokal, dan kedekatan dengan waktu fisik; jawaban ini tidak mengklaim urutan waktu nyata global atau urutan total yang bebas konflik.
• Jawaban yang kuat memberikan invarian pembaruan untuk peristiwa lokal dan terima alih-alih sekadar mengulang "waktu fisik ditambah pencacah (counter)".
• Jawaban yang kuat membawa skew jam maksimum ε ke dalam operasi baca dan menjelaskan mengapa MVCC dapat melakukan percobaan ulang (retry), alih-alih hanya menghasilkan stempel pada operasi tulis.
• Jawaban yang kuat membandingkan vector clock dan TrueTime serta menyatakan bahwa HLC tidak menggantikan konsensus, batasan keunikan, atau resolusi konflik aplikasi.

Jawaban yang lemah hanya mengambil nilai maksimum dari dua jam mesin. Hal itu melewatkan kausalitas pesan, pembalikan jam (clock rollback), luapan counter logis, dan interval ketidakpastian.

Klarifikasi sebelum menjawab

1. Apa yang harus dijamin oleh stempel? HLC cukup untuk mengurutkan versi MVCC per kunci; urutan commit konsistensi eksternal antar wilayah memerlukan konsensus atau layanan bounded-time.
2. Apakah 50 milidetik merupakan batas mutlak (hard bound) atau metrik yang teramati? Hanya batas mutlak yang dapat mendefinisikan ε secara aman; sebuah perkiraan berguna untuk peringatan dan percobaan ulang yang konservatif.
3. Apakah operasi baca dapat melintasi replika, dan bolehkah mencoba ulang? Pembacaan lintas replika harus membawa timestamp baca dan batas ketidakpastian; jika percobaan ulang dilarang, jaminan atau putaran koordinasi harus diubah.
4. Bagaimana penulisan konkuren digabungkan? HLC membuat timestamp dapat dibandingkan, tetapi aplikasi tetap memerlukan penulisan kondisional, konteks vektor, atau aturan penggabungan eksplisit.

Kerangka jawaban 30 detik

"Saya akan mempertahankan (p,l) di setiap node. p adalah waktu fisik terbesar yang teramati, dan l menjadi pemecah seri dalam waktu fisik tersebut. Untuk peristiwa lokal, gunakan max(now,p), reset bagian logis ketika waktu fisik maju, jika tidak, lakukan inkremen. Pada stempel jarak jauh, ambil nilai maksimum dari komponen fisik lokal, jarak jauh, dan saat ini, kemudian lakukan inkremen pada bagian logis setiap kali beberapa sumber memiliki nilai maksimum yang sama. Oleh karena itu, pesan kausal memajukan HLC sementara nilainya tetap mendekati wall time. Untuk MVCC, ubah batas skew ε menjadi jendela ketidakpastian; versi di dalam jendela tersebut memerlukan percobaan ulang atau timestamp baca yang lebih tinggi. HLC tidak membuktikan urutan nyata dari peristiwa konkuren dan tidak menggantikan konsensus atau penggabungan konflik."

Jawaban mendalam langkah demi langkah

1. Nyatakan invarian terlebih dahulu

Setiap node mempertahankan T=(p,l), yang dibandingkan berdasarkan p terlebih dahulu dan l kedua. Desain ini memerlukan tiga invarian:

• p setidaknya merupakan wall time dan komponen fisik jarak jauh yang telah diamati oleh node.
• Peristiwa berurutan yang dipancarkan oleh satu node memiliki stempel yang meningkat secara ketat.
• Jika stempel peristiwa A dibawa ke peristiwa B, stempel B secara ketat lebih besar.

Makalah HLC menjelaskan hal ini sebagai mempertahankan informasi kausal sambil tetap dekat dengan waktu fisik. Pola Martin Fowler juga memodelkan timestamp hibrida sebagai waktu fisik ditambah pencacah logis.

2. Memperbarui peristiwa lokal

Misalkan now adalah waktu fisik saat ini dan (p,l) adalah stempel lama:

if now > p:
    p = now
    l = 0
else:
    l = l + 1

Jika wall clock bergerak mundur, p tidak bergerak mundur dan bagian logis terus bertambah. Implementasi harus mendeteksi pencacah yang mendekati batasnya; wrap-around diam-diam akan membalikkan hasil perbandingan. Makalah menunjukkan bahwa HLC dapat menggunakan penyimpanan dengan lebar tetap, tetapi lebarnya tetap perlu divalidasi terhadap resolusi jam, drift yang diizinkan, dan laju peristiwa.

3. Memperbarui setelah menerima stempel jarak jauh

Untuk R=(rp,rl) jarak jauh, hitung q=max(now,p,rp), lalu pilih komponen logis berdasarkan sumber mana yang mencapai nilai maksimum tersebut:

if q == now and q > p and q > rp:
    (p, l) = (q, 0)
else if q == p and q == rp:
    (p, l) = (q, max(l, rl) + 1)
else if q == p:
    (p, l) = (q, l + 1)
else:
    (p, l) = (q, rl + 1)

Invarian yang penting bukanlah sintaksisnya: komponen fisik maksimum tidak pernah mundur, dan ketika nilai lokal dan jarak jauh bernilai sama untuk nilai maksimum, komponen logis akan melebihi keduanya. Lampirkan HLC saat ini ke pesan keluar atau konteks transaksi; penerima memperbarui jamnya sebelum memberi stempel pada peristiwanya sendiri. Oleh karena itu, pesan lama yang urutannya berubah tidak dapat menurunkan timestamp kausal yang sudah teramati.

4. Menggunakan HLC untuk versi MVCC

Operasi tulis MVCC dapat menggunakan HLC-nya sebagai versi. Transaksi baca dimulai pada t dan menyimpan t+ε sebagai batas ketidakpastian, di mana ε adalah skew jam fisik maksimum yang diizinkan oleh klaster. Jika melihat versi v setelah t dan tidak lebih lambat dari t+ε, sistem tidak dapat memastikan apakah versi tersebut di-commit sebelum pembacaan atau berasal dari jam yang lebih cepat. Implementasi yang aman akan menunggu, memajukan timestamp baca, atau memulai ulang. Dokumentasi lapisan transaksi CockroachDB menjelaskan komponen fisik dan logis HLC serta perilaku retry ketidakpastian ini.

Ini mengubah kesalahan sinkronisasi menjadi biaya percobaan ulang yang dapat diamati. Pantau ε, tingkat percobaan ulang ketidakpastian, dan pertumbuhan counter logis alih-alih hanya melihat latensi rata-rata.

5. Membandingkan alternatif

• Vector clock mengidentifikasi konkurensi, tetapi metadata bertambah seiring bertambahnya himpunan partisipan; ini cocok untuk sistem yang memerlukan deteksi konflik eksplisit dengan himpunan replika yang kecil.
• HLC menggunakan stempel fisik-plus-logis dengan lebar tetap untuk MVCC, audit, dan pengurutan. HLC tidak dapat membuktikan bahwa dua peristiwa konkuren tidak saling berhubungan, dan tidak dapat menyelesaikan protokol commit global secara mandiri.
• Layanan bounded-time seperti TrueTime mengekspos interval waktu dengan batas kesalahan dan dapat mendukung konsistensi eksternal yang lebih kuat; layanan ini memerlukan infrastruktur jam khusus atau commit waiting.

Aturan keputusannya adalah: pilih HLC untuk metadata rendah, timestamp mendekati fisik, dan versi yang dapat dibandingkan; pertahankan konteks vektor ketika konkurensi harus dideteksi secara tepat; tambahkan konsensus atau layanan bounded-time untuk konsistensi eksternal.

6. Kasus kegagalan dan verifikasi

• Rollback fisik: masukkan lompatan mundur dan verifikasi bahwa p tidak pernah menurun dan stempel tetap meningkat.
• Pengurutan ulang jarak jauh: kirimkan stempel yang lebih besar lalu yang lebih kecil; stempel yang lebih kecil tidak boleh menurunkan status lokal.
• Pertumbuhan logis: bekukan waktu fisik dan buat peristiwa dengan cepat; verifikasi jalur perlindungan sebelum terjadi overflow.
• Skew di atas ε: masukkan clock drift dan verifikasi penolakan startup, penurunan ke mode baca-saja, atau percobaan ulang yang terlihat, alih-alih klaim konsistensi diam-diam.
• Badai percobaan ulang MVCC: catat tingkat hit jendela, jumlah percobaan ulang, dan distribusi node untuk memisahkan konflik sebenarnya dari skew jam.

Contoh jawaban berkualitas tinggi

"Saya akan memisahkan jaminan jam dari jaminan penyimpanan. Jam mempertahankan (p,l), di mana p adalah waktu fisik terbesar yang teramati dan l maju ketika waktu fisik tidak maju atau ketika stempel jarak jauh memiliki komponen fisik maksimum yang sama. Setiap pesan keluar membawa HLC. Penerima mengambil komponen fisik maksimum dari waktu lokal, jarak jauh, dan waktu saat ini, lalu membuat komponen logis lebih besar dari setiap sumber pada nilai maksimum tersebut. Oleh karena itu, rantai kausal mendapatkan stempel yang meningkat secara ketat bahkan jika wall clock bergerak mundur.

Untuk MVCC, transaksi baca memiliki timestamp mulai t dan batas skew ε. Melihat versi antara t dan t+ε bersifat ambigu, jadi saya mencoba ulang atau memajukan timestamp baca. Hal itu mengubah kesalahan jam menjadi biaya percobaan ulang yang eksplisit; saya memantau skew, counter logis, dan hit jendela. HLC berguna untuk pengurutan versi dengan metadata rendah, tetapi peristiwa konkuren masih dapat menerima urutan perbandingan yang arbitrer. HLC tidak menyediakan deteksi konkurensi vector-clock atau jaminan konsistensi eksternal dari konsensus atau TrueTime."

Kesalahan umum

• Kesalahan → menimpa stempel lokal dengan now → pembalikan jam memindahkan versi ke belakang → pertahankan komponen fisik maksimum dan lakukan inkremen secara logis.
• Kesalahan → hanya menyimpan waktu fisik jarak jauh maksimum → urutan kausal pada waktu fisik yang sama hilang → lakukan inkremen melampaui nilai logis lokal dan jarak jauh saat terjadi seri.
• Kesalahan → mengklaim HLC mengidentifikasi setiap hubungan konkuren → satu perbandingan skalar tidak dapat membuktikan 'konkuren' → bawa konteks vektor atau kausal eksplisit untuk deteksi konflik.
• Kesalahan → mengabaikan versi yang tampak di masa depan → versi tersebut mungkin sudah ada sebelum pembacaan di bawah skew jam → gunakan jendela ε dan coba ulang atau majukan timestamp baca.
• Kesalahan → menghilangkan pemantauan skew → badai percobaan ulang terlihat seperti konflik database → catat skew per-node, hit jendela, dan pertumbuhan counter logis.

Tindak lanjut dan tanggapan

Jika dua penulisan konkuren memiliki nilai HLC yang sebanding, mana yang menang?

HLC menyediakan kunci pengurutan, bukan urutan dunia nyata. Jika last-writer-wins dapat diterima, tentukan pemecah seri (HLC, node-id) yang deterministik. Jika pengeditan konkuren tidak boleh hilang, pertahankan beberapa versi atau bawa konteks vektor untuk penggabungan aplikasi. Nyatakan dengan jelas bahwa ini adalah kebijakan konflik, bukan bukti kausal HLC.

Bagaimana jika skew maksimum bertambah dari 50 milidetik menjadi 2 detik?

Berhenti memperlakukan ε lama sebagai aman, isolasi node yang mengalami drift, dan perbaiki sinkronisasi waktu. Meningkatkan ε meningkatkan percobaan ulang ketidakpastian MVCC; mengecilkannya berisiko membaca versi yang salah. Jika batas tidak dapat dipulihkan, jeda penulisan, turunkan ke mode baca-saja, atau tambahkan koordinasi yang lebih kuat. Ambang batas, peringatan, dan tindakan pemulihan merupakan bagian dari kebijakan operasional.

Bagaimana cara mencegah counter logis tumbuh tanpa batas pada throughput tinggi?

Batasi peristiwa per tick fisik, gunakan integer yang cukup lebar, dan beri peringatan saat mendekati batas. Anda dapat menunggu waktu fisik maju, meningkatkan resolusi waktu, atau menolak penulisan; memotong (truncate) counter akan merusak monotonisitas. Uji stres harus membekukan now dan menguji jalur perlindungan pra-overflow.

Mengapa tidak menggunakan urutan auto-increment database secara langsung?

Urutan tunggal memberikan urutan total, tetapi penulisan lintas wilayah harus mencapai koordinator secara sinkron, yang menambah latensi dan mengurangi ketersediaan. HLC memungkinkan node menghasilkan stempel mendekati waktu nyata secara lokal untuk pengurutan versi dan petunjuk kausal. Ketika urutan commit global yang ketat diperlukan, gunakan urutan konsensus, TrueTime, atau koordinasi yang setara.