分布式理论

AKF

AKF是指”AKF扩展立方体”(AKF Scaling Cube),这是一个由Arnold Karr和Martin Abbott提出的分布式系统扩展模型。这个模型提供了三个维度来思考如何扩展系统:

1. X轴 - 水平复制:
   这涉及到简单地复制整个应用或服务。每个复制品都能处理任何请求。这通常通过负载均衡器实现。
2. Y轴 - 功能解耦:
   这涉及到将不同的功能或服务分离开来。例如,可以将认证服务、支付服务和商品目录服务分开。
3. Z轴 - 数据分区:
   这涉及到基于某些标准(如用户ID、地理位置等)将数据分成不同的部分。每个服务器负责一部分数据。

AKF立方体提供了一个全面的框架,帮助架构师和开发者思考如何最有效地扩展他们的系统。每个轴代表了一种不同的扩展策略,而这些策略可以单独使用或组合使用。

CAP定理

CAP定理是分布式系统设计中的一个基本概念。它指出在一个分布式系统中，一致性（Consistency）、可用性（Availability）和分区容错性（Partition tolerance）这三个属性无法同时完全满足。让我详细解释一下这三个属性以及它们之间的权衡：

1. 一致性（Consistency）：
   所有节点在同一时间具有相同的数据。当向系统写入数据后，任何时刻任何客户端都能读取到最新的数据。

2. 可用性（Availability）：
   系统保证每个请求都能得到响应，而不保证返回的是最新数据。即使部分节点故障，系统仍能继续运行。

3. 分区容错性（Partition tolerance）：
   系统在网络分区的情况下仍能继续运行。即使节点之间的网络连接中断，系统仍能继续处理请求。

CAP定理指出，在分布式系统中，这三个属性最多只能同时满足两个。这就导致了三种可能的组合：

1. CA（一致性 + 可用性）：
   适用于传统的单点关系数据库系统。但在分布式环境下，无法保证分区容错性。

2. CP（一致性 + 分区容错性）：
   在分区发生时，系统会牺牲可用性来保证数据一致性。例如，某些分布式数据库如HBase。

3. AP（可用性 + 分区容错性）：
   在分区发生时，系统会继续提供服务，但可能返回旧数据。例如，某些NoSQL数据库如Cassandra。

在分布式系统中，分区容忍性（Partition Tolerance）通常被认为是天然满足的。这是因为：

1. 网络故障不可避免：在分布式系统中，网络分区可能由于硬件故障、网络拥堵、路由问题等原因发生。因此，系统必须能够处理这些不可预见的分区情况。

2. 设计考虑：大多数分布式系统在设计时就考虑了网络分区的可能性，采用了如复制、冗余和一致性协议等技术，以确保即使在网络分区的情况下，系统仍然能够继续运行。

3. CAP 定理的前提：CAP 定理本身就假设网络分区是不可避免的，因此在选择一致性和可用性之间的权衡时，分区容忍性是必须考虑的基础。

在实际应用中，CAP的选择往往取决于具体的业务需求：

• 对于银行交易这样的场景，可能会选择CP，因为数据一致性至关重要。
• 对于社交媒体这样的应用，可能会选择AP，因为可用性更为重要，用户可以容忍短暂的数据不一致。

需要注意的是，CAP定理描述的是极端情况下的取舍。在实际系统设计中，我们通常会寻求这三个属性之间的平衡，而不是完全放弃其中之一。

所以我们常说只能同时满足两个，而不能兼顾三个。

共识（Consensus）算法-Paxos（读/ˈpæk.sɒs/，帕克-索斯）

Paxos算法是莱斯利·兰伯特（Leslie Lamport，LaTeX中的“La”）于1990年提出的一种基于消息传递且具有高度容错特性的共识（consensus）算法，他因在分布式系统中的贡献获颁2013年的图灵奖、2014被选为ACM Fellow。
需要注意的是，Paxos常被误称为“一致性算法”。但是“一致性（consistency）”和“共识（consensus）”并不是同一个概念。Paxos是一个共识（consensus）算法，但常用于解决分布式系统中的一致性问题。

Paxos算法本身其实并不复杂[虽然网上很多人认为其晦涩难懂]，算法难以理解的地方在于在设计这套算法的来龙去脉和其正确性的论证过程。换句话说，这套算法的流程不难理解，这套算法怎么设计出来的以及为什么这么好用的原因才是最难理解的。

这里插一句关于Paxos的念法，Paxos[Greek: Παξοί, pronounced Paksi in English]又名Paxi是希腊西南部一个风景如画的小岛。Paxos算法作者Lamport关于命名问题，这样解释道:I thought, and still think, that Paxos is an important algorithm. Inspired by my success at popularizing the consensus problem by describing it with Byzantine generals, I decided to cast the algorithm in terms of a parliament on an ancient Greek island. Leo Guibas suggested the name Paxos for the island.

由来

为描述Paxos算法，Lamport虚拟了一个叫做Paxos的希腊城邦，这个岛按照议会民主制的政治模式制订法律，但是没有人愿意将自己的全部时间和精力放在这种事情上。所以无论是议员，议长或者传递纸条的服务员都不能承诺别人需要时一定会出现，也无法承诺批准决议或者传递消息的时间。但是这里假设没有拜占庭将军问题[Byzantine failure，即虽然有可能一个消息被传递了两次，但是绝对不会出现错误的消息]；只要等待足够的时间，消息就会被传到。另外，Paxos岛上的议员是不会反对其他议员提出的决议的。

先用Lamport说的这个例子解释Paxos算法流程，同时维基百科也是用这个例子：

有A1, A2, A3, A4, A5 5位议员，就税率问题进行决议，采用少数服从多数的机制，而且每个议员会直接同意他第一个收到的草案。每两位议员会有一个专门的信使负责彼此传递消息。议员A1决定将税率定为10%,因此它向所有人发出一个草案。这个草案的内容是：

现有的税率是什么？如果没有决定，则建议将其定为10%。时间：本届议会第3年3月15日；提案者：A1。

然后由专门负责传递给 A2, A3, A4, A5 4位议员消息的信使传给他们。最理想的情况是，所有信使安全抵达，然后4为议员批准了这项议题，然后信息回到A1。

我已收到你的提案，没有异议，并等待最终批准。

当A1议员等到其中两个信使到达的时候，他就收到了2份同意书，算上自己超过半数，那么他就会公开宣布，并由信使传达给各位议员：

税率已定为10%，新的提案不得再讨论本问题。

在上述情况，全体议员都同意这个草案，其实这就是我们之前文章介绍的2PC（二阶段提交）机制。A1为coordinator，A2-A5为cohort。所不同者，在于A1之后到了两份同意书达到多数后就宣布确定消息，而在2PC中，必须所有人都同意才可以（当然这个不是这么简单，但是在确定机制上是有这样的分别）。

现在在同一天的时间里，A5议员也提出一个草案：

现有的税率是什么？如果没有决定，则建议将其定为20%。时间：本届议会第3年3月15日；提案者：A5。

现在A1和A5同一天内发送了草案，并由各自的信使送达其他议员。A1的草案将由4位信使送到A2-A5那里。现在，负责A2和A3的信使将草案顺利送达，负责A4和A5的信使则不上班。A5的草案则顺利的送至A3和A4手中。现在, A1, A2, A3收到了A1的提案; A3, A4, A5收到了A5的提案。按照协议, A1, A2, A4, A5将接受他们收到的提案，信使将拿着同意书各自回到A1和A5。此时A1和A5手中各有2份同意书，而A3拥有决定性的一票。

这里例子又分了三种情况，

情况一

A1的信使到达A3，A3同意A1的议案，而A5的信使正好在返程当天到了轮休的日子，所以A1获得绝对多数后，让信使告诉议员，

税率已定为10%，新的提案不得再讨论本问题。

而过了好久A3又收到了A5的信使，但是之前的草案已经获得通过。所以A5得提议被否决，信使会带着A3的回复，回到A5。

税率已在之前的投票中定为10%，不得发起类似草案。

更有可能的是A5已经知道了之前的草案，因为A1和A5之间的信使已经传递了此项消息，只不过A3和A5之间的信使当时在放假。当然如果A1和A5之间的信使放了更长时间的假，那么这个回复就会重要一些，因为A5议员已经失联很久了。

情况二

依然假设A1的提案先送到A3处，但是这次A5的信使不是放假了，只是中途耽搁了一会。这次, A3依然会将”接受”回复给A1。但是在决议公开发布之前它又收到了A5的提案。这时协议有两种处理方式：

如果A5是个大人物

按照传统应该由谁先到谁获得同意回复，现在看来两份提案的时间一样（本届议会第3年3月15日）。只不过他已经回复了A1，但是A5是个惹不起的大人物。于是A3回复：

我已收到您的提案，等待最终批准，但是您之前有人提出将税率定为10%，请明察。

于是, A1和A5都收到了足够的回复。这时关于税率问题就有两个提案在同时进行。但是A5知道之前有人提出税率为10%。根据协议先到先得的策略，于是A1和A5都会向全体议员广播：

税率已定为10%，新的提案不得再讨论本问题。

A5是个无足轻重的小人物

这时A3不再理会他, A1不久后就会广播税率定为10%。

情况三

在这个情况中，我们将看见，根据提案的时间及提案者的权势[*在分布系统中，是节点的重要性，优先级*]决定是否应答是有意义的。在这里，时间和提案者的权势就构成了给提案编号的依据。

这样的编号符合”任何两个提案之间构成偏序”的要求。

A1和A5同样提出上述提案，这时A1可以正常联系A2和A3; A5也可以正常联系这两个人。

这次A2先收到A1的提案; A3则先收到A5的提案。A5更有权势。在这种情况下，已经回答A1的A2发现有比A1更有权势的A5提出了税率20%的新提案，于是回复A5说：

我已收到您的提案，等待最终批准。

而回复了A5的A3发现新的提案者A1是个小人物，不予理会。 A1没有达到多数，A5达到了，于是A5将主持投票，决议的内容是A5提出的税率20%。

如果A3决定平等地对待每一位议员，对A1做出”你之前有人提出将税率定为20%”的回复，则将造成混乱。这种情况下A1和A5都将试图主持投票并群发消息，但是这次两份提案的内容不同。

这种情况下, A3若对A1进行回复，只能说：

有更大的人物关注此事，请等待他做出决定。

另外，在这种情况下, A4与外界失去了联系。等到他恢复联系，并需要得知税率情况时，他（在最简单的协议中）将提出一个提案：

现有的税率是什么？如果没有决定，则建议将其定为15%。时间：本届议会第3年4月1日；提案者：A4

这时，（在最简单的协议中）其他议员将会回复：

税率已在之前的投票中定为20%，不得再提出此项草案!

此例子描述了大部分Paxos的流程。后续会介绍整个算法流程。

Paxos算法是一种用于在分布式系统中实现一致性的方法，通常用于确保多个节点在面对网络分区或故障时仍然能够达成一致。Paxos最主要的贡献是解决了在不可靠通信和可能失效的节点中达成共识的问题。

Paxos算法的基本概念

Paxos算法由三种角色组成：

1. 提议者（Proposer）：提出提议（Proposal）。
2. 接受者（Acceptor）：投票决定是否接受一个提议。
3. 学习者（Learner）：学习最终被选定的提议。

Paxos的基本流程

Paxos可以分为两个主要阶段：准备阶段（Prepare Phase）和接受阶段（Accept Phase）。

准备阶段

1. 提议者选择提议编号 n，并向一组接受者发送准备请求（Prepare Request）。
2. 接受者收到准备请求后，如果 n 大于其已经响应过的所有编号，则承诺不再接受编号小于 n 的提议，并回复其最后接受的提议（如果有）及其编号。

接受阶段

1. 提议者收到足够数量的承诺回复后，可以发出一个带有编号 n 的提议请求（Propose Request），提议内容可以是接受者回复中编号最高的已接受提议的值，或者是一个新值（如果没有已接受的提议）。
2. 接受者收到提议请求后，如果尚未对编号大于或等于 n 的准备请求作出承诺，则接受该提议。

决策达成

一旦某个提议被多数接受者接受，那么这个提议就是被选定的提议。学习者可以通过接受者的消息得知最终选定的提议。

Paxos的特性保证了一致性

• 安全性：即使在网络分区或节点失效的情况下，Paxos仍能确保不会出现冲突的决策，只有一个值会被选定。
• 活性：在某些条件下，Paxos可能会陷入无法达成决定的状态（如不断有新的提议者尝试提出新的提议），但在实际应用中，通常通过引入超时和领导者选举等机制来解决。故如果多数Acceptors活着，最终会选定一个值。

活锁问题

Paxos可能出现活锁，即多个Proposers不断提出更高编号的提案，导致没有值被选定。解决方法包括:

• 选举一个主Proposer。
• 引入随机延迟。

优化与变体

Paxos算法有许多变种和优化版本，如：

• Multi-Paxos：用于处理多个提议的情况，减少协议开销。
• Fast Paxos：通过减少消息延迟来提高效率。
• EPaxos：优化了不同数据中心之间的性能。

实际应用

Paxos在许多分布式系统中得到应用，如：

• Google的Chubby分布式锁服务
• Apache ZooKeeper（使用了Paxos的变体）

共识（Consensus）算法-Raft

Raft是一种用于替代Paxos的共识算法。相比于Paxos，Raft的目标是提供更清晰的逻辑分工使得算法本身能被更好地理解，同时它安全性更高，并能提供一些额外的特性。Raft能为在计算机集群之间部署有限状态机提供一种通用方法，并确保集群内的任意节点在某种状态转换上保持一致。Raft这一名字来源于”Reliable, Replicated, Redundant, And Fault-Tolerant”（“可靠、可复制、可冗余、可容错”）的首字母缩写。

概念

角色

Raft将服务器节点分为三种角色：

• Leader（领导者）：只有一个，处理所有客户端请求，管理日志复制。
• Follower（跟随者）：被动响应来自Leader和Candidate的请求。
• Candidate（候选人）：用于选举新的Leader。

任期（Term）

Raft将时间划分为任意长度的任期（Term）。每个任期都有一个单调递增的整数标识。每个任期开始于一次选举。

流程

通常领袖会借由固定时间发送消息，也就是“心跳（heartbeat），让追随者知道集群的领袖还在运作。而每个追随者都会设计超时机制（timeout），当超过一定时间没有收到心跳（通常是150 ms或300 ms），集群就会进入选举状态。

Raft将问题拆成数个子问题分开解决，让人更容易了解：

• 领袖选举（Leader Election）
• 记录复写（Log Replication）
• 安全性（Safety）

Leader选举

1. 所有节点初始化为Follower。
2. 如果Follower在一定时间内没有收到Leader的心跳，它会变成Candidate并开始一次选举。
3. Candidate增加当前任期号，给自己投票，并并行地向其他节点发送请求投票的 RPC。
4. 其他节点根据以下规则响应投票请求：
   • 如果任期号小于自己的当前任期，则拒绝投票。
   • 如果没有投票给其他候选人，则投票给该候选人。
5. 候选人在以下情况下赢得选举：
   • 获得多数票。
   • 没有其他候选人在相同任期内赢得选举。

在起始算法或领袖死机、断线的时候，就需要选举出新的领袖。

Raft每个服务器的超时期限是随机的，这降低伺服务同时竞选的几率，也降低因两个竞选人得票都不过半而选举失败的几率。

日志复制

1. 客户端发送命令到Leader。
2. Leader将命令追加到自己记录中的新指令部分。
3. Leader并行发送AppendEntries RPC给Followers。
4. Leader收到过半Followers确认写入的消息，就会把指令视为已存储（committed）。Leader应用该命令到状态机并返回结果给客户端。
5. 当Followers发现指令状态变成已存储，就会在其状态机上执行该指令。
6. 如果Followers崩溃或运行缓慢，Leader会不断重试AppendEntries RPC。

当领袖死机时，领袖的某些新指令可能还没复写到集群整体，造成集群的记录处于不一致的状态。新领袖会担起重返一致的责任，让每个追随者的记录都和它的一致，做法是：和每个追随者比对记录，找出两者一致的最后一笔指令，删除追随者之后的指令，把自己之后的指令拷贝给追随者。这个机制完成时，每个服务器的记录就会一致。

安全性

• Raft的安全性规则

Raft保证以下的安全性：

• 选举安全性：每个任期最多只能选出一个领袖。
• 领袖附加性：领袖只会把新指令附加（英语：append）在记录尾端，不会改写或删除已有指令。
• 记录符合性：如果某个指令在两个记录中的任期和指令序号一样，则保证序号较小的指令也完全一样。
• 领袖完整性：如果某个指令在某个任期中存储成功，则保证存在于领袖该任期之后的记录中。
• 状态机安全性：如果某服务器在其状态机上执行了某个指令，其他服务器保证不会在同个状态上执行不同的指令。

前四项保证的原因详见上述算法，状态机安全性则借由下述选举流程的限制所达到。

• 追随者死机

当某台追随者死机时，所有给它的转发指令和拉票的消息都会因没有回应而失败，此时发送端会持续重送。当这台追随者开机重新加入集群，就会收到这些消息，追随者会重新回应，如果转发的指令已经写入，不会重复写入。

• 领袖死机

领袖死机或断线时，每个已存储指令必定已经写入到过半的服务器中，此时选举流程会让记录最完整的服务器胜选。其中一个因素是Raft候选人拉票时会揭露自己记录最新一笔的信息，如果服务器自己的记录比较新，就不会投票给候选人。

• 超时期限和可用性

  因为Raft启动选举是基于超时，使得超时期限的选择至为关键。若遵守算法的时限需求

  广播时间 << 超时期限 << 平均故障间隔

  就能达到稳定性。这三个时间定义如下：

  • 广播时间 是单一服务器发送消息给集群中每台服务器并得到回应的平均时间，需要测量得到。
  • 超时期限 是发动选举的超时期限，由部署Raft集群的人选定。
  • 平均故障间隔 是服务器发生故障之间的平均时间，可以测量或估计得到。

  广播时间典型是 0.5ms 到 20ms，平均故障间隔通常是用周或月来计算的，所以可以将超时期限设在 10ms 到 500ms。