知识卡片
并发与版本向量
无主复制下多个客户端可能并发写同一个键,即使有严格的法定人数也无法避免——问题 根源是网络延迟和部分故障导致不同节点看到写入的顺序不同,如果每个节点只是简单地 拿后到的写入覆盖先到的,各副本会永久停留在不一致的最终值上。要正确处理,先要精确 定义”并发”:如果操作B在执行时知道、依赖于、或建立在操作A之上,就说A在B”此前发生”; 如果两个操作互相都不知道对方的存在,就说它们是并发的——这个定义完全不依赖两者 物理时间上是否重叠,而只取决于信息上是否互相可知:即使两个操作物理时间上有间隔, 只要网络延迟或中断阻止一方获知另一方的存在,它们依然算并发。捕获这种关系的算法是: 服务器给每个键维护一个版本号,每次写入递增;客户端读取时拿到当前所有未被覆盖的值 及最新版本号;客户端写入时必须带上之前读到的版本号,并把之前读到的所有值合并进 新写入;服务器收到带某版本号的写入时,可以覆盖该版本号或更低版本的所有值(因为 已被合并进新值),但必须保留版本号更高的值(因为它们和这次写入是并发的、不能被 覆盖)。购物车场景中,这意味着并发添加的商品都会被保留成”兄弟”(siblings),客户端 需要负责合并这些兄弟(比如取并集),如果要支持删除,被删除的项不能直接消失,而要 留一个带版本号的删除标记(墓碑),否则合并兄弟时删掉的项会诡异地重新出现。当有 多个副本、每个副本都能独立接受写入时,单一版本号不够用,需要给每个副本单独维护 一个版本号,所有副本版本号的集合构成版本向量,用来在多副本场景下精确区分”覆盖写入” 和”并发写入”。
结构图:
flowchart LR
A[操作B执行时知道/依赖A] --> B[A此前发生于B]
C[两操作互不知道对方存在] --> D[并发, 与物理时间重叠与否无关]
E[服务器为键维护版本号] --> F[客户端写入须带上次读到的版本号]
F --> G[覆盖同版本或更低版本的值]
F --> H[保留更高版本的并发值 = 兄弟siblings]
H --> I[客户端负责合并兄弟, 删除需墓碑标记]
J[多副本场景] --> K[每副本各自维护版本号=版本向量]
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 第五章:复制
原书出处 · 1 处
- 第五章:复制 · 查看原书依据
为了定义并发性,确切的时间并不重要:如果两个操作都意识不到对方的存在,就称这两个操作并发,而不管它们发生的物理时间。