CAP理论

加州大学终身教授与著名计算机科学家Eric Allen Brewer在90年代末提出了CAP理论，理论断言任一个基于网络的分布式系统，最多只能满足“数据一致性”、“可用性”、“分区容错性”三要素中的两个要素。

该理论后被MIT证明可行，故架构师无需将精力浪费在如何设计能满足三者的完美分布式系统，而是应该进行取舍。 

CAP理论也即被捧为“分布式系统设计”的重要评分标准，其包含下述三项定义：

• Consistency(一致性)：集群中所有节点在同一时刻可见同样的值。

• Availability(可用性)：健康的节点在限时内，可返回可靠的结果。

• Partition tolerance(分区容错性)：集群中某些节点失联后，集群仍可继续服务。

那为什么一个系统只能同时满足三要素中的两个要素呢？我们来看看下面例子：

1.首先使分布式系统满足“分区容错性”要素：

当上海、台北服务器共用数据存储时，上海数据中心存储的宕机将造成台北服务器也不可用，拓扑图如下。

如何来满足分区容错性：我们可在各数据中心分别建存储机制，在各数据中心存储进行写操作的同时，触发存储同步，保障数据中心间存储数据同步。

故当任一数据中心存储宕机，也不会造成其它数据中心的存储读写操作，如下图所示：

2.满足“分区容错性”的前提下，“一致性”，“可用性”两者只可选其一假定当前两地存储中的数据为“版本1”，此时上海与台北数据中心网络中断，存储间无法同步。然后上海服务器将数据版本更新为“版本2”，由于同步受阻，台北数据中心仍保存数据版本“版本1”，如下图所示：

“台北服务器向台北分区存储进行查询”这一动作在CAP理论模型下只能满足下述情况之一

（CP）保障“一致性”，放弃“可用性”：

等待网络恢复正常，上海存储将“版本2”同步至台北存储，台北存储将满足“一致性”的数据“版本2”返回给服务器。

由于网络恢复时间的不确定性，请求可能会超时，违反“可用性”限时的条件。

（AP）保障“可用性”，放弃“一致性”：

台北存储在“可用性”高响应的驱动下将过期数据“版本1”返回给服务器。

由于返回的“版本1”与最新数据“版本2”不一致，违反了“一致性”。

CAP理论小结：

无论CP，AP还是CA，在CAP理论驱动下的系统，都以SLA（Service Level Agreement）为系统最终评估基准。目前SLA 5个9乃至6个9的系统，都会以AP设计为重，略微放弃一致性来换取系统的“活”。

目前主流的分布式系统设计理论BASE（Basically Available 基本可用）（Soft State 软状态）（Eventual Consistency 最终一致性）则是对CAP中AP理论的扩展，通过实现“最终一致性”来保障SLA的同时确保信息准确。

基于BASE理论设计的主要的产品则为主流NoSQL数据库：包括Cassandra，MongoDB，Redis, CouchDB等。

故在AP模型稳定的情况下，SLA指标中能有几个9，与Consistency（一致性）的算法实现密切相关，下面我们来看一下“一致性算法”

一致性算法Raft

20世纪80年代开始，一致性算法的研究就没有停止过，主流的实现则依赖共享内存（Shared memory）和消息传递（Messages passing）。直至21世纪的今天，基于“消息传递”为一致性算法实现的系统占到了绝大多数。

微软研究院首席科学家、2013年图林奖获得者LeslieLamport于1990年提出的一种基于消息传递且具有高度容错特性的一致性算法Paxos。该算法的典型应用场景为分布式数据库：在一个多节点的分布式系统中，“使用一致性算法”保证每个节点执行相同的命令序列，确保每个节点的状态一致。

Google的分布式锁服务Chubby，Apache的分布式服务框架ZooKeeper都是基于Paxos算法进行的实现。Paxos也是类似算法中最为可靠与广知的，但Paxos算法的流程复杂与实现困难导致世界级产品数量极少。

2013年来自Stanford大学的DiegoOngaro、John Ousterhout发布论文“In Search of an Understandable Consensus Algorithm”，公布了的新的分布式协议研究称为Raft，它是一个为真实世界应用建立的协议，主要注重协议的落地性和可理解性。

时至今日，Raft的易实现性使其成为与Paxos同级别的一致性算法，在Raft的Github官网上，已发布了十多种Raft一致性算法的实现，生态圈日渐强大。详细信息可见：https://raft.github.io/

主流的服务发现框架Etcd，Consul等都是基于Raft一致性算法实现的。Google开源的容器集群管理Kubernetes作为Docker生态圈中重要一员，也是基于Raft来管理一致性的。

Raft算法拆解后主要包含三大功能，各功能运作的完整流程也可参考Raft可视化网站，让我们通过生动的图形来了解Raft算法的秘密吧！

网址：

http://thesecretlivesofdata.com/raft/

1.       Leader选取：

Raft服务集群中有3个角色Leader，Candidate与Follower。Leader则会统一管理Follower与自己的状态机同步。

Raft使用心跳机制来触发选举Leader。在没有Leader的情况下在Follower默认的“选举计时器”（150毫秒到300毫秒超时）超时后，将会推举自己为Candidate，当大多数（n/2+1 ）节点同意后将会升级为Leader。然后Leader与Follower间使用心跳进行状态维护，只要心跳是在“心跳计时器”超时范围内，Leader状态则可永久保持。

在Raft算法内，只会存在一个Leader与多个Follower，集群维护单个数服务器。

*在极端多Follower“选举计时器”同时超时，多Candidate同时出现的情况下，则以收到其他Follower推举回应同时重置“选举计时器”的时间点来决定最终Leader。

Leader选举的流程如下，图来自Stanford论文：

2.       日志复制、同步：

Leader角色负责日志同步，流程如下：

当Leader收到客户端信息，则先写入本地日志文件，同时将信息发给其他Follower。当大多数Follower保存至本地成功，则回复Leader成功，Leader获取大多数Follower回复后，提交本地写入的日志，并则通知客户端收到信息。

如Follower有丢包或者奔溃，Leader将进行重试来保障一致性。所以数据的最终提交、状态机的维护将由Leader决定。Leader会保障多数节点写入信息来进行最终提交。

如下图所示，Leader上最后写入的x<-4未被提交，则是由于仅有Leader与1/4的Follower，共2/5的节点写入此日志。而x<-5则有Leader与1/2的Follower，共3/5 (n/2+1)节点写入此日志，Leader发现大多数节点3/5已写入信息成功，做了最终提交。

3.       安全性：

Leader作为Raft集群的控制核心，也存在奔溃的可能。此时则集群中任意Follower可推举自己为Candidate。Raft的安全性保障当Follower如没有获得当前完整Committed entries（见上图）时，则无法成为Candidate。此安全性举动保障了数据的可靠性，不会丢数据。

如要保障新选举的Leader不会将过期脏数据同步至Follower。安全性检查会在做数据的提交时，也检查当前Leader所要提交的数据至少有一个存储在大部分Follower上。

当新Leader在工作的同时，老Leader突然恢复工作。Raft的安全性保障使用Term号的方式使老Leader发出的过期Term号对所有Follower都不生效。保障了老Leader不会触发错误同步，直至降级为Follower。

Raft一致性算法小结：

Raft通过算法实现强一致性。但是其单一Leader节点的设计在写操作量大的情况下会造成单点写瓶颈。故使用场景为读操作大于写操作的，对一致性要求高的系统。

服务发现框架Consul介绍

Consul为Hashicorp公司使用Go语言编写的开源项目，其核心是基于Raft（CAP一致性算法）与Gossip（BASE最终一致性算法）进行实现的。基于Raft与Gossip的Consul集群，可保障Consul Server集群（服务端）间的数据一致性同步，Consul Server集群与集群间、Consul Agent（客户端）与Agent间的数据最终一致性同步。

*Gossip最终一致性算法尝试解决的问题是：在一个有界网络中，每个节点都随机地与其他节点通信，经过一番杂乱无章的通信，最终所有节点的状态都会达成一致。Gossip具有“去中心化的特点”，也天然具有分布式容错，虽然无法保证在某个时刻所有节点状态一致，但可以保证在”最终“所有节点一致。

Consul的特色非常适合融入当前互联网公司的微服务架构，可轻松覆盖多种操作系统。官方已经发布的Consul客户端支持Mac OS X、FreeBSD、Linux、Solaris、Windows等多种操作系统，发布在这些操作系统上的Restful API都可轻松接入Consul集群。

Consul产品开源的同时也提供了多种语言的接入SDK，包括Go，Python，Php，Scala，Java，ErLang，Ruby，Node.js，.NET，Perl等，大大降低了开发人员的接入工时。

下图为Consul在多数据中心部署的架构图，单数据中心内使用Raft算法保障服务端一致性，同时使用Gossip协议进行跨数据中心（WAN Gossip）同步，与客户端间（LAN Gossip）同步。

两种一致性算法结合使用的Consul集群可保证各个节点的数据一致。

.NET API服务如何接入Consul服务发现框架

首先将Consul以服务端模式部署在至少3台（总台数为单数）服务器上，然后在.NET API部署服务器上安装Consul Agent模式。

由于.NET API多运行于Windows服务器上，可使用nssm.exe（http://www.nssm.cc/）来进行从命令行至windows服务的包装，保障跨Windows会话的安全性。

服务端启动脚本，需使用-ui-dir来指定UI项目路径

Agent端启动脚本仅需加入指定Consul服务端集群

Consul服务端与Agent端启动后，可通过http://consulserver:8500/ui 地址进行Consul集群健康状态管理。

.NET API服务发布与发现的SDK接入方法：

通过Nuget包管理器还原并安装Consul.NET SDK安装包，当前版本为7.0.5。使用SDK安装包中提供的ConsulClient.Agent.ServiceRegister方法进行“服务注册”，可使用的默认Agent地址为http://127.0.0.1:8500/ 核心方法如下

使用ConsulClient.Agent. ServiceDeregister方法进行“服务注销”

使用ConsulClient.Health.Service方法进行“服务发现”，将会返回符合要求的服务列表，后通过主流负载均衡算法进行最终服务筛选，完成服务发现流程。

在.NET API启动与退出时集成Consul.NET SDK相应的注册与注销方法，完成服务自注册。在.NET API需要与其他API进行通讯时，使用服务发现方法完成地址查询，后发起Restful HTTP请求完成API调用。

进行服务注册时，需通过AgentServiceRegistration.AgentServiceCheck类型将心跳HTTP的接口信息，心跳间隔信息等同时递交注册，ConsulAgent将会以配置好的间隔对服务进行心跳检查，来保障任意Agent进行“服务发现”时，获取的注册API为可用的。

Consul服务发现框架集成小结：

在Consul集群基础设施部署完毕，相应SDK语言包成熟的基础上，用户开发的Restful API可轻松接入集群。Consul的核心架构于一致性算法的基石上，各服务节点的信息可靠性、可用性得到高保障，服务与服务之间可无障碍进行沟通，形成微服务网。

参考文献：

https://en.wikipedia.org/wiki/Eric_Brewer_(scientist)

https://en.wikipedia.org/wiki/CAP_theorem

http://www.julianbrowne.com/article/viewer/brewers-cap-theorem

https://en.wikipedia.org/wiki/Raft_(computer_science)

https://ramcloud.stanford.edu/wiki/download/attachments/11370504/raft.pdf

https://en.wikipedia.org/wiki/Paxos_(computer_science)

https://en.wikipedia.org/wiki/Gossip

https://raft.github.io/

http://thesecretlivesofdata.com/raft/

https://www.consul.io/docs/internals/architecture.html

https://www.nuget.org/packages/Consul