每个跑过并发事务的工程师大概都经历过这种时刻线上一个简单的先查后写操作在低峰期一切正常一到业务高峰就频繁超时、报错、数据对不上。排查到最后十有八九是并发控制没做好。数据库领域的并发控制方案最著名的两条路线是封锁Locking和时间戳排序Timestamp Ordering简称TO。前者被传统关系型数据库用了几十年后者则在不少分布式数据库和内存数据库里被发扬光大。这篇文章我想认真聊一聊后者——时间戳排序并发控制把它的原理、实现细节、工程落地里的坑以及和传统封锁方案的对比一次讲透。如果你是刚接触数据库内核的开发者或者你正在做中间件、自研存储引擎又或者你只是好奇乐观并发控制到底是怎么做到不锁也能保证一致性的这篇文章应该都能给你一份比较完整的参考。我会从最基础的冲突场景讲起一直说到工业级实现里常见的时间戳分配方案和优化变种。1. 从数据库的冲突现场说起TO协议要解决的根本问题1.1 一个并发更新的车祸现场假设有一个账户表两个事务同时在做转账操作。事务T1把A账户余额从1000改成900事务T2把A账户余额从1000改成800。如果两个事务真的同时执行且没有任何干预最终余额可能是900也可能是800取决于谁后写。但更麻烦的是如果T1还读了B账户T2还写了B账户那最终的数据状态就完全不可控了——可能T1读到的是T2写了一半的B账户余额。这个问题的本质是多个事务并发执行时它们的读写操作之间存在冲突而系统需要保证这些并发事务的执行结果等价于它们按某个串行顺序执行的结果。这就是数据库理论里的可串行化Serializability要求。满足可串行化事务之间就不会互相干扰数据一致性就有了底线。传统做法是加锁谁先拿到锁谁先操作其他人等着。但加锁带来的问题也很明显——锁等待、死锁检测、锁升级这些机制本身就有不小的开销和复杂度。时间戳排序走的是另一条路不排队不等待用先来后到的规则直接决定谁有资格执行。1.2 可串行化与冲突等价TO的理论地基时间戳排序协议的核心逻辑其实就一句话给每个事务分配一个全局唯一递增的时间戳时间戳越小的事务优先级越高越先执行。所有冲突操作必须按照时间戳的顺序来判定——如果低优先级事务的操作和高优先级事务的冲突操作撞上了低优先级的事务要么回滚要么被抛弃。这里有个关键概念叫冲突等价Conflict Equivalence。两个事务T1和T2如果它们交换了某些操作的执行顺序会产生不同的结果那这些操作就是冲突的。TO协议的目标是让所有冲突操作都按照事务时间戳的大小顺序执行这样整个并发调度的结果就等价于按时间戳串行执行的结果。注意TO协议不是不要锁而是原则上不加锁某些实现为了一些内部保护可能仍会用到短临界区。它靠的是碰上了就判断谁该让路的规则所以理论上不会出现死锁——因为事务不会持有资源等待别的资源每个操作要么立刻执行要么立刻被拒绝。这也引出了TO协议最鲜明的两个特征第一没有等待就没有死锁第二冲突严重时会有大量回滚性能可能断崖式下跌。这两点我们在后面的章节里详细展开。2. 时间戳排序的两条铁律读规则与写规则2.1 时间戳从哪来TS(Ti)的含义与来源在讲规则之前先把符号统一一下。我们用TS(Ti)表示事务Ti的时间戳用W-timestamp(Q)表示数据项Q最近一次被写入时对应事务的时间戳用R-timestamp(Q)表示Q最近一次被读取时对应事务的时间戳。每个数据项上都挂了这两个时间戳它们记录了这个数据项最后一次被谁写过和最后一次被谁读过。TS(Ti)怎么产生这个看似简单的问题其实在工程实现里有大学问。单机环境下一个原子递增的计数器就够了。但在分布式环境下如何让每个节点产生的时间戳既唯一又大致有序是一个非常棘手的问题。系统时钟可能漂移网络有延迟每台机器的当前时间并不一致。这个问题我在第3节专门展开先记住一点TO协议的正确性完全建立在时间戳的全局有序性上时间戳一旦乱序后面所有规则都是空中楼阁。2.2 读规则晚到的事务不能读旧数据TO协议的读规则如下如果事务Ti想读取数据项Q且TS(Ti) W-timestamp(Q)说明Q的最新值是由一个比Ti更晚的事务写入的。也就是说Ti作为一个较早的事务却想读一个较新的值这违背了时间戳顺序。此时Ti必须回滚。反之如果TS(Ti) W-timestamp(Q)说明Q的最新值是由一个不比Ti晚的事务写的或者就是Ti自己写的那Ti就可以安全地读取Q。读取完成后需要把R-timestamp(Q)更新为max(R-timestamp(Q), TS(Ti))。这条规则背后的直觉是既然T2的时间戳比T1大在串行顺序里T2应该排在T1后面。那么T1在读数据时绝对不能读到T2写的值——因为序列化的顺序是T1先执行T1读到的应该是T2执行之前的状态。如果T1读到了T2写的值说明实际执行顺序是T2写→T1读这和串行顺序T1在T2之前矛盾整个调度就不可串行化了。2.3 写规则晚到的事务不能覆盖新数据TO协议的写规则分两条如果事务Ti想写入数据项Q且TS(Ti) R-timestamp(Q)说明有一个时间戳比Ti大的事务Tj已经读过Q的最新值了。如果允许Ti写入Tj读到的值就会被覆盖Tj等于读到了一个从未存在过的旧值这同样破坏可串行化。此时Ti必须回滚。如果事务Ti想写入数据项Q且TS(Ti) W-timestamp(Q)说明Q已经被一个时间戳比Ti大的事务写过了。此时如果Ti直接覆盖就相当于在串行顺序里排在后面的Tj把先执行的事务Ti的值覆盖了也违反规则。同样Ti必须回滚。只有TS(Ti) R-timestamp(Q) 且 TS(Ti) W-timestamp(Q) 时Ti才能成功写入。写入后W-timestamp(Q)更新为TS(Ti)。2.4 一张判定表搞定全部场景把两条规则合并可以整理成一张非常直观的判定表场景条件判定结果原因Ti读QQ的最新写者更晚TS(Ti) W-timestamp(Q)回滚TiTi读到了未来事务写的值Ti读QQ的最新写者不晚于TiTS(Ti) W-timestamp(Q)允许读更新R-timestamp符合串行顺序Ti写Q有更晚的读者TS(Ti) R-timestamp(Q)回滚Ti更晚事务读到的值会被破坏Ti写Q有更晚的写者TS(Ti) W-timestamp(Q)回滚Ti更晚事务写入的值会被覆盖Ti写Q没有更晚的读/写者其余情况允许写更新W-timestamp符合串行顺序这张表我建议想深入理解TO协议的朋友自己手推一遍。不要死记规则而是思考一个问题如果我不按这个规则走最终会有什么后果把每个违规场景都想象成一个具体的并发案例规则自然就记住了。3. 时间戳分配机制为什么不能用gettimeofday()3.1 单机物理时钟的问题并发度一高就撞车很多人第一次实现TO协议时会想当然地用系统时间作为时间戳——反正时间戳嘛当前时间微秒级总该是唯一的吧但实际一测就翻车了。单机上两个线程在同一微秒内各自开启一个事务拿到的系统时间完全一样。如果直接拿这个时间戳去做读写规则判定两个事务就有一样的时间戳谁先谁后就变成未定义行为了。更隐蔽的问题是系统时间可能回拨。NTP校时、手动改时间、虚拟机快照恢复都可能导致系统时间倒退。一旦时间回拨新事务可能拿到比老事务更小的时间戳整个TO协议的判定逻辑就乱了——旧事务变成未来事务新事务变成过去事务数据一致性瞬间崩塌。所以在单机实现里最稳妥的做法是用一个原子自增计数器事务启动时从计数器取一个递增值。这个方案简单可靠但有一个瓶颈所有事务的时间戳都要从这个全局计数器拿高并发场景下这一个点会成为性能热点。实际工程里通常用批量预分配的方式优化——每个线程/核心预取一段时间戳区间用完了再取下一段把全局竞争从每次取号降为每次取一段。3.2 逻辑时钟Lamport方案的工程简化单机自增计数器的问题在于分布式场景下不管用了——每台机器都维护一个自增计数器两个节点产生的时间戳必然冲突。这时需要引入逻辑时钟的概念。Lamport在1978年那篇著名的论文里提出了happens-before关系如果进程A给进程B发了消息那么A的某个事件happens-before B的某个事件A的逻辑时钟必须小于B的逻辑时钟。在TO协议的工程实现里逻辑时钟被简化成了这样一个规则每个节点维护一个本地逻辑时钟初始为0。本地事务启动时本地时钟加1作为事务时间戳。节点间通信时消息里带上发送方的逻辑时钟值。接收方收到消息后把自己的逻辑时钟更新为 max(本地时钟, 消息携带的时钟) 1。这样就能保证如果事务T1在事务T2开始之前并且T1的节点给T2的节点发过消息即T1 happens-before T2那T1的时间戳一定小于T2的时间戳。TO协议其实只要求冲突事务之间时间戳有序而两个事务如果在不同节点上且没有通信它们之间就没有先后依赖谁先谁后都不影响串行化结果。这正是逻辑时钟能work的关键——它不需要全局时钟完全统一只需要捕获真实的依赖顺序。3.3 分布式系统里的混合时钟HLC的思路逻辑时钟解决了唯一性和顺序性问题但它有一个缺点时间戳和真实时间完全没有关系。这在业务上可能很麻烦——运维想看这个事务是什么时候发生的完全看不出审计也做不了。工业界的主流做法是混合逻辑时钟Hybrid Logical ClockHLC。思路很简单时间戳的高位取物理时间低位取逻辑计数器。具体实现是每个节点维护一个HLC规则如下本地事件发生时如果当前物理时间大于HLC的物理部分则把HLC的物理部分更新为当前物理时间逻辑部分归零否则HLC的物理部分保持不变逻辑部分加1。收到消息时取 本地HLC 和 消息携带的HLC 中的较大值再按照上面的规则修正。HLC的精妙之处在于它在绝大多数情况下等于物理时间只有在同一物理时间戳内发生大量事件时才用逻辑部分扩展。这样既保证了时间戳单调递增又保留了和物理时间的对应关系。CockroachDB的时间戳方案就是HLC的工程化应用后面第8节会再提到。我在实际项目里的建议是单机场景无脑用原子计数器或批量预分配别再想物理时间的事分布式场景优先考虑HLC除非你的场景有非常强的必须接近物理时间的审计需求。纯逻辑时钟虽然简单但排查问题的时候你会很想哭——日志里两个时间戳只差1你完全不知道它们对应的真实时间。4. 与2PL的正面对比TO到底赢在哪、输在哪4.1 2PL的核心思想与封锁代价要对TO有深刻的理解必须把它放进和传统两阶段封锁2PL的对比里看。2PL的思路是冲突就在入口拦住事务在读取或写入数据前必须先申请对应的共享锁或排他锁拿到锁才能访问数据所有加锁操作分为增长阶段和收缩阶段一旦开始释放锁就不能再加新锁以此保证事务的访问模式是可串行化的。2PL在传统关系型数据库里统治了几十年是因为它在读写比例均衡、并发冲突可控的场景下确实可靠。但它有两个绕不开的问题。第一个是死锁。两个事务各自持有对方需要的锁谁也无法继续只能靠死锁检测或超时机制来打断。死锁检测本身要构建等锁图成本和复杂度都不低。第二个是锁等待带来的尾部延迟。一个事务可能在锁队列里等很久尤其是有长事务时后面的短事务全部被堵住响应时间像坐过山车。4.2 TO的赢面无死锁、无阻塞TO协议在理论上的最大优势就是没有等待。每个操作做判定时只有执行和回滚两个选项只要条件满足就立刻执行不满足就立刻让事务失败。没有锁队列就没有死锁也没有锁等待导致的延迟波动。这对某些场景来说是决定性的。最典型的是内存数据库和主内存OLTP系统。这些系统的核心卖点就是低延迟高吞吐如果事务动不动阻塞在锁上性能优势就没了。而且内存数据库通常不支持阻塞式锁等待的高昂代价——内存里数据多锁粒度细锁管理器的开销会被放大。TO协议用冲突就回滚换来了无阻塞的清爽而且内存数据库的事务通常短小回滚成本低回滚了快速重试一次往往就成功了。4.3 TO的输面级联回滚与低并发下的性能损耗TO协议当然不是银弹。它最大的代价是回滚可能级联。假设T1读了数据AT2写了A并提交之后T1尝试写B时因为和T3冲突被判定回滚。T1回滚后所有读过T1写入值的事务——即使它们已经执行了很多操作——都必须一并回滚。这个回滚链可能很长在极端场景下甚至可能引发连锁反应导致系统整体吞吐瞬间崩塌。这是TO协议最需要工程设计去缓解的地方。我在后面讲MVTO多版本时间戳排序时会提到多版本化是缓解级联回滚的利器。TO的另一个问题是在低并发冲突场景下仍然要付出时间戳判定的额外开销。每次读写都要比较时间戳、更新R/W-timestamp这些操作虽然比加锁轻但也是实实在在的开销。如果一个系统大多数事务互不冲突2PL的锁开销可能比TO的判定开销更低因为读写锁在无竞争时可以用非常轻量的原子操作完成。TO适合冲突率较高但事务短小的场景2PL适合冲突率低或事务较长的场景。4.4 到底该怎么选场景判断经验根据自己的经验我总结了一套选择倾向事务短小、冲突率高、对延迟抖动敏感的场景优先考虑TO或MVTO。典型例子是内存数据库、金融转账类高竞争热点账户操作。事务长、读写混合、冲突率低的场景优先考虑2PL或MVCC多版本并发控制。典型例子是传统OLTP业务报表、订单、用户中心的常规读写。读写比例极不均匀、读多写少的场景根本不应该用基础TO应该用MVCC或多版本TO否则读事务会被写事务疯狂误伤。5. 工程落地中一定会遇到的几个坑5.1 读多写少场景下读规则误伤短事务TO协议里只要Ti的时间戳小于Q的W-timestampTi的读就会被拒绝。在一个热数据反复被更新大量新事务同时读它的场景下新启动的事务时间戳都很小但热数据的W-timestamp被频繁更新到很大的值。结果就是几乎所有读操作都会触发回滚系统吞吐直接归零。这就是为什么工业界几乎不会在纯读多写少场景单独用基础TO。解决方案通常是多版本化——读操作不再被W-timestamp拒绝而是去读自己时间戳之前的最新版本。这个方法在MVCC里已经非常成熟了PostgreSQL、InnoDB的MVCC本质上都在做类似的事。5.2 长事务拖死短事务TO协议对长事务极不友好。一个执行了很长时间、时间戳很小的事务因为它资格老所有和它冲突的新操作都会被拒绝——但反过来说它一旦需要回滚级联范围也可能非常大。更麻烦的是长事务持有的资源和它造成的回滚风险随执行时间增长短事务则不断因为撞上老资格事务而回滚重试整体表现就是系统越来越慢长事务还迟迟不结束。工业界对长事务的通行做法是限制事务执行时间或操作数超过阈值则强制回滚。这在设计时就该考虑——如果你的业务场景天然存在大事务基础TO几乎注定要出问题要么换MVCC要么在应用层拆事务。5.3 事务读不到自己刚写入的值TO协议一个特别容易踩的坑是事务内先写后读。T1写入数据QQ的W-timestamp被更新为TS(T1)。随后T1又读Q按读规则需要TS(T1) W-timestamp(Q)。这两个值是相等的所以判定可以通过不会出问题。但问题是有些工程实现为了性能读路径没有检查这个值是不是我自己写的而是直接找了最新的已提交版本或最新版本结果读到了自己提交前的旧值或者别的并发事务写的值。这是一种非常隐蔽的逻辑错误测试时很难发现。我的建议是实现TO协议时一定要在数据项上记录最后写入者的事务ID读路径先检查写入者是否为当前事务如果是就直接返回不参与时间戳判定。这个判断成本很低但能避免一大类疑难Bug。5.4 版本号更新的原子性问题还有一个容易被忽略的工程细节R-timestamp和W-timestamp的更新必须保证原子性。多个事务并发读写同一个数据项时时间戳字段可能被同时修改。如果这两个字段的更新不是原子的可能出现一个事务读取后另一个事务把它要更新的R-timestamp覆盖了导致漏判冲突。在实现时我建议把检查时间戳条件 更新对应时间戳做成一个原子操作。单机上用CAS比较并交换就够了不要图省事拆成两步。分布式环境下这个问题会更复杂通常需要借助数据项所在节点的本地锁或原子指令来保证。6. Thomas写规则给TO打上的关键补丁6.1 Thomas写规则到底是什么前面讲的写规则里如果TS(Ti) W-timestamp(Q)Ti必须回滚。但有一个著名的优化叫Thomas写规则Thomas Write Rule可以显著减少这类回滚。Thomas写规则的判定是这样的如果TS(Ti) R-timestamp(Q)说明有更晚的事务读过QTi的写入会造成读到的值被覆盖必须回滚。如果TS(Ti) W-timestamp(Q)说明Q已经被更晚的事务写过了。此时不写Q但事务Ti也不回滚直接跳过这个写操作继续执行。为什么可以跳过因为W-timestamp(Q) TS(Ti)意味着在串行顺序里Q最终的值由更晚的事务决定。Ti写不写这个值反正都会被更晚的事务覆盖最终可见的Q都不会包含Ti写入的值。既然最终结果一样那就没必要让Ti回滚直接忽略它的这次写入即可。6.2 这个补丁能带来多大的收益Thomas写规则的实际收益在写冲突频繁但读相对少的场景非常明显。比如两个事务同时给同一个账户加钱T1时间戳100T2时间戳200。如果没有Thomas写规则T2的写会触发T1的回滚有了Thomas写规则T1可以直接忽略写入T2正常执行T1的其他操作不受影响。要注意的是Thomas写规则只优化了写-写冲突的场景对读-写冲突依然无能为力——TS(Ti) R-timestamp(Q)时依然只能回滚。因为更晚的事务已经读过Q的旧值了如果Ti再写入那个更晚的事务就读到了一个未来不存在的值这无论如何都无法忽略。6.3 Thomas写规则的代价视图可串行化问题Thomas写规则不是免费的午餐。跳过写入会让最终的调度结果不满足冲突可串行化Conflict Serializability但满足视图可串行化View Serializability。简单说有些被忽略掉的写入操作其效果被后续写入覆盖了最终结果和某个串行执行计划等价但中间过程可能有细微的差异。绝大多数业务场景下视图可串行化提供的一致性已经足够但如果你在对一致性要求极高的场景下工作需要知道这一点。我在实现里遇到的实际情况是Thomas写规则带来的性能提升通常非常可观以至于它的理论瑕疵在工程上完全可以接受。但如果你要拿这个去做严格的正确性论证建议把启用Thomas写规则作为系统的一个可配置项并且保证测试覆盖到位。7. 从单版本到多版本MVTO的演进之路7.1 为什么必须多版本化基础TO协议最大的毛病就是读规则会让读操作频繁回滚。设想一个数据项Q正在被频繁更新W-timestamp(Q)不断变大一个新启动的事务T1时间戳较小去读Q直接触发回滚。这在读多写少的业务里是无法接受的。多版本化的思想非常直接保留数据的多个历史版本。每个版本都记录自己的写入时间戳W-TS和版本起止时间区间。事务读数据时不需要检查W-timestamp是否小于自己的时间戳而是直接查哪个版本的时间戳区间包含我的事务时间戳找到那个版本读就行了。这样读操作几乎永远不会因为读到未来数据而回滚——它总是能找到属于自己时间点的那个版本。7.2 版本链的实现与垃圾回收MVTO实现的核心是版本链Version Chain。每个数据项的逻辑上有一个版本链表链表从头到尾按版本新旧排列每个节点包含值本身版本写入时间戳W-TS读时间戳R-TS用于判断是否有更晚事务读过这个版本指向下一个版本的指针新写入的版本插入链表头部。读操作从头部开始沿着链查找找到第一个W-TS小于等于自己事务时间戳的版本即可。这个查找过程是O(n)的n是版本链长度。版本链过长会导致性能下降所以需要垃圾回收机制——定期清理那些事务时间戳不可能再查到的旧版本。一个实用的GC规则是记录系统当前最老的活动事务时间戳M任何版本如果W-TS小于M并且它对应的读时间戳R-TS也小于M那这个版本永远不会再被任何事务读取可以安全回收。7.3 MVTO与传统MVCC的关系很多人问MVTO和MVCC有什么区别。其实MVCC是一个更大的概念泛指多版本并发控制MVTO是MVCC下的一种具体调度协议核心特征是使用时间戳排序来决定版本可见性和冲突处理。PostgreSQL的MVCC并不完全等同于MVTO——它的可见性判断基于事务快照snapshot事务看到的版本集合由快照决定更像是一种多版本快照隔离Snapshot Isolation。而MVTO是明确用事务时间戳来判定每个操作的合法性更贴近TO协议的理论框架。两者的工程实现有大量共通之处但理论模型和冲突处理策略有区别。8. 现实世界里谁在用TO工业实现案例与优化思路8.1 H-Store和S-Store的批次式时间戳排序H-Store是学术界非常有名的内存数据库原型系统它的设计目标就是用主内存存储加无锁并发控制来达到极致的OLTP性能。H-Store默认不采用TO但它的研究衍生系统S-Store大量借鉴了TO的思想。S-Store把事务进行分期epoch批处理同一批次内的事务使用时间戳排序来管理状态最新的状态只属于当前批次。这种方式把TO的判定从每条数据一个时间戳简化为整个批次一个时间戳极大减少了时间戳维护的开销。8.2 TiDB的TSO分配器是怎么设计的TiDB作为分布式数据库它的全局时间戳分配器PDPlacement Driver提供了一个全局单调递增的TSOTimestamp Oracle。所有事务都从PD获取TSO作为自己的起始时间戳保证全局有序。这个TSO的生成方式就是用物理时间高位逻辑时间低位组合配合批量分配——每个请求一次性取一批时间戳减少跨节点通信频率。TiDB的处理方式是内部时间戳用逻辑递增但对外保证事务时间戳和物理时间大致对应方便运维排查。从TiDB的实现里可以看到分布式数据库对时间戳的要求是全局唯一 单调递增 尽量贴近物理时间这三点同时满足是非常有挑战的。TSO方案本质上是引入一个中心化分配器作为时间戳来源简单可靠但有一个中心节点热点的问题HLC方案则不需要中心节点但时间戳的物理时间属性有稍微宽松的取舍。8.3 CockroachDB的混合逻辑时钟CockroachDB使用的是HLC方案。每个节点维护自己的HLC事务在本地启动时取HLC值作为时间戳跨节点通信时把HLC传播给对方。由于HLC在有通信发生时才推进两个没有通信的事务即使时间戳有偏差也不影响正确性——因为它们之间没有依赖关系。但CockroachDB也遇到了时间戳回退的问题如果一个事务的timestamp小于某些已提交数据的timestamp它就需要重试甚至会把整个事务的timestamp推到一个更大的值重新执行。这就是事务重启机制本质上是TO协议的工程变体——不直接回滚而是换一个更大的时间戳重试。这种设计大幅降低了回滚的破坏性。8.4 结合乐观并发控制的优化方向最后聊一下TO和OCC乐观并发控制Optimistic Concurrency Control的结合。OCC的基本思想是事务在本地私有空间执行修改提交时统一验证——如果验证失败就回滚。TO的判定逻辑天然适合作为OCC的提交验证器在提交阶段检查事务的所有读写集合是否满足时间戳规则不满足则冲突。把TO作为提交验证器的好处是事务执行期间完全无锁只在提交点做一次全局判定冲突率低时性能极好。这也是不少NewSQL系统采用的思路比如一些基于内存事务引擎的实现就会在提交阶段用版本号或时间戳做CAS验证。写在后面的一点体会从理论到工程实现TO协议看起来只有薄薄几页纸的规则但真正落地时你会遇到远比教科书复杂的问题——时间戳分配器的热点、旧版本回收的时机、回滚的事务要在多长时间内快速重试、日志和持久化如何配合无锁执行……每一条都需要在性能和正确性之间反复权衡。我个人最大的体会是做并发控制方案选型一定要清楚自己业务里事务的特征长短、读写比例、冲突热点、延迟敏感度。没有哪种协议是普适银弹2PL在低冲突场景下依然高效TO在短事务高冲突场景下确实能给到惊喜MVCC则覆盖了绝大部分读多写少的互联网业务。理解TO的判定规则和它的变种优化不是为了在项目里强行套用而是为了在遇到问题时心里多一张可打的牌。