文档章节

Paxos在大型系统中常见的应用场景

山哥
 山哥
发布于 2012/03/19 10:03
字数 1509
阅读 318
收藏 3
点赞 0
评论 0

在分布式算法领域,有个非常重要的算法叫Paxos, 它的重要性有多高呢,Google的Chubby [1]中提到

all working protocols for asynchronous consensus we have so far encountered have Paxos at their core.

关于Paxos算法的详述在维基百科中有更多介绍,中文版介绍的是choose value的规则[2],英文版介绍的是Paxos 3 phase commit的流程[3],中文版不是从英文版翻译而是独立写的,所以非常具有互补性。Paxos算法是由Leslie Lamport提出的,他在Paxos Made Simple[4]中写道

The Paxos algorithm, when presented in plain English, is very simple.

当你研究了很长一段时间Paxos算法还是有点迷糊的时候,看到上面这句话可能会有点沮丧。但是公认的它的算法还是比较繁琐的,尤其是要用程序员严谨的思维将所有细节理清的时候,你的脑袋里更是会充满了问号。Leslie Lamport也是用了长达9年的时间来完善这个算法的理论。

实际上对于一般的开发人员,我们并不需要了解Paxos所有细节及如何实现,只需要知道Paxos是一个分布式选举算法就够了。本文主要介绍一下Paxos常用的应用场合,或许有一天当你的系统增大到一定规模,你知道有这样一个技术,可以帮助你正确及优雅的解决技术架构上一些难题。

1. database replication, log replication等, 如bdb的数据复制就是使用paxos兼容的算法。Paxos最大的用途就是保持多个节点数据的一致性。

2. naming service, 如大型系统内部通常存在多个接口服务相互调用。
1) 通常的实现是将服务的ip/hostname写死在配置中,当service发生故障时候,通过手工更改配置文件或者修改DNS指向的方法来解决。缺点是可维护性差,内部的单元越多,故障率越大。
2) LVS双机冗余的方式,缺点是所有单元需要双倍的资源投入。
通过Paxos算法来管理所有的naming服务,则可保证high available分配可用的service给client。象ZooKeeper还提供watch功能,即watch的对象发生了改变会自动发notification, 这样所有的client就可以使用一致的,高可用的接口。

3.config配置管理
1) 通常手工修改配置文件的方法,这样容易出错,也需要人工干预才能生效,所以节点的状态无法同时达到一致。
2) 大规模的应用都会实现自己的配置服务,比如用http web服务来实现配置中心化。它的缺点是更新后所有client无法立即得知,各节点加载的顺序无法保证,造成系统中的配置不是同一状态。

4.membership用户角色/access control list, 比如在权限设置中,用户一旦设置某项权限比如由管理员变成普通身份,这时应在所有的服务器上所有远程CDN立即生效,否则就会导致不能接受的后果。

5. 号码分配。通常简单的解决方法是用数据库自增ID, 这导致数据库切分困难,或程序生成GUID, 这通常导致ID过长。更优雅的做法是利用paxos算法在多台replicas之间选择一个作为master, 通过master来分配号码。当master发生故障时,再用paxos选择另外一个master。

这里列举了一些常见的Paxos应用场合,对于类似上述的场合,如果用其它解决方案,一方面不能提供自动的高可用性方案,同时也远远没有Paxos实现简单及优雅。

Yahoo!开源的ZooKeeper [5]是一个开源的类Paxos实现。它的编程接口看起来很像一个可提供强一致性保证的分布式小文件系统。对上面所有的场合都可以适用。但可惜的是,ZooKeeper并不是遵循Paxos协议,而是基于自身设计并优化的一个2 phase commit的协议,因此它的理论[6]并未经过完全证明。但由于ZooKeeper在Yahoo!内部已经成功应用在HBase, Yahoo! Message Broker, Fetch Service of Yahoo! crawler等系统上,因此完全可以放心采用。

另外选择Paxos made live [7]中一段实现体会作为结尾。

*  There are significant gaps between the description of the Paxos algorithm and the needs of a real-world system. In order to build a real-world system, an expert needs to use numerous ideas scattered in the literature and make several relatively small protocol extensions. The cumulative effort will be substantial and the final system will be based on an unproven protocol.
* 由于chubby填补了Paxos论文中未提及的一些细节,所以最终的实现系统不是一个理论上完全经过验证的系统

* The fault-tolerance computing community has not developed the tools to make it easy to implement their algorithms.
* 分布式容错算法领域缺乏帮助算法实现的的配套工具, 比如编译领域尽管复杂,但是yacc, ANTLR等工具已经将这个领域的难度降到最低。

* The fault-tolerance computing community has not paid enough attention to testing, a key ingredient for building fault-tolerant systems.
* 分布式容错算法领域缺乏测试手段

这里要补充一个背景,就是要证明分布式容错算法的正确性通常比实现算法还困难,Google没法证明Chubby是可靠的,Yahoo!也不敢保证它的ZooKeeper理论正确性。大部分系统都是靠在实践中运行很长一段时间才能谨慎的表示,目前系统已经基本没有发现大的问题了。

Resources
[1] The Chubby lock service for loosely-coupled distributed systems (PDF)
[2] http://zh.wikipedia.org/wiki/Paxos算法
[3] http://en.wikipedia.org/wiki/Paxos_algorithm
[4] Paxos Made Simple (PDF)
[5] ZooKeeper
[6] The life and times of a zookeeper
[7] Paxos Made Live – An Engineering Perspective (PDF)

本文转载自:http://timyang.net/distributed/paxos-scenarios/

共有 人打赏支持
山哥

山哥

粉丝 242
博文 350
码字总数 136465
作品 0
南京
程序员
Paxos算法在大型系统中常见的应用场景

在分布式算法领域,有个非常重要的算法叫Paxos, 它的重要性有多高呢,Google的Chubby [1]中提到 all working protocols for asynchronous consensus we have so far encountered have Paxos...

wikison
2015/11/28
41
0
Paxos(解决分布式环境一致性问题)算法

Paxos算法 1)问题描述 分布式中有这么一个疑难问题,客户端向一个分布式集群的服务端发出一系列更新数据的消息,由于分布式集群中的各个服务端节点是互为同步数据的,所以运行完客户端这系列...

Picasso
2011/09/17
0
0
分布式设计与开发(二)------几种必须了解的分布式算法

分布式设计与开发中有些疑难问题必须借助一些算法才能解决,比如分布式环境一致性问题,感觉以下分布式算法是必须了解的(随着学习深入有待添加): Paxos算法 一致性Hash算法 Paxos算法 1)...

edeis2011
2016/05/10
10
0
分布式设计与开发(二)------几种必须了解的分布式算法

分布式设计与开发中有些疑难问题必须借助一些算法才能解决,比如分布式环境一致性问题,感觉以下分布式算法是必须了解的(随着学习深入有待添加): Paxos算法 一致性Hash算法 Paxos算法 1)...

商者
2016/04/05
14
0
分布式设计与开发(二)------几种必须了解的分布式算法

分布式设计与开发中有些疑难问题必须借助一些算法才能解决,比如分布式环境一致性问题,感觉以下分布式算法是必须了解的(随着学习深入有待添加): Paxos算法 一致性Hash算法 Paxos算法 1)...

山哥
2012/03/19
0
2
分布式设计与开发------几种必须了解的分布式算法

分布式设计与开发中有些疑难问题必须借助一些算法才能解决,比如分布式环境一致性问题,感觉以下分布式算法是必须了解的(随着学习深入有待添加): Paxos算法 一致性Hash算法 Paxos算法 1)...

wikison
2015/11/28
143
0
Raft一致性算法

Why Not Paxos Paxos算法是 莱斯利·兰伯特(LeslieLamport,就是 LaTeX 中的”La”,此人现在在微软研究院)于1990年提出的一种基于消息传递的一致性算 法。由于算法难以理解起初并没有引起...

cccyb
2016/10/11
3
0
ZooKeeper学习笔记九 ZooKeeper典型应用场景——Master选举

本文学习资源来自《从Paxos到ZooKeeper分布式一致性原理与实践》 电子工业出版社 Master选举是一个在分布式系统中非常常见的应用场景。分布式最核心的特性就是能够将具有独立计算能力的系统单...

xundh
05/02
0
0
分布式设计与开发---宏观概述

有些情况下,对分布式的需求就没这么简单,在每个环节上都有分布式的需求,比如Load Balance、DB、Cache和文件等等,并且当分布式节点之间有关联时,还得考虑之间的通讯,另外,节点非常多的...

zchd
2013/06/27
0
0
强一致、高可用、自动容灾能力背后,阿里X-Paxos的应用实践

axos(分布式一致性算法)作为分布式系统的基石,一直都是计算机系统工程领域的热门话题。Paxos 号称是最难理解的算法,其实当真这么困难么? X-Paxos 是阿里巴巴数据库团队面向高性能、全球部署...

雪夜凋零
2017/08/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

使用爬虫实现代理IP池之放弃篇

啥叫代理IP以及代理IP池 概念上的东西网上搜索一下就好了,这里简单科普一下(大部分会读这篇文章的人,基本是不需要我来科普的),白话说就是能联网并提供代理访问互联网的服务器,它提供的...

一别丶经年
6分钟前
0
0
rabbitmq学习记录(五)交换机Exchange-fanout

之前学习的都是一条消息发给一个消费者,下面开始记录如何把一条信息发给多个消费者 这边我们用到了交换机Exchange 交换机模式:fanout 模式特点:生产者把消息发送给Exchange之后,Exchang...

人觉非常君
27分钟前
0
0
sqoop导入数据到Base并同步hive与impala

使用Sqoop从MySQL导入数据到Hive和HBase 及近期感悟 基础环境 Sqool和Hive、HBase简介 Sqoop Hive HBase 测试Sqoop 使用Sqoop从MySQL导入数据到Hive 使用复杂SQL 调整Hive数据类型 不断更新 ...

hblt-j
33分钟前
0
0
Dart 服务端开发 文件上传

clent端使用angular组件 upload_component.html form id="myForm" method="POST" enctype="multipart/form-data"> <input type="file" name="fileData"> <!-- file field --></form>......

scooplol
33分钟前
0
0
apache和tomcat同时开启,乱码问题

tomcat和apache同时开启,会走apache的转发,执行的是AJP/1.3协议。所以在tomcat的配置文件server中, <Connector port="8009" protocol="AJP/1.3" redirectPort="8443" useBodyEncodingForU......

Kefy
49分钟前
0
0
使用ssh-keygen和ssh-copy-id三步实现SSH无密码登录 和ssh常用命令

ssh-keygen 产生公钥与私钥对. ssh-copy-id 将本机的公钥复制到远程机器的authorized_keys文件中,ssh-copy-id也能让你有到远程机器的home, ~./ssh , 和 ~/.ssh/authorized_keys的权利 第一步...

xtof
今天
0
0
orcale 查询表结构

SELECT t.table_name, t.colUMN_NAME, t.DATA_TYPE || '(' || t.DATA_LENGTH || ')', t1.COMMENTS FROM User_Tab_Cols t, User_Col_Comments t1WHERE t.table_name......

wertwang
今天
0
0
Java 之 反射

反射,剖析 Java类 中的 各个组成部分,映射成 一个个 Java对象,多用于 框架和组件,写出复用性高的通用程序。 测试类代码如下: class Person { private String name; public St...

绝世武神
今天
0
0
华为nova3超级慢动作酷玩抖音,没有办法我就是这么强大

华为nova3超级慢动作酷玩抖音,没有办法我就是这么强大!华为nova3超级慢动作酷玩抖音,没有办法我就是这么强大! 在华为最新发布的nova 3手机上,抖音通过华为himedia SDK集成了60fps、超级...

华为终端开放实验室
今天
0
0
多 SSH Key 实现同一台服务器部署多 Git 仓库

本文以以下需求为背景,介绍详细的做法: 需在同一台服务器同时部署两个不同的 Github 仓库(对 Bitbucket 等 git 服务同样适用) root 用户可在远程登录 SSH 后附上预期的 SSH Key 进行 gi...

yeahlife
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部