• Feeds

  • Archive for the ‘分布式’ Category


    分布式服务框架的4项特性

    在移动及云时代,尽管大部分可扩展的问题可以通过云平台解决,但是服务本身的扩展性挑战仍然存在。比如一个新的项目,用PHP或JSP实现了基本功能,部署在Apache或Tomcat等容器上,在业界这种部署在一个容器内的功能模块通常可以称为一个service。服务容器很容易通过EC2或者docker等方式来扩展部署更多的实例。但service本身的管理的以下几个方面的问题仍然需要架构师去设计及解决。

    1、服务的远程调用(RPC)。

    随着系统的用户访问规模增大,以及系统功能的增多,众多的功能模块(service)很难用单个service来承载,这些不同功能的service可能由不同的开发团队开发,甚至使用不同的开发语言,最终部署在不同的服务器容器内。Service之间的调用需要一种协议及远程调用的实现,需要具备灵活的data type支持,对调用双方透明(理想情况它就像在执行本地调用),并且具有良好的性能。比较典型的RPC实现有
    Google: Protocol Buffers RPC
    Facebook: Thrift
    Twitter: Finagle

    2、服务的分布式调用链及服务状态跟踪统计

    随着系统内部的服务增多,一个功能的调用可能会通过系统内部多个服务相互调用来完成,并且这些服务可能由不同的团队开发,并且分布在不同的服务器容器,甚至可能在多个地域不同的机房内。因此分布式系统需要有一种方式来清晰的了解系统的调用及运行状况,测量系统的运行性能,方便准确的指导系统的优化及改进。

    由于trace的主要功能都是依赖日志输出来完成,因此通常也需要建设相关的分布式日志系统及数据实时分析展示系统等,分布式日志收集及数据实时分析也是一个非常大的话题,本文不展开详谈。比较典型的trace系统有
    Google: Dapper
    Twitter: zipkin

    3、服务的配置管理。包括服务发现、负载均衡及服务依赖管理。

    比较常用的服务发现是域名方式,调用方通过域名来定位目标服务。域名寻址方式可通过配置多IP(或VIP)来实现负载均衡。域名方式存在一些弊端,常用的DNS服务器通常是上个世纪的产物,管理繁琐,更新域名记录后由于协议设计上存在的TTL缓存机制,修改不能立即生效,也无法做变更的push操作。更高级的特性如控制流量、灰度发布等也无法实现。

    目前,成熟的分布式服务较多使用基于ZooKeepr的配置服务,ZooKeeper由于与client保持长连,因此具有push能力,可以迅速的调整配置及生效。但由于ZooKeeper本身只是一个通用工具,分布式服务具体场景各种高级特性还需要自行在此基础上实现。

    基于DNS的服务发现在负载均衡方面具有明显缺点,由于多IP或VIP使用类似round robin的策略,在实践中,同一服务的多个IP之间负载通常并不均衡。而服务提供方并没有有效手段对runtime期间不均衡进行调整。基于ZooKeeper的配置服务可以支持各种复杂的特性,但需要做一些定制化开发,但服务发现作为系统中最核心的一个环节,这些定制化开发需要较多的经验的积累及沉淀,之前在线上就碰到过配置服务将一个服务池中疑似不稳定的节点移除过多,从而导致出现雪崩的情况。

    除了ZooKeeper之外,业界还有一些类似工具,如serfdomconsui

    4、服务之间的调度及生命周期管理

    目前大部分服务的部署都是按照事先的规划安装在机房不同的服务器上,配置服务通常只是起服务节点的failover作用,业务中真正按弹性调度来运作的系统还不普遍。但原理上所有的service可以看做是MapReduce中的task,它的调度及生命周期可以很高效的由分布式容器来管理,并且根据service的属性来灵活的分配资源,比如控制CPU的核及内存大小。

    业界比较成熟的有Apache旗下的MesosYARN。它们的特性有点类似,但是由不同的组织开发。Mesos主要功能是由C++来实现,可以支持docker container来进行调度,因此它的实现更偏底层一些。Yarn是Hadoop 2的一部分,可以更灵活的来调度MapReduce jobs,它是一种JVM内部的实现,可以很好的支持JVM级别的任务分配及调度。

    上面介绍了这么多,主要是最近考虑团队在上述1-4之间做一些事情。一方面目前业界在这几点之间还有一些缺失或者欠优化之处,另外1-4点之间也可以适当做一些实现的整合。整合并不是要产出一个大而庞杂的软件,我个人是极力反对大而全,也不喜欢沉重的框架,业务的service实现方不应该import太多工具或者SDK,因此将要做的功能肯定是透明及可插拔的。

    由于这件事情并没有严格的可参考目标,因此对于最终实现的是哪个子集还存在一些不确定因素,这个项目如果具有通用性,也考虑以开源的方式来开发。对这方面有什么想法,欢迎留言。

    多IDC的数据分布设计(一)

    上个月跟某个朋友谈及多IDC数据同时读写访问的问题(tweet),当时觉得有不少解决方案,但觉得思路还不够清晰。最近看了Google App Engine工程师Ryan Barrett介绍GAE后端数据服务的演讲稿Transactions Across Datacenters(视频),用Ryan的方法来分析这个问题后就豁然开朗。

    按Ryan的方法,多IDC实现有以下几种思路。

    一、Master/slave

    这个是多机房数据访问最常用的方案,一般的需求用此方案即可。因此大家也经常提到“premature optimization is the root of all evil”。
    优点:利用mysql replication即可实现,成熟稳定。
    缺点:写操作存在单点故障,master坏掉之后slave不能写。另外slave的延迟也是个困扰人的小问题。

    二、Multi-master

    Multi-master指一个系统存在多个master, 每个master都具有read-write能力,需根据时间戳或业务逻辑合并版本。比如分布式版本管理系统git可以理解成multi-master模式。具备最终一致性。多版本数据修改可以借鉴Dynamo的vector clock等方法。

    优点:解决了单点故障。
    缺点:不易实现一致性,合并版本的逻辑复杂。

    三、Two-phase commit(2PC)

    Two-phase commit是一个比较简单的一致性算法。由于一致性算法通常用神话(如Paxos的The Part-Time Parliament论文)来比喻容易理解,下面也举个类似神话的例子。

    某班要组织一个同学聚会,前提条件是所有参与者同意则活动举行,任意一人拒绝则活动取消。用2PC算法来执行过程如下

    Phase 1

    Prepare: 组织者(coordinator)打电话给所有参与者(participant) ,同时告知参与者列表。
    Proposal: 提出周六2pm-5pm举办活动。
    Vote: participant需vote结果给coordinator:accept or reject。
    Block: 如果accept, participant锁住周六2pm-5pm的时间,不再接受其他请求。

    Phase 2

    Commit: 如果所有参与者都同意,组织者coodinator通知所有参与者commit, 否则通知abort,participant解除锁定。

    Failure 典型失败情况分析

    Participant failure:
    任一参与者无响应,coordinator直接执行abort
    Coordinator failure:
    Takeover: 如果participant一段时间没收到cooridnator确认(commit/abort),则认为coordinator不在了。这时候可自动成为Coordinator备份(watchdog)
    Query: watchdog根据phase 1接收的participant列表发起query
    Vote: 所有participant回复vote结果给watchdog, accept or reject
    Commit: 如果所有都同意,则commit, 否则abort。

    优点:实现简单。
    缺点:所有参与者需要阻塞(block),throughput低;无容错机制,一节点失败则整个事务失败。

    四、Three-phase commit (3PC)

    Three-phase commit是一个2PC的改进版。2PC有一些很明显的缺点,比如在coordinator做出commit决策并开始发送commit之后,某个participant突然crash,这时候没法abort transaction, 这时候集群内实际上就存在不一致的情况,crash恢复后的节点跟其他节点数据是不同的。因此3PC将2PC的commit的过程1分为2,分成preCommit及commit, 如图。

    (图片来源:http://en.wikipedia.org/wiki/File:Three-phase_commit_diagram.png)

    从图来看,cohorts(participant)收到preCommit之后,如果没收到commit, 默认也执行commit, 即图上的timeout cause commit。

    如果coodinator发送了一半preCommit crash, watchdog接管之后通过query, 如果有任一节点收到commit, 或者全部节点收到preCommit, 则可继续commit, 否则abort。

    优点:允许发生单点故障后继续达成一致。
    缺点:网络分离问题,比如preCommit消息发送后突然两个机房断开,这时候coodinator所在机房会abort, 另外剩余replicas机房会commit。

    五、Paxos

    Google Chubby的作者Mike Burrows说过, “there is only one consensus protocol, and that’s Paxos” – all other approaches are just broken versions of Paxos. 意即“世上只有一种一致性算法,那就是Paxos”,所有其他一致性算法都是Paxos算法的不完整版。相比2PC/3PC, Paxos算法的改进

    • P1a. 每次Paxos实例执行都分配一个编号,编号需要递增,每个replica不接受比当前最大编号小的提案
    • P2. 一旦一个 value v 被replica通过,那么之后任何再批准的 value 必须是 v,即没有拜占庭将军(Byzantine)问题。拿上面请客的比喻来说,就是一个参与者一旦accept周六2pm-5pm的proposal, 就不能改变主意。以后不管谁来问都是accept这个value。
    • 一个proposal只需要多数派同意即可通过。因此比2PC/3PC更灵活,在一个2f+1个节点的集群中,允许有f个节点不可用。

    另外Paxos还有很多约束的细节,特别是Google的chubby从工程实现的角度将Paxos的细节补充得非常完整。比如如何避免Byzantine问题,由于节点的持久存储可能会发生故障,Byzantine问题会导致Paxos算法P2约束失效。

    以上几种方式原理比较如下

    (图片来源:http://snarfed.org/space/transactions_across_datacenters_io.html)

    后文会继续比较实践环境选取何种策略合适。

    (PS: 写完后在Google Reader上发现本文跟王建硕最近发表的《关于两个机房的讨论》文章有点类似,特别是本文一、二方式。不过他的文章偏MySQL的实现,我的重点是一致性算法,大家可以有选择性的阅读。)

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

    在分布式算法领域,有个非常重要的算法叫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)