Distributed Systems: Locks, Logical Clocks và Ordering

Safety:   Mutual exclusion — tại một thời điểm, chỉ 1 client hold lock
Liveness: Deadlock-free — client cuối cùng acquire được lock
          (kể cả client holding lock crash)
Fault-tolerance: Nếu N/2 nodes up → lock vẫn work

Acquire:
  SET lock:{resource} {unique_value} NX PX {ttl_ms}

  unique_value = UUID + client_id (để chỉ owner mới release được)
  NX = only if not exists
  PX = TTL in milliseconds

  Tại sao cần TTL?
  → Client crash → lock tự expire → không bị stuck forever

  Tại sao cần unique_value?
  → Phân biệt: lock của tôi hay của người khác?

Release (PHẢI atomic bằng Lua script):
  -- Chỉ xóa nếu value match (tôi là owner)
  if redis.call("get", KEYS[1]) == ARGV[1] then
      return redis.call("del", KEYS[1])
  else
      return 0
  end

  Tại sao Lua script?
  Without Lua:
    GET lock → value matches (still my lock)
    [GC pause, TTL expires, another client acquires lock]
    DEL lock → XÓA LOCK CỦA NGƯỜI KHÁC! ← race condition

  Lua script = atomic ở Redis → không có race condition

N = 5 independent Redis instances (không phải cluster/replica)

Acquire Redlock:

  1. t1 = current timestamp (milliseconds)

  2. Với mỗi Redis instance i (theo thứ tự):
     SET lock:{resource} {uuid} NX PX {lock_ttl}
     (dùng short timeout để không block quá lâu ở instance down)
     count++ nếu thành công

  3. t2 = current timestamp
     elapsed = t2 - t1
     validity_time = lock_ttl - elapsed - clock_drift_factor

  4. Nếu count >= 3 (majority) AND validity_time > 0:
     → Lock acquired! Hữu hiệu trong validity_time ms

  5. Nếu không:
     → Release tất cả instances đã acquired (cleanup)
     → Retry sau random delay

Release Redlock:
  Gửi Lua delete script đến TẤT CẢ 5 instances
  (kể cả instance failed — có thể recover sau, phải clean up)

Tại sao N=5 independent instances?
  Tolerate 2 failures (N/2 - 1 = 2)
  Không dùng master-replica: replica lag có thể leak lock
  Không dùng cluster: hash slots → lock có thể chỉ ở 1 node

Kleppmann's Critique (2016):

Scenario 1 — GC Pause:
  Client 1 acquires Redlock (validity = 10s)
  Client 1 bị GC pause 15 seconds
  Lock expires!
  Client 2 acquires lock (valid)
  Client 1 resumes → thinks it still holds lock
  → C1 và C2 CÙNG access resource!

Scenario 2 — Clock Jump:
  Client acquires lock trên Redis-A, B, C, D, E
  Redis-A admin thay đổi clock (NTP sync nhảy vọt)
  → Lock on Redis-A expires sớm hơn expected
  → Another client acquires lock on Redis-A, B, C
  → 6 clients cùng "hold" lock!

Sanfilippo's Defense:
  GC pause scenario: bounded GC pause + conservative TTL
  Clock jump: disable NTP large jumps, gradual clock adjustment
  Redlock cung cấp "reasonable" safety cho nhiều use cases

Kleppmann's conclusion:
  Redlock for "efficiency": OK (avoid duplicate work, occasional failures OK)
  Redlock for "correctness": NOT OK (use ZooKeeper + fencing token)

Fencing Token là giải pháp đúng đắn:
  Lock service trả về monotonic token khi grant lock
  Resource server: reject requests với token < last_seen_token
  → Dù lock expire và reassigned → old client's request rejected
  → TRUE mutual exclusion

etcd = strongly consistent (Raft-based) → phù hợp cho distributed locking

etcd Lock với Leases:

// Tạo lease với TTL
lease = etcd.grant_lease(ttl=30)

// Acquire lock
etcd.put(key="lock/resource", value=client_id, lease=lease.id,
         prev_kv=None)  // only if not exists

// Keep-alive: renew lease để giữ lock
goroutine {
    etcd.keep_alive(lease.id)  // gửi keep-alive mỗi TTL/3
}

// Release lock
etcd.delete(key="lock/resource")
etcd.revoke_lease(lease.id)

Ưu điểm vs Redlock:
  Raft consensus → strong safety guarantees
  Lease cấp fencing token (revision number)
  etcd revision là monotonic counter → dùng làm fencing token!

etcd Watch:
  Clients watch lock key
  Khi key bị delete → notification → retry acquire
  Sequential watches = fair lock (FIFO)

Tại sao không dùng wall clock?

Clock Drift:
  Hardware oscillator không chính xác tuyệt đối
  Drift ~1ms/second → ~86 seconds/day
  NTP sync: giảm drift nhưng không eliminate

Clock Skew:
  Hai machines có thể differ vài milliseconds đến vài seconds
  AWS machines: drift ~1ms typical, có thể lên 200ms+

  Machine A: event at t=1000ms
  Machine B: event at t=999ms (B's clock slightly behind)
  → Không thể biết event nào xảy ra trước!

Network Latency:
  Gửi timestamp: t=1000ms
  Message takes 100ms
  Receiver nhận: t=1100ms (nhưng local clock đã là 1050ms!)
  → Ai đúng?

Kết luận: Physical clocks KHÔNG reliable để order distributed events

"Time, Clocks, and the Ordering of Events in a Distributed System"
Bài báo được cite nhiều nhất trong distributed systems

Happens-Before (→) được định nghĩa:
  Rule 1: Trong cùng process: nếu a xảy ra trước b → a → b

  Rule 2: Message passing:
    Nếu a = "send message" và b = "receive message" → a → b
    (gửi phải xảy ra trước nhận)

  Rule 3: Transitivity:
    Nếu a → b và b → c → a → c

  Concurrent: nếu không có a → b NOR b → a
    → a và b là CONCURRENT (không liên quan nhân-quả)

Ví dụ:
  Process P: a → b → c
  Process Q: d → e → f
  Message: b → e (P sends, Q receives)

  Happens-before:
    a→b→c (P's local order)
    d→e→f (Q's local order)
    b→e (message)
    b→f (transitivity: b→e→f)
    a→e, a→f (transitivity: a→b→e→f)

  Concurrent pairs:
    a và d (no path between them)
    c và d, c và e, c và f

Mỗi process có một counter C (integer)

Rules:
  Rule 1: Trước mỗi event, increment counter:
    C = C + 1

  Rule 2: Khi gửi message m:
    C = C + 1
    gửi m với timestamp = C

  Rule 3: Khi nhận message m với timestamp T:
    C = max(C, T) + 1

Ví dụ:
  Process A (C_A)    Process B (C_B)    Process C (C_C)
  C_A=1: event a1    C_B=1: event b1    C_C=1: event c1
  C_A=2: send→B      C_B=2: event b2    C_C=2: send→B
  C_A=3: event a3    C_B=max(2,2)+1=3   C_C=3: event c3
                          receive from A
                     C_B=max(3,3)+1=4
                          receive from C
                     C_B=5: send→A

  A receive from B: C_A=max(3,5)+1=6

Lamport Clock Property:
  Nếu a → b thì C(a) < C(b)     [TRUE]
  Nếu C(a) < C(b) thì a → b     [FALSE!] ← KHÔNG đảm bảo

  Lamport clock chỉ capture happens-before in one direction
  Không phân biệt được concurrent events!

Total Order:
  Để total order: break ties bằng process ID
  (a, pid_A) < (b, pid_B) nếu C(a) < C(b) hoặc (C(a)==C(b) AND pid_A < pid_B)
  → Deterministic total order (nhưng arbitrary với concurrent events)

Lamport Clock:
  a → b ⟹ L(a) < L(b)         ✅
  L(a) < L(b) ⟹ a → b         ❌

Muốn: phát hiện CONCURRENT events!
  Vector Clock cho phép: V(a) < V(b) ⟺ a → b

Nếu V(a) không < V(b) AND V(b) không < V(a)
  → a và b là CONCURRENT ✅

N processes → mỗi process i có vector V_i = [0, 0, ..., 0] (N phần tử)

Rules:
  Rule 1: Trước event, increment own component:
    V_i[i] = V_i[i] + 1

  Rule 2: Khi gửi message:
    V_i[i] = V_i[i] + 1
    gửi message kèm V_i

  Rule 3: Khi nhận message với vector W:
    V_i[i] = V_i[i] + 1
    V_i[j] = max(V_i[j], W[j]) for all j ≠ i

Ví dụ (3 processes: A=0, B=1, C=2):

  A: [1,0,0] a1
  A: [2,0,0] send→B
  B: [0,1,0] b1
  B: [2,2,0] receive from A (max([2,0,0],[0,1,0])+1 at B)
  C: [0,0,1] c1
  C: [0,0,2] send→B
  B: [2,3,2] receive from C (max([2,2,0],[0,0,2])+1 at B)
  B: [2,4,2] send→A
  A: [3,4,2] receive from B

Comparison:
  V(a) < V(b) nếu V(a)[i] ≤ V(b)[i] for all i, và < cho ít nhất 1 i

  [2,2,0] vs [0,0,2]:
  [2,2,0][A]=2 > [0,0,2][A]=0 → không thể < theo A
  [0,0,2][C]=2 > [2,2,0][C]=0 → không thể < theo C
  → CONCURRENT! ✅ (B nhận từ A và C độc lập)

  [2,0,0] vs [2,2,0]:
  [2,0,0][A]=2 ≤ [2,2,0][A]=2 ✓
  [2,0,0][B]=0 ≤ [2,2,0][B]=2 ✓
  [2,0,0][C]=0 ≤ [2,2,0][C]=0 ✓
  → [2,0,0] < [2,2,0] → "send from A" → "receive at B" ✅

Amazon DynamoDB (original design, Dynamo paper 2007):
  Mỗi version của object có vector clock
  Conflict = concurrent writes → trả về cả hai → client reconcile

  get(key="cart") → [
    ({items:[A,B]}, VC=[{node1:2}]),
    ({items:[A,C]}, VC=[{node2:1}])  ← concurrent write!
  ]
  client: merge = {items:[A,B,C]} → put

Vấn đề với Vector Clocks trong practice:
  Size: O(N) với N = number của nodes
  Large clusters → vector clock lớn
  Giải pháp: Version Vectors (chỉ track nodes có writes)

Riak:
  Dùng Dotted Version Vectors (DVV) — improved version
  Giải quyết false conflicts từ Vector Clocks

Git:
  Tương tự vector clocks
  Merge conflicts khi concurrent edits → manual resolve

Vector Clock: track causality của events (operations)
Version Vector: track causality của values (data versions)

Subtle difference:
  VC: gắn với operations/messages
  VV: gắn với data replicas/values

Practical difference:
  VC có thể có false conflicts nếu không cẩn thận
  VV được thiết kế đặc biệt cho tracking data versions

Dotted Version Vectors (DVV):
  Giải quyết "sibling explosion" trong Riak
  Mỗi version có: base (VV) + dot (specific event)
  → Phân biệt chính xác concurrent vs sequential writes

Lamport / Vector Clocks:
  Không correlate với physical time
  Không thể hỏi "events trong khoảng 12:00-13:00"
  Debugging khó (timestamps vô nghĩa)

Physical Clocks:
  Không đảm bảo causality
  Clock skew → wrong ordering

HLC: kết hợp tốt nhất của cả hai!
  Correlate với physical time (NTP-based)
  Đảm bảo: nếu a → b thì HLC(a) < HLC(b)
  HLC values gần với physical time

Mỗi node có:
  l: "logical" part (max physical time seen)
  c: counter (tie-breaker khi l bằng nhau)

On local event:
  l' = max(l, pt)  (pt = physical time now)
  if l' == l: c = c + 1
  else: l = l', c = 0

On send:
  same as local event, gửi (l, c)

On receive(l_m, c_m):
  l' = max(l, l_m, pt)
  if l' == l == l_m: c = max(c, c_m) + 1
  elif l' == l: c = c + 1
  elif l' == l_m: c = c_m + 1
  else: c = 0
  l = l'

HLC timestamp = (l, c)
Comparison: (l1, c1) < (l2, c2) nếu l1 < l2 hoặc (l1 == l2 AND c1 < c2)

Guarantee:
  Nếu a → b: HLC(a) < HLC(b)  ✅
  HLC(a) ≈ physical_time(a) (bounded skew)  ✅

Used in: CockroachDB, YugabyteDB