首页后端开发 CAP理论与分布式系统设计

CAP理论与分布式系统设计

Author: 曹洪伟 · 分类：后端开发 · 2024年12月 · tags: cap 分布式并发

首先第一个难题，是否允许任意节点并发可写。在Google的F1，蚂蚁的OceanBase，亚马逊的Aurora中，都是指定一个写节点或者更新节点的（据说OB升级1.0后，所有节点都是同等地位的）。

第二个难题，是否支持读写并发。这里涉及到读写一致性的问题。比如上图，当用户A在写入系统的时候，用户B的读取情况是什么样子的？是读取数据的上一个快照，还是读取A写入的最新数据？用户A和用户B在读取的过程中如何加锁？特别跨越广域网的不同的数据中心的时候。这里tricky的地方在于是否要对整个数据加读写锁。目前我看Google的主要方法是目前A进程在写的时候采用多版本数据存储，并保证分布式事务。B进程可以实现无锁的快照读取。基于中心节点的机制，如果读写冲突或者写写冲突，会被锁机制拒绝，用户操作失败。

这个问题还涉及到分布式事务的隔离性问题。传统数据库ANSISQL标准定义了四个“隔离等级”：

未提交读：一个事务可以读任何已提交或未提交的数据。这可以通过“读操作不需要请求任何锁”来实现。
已提交读：一个事务可以读任何已提交的数据。对于同一个对象的重复读可能导致读到不同版本的数据。实现方式是，读数据前必须首先获得一个读操作锁，一旦数据读取之后该锁被立即释放。
可重复读：一个事务只能读取一个已提交数据的一个版本；一旦该事务读取了一个对象，那么，它将只能读取该对象的同一个版本。实现方式是，事务在请求读数据之前必须获得一个锁，并且保持该锁直到事务结束。
可串行化：保证完全的可串行化。

分布式数据库如何满足，是设计分布式系统的首要问题。严格说来，Google的实现应该是一种可重复读（这里还要存疑）。

第三个难题，元数据如何保存。用户A或B在读取或者写入系统的时候，如何获得数据的版本和时间戳？这在OceanBase， spanner/F1，以及TiDB中PD机制中略有涉及，但都不详细。如果元数据在异地数据中心，获得元数据将会有一个广域网延迟到时间开销。我认为Google的truetime是用了物理时间代替经典的逻辑时钟，并且作为副本的时间戳，也就是版本号，这样基于truetime的精巧API设计，让版本号和物理时间线性对齐，无需去查询副本的元数据信息。相反的例子是Google Chubby提到的：在一个已经初步成熟的复杂应用程序的每次操作中引入版本号的开销是非常大的。所以后来退一步求其次，Chubby采用了仅仅在所有使用锁的操作中引入版本号。

第四个难题，在读写事务期间，节点故障。注意，这里是指任意节点故障，包括一次事务中的leader节点，参与节点，以及用户节点。特别是用户所在的节点故障要求系统必须有加锁租约等自恢复机制。

关于锁的设计，在CAP的范围内，需要满足三点：

锁对象信息的要写入多副本以应对故障
不同对象的锁信息需要分布化和负载均衡
锁信息写入持久化存储系统

注意，这里锁的概念和Google Chubby中锁的概念是不同的。这里是一种粗粒度的锁（leader选举），其作者也不建议把Chubby应用在细粒度锁（事务更新）的场景中。这两种锁在CAP的范围内使用时值得非常细心的研究和讨论，特别是在分布式数据库领域内。

第五个难题，嵌套事务或者链式事务。这是电子商务的基础。下面以Percolator的实现说明这个问题。银行转账，Bob 向 Joe 转账7元。该事务于start timestamp =7 开始，commit timestamp=8 结束。具体过程如下：

初始状态下，Bob的帐户下有10（首先查询column write获取最新时间戳数据,获取到data@5,然后从column data里面获取时间戳为5的数据，即$10），Joe的帐户下有2。

2、转账开始，使用stattimestamp=7作为当前事务的开始时间戳，将Bob选为本事务的primary，通过写入Column Lock锁定Bob的帐户，同时将数据7:$3写入到Column,data列。

3、同样的，使用stat timestamp=7，锁定Joe的帐户，并将Joe改变后的余额写入到Column,data,当前锁作为secondary并存储一个指向primary的引用（当失败时，能够快速定位到primary锁，并根据其状态异步清理）

4、事务带着当前时间戳commit timestamp=8进入commit阶段：删除primary所在的lock，并在write列中写入从提交时间戳指向数据存储的一个指针commit_ts=>data @7。至此，读请求过来时将看到Bob的余额为3。

5、依次在secondary项中写入write并清理锁，整个事务提交结束。在本例中，只有一个secondary:Joe.

7 总结

本文的主要观点是：

CAP中的三个因素并不对等，P是基础，CA之间需要tradeoff。系统设计不是三选二的取舍。
延迟作为可用性的指标和体现，系统设计通常需要在C和延迟之间tradeoff。
CAP真正的trade-off在CA之间，系统设计需要细心分解C和A，不同的系统有不同的需求。本文在对CAP分解的基础上，提供了系统设计的一些思考方法。未来系统的设计必然是要满足多种一致性模型和多种可用性需求（例如微软的cosmos DB声称支持多种一致性模型）。
针对分区设计数据不变性，记录所有的分区历史，这让分区合并之后的compensation有据可依。借助社会和法律因素，一致性最终都是可以保证的。另外，如果像阿里日照的见解，可用性是一定时间延迟（可能是一天）之后返回响应（在这期间实现服务切换），那么可用性也是可以保证的。
在第3点的基础上，未来分布式系统需要从整体上考虑，即需要考虑IT基础设施，也要考虑应用的适应和配合，以及人类社会中的法律和补偿。

6. 本文讨论了在CAP范围内，分布式系统设计的一些难点。

注意本文的分区和数据库的分片（分区）不是一个概念。
8 附录

8.1 附录1：不变性如何打败CAP定理？

以下翻译自《how to beat CAP》。

CAP定理仍然适用，所以你需要在可用性和一致性上做出选择，这里的漂亮之处在于，一旦你权衡之后做出了选择，你就做完了所有的事情。通常的那些因为CAP定理带来的问题，都可以通过不可改变的数据和从原始数据中计算查询来规避。

如果你选择一致性而不是可用性，那么跟以前并没有多大的区别，因为你放弃了可用性，所以一些时候你将无法读取或者写入数据。当然这只是针对对强一致性有要求的系统。

如果你选择可用性而不是一致性，在这种情况下，系统可以达到最终一致性而且规避了所有最终一致性带来的复杂问题。由于系统总是可用的，所以你总可以写入新数据或者进行查询。在出错情况下，查询可能返回的不是最近写入的数据，但根据最终一致性，这个数据最终会一致，而查询函数最终会把这个数据计算进去。

这里的关键在于数据是不可变的。不可变数据意味着这里没有更新操作，所以不可能出现数据复制不同这种不一致的情况，也意味着不需要版本化的数据、矢量时钟或者读取修复。在一个查询场景中，一个数据只有存在或者不存在两种情况。这里只有数据和在数据之上的函数。这里没有需要你为确保最终一致性额外做的事情，最终一致性也不会因此使你的系统变得复杂。

8.2 附录2：放弃P,选择C

在《Errors in DatabaseSystems, Eventual Consistency, and the CAP Theorem》一文中，Michael Stonebraker指出：

A partition in a WAN network. There is enough redundancy engineered into today’s WANs that apartition is quite rare. My experience is that local failures andapplication errors are way more likely. Moreover, the most likely WANfailure is to separate a small portion of the network from the majority. Inthis case, the majority can continue with straightforward algorithms, and onlythe small portion must block. Hence, itseems unwise to give up consistency all the time in exchange for availabilityof a small subset of the nodes in a fairly rare scenario.

In summary, one should not throw out the C so quickly, since there are realerror scenarios where CAP does not apply and it seems like a bad tradeoff inmany of the other situations.

8.3 附录3：用PACELC替换CAP

《Problems with CAP,and Yahoo’s little known NoSQL system》

Not only is the asymmetry of thecontributions of C, A, and P confusing, but the lack of latency considerationsin CAP significantly reduces its utility.

In conclusion, rewriting CAP as PACELC removessome confusing asymmetry in CAP, and, in my opinion, comes closer to explainingthe design of NoSQL systems.
9 参考文献

Immutability Changes Everything

Transactions Across Datacenters

https://snarfed.org/transactions_across_datacenters_io.html

From the Ground Up: Reasoning AboutDistributed Systems in the Real World

http://bravenewgeek.com/from-the-ground-up-reasoning-about-distributed-systems-in-the-real-world/

How Google Serves Data From MultipleDatacenters

http://highscalability.com/blog/2009/8/24/how-google-serves-data-from-multiple-datacenters.html

Everything You Know About Latency Is Wrong

http://bravenewgeek.com/everything-you-know-about-latency-is-wrong/

You Can’t Sacrifice Partition Tolerance

https://codahale.com/you-cant-sacrifice-partition-tolerance/

Distributed systems for fun and profit