1. 故障与部分失效

部分失效：分布式系统中，一部分正常工作，另一部分出现故障。而这些故障往往不确定，从而提高了分布式系统的复杂性。

部分失效是分布式系统中必然面临的，因此软件系统需要提供容错机制，提供可靠性（即在不可靠的组件上构建可靠系统）。

2. 不可靠的网络

由于大部分使用异步网络（之前文章有提及），数据从一个节点发到另一个节点，但不保证什么时候到达，也不保证一定到达，出错的位置从发送到接收都有可能：

本机：请求在队列未发送（可能网络/对方超负荷）/收到回复但延迟处理（可能网络/本机超负荷)
网络：发送时请求丢失/应答时回应丢失
远程节点：节点失效/暂停无法响应（可能在进程暂停，如GC）

可采用超时机制，但不能确定是什么原因造成的，如不能确定远程节点是否受到请求。

网络分区/分割：网络的一部分由于故障与其它部分断开。

2.1. 超时与无限期延迟

基于超时的故障检测，设定的超时时长要适当（过短则会由于小扰动而误报，而平衡集群会带来额外的负担；过长则需要更长时间的等待）。

2.1.1. 网络拥塞与排队

网络上的数据包延迟往往源于“排队”：

交换机的缓冲区会排队（若数据量过大可能会丢弃数据）
机器忙，消息在操作系统的队列中待处理
TCP等实现背压/流量控制功能的协议下，节点会限制发送的速度，即在发送端排队

因此，一般使用实验的方式设置超时，或者通过测量而变化地设定超时（如TCP的超时重传）。

2.2. 同步与异步网络

同步网络：网络端到端最大延迟固定，即有界延迟。

异步网络：网络端到端最大延迟可无限大。

3. 不可靠的时钟

节点自己的时钟设备不准确（即存在时钟偏移核时钟漂移，见此）。当然一定程度上可以同步节点间的时钟（如使用NTP协议），但是有很多限制。

3.1. 单调时钟与墙上时钟

3.1.1. 墙上时钟

根据某个日历返回当前的日期与时间（如clock_gettime(CLOCK_REALTIME)和System.currentTimeMillis()），且可以和NTP同步。

但是NTP同步的强制跳转不太适合测量时间间隔。此外墙上时钟的精度可能有问题。

3.1.2. 单调时钟

适合测量持续时间段（如clock_gettime(CLOCK_MONOTONIC)和System.nanoTime()），但单纯的值没有意义。它保证值不会被回拨，且精度更高。

若节点拥有多CPU，每个CPU可能有单独的时钟，OS会补偿它们的偏差，但是对该补偿应持谨慎态度。

墙上时钟和单调时钟都是物理时钟，而后面的递增计数器则是逻辑时钟

3.2. 依赖同步的时钟

节点的时钟也会有故障（如出现漂移）。若应用需要精确同步的时钟，需要监控集群中所有节点的时钟偏差，并移除漂移超出上限的节点。

3.2.1. 时间戳与事件顺序

分布式多节点场景下，不能依照（它们之间的）物理时钟（包括墙上和单调）来确定事件的先后性（即使使用NTP同步）。

因此，排序而言，基于递增的计数器（逻辑时钟，后面几章会讲，之前的文章也有提及）更加可靠，它测量的是事件的相对顺序。

3.2.2. 时钟的置信区间

应该视时钟的读数为带有置信区间的时间范围（置信区间见数理统计定义），虽然调用clock_gettime()等函数只返回一个时间值。

Google TrueTime API可报告本地时钟的置信区间

3.2.3. 全局快照的同步时钟

对于如分布式数据库场景，创建所有节点上全局递增的事务ID往往会引入瓶颈。

Twitter的Snowflake服务将ID空间划分为不同范围：

41位时间序列（精确到毫秒）

10位机器标识（可部署最多1024个节点）

12位计数序列（每节点每毫秒可产生4096个ID）

它可以生成全局的、近似单调递增的唯一ID，但有时无法保证与因果关系一致的顺序（因为强依赖物理时钟，受到偏移、回拨的影响），详细可见下一章。

Google Spanner使用下面思路：

根据TrueTime API返回时间置信区间；
生成的2个置信区间$A = [A_{early}, A_{late}]$, $B = [B_{early}, B_{late}]$比较，只有区间不重叠的时候，才能断定先后顺序，否则顺序不明确。

Google Spanner在提交读写事务前，会故意等待置信区间的程度，以确保读事务足够晚发生（即产生重叠）。且为了缩短等待时间，时钟误差范围要尽可能小，因此还部署了GPS接收器或原子钟。

3.3. 进程暂停

租约：可由授权者随心跳下发，也可以自己申请抢占（即一种分布式锁的实现），决定该节点在某个时间段可用。

分布式系统中，必须假定一个节点可能在任何时刻被暂停很长时间，若使用时钟，则需要小心。

3.3.1. 响应时间保证

需要多方面支持：

操作系统需要实时操作系统（RTOS）
库函数需要考虑最坏执行时间
动态内存分配需要限制/禁止
GC不能处理太多任务
需要大量充分的测试

但是开销大，所以实际设计软件时要考虑进程暂停、时钟不稳定的问题。

3.3.2. 调整GC

实际方法：控制GC任务

新的想法：GC暂停时临时下线，通知客户端路由请求到其它节点；或者当短期对象变成长期对象（如eden -> survivor -> old 时）定期重启。

4. 真相与谎言

4.1. 多数决定

节点不能根据自己的信息判断自身的状态（如是否失效），而需要由集群多数节点的“投票”决定。

4.1.1. 主节点与锁

当集群中只能存在一个主节点的时候，需要其它的多数节点（即法定票数），即使自己认为是自己是唯一的主节点。

如“错误的租约”，HBase中文件只能由一个客户端访问：

c1申请租约lease_1，申请到后由于GC暂停到租约结束
c2在lease_1过期后成功申请到租约而成功操作
c1恢复后未检查而修改数据，造成崩溃

代码如下

public void modifyData(Data data) {
    // ...
    if(willExpired(lease)) {
        lease = renew(lease);
    }
    
    if(lease.isValid()) { //GC paused the whole process
        // operation ...
    }
}

4.1.2. Fencing令牌

使用锁和租约保护并发访问时，需要确保过期的“唯一”节点（如4.1.1.所述）不能影响其它的正常访问，这可用Fencing令牌实现。

实现：

申请锁的时候，附带一个单调递增的ID（即Fencing令牌，由锁服务提供）
对服务端操作时，服务端需要检查ID，若传来的ID比之前请求的最大ID小，则拒绝请求

使用ZooKeeper提供锁服务时，可用事务标识zxid或节点版本cversion充当令牌，算法如下：

客户端连接zk，并在/lock下创建临时的且有序的子节点（使用上述令牌），第一个客户端对应的子节点为/lock/lock-0000000000，第二个为/lock/lock-0000000001，以此类推。

客户端获取/lock下的子节点列表，判断自己创建的子节点是否为当前子节点列表中序号最小的子节点，如果是则认为获得锁，否则监听/lock的子节点变更消息，获得子节点变更通知后重复此步骤直至获得锁；

执行业务代码；

完成业务流程后，删除对应的子节点释放锁。

4.2. 拜占庭故障

拜占庭故障：系统中的节点可能出错而发送错误的信息，或通讯网络导致信息的损坏，使得集群中不同节点作出错误的决策。（如节点没收到消息，却对外宣称收到了）

解决拜占庭容错的系统协议很复杂（如PBFT、DBFT、POW、POS），且很可能需要硬件支持，因此绝大部分场景，部署拜占庭容错的解决方案不可行。

4.2.1. 防范“弱的谎言”

若TCP/UDP以及下层的协议出现损坏/逃过校验，可在应用层增加校验
所有公共开放的输入必须校验
…

4.3. 理论系统模型与现实

计时系统模型：

同步模型：网络延迟有上界
部分同步模型：大多数像同步模型，但有时会超出预期上界
异步模型：网络延迟没有上界，（算法）不对时机作任何假设，甚至里面没有时钟（也没有超时机制）

节点失效系统模型：

崩溃-中止模型：算法只假设节点只以崩溃中止的形式发生故障，即节点可能任何时候停止响应且永远消失
崩溃-恢复模型：节点可能任何时候停止响应，但会在一段未知时间内恢复，节点上的持久性存储不会丢失，但内存中的状态可能丢失
拜占庭（任意）模型：节点可能发生任何事情，包括欺骗其它节点

最普遍的建模往往是：部分同步 + 崩溃-恢复。

4.3.1. 算法的正确性

通过描述分布式算法的相关属性来定义其正确性。如Fencing令牌，保证令牌唯一、令牌单调递增以及可用性（请求令牌的节点若不崩溃一定收到响应）

4.3.2. 安全性和活性

安全性：可理解为“没发生意外”。

活性：可理解为“预期的事情最终一定发生”。

数学形式化定义：Defining Liveness

通常，分布式算法要求所有可能的系统模型下，符合安全性（即使所有节点崩溃，确保不会返回错误结果）；对于活性，则需要存在一些必要条件和前提。

安全性、活性以及系统模型对于评测分布式算法的正确性很重要。但这些抽象往往是简化，现实中更加复杂，即证明出算法正确并不代表现实的具体实现一定正确。

DDIA-分布式中的故障