知识卡片
用此前发生关系而非物理时间定义并发及版本向量的作用
内容
无主复制下多个客户端可能并发写同一个键,即使有严格的法定人数也无法避免——问题 根源是网络延迟和部分故障导致不同节点看到写入的顺序不同,如果每个节点只是简单地 拿后到的写入覆盖先到的,各副本会永久停留在不一致的最终值上。要正确处理,先要精确 定义”并发”:如果操作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[每副本各自维护版本号=版本向量]
参考来源
- 位置:《数据密集型应用系统设计》第五章《复制》"此前发生的关系和并发""捕获此前
发生关系""合并同时写入的值""版本向量"(源文件:_epub-src/ch5_split_005.html)
- 结论依据:原文定义"如果操作B了解操作A,或者依赖于A……则操作A在另一个操作B之前
发生",并说明两个操作都不知道对方即为并发,详述基于版本号的读写合并算法及墓碑
删除标记,以及多副本场景需要版本向量,直接支撑本卡片的结构梳理。
- 原始内容:如果操作B了解操作A,或者依赖于A,或者以某种方式构建于操作A之上,则
操作A在另一个操作B之前发生……如果两个操作都不知道另一个存在,就称这两个操作
并发……客户端写入键时,必须包含之前读取的版本号,并且必须将之前读取的所有值
合并在一起……所有副本的版本号集合称为版本向量。