分布式系统基石:Paxos

标签: 分布 系统 基石 | 发表时间:2020-02-22 00:10 | 作者:老马
出处:http://weekly.dockone.io

这个世界上只有一种一致性算法,那就是Paxos,其它的算法都是残次品。
——Mike Burrows(Google Chubby 的作者)

Paxos是学习分布式系统无法绕开的一环,从理论上看Paxos是非常优雅的,但是实现起来就没有那么简单了。《 The Part-Time Parliament》又看不懂,只能看《 Paxos Made Simple》和 视频教程这种东西才能维持的了生活这样子。

Paxos

基本问题

假设一组进程可以提议一些值,共识算法需要保证最终只有一个提议的值被选中。对于共识的安全性要求如下:
  • 只有被提出的值才有可能被选中
  • 只有一个值被选中
  • 进程只会学习选中的值


Paxos算法中有三中主体:提议者(proposer)、接受者(acceptor)和学习者(learner),一个进程可以扮演多种主体。
  • 任何主体会以任意速度执行,可能停机或者重启
  • 消息会花费任意长的时间传递,会丢失或者重复,但是不会被破坏


选一个值

一个最简单的方案就是设置唯一接受者,让它选择第一接收到的值,但是这样是无法处理接受者崩溃的情况的。因此比较安全的方法是设置多个接受者,选择当大多数接受者接收的值。

可以尝试设计一个要求:

P1. 接受者接收它收到的第一个提议。

然而,如果不存在一个被大多数接受的值,那么就无法达成共识了。因此最好让接受者可以接收多个提议,每个提议用一个递增的数字进行编号。现在接受者可以接收多个提议了,但是需要保证所有选中的提议都包含同一个值,根据编码递增性质,可以给出要求:

P2. 如果一个包含值v的提议被选中,任何选中的高编号的提议必须包含值v。

一个提议被选中的前提是至少被一个接受者接收,所以通过满足一下条件来满足P2:

P2a. 如果一个包含值v的提议被选中,任何被接受的高编号的提议必须包含值v。

如果一个刚苏醒的提议者给没有接收过任何提议的接受者一个高编号的提议,那就有可能破坏P2a,因此可以加强为:

P2b. 如果一个包含值v的提议被选中,任何由提议者提出的高编号的提议必须包含值v。

进一步可以通过满足P2c来满足P2b:

P2c. 对于任意的v和n,如果一个包含值v,编号为n的提议被提出,存在一个由大多数接受者组成的集合S,那么必然为两种情况之一:
  • S中不存在任何接受者接受了编号小于n的提议
  • v就是S中接受者已经接受的最高编号并且编号小于n的提议的值


根据P2c的要求,提议者在提议之前必须知道编号小于n的最大编号提议,包括那些已经被接受的或者将要被接受的。一个提议是否会被接受无法预测,但是可以让接受者保证不接受编号小于n的提议。

这就需要提议者事先发送一个带编号n的准备请求给接受者,要求接受者返回:
  • 一个承诺:它不会接收任何编号小于n的提议
  • 已经接受的最高编号的提议


如果提议者发出的准备请求得到了大多数接受者的回应,那么它将编号n包含值v的提议发送给这些接受者,那么v是回应中最高编号的提议值,如果没有提议,那么可以是任意值。

因此对于接受要求就是:

P1a 接受者接受一个编号n的提议当且仅当它没有响应过编号大于n的准备请求。

阶段1:
  • 提议者选择一个提议编号n,然后将带有编号n的准备请求发送给大多数接受者。
  • 如果一个接受者接收到一个准备请求,其编号n大于任何已经回应过的准备请求,那么接收者返回一个承诺:它不会接收任何编号小于n的提议,以及已经接受的最高编号的提议。


阶段2:
  • 如果提议者发出的准备请求得到了大多数接受者的回应,那么它将编号n包含值v的提议发送给这些接受者,那么v是回应中最高编号的提议值,如果没有提议,那么可以是任意值。
  • 如果接收者收到了编号为n的接受请求,除非已经回应了一个更高编号的准备请求,否则接收这个提议。


学习选到值

最简单的策略就是让每个接受者把选中的提议发送给全部的学习者,但是这样的消息数量巨大。消息最少的方法是将每个接受者将选中的提议发送给一个特殊的学习者,然后又转给全体学习者。只有一个负责转发的特殊学习者容错性较差,可以设置多个这样的学习者。如果消息丢失的话,学习者可能得不到大多数接受者的选择提议,这个时候可以通过新的提议获取,比如让提议者主动发起一个提议。

进展

如果有两个提议者互相不停打断对方的准备阶段,那么永远没有提议被选中。解决方法就是使用领导选举算法,选举一个唯一的提议者。

实现

在具体实现中,算法需要选举一个领导作为唯一提议者和特殊学习者。要使用容错的稳定存储来记录接受者需要记住的信息。

MultiPaxos

Paxos每次只达成一个值的共识,如果我们要实现状态机就需要一条日志,做法就是在每条日志项上运行一次Paxos,然而这样做的代价是巨大的,将Paxos应用到日志上需要处理以下技术点。

新项

新的日志项需要加到从头开始第一个值没有被选中的日志槽中。

服务器可以并行处理添加表项,但是应用到状态机的时候必须是有序的。

提高效率

  • 领导选举:多个提议者容易造成冲突,降低性能,索性选举一个领导负责提议,领导选举可以采用最大ID等选举算法;
  • 单次准备:将领导任期内的所有选中表项都使用一个编号(前提是插入位置的后面没有其他被选中的日志槽),这样每个领导任期之内只需要一次准备,后续添加表项直接使用接收请求(直到被拒绝为止);


备份和应用

算法还面临两个问题。

问题一:如何将日志备份到全部节点?

在后台不断尝试发送接受请求确保全部节点响应。

问题二:如何让其他节点知道日志项被选中?

首先约定将选中的日志槽的编号设为无穷acceptedProposal[i] = ∞,记录第一个未选中日志槽的位置firstUnchosenIndex。
  • 提议者告知接收者:在请求RPC中包含firstUnchosenIndex,接收者将所有满足i < request.firstUnchosenIndex和acceptedProposal[i] == request.proposal的日志槽i标记为选中;
  • 处理旧领导添加的日志项:接受者在回应中包含firstUnchosenIndex,如果提议者的firstUnchosenIndex大于接收者的firstUnchosenIndex,提议者发送Success RPC。


接收者收到RPC Success(index, v)之后,设置acceptedValue[index] = v和acceptedProposal[index] = ∞,返回firstUnchosenIndex。

原文链接: https://juejin.im/post/5d81cd1bf265da03b31c0466,作者:zhenghaoz

相关 [分布 系统 基石] 推荐:

分布式系统基石:Paxos

- - DockOne.io
这个世界上只有一种一致性算法,那就是Paxos,其它的算法都是残次品. ——Mike Burrows(Google Chubby 的作者). Paxos是学习分布式系统无法绕开的一环,从理论上看Paxos是非常优雅的,但是实现起来就没有那么简单了. 《 The Part-Time Parliament》又看不懂,只能看《 Paxos Made Simple》和 视频教程这种东西才能维持的了生活这样子.

分布式缓存系统 Xixibase

- Le - 开源中国社区最新软件
Xixibase是一个高性能,跨平台的分布式缓存系统. Xixibase server 采用 C++ 实现,底层网络库采用的是Boost Asio. Xixibase 主要特点: 1. 实现'Local Cache'功能, 当客户端打开'Local Cache'选项, 客户端可以将数据同时存储在Server 端和本地,并且保证本地数据和Server 端的数据的一致性.

分布式检索系统 ElasticSearch

- - 丕子
ElasticSearch最近发展不错,github等都用它,可以关注I下. ElasticSearch是分布式,REST风格,搜索和分析系统. 具有实时数据,实时分析,分布式,高可用性,多租户,全文搜索,面向文档,冲突管理,自由模式,rest风格API,每个操作的持久性,Apache 2的开源许可证,基于Apache Lucene之上的特点.

分布式消息系统:Kafka

- - 标点符
Kafka是分布式发布-订阅消息系统. 它最初由LinkedIn公司开发,之后成为Apache项目的一部分. Kafka是一个分布式的,可划分的,冗余备份的持久性的日志服务. 在大数据系统中,常常会碰到一个问题,整个大数据是由各个子系统组成,数据需要在各个子系统中高性能,低延迟的不停流转. 传统的企业消息系统并不是非常适合大规模的数据处理.

分布式系统介绍-PNUTS

- - CSDN博客推荐文章
PNUTS是Yahoo!的分布式数据库系统,支持地域上分布的大规模并发操作. 它根据主键的范围区间或者其哈希值的范围区间将表拆分为表单元(Tablet),多个表单元存储在一个服务器上. 一个表单元控制器根据服务器的负载情况,进行表单元的迁移和拆分. 每条记录的数据都没有固定的模式(采用JSON格式的文本).

Ganglia:分布式监控系统

- - CSDN博客移动开发推荐文章
1         环境安装配置. 1.1      依赖软件下载. Ganglia是伯克利开发的一个集群监控软件. 可以监视和显示集群中的节点的各种状态信息,比如如:cpu 、mem、硬盘利用率, I/O负载、网络流量情况等,同时可以将历史数据以曲线方式通过php页面呈现. 而ganglia又依赖于一个web服务器用来显示集群状态,用rrdtool来存储数据和生成曲线图,需要xml解析因此需要expat,配置文件解析需要libconfuse.

kafka分布式消息系统

- - CSDN博客云计算推荐文章
Kafka[1]是linkedin用于日志处理的分布式消息队列,linkedin的日志数据容量大,但对可靠性要求不高,其日志数据主要包括用户行为(登录、浏览、点击、分享、喜欢)以及系统运行日志(CPU、内存、磁盘、网络、系统及进程状态). 当前很多的消息队列服务提供可靠交付保证,并默认是即时消费(不适合离线).

分布式内存文件系统:Tachyon

- - 杨尚川的个人页面
Tachyon是一个分布式内存文件系统,可以在集群里以访问内存的速度来访问存储在Tachyon里的文件. Tachyon是架构在最底层的分布式文件系统和上层的各种计算框架之间的一种中间件,其主要职责是将那些不需要落地到DFS里的文件,落地到分布式内存文件系统中,来达到共享内存,从而提高效率,减少内存冗余,减少GC时间等.

FastDFS分布式文件系统

- - 开源软件 - ITeye博客
       FastDFS是一个开源的轻量级 分布式文件系统,它对文件进行管理,功能包括:文件存储、文件同步、文件访问(文件上传、文件下载)等,解决了大容量存储和负载均衡的问题. 特别适合以中小文件(建议范围:4KB < file_size <500MB)为载体的在线服务,如相册网站、视频网站等等.

FastDFS分布式文件系统架构

- - 企业架构 - ITeye博客
FastDFS分布式文件系统架构.            FastDFS是一个开源的分布式文件系统,她对文件进行管理,功能包括:文件存储、文件同步、文件访问(文件上传、文件下载)等,解决了大容量存储和负载均衡的问题. 特别适合以文件为载体的在线服务,如相册网站、视频网站等等. 二、 FastDFS系统架构.