知识卡片
时间戳排序避环
内容
CockroachDB 用事务时间戳约束冲突方向，只允许冲突图按时间戳单向增长，从而避免 serializability graph 成环。发散：可串行化不一定靠锁等待实现，也可以靠检测、回滚和重试维护顺序。
参考来源
- 位置：《分布式系统与一致性》第9章《分布式数据库CockroachDB》"1.serializability理论和timestamp ordering技术"一节（源文件：_epub-src/OEBPS/Text/chapter13.xhtml）
- 结论依据：原文明确"根据serializability理论，如果serializability graph无环就能保证事务的执行是可串行化的"，CockroachDB的做法是"只允许与较早的时间戳发生冲突的操作存在，不允许与较晚的时间戳发生冲突的操作存在……这种timestamp ordering技术可以保证serializability graph无环，从而保证事务的执行是可串行化的"。
- 原始内容：根据serializability理论，如果serializability graph无环就能保证事务的执行是可串行化的（serializable）……CockroachDB使用timestamp ordering技术保证serializability graph中不存在环……只允许与较早的时间戳发生冲突的操作存在，不允许与较晚的时间戳发生冲突的操作存在，也就是只接受比自己的时间戳大的操作。这种timestamp ordering技术可以保证serializability graph无环。