前言

随着近年来微服务理论越来越流行，其基础之一的服务发现也越来越受到人们的重视。传统的单点服务仓库受限于不易扩展、容灾麻烦等缺点的考虑已不再适用于复杂的集群系统。目前来说，大多数的成熟服务发现系统采用的是zookeeper、etcd或是consul作为服务存储仓库，如kubernetes用的就是etcd。虽然以上三种组件内部协议和功能侧重点各不相同，但最终都实现了一个具有强一致性、高可用性、分布式的存储系统。对于这样的存储系统，分布式支持服务发现可用水平扩展、高可用性可以保证了服务发现的稳定性，KV系统存储了服务数据，而唯一有质疑的是强一致性。下面我们要探讨一个问题，究竟服务发现是否真的需要强一致性？网上有一篇文章《为什么不要把ZooKeeper用于服务发现》探讨了这个问题。有兴趣的同学可以看一下。
　其实强一致性有两个方面限制了服务发现：

• zookeeper这类组件的强一致性是有代价的：即在一个2n+1个节点组成的集群中，一旦少于n+1个节点工作，就不可用。假设一个服务发现集群有5个节点，当3个以上节点出现故障时，整个集群也就无法提供服务了。拿CAP理论来说，就是牺牲了A（可用性）换取了C（一致性），但对于服务发现系统，一般可以接受返回几次错误数据，但是决不能容忍服务停摆的。
• zookeeper这类组件虽然可以支持扩展，但受自身实现一致性协议的限制，扩展节点数目越多，为达到半数的通信成本也越高，因此是无法实现无限扩展的。

本文介绍了一种基于流言协议的KV存储系统，该系统具有最终一致性、分布式、高可用的特点，可以有效的运用与服务发现系统。

服务仓库工作示意图

流言协议

流言协议是一个去中心化的通信协议，当某节点收到一个新事件时会有以下的操作：

• 随机的选择其他n个节点作为传输对象。
• 若其他节点第一次收到该事件，则随机选择n个节点转发。
• 每个收到事件信息的节点重复完成上述工作。

流言协议主要实现了两个功能：节点存活检查和消息传递。常用的检测节点存活技术是心跳协议，即定时发出心跳包来证明自己存活。但这样的心跳协议有很多缺点，首先如何是确保心跳包准确送达目标节点，如果网络问题导致心跳包没有正确送达，会不会误伤健康的节点？这个虽然可以通过协议来解决但同时导致了协议的复杂度。其次心跳协议是一个端到端的协议，如何应用与大规模的集群中？采用星型拓扑结构会带来单点问题；采用多对多拓扑随着节点数目过多带来通讯成本急剧上升；采用环状拓扑会因为同时两处节点故障导致不可用。消息传递同样面临这存活检测遇到上述问题，如何保证数据准确传达和选择通讯拓扑结构？对此流言协议可以很好的解决这些问题。

不靠谱的拓扑结构

"SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol"。这篇论文详细描述了流言协议实现方式：

• 采用两次检查的存活协议，节点定时ping已知任一节点，如果没有收到ack，则转发请求给k个节点，让这些节点发送ping给被检测节点，若这些节点都没有收到ack就认为被检测节点有问题。
• 需要传输的数据作为ping和ack包的附带数据一起传输，有效减少传输次数。

此文章同时也论证了流言协议两个特点：

• 对于每个节点来说，存活检查需要的时间和数据载荷大小与集群规模无关。（成本固定）
• 对于一个n个节点的集群，消息传递到全部节点的时间是K*log(n)。（快速收敛）

流言协议的传播速度

服务发现的KV存储系统

现在我们需要设计一个用于服务发现的KV存储系统，考虑到实践运用场合，该系统应该具备：

• 分布式：存储系统由多个节点构成。
• 高可用：每个存活的节点都能提供服务。
• 最终一致性：任一节点上的数据变化最终体现在各个节点上。由于服务启停是个频率较低的过程，服务发现系统可以忍受几秒的数据的不一致，但要求最终提供的服务数据是一致的。
• 状态检测：新增或是移除节点，亦或是节点故障，其他节点必须知悉，并对应新增或删减数据。

我们不难发现分布式、高可用和状态检测这些特性流言协议已经实现了。无论集群的节点数目有多少，每个节点只要付出固定的成本就可以实现快速的存活检测和数据传输。这样我们可以构建这样的模型：

• 集群中的每个节点各自维护一个KV存储。
• 对节点KV数据的修改都会通过流言协议扩散到集群其他节点。
• 节点收到其他节点数据增减消息后会对自身的KV存储进行增减操作并扩散。
• 新增节点在加入集群后立刻将本节点存储的数据通过流言协议同步给集群其他节点。

但是这样模型还是有些问题。假设两个不同节点同时对一个Key值的数据进行修改，那对于集群的其他节点来说，究竟应该采用哪个节点的数据？这种情况会导致丧失最终一致性。我们发现仅仅依靠流言协议是无法实现服务发现的，还要做一些其他的工作。
　针对服务发现这个特殊场合，我们不难发现一个特点：每个节点只会主动增减和自己相关的数据。也就是说A节点上服务发生变化只会让A节点增减数据，其他节点只是被动的接收A节点的数据变化。A节点上的数据，A节点具有最终的发言权！为了解决不同节点同时写带来的数据不一致问题，我们加上两条规定：

• 每个节点只能修改属于自己的数据，然后再将数据同步给集群其他节点。

• 当某个节点故障或脱离集群时，其他的节点删除与此节点相关数据。

  
  数据同步模型

但这并不能完全解决最终一致性的问题。流言协议不能保证传输的顺序性，也就是说假设A节点先发送了消息a=1，再发送a=2。B节点可能会先收到a=2再收到a=1。消息传输完毕后，我们发现A节点中a=2，B节点a=1，失去了最终一致性。其实解决这种只有唯一写者的顺序不一致问题很简单，只需要对每个消息添加一个版本号就可以。只有收到的消息比当前数据版本号新才修改数据。在这新增两条规则：

• 每个节点维护一个版本号，当修改数据时增加此版本号。其他节点收到同步消息时对比消息的版本号和自身数据的版本号，只有发现消息版本号大于数据版本号才对数据进行修改。
• 删除数据时并不直接删除数据，而是记录下此时的版本号，标记此数据删除，防止过时消息污染数据。经过一段时间才回收被删除数据。

到这里看起来已经解决了最终一致性的问题，但是在实践运用场合我们发现这样的问题。如图在T3时刻，A节点发生崩溃重启再加入集群，由于重启时间较短，集群其他节点不认为此节点失活因此保留A节点相关数据。但新启动的A节点并不知道崩溃前的最新版本号，还是从版本号1开始同步数据。这个同步消息自然遭到目前版本是3的B节点的拒绝，至此最终一致性丧失。

节点崩溃导致最终一致性丧失

　解决这个问题有两个思路，一个是实时将节点最新的版本号记录在本地文件或是外部存储器中，这样即使崩溃重启也能恢复最新版本号。另一种方法比较简单，按照之前的原则”节点具有本节点数据的最终发言权“，当A节点发现属于自己节点的数据版本号竟然比自己当前版本号还大时，就立即明白本节点的版本号已经过时了。这样将本节点版本号置为数据版本号+1，再同步数据，就解决了这个问题。如图虽然T4时刻同步失败了，当T5时刻收到B节点转发的数据后，A节点更新了自己的版本号，只后同步数据就OK了。在此新增一条规则：

• 节点收到属于自己的数据消息且发现版本号比自己版本号大时，更新自己的版本号。

  
  更新过时版本号

通过以上的几条规则，我们成功的在流言协议的基础上实现了最终数据一致性，从而完成了基于服务发现KV存储的设计。在实际使用过程中，服务端嵌入KV存储来实时更新集群可用服务，客户端既可以通过嵌入KV存储也可以通过查询嵌入KV存储的DNS服务器来查询服务。

基于流言协议的服务发现框架

代码实现

实现流言协议并不是一件轻松的事情，幸好hashicorp的memberlist组件已经帮我们实现了流言协议主要功能。memberlist的流言传播用的是udp协议。这带来一个问题，众所周知udp是一个一个包传输的，数据信息作为ping或ack的附加载荷受限与udp包的大小，这限制了包的信息的传播速度。幸好服务发现数据量不是很大，udp包也完全满足。但只有一种情况除外，那就是新节点加入集群时需要同步自己全部的数据，此时数据量就可能比较大了。如果只用udp传输协议，可能导致数据同步比较慢。memberlist为此新增了tcp同步的功能，我们可以利用tcp同步的接口一次传输大量数据，加速数据收敛速度。

参考

https://github.com/hashicorp/memberlist
https://github.com/docker/libnetwork
Gossip Protocol
SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol