Lamport Clock — distributed tizimdagi hodisalarning sababiy tartibini ifodalash uchun har process yuritadigan mantiqiy hisoblagich. U fizik vaqtni o‘lchamaydi. Maqsad turli node’larda yuz bergan eventlar uchun “oldin sodir bo‘lgan” munosabatiga mos timestamp yaratish.
Lamport Clock distributed system nazariyasida logical clockning asosiy ko‘rinishidir.
Fizik soat muammosi
Turli serverlarning real soatlari mukammal sinxron emas.
Muammolar:
Ikki log timestampi qaysi event sabab va qaysi biri natija ekanini aniq ko‘rsatmasligi mumkin.
Happened-before
Lamport Clock happened-before munosabatiga tayanadi.
a → b quyidagi holatlarda:
- a va b bir processda, a oldin bajarilgan;
- a message yuborish, b shu message’ni qabul qilish;
- transitiv ravishda a → c va c → b.
Bu sababiy tartibni ifodalaydi.
Local counter
Har process integer counter saqlaydi.
Masalan:
P1 clock = 0
P2 clock = 0
Har local eventdan oldin yoki event vaqtida counter oshiriladi.
Timestamp eventga biriktiriladi.
Local event qoidasi
clock = clock + 1
Masalan, P1:
event A → 1
event B → 2
Shu process ichida timestamp tartibi execution tartibiga mos.
Message yuborish
Process message yuborishdan oldin clockni oshiradi.
Message bilan current logical timestamp yuboriladi.
Masalan:
P1 clock = 3
send(message, timestamp=3)
Message qabul qilish
Receiver message timestampi tni oladi.
U o‘z clockini:
max(local_clock, t) + 1
qiymatiga o‘rnatadi.
Shunda send event timestampi receive event timestampidan kichik bo‘ladi.
Misol
P1:
A: clock 1
send M: clock 2
P2 local clocki 5 bo‘lsa, M timestamp 2 bilan keladi:
receive M: max(5, 2) + 1 = 6
Receive event 6 timestamp oladi.
Asosiy xususiyat
Agar:
a → b
bo‘lsa:
L(a) < L(b)
bo‘ladi.
Lekin teskarisi har doim to‘g‘ri emas.
L(a) < L(b) bo‘lsa a albatta bga sabab bo‘lgan degani emas.
Concurrent event
Ikki event o‘rtasida happened-before relation bo‘lmasa ular concurrent.
Lamport timestamp ularga baribir turli son berishi mumkin.
Faqat scalar clock concurrentlikni aniq aniqlay olmaydi.
Buning uchun Vector Clock kuchliroq ma’lumot beradi.
Total order
Lamport timestampga process ID qo‘shib deterministic total order yaratish mumkin.
Masalan:
(timestamp, process_id)
Avval timestamp, teng bo‘lsa process ID solishtiriladi.
Bu barcha eventlarni bir tartibga qo‘yadi.
Ammo bu total order barcha eventlar orasida haqiqiy sababiy bog‘lanish bor degani emas.
Distributed mutual exclusion
Lamport timestamp requestlarni tartiblash uchun ishlatilishi mumkin.
Node’lar critical section requestlarini:
timestamp + process ID
bo‘yicha queue qiladi.
Message va acknowledgement protokoli bilan bir vaqtda bitta node kirishi ta’minlanadi.
Node failure va membership alohida boshqariladi.
Event ordering
Distributed log va replicated operationlar uchun logical timestamp tie-breaker sifatida ishlatilishi mumkin.
Masalan, ikki update’ni deterministic tartibga qo‘yish.
Lekin “katta timestamp yutadi” business conflictni to‘g‘ri hal qilishini kafolatlamaydi.
Causality
Lamport Clock sababiy tartibni hurmat qiladi, ammo causality’ni to‘liq qayta tiklamaydi.
A va B timestampi turli bo‘lsa ham ular mustaqil eventlar bo‘lishi mumkin.
Vector Clock har process componenti orqali concurrent eventlarni ajratishi mumkin.
Clock initialization
Process clock odatda noldan boshlanadi.
Restartdan keyin oldingi eventlar bilan collision bo‘lmasligi uchun:
talab qilinishi mumkin.
Faqat noldan boshlash eski message bilan tartib muammosi yaratadi.
Overflow
Counter cheklangan integer bo‘lsa juda uzoq ishlaydigan tizimda overflow nazariy muammo.
Katta integer, epoch yoki reset protocol ishlatiladi.
Reset barcha node bilan coordination talab qilishi mumkin.
Message duplication
Ayni message ikki marta qabul qilinsa har receive local clockni oshiradi.
Lamport Clock duplicate’ni aniqlamaydi.
Message ID va deduplication alohida mexanizm.
Message delay
Juda eski message keyin kelishi mumkin.
Receiver max() qoidasi sabab clock orqaga qaytmaydi.
Eski message yangi local timestamp oladi.
Bu physical event time’ni emas, receive causality’ni ifodalaydi.
Lamport Clock va Physical Clock
Lamport Clock:
- interval o‘lchamaydi;
- sana bermaydi;
- timeout uchun ishlatilmaydi;
- causality orderini beradi.
Physical clock:
- real vaqt;
- deadline;
- timestamp;
- duration
uchun.
Ko‘p tizim Hybrid Logical Clock kabi ikkala yondashuvni birlashtiradi.
Log tahlili
Distributed trace’da logical timestamp event orderini tushunishga yordam beradi.
Ammo trace context, span parent va physical vaqt ham kerak.
Lamport timestamp qaysi request qaysi messagega tegishli ekanini o‘zi ko‘rsatmaydi.
Bir xil timestamp
Ikki process mustaqil ravishda bir xil scalar timestamp yaratishi mumkin.
Shuning uchun total order uchun process ID yoki node ID qo‘shiladi.
Bu pair unique bo‘lishi kerak.
Database version
Logical counter record versioni sifatida ishlatilishi mumkin.
Update katta version bilan kelsa qabul qilinadi.
Ammo ikki mustaqil write orasidagi causality noma’lum bo‘lsa scalar version ulardan birini arbitrary ravishda ustun qo‘yadi.
Hybrid Logical Clock
Hybrid Logical Clock fizik vaqtga yaqin timestamp va logical counter’ni birlashtiradi.
U causality tartibini saqlashga intilib, vaqtga yaqin sortable qiymat beradi.
Clock skew va overflow qoidalari alohida boshqariladi.
Bog‘liq tushunchalar
Logical clock, Happened-before, Causality, Distributed system, Vector Clock, Hybrid Logical Clock, Total order, Message ordering, Clock skew, Event