上一篇聊了聊构建分布式系统所面临的困难，这篇将着重讨论构建容错分布式系统的算法与协议。构建容错系统的最佳方法是使用通用抽象，允许应用程序忽略分布式系统中的一些问题。本篇我们先聊一聊线性一致性，以及与线性一致性有关的技术，后续需要了解的分布式协调服务，如：ZooKeeper等，都是基于分布式系统的线性一致性。
1.更强的一致性
大多数分布式数据库至少提供了最终一致性，这意味着如果停止对数据库的写操作并等待一段时间，最终所有读请求将返回相同的值。但是，这是一个非常弱的一致性保证，所谓的一段时间并不确定。如果写入一个值，然后立即读取它，就不能保证读取到刚才写入的值。
最终一致性的模型对于应用程序开发人员来说是个大烦恼，当使用只提供弱一致性的数据库时，开发人员需要意识到它的问题，数据库可能会有很微妙的错误，因为应用程序可能大部分时间都工作得很好。而当系统中有故障（例如网络中断）或高并发性时，最终一致性的数据模型将会暴露很多问题。所以数据系统可以选择提供的更强的一致性模型,但是又会引入新的Trade-off:有更强一致性的系统虽然更容易正确使用，但是它可能比弱一致性的系统的性能更差或容错性更低，我们需要更好的理解它并且选择最适合需求的数据模型。
线性一致性
线性一致性的思想很简单，我们用下面两幅图来说明：
在一个线性系统之中，一定会有某个时间点（开始和结束的写操作之间），x的值从0变成了1。因此，如果一个客户端的读取x时返回了新值1，所有后续的读取也必须返回新的值。
线性化与串行化
线性化与串行化不同，它不构成事务。因此不能完全保证并发写的安全性。数据库可以同时提供串行化和线性化，如两阶段锁便是可以同时提供串行化与线性化，而序列化的快照隔离不是线性化的。
线性一致性可以解决什么问题？
分布式锁和Leader选举
单Leader的系统需要确保只有一个Leader，多个Leader会导致脑裂的发生。而Leader选举的本质是锁的争用，每个节点试图获取锁，获取成功的节点成为Leader。而无论如何，这把锁必须是线性化：所有节点都必须同意哪个节点拥有锁，成为Leader唯一性约束
唯一性约束在数据库中很常见：例如，用户名或电子邮件地址必须唯一地标识一个用户，而在文件存储服务中，不能有两个具有相同路径和文件名的文件。如果你想为数据写入执行这一约束（例如，如果两人试图同时创建一个用户或一个具有相同名称的文件，其中将返回一个错误），你需要线性化。
如何实现线性化系统？
线性化意味着：如同一个单拷贝的数据，并对其所有的操作都是原子的。最简单的答案就是真的只使用一个单一的数据复制。这种方式显然就失去了容错性，单一节点出现异常则系统将无法访问。而使系统容错的最常用方法是使用副本技术：
单Leader多Follower机制
在单Leader多Follower机制之中，Leader拥有主副本，Follower在其他节点上维护数据的备份副本。可以选择从Leader上读，或同步更新的Follower，可以在这个基础之上实现线性化系统。一致性算法
通过协商一致性协议算法可以防止脑裂和读取过期数据，通过一致性算法可以实现核心数据线性化的安全存储。这是ZooKeeper与Chubby等分布式协调服务的基础算法。
CAP理论与一致性的代价
Eric Brewer在2000年提出CAP理论，简而言之便是：数据系统必须在一致性、可用性、分区容忍性的三角关系之中有所权衡，任何系统没有办法同时满足三种特性。
所以使用线性化的一致性自然会需要在可用性上做一些妥协， 在单Leader多Follower机制之下，需要满足线性化一致性的写入和读取的客户端必须连接到Leader。如果Leader产生中断，仍然可以读取Follower的数据，但此时就无法保证线性化的要求了。
2.全序广播
上文已经提到过，可以通过单Leader多Follower机制与一致性算法来实现一个线性化的系统，但是，这里还有一个很重要的内容我们需要探讨：全序广播。
不过先不要着急，咱们先再聊一聊分布式系统之中的时序：
Lamport时间戳
Lamport时间戳是生成因果关系的序列号的一种方法，我们可以通过它理清分布式系统之中操作的顺序，Leslie Lamport 在1978年提出。Lamport时间戳的实现很简单，每个节点有一个唯一计数器标识符，并且每个节点都保存它的计数器。两个节点有时可能具有相同的计数器值，但在计数器值之中都包含节点id，所以每个计数器值都可以认为是唯一的时间戳。
Lamport时间戳没有确切的物理时间，但它可以分布式系统之中的事件排序：存在两个时间戳，一个更大计数器的时间戳是更新的值；如果计数器的值是相同的，一个更大的节点ID是更大的时间戳。下图展示了Lamport时间戳的工作原理，它能够符合分布式系统之中的因果关系：
但是从Lamport时间戳的总顺序来看，无法判断两个操作是并发的，还是它们是因果相关的。虽然Lamport时间戳能够确认操作的因果关系，但是在分布式系统之中仍然存在一些问题：
请考虑一个系统，该系统需要确保用户名唯一标识用户帐户。如果两个用户同时尝试创建具有相同用户名的帐户，则其中一个应该成功，另一个应该失败。显然，如果两个相同的用户名的账户创建，选择具有较低的时间戳的操作成功，因为Lamport时间戳是完全有序的，这种比较是有效的。但是为了确保没有其他节点在同时在较早的时间创建帐户，所以节点不得不与其他每个节点通信进行确认。如果出现网络问题，其他节点中的一个已经失效或无法到达，则系统也将失效。
Lamport时间戳的问题在于：需要收集所有操作之后，操作的总顺序才会出现。如果另一个节点有其他操作，在不知道的情况下，无法构造操作的最终顺序。
全序广播
全序广播的机制是使用：通过单Leader多Follower机制，在Leader节点上对所有操作进行排序，从而决定了整个操作顺序，并将操作顺序进行广播。全序广播可以保证全局知晓信息，而解决Lamport时间戳面临的问题。但是全序广播同样要解决这样几个问题：如果吞吐量大于单Leader的处理量，那么如何扩展系统，以及出现Leader失效的情况，如何进行故障转移。
全序广播要求满足如下两个属性总是被满足：
- 可靠的交付,没有消息丢失：如果消息被传递到一个节点，它将被传递给所有节点。
- 完全有序传递，消息以相同的顺序传递给每个节点。
一个正确的全序广播算法必须保证节点和网络故障时的可靠性和有序性。一旦出现网路分化的现象，算法可以保持重试，仍然保持信息的有序性。全序广播对于分布式系统来说有十分重要的意义：如果每个消息表示对数据库的写入，并且每个副本以相同的顺序处理相同的写入，则副本将保持彼此一致，而各个节点的状态机也能够保持一致，可以通过这样的方式来实现状态机复制。
3.通过全序广播实现线性化一致性
全序广播是异步的：消息保证以固定的顺序可靠地传递，但不能保证何时传递消息（因此存在节点可能落后于其他节点）。而线性化一致性能够保证：每次读操作能够读到最新值的写入。我们可以依托于全序广播，在存储上实现线性化一致性：
1.将消息append到日志中，添加要声明的用户名。
2.节点通过内存之中的状态机检查，如果该用户名的第一条消息，则用户名写入成功。否则，终止该操作。
由于全序广播保证了，消息是以相同的顺序传递给所有节点，假设存在并发写入，所有节点都会达成共识，第一个写入用户名的消息。虽然全序广播可以保证程序的线性写入，但是假设进行读操作的节点却不能保证线性读取，因为消息传递的延迟性，所以读操作的结果可能是过时的。
当然这里可以通过返回最新日志消息的位置，通过查询位置，等待所有条目需要读取的条目被写入，再进行读操作，便能够达到读操作的线性一致性。（在ZooKeeper中通过sync()操作实现），或者可以通过强制读取Leader节点的副，显然Leader节点上的数据一定是最新的结果。
小结：
通过全序广播的线性一致性，我们已经可以实现一个分布式系统的的协调服务了。下一篇将聊一聊分布式系统之中的一致性协议，也是分布式系统最核心的概念，我们怎么样能够让分布式的节点达成一致性，难者不会，会者不难，我们下一篇见。
