18 · 一致性：分清实时顺序与因果顺序
目标：从调用历史判断一个读写寄存器是否满足线性一致性。
给每次操作找一个生效点
线性一致性（linearizability）要求每次操作看起来在调用与返回之间的某个瞬间生效，并遵守真实时间约束：若写入已经返回，之后才发起的读取不能再看到被它替代的旧值，除非中间又有新的写入。
并发操作的区间重叠时，通常有多个可接受顺序。但一旦某次读取已观察到新值，后来发起的读取不能退回旧值。可串行化主要约束事务效果是否等价于某个串行顺序；严格可串行化还保留事务间实时先后。它们描述的对象与限制要分清。
本课检查单个初值为 0 的读写寄存器。它没有事务、CAS 或数据库快照，只足以检查这种模型的有限历史。
枚举可能的顺序
保存 consistency.py。每个操作记录类型、值、开始与结束时刻。先判断与写入重叠的旧值读取是否可能合法。
from itertools import permutations
def linearizable(history):
for order in permutations(range(len(history))):
position = {op: i for i, op in enumerate(order)}
violates_time = any(
a[3] < b[2] and position[i] > position[j]
for i, a in enumerate(history) for j, b in enumerate(history)
)
if violates_time:
continue
value, valid = 0, True
for i in order:
kind, arg, start, end = history[i]
if kind == "write":
value = arg
elif arg != value:
valid = False
break
if valid:
return True
return False
overlap = [("write", 1, 1, 4), ("read", 0, 2, 3)]
regression = [("write", 1, 1, 2), ("read", 1, 3, 4), ("read", 0, 5, 6)]
assert linearizable(overlap)
assert not linearizable(regression)
print("overlap_valid:", linearizable(overlap))
print("regression_valid:", linearizable(regression))
uv run --python 3.12 --no-project consistency.py
预期输出：
overlap_valid: True
regression_valid: False
第一段可以把读取排在写入前，同时让两者各自的生效点落在调用区间中。第二段没有任何合法重排能解释末尾的 0。算法枚举阶乘数量的顺序，因此只用于很小的完整历史；真实验证器还需处理未完成操作、规模和更复杂语义。
引导修改：① 把第二段最后一次读取值改成 1；② 断言应改为合法；③ 再把读取保持 0，但增加一条在它之前已完成的 write 0，也可以合法。检查必须考虑完整历史，不能只凭两条日志判错。
有序 ID 不是全部答案
Lamport 时钟在本地事件上递增，接收消息时取 max(本地, 消息)+1，保证因果先发生的事件得到更小时间戳；反向推论不成立，小时间戳不证明有因果关系。混合逻辑时钟把物理时间与逻辑计数组合，仍需明确误差和语义。唯一 ID、有序 ID 与线性一致的 ID 分配是不同要求。
CAP 中的 C 指线性一致性；发生网络分区时，不能同时让每个非故障节点都及时响应所有操作且继续保证这种一致性。分区不是日常菜单上的可关闭选项，正常情况下的延迟和一致性取舍也不会被一句“三选二”解释完。可以按接口选择策略，例如报名确认暂停、普通列表提供注明滞后的结果。
独立练习：主节点确认报名后隔离，一侧只有旧副本。该副本应如何响应“我刚才是否报名成功”，才能保住线性一致承诺？
参考答案
如果无法验证最新权威状态，就等待或返回明确不可用/结果待核实，不能用旧副本返回“未报名”并声称满足承诺。前端可保留先前收到的报名凭证，但这不使后端旧副本变成线性一致。若产品允许旧读，必须把该接口承诺改为较弱模型。
验证结果不符合直觉时，先检查区间是否真的重叠、值是否来自同一个键。客户端不同机器的时间戳可能不能直接当真实全局顺序，历史采集也要有可靠方法。在 design.md 为报名确认、浏览和日报分别命名一致性要求。