从DCOS项目谈谈CRDT的使用（crd模式）

近日，Mesosphere开源了完整的数据中心操作系统DCOS解决方案。在DCOS中，值得注意的是几个Erlang写成的组件，包括服务发现和负载均衡。在Mesos/Kubernetes/Nomad等为微服务提供容器编排的PaaS中，服务发现和负载均衡有许多解决方案，比如HAProxy/Consul/Bamboo，比如Traefik，比如Mesosphere-DNS，SmartStack等等。这些方案在公司中得到了大量运用，比如Airbnb，Yelp，Cisco，Apple，等等。然而，DCOS项目为什么要重新实现这一套，而且还用那么小众的Erlang呢？这主要是考虑到大规模网络下更好的高可用和容错设计。

在DCOS中，除了监控和UI，一个核心组件叫做Minuteman，它在DCOS中的角色是负载均衡，并且是分布式高可用的负载均衡，用户可以在DCOS中指定Minuteman暴露的虚IP地址，从而作为整个集群访问后端服务的入口。Minuteman在设计上的一个亮点是容错设计，这是由Lashup组件来负责的。

Lashup本身是一个称作overlay的中继网络，它是一个维护了节点之间连接状态的巨大图。每个节点都内嵌一个邻接表，并通过gossip机制同步到其它所有节点，这些邻接表用于应用层多播。节点之间连接由自适应Ping算法来监控，当连接出错，或者有新连接时，都会通过gossip同步状态。在利用gossip同步状态时，Lashup做了一些修改，主要是避免gossip过长的收敛时间。根据试验，维护1000个节点的邻接表，每个节点设置为扇出(fan out)6个广播信息，需要50M的存储。自适应Ping采用1秒的间隔对连接做健康检测，每个连接的所有历史的Ping数据也保存下来，用来决策未来连接round trip时间的正常范畴。Lashup针对容错设计的目标是：gossip能够在1.5秒内让集群90%的节点获悉某节点的失效信息，同时系统需要能够检测网络割裂(脑裂)，例如有Master节点M1，M2，M3，Agents节点A1，A2，A3，A4，A5，Lashup需要能够检测A[1-5]能够跟M[1-3]通信，但A[1-2]无法跟A[3-4]通信的场景。这种脑裂的场景在云平台中时常会发生。在Lashup overlay中继网络同步的数据，包括可路由的节点信息如IP地址，端口，以及节点本身运行的任务信息。在一个巨大的集群中，每个节点都会以秒为间隔更新自身的状态，同时迅速让其它节点能够读取，做到这样的要求并不容易，Lashup采用了一种称作CRDT的数据结构。

谈起CRDT，本号在之前也有提及：它的全称叫做Convergent Replicated Data Type，目的是提供不用协调的收敛到一致的数据结构，因此又称为Conflict-free Replicated Data Type。分布式计数器是CRDT数据结构中最常见的一个例子：假设每个用户都能写入到自己的计数器中，当每个用户需要改变它的计数器数值时，它只改变自己的数值，那么，在分布式系统中，如何得到最后的整个计数器结果？只要将单独的这些计数器加起来即可，所以为了得到一个全局整体的计数器，每个节点用户都需要知道彼此另外节点上的计数器值，这就需要在节点间广播这些值。可是网络不是100%可靠，广播的消息有可能会丢失或延迟到达，解决这个问题就变得更加复杂：

1. 在发送方，节点服务器规则地广播它们的状态。

2. 在接收方，需要一种方式搞清楚发现消息的重复，节点服务器通过比较接受值和现有值，如果这两个值是相同的表示这是重复的消息，否则就是一个新的消息，更新原来的值即可。

解决延迟消息投递问题需要另外的技巧：假设计算器总是不断向前增加，不允许减少。那么现在该发现当接受到消息应该怎么做了：只要选择接受值和现有值之间最大差值的那个值。这样，每个节点都知道接受到消息后该怎么做，就有了最终一致性，因为只要一个节点接受到所有广播消息事件（无论以任何顺序），它会知道计数器当前状态，每个节点的状态也是相同的，没有冲突，所有节点最终会汇聚到相同的值。这就是CRDT的分布式计数器。

CRDT还有其他一些种类，比如Map，Set等等，在Lashup中采用的是Map。目前，CRDT在商业环境下采用得并不多，Riak是为数不多的实现了CRDT的存储引擎，而Lashup就是基于Riak[2]构建，这也是Lashup采用Erlang开发的原因之一。在Lashup overlay中继网络里，每个节点维护的信息可达数K乃至数百KB，在gossip广播中，每秒都广播如此大的数据会导致很高负担，因此Lashup采用了类似上面计数器采用的Delta-CRDT机制[1]，只广播增量变化数据，而Riak DT[2]为Lashup提供了构建这些元素所需要的所有基础组件。Riak是采用Dynamo模型的分布式KV，根据测试，在实际中会产生很多写入丢失的问题，而作为最终一致性保证的Riak DT就没有这方面的问题[4]。因此，要求最终一致性场景的需求，都会或多或少得引入CRDT设计。

基于CRDT数据结构，整个Lashup可以看做是一个最终一致的分布式Key-Value数据库，它在DCOS中扮演许多角色，除了做容错检测之外，还包括给Minuteman发布虚IP地址，配合Minuteman实现比较新的负载均衡算法例如Joint-Idle-Queue[3]，这些新型算法需要结合节点错误信息来决定如何更好的平衡负载，而不是通常的round-robin或者随机算法，因此在大型数据中心分布式负载均衡中表现更好。除此以外，很多依赖发布订阅来做的功能，在DCOS中也用Lashup实现，比如安全策略等。

总体来看，这是笔者看到的第一个CRDT数据结构在大规模系统中运用的成功例子。DCOS利用CRDT和gossip机制，应对大规模集群(包括跨中心)的容错和高可用信息同步，仅就这个项目而言，的确是领先的设计。

[1] Efficient state-based CRDTs by delta-mutation, Almeida, Paulo S'ergio and Shoker, Ali and Baquero, Carlos, arXiv preprint arXiv:1410.2803, 2014

[2] https://github.com/basho/riak_dt

[3] Join-Idle-Queue: A Novel Load Balancing Algorithm for Dynamically Scalable Web Services, Lu, Yi and Xie, Qiaomin and Kliot, Gabriel and Geller, Alan and Larus, James R and Greenberg, Albert, Performance Evaluation, 2011

[4] https://aphyr.com/posts/285-jepsen-riak