KAL
Menu

Waktu dan Pengurutan

Clock skew, jam Lamport, dan hybrid logical clock untuk mengurutkan peristiwa.

Daftar isi

Topik ini membahas waktu sebagai sumber kebenaran yang rapuh pada sistem terdistribusi. Pembahasan dimulai dari clock skew yang membuat jam fisik antarnode tidak dapat dibandingkan langsung, dilanjutkan dengan jam Lamport yang mengurutkan peristiwa secara causal, dan diakhiri hybrid logical clock yang menyimpan komponen fisik sekaligus logika. Dua simulasi Python dan satu diagram ruang waktu memperlihatkan mekanismenya sampai ke angkanya.

Clock skew dan batas jam fisik#

Clock skew adalah selisih waktu antara dua jam pada saat yang sama, dan selisih itu dijamin ada. Jam kristal pada mesin yang berbeda berjalan dengan laju yang sedikit berbeda, sehingga keduanya saling menjauh seiring waktu. Protokol NTP (Network Time Protocol) menyelaraskan jam mesin dengan server referensi, tetapi hasil penyelarasan itu berhenti pada tingkat milidetik dan kadang diterapkan dengan lompatan yang menggerakkan jam mundur. Pada klaster yang tersebar antarwilayah, selisih antarnode dapat mencapai puluhan milidetik tanpa ada yang salah pada masing-masing node.

Akibatnya, dua stempel waktu fisik dari node berbeda tidak dapat diurutkan dengan pasti. Tulisan yang secara sebab-akibat terjadi sesudah dapat membawa stempel yang tampak lebih tua, dan tidak ada pemeriksaan lokal yang dapat menemukan kekeliruan itu. Keadaan ini bukan kegagalan langka, melainkan kondisi kerja biasa yang harus diantisipasi desain. Aturan praktisnya, stempel waktu fisik cukup untuk kebutuhan tampilan dan pemecahan berkas log, tetapi tidak cukup untuk menentukan urutan kejadian di antara node yang berbeda.

Jam Lamport#

Jam Lamport mengganti pertanyaan “berapa jam sekarang” dengan “peristiwa mana yang dijamin lebih dahulu”. Setiap proses menyimpan satu penghitung dengan tiga aturan: peristiwa lokal menaikkan penghitung sebesar satu, pesan keluar membawa stempel jam pengirimnya, dan penerima menetapkan jamnya menjadi maksimum antara jam sendiri dan stempel pesan, lalu menaikkan satu. Dengan aturan itu, apabila peristiwa a memengaruhi peristiwa b secara causal, jam a pasti lebih kecil daripada jam b. Urutan yang dijamin inilah yang disebut urutan causal, dan jam Lamport tidak pernah melanggarnya.

Simulasi berikut menjalankan jadwal delapan peristiwa pada tiga proses, termasuk tiga pengiriman pesan. Stempel yang dibawa setiap pesan tercetak pada kolom peristiwa, dan kolom jam menunjukkan nilai penghitung proses setelah peristiwanya selesai.

python jam-lamport.py 
# Simulasi jam Lamport pada tiga proses.
# Event lokal dan pengiriman pesan menaikkan jam sebesar satu.
# Pesan membawa stempel waktunya, dan penerima mengambil nilai
# maksimum antara jamnya sendiri dengan stempel pesan, lalu menaikkan satu.

jam = {"P1": 0, "P2": 0, "P3": 0}
pesan = None   # stempel waktu pesan yang sedang dalam perjalanan

jadwal = [
    ("P1", "lokal",  None),
    ("P1", "kirim",  "P2"),
    ("P2", "terima", "P1"),
    ("P3", "lokal",  None),
    ("P2", "kirim",  "P3"),
    ("P3", "terima", "P2"),
    ("P1", "kirim",  "P3"),
    ("P3", "terima", "P1"),
]

print(f"{'Proses':<7}{'Peristiwa':<30}{'Jam'}")

for proses, aksi, lawan in jadwal:
    if aksi == "lokal":
        jam[proses] += 1
        ket = "event lokal"
    elif aksi == "kirim":
        jam[proses] += 1
        pesan = jam[proses]
        ket = f"kirim ke {lawan} (stempel {pesan})"
    else:
        jam[proses] = max(jam[proses], pesan) + 1
        ket = f"terima dari {lawan} (stempel {pesan})"
    print(f"{proses:<7}{ket:<30}{jam[proses]:>3}")

print()
print("Jam akhir:", jam)
text Keluaran 
Proses Peristiwa                     Jam
P1     event lokal                     1
P1     kirim ke P2 (stempel 2)         2
P2     terima dari P1 (stempel 2)      3
P3     event lokal                     1
P2     kirim ke P3 (stempel 4)         4
P3     terima dari P2 (stempel 4)      5
P1     kirim ke P3 (stempel 3)         3
P3     terima dari P1 (stempel 3)      6

Jam akhir: {'P1': 3, 'P2': 4, 'P3': 6}
P1P2P312334156
Diagram ruang waktu jam Lamport pada tiga proses

Keluaran dan diagram memperlihatkan aturan maksimum yang bekerja. P2 naik ke 3 setelah menerima stempel 2 dari P1, dan P3 naik ke 5 setelah menerima stempel 4 dari P2. Sebaliknya, baris keenam dan ketujuh memperlihatkan batas kekuatan jam ini: P1 mengirim dengan stempel 3 setelah P3 sudah berada di 5, karena peristiwa pada proses yang tidak bertukar pesan tidak saling memengaruhi. Apabila jam a lebih kecil daripada jam b, a belum tentu penyebab b, sehingga urutan jam Lamport menjamin sebab-akibat satu arah saja.

Hybrid logical clock#

Jam Lamport murni meninggalkan kebutuhan lain: nilainya tidak berhubungan dengan waktu nyata, sehingga pertanyaan seperti peristiwa pada jendela lima menit terakhir atau pembersihan data yang kedaluwarsa tidak dapat dijawab dengannya. Jam fisik murni menjawab pertanyaan itu, tetapi ambigu pada clock skew sebagaimana dibahas di awal. Hybrid logical clock (HLC) mengambil keduanya dengan stempel berupa pasangan nilai, yaitu komponen fisik yang mengikuti jam mesin dan komponen logika yang naik setiap kali ada peristiwa dengan komponen fisik yang sama.

Simulasi berikut mengulang skenario skew yang menyesatkan. Node A menulis pada jam fisiknya 100, lalu node B yang jamnya tertinggal menerima perubahan itu pada jam fisiknya 97. Urutan fisik menyatakan tulisan B lebih tua, padahal B justru menerima datanya dari A. HLC mengambil maksimum komponen fisik dari kedua sumber dan menaikkan komponen logikanya, sehingga urutan sebab-akibat tetap terbaca.

python hlc.py 
# Perbandingan pengurutan berbasis jam fisik dengan hybrid logical clock.
# Jam node B tertinggal dari node A, sehingga stempel fisiknya
# menyesatkan, sedangkan HLC menyimpan komponen logika tambahan.

def hlc_awal(waktu_fisik):
    return (waktu_fisik, 0)

def hlc_terima(stempel_lokal, stempel_pesan, waktu_fisik):
    l_lokal, c_lokal = stempel_lokal
    l_pesan, c_pesan = stempel_pesan
    l = max(l_lokal, l_pesan, waktu_fisik)
    if l == l_lokal and l == l_pesan:
        c = max(c_lokal, c_pesan) + 1
    elif l == l_lokal:
        c = c_lokal + 1
    elif l == l_pesan:
        c = c_pesan + 1
    else:
        c = 0
    return (l, c)

def lebih_dulu(x, y):
    return x[0] < y[0] or (x[0] == y[0] and x[1] < y[1])

node_a = hlc_awal(100)
node_b_lokal = hlc_awal(95)
node_b = hlc_terima(node_b_lokal, node_a, 97)

print("Node A menulis pada jam fisik 100, stempel HLC:", node_a)
print("Node B menerima pada jam fisik 97, stempel HLC:", node_b)
print("Menurut jam fisik: 97 < 100, tulisan B tampak lebih tua")
print("Menurut HLC      :", node_a, "sebelum", node_b)
print("Pemeriksaan urutan HLC (A sebelum B):", lebih_dulu(node_a, node_b))
text Keluaran 
Node A menulis pada jam fisik 100, stempel HLC: (100, 0)
Node B menerima pada jam fisik 97, stempel HLC: (100, 1)
Menurut jam fisik: 97 < 100, tulisan B tampak lebih tua
Menurut HLC      : (100, 0) sebelum (100, 1)
Pemeriksaan urutan HLC (A sebelum B): True

Stempel HLC tetap dekat dengan waktu nyata karena komponen fisiknya ikut naik bersama jam mesin, sehingga pemindaian jendela waktu tetap dapat dilakukan. Pada saat yang sama, komponen logikanya menjaga urutan causal seperti jam Lamport. Sifat ganda itulah yang membuat HLC dipakai pada basis data terdistribusi yang perlu mengurutkan event sekaligus menjawab pertanyaan berbasis jendela waktu.

Kesalahan umum#

Kesalahan pertama adalah mengurutkan event antarnode dengan membandingkan stempel waktu fisiknya. Penyebabnya adalah mengasumsikan jam yang disinkronkan NTP sudah sama persis, padahal clock skew tetap ada sampai batas milidetik. Perbaikannya adalah jam Lamport atau HLC untuk keputusan urutan, dan jam fisik hanya untuk kebutuhan tampilan.

Kesalahan kedua adalah memperlakukan jam Lamport sebagai waktu nyata. Nilai 6 pada simulasi bukan detik atau milidetik, melainkan penghitung peristiwa, sehingga pertanyaan jendela waktu tidak dapat dijawab dengannya. Perbaikannya adalah HLC bila kedua kebutuhan urutan dan jendela waktu ada sekaligus.

Kesalahan ketiga adalah memercayai penyesuaian NTP secara mutlak. Lompatan jam mundur dan kegagalan server referensi adalah kondisi yang pernah terjadi secara luas, sehingga stempel fisik bisa mundur di tengah operasi. Perbaikannya adalah merancang pengurutan yang tidak bergantung pada arah jam fisik, sebagaimana pola di atas.

Ringkasan#

  • Clock skew membuat stempel waktu fisik antarnode tidak dapat dibandingkan untuk keputusan urutan, karena tulisan yang lebih baru secara causal dapat membawa stempel yang lebih tua.
  • Jam Lamport menjamin urutan causal satu arah dengan penghitung per proses dan aturan maksimum pada penerimaan pesan, tetapi nilainya tidak berhubungan dengan waktu nyata.
  • Hybrid logical clock menyimpan pasangan komponen fisik dan logika, sehingga menjaga urutan causal sekaligus mendukung pemindaian berbasis jendela waktu.

Referensi#