分布式系统常用思想和技术综述

与单机系统相比，分布式系统有哪些困难？0x01：网络因素

由于服务和数据分布在不同的机器上，每次交互都需要跨机器运行，因此存在以下问题：

网络延迟：性能、超时

同一机房的网络IO相对较大，但跨机房，特别是跨IDC，网络IO已成为一个不可忽视的性能瓶颈。此外，延迟不是带宽，带宽可以随意增加，千兆网卡到万兆，只是成本问题，但延迟是物理限制，基本上不可能减少。

这带来的问题是系统整体性能的降低，会带来一系列问题，如资源锁定，所以系统呼叫一般设置超时自我保护，但过度延迟会导致系统RPC呼叫加班，引起头痛：分布式系统呼叫三种状态结果：成功、失败、加班。不要低估这个第三种状态，这几乎是所有分布式系统复杂性的根源。

对于这个问题，有一些相应的解决方案：异步化、失败和重新测试。对于跨IDC数据分布带来的巨大网络因素，通常采用数据同步、代理线等处理方法。

• 网络故障：丢包、乱序、抖动。

这可以通过在可靠的传输协议中建立服务来解决，如TCP协议。但它带来了更多的网络交互。因此，它是一个性能和流量 off。移动互联网需要考虑这一点。

0x02：不能兼得鱼和熊掌-CAP定律

Ericccap理论由Ericcap理论组成 Brewer提出的分布式系统中最重要的理论之一：

• Consistency：[强]一致性、事务保障、ACID模型。
• Availiablity：[高]可用性，冗余以避免单点，至少灵活（服务降级）。
• Partition tolerance：[高]可扩展性(分区容忍度)：一般要求系统按需自动扩展，如HBase。

CAP原理告诉我们，这三个因素最多只能满足两个因素，三者不可能兼顾。分区容错是分布式系统的基本要求，因此必须放弃一致性。对于大型网站，分区容错和可用性要求较高，因此一般选择适当放弃一致性。与CAP理论相对应，NoSQL追求AP，而传统数据库追求CA，这也可以解释为什么传统数据库的扩展能力有限。

在CAP三者中，“可扩展性”是分布式系统的独特性。分布式系统的初衷是利用集群多机的能力来处理单机无法解决的问题。当需要扩展系统性能时，一种方法是优化系统性能或升级硬件(scale up)，一种方法是“简单”地增加机器来扩展系统的规模(scale out)。良好的分布式系统总是追求“线性扩展”，即随着集群数量的增加，性能可以线性增长。

可用性和可扩展性一般都是相关的，可扩展性好的系统，其可用性一般都比较高，因为有多个服务(数据)节点，不是整体单点。因此，分布式系统的所有问题基本上都是一致性、可用性和可扩展性之间的协调和平衡。对于没有状态的系统，没有一致性问题。根据CAP原理，它们具有很高的可用性和分区容忍度。简单地添加机器可以实现线性扩展。对于一个状态系统，CAP三者中的一个需要根据业务需求和特点牺牲。一般来说，交易系统业务对一致性要求较高，ACID模型一般用于保证数据的强一致性，因此其可用性和可扩展性相对较差。大多数其他业务系统通常不需要保证强一致性，只要最终一致性，它们通常使用BASE模型，设计分布式系统与最终一致性的想法，使系统可以实现高可用性和可扩展性。

CAP定律实际上是衡量分布式系统的一个重要指标，另一个重要指标是性能。

一致性模型

主要有三种:

• Strong Consistency(强一致性)：一旦新数据被写入，新值可以在任何副本中随时读取。例如：文件系统，RDBMS，Azure Table一致性强。
• Week Consistency(弱一致性)：不同副本上的值有新有旧，应用程序需要做更多的工作来获得最新值。例如Dynamo。
• Evantual Consistency(最终一致性)：一旦更新成功，每个副本的数据最终将达成一致。

从这三种一致模型中，我们可以看到Weak和Eventually通常是异步冗余，而Strong通常是同步冗余（多写）。异步通常意味着更好的性能，但也意味着更复杂的状态控制。同步意味着简单，但也意味着性能下降。

其他变体：以及其他变体：

• Causal Consistency(因果一致性)：假如Process A通知Processprocesss B已经更新了数据，所以Process B的后续读取操作可以读取A写入的最新值，而与A无因果关系的C可以最终一致。
• Read-your-writes Consistency(阅读你所写的一致性)：假如Process A写入最新值，然后 Process A的后续操作将读取最新值。但其他用户可能需要一段时间才能看到它。
• Session Consistency(会话一致性)：一旦在会话中读到某个值，就不会读到更旧的值。
• Monotonic Read Consistency(单调一致性)：一旦用户读到一个值，他就不会读到比这个值更旧的值，其他用户也不一定。

第二条是最重要的变体：Read-your-Writes Consistency。特别适用于数据更新同步，用户修改可以立即看到自己，但其他用户可以看到他的旧版本。Facebook的数据同步采用了这一原则。

0x03：分布式系统常用技术和应用场景

• consistent hashing [with virtual node]：一致性哈希，数据分布
• vector clock：修改时钟向量，修改多版本数据
• Quorum W+R>N [with vector clock]：抽屉原理，数据一致性的另一个解决方案。时钟向量，多版本的数据修改。
• Merkle tree [with anti-entropy]：数据复制
• MVCC：copy-on-write和snapshot
• 2PC/3PC：分布式事务
• Paxos：强一致性协议
• Symmetry and Decentralization：对称性和分散性。对称性(symmetry)简化了系统的配置和维护。分散化是对称性的延伸，可以避免master单点，方便集群scale out。
• Map-Reduce：分而治之；移动数据不如移动计算好。将计算调度到与存储节点在同一物理机器上的计算节点上，称为本地化计算。本地化计算是计算调度的重要优化。
• Gossip协议：节点管理
• Lease机制：

consistent hashing：一致性哈希，解决数据均衡分布问题

我们通常使用hash算法hash() mod n，但是，如果某个节点失效，则不能快速切换到其他节点。为了解决单点故障的问题，我们为每个节点添加了一个备用节点。当某个节点失效时，它会自动切换到备用节点，类似于数据库的master和slave。但是，在添加或删除节点后，仍然无法解决hash重分布的问题，即不能动态添加或删除节点。此时引入了一致性hash概念 ，将所有节点分布在hash环上，每个请求都落在hash环上的某个位置。顺时针方向找到的第一个节点是您需要的服务节点。当一个节点出现故障时，只需在环上找到下一个可用的节点。

一致性hash算法最常用于分布式cache，如注意memcached。Dynamo还将其用作数据分布算法，并对一致性算法进行了改进，提出了基于虚拟节点的改进算法，其核心思想是引入虚拟节点，每个虚拟节点都有一个相应的物理节点，而每个物理节点都可以对应几个虚拟节点。

更多关于一致性hash的内容，请参考作者的另一篇博文：Memcached分布式算法学习。

本文还可以看到哈希在分布式应用实践中的一些一致性问题

virtual node

前面说过，有些Consistententent， 实现Hashing的方法采用了虚拟节点的思想。如果使用一般的hash函数，服务器映射位置的分布非常不均匀。因此，利用虚拟节点的思想，在continum上为每个物理节点(服务器)分配1000～200个点。这样可以抑制分布不均匀，减少服务器增减时的缓存再分布。

Quorum W+R>N：抽屉原理是数据一致性的另一个解决方案

N: 复制的节点数，即数据保存的份数。R: 成功读取操作的最小节点数，即每次读取成功所需的份数。W: 成功写作操作的最小节点数 ，也就是说，每次写成功所需的份数。

所以 W+R>N的意思是:对于有N份拷贝的分布式系统，写W(W<=N)成功计算和写作，读R(R<=N)数据算读成功。

这三个因素决定了可用性、一致性和分区容错性。W+R>N可以保证数据的一致性(C)，W越大，数据一致性就越高。该NWR模型将CAP的选择权交给用户，让用户在功能、性能和成本效益之间进行权衡。

对于一个分布式系统，N通常大于3，这意味着同一数据需要保存在三个以上不同的节点上，以防止单点故障。W是成功写作操作的最小节点，这里的成功写作可以理解为“同步”写作，如N=3，W=1.只需写一个成功的节点，另外两个数据是通过异步复制的。R是成功阅读操作的最小节点。为什么要阅读多个数据？在分布式系统中，数据可能在不同的节点上不一致。我们可以选择在多个节点上阅读不同的版本，以增强一致性。

NWR模型的某些设置会导致脏数据和版本冲突，因此通常需要引入vector 为了解决这个问题，clock算法。

需要确保系统中有max(N-W+1,N-R+1)可以使用一个节点。

对于NWR模型，建议阅读分布式系统的事务处理，写得通俗易懂。

vector clock：修改时钟向量，修改多版本数据

参见分布式系统的事务处理，写得通俗易懂。

lease机制

chubby、zookeeper 系统承诺获得lease(租约)的节点:数据/节点角色在有效期内是有效的，不会改变。

lease机制的特点：

• lease颁发过程只需要如果网络可以单向通信，发起人可以反复向接受人发送相同的lease。即使发起人偶尔发送lease失败，发起人也可以简单地通过重新发送来解决。
• 机器停机对lease机制影响不大。如果发起人停机，停机的发起人通常无法改变之前的承诺，也不会影响lease的正确性。如果发起人在发起人机恢复后恢复了以前的lease， 信息，发起人可以继续遵守lease的承诺。如果发起人无法恢复lease信息，只需等待最大的lease超时就可以使所有lease失效，从而不破坏lease机制。
• lease机制依赖于有效期，这就要求发起人和接收人的时钟同步。(1)如果发起人的时钟比接收人的时钟慢，当接收人认为lease已经过期时，发起人仍然认为lease有效。接收者可以在lease到期前申请新的lease来解决这个问题。(2)如果发起人的时钟比接收人的时钟快，当发起人认为lease已经过期时，lease可能会发给其他节点，导致承诺失效，影响系统的正确性。对于这种时钟不同步，实践中常见的做法是将发起人的有效期设置得比接收人稍大，只需大于时钟误差即可避免对lease有效性的影响。

在工程中，经常选择的lease持续时间为10秒，这是一个验证的经验值，在实践中可以作为参考，综合选择合适的持续时间。

双主题(脑裂)

lease机制可以解决网络分区问题引起的“双主”问题，即所谓的“脑裂”现象。配置中心为节点发放lease，表示该节点可作为primary节点工作。当配置中心发现primary有问题时，只需等到前一个primary的lease过期，就可以安全地向新的primary节点发布新的lease，而不会出现“双主”问题。在实际系统中，以中心节点作为配置中心发送lease的风险也很大。实际系统总是使用多个中心节点作为副本，成为一个小集群，具有很高的可用性，并提供发布lease的功能。chubby和zookeeper都是基于这种设计的。

chubby一般由五台机器组成一个集群，可部署成两地三机房。chubby内部的五台机器需要通过Paxos协议选择chuby master机器，其他机器是chubby slave，同一时刻只有一个chubby master。与chubby相关的数据，如锁定信息、客户端session信息等，都需要同步到整个集群，采用半同步的方法，超过一半的机器可以成功回复客户端。最后，只有一个和原来的chuby可以确保 master保持完全同步的chuby slave被选为新的chubby master。

Gossip协议

在P2P系统中，Gossip用于了解自治节点对集群的理解(如集群的节点状态、负载等)。).系统中的节点定期相互八卦，很快八卦就在整个系统中传播。A、B两个节点八卦的主要方式是:A告诉B谁知道什么八卦；B告诉AB在这些八卦中知道更新了什么；B更新A告诉他八卦... 说是自治系统，其实节点里有一些种子节点。种子节点的作用主要体现在新节点加入系统时。在系统中加入新节点，首先与种子节点八卦，新节点获取系统信息，种子节点知道系统中有更多的新节点。当其他节点定期与种子节点八卦时，就会知道新节点加入了。在每个节点互相八卦的过程中，如果发现某个节点的状态很长时间没有更新，则认为该节点已经停机。

Dynamo使用Gosip协议进行会员和故障检测。

2PC、3PC、Paxos协议： 分布式事务的解决方案

分布式事务很难做，所以除非有必要，否则最终一致性通常被用来避免分布式事务。

目前，Google系统是唯一一个在底层NoSQL存储系统中实现分布式事务的系统。它在Bigtable上开发了一种系统Megastore，用Java语言实现了两阶段锁，并通过Chubby避免了两阶段锁协调员停机带来的问题。目前，Megastore的实现只是一个简单的介绍，没有相关的论文。

2PC

实现简单，但效率低，所有参与者都需要block，throughput低；无容错，一个节点失败，整个事务失败。如果参与者在第一阶段完成后没有在第二阶段收到决策，数据结点将进入“不知所措”状态，这将使整个事务失败。

3PC

2PC改进版，将2PC的第一段break分为两段： 询问，然后锁定资源，最后真正提交。3PC的核心概念是，除非每个人都同意，否则在询问时不锁定资源。

3PC比2PC的优点是，如果结点处于P状态（PreCommit）当Fail/Timeout出现问题时，3PC可以继续直接将状态转化为C状态（Commit），而2PC则不知所措。

然而，3PC难以实现，无法处理网络分离问题。如果precommit消息发送后两个机房断开，此时cordinator所在的机房将abort，剩余的participant将commit。

Paxos

Paxos的目的是同意整个集群的结点对某个值的变化。Paxos算法是一种基于信息传输的一致性算法。Paxos算法基本上是一种民主选举算法——大多数决策将成为整个集群的统一决策。

任何点都可以提出修改数据的建议，这取决于集群中是否有一半以上的结点同意（所以Paxos算法要求集群中的结点是单数）。这是Paxos与2PC和3PC最大的区别，允许F节点在2f+1节点的集群中使用。

除了保证数据变化的一致性外，Paxos的分布式民主选举方式也常用于单点切换，如Master选举。

Paxos协议的特点是难，both 理解 and 实现 :(

对于2PC、3PC和Paxos，强烈推荐阅读分布式系统的事务处理。

目前，大多数支付系统实际上都是在2PC的基础上进行自我完善的。一般来说，引入错误处理器进行错误协调（回滚或失败处理）。

MVCC：并发控制多版本

这是许多RDMS存储引擎实现高并发修改的重要实现机制。详见：

1.并发控制多版本(MVCC)应用于分布式系统

2.MVCC (Oracle, Innodb, Postgres).pdf

Map-Reduce思想1. 分而治之2. 移动数据不如移动计算

如果计算节点和存储节点位于不同的物理机器中，则计算的数据需要通过网络传输，这是非常昂贵的。另一个想法是将计算调度到与存储节点在同一物理机器上的计算节点，称为本地化计算。本地化计算是计算调度的重要优化。

经典论文和分布式系统学习DynamoHBaseLSMS Tree

• LSM（Log Structured Merge Trees）是B+ Treee是一种改进
• 为了大大提高写作性能，牺牲了一些读写性能
• 想法：拆分树（1）先写WAL，然后将数据记录到内存中，构建有序树(memstore)(2)随着子树越来越大，内存的子树会在磁盘上flush(storefile)(3)读取数据:必须遍历所有有序子树(不知道数据在哪棵子树) (4) Compact：后台线程合并磁盘中的子树，变成大树(子树读得慢)

事实上，lucene的索引机制也类似于HBase的LSM树。也写在单独的segment上，后台合并segement。

Java乐园