线性一致性:
Client A: write(X=1) ──── 成功 ────→
                              ↓ 全局时间点 t
Client B:          read(X) ── 返回 1 ──→

所有节点在 t 之后都能读到 X=1
操作的效果看起来是在 t 时刻瞬间完成的

实现代价:
- 需要协调多数节点（如 Paxos/Raft）
- 延迟至少为一次网络往返
- 分区时可能不可用

顺序一致性 vs 线性一致性:

顺序一致性: 操作有全局顺序，但顺序不一定与实时时间一致
线性一致性: 全局顺序必须与实时时间一致

示例:
Client A: write(X=1) at time 100
Client B: write(X=2) at time 200

顺序一致性允许: 全局顺序为 X=2, X=1 (只要所有节点看到相同顺序)
线性一致性不允许: 因为 X=2 的写入时间晚于 X=1，全局顺序必须是 X=1, X=2

因果关系:
A: write(X=1)
    ↓ (因果依赖)
B: read(X=1), write(Y=2)
    ↓ (因果依赖)
C: read(Y=2)

因果一致性保证: 如果 A 发生在 B 之前，所有节点都先看到 A 的效果再看到 B 的效果

并发事件:
A: write(X=1)  ─┐
                 ├→ 这两个事件是并发的，没有因果关系
B: write(Y=2)  ─┘
因果一致性允许: 不同节点可能以不同顺序看到 X=1 和 Y=2

向量时钟: [N_A, N_B, N_C]  (每个节点一个计数器)

事件发生时: 本地计数器 +1
收到消息时: 每个分量取 max，然后本地计数器 +1

示例:
A: [1,0,0] → 发送消息 → B
B: 收到后 [1,1,0] → 发送消息 → C
C: 收到后 [1,1,1]

比较:
[1,0,0] < [1,1,0] → 因果关系 (A 发生在 B 之前)
[1,0,0] vs [0,1,0] → 并发 (无法比较)

读己之所写 (Read Your Writes):
- 客户端写入后，后续读取一定能看到自己的写入
- 实现: 客户端携带版本号，读时等待版本 ≥ 写入版本

单调读 (Monotonic Reads):
- 客户端一旦读到某个值，后续读取不会读到更旧的值
- 实现: 将客户端绑定到特定节点，或携带版本号

单调写 (Monotonic Writes):
- 一个客户端的写入不会在后续写入之后被覆盖
- 实现: 将同一客户端的写入路由到同一节点

一致前缀读 (Consistent Prefix Reads):
- 读取结果一定是某个写入序列的前缀
- 实现: 保证写入按顺序传播

class VectorClock:
    def __init__(self, nodes):
        self.clock = {node: 0 for node in nodes}

    def increment(self, node):
        self.clock[node] += 1

    def merge(self, other):
        for node in self.clock:
            self.clock[node] = max(self.clock[node], other.clock[node])

    def compare(self, other):
        """返回: 'happened_before', 'happened_after', 'concurrent', 'equal'"""
        le = ge = False
        for node in self.clock:
            if self.clock[node] < other.clock[node]:
                le = True
            elif self.clock[node] > other.clock[node]:
                ge = True
        if not le and not ge:
            return 'equal'
        elif le and not ge:
            return 'happened_before'
        elif ge and not le:
            return 'happened_after'
        else:
            return 'concurrent'

    def __repr__(self):
        return str(self.clock)

# 使用示例
vc_a = VectorClock(['A', 'B', 'C'])
vc_a.increment('A')  # A 的事件: [1,0,0]

vc_b = VectorClock(['A', 'B', 'C'])
vc_b.merge(vc_a)
vc_b.increment('B')  # B 收到 A 的消息: [1,1,0]

print(vc_a.compare(vc_b))  # 'happened_before'

vc_c = VectorClock(['A', 'B', 'C'])
vc_c.increment('C')  # C 独立事件: [0,0,1]
print(vc_a.compare(vc_c))  # 'concurrent'