分布式系统与算法
分布式系统面对的挑战
网络故障
超时、重发冗余包、延迟到达...
节点故障
崩溃后终止
崩溃后重启（利用持久化存储中的数据恢复节点的状态）
拜占庭式错误
节点存在恶意行为，例如，一个运行 Raft 协议的节点故意将自己的 term 设为很大以取代现任领导者。不过，大多数分布式系统不必考虑这类错误，因为成本昂贵。且服务器多是运行在受控条件下的，除了软件 bug，不太可能引入恶意行为。在那些去中心化的系统中，比如区块链，就要考虑拜占庭式的错误。
很多事情都会出错
- TCP/UDP 的校验和可能出错
- 不要太信任时钟
- GC 可能随时发生
- 线程可能被随时剥离 CPU
一致性
在分布式系统中，一致性是指数据在多个副本之间能够达到一致的状态。一致性有不同的级别，越强的一致性将带来越大的延迟和越复杂的系统。
线性一致性（强一致性）：要求系统中的所有操作看起来都是顺序发生的。这意味着一旦数据更新成功，所有后续的访问都将返回新的值。
最终一致性：一种较弱的一致性模型，它只保证如果没有新的更新，则最终所有数据副本都将是一致的。系统不保证达到一致状态的时间。
如何解决复制滞后？（在主从复制模型中进行讨论，即写请求只能发往主节点，而读请求可以发往从节点）
读自己的写
在客户端向主节点写入数据后，至少需要保证同一个客户端随后进行读时，可以读到最新的值，这称作「read-after-write」一致性。例如，可以考虑这次读请求距离最近一次写请求的时间间隔，如果时间间隔较长，可以认为大多数从节点已经进行了更新，此时可以请求从节点；否则，还是请求主节点，因为主节点一定包含了上次被写入的最新结果。
单调读
假设一个客户端从不同从节点进行了多次读取，但是这些不同的从节点的数据同步程度可能不一致。如若第一次读请求被路由到一个较新的从节点，用户可能会看到某个用户的最新评论；但是，第二次读请求被路由到一个旧的从节点，此时，上次读到的那条评论就消失了，用户就会感到很奇怪。避免这种现象的一致性被称为「单调读」一致性，这是一种比最终一致性强，又比线性一致性弱的保证。例如，避免同一个客户端的读请求被路由到不同的从节点。
前缀一致读
在分区的数据库中，可能出现这样的情形。写入 A 先于写入 B 发生，因此具有因果关系。不过，由于分区的机制，写入 A 必须写入分区 1，写入 B 必须写入分区 2。不过，由于分区 1 的写入滞后了，导致外部观察者观察到 B 先于 A 发生，这就违反了逻辑。避免出现这种情形则称为「前缀一致读」。这种解决方法比较复杂，例如可以通过将具有因果顺序的操作交给一个分区完成。
因果一致性：在因果一致性模型中，如果一个操作在因果上先于另一个操作，则这种关系在系统中的所有副本上都必须被保留。
会话一致性：在一个客户端与系统交互的会话期间，客户端对数据的更新能被连续的查询操作观察到，而且更新后的数据在该会话中保持一致。换句话说，一个客户端在会话中所做的更改对于同一会话中的后续操作是可见的，但对于其他客户端的会话可能不是立即可见的。
一个十分简单却低效的会话一致性的实现方案是，来自同一个客户端的请求总是被同一个服务器处理。不过这也失去了「分布式」系统的意义
CAP 定理
CAP 定理表明，在面对网络分区（即系统的一部分节点由于网络问题无法与其他节点通信）的情况下，一个分布式系统不可能同时满足以下三个属性：
一致性（Consistency）：每次读取都能获得最新的写入数据，即系统的所有节点看到的数据是一致的。
这里的一致性指的是强一致性（线性一致性）
可用性（Availability）：每个请求都能获得关于其操作是否成功的响应，不论个别节点的失败。
分区容错性（Partition Tolerance）：系统能够持续运作，即使出现了网络分区的情况。
在一个出现分区的系统中，一致性与可用性是不可兼得的。选择一致性，那么一些节点将会无法处理请求，则牺牲了可用性；选择可用性，那么一些节点的状态可能不是最新的，此时则破坏了强一致性，只能满足最终一致性
事件
并发：超越单机
在单机中，并发指的是多个进程在一个时间段来看是同时运行，是通过时间片分用来实现的。
因此在单机中，通常如果两个事件「同时」发生，则称之为并发。不过，在分布式系统中，事件是否在时间上重叠并不重要，并且由于分布式系统中复杂的时钟同步问题，有时往往难以确定它们是否同时发生。
在分布式系统中，如果两个事件之间没有因果依赖，即不需要意识到对方，就可以称这两个事件是并发的。换言之，我们对这两个事件的先后顺序不可做出任何断言。
作为参考，一个典型的具有因果依赖的事件序列是，对于数据库中原本不存在的某个行，必须先 insert 才能 update，这两个事件就不是并发操作。
逻辑时钟
可以理解为事件的序号。例如一个简单的拒绝冗余请求的算法是，维护一个上次处理的请求的序号的 last_id，拒绝那些序号小于这个值的请求。一个著名的逻辑时钟是 Lamport timestamp 算法。
分布式系统中的偏序与全序
- 偏序：如果系统中的某些事件存在先后关系(happen before)，那么就称为偏序关系。
- 全序：如果系统中的事件两两间存在先后关系，那么就称为全序关系。这样我们可以确定这些事件在不同节点上的执行顺序都是一致的，从而取得一致性，例如 Raft 协议中的 log entry 之间就是全序关系。
2PC
注意这不是数据库系统中的「两阶段锁，2PL」。两阶段锁协议将事务的锁操作分为两个阶段：
- 扩展阶段：事务可以获取任何它需要的锁（包括读锁和写锁），但不能释放任何锁。
- 收缩阶段：在收缩阶段，事务可以释放已持有的锁，但不能再获取任何新的锁。
Two-Phase Commit 用于保证在分布式系统中多个节点提交事务时要么全部成功，要么全部失败，从而保证一致性。
2PC 协议由协调者（coordinator）和多个参与者（participants）组成。它分为两个阶段：准备阶段（prepare phase）和提交阶段（commit phase）。
准备阶段：
协调者向所有参与者发送「准备提交」的请求，询问它们是否可以准备好提交事务。
每个参与者在接收到准备请求后，执行事务操作但不提交。如果参与者准备就绪，则记录事务日志并锁定相关资源，然后向协调者发送「准备就绪」。如果不能准备好，则发送「中止」消息。
提交阶段：
协调者根据从所有参与者收到的响应来决定事务的最终状态。如果所有参与者都发送「准备就绪」消息，则协调者向所有参与者发送「提交」消息。如果有任何参与者发送「中止」消息，或者超时未收到某个参与者的响应，则协调者向所有参与者发送「中止」消息。
参与者在接收到协调者的「提交」或「中止」消息后，执行相应的操作（提交事务或回滚事务），并释放锁定的资源。然后向协调者发送确认消息。
不过协调者会带来单点故障的可能性；另外参与者频繁的阻塞操作也会带来性能问题。
与 Raft 相比，2PC 牺牲一定的可用性换来强一致性；Raft 牺牲强一致性换来更好的可用性。
2PC：侧重于分布式事务的原子性和一致性，但在协调者故障或网络分区时可能面临阻塞问题。
Raft：侧重于分布式系统中的日志一致性和高可用性，通过领导者选举和日志复制机制，提供可靠的一致性和快速的故障恢复能力。
Quorum
设有