分布式系统与单机系统相比有哪些难点？0x01:网络因素由于服务和数据分布在不同的机器上，每次交互都需要跨机器运行，这带来了以下问题：网络延迟：性能和超时同机房网络IO比较块状，但是跨机机房，尤其是跨IDC，网络IO已经成为不可忽视的性能瓶颈。而且，延迟不是带宽，带宽可以随意增加。将千兆网卡换成10千兆网卡只是成本问题，但延迟是物理限制，基本不可能降低。这样带来的问题是系统整体性能的降低，会带来资源锁定等一系列问题，所以系统调用一般需要设置超时时间进行自我保护，但是过长的延迟会带来系统错误。RPC调用超时，头疼：分布式系统调用的三态结果：成功、失败、超时。不要低估这第三种状态，它是几乎所有分布式系统复杂性的根源。这个问题有一些相应的解决方案：异步化，失败重试。针对跨IDC数据分发带来的巨大网络因素影响，一般采用数据同步、代理专线等处理方式。网络故障：丢包、乱序、抖动。这可以通过在可靠的传输协议（例如TCP协议）上构建服务来解决。但是它带来了更多的网络交互。所以这是性能和流量的折衷。这在移动互联网中更需要考虑。0x02：鱼和熊掌不可兼得——CAP法则CAP理论是EricBrewer提出的分布式系统中最重要的理论之一：Consistency：一致性、事务保证、ACID模型。Availability：[高]可用性，避免单点的冗余，至少是灵活的可用性（服务降级）。Partitiontolerance:[High]Scalability（分区容忍度）：一般要求系统能够按需自动扩展，比如HBase。CAP原则告诉我们，这三个因素最多只能满足两个，不可能三个都兼顾。对于分布式系统，分区容错是一个基本要求，所以必须放弃一致性。对于大型网站，对分区容忍度和可用性的要求更高，所以一般会选择适当放弃一致性。对应CAP理论，NoSQL追求AP，而传统数据库追求CA，这也可以解释为什么传统数据库的可扩展性有限。在这三个CAP中，“可扩展性”是分布式系统独有的属性。分布式系统设计的初衷是利用集群多机的能力来处理单机无法解决的问题。当系统性能需要扩展时，一种方式是优化系统性能或升级硬件（scaleup），一种方式是“简单地”增加机器来扩大系统规模（scaleout）.好的分布式系统总是追求“线性可扩展性”，即性能可以随着集群的数量线性增加。可用性和可伸缩性通常是相关的。一个可扩展性好的系统，一般可用性都比较高，因为有多个服务（数据）节点，而不是一个整体的单点。因此，分布式系统中的所有问题基本上都是一致性、可用性和可伸缩性之间的协调和平衡。对于无状态系统，不存在一致性问题。根据CAP原理，它们的可用性和分区容忍度都非常高，简单的增加机器就可以实现线性扩展。对于有状态的系统，需要根据业务需求和特点，牺牲三个CAP中的一个。一般来说，交易系统业务对一致性的要求比较高，一般采用ACID模型来保证数据的强一致性，所以可用性和扩展性比较差。其他大部分业务系统一般不需要保证强一致性，只要最终一致即可。他们一般采用BASE模型，利用最终一致性的思想来设计分布式系统，让系统实现高可用和扩展。性别。CAP定律其实是衡量分布式系统的一个重要指标，另外一个重要指标就是性能。主要有三种一致性模型：强一致性：一旦写入新数据，可以在任何副本中随时读取新值。例如：文件系统、RDBMS、AzureTable都是强一致性的。WeekConsistency（弱一致性）：不同副本上的值有新有旧，需要应用端做更多的工作才能获得最新的值。比如发电机。EvantualConsistency（最终一致性）：一旦更新成功，各副本的数据最终会达到一致性。从这三个一致的模型可以看出，Weak和Eventually一般是异步冗余的，而Strong一般是同步冗余的（多次写入），而异步通常意味着更好的性能，但也意味着更复杂的状态控制。同步意味着简单，但也意味着降低性能。及其他变体：CausalConsistency（因果一致性）：如果进程A通知进程B它更新了数据，那么进程B后续的读操作读取的是A写入的最新值，与A没有因果关系的C最终可以保持一致。Read-your-writesConsistency：如果进程A写入最新的值，那么进程A的后续操作将读取最新的值。但是其他用户可能需要一段时间才能看到它。SessionConsistency（会话一致性）：一旦在一个会话中读取了一个值，就不会再读取一个更旧的值。单调读一致性：用户一旦读到某个值，他就不会读到比这个值更旧的值，其他用户也不一定。最重要的变体是第二个变体：Read-your-WritesConsistency。特别适用于数据更新同步。用户的修改他自己立即可见，但其他用户可以看到他的旧版本。Facebook的数据同步就是基于这个原理。0x03：分布式系统一致性哈希常用技术及应用场景[withvirtualnode]：一致性哈希，数据分布向量clock：时钟向量，多版本数据修改QuorumW+R>N[withvectorclock]：drawerprinciple，Another数据一致性的解决方案。时钟向量，多版本数据修改。Merkletree[withanti-entropy]:DatareplicationMVCC:copy-on-writeandsnapshot2PC/3PC:DistributedtransactionsPaxos:StrongconsistencyprotocolSymmetryandDecentralization:对称和去中心化。对称性简化了系统配置和维护。去中心化是对称性的延伸，可以避免主节点单一，便于集群横向扩展。Map-Reduce：分而治之；移动数据不如移动计算。将计算调度到与存储节点在同一物理机上的计算节点，称为本地化计算。本地化计算是计算调度的重要优化。Gossipprotocol:nodemanagementLeasemechanism:consistenthashing:consistenthashing，解决数据均衡分布的问题我们通常使用的hash算法是hash()modn，但是如果一个节点出现故障，无法快速切换到其他节点。为了解决单点故障问题，我们为每个节点添加一个备节点。当一个节点出现故障时，会自动切换到备节点，类似于数据库的主从。但是仍然无法解决节点增删后哈希重分配的问题，即无法动态增删节点。这时候就引入了一致性哈希的概念，所有的节点都分布到一个哈希环上，每个请求都落在这个哈希环上的某个位置上，只有顺时针方向找到的第一个节点，就是你需要的服务节点.当一个节点出现故障时，只需要在环上寻找下一个可用的节点即可。一致性哈希算法最常用于分布式缓存，例如memcached。Dynamo也将其作为数据分发算法，并对共识算法进行了改进，提出了基于虚拟节点的改进算法。核心思想是引入虚拟节点，每个虚拟节点都有对应的物理节点，每个物理节点可以对应若干个虚拟节点。关于consistenthash的更多内容可以参考作者的另一篇博文：Memcached的分布式算法学习。也可以看这篇文章：ConsistentHashing在分布式应用虚拟节点实践中的一些问题前文提到，ConsistentHashing的一些实现方式使用了虚拟节点的思想。如果使用一般的哈希函数，服务器的映射位置分布很不均匀。因此，利用虚拟节点的思想，在连续体上为每个物理节点（服务器）分配100-200个点。这可以抑制分布不均，并在添加或删除服务器时最大限度地减少缓存重新分布。QuorumW+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模型的一些设置会造成脏数据和版本冲突，所以一般引入vectorclock算法来解决这个问题。需要保证系统中有max(N-W+1,N-R+1)个节点可用。关于NWR模型，推荐阅读TransactionProcessingofDistributedSystems，非常容易理解。vectorclock：时钟向量，多版本数据修改，参考分布式系统的事务处理，非常容易理解。租约机制Chubby和zookeeper获取租约（lease）节点得到系统的承诺：在有效期内，数据/节点角色等有效，不会改变。租约机制的特点：租约发布过程只需要在网络上进行单向通信，发布者可以向接收者重复发送相同的租约。即使发布者偶尔发送租约失败，发布者也可以简单地重新发送解决方案。机器停机对租赁机制影响不大。如果发行人宕机，宕机的发行人通常不能改变之前的承诺，也不会影响租约的正确性。发行方机器恢复后，如果发行方恢复了之前的租赁信息，则发行方可以继续遵守租赁承诺。如果发行者无法恢复租约信息，则只需等待最大租约超时时间即可使所有租约失效，从而不会破坏租约机制。租用机制依赖于过期，这需要发布者和接收者的时钟同步。(1)如果发行者的时钟比接收者的时钟慢，当接收者认为租约到期时，发行者仍然认为租约有效。接收方可以通过在租约到期前申请新的租约来解决这个问题。(2)如果发布者的时钟快于接收者的时钟，当发布者认为租约到期时，可能会向其他节点发布租约，导致承诺失效，影响系统的正确性。对于这种时钟不同步，实践中常见的做法是将发送方的有效期设置得比接收方的有效期略大，只要不影响租约的有效性就可以避免大于时钟误差。在工程中，通常选择的租约时间为10秒。这是经过验证的经验值，可以在实践中作为参考，综合选择合适的时长。双主问题（脑裂问题）租赁机制可以解决网络分区问题导致的“双主”问题，即所谓的“脑裂”现象。配置中心向节点签发租约，表明该节点可以作为主节点。当配置中心发现primary出现问题时，只需要等到之前primary的租约到期，就可以安全地向新的primary节点发出新的租约，而不会出现“双主”问题。在实际系统中，如果采用一个中心节点作为配置中心来发送租约，存在很大的风险。实际系统总是使用多个中心节点作为彼此的副本，形成一个小集群。这个小集群具有高可用性，提供对外发布租约的功能。chubby和zookeeper都是基于这个设计的。Chubby一般有5台机器组成一个集群，可以部署在两个地点，三个机房。Chubby内部的5台机器需要通过Paxos协议选出一台Chubbymaster机器，其他机器都是Chubbyslave，同时只有一台Chubbymaster。Chubby相关的数据，比如锁信息，客户端session信息，需要同步到整个集群。使用半同步，一半以上的机器可以成功回复客户端。最后，可以保证只选择一个与原chubbymaster完全同步的chubbyslave作为新的chubbymaster。Gossip协议Gossip在P2P系统中用于自治节点了解集群（如集群节点状态、负载情况等）。系统中的节点定期相互八卦，很快八卦就传遍了整个系统。A和B两个节点主要通过以下方式进行八卦：A告诉B谁知道八卦是什么；B告诉AB知道哪些八卦已经更新；B更新A告诉他的八卦……说是自治系统，其实节点里面有一些种子节点。种子节点的作用主要体现在新节点加入系统时。当新节点加入系统时，首先与种子节点进行八卦，新节点获取系统信息，种子节点知道系统中有新节点。当其他节点定期与种子节点进行八卦时，它们就会知道有新节点加入。在节点之间的八卦过程中，如果发现某个节点的状态长时间没有更新，则认为该节点已经宕机。Dynamo使用Gossip协议进行成员资格和故障检测。2PC、3PC、Paxos协议：分布式事务的解决方案分布式事务很难做，所以除非必要，一般来说使用最终一致性来避免分布式事务。目前底层的NoSQL存储系统只有谷歌实现分布式事务的系统。它在Bigtable之上用Java语言开发了一个系统Megastore，实现了两级锁，使用Chubby避免了两级锁协调器的宕机。问题。Megastore的实现目前只有简单的介绍，没有相关的论文。2PC实现简单，但效率低，所有参与者都需要区块，吞吐量低；如果没有容错，如果一个节点发生故障，则整个交易将失败。如果参与者在第一阶段完成后没有收到第二阶段的决定，数据节点将进入“不堪重负”状态，这将阻塞整个交易。2PC，3PC的改进版，将2PC的第一段拆成两段：查询，然后锁定资源，最后提交。3PC的核心思想是：问的时候不锁资源，除非大家都同意，才开始锁资源。3PC相对于2PC的优势在于，如果节点处于P状态（PreCommit）时出现Fail/Timeout问题，3PC可以继续直接改变状态为C状态（Commit），而2PC则无所适从。但是3PC实现起来比较困难，无法处理网络分离的问题。如果发送preCommit消息后两个机房都断开了，则协调者所在的机房会中止，剩下的参与者会commit。PaxosPaxos的目的是让整个集群的节点就某个值的变化达成一致。Paxos算法是一种基于消息传递的共识算法。Paxos算法基本上是一种民主选举算法——大多数决策将是整个集群的统一决策。任何一个点都可以提出修改某个数据的提议，提议是否通过取决于集群中是否有超过半数的节点同意（所以Paxos算法要求集群中的节点数为奇数）。这是Paxos与2PC、3PC最大的区别。在2f+1个节点的集群中，允许f个节点不可用。Paxos的分布式民主选举方式，除了保证数据变化的一致性外，还常用于单点切换，比如Master选举。Paxos协议的特点是既难以理解又难以实现：（关于2PC、3PC和Paxos，强烈推荐阅读分布式系统的交易处理，目前大部分支付系统还在自我完善中2PC的基础，一般介绍一个errorprocessor，用于错误协调（回滚或故障处理）MVCC：Multi-versionconcurrencycontrol这是很多RDMS存储引擎实现高并发修改的重要实现机制，详情请看参考：1.多版本并发控制（MVCC）在分布式系统中的应用2.MVCC(Oracle,Innodb,Postgres).pdfMap-Reduce思想1.分而治之2.移动数据不如移动计算如果计算节点和存储节点位于不同的物理机上，计算出来的数据需要通过网络传输，这种方式开销很大，另外一种思路是调度计算与存储节点在同一台物理机上的计算节点，称为本地化计算。本地化计算是计算调度的一个重要优化。经典论文和分布式系统学习DynamoHBaseLSMTreeLSM（LogStructuredMergeTrees）是B+Tree的一种改进，牺牲部分读性能来大幅提升写性能思路：拆分树（1）先写WAL，然后将数据记录到内存中,建立有序子树(memstore)(2)随着子树越来越大,内存子树会刷到磁盘(storefile)(3)读数据:必须遍历所有有序子树(不知道是哪个子树(4)Compact：后台线程将磁盘中的子树合并成一棵大树（子树太多读取速度慢）。其实luceneHBase的索引机制也类似于HBase的LSM树。写的时候也是分段写的，后台合并段。
