Pisahkan waktu dari kausalitas

Pertanyaan

Kalau dua mesin mencatat dua kejadian dengan timestamp, kapan urutan timestamp itu boleh dipercaya, dan apa penggantinya kalau tidak?

Setelah baca ini, kamu bisa menunjukkan kapan last-write-wins berbasis jam membuang tulisan yang benar, menjalankan Lamport clock dan vector clock di contoh kecil, dan memilih antara jam fisik dan logical clock untuk sebuah kebutuhan.

Prasyarat dan contoh

Kamu sudah paham konflik tulis saat partisi (M08.03) dan identifier berbasis waktu (M05.04).

Pengguna mengganti alamat kirim dari mesin server 1, lalu 200 ms kemudian mengganti lagi dari server 2. Jam server 2 tertinggal 350 ms dari server 1. Tulisan pertama bertimestamp 10:00:00.500, tulisan kedua 10:00:00.350 (jam server 2 tertinggal). Penyimpanan memakai last-write-wins dan menyimpan yang timestamp-nya lebih besar: alamat lama menang, alamat baru dibuang. Tidak ada error, tidak ada log, dan pengguna melihat paket dikirim ke alamat lama.

Mekanisme

Jam fisik tidak sinkron. Tiap mesin punya osilator sendiri yang melenceng. Tanpa koreksi, jam kuarsa biasa bisa melenceng puluhan milidetik per hari. Dengan NTP, selisih antar-mesin biasanya satu sampai puluhan milidetik di jaringan baik, dan bisa ratusan milidetik atau lebih saat sinkronisasi gagal. Jam juga bisa melompat mundur saat dikoreksi. Karena itu timestamp(A) < timestamp(B) tidak membuktikan A terjadi sebelum B kalau keduanya dari mesin berbeda.

Kausalitas bukan waktu. Kejadian A mendahului secara kausal B (A → B) kalau B bisa dipengaruhi A: keduanya di proses yang sama dengan A lebih dulu, atau A adalah pengiriman pesan yang diterima di B. Kalau tidak ada jalur pesan di antara keduanya, mereka konkuren, dan "mana yang duluan" tidak punya jawaban yang bermakna, hanya jawaban yang kebetulan dari jam.

Lamport clock. Tiap proses menyimpan penghitung L. Sebelum kejadian lokal: L = L + 1. Saat mengirim pesan, sertakan L. Saat menerima pesan dengan m: L = max(L, m) + 1.

P1: kejadian a  L=1
P1: kirim ke P2 L=2
P2: kejadian b  L=1   (konkuren dengan a)
P2: terima      L=max(1,2)+1=3

Jaminannya satu arah: kalau A → B maka L(A) < L(B). Kebalikannya tidak berlaku: L(A) < L(B) tidak berarti A mendahului B. Lamport clock memberi urutan total yang konsisten dengan kausalitas, tapi tidak bisa mendeteksi konkurensi.

Vector clock. Tiap proses menyimpan vektor penghitung, satu entri per proses. Aturan: naikkan entri sendiri saat kejadian, dan saat menerima, ambil maksimum per entri lalu naikkan entri sendiri. Bandingkan dua vektor: kalau satu ≤ yang lain di semua entri, urutannya kausal. Kalau tidak ada yang ≤, kejadiannya konkuren, dan sistem tahu ada konflik yang perlu digabung. Harganya ukuran vektor tumbuh dengan jumlah proses.

Jam fisik dengan batas ketidakpastian. Beberapa sistem (misalnya Spanner dengan TrueTime) tidak menganggap jam akurat, tapi melaporkan interval [awal, akhir] dan menunggu sampai interval pasti terlewati sebelum mengonfirmasi tulisan. Itu mengganti asumsi "jam benar" dengan "jam salah paling banyak ε", dan membayar ε sebagai latensi (beberapa milidetik).

Alternatif praktis. Nomor versi per baris dengan compare-and-set (UPDATE ... WHERE versi = 7), urutan dari satu leader, atau ID yang monotonik dari log yang direplikasi. Tiga-tiganya tidak butuh jam yang akurat.

Saat rancangan ini gagal

• Last-write-wins berbasis jam fisik. Seperti contoh di atas, jam yang tertinggal membuat tulisan yang benar kalah dengan diam-diam. Kehilangan datanya tidak muncul di metrik apa pun.
• ID berbasis waktu yang diasumsikan terurut. ID gaya Snowflake terurut kasar antar-mesin saja. Dua tulisan di mesin berbeda dalam milidetik yang sama bisa berurutan terbalik (M05.04).
• Jam melompat mundur. Lamport clock tidak terganggu, tapi durasi yang diukur dengan jam dinding bisa negatif. Pakai jam monotonik untuk durasi.
• Vector clock yang membengkak. Dengan ribuan klien yang menulis, vektornya tidak praktis tanpa pemangkasan, dan pemangkasan mengorbankan akurasi deteksi konflik.
• Mengira Lamport mendeteksi konkurensi. L(a) lebih kecil dari L(b) tidak membuktikan sebab-akibat.

Contoh tandingan: TTL cache 60 detik memakai jam lokal tiap node. Selisih jam 300 ms antar-node hanya mengubah kedaluwarsa 0,5%, dan tidak ada keputusan bergantung pada urutan. Di sini jam fisik cukup.

Latihan

Tiga proses P1, P2, P3 dengan Lamport clock awal 0. Urutan: P1 kejadian lokal; P1 kirim pesan m1 ke P2; P3 kejadian lokal dua kali; P2 terima m1; P2 kirim m2 ke P3; P3 terima m2. Hitung nilai L tiap langkah. Lalu, dua tulisan konflik dengan Lamport 4 (dari P3) dan 5 (dari P2) apakah bisa dipastikan yang kedua mendahului kausal?

Lihat pembahasan+

Hitung langkah demi langkah:

• P1 kejadian lokal: L1 = 1
• P1 kirim m1: L1 = 2, m1 membawa 2
• P3 kejadian lokal dua kali: L3 = 1, lalu 2
• P2 terima m1: L2 = max(0, 2) + 1 = 3
• P2 kirim m2: L2 = 4, m2 membawa 4
• P3 terima m2: L3 = max(2, 4) + 1 = 5

Untuk dua tulisan dengan L = 4 (P3) dan L = 5 (P2): tidak bisa dipastikan. Lamport clock hanya menjamin A → B menghasilkan L(A) < L(B), bukan sebaliknya. Pada contoh, kejadian P3 yang bernilai 2 dan kejadian P1 yang bernilai 1 tidak terkait kausal walau angkanya berurutan. Untuk tahu konkuren atau tidak, perlu vector clock: bandingkan vektornya, dan kalau tidak ada yang ≤ yang lain, anggap konflik dan gabungkan secara eksplisit.

Jawaban yang bagus memisahkan "urutan total yang konsisten" dari "bukti sebab-akibat".

Terkait

• M08.03 Bernalar tentang partisi jaringan menjelaskan kenapa konflik tulis muncul dan butuh aturan gabung.
• M08.05 Pahami konsensus memberi urutan lewat log leader, bukan lewat jam.
• M08.06 Gunakan lease dengan hati-hati memakai jam untuk kedaluwarsa dan menunjukkan jebakannya.
• M05.04 membahas identifier berbasis waktu dan caveat clock-nya.

Catatan

• Asumsi: kejadian dan pesan dimodelkan tanpa kegagalan Byzantine.
• Yang tidak dibahas: hybrid logical clock, protokol NTP/PTP secara rinci, dan detail TrueTime.
• Angka skew adalah rentang tipikal, bukan jaminan. Ukur jam di lingkunganmu.
• Terakhir ditinjau: 26 Oktober 2026.