分布式与一致性协议之常见疑惑(一)

常见疑惑

什么是线性一致性

线性一致性(Linearizability),也称为原子性或强一致性，是分布式系统中的一个一致性模型，它定义了系统对读写操作的行为，以确保系统表现得好像只有一个数据副本，并且所有操作都是原子的。
在线性一致性模型中，系统的行为应该满足以下条件:

• 1.单副本视角(Single Copy View):系统对外表现为只有一个数据副本，即所有客户端看到的数据状态是一致的，不管它们连接到哪个服务器副本
• 2.原子性(Atomicity):每个操作好像都是瞬间完成的，即一旦操作返回给客户端，所有客户端就能立即看到这个操作的结果
• 3.实时性(Real-time):操作的顺序应该与实际发生的时间顺序一致，即如果操作A在操作B之前完成，那么所有客户端都应该先看到操作A的结果，然后才能看到操作B的结果。

线性一致性模型是分布式系统中一致性最强的一个模型，它为客户端提供了最直观和最易于理解的行为保证。然而，实现线性一致性通常需要牺牲性能和可用性，因为在保持强一致行的同时，系统需要在多个副本之间进行更多的协调和通信。

分布式系统中，线性一致性通常通过以下机制来实现:

• 1.一致性:如Paxos、Raft、ZAB等，用于在多个副本之间达成共识，并确保操作的顺序和结果的一致性
• 2.锁机制:用于协调对共享资源的访问，确保同一时间只有一个操作可以修改数据。
• 3.时间同步:确保不同服务器之间的时钟偏差足够小，以便可以准确判断操作的顺序。

线性一致性模型在需要严格数据一致性的场景张非常重要，例如金融系统、实时控制系统等。然而，对于许多其他类型的分布式系统，尤其是那些对性能和可用性有更高要求的系统，可能会选择较弱的一致性模型，如最终一致性(Eventual Consistency)或其他妥协方案

假如，客户端C1要实现X=1,客户端C2要实现X=2,当Raft中的领导者收到C1的写请求，此时，领导者还没有收到大多数节点的确认，领导者又收到了C2的写请求，此时，C2会不会比C1先一步收到大多数节点的确认？

答案: 在Raft算法中领导者负责将客户端的请求(命令)作为日志条目顺序地追加到自己的日志中,并尝试将这些日志条目复制到集群中的其他服务器，日志条目的顺序是由领导者决定的，并且这个顺序会严格按照领导者接收请求的顺序来复制和提交。
对于上面描述的场景:Raft会这样处理

• 1.领导者接收请求:领导者首先收到了客户端C1的写请求X=1,并将其作为日志条目添加到自己的日志中。然后，领导者开始尝试将这个日志条目复制到集群中的其他服务器。
• 2.日志条目复制:在领导者还没收到大多数服务器对这个日志条目X=1的确认之前，领导者又收到了客户端C2的写请求X=2.领导者会将这个请求也作为日志条目添加都自己的日志中，紧随X=1的条目之后。
• 3.顺序复制:领导者会尝试按照日志条目的顺序将它们复制到其他服务器。这意味着X=2的日志条目被复制到大多数服务器之前，领导者会先尝试完成X=1的日志条目的复制
• 4.提交日志条目:只有当X=1的日志条目被大多数服务器确认之后，它才会被认为是"已提交"的，此时领导者才会将X=1应用到状态机，并通知客户端C1请求已成功执行。之后，领导者才会开始尝试复制X=2的日志条目，并重复这个过程

因此，即使在领导者还没有收到大多数节点对X=1的确认之前就收到了X=2的请求，X=2也不会比X=1先一步被提交。Raft算法通过这种顺序性的保证来确保操作的线性一致性，即所有客户端的状态变化顺序是一致的

Raft是如何保证线性一致性的？

Raft算法通过一系列机制来保证线性一致性的，即使得系统表现得好像只有一个数据副本，且所有的操作都是原子的,
以下是Raft算法如何实现线性一致性的关键点:

• 1.领导者的单一性: 在任意给定时间，系统中只有一个领导者。所有客户端请求都必须通过领导者来处理，领导者负责将请求作为日志条目复制到其他服务器。这确保了所有操作都可以通过一个中心点来顺序化
• 2.日志条目的连续性和顺序性:领导者将客户端请求作为日志条目按顺序追加到自己的日志中，并为每个日志条目分配一个连续的索引号。日志条目在领导者上的顺序决定了它们将被应用到状态机的顺序
• 3.日志条目的提交:当一个日志条目被复制到大多数服务器上后，它被认为是"已提交的"。一旦日志条目被提交，它就被应用到状态机上，并且其结果对客户端可见。在Raft中，领导者确保在将结果返回给客户端之前，相应的日志条目已经被提交
• 4.领导者的租约:Raft算法中，领导者有一个租约(lease)，它是一个时间间隔，在这个时间内，领导者假定自己是唯一的活跃领导者。在租约期间，领导者可以不需要与其他服务器通信就能处理客户端请求，这减少了延迟，
  并提高了系统的响应速度。
  5.领导者变更时的线性一致性:当领导者宕机或失去与大多数服务器的通信时，新的领导者会被选举出来。在领导者变更期间，系统不处理新的客户端请求，这保证了在领导者变更过程中不会违反线性一致性。新的领导者确保前任领导者留下的未提交日志条目被正确处理

通过上述机制，Raft算法能够在一个分布式系统中提供线性一致性，即使在面对网络延迟、分区、服务器故障等挑战时也能保持系统的一致性和稳定性

Raft算法如何保证操作的顺序性。

Raft算法是一种分布式系统中用于管理复制日志的一致性算法，它通过一系列机制来保证操作的顺序性。在分布式系统中，多个服务器需要协同工作，保持数据的一致性，而操作顺序性的保证是至关重要的。Raft算法通过以下几个关键机制来确保操作的顺序性:

• 1.领导者选举(Leader Election):
  1.1 Raft算法中，系统通过领导选举机制选出一个领导者(Leader)，所有日志条目的复制都由领导者负责。
  1.2 当现任领导者宕机或失去与大多数服务器的通信时，会触发新的领导者选举
  1.3 在选举过程中，节点之间通过投票来决定哪个节点成为新的领导者
  1.4 一旦选举出新的领导者，所有的后续操作都会通过领导者来保证顺序性
• 2.日志复制(Log Replication):
  2.1 客户端的请求首先发送给领导者
  2.2 领导者将请求作为日志条目(Log Entry)追加到自己的日志中
  2.3 随后，领导者并行地将这些日志条目复制到其他服务器
  2.4 只有当大多数服务器已经存储了该日志条目时，领导者才会将日志条目应用到状态机，此时操作才被认为是"已提交"
  2.5 日志条目在各个服务器上的顺序是由领导者分配的索引号来保证的，因此所有服务器上的日志条目顺序是一致的
• 3.领导者的单调性(Leader Monotonicty):
  3.1 Raft算法中，领导者保证日志条目的顺序单调递增，即在任意任期中，一个日志条目的索引号不会重复
  3.2 这保证了即使在网络分区或领导者变更的情况下，日志条目的顺序性也不会被打乱
• 4.日志匹配属性(Log Matching Property):
  4.1 如果在两个不同的日志中，两个条目有着相同的索引号和任期号，那么这两个条目之前的所有日志条目也必然相同。
  4.2 这个属性保证了即使在发生网络分区或者服务器故障的情况下，各服务器上的日志在大多数情况下是一致的。
• 5.提交之前的状态(State Before Commit):
  5.1 Raft算法中，领导者会跟踪哪些日志条目已经被提交，并确保在将日志条目应用到状态机之前，这些条目已经被复制到了大多数服务器上
  5.2 这确保了在领导者宕机后，新的领导者也能知道哪些操作是已经被提交的，从而保证操作的顺序性

执行多次Basic Paxos为什么如果多个提议者同时提交提案，可能出现因为提案编号冲突，在准备阶段没有提议者收到大多数准备响应，导致协商失败，需要重新协商？

Basic Paxos是一种解决分布式系统中一致性问题的算法。它允许一组进程就某个值达成一致，即使在发生网络分区、进程故障等不确定性的情况下也能保证最终一致性。
在Basic Paxos中，为了达成一致性，提案者(proposer)需要与接收者(acceptor)进行两阶段提交过程:

• 1.准备阶段(Prepare Phase):
  1.1 提案者选择一个提案编号N,并向接受者的多数派发送准备请求(prepare request)
  1.2 当接受者收到准备请求后，如果提案编号N大于它已经响应过的任何准备请求的编号，它就会承诺不再接受编号小于N的任何提案，并将其之前接受的最高编号的提案(如果有)作为响应发送回提案。
• 2.接受阶段(Acceptor Phase):
  2.1 当提案者从多数派的接受者那里得到响应后，它会发出一个带有提案编号N和提案值V的接受请求(accept request).
  2.2 接受者收到接受请求后，如果它没有违背之前发出的任何承诺，就会接受这个提案

但是，如果有多个提案者同时尝试提交提案，可能会出现以下问题:

• 1.提案编号冲突:每个提案者选择的提案编号可能相同或小于已经承诺不再接受的其他提案者发送的提案编号
• 2.准备阶段响应不足:由于网络延迟、分区或进程故障，提案者可能无法从多数派的接受者哪里获得响应。

当发生上述情况时，提案者在准备阶段可能无法接收到大多数接受者的准备响应，导致协商失败。协商失败后，提案者需要重新开始两阶段提交过程，选择一个新的、更大的提案编号，并再次尝试

为了避免提案编号冲突，提案者通常会采用一些策略。例如使用唯一标识符(如进程ID)和时间戳来生成提案编号。此外，还可以通过选举一个领导者(leader)来减少多个提案者同时提交提案的情况，由领导者作为唯一的提案者来提交提案，从而减少冲突和协商失败的可能性