Logical Clocks, Vector Clocks, and Hybrid Logical Clocks (HLC) TODO
Concept
In a distributed setting you can't assume a fully synchronized global physical clock, so event order is defined through causality instead. A Lamport clock has each node keep a counter, incrementing it on every local event and updating it to max(mine, received)+1 on message receipt; if a causes b, then C(a) < C(b) is guaranteed, but the converse doesn't hold, so it can't distinguish concurrency. A vector clock carries an array of counters, one per node, and can precisely tell whether two events are causally ordered or concurrent — but its metadata size scales with the number of nodes, hurting scalability. A hybrid logical clock (HLC) combines physical time and a logical counter into one value, producing a monotonically increasing timestamp that stays close to physical time without violating causality. Because causal order survives clock skew and the value stays close to a human-readable time, HLCs are used as version timestamps in distributed databases.
Sorting logs from multiple nodes by physical time can make cause and effect look reversed, and whether you can even detect concurrent-update conflicts ultimately comes down to which clock you use.
Code & Formula
# 논리 시계·벡터 시계 — 벡터 시계로 두 이벤트가 인과적으로 순서가 있는지, 동시(concurrent)인지 판별한다.
# Lamport 시계는 동시성을 구분 못하지만, 벡터 시계는 노드별 카운터 배열로 정확히 판별한다.
class VectorClock:
def __init__(self, node_id, n_nodes):
self.node_id = node_id
self.clock = [0] * n_nodes
def local_event(self):
self.clock[self.node_id] += 1
return tuple(self.clock)
def send(self):
self.clock[self.node_id] += 1
return tuple(self.clock)
def receive(self, remote_clock):
self.clock = [max(a, b) for a, b in zip(self.clock, remote_clock)]
self.clock[self.node_id] += 1
return tuple(self.clock)
def compare(vc_a, vc_b):
"""a <= b 성분별 비교로 인과 순서 또는 동시성을 판별"""
le = all(a <= b for a, b in zip(vc_a, vc_b))
ge = all(a >= b for a, b in zip(vc_a, vc_b))
if vc_a == vc_b:
return "동일 이벤트"
if le:
return "a -> b (a가 b의 원인)"
if ge:
return "b -> a (b가 a의 원인)"
return "concurrent (동시, 인과관계 없음)"
n = 3
node0, node1, node2 = VectorClock(0, n), VectorClock(1, n), VectorClock(2, n)
e1 = node0.local_event() # node0: [1,0,0]
msg = node0.send() # node0: [2,0,0]
e2 = node1.receive(msg) # node1: [2,1,0] <- node0 인과적으로 앞섬
e3 = node2.local_event() # node2: [0,0,1] <- node0/node1과 무관하게 독립 발생
print(f"e1 (node0 local) = {e1}")
print(f"e2 (node1, e1 이후 수신) = {e2}")
print(f"e3 (node2 독립 이벤트) = {e3}")
print(f"\ncompare(e1, e2) = {compare(e1, e2)}") # e1이 e2의 원인
print(f"compare(e1, e3) = {compare(e1, e3)}") # concurrent
print(f"compare(e2, e3) = {compare(e2, e3)}") # concurrent
docs/code/algorithms/algorithms-53.py
Exercise
Write a simulation of 3 nodes exchanging messages, attach both a Lamport clock and a vector clock to the same run, and find event pairs that only the vector clock identifies as concurrent.
Practical Connection
In a matching service where multiple instances accept orders, determining which order came first by each server's physical clock gets the order reversed by skew, which is exactly why you need a single sequencer or a causal timestamp like HLC.
Where it lands in Jayverse
- Verex: adopt a single sequencer or HLC-stamped events for the matching service. Write a test that deliberately induces clock skew across API instances and confirms order sequencing never reverses.
- Devnet: use devnet as the fixture for the 3-node concurrency exercise. Run multiple matching-API instances against the shared devnet chain and find the event pairs only a vector clock or HLC would catch, before production traffic does.
- gitboard: expose HLC drift as a health metric. A growing gap between logical and physical time is the early signal that skew is approaching what the matching engine assumes it can tolerate.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| hurt scalability | 확장성을 해치다 · 노드 수가 늘수록 오버헤드가 커져 시스템이 커지기 힘들어질 때. "scales with the number of nodes, hurting scalability" |
| stay close to | ~에 가깝게 유지되다 · 논리 시계 값이 실제 물리 시간과 크게 어긋나지 않을 때. "stays close to physical time" |
| survive (clock skew) | (오차·왜곡을) 견뎌내다, 살아남다 · 시계가 어긋나도 인과 순서가 무너지지 않을 때. "causal order survives clock skew" |
| come down to | 결국 ~로 귀결되다 · 여러 요인을 정리하면 결국 하나의 선택 문제로 좁혀질 때. "ultimately comes down to which clock you use" |
| look reversed | (실제와 반대로) 뒤바뀐 것처럼 보이다 · 원인과 결과의 순서가 잘못 정렬되어 보일 때. "can make cause and effect look reversed" |
| skew (n.) | (시계·시간의) 오차, 어긋남 · 서버 간 물리 시계가 서로 안 맞는 정도. "gets the order reversed by skew" |
| the converse doesn't hold | 그 역은 성립하지 않는다 · 한쪽 방향은 참이지만 반대 방향은 참이 아닐 때. "but the converse doesn't hold" |
| HLC | 하이브리드 논리 시계(Hybrid Logical Clock) · 물리 시간과 논리 카운터를 결합해 인과성을 지키면서 물리 시간에 가까운 타임스탬프를 만드는 기법, 분산 DB의 버전 타임스탬프로 쓰임. "HLCs are used as version timestamps in distributed databases" |
| Lamport clock | 램포트 시계 · 각 노드가 카운터를 증가시키며 인과관계는 보장하지만 동시성은 구분 못 하는 논리 시계. "A Lamport clock has each node keep a counter" |
| vector clock | 벡터 시계 · 노드마다 카운터 배열을 두어 두 이벤트가 인과적으로 순서가 있는지 동시적인지 정확히 판별하지만, 메타데이터가 노드 수에 비례해 커지는 논리 시계. "A vector clock carries an array of counters, one per node" |
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.