多版本并发控制(MVCC)在分布式系统中的应用

fmms 12年前
     <p>        <strong>问题</strong></p>    <p>        最近项目中遇到了一个分布式系统的并发控制问题。该问题可以抽象为:某分布式系统由一个数据中心D和若干业务处理中心 L1,L2 … Ln 组成;D本质上是一个 key-value 存储,它对外提供基于 HTTP 协议的 CRUD 操作接口。L的业务逻辑可以抽象为下面 3 个步骤:</p>    <ol>     <li>read: 根据 keySet {k1, … kn}从D获取 keyValueSet {k1:v1, … kn:vn}</li>     <li>do: 根据 keyValueSet 进行业务处理,得到需要更新的数据集 keyValueSet’ {k1′:v1′, … km’:vm’} (<strong>注</strong>:读取的 keySet 和更新的 keySet’可能不同)</li>     <li>update: 把 keyValueSet’更新到D (<strong>注</strong>:D保证在一次调用更新多个 key 的原子性)</li>    </ol>    <p>        在没有事务支持的情况下,多个L进行并发处理可能会导致数据一致性问题。比如,考虑 L1 和 L2 的如下执行顺序:</p>    <ol>     <li>L1从D读取 key:123对应的值 100</li>     <li>L2从D读取 key:123对应的 100</li>     <li>L1将 key:123更新为 100 + 1</li>     <li>L2将 key:123更新为 100 + 2</li>    </ol>    <p>        如果 L1 和 L2 串行执行,key 123 对应的值将为 103,但上面并发执行中 L1 的执行效果完全被 L2 所覆盖,实际 key 123 所对应的值变成了 102。</p>    <p>        <strong>解决方案1:基于锁的事务</strong></p>    <p>        为了让L的处理具有可串行化特性(Serializability),一种最直接的解决方案就是考虑为D加上基于锁的简单事务。让L在进行业务 处理前先锁定D,完成以后释放锁。另外,为了防止持有锁的L由于某种原因长时间未提交事务,D还需要具有超时机制,当L尝试提交一个已超时的事务时会得到 一个错误响应。</p>    <p style="text-align:center;"><img style="width:621px;height:604px;" alt="多版本并发控制(MVCC)在分布式系统中的应用" src="https://simg.open-open.com/show/69dd148d1a49319ace1e69cab667fb5f.png" /></p>    <p>        本方案的优点是实现简单,缺点是锁定了整个数据集,粒度太大;时间上包含了L的整个处理时间,跨度太长。为此,可以考虑把锁定粒度降低到数据项 级别,按 key 进行锁定,但这又会带来其他的问题。由于更新的 keySet’可能是事先不确定的,所以可能无法在开始事务时锁定所有的 key;如果分阶段来锁定需要的 key,又可能出现死锁(Deadlock)问题。另外,按 key 锁定在有锁争用的情况下并不能解决锁定时间太长的问题。所以,按 key 锁定仍然存在重要的不足之处。</p>    <p>        <strong>解决方案2:多版本并发控制</strong></p>    <p>        为了实现可串行化,同时避免锁机制存在的各种问题,我们可以采用基于多版本并发控制(Multiversion concurrency control,MVCC)思想的无锁事务机制。人们一般把基于锁的并发控制机称成为悲观机制,而把 MVCC 等机制称为乐观机制。这是因为锁机制是一种预防性的,读会阻塞写,写也会阻塞读,当锁定粒度较大,时间较长是并发性能就不会太好;而 MVCC 是一种后验性的,读不阻塞写,写也不阻塞读,等到提交的时候才检验是否有冲突,由于没有锁,所以读写不会相互阻塞,从而大大提升了并发性能。目 前,Oracle、PostgreSQL 和 MySQL 都已支持基于 MVCC 的并发机制,但具体实现各有不同。</p>    <p>        MVCC 的一种简单实现是基于 CAS(Compare-and-swap)思想的有条件更新(Conditional Update)。普通的 update 参数只包含了一个 keyValueSet’,Conditional Update 在此基础上加上了一组更新条件 conditionSet { … data[keyx]=valuex, … },即只有在D满足更新条件的情况下才将数据更新为 keyValueSet’;否则,返回错误信息。这样,L就形成了如下图所示的 Try/Conditional Update/(Try again)的处理模式:</p>    <p style="text-align:center;"><img style="width:569px;height:368px;" alt="多版本并发控制(MVCC)在分布式系统中的应用" src="https://simg.open-open.com/show/c543d67aca546393037c12f3e6047f9d.png" /></p>    <p>        虽然对单个L来讲不能保证每次都成功更新,但从整个系统来看,总是有任务能够顺利进行。这种方案利用 Conditional Update 避免了大粒度和长时间的锁定,当各个业务之间资源争用不大的情况下,并发性能很好。不过,由于 Conditional Update 需要更多的参数,如果 condition 中 value 的长度很长,那么每次网络传送的数据量就会比较大,从而导致性能下降。特别是当需要更新的 keyValueSet’很小,而 condition 很大时,就显得非常不经济。</p>    <p>        为了避免 condition 太大所带来的性能问题,可以为每条数据项增加一个 int 型的版本号字段,由D维护该版本号,每次数据有更新就增加版本号;L在进行 Conditional Update 时,通过版本号取代具体的值。</p>    <p style="text-align:center;"><img style="width:560px;height:210px;" alt="多版本并发控制(MVCC)在分布式系统中的应用" src="https://simg.open-open.com/show/d6ce8b7e871820212201942cc09b0807.png" /></p>    <p>        另一个问题是上面的解决方案假设了D是可以支持 Conditional Update 的;那么,如果D是一个不支持 Conditional Update 的第三方的 key-value 存储怎么办呢?这时,我们可以在L和D之间增加一个P作为代理,所有的 CRUD 操作都必须经过P,让P来进行条件检查,而实际的数据操作放在D。这种方式实现了条件检查和数据操作的分离,但同时降低了性能,需要在P中增加 cache,提升性能。由于P是D的唯一客户端;所以,P的 cache 管理是非常简单的,不必像多客户端情形担心缓存的失效。不过,实际上,据我所知 redis 和 Amazon SimpleDB 都已经有了 Conditional Update 的支持。</p>    <p>        <strong>总结</strong></p>    <p>        本文介绍了一种基于多版本并发控制(MVCC)思想的 Conditional Update 解决分布式系统并发控制问题的方法。和基于锁的方法相比,该方法避免了大粒度和长时间的锁定,当各个业务之间资源争用不大的情况下,并发性能很好。</p>    <p>        <strong>参考</strong></p>    <p>        <a href="/misc/goto?guid=4958332692734308237">Wikipedia – Serializability</a></p>    <p>        <a href="/misc/goto?guid=4958332693539578276">Wikipedia – Compare-and-swap</a></p>    <p>        <a href="/misc/goto?guid=4958332694326922740">Wikipedia – Multiversion concurrency control</a></p>    <p>        <a href="/misc/goto?guid=4958332695120984972">Lock-free algorithms: The try/commit/(try again) pattern</a></p>    <p>        <a href="/misc/goto?guid=4958332695931508353">Amazon SimpleDB FAQs – Does Amazon SimpleDB support transactions?</a></p>    <p>        <a href="/misc/goto?guid=4958332696725506717">redis – Transactions</a></p>    <p>        <a href="/misc/goto?guid=4958332697522740537">A Quick Survey of MultiVersion Concurrency Algorithms</a></p>    <p>        <a href="/misc/goto?guid=4958332698334236590">非阻塞算法思想在关系数据库应用程序开发中的使用</a></p>    <p>        <strong>友情推荐</strong></p>    <p>        本文的图是陈皓开发的 <a href="/misc/goto?guid=4958332699122647584">TextDiagram</a> 工具画的,欢迎试用!如果您喜欢,请推荐给朋友,谢谢</p>