在分布式算法领域,有个非常重要的算法叫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.blog.51cto.com/1539170/307122
相关推荐
比如,在一个在线支付场景中,支付系统与银行系统进行数据交互,由于各种网络或者系统故障,可能导致支付成功后,银行系统未能及时更新账户状态,这种情况下就发生了系统间状态不一致的问题。其他常见的不一致问题还...
在系统设计面试中,通常会要求设计高并发、高可用、可扩展的解决方案,因此对上述知识点的深入理解和实践是非常重要的。结合Anki抽认卡的学习方法,可以更有效地巩固这些概念,以便在面试中能够清晰、自信地阐述你的...
恢复机制则确保即使在系统故障后,事务的状态也能正确恢复,常见的方法有日志记录、检查点和两阶段提交等。 2. **分布式数据库并发控制**:在单个数据库中,通过锁机制实现并发控制。但在分布式环境下,由于网络...
在《分布式系统原理与范型》第二版中,读者可以期待深入探讨这些范型的实现细节,以及如何在实际项目中应用。书中可能涵盖了诸如CAP定理、Paxos协议、Raft共识算法、Chubby锁服务、Zookeeper协调服务等经典理论和...
通过深入理解Paxos的工作原理及其应用场景,可以帮助我们在设计和实现分布式系统时做出更加合理的选择。尽管Paxos协议本身较为复杂,但其背后的逻辑和思想对于理解和解决分布式系统中的一致性问题具有重要意义。
例如,强一致性、弱一致性、最终一致性等模型各有优缺点,需要根据应用场景选择合适的模型。 4. **分布式文件系统**:如Hadoop HDFS和Google File System (GFS)等,是分布式系统中的重要组成部分,它们允许多个节点...
在构建大型分布式网站架构时,我们面临的主要挑战是如何处理高...以上就是大型分布式网站架构中的核心知识点,这些技术和策略的合理应用,能够构建出稳定、高效、可扩展的网站系统,应对复杂的业务场景和高并发挑战。
例如,Paxos和Raft算法用于在分布式环境中达成一致性,而Hadoop的HDFS提供了数据冗余和容错能力。还有,负载均衡策略,如轮询、权重轮询和最少连接数等,用于优化资源分配,确保系统性能。 在实际操作层面,我们...
Paxos是一种解决分布式系统中一致性问题的算法,而ZooKeeper是一个分布式协调服务,广泛应用于大型分布式环境中。理解这些概念对于构建高可用、高扩展性的分布式系统至关重要。 《大型网站技术核心原理与案例分析》...
Java作为企业级应用的首选语言,其强大的生态系统和丰富的开源框架使其在分布式系统中扮演了重要角色。 1. **Java分布式技术**:Java提供了多种分布式技术,如RMI(Remote Method Invocation)用于远程方法调用,...
7. **微服务架构**:将单一应用拆分为一组小型、独立的服务,每个服务都运行在其自己的进程中,服务之间通过API进行通信。 8. **容器化与编排**:Docker提供轻量级的虚拟化,Kubernetes等工具则负责容器的部署、...
4. **分布式一致性与复制**:如Paxos、Raft和Zookeeper等算法提供了在分布式环境中保持数据一致性的解决方案。复制技术则用于确保数据在多台服务器间同步,提高可用性。 5. **分布式数据库**:如Hadoop HBase、...
分布式实例是一种在多台计算机上部署和运行相同应用程序实例的技术,这种技术主要应用于大型系统以实现高可用性、可扩展性和负载均衡。在Linux环境中,分布式实例常常与集群计算、分布式存储和分布式数据库等概念...
12. **微服务架构**:将大型应用分解为一组小型、独立的服务,每个服务都能独立部署、扩展和升级,便于构建和维护复杂的分布式系统。 13. **安全性**:分布式系统中的身份验证、授权、加密和审计是保障系统安全的...
2. **微服务架构**:随着技术的发展,微服务架构成为主流,它提倡将一个大型的单体应用拆分成一组小的服务,每个服务都独立部署和运行,提高系统的可伸缩性和容错性。 3. **分布式系统**:掌握分布式计算的基本概念...
在系统设计面试中,面试官通常会考察候选人的架构设计能力、问题解决技巧以及对大规模分布式系统的理解。这个名为"system-design,准备系统设计面试问题.zip"的压缩包可能包含了一个开源项目,该项目旨在帮助面试者...
在IT行业中,大型分布式网站架构设计与实践是构建高可用、高性能、可扩展的互联网服务的核心技术。这一领域涵盖了诸多关键知识点,包括负载均衡、数据存储、服务治理、容错机制、性能优化等多个方面。以下将对这些...
10. **微服务架构**:近年来流行的微服务架构将大型应用拆分为一组小型、独立的服务,每个服务都在自己的进程中运行,通过API通信,增强了系统的可扩展性和可维护性。 这个课件可能涵盖了以上这些主题,并通过实例...
总的来说,Zookeeper是一个在分布式系统领域具有广泛应用的协调中间件,它在大数据处理、云服务、分布式计算等场景中发挥着至关重要的作用。通过其提供的数据模型和操作接口,开发者可以较为容易地构建出稳定可靠的...
本笔记将深入解析阿里巴巴开源的分布式核心技术,帮助读者理解分布式系统的运作原理及其在实际应用中的价值。 首先,我们要了解分布式系统的基本概念。分布式系统是由多台独立的计算机通过网络连接,协同工作以完成...