一文搞懂分布式系统一致性算法

为了更好地理解一致性算法，首先我们先了解下什么是分布式系统，什么是分布式一致性，一致性的重要性。

什么是分布式服务系统

提到分布式，就不得不说到集中式系统了，集中式系统是采用单体架构开发部署的系统，整个项目作为一个独立的应用，访问量小的时候可能会部署在一台服务器，当访问量上来后，往往会将单体应用进行集群部署，通过负载均衡服务器来达到避免单点的目的，进一步发展可能会单独部署缓存服务器，数据库等，虽然这种架构有一定的并发能力，但是面对复杂业务，依然无法改变系统是单体架构的事实，业务代码会越来越庞杂，变得越来越难以维护。

单体架构系统的优缺点都很明显

• 优点：
  1. 架构简单，便于管理
  2. 开发速度快、成本低
• 缺点：
  1. 不易扩展，比如现在订单模块是瓶颈，我们希望只扩展订单模块，这一点单体系统是做不到的。
  2. 资源无法隔离，整个单体系统各个功能模块都依赖于同样的数据库、内存等资源，一旦某个功能模块对资源使用不当，就会影响全局，甚至整个系统被拖垮。
  3. 项目过于臃肿，代码都在同一个项目中，整个项目必然变得臃肿，越来越难以维护。

那么当业务发展到一定程度，我们要如何解决单体架构的这些问题呢，没错就是我们的分布式架构。

分布式概念概述

分布式系统呢大家理解分布式概念之前，还需要理解两个概念，并发与并行。

1. 并发：一个CPU同时干多件事情
2. 并行：多个CPU同时干一件事情

所谓分布式系统，其实就是并发与并行的结合，既能并发，也能并行。官方一点的说法呢，就是硬件或者软件组件分布在不同的网络计算机上，彼此之间仅仅通过消息传递进行通信和协调的系统。听起来有点抽象，没关系，现在我们稍微有个概念就行。

分布式优缺点

• 优点：
  1. 高吞吐，集群协同解决单机性能瓶颈
  2. 高可用，冗余部署，个别服务宕机不会影响系统可用性
  3. 高扩展，系统具备快速扩张能力
• 缺点：
  1. 系统设计复杂，管理、运维难度大幅增加
  2. 数据一致性问题，也是业界普遍认为带来的最大的问题

如何解决数据一致性问题呢，这就是我们今天重点讨论的分布式系统的数据一致性算法要解决的问题

什么是分布式数据一致性

因为分布式系统是分布在不同网络不同区域的节点上，每个节点都有独立的计算与存储，一致性其实就是要求分布式系统中的各个节点之间不能产生矛盾，数据需要保持一致性

一致性的重要性

CAP理论告诉我们，对于一个分布式系统，不能同时满足一致性（Consistency）、可用性（Availability）、分区容错性（Partition Tolerance），最多只能同时满足两个，但是，无论一个分布式系统如何在CAP三者之间权衡，都无法彻底放弃一致性，如果真的放弃了一致性，导致数据不可信，那么数据就没有了意义，系统也没有价值可言。所以，无论如何，分布式系统的一致性问题都是需要重点关注的。

一致性模型

• 弱一致性
  • 最终一致性
    • DNS （Domain Name System）
    • Gossip （Cassandra的通信协议）
• 强一致性
  • 同步
  • Paxos
  • Raft （mult-paxos）
  • ZAB （mult-paxos）

明确问题

为了保证数据的可靠性，数据不能存在单点上，分布式系统的一般解决方案是状态机复制（state machine replication）。

状态机复制，听着很高大上，其实本质就是通过log的形式，往节点上写入log，然后将日志复制到其他节点，保证日志不是存储在单点，而是存在多个节点

其实我们今天讨论的准确的说，应该是状态机复制（state machine replication）的共识算法。

Paxos其实是一个共识算法，系统的最终一致性，不仅需要达成共识，还取决于client的行为

强一致性算法——主从同步

主从同步复制

1. Master接受写请求
2. Master复制log至Slave
3. Master等待，直到所有从库返回

问题：

一个节点失败，Master阻塞，导致整个集群不可用，虽然保证了一致性，但可用性却大大降低

强一致性算法——多数派

基本思想：

多数派

• 每次写都保证写入大于N/2个节点，每次读保证从大于N/2个节点中读

问题：在并发环境下，无法保证系统正确性，顺序非常重要

强一致性算法那——Paxos

为了描述Paxos算法，Lamport虚拟了一个叫做Paxos的希腊城邦，这个岛按照议会民主制的政治模式制定法律，但是没人愿意将自己的全部时间和精力放在这种事情。所以无论是议员，议长还是传递纸条的服务员都不能承诺别人需要时一定出现，也无法承诺批准决议或者传递消息的时间。

Paxos有三个版本

• Basic Paxos
• Multi Paxos
• Fast Paxos

Basic Paxos

角色介绍：

• Client：系统外部角色，请求发起者。像民众。
• Proposer：接受Client请求，向集群提出提议（propose）。并在冲突发生时，起到冲突调节者的作用。像议员，提民众提出议案。
• Acceptor（Voter）：提议投票和接收者，只有形成法定人数（一般即为多数派）时，提议才会最终被接收。像国会。
• Learner：提议接受者，backup，备份，对集群一致性没什么影响。像记录员。

步骤、阶段：

1. 步骤一：proposer提出一个议案，编号为N，此N大于这个proposer之前提出的议案编号。请求acceptors的多数派接受。
2. 步骤二：如果N大于此acceptor之前接受的任何提案编号则接受，否则拒绝。
3. 步骤三：如果达到了多数派，proposer会发出accept请求，此请求包含提案编号N，以及提案内容。
4. 步骤四：如果此acceptor在此期间没有收到任何编号大于N的提案，则接受此提案内容，否则忽略。

sequenceDiagram
participant Client
participant Proposer
participant Acceptor
participant Learner
Client -->> Proposer:Request
Proposer -->> Acceptor:Prepare(1)
Acceptor -->> Proposer:Promise(1,{Va,Vb,Vc})
Proposer -->> Acceptor:Accept!(1,Vn)
Acceptor -->> Proposer:Accepted(1,Vn)
Acceptor -->> Learner:Accepted(1,Vn)
Learner -->> Client:Response

问题：

• 难实现
• 效率低（2轮RPC）
• 活锁（liveness）或者dueling

Multi Paxos

加入新概念，Leader：唯一的propser，所有请求都需经过Leader

赏

谢谢你请我吃糖果

支付宝

微信