# 分布式系统和集中式系统对比
在讲分布式系统之前，得了解一下什么是集中式系统，才知道为什么会有分布式系统的出现。
集中式系统多采用Client-Server架构，该架构采用单个功能强大的服务器构建。连接到中央服务器的功能较弱的客户端节点可以将其处理请求提交到服务端，而不是直接在本地执行它们。
它的优点是：
- 由于采用客户端-服务器架构，易于设置并可快速开发
- 整个系统可以通过中央服务器进行管理和监控
- 由于只需要更新一台机器，因此可以更高效地更新系统
- 很容易对服务器进行物理保护和维护
- 客户端节点可以轻松删除和添加，而不影响整个系统
它的缺点是：
- 中央服务器出现问题可能会导致系统完全崩溃。因此，存在单点故障
- 整个系统的可用性取决于中央服务器，因此系统的更新必须即时完成。这导致服务器维护困难
- 维护备份的可能性较小。如果中央服务器出现故障并且没有备份，所有数据都将被删除
正是由于上述集中式系统的缺点，所以才会有分布式系统的出现。
分布式系统采用的是点对点架构，即P2P，它是一个网络互连的独立计算机的集合。分布式系统中的每个节点都拥有足够的计算能力来协作完成任务。在分布式系统中，用户对数据具有平等的访问权限。单个节点的故障不会影响整个系统，从而提高可用性和可靠性。
下面是两个系统的一个对比：
| 特征 | 集中式系统 | 分布式系统 |
|---|---|---|
| 网络拓扑 |  |  |
| 可扩展性 | 受到中央服务器容量的限制。 | 高度可扩展；可以通过添加更多节点进行扩展。 |
| 容错 | 容易出现单点故障；如果中央服务器发生故障，系统就会崩溃。 | 具有故障恢复能力；如果一个节点发生故障，其他节点可以接管其职责。 |
| 表现 | 由于所有请求都经过中央服务器，因此在高负载下可能会成为瓶颈。 | 由于工作负载分布在多个节点上，因此在高负载下提供更好的性能。 |
| 灵活性 | 由于所有组件紧密耦合且依赖于中央服务器，因此更改的灵活性较差。 | 由于组件松散耦合，可以独立修改或替换，甚至部署在不同的操作系统上，因此更加灵活、适应性更强。 |
| 成本 | 由于升级中央服务器需要大量投资，因此扩展成本可能很高。 | 由于涉及添加商品硬件或虚拟机，因此扩展更具成本效益。 |
| 部署 | 轻松快速地部署 | 整个系统很复杂 |
| 测试 | 需要端到端测试，难以实现全面覆盖 | 个别组件测试 |
| 开发/工程速度 | 分配工作更加困难，通常由于数据库太大而无法分割而受到限制 | 团队可以独立开展各种服务 |
# CAP理论
CAP理论，也称为Brewer's定理，是由计算机科学家Eric Brewer于2000年提出的理论，它关注分布式系统中一致性（Consistency）、可用性（Availability）、分区容忍性（Partition Tolerance）这三个属性之间的权衡关系。
具体来说，CAP理论指出在一个分布式系统中，这三个属性不可能同时得到满足，最多只能同时满足其中的两个。以下是CAP理论的三个属性的简要解释：
一致性（Consistency）：所有节点在同一时间具有相同的数据。在一致性的系统中，任何对系统的更新操作都将立即反映在所有节点上，使得所有节点保持一致的数据状态。这可确保用户始终观察到一致的数据。
在分布式系统中实现强一致性可能具有挑战性，尤其是在存在网络延迟、故障或高延迟的情况下。协调节点之间的数据同步以保持一致性通常会带来额外的复杂性和性能开销。
可用性（Availability）：即使出现故障或网络分区，对系统发出的每个请求都会得到响应。即使个别节点或组件出现故障，可用的系统仍能响应用户请求并继续运行。
确保高可用性通常涉及冗余和容错机制，例如复制、负载平衡和故障转移策略。这些机制允许系统通过将请求重定向到健康节点或使用数据的备份副本来继续运行，相反这就会增加更多的成本。
分区容忍性（Partition Tolerance）：分布式系统在出现网络分区或通信故障时仍能继续运。当分布式系统中的节点由于网络问题或其他因素而无法相互通信时，就会发生网络分区。这可能导致消息丢失、延迟或节点彼此隔离。
由于无法保证完全的网络可靠性，因此分区容错性是分布式系统中的基本要求，即P是必须的。有了分区容错性，即使某些节点无法相互通信，分布式系统也可以继续运行并提供服务。
根据CAP理论，一个分布式系统只能在一致性、可用性和分区容忍性中选择两个，无法同时满足所有三个。这种权衡关系对于设计和理解分布式系统非常重要，因为在实际应用中需要根据具体的需求和场景来选择适当的系统设计方案。
如果发生网络分区 (P)，分布式系统必须在一致性 (C) 和可用性 (A) 之间做出选择。换句话说，在存在网络分区的情况下，不可能同时实现一致性和可用性。
# CA系统
CA 系统旨在同时实现一致性和可用性，但它们牺牲了分区容忍度。换句话说，它们优先维护数据的一致，并在没有网络分区的情况下响应用户请求。
CA 系统通常部署在网络可靠性高、网络分区可能性低的环境中。它们非常适合数据一致性和高可用性至关重要的应用程序，例如传统的单站点数据库。
# AP系统
AP 系统优先考虑可用性和分区容忍度，弱化一致性。这些系统选择保持可用性，即使在网络分区期间也能响应用户请求，接受不同节点可能具有暂时不一致的数据。
AP 系统通常用于高可用性至关重要的场景，例如实时协作应用程序或内容交付网络 (CDN)。它们优先提供响应式服务，即使这意味着接受最终一致性并允许跨节点的暂时不一致，这种是目前大多数分布式系统的选择。
这里提一下，最终一致性是分布式系统中实现可用性和一致性之间平衡的一种常用方法。最终一致性不会强制所有节点立即保持一致，而是允许出现暂时的不一致，并最终随着时间的推移收敛到一致状态。这种方法可实现高可用性和响应能力，同时仍提供最终的数据收敛，例如HDFS、Elasticsearch、Kafka等系统。
# CP系统
CP 系统优先考虑一致性和分区容忍度，弱化可用性。在这些系统中，当发生网络分区时，它们会选择保持强一致性，即使这意味着暂时牺牲可用性。这意味着在分区期间，系统更新可能会被阻止，直到实现一致性或解决分区问题。
CP 系统通常用于数据一致性至关重要的场景，例如金融系统或需要严格同步的系统。它们愿意在网络分区期间牺牲可用性，以确保所有节点都具有相同的一致数据。
# Paxos一致性算法
前面我们说了，CAP理论只能三选二，在现实中，大部份系统会选择弱化一致性，即选择AP系统，选择最终一致性。所以，这里一致性算法就发挥了重要的作用，其中Paxos更是分布式系统的奠基石。
Paxos是一种经典的分布式一致性算法，用于解决分布式系统中的一致性问题。Paxos算法定义了三个角色，这些角色可以单独一个节点执行，也可以在同一个节点上执行。Paxos算法的执行就是对一个值形成共识，过程如下：
- 提议者(Proposer)： 发起一个提案，并向其他节点发送提案请求。
- 接收者(Acceptor)： 收到提案后，如果没有其他更高编号的提案，则接受提案并广播接受通知。
- 学习者(Leaner)： 当收到大多数节点的接受通知后，就可以学习该值。
Paxos的运行分为下面两个阶段。
- 在第一阶段，Proposer通过获得大多数Acceptor的承诺来获得临时的领导地位，这个领导地位会持续到另一个Proposer获得大多数Acceptor的承诺为止。
- 在第二阶段，Proposer利用它临时的领导权来发起新的提案让大家接受。Proposer只有很短的时间利用其已建立的领导权来获得大多数Acceptor的接受。如果Proposer不够快，其临时领导权可能会被另一个Proposer接管，而新Proposer必须重复此过程。
# 阶段1 (Phase 1)
# Prepare阶段(Phase 1a)
每个Proposer会发起一个提案，每个提案都带一个编号，这个编号是全局唯一且递增的。
Proposer会向所有Acceptor发送一个prepare(n)的消息，其中n是提案编号。
# Promise阶段(Phase 1b)
Acceptor接收到prepare(n)请求后，会比较提案编号n和自己已接受的最大提案编号m。
- n>m，即n大于已接受的最大提案编号m。它会发送
promise(m,v)消息，并承诺不再接受编号小于n的提案。同时，Acceptor会将自己已经接受的最大编号提案的值告诉Proposer。 - n<=m，即n小于或等于已接受的最大提案编号m。Acceptor会拒绝该prepare请求。
# 阶段2 (Phase 2)
# Accept阶段(Phase 2a)
Proposer在收到多数Acceptor的Promise响应后，会从所有响应中选择一个已接受的最大编号提案的值，作为本次提案的值。然后，Proposer会将提案编号n和提案值v发送给所有Acceptor，即发送Accept(n, v)消息，请求他们接受这个提案。
# Accepted阶段(Phase 2b)
Acceptor收到Accept(n, v)请求后，会检查该提案编号n是否大于等于自己承诺过的最大提案编号m。如果满足条件，Acceptor会接受这个提案，并将接受结果发送给Proposer，即发送Accepted消息。否则，Acceptor会拒绝该请求。
假如有多个Proposer，此时Proposer B发出了一个提案编号更大n2(n2>n)的提案。如下，当Proposer A发出accept(n,v)请求时，此时Acceptor承诺过的最大填编号是n2，它大于Proposer的提案编号n，所以此时会拒绝Proposer A的accept请求，转而接受Proposer B的提案。
当Proposer收到多数Acceptor的Accepted响应时，该提案就达成了共识。此时，其他节点可以从Proposer或者Acceptor处学习到这个已达成共识的提案值，以确保系统的一致性。
需要注意的是，这里的“多数”指的是参与者集合的过半数。Paxos算法能够保证在任何时刻，只要有超过半数的节点正常工作，系统就能够达成一致。这使得Paxos算法具有很好的容错性和可扩展性。
# 伪代码
Proposer伪代码
Proposer
{
// Proposer提议者的状态
v; // 建议值
p_num; // 提案编号
acks; // 从Acceptor接收到的确认数
promises; // 从Acceptor接收到的承诺
// 客户端调用Proposer的此函数来提出其期望值。中止后也会调用此函数来重试。
on propose(client_value)
{
p_num = 生成一个大于上次生成的 p_num 的唯一提案编号
v = 客户端值;
acks = 0;
promises = {};
发送<Prepapre, p_num>给所有的Acceptor;
}
// 当提议者从其中一个Acceptor收到承诺消息时，会调用此函数。
on promise(n, promise)
{
if (n != p_num) // 忽略它
return;
promises.add(promise);
if (promises.size == ceil(acceptors.size+1)/2) { // 大多数
if (promises.max_value() != NULL){ // 至少一个承诺具有价值
v = promises.max_value(); // 选择从 Acceptor 接收到的最大编号的值
}
发送 <Accept, p_num, v> 给所有Acceptor;
}
}
// 当Proposer从其中一个Acceptor收到已接受的消息时，将调用此函数。
on accepted(n) {
if (n != p_num)
return; // 忽略它
acks++;
if (acks == ceil(acceptors.size+1)/2) { // 大多数
发送 <Descide, v> 给所有Learner;
}
}
// 当Proposer从其中一个Acceptor收到 nack 消息时，将调用此函数。
on nack(n) {
if (n != p_num)
return; // 忽略它
abort();
p_num = 0; //将导致所有未来消息被忽略
}
}
Acceptor伪代码
Acceptor {
// Acceptor状态
accepted_num // 接受的最高提案编号
promised_num // 承诺的最高提案编号
accepted_value // 接受的值
// 当Acceptor从其中一个Proposer收到准备消息时，会调用此函数。
on prepare (n, sender) {
if (promised_num < n) {
promised_num = n;
存储在磁盘;
发送 <Promise, n, promise(accepted_num, accepted_value)> 给发送者;
} else {
发送 <Nack, n> 给发送者;
}
}
// 当Acceptor从其中一个Proposer收到接受消息时，会调用此函数。
on accept (n, v, sender) {
if (promised_num <= n){
promised_num = n;
accepted_num = n;
accepted_value = v;
存储在磁盘;
发送 <Accepted, n> 给发送者;
}else {
发送 <Nack, n> 给发送者;
}
}
}
Learner伪代码
Learner {
// Learner的状态
decided_value = NULL;
// 当Learner收到其中一个Proposer发来的决定消息时，此函数被调用。
on decide (v){
if (decided_value == NULL) {
decided_value = v;
Learn (v);
}
}
}