【架构专题】阿里巴巴面试必问的分布式算法

35岁程序员那些事

发布于 2023-08-18 12:42:11

4560

发布于 2023-08-18 12:42:11

分布式算法是一种设计用于在由互连处理器构成的计算机硬件上运行的算法。分布式算法应用于分布式计算的不同应用领域，如电信、科学计算、分布式信息处理、实时过程控制等。分布式算法解决的标准问题包括领导人选举、共识、分布式搜索、生成树生成、互斥和资源分配。

分布式算法是并行算法的一个子类型，通常同时执行，算法的不同部分在独立的处理器上同时运行，并且对算法的其他部分正在做什么的信息有限。开发和实施分布式算法的主要挑战之一是在面对处理器故障和不可靠的通信链路时成功地协调算法的独立部分的行为。解决给定问题的适当分布式算法的选择取决于问题的特征，以及算法将运行的系统的特征，例如处理器或链路故障的类型和概率，可以执行的进程间通信，以及不同进程之间的时间同步级别。

Part.1 理解原子提交

原子提交是一种操作，其中一组不同的更改作为单个操作应用。如果原子提交成功，则意味着所有更改都已应用。如果在完成原子提交之前出现故障，则“提交”将中止并且不会应用任何更改。

解决原子提交问题的算法有两阶段提交协议和三阶段提交协议。

在计算机科学领域，原子提交是将一组不同的更改应用为单个操作的操作。如果应用了更改，则称原子提交已成功。如果在完成原子提交之前发生故障，则撤销原子提交中完成的所有更改。这确保系统始终处于一致状态。隔离的另一个关键属性来自于它们作为原子操作的性质。隔离确保一次只处理一个原子提交。原子提交最常见的用途是在数据库系统和版本控制系统中。

原子提交的问题在于它们需要多个系统之间的协调。由于计算机网络是不可靠的服务，这意味着没有算法可以协调所有系统，如两将问题中所证明的那样。随着数据库变得越来越分布式，这种协调将增加进行真正原子提交的难度。

（1）原子提交的用法

原子提交对于数据的多步更新至关重要。这可以在两个支票账户之间的汇款的简单示例中清楚地显示出来。

在将 100 美元从账户 X 转移到 Y 的交易中，检查账户 Y 余额的交易使这个示例变得复杂。首先，首先从账户 X 中删除 100 美元。其次，将 100 美元添加到账户 Y。如果整个操作没有作为一个原子提交完成，那么可能会出现几个问题。如果系统在操作中途出现故障，在从 X 中取出钱后，在添加到 Y 中之前，那么 100 美元就消失了。另一个问题是，如果在添加 100 美元之前检查 Y 的余额，则会报告 Y 的错误余额。

对于原子提交，这两种情况都不会发生，在系统故障的第一种情况下，原子提交将被回滚并将钱返回给 X。在第二种情况下，Y 的余额请求不会发生，直到原子提交提交已完全完成。

（2）数据库系统

数据库系统中的原子提交满足ACID的两个关键属性，原子性和一致性。仅当原子提交中的每个更改都一致时，才能实现一致性。

原子提交对于数据库中的多步操作至关重要。由于数据库所在的物理磁盘的现代硬件设计，真正的原子提交不存在。磁盘上可以写入的最小区域称为扇区。单个数据库条目可能跨越几个不同的扇区。一次只能写入一个扇区。这个写入限制是为什么真正的原子提交是不可能的。修改内存中的数据库条目后，它们将排队等待写入磁盘。这意味着示例中确定的相同问题再次出现。这个问题的任何算法解决方案仍然会遇到两个将军的问题。两阶段提交协议和三阶段提交协议试图解决这个问题以及与原子提交相关的其他一些问题。

两阶段提交协议需要一个协调器来维护在出现问题时恢复数据库原始状态所需的所有信息。顾名思义，有两个阶段，投票和提交。

在投票阶段，每个节点将原子提交中的更改写入自己的磁盘。然后节点将它们的状态报告给协调器。如果任何节点没有向协调器报告或它们的状态消息丢失，协调器就会认为该节点的写入失败。一旦所有节点都向协调器报告，第二阶段就开始了。

在提交阶段，协调器向每个节点发送提交消息以记录在它们各自的日志中。在将此消息添加到节点日志之前，所做的任何更改都将被记录为不完整。如果任何节点报告失败，协调器将改为发送回滚消息。这将删除节点已写入磁盘的所有更改。

三阶段提交协议试图消除两阶段提交协议的主要问题，如果协调器和另一个节点在提交阶段同时发生故障，就会发生这种情况，但两者都不知道应该采取什么行动。为了解决这个问题，第三阶段被添加到协议中。准备提交阶段发生在投票阶段之后和提交阶段之前。

在投票阶段，类似于两阶段提交，协调器请求每个节点准备好提交。如果任何节点发生故障，协调器将在等待故障节点时超时。如果发生这种情况，协调器会向每个节点发送一条中止消息。如果任何节点返回失败消息，将执行相同的操作。

在投票阶段从每个节点收到成功消息后，准备提交阶段开始。在此阶段，协调器向每个节点发送一条准备消息。每个节点必须确认准备消息并回复。如果错过任何回复或任何节点返回它们未准备好，则协调器将发送一条中止消息。在超时到期之前没有收到准备消息的任何节点都会中止提交。

在所有节点都回复了准备消息之后，提交阶段开始。在此阶段，协调器向每个节点发送提交消息。当每个节点收到此消息时，它会执行实际的提交。如果提交消息由于消息丢失或协调器失败而未到达节点，则他们将在超时到期时执行提交。如果协调器在恢复时失败，它将向每个节点发送一条提交消息。

（3）修订版本

原子提交是版本控制软件的一个共同特征，对于在存储库中保持一致的状态至关重要。大多数版本控制软件不会应用任何失败的提交部分。值得注意的例外是CVS、VSS和IBM Rational ClearCase（在 UCM 模式下）。

例如，如果版本控制软件遇到无法自动解决的合并冲突，则不会合并变更集的任何部分。相反，开发人员有机会恢复他们的更改或手动解决冲突。

这可以防止整个项目由于部分应用的更改集而进入中断状态，其中来自提交的一个文件已成功提交，但具有相关更改的另一个文件失败。

原子提交也可以指使用版本控制软件在单个操作中同时跨多个项目进行更改的能力，使用称为 monorepo 的版本控制软件开发策略。

（4）约定原子提交

当使用版本控制系统时，一个常见的约定是使用小提交。这些有时被称为原子提交，因为它们（理想情况下）只影响系统的一个方面。这些原子提交可以提高可理解性，减少回滚更改的工作量，更容易识别错误。

更大的可理解性来自提交的小规模和集中性质。如果只寻找一种变化，则更容易理解变化的内容和变化背后的原因。在对源代码进行格式更改时，这一点变得尤为重要。如果将格式和功能更改结合在一起，则很难识别有用的更改。想象一下，如果文件中的间距从使用制表符更改为三个空格，文件中的每个制表符都将显示为已更改。如果还进行了一些功能更改，这将变得至关重要，因为审阅者可能根本看不到功能更改。

如果只进行原子提交，那么引入错误的提交将变得更容易识别。不需要查看每个提交来查看它是否是错误的原因，只需要检查处理该功能的提交。如果要回滚错误，原子提交再次使工作变得更加简单。在集成任何以后的更改之前，不必恢复到有问题的修订并手动删除更改；开发人员可以简单地恢复已识别提交中的任何更改。这也降低了开发人员意外删除恰好在同一提交中的不相关更改的风险。

如果一次只提交一个错误修复，原子提交还允许轻松审查错误修复。审阅者不必检查多个可能不相关的文件，而只需检查直接影响正在修复的错误的文件和更改。这也意味着可以轻松打包错误修复以进行测试，因为只有修复错误的更改才会提交。

Part.2 共识

共识算法试图解决许多进程就共同决策达成一致的问题。更准确地说，共识协议必须满足以下四个正式属性。

终止，每一个正确的过程都决定了一些价值；
有效性，如果所有进程都提出相同的值，然后每个正确的过程决定；
完整性，每个正确的进程最多决定一个值，如果它决定了某个值V，然后V一定是由某个过程提出的；
协议，如果一个正确的过程决定V, 然后每个正确的过程决定V。

其中，解决共识的常用算法有Paxos算法和Raft算法。

（1）Raft算法

Raft是一种共识算法，旨在替代Paxos系列算法。通过逻辑分离，它的目的是比 Paxos 更容易理解，但它也被正式证明是安全的，并提供了一些额外的功能。Raft 提供了一种在计算系统集群中分布状态机的通用方法，确保集群中的每个节点都同意同一系列的状态转换。它有许多开源参考实现，在Go、C++、Java和Scala中有完整规范的实现。它以可靠、复制、冗余和容错命名。

Raft 不是拜占庭容错(BFT) 算法：节点信任当选的领导者。

Raft 通过选举产生的领导者达成共识。raft 集群中的服务器要么是leader要么是follower ，并且可以在选举的精确情况下成为候选人（领导者不可用）。领导者负责将日志复制到追随者。它定期通过发送心跳消息通知追随者它的存在。每个跟随者都有一个超时时间（通常在 150 到 300 毫秒之间），在此期间它期望来自领导者的心跳。超时在收到心跳时重置。如果没有收到心跳，follower 将其状态更改为 candidate 并开始 leader 选举。

（2）Paxos算法

Paxos是一系列协议，用于在不可靠或易出错的处理器网络中解决共识问题。共识是一组参与者就一个结果达成一致的过程。当参与者或他们的通信可能遇到故障时，这个问题就变得困难了。

正如Leslie Lamport所建议并由Fred Schneider调查的那样，共识协议是分布式计算状态机复制方法的基础。状态机复制是一种将算法转换为容错的分布式实现的技术。临时技术可能会使重要的故障案例得不到解决。Lamport 等人提出的原则性方法。确保所有案件都得到安全处理。

Paxos 协议于 1989 年首次提交，并以希腊Paxos岛上使用的虚构立法共识系统命名，Lamport 在那里写道，议会必须运作，“即使立法者不断进出议会会议厅”。后来于1998年作为期刊文章发表。

Paxos 系列协议包括处理器数量、学习约定值之前的消息延迟数量、各个参与者的活动级别、发送的消息数量和失败类型之间的一系列权衡。尽管在异步网络中没有确定性的容错共识协议可以保证进展（Fischer、Lynch和Paterson 的论文证明了这一结果），但 Paxos 保证了安全性（一致性），以及可能阻止其进展的条件很难挑起。

Paxos 通常用于需要持久性的地方（例如，复制文件或数据库），其中持久状态的数量可能很大。即使在某些有限数量的副本无响应期间，该协议也会尝试取得进展。还有一种机制可以删除永久失败的副本或添加新副本。

Part.3 实现Raft

这篇文章我就不详细的分析Raft算法的原理了，主要是因为也讲不明白，太难了。

工业级别使用Raft算法的框架有哪些呢？

（1）CockroachDB在复制层使用 Raft；

（2）Etcd使用 Raft 来管理一个高可用的复制日志；

（3）Hazelcast使用 Raft 来提供其 CP 子系统，这是一个用于分布式数据结构的强一致性层。

（4）MongoDB在复制集中使用 Raft 的变体。

（5）Neo4j使用 Raft 来保证一致性和安全性。

（6）RabbitMQ使用 Raft 来实现持久的、复制的 FIFO 队列。

（7）Splunk Enterprise 在搜索头集群 (SHC)。

（8）TiDB使用 Raft 和存储引擎 TiKV。