信息、真相和谎言

这章阐述分布式系统中的基本问题：我们能判断哪些事情的真假？我们如何确定信息，测量和感知是否可靠？软件是否会违背现实世界法则，起因和影响是什么？以及分布式系统中关于信息和真相的一些常识。

 

事实由多数决定

设想一个发生不对称的网络问题的场景：

一个节点能够接受到其他节点的信息，但是其他节点没法收到它的信息，结果就是其他节点没有收到关于它的反馈，虽然该节点正常工作，但是系统只能认为它已经“死亡”。

如果节点能够发现其他节点没有回应它所发送的信息，它可能意识到网络出了问题，可能意识到它已经被宣布“死亡”，但是它对此无能为力。

第三个场景是节点经过了长时间的垃圾回收。在垃圾回收期间，节点不会处理任何请求，不会发出回应，因此在经过长时间的等待后，其他节点会认为该节点已经“死亡”。

上述例子是为了说明，系统中一个节点的状态不是由自己决定的，而是由其他大多数节点决定的。分布式系统不依赖单一节点，依赖“阈值”。使用“阈值”，即便少数节点挂掉，系统也能运行。

 

主节点与锁

系统经常需要一些全局唯一的事情。比如：单主节点，分布式事务或者分布式锁，全局唯一的用户名。

实现全局唯一性，需要注意的是：某个节点可能自认为自己是主节点，但是其实其他节点并不这么认为。

一个节点，可能自己认为自己是被选中，但是其实不是，如果该节点继续运作，可能造成错误，例如：

client1经过长时间的垃圾回收后，失去了锁，但是它仍然认为自己持有锁，结果出错。

 

排他令牌

当使用锁来保护系统资源时，我们需要确保，一个自认为自己被选中，但实际不是的节点不会影响系统的其他部分；可以使用一个简单的方法，“围栏”来达到目的。

每次请求获取锁的时候，锁服务都会返回一个令牌。节点需要带着令牌去访问资源。如图8-5，token：34优先于token：33，所以client1的请求被拒绝。这个机制需要资源服务自己比较token，只依靠客户端自己是不够的。

 

拜占庭将军问题

围栏令牌可以组织节点不小心造成的破坏，但是如果是节点要故意造成破坏，那么它只要发送伪造的令牌就行了。

本书里，我们讲节点看成是不可靠但是是诚实的。节点可能慢或者失去响应，但是如果节点给出响应，那么我们认为它们通知的是事实，它们遵从协议。

如果分布式系统可能“撒谎”，那么会变得更加复杂。例如，一个节点可能声明收到了特定的消息，但实际上它没有：这种行为称为“拜占庭故障”，在无法信任的环境中要达成一致，这称为：拜占庭将军问题。

如果一个系统能够处理拜占庭故障，或者是恶意的网络攻击，那么它能容忍拜占庭故障。拜占庭故障只与特定的场景有关：1、外太空环境，电磁辐射会干扰内存或者CPU，或导致节点作出无法预测的回应。2、在跨公司合作的系统，一些参与者试图欺诈其他参与者，这种情况下，一个节点无法简单地信任其他参与制。

但是本书中，默认讨论的系统不会有拜占庭错误。公司内部的节点都是可以信任的，辐射也不会成为问题。应对拜占庭问题的协议很复杂，而且需要硬件支持，对于绝大多数数据服务系统来说，要应对拜占庭错误是不实际的。

 

系统模型和现实

为了解决分布式系统问题，有不少算法。算法需要尽可能独立于软硬件，用于应对特定的错误，我们可以将特定的错误和应对方法称为“模型”。

最常用三个模型：

1、同步模型：同步模型认为网络延迟，进程暂停和时钟误差都是有边界的。这并不意味着同步时钟和无网络延迟，知识认为网络延迟，时钟偏差和进程暂停都在特定范围内。同步模型在现实中并不实用，因为无限暂停和延迟确实会发生。

2、部分同步模型：部分同步意味着大部分时间，系统是按照同步模型来运行，但是有时候网络延迟，进程停顿和时钟偏移会超过限度。这也是现实中大部分系统会使用的模型：大部分时候，网络和进程工作良好，但是系统不可能永远正常运行，我们不得不认为可能发生糟糕的事情，那时候，网络延迟，进程停顿和时钟偏移会超过限度。

3、异步模型：模型不允许作出定时的假设，甚至可能没有时钟（不能使用超时设置）。

在时间问题之外，我们不得不考虑节点故障，有三种最常用的模型：

1、故障-停止：在故障停止模型中，节点可能在任意时候停掉，然后用于你不会恢复。

2、故障-重启：节点可能在任何时候停机，任意时间后开始回复。在这个模型中，节点被认为是有持久化存储，从故障中恢复后能读取，但是内存中的数据会丢失。

3、拜占庭式错误：节点的任何事情都是不确定的，可能欺骗其他节点。

现实中最常用的就是部分同步模型和故障-重启模型。

 

算法的正确性

先描述下算法的正确性，正确性就是算法具备某些特性；比如一个排序算法，它的特性就是输出一组元素，左边的元素不大于右边的元素，如此称之为正确。

类似的，分布式算法需要具备一些特性才能称之正确。例如，如果是为锁生成围栏令牌，需要算法有以下特性：

唯一性：两个请求不可能得到相同的值

单调递增性：请求x获得令牌tx，请求y获得令牌ty，x先于y完成，则tx<ty

可用性：一个无故障的节点请求令牌，最终总能得到回应

只有在系统模型中满足某些特性，算法才称之为正确。

 

安全特性和存活特性

为例分辨场景，需要辨别两种不同的特性：安全和存活特性。在之前的例子中，唯一性和单调递增是安全特性，可用性是存活特性。分辨它们的一个简单方法就是存活特性的描述中总带有“最终”这类字眼。安全特性一般被定义为“不会发生坏事”，存活特性一般被定义为“最终会发生的一些好事”。更正式的定义：

1、如果违背了安全特性，我们能够找出什么时间什么地方出错了（比如返回了相同的围栏令牌，我们可以找出哪个特定的操作导致返回了相同的令牌）。在安全特性被违背后，损坏无法撤销。

2、存活特性相反：某些时候无法保证特性（比如发出一个请求但是还没有回复），但是未来终会满足（收到回复）。

 

系统模型映射至现实

安全特性，存活特性和系统模型都可以用来解释分布式系统的正确性。但是当实现算法的时候需要处理海量的细节。

 

总结

这章讨论了分布式系统中普遍存在的问题，包括

1、通过网络发包，可能延迟，可能丢失；回复也可能丢失或者延迟。如果没收到回复，就不知道信息是否收到了。

2、一个节点的时钟可能与其他节点不同步。因为时钟存在偏移，也没有很好的方法进行检测，因此依赖时钟是很危险的。

3、进程可能在运行中的任何时间暂停相当长的时间，然后被其他节点宣布挂掉了，但是它回复过来后依然继续工作没有意识到之前的暂停。

事实上局部错误就是分布式系统的特性之一。

为了应对错误，第一步就是检测它们，但是这很难。绝大多数分布式系统没有准确的方法检测节点是否故障，只能使用超时机制来判断节点是否可用。但是超时机制无法分辨是网络故障还是节点故障，网络延迟也会导致误判。并且，节点也可能处于低速状态（因为驱动错误导致吞吐降到1kb/s），这种节点更难处理。

检测到错误后，处理起来也不简单。没有全局变量，没有共享的内存或者其他的共享机制，节点间甚至连时间都没法达成一致，遑论其他事情。唯一能传递信息的方法就是使用不可靠的网络。因为单一节点来决定事情是不可靠的，所以需要阈值机制。

这章也讨论过不可靠的网络，时钟和进程是不是分布式系统中不可避免的，结论是：不是。但是要处理上述问题需要高昂的投入。绝大多数对安全性不严格的系统会选择不可靠、廉价而不是可靠、昂贵。

这章浏览了这些问题，给出了一个悲观的前景，下一章就讨论解决方法。