PayPal将CRDT数据类型落实到生产环境

Dmitry Martyanov谈到PayPal如何开发处理一致性问题的分布式系统，并分享他在开发基于最终一致数据存储的系统中学到的经验教训。该解决方案利用无冲突，复制的数据类型CRDT和因果关系跟踪，实现多主数据中心数据库部署中关键数据的强大最终一致性。

我们都知道共享可变状态是软件中大多数问题的根本原因。我们尽量减少......它增加了意外的复杂性，它引入了副作用。良好的设计通常可以最小化共享的可变状态，实现可变状态共享的解决方案是互斥锁或锁。其目的是限制对数据点的访问，以保证数据修改的一致性。锁是一个很好的解决方案。他们工作得很快。它们非常可靠，随着时间的推移得到了验证。

当您在可变状态和存储数据库领域内考虑这种概念时，其实就是通过事务处理来实现。事务保证了我们的操作原子性，一致性，隔离性和持久性ACID。当在同一个数据中心内并且没有跨全局消息传播时，ACID能很好地工作。

但是，当您迁移到地理上的分布式环境时，事务再也无法正常工作，因为数据中心之间的物理距离对事务时间的影响很大。如果您拥有高负载流量，则会开始发现事务失败，事务重叠，这将成为系统可伸缩性的瓶颈。这正是CAP定理告诉我们的一致性和可用性之间的权衡。

最终一致性

牺牲一致性和增加可用性，对于大多数情况来说，它的效果非常好，但是如果你真的有很高的流量负载并且你的数据修改比复制更频繁，那么这个系统工作得更糟，因为不会出现事务故障和事务重叠，但你会看到数据丢失，这通常是无法控制的，而且非常困难追踪。

这是因为分布式系统包含多个组件。它们中的每一个都有一个本地数据的的复制副本节点，称为复制副本节点服务器。组件本身是可靠的。它们保证了它内部的强一致性，并且它们通过异步消息传递相互通信，实现数据复制。但这种通信却并不那么可靠。您不能确保通信所需的时间，也不能确保成功建立通信连接。

如果在复制副本节点A中成功执行了一些put操作，并且在相同这个数据节点A实现后续读取操作，你会看到put操作的结果。但是，如果从这个节点的另一个复制副本节点执行读取操作，则可能不会得到预期结果，具体取决于这两个节点之间的复制是否已经发生。这是一个非常重要的问题，因为从字面上看，这意味着每次读取数据点时，都不知道它是否真实。你没有办法核实它。当然，如果将此数据值转换为其他值，系统可能会开始出现分歧。所以我们开始考虑如何建立一个最终不会分歧的系统。

具有密切关系的方法

第一类方法是基于密切关系的方法（高聚合）。依赖的事实是，在同一个节点中的数据肯定具有很强的一致性。因此为数据的访问模式引入一些约束，它无法同时与不同的副本节点进行通讯。

最受欢迎的密切关系解决方案是票务会话。在客户会话中，您可以在同一个数据中心处理所有请求，并且您有阅读权限的情况。

基于密切关系方法存在的问题是，您的数据必须以这种方式切片Sharding。如果您的客户端修改了他的个人数据并且没有其他人接触到这些数据，那么它的效果非常好。但是当您有多个操作者在相同的数据点上进行交互时，定义这些约束以及如何在此处定义关联性就不是一项简单的任务。

基于协调器的方法

第二类方法是基于协调器的方法。这些方法依赖于一些负责管理环境冲突的协调器的存在。不一定意味着每个客户端都与协调器交互，但协调器可以处理一些关键组件。我们非常认真地将协调器视为一种解决方案，但是当我们开始向我们的设计引入更多细节时，我们认识到处理协调生命周期的所有可能性非常复杂，因为他可能会失败并且您需要在另一个生命周期中恢复它区。并且存在一些中间状态，您需要以某种方式处理您的请求，或类似的事情将它们搁置，这就是我们放弃协调器的原因。

基于共识的方法

第三类方法是基于共识的方法。这个想法是复制副本节点之间彼此通信，并且他们有一个协议来达成关于数据转换的一些协议。这实际上是分布式系统中非常基本的主题。并且有一些非常可靠的产品建立在Google Spanner或FoundationDB等共识方法之上。但是，让我告诉你为什么它对我们不起作用。

如果您从事产品开发，您的服务堆栈看起来像处理客户端请求的多个层。顶层是合规性的业务逻辑。例如，验证需要哪些类型的文档。然后你有一个领域平台，它引入了一些数据访问函数，实体对象的描述和流程控制机制。而服务的最后一层就像服务基础架构，它负责下游依赖项发现，不同的路由和平衡，以及重试请求等故障转移策略。同时你有数据库管理你的数据。与此同时，有大量与数据存储配置，部署方式，故障转移策略相关的工作。

当您在产品开发团队中时，您通常拥有这些部件。作为服务提供的服务基础结构，通常在需要调用某些下游依赖项时，您不一定知道如何组织此下游依赖项的池。在数据存储中也是如此; 您不知道有多少实际硬件节点用于支持您的数据库。

但是如果你想达成共识，你需要处理这些部分，因为你需要知道你的类堆栈的配置，有多少复制副本节点服务器，它们之间如何相互交互，如果一个副本节点以某种方式失败会做出什么反应等等。

通常，在一些共享层中实现共识。对于大型企业来说，这很难做到，因为这个责任和它的实施将落在多个团队之间，您需要将其注入到您的服务基础架构路线图中，，该路线图有自己的计划以实现他们想要的工作。

如果您拥有端到端的数据库，那么您才拥有与您的数据一起使用的每个流程，这样共识才是一个很好的解决方案。这就是FoundationDB团队和Google Spanner团队所处的位置。

无冲突的复制数据类型

所以在这个时刻，我们开始寻找一个能够存在于产品领域的解决方案。我们开始研究无冲突的复制数据类型。所以在那个时刻，我已经在Riak有过一些CRDT经验。我还查看了Akka分布式数据中的CRDT。

有两大类CRDT。第一类是可交换的CRDT，当副本通过传递“更新操作”实现相互通信时; 这种“更新操作”必须是可交换和关联的，因此 排序 无关紧要。您的环境必须提供一次交付。交换式CRDT的一个非常粗略的例子是区块链网络中的支付。因此，加减操作是可交换和关联的，而块链魔术可以帮助您只接收一次事件。

第二类是收敛CRDT，当副本通过发送整个状态相互通信时，当另一个副本接收状态时，它将状态与本地状态合并。此合并操作也必须是可交换和关联的，但它也必须是幂等的，并且环境需要至少支持一次交付，这更容易。

收敛CRDT的经典例子是仅增长设置。这是一组有序的独特元素，没有删除操作。您可以进行思考实验并置换并发环境中数据结构可能发生的情况，并且您将认识到，最终，此数据结构是一致的和收敛的，并且它将包含中间阶段中所有元素的并集。

收敛CRDT

我们需要为业务数据类型实现一些合并功能，这些功能将是可交换的，关联的和幂等的。这不是一件容易的事，因为您的业务数据看起来不像学术数据结构一样; 它包含字段和参数之类的东西，这不是一件容易的事。但是我们非常鼓舞这样的事实，因为这只是一种数据类型和操作，CRDT的实现类似于当您需要向数据模型添加一个字段时的情况，您需要再添加一列到你的数据库。您无需与DB管理员交互；您无需与服务基础架构进行通信，你只需修改你的对象，使用数据库保存新的数据模型。

航班订座系统

假设我们在复制副本节点A有一个订位12F，在复制副本节点B有一个订位16D，跨数据中心复制后，副本节点B的值为12F。这是怎么回事？

数据库通常维护有关您的记录的一些元数 它可能是上次修改或访问记录时的时间戳，也可能是某些生成计数器。当数据库数据存储看到值不同时，它会使用这些元数据来解决您的冲突。

令人惊讶的是，这也是CRDT。这是“以最后一次写为准”的策略，其合并函数等于取a，b中的最大值。220大于150，这就是12F超越16D的原因。

在我们的设计中，我们不希望任何数据被我们无法控制的数据库元信息丢弃，因为我们希望在现有数据库之上构建我们的解决方案。

这就是为什么我们这样做的原因。我们不是存储一些标量值，而是将数据类型扩展到某个Map。当它在12F之前时，就变为A1:12F和B1:16D，这里的键key代表一个复制副本节点标识，操作的原子计数器，在每个节点内维护一个原子计数器，因为节点内部可以保证高一致性，下一次发生新数据插入，则A1将变成A2，如此累计计数器。

由于这些kley在全局范围内是唯一的，因此我们希望跨数据中心复制按键key合并这些map。在这种情况下，没有任何值会丢失。所以我们仍然拥有两个值。

如果你再看看这个Map，这些key是全局唯一的，并且它们是不可变的，因为每次计数器都是新的。当我们只能插入一个具有某个值的新键时，只添加到map，这就是CRDT。这是可交换的，幂等的和联合的，对吗？

此Map的键key集合在某个时刻唯一地标识复制副本节点的状态。这意味着我们可以使用这些数据来维持因果关系。那么因果关系是什么？如果你把Map的值的演变看作一个graph，因果关系就是你的优势。例如，我们有一些初始值12F，一些客户端将其改变到10A。因此，12F是10A的原因，那么我们可以删除12F。然后当客户从10A改变到5C，则10A是5C的因，我们可以去除10A。

这有另一种情况：当12F是10A的原因时，我们可以放弃12F，但是另一个不知道这种转变的客户，他想将10A变到5C。在这种情况下，10A不是5C的因，我们不能放弃10A，在这种情况下，10A和5C是并发值。我们称之为siblings兄弟姐妹，而且我们无法在当前时刻解决它们先后顺序。

当我们总结这张地图的所有键时，它会给我们一些因果关系向量。因此，要使用此因果关系向量，我们希望在读取数据时将其返回给客户。为此，我们需要扩展get和put操作的签名。因此我们将因果向量添加到get操作的总类型中，并将因果向量添加到其中一个参数以进行操作。

当我们提供某个版本的值时，它与比较和设置的工作方式非常相似，然后当你想写操作时，将这个版本与当前版本进行比较。

Aerospike数据存储

我们想在一些可用的数据存储上实现它，因为我们不想开发自己的数据存储，我们使用了Aerospike。这是一个混合内存键值存储。它具有非常高的性能和高吞吐量，低延迟。事实证明，大多数写入和读取操作将在一毫秒内完成。因此混合存储器意味着键的索引存储在操作存储器中，但是记录本身存储在SSD盘上。Aerospike在其集群中具有一致性强的模式，并且还具有跨数据中心复制功能。到目前为止，它看起来很合适。

Aerospike的数据模型是根据记录Record的概念设计的。您可能会将记录视为经典关系数据库中的一行。记录有一个键和元数据，但值本身存储在bin中。因此，您可能会将bin视为关系数据库中的列，唯一的区别是Aerospike不要求您为所有记录设置相同的bin。因此，每条记录可能都有其独特的箱柜。而且，Aerospike为您提供了一个API来迭代记录中的所有二进制位。

我们还使用了Aerospike的另外两个功能。第一个是用户定义的函数。LUA操作是按记录原子执行的。这些用户定义的函数帮助我们维护了这个原子计数器。如果您不使用用户定义的函数，则意味着在副本中，我们需要一些锁定机制，如乐观锁或悲观锁来维护此计数器。但是在服务器端更容易实现。

Aerospike中跨越数据中心复制的第二个好功能可以通过隔离复制bin的方式进行配置。如果你有两个bin-bin one和bin two在某个副本A中，bin 2和bin 3在副本B中，交叉数据中心复制的结果将是所有这些bin的联合，这是非常好的概念我们的设计。例如，如果您想在 MongoDB 中重复它并且您的结构类似于JSON，那么它将不是那么容易，因为您实际上需要构建一个新的JSON，它将是其中所有键的并集。所以它帮助我们用我之前谈过的合并操作维护这个因果关系图。

它是如何工作的？

当你想选择座位时，您将转到浏览器并选择一个座位，12F。由于没有初始状态，我们执行put操作，包含12F和空因果向量，空是因为没有初始状态。我们在副本A节点：A1中创建一个新的bin，其中包含12F。

我们在数据库上成功执行了它，但您的浏览器已挂起卡住，出了点问题，你不想失去选择正确座位的机会，你决定使用移动应用程序，移动应用程序连接到副本B节点服务，而副本B中没有初始状态，因此您在帐户中看不到你已经选的任何席位，这样就新选择了另一个座位，10D，移动应用程序执行值为10D且无空因果矢量的put操作。我们在副本B中创建了bin B1，它从零开始包含值10D。

在这个时刻，两个副本每个都有一个值，但是他们彼此不了解，对吧？

这完全是最终的一致性。然后交叉数据中心复制发生，bin A被复制到副本B，bin B1被复制到副本A.

所以现在，每个副本都有相同的bin组，但它们都不是彼此的因果关系。它们彼此平行。

然后你的浏览器有正常了，它说，“嘿，你成功选择了你的座位，12F。”它还会返回因果关系信息，因为在那个时刻，只有一个bin A1，你的因果关系矢量将是A1。

你很惊讶：“我刚刚选了一个地方，10D。所以我想至少验证系统工作正常”，你决定又选择一个新的位置：10F，期待它会覆盖前面其他一切选择的座位号。

这个10Fput操作:

这个10F具有因果关系上下文A1。而这正是我们的CRDT魔法发生的时刻。我们有一个新的bin: A2，其值为10F:A1。并且数据库理解该因果关系向量A1大于或等于bin: A2。这意味着bin A1是A2的原因。这意味着我们可以删除bin A1，因为它在我们的逻辑中被覆盖了。我们的客户也知道有bin A1，因为知道有这个数据值，所以想覆盖它;所以删除以前的版本并添加一个新版本吧？

你仍然有B1 bin，它与A2平行，但A1是A2的原因，这就是我们放弃A1 bin的原因。

你乘坐航班时候，要求航空公司改为商务舱，它是从副本A读取你的数据。他决定给你另一个座位，5C，这是商务舱。所以他用因果矢量A2，B1执行put操作，并且它对副本A是持久的。

所以我们创建了bin A3，因为这是副本A中的第三个操作，它具有因果向量A2和B1。CRDT魔法再次发生。我们知道A2，B1矢量大于B1并且大于A2。这就是为什么我们可以丢弃这些因，我们仍然有两个位置：A1和B1，然后再次发生复制，因此，bin A3被复制到副本B，A2具有因果向量A2，B1。即使在复制品B中根本没有A1，我们也可以做一个简单的矢量比较，说A2，B1大于B1和A1。

所以最终，你会看到我们的状态是收敛的。如果你尝试另外一个操作来置换它，它也会收敛。

学习收获

我在2016年开始研究这个项目，现在有一年多一点，我们开始投入生产。它已经工作了一年。所以我从中学到了：CRDT是真实的，他们是可行的。这不仅仅是一篇学术论文。它们肯定要求您重新考虑如何处理并发，但它允许您实现数据的收敛可预测状态，而不会在集群之间实现强同步。

第二个学习是当你想要处理你的并发性时，需要教育自己在一致性和正确性之间的正确权衡。

第三种学习永远不会低估并发数据访问。当我们开始这个项目时，当然，我们做了一些关于我们应该面对的并发数据操作率的评估。一旦我们上线，我们就认识到这个速度要高得多。问题是这种向分布式部署模式的过渡已经影响了许多其他团队。其中一些可能会错误地解释下游依赖关系如何工作的概念，或者它们如何处理流量。例如，我们遇到一种情况，即两个数据中心的消息都出了两次。

所以我想说的是，通常我们不会过度设计解决方案。但与此同时，我们设计它们时假设天气好; 每个人都工作正常，数据库总是响应，消息总是只出列一次。这并非总是如此，正是我想说的。保证解决方案足够耐用。