摘要:GFS单Master架构大幅简化分布式文件系统,但Master成为单点,Hadoop中HDFS同样受制于此。XFS提供Master主备机制去掉单点,包含基于流水线和预测的两阶段提交的Replication;failover完成主备切换;learning完成自动恢复。XFS Master 1主2备下5.58万的峰值写qps,几百毫秒的failover和learning,支持Rolling Update,自2011年4月起部署在全部超过10个机群。
1XFS Master主备机制导论
1.1  主备机制源起:why?
    Google的GFS系统的单Master架构大大简化了分布式文件系统的设计与实现,Master存储整个机群的目录树等元信息,并提供全局调度等功能。但这使得Master成为了单点:一旦Master宕机,整个GFS机群将不可用。Hadoop中HDFS沿袭了GFS的设计,其NameNode也设计为单点。
    XFS是台风(Typhoon)云计算平台中的分布式文件系统。XFS架构中, Master是元信息管理的唯一持久存储,提供整个机群的目录树管理和节点分配等功能,是整个XFS机群最关键的单点,是XFS可靠性和可用性的瓶颈。
    因此,我们希望设计一套主备机制,维持Master的多个副本,以便出错时切换到备用Master,持续提供服务,提高XFS整系统的可靠性和可用性。
1.2      设计目标
    XFS Master的主备机制期望达到下述目标:提高数据可靠性,提升Master的可用性,支持错误节点的自动恢复和运行时增加Master节点,并提供较高的性能。
    上述目标完成后,Master可以支持Rolling Update,在不停服务的情况下升级Master。
1.3      挑战
    完成一套主备机制并不容易,实际是设计与实现一套分布式协议,面临下述挑战:
1)         XFS Master功能多导致协议复杂。XFS的Master除了存储文件目录树结构,还集成节点分配,接收上报的NodeServer信息,负责文件的MetaServer分配,支撑MetaServer的数据收集,更新用户Quota设置等。功能的复杂导致主备切换时需要切换的状态增加。
2)         XFS Master没有可依赖的持久存储。主备机制中,如果能将持久状态可靠的存储在分布式文件系统中,使得服务器程序只维持非持久的状态,则主备切换时只需选举主节点读取持久状态,即可完成主要工作。然而很不幸,XFS master正是分布式文件系统的关键部件,必须不依赖于分布式文件系统实现数据的可靠存储。这迫使Master采用两阶段提交协议。
3)         兼顾正确性和性能增加了协议的复杂性。Master是XFS的单点,主备机制不可避免会导致Master性能下降,因此除了保证协议正确,还需优化协议性能,并采用全异步的实现。
4)         难以测试。主备机制本身就是应对各种出错情况,包括磁盘、网络、操作系统故障、程序bug等,这些错误即使压测也难以出现,如何测试需要仔细考虑。
2          主备机制概览
    XFS master的主备机制是让多份master进程以不同角色运行,提供软件层的备份和容错,以便可靠地提供服务,同时保障Master完成rolling update。Master启动过程为INIT身份,启动完成后可能以主(Primary)、备(Secondary)、Newbie的身份运行。主备机制需要依赖于一套分布式选举协议,用于选举主Master,并存储一致的主备视图(ReplicaView)。
    XFS Master的所有操作可以划分成写和读两类操作,写操作会更改Master持久存储的状态数据,而读操作只获取数据,不改变状态。
    XFS Master的主备机制作为XFS Master的功能入口,细分为Replication协议、Failover协议和Learning协议。其中Replication协议形成Hot standby,Failover协议完成failure handling,Learning协议完成failure recovery。
    Replication协议对所有的写操作(Mutation)执行两阶段提交协议。Replication的写操作由Master发起,确保数据持久写入主和足够的备才报告用户成功,以提高Master可靠性。读操作由主Master完成,以确保强一致性语义:已报告用户成功的数据一定可以读取。
    Failover协议在主Master出错时,选举新的主Master,完成服务的平滑迁移,增强Master容错能力。事实上,Failover协议需要完成Master的主、备、Newbie、Init等角色之间的全部转换流程。
    Learning协议负责将新加入的或者滞后的Newbie Master对齐到与主Master同步的状态,以不停服务下的自动完成新加Master或者修复出错的Master。
    下图概述了XFS Master主备机制。

3          Replication协议:Hot standby
    Replicaition协议保证系统有主和多个备,备成为Hot standby,提高系统可靠性。
3.1      一致性语义
XFS Master的数据一致性的定义如下:
1)         写数据返回给用户成功,则一定成功,该客户端马上能读到新的数据。
2)         因果关系一致性:一个客户端A写成功后,通知另外一个客户端B,然后B肯定能读到新的数据。
3)         写数据返回用户失败,数据不一定失败。有可能数据已经写入,只是response丢了而已。这条记录进入un-defined的状态,即客户端可能会读到老的或者新的数据。
3.2      通用两阶段提交协议概述
两阶段提交协议中,每个Mutation都会经历两个状态:prepare和commit。Master把mutation持久地写入log的时候,算是准备好了(prepared)。当主和备都准备好后,才进入commit状态,向用户返回成功。一个已经prepare但还没有commit的mutation是可以被回滚的(是否回滚取决于系统策略)。
Wikipedia对两阶段提交协议(two-phase commit protocol, 2PC)的描述如下:
http://en.wikipedia.org/wiki/Two-phase_commit_protocol
1)         包含一个coordinator,若干个cohorts。
2)         假设:每个节点都有可靠永久存储。事实上,存储可能不那么可靠,比如硬盘可能会坏,文件可能丢失或坏掉,误操作可能会格式化机器。
3)         假设:任意两个节点之间都可以通信。也许交换机故障导致网络partition,也许有一个节点坏了,运维修复耗时1天。
Prepare阶段
1)         Coordinator把prepare mutation发送给所有的cohorts。
2)         每一个cohort把mutation写入自己的log,算是prepare好了。
3)         Cohort给coordinator发送agree响应。
Commit阶段:成功
1)         如果Coordinator收到所有的cohort的agree响应,则成功,开始做commit。
2)         Coordinator给所有cohort发送commit消息。
3)         Cohort收到消息后做commit,并且发回响应。
4)         Coordinator结束这次transaction。

Commit阶段:失败
1)         如果coordinator没有收到所有的cohort的agree响应,则失败,开始做rollback。
2)         Coordinator给cohort发送rollback消息。
3)         Cohort rollback其commit log,并发送回应。
4)         Coordinator结束这次transaction。

3.3      XFS Master的两阶段提交协议实现
3.3.1   写操作定序
    两阶段提交协议的前提是对来自不同客户端的写请求(mutation)进行全局定序。主Master提供一个队列用于接收用户请求,对用户请求确定先后顺序。主Master在内存中维护最新的prepare和commit的sequence id (SN),同时保证prepare sn和commit sn持久存储。并通过failover协议保证即使主备切换,也维持commit sn的单调连续增长,并保证prepare sn反应全局的最新commit或者rollback状态。当处理队列请求时,以当前的全局prepare SN为请求定序。
对所有写操作定序后,主Master按两阶段提交协议广播请求,使得主备按同样的顺序执行所有写操作,这是获得强一致性的基础。
3.3.2   正常流程的两阶段提交协议
    正常情况下,XFS Master用两阶段提交协议完成热备份。这里正常情况是指:
1)         没有机器被重起
2)         没有服务被重起
3)         写硬盘都成功
4)         网络通信正常(重试次数之内能连上)
5)         服务器与ZooKeeper之间的心跳正常

    正常情况下,写操作流程如下:
1)       主收到一个mutation时,把当前的prepare sn作为这个mutation的sn,写入log。
2)       主向replica view里面的备发送mutation,备收到后也把它当做prepare写入log。
3)       备回应给主,说已经准备好了。
4)       当所有备都准备好的时候,主将这个mutation标记为commit(把主的commit sn增长到这个mutation的sn),执行这个mutation以更新内存数据结构,然后给用户返回写成功。
3.3.3   出错回滚
    如果某一个备没有回应准备好,主会重试。重试若干次以后,主将这个备踢出replica view,踢出的过程在Failover协议中介绍。
    如果主踢掉某个备后,replica view中的备数目足够(默认配置大于等于1),并且这些备已经返回prepare信息,就给用户返回写操作成功。
    当replica view里面备的数目不足时(少于1个),当前mutation失败,并且回滚这个mutation。由于这个mutation只写了log,还没有被应用到内存数据结构中,它是可以被回滚的。
    回滚log时,主给下一条mutation分配与上一条mutation一样的序列号,以后读log的时候遇到相同序列号的,忽略老mutation。
3.3.4   日志读取时的出错回滚
    Master重启或者Learning时,需要从log中重建内存数据结构,这时需要处理log的回滚。

    已经commit的mutation不会被回滚,而prepare的mutation可能会被回滚。读log的时候需要保留一个缓冲区,记录当前读到的已经prepare还没有commit的log。如果读到一个mutation,它的序列号与缓冲区中某条记录一致,用新的mutation覆盖老的,即完成回滚。
3.4      协议优化
3.4.1   批量执行
    XFS Master实际是分批执行两阶段提交协议,即流程中的每一条mutation实际是一批mutation,由此大幅减少广播和写磁盘的次数。
3.4.2   Commit消息与下一次的Prepare请求合并
    主并不单独发送一个commit的消息给备,而是把commit的消息附在下一条prepare mutation一起发。主/备写log的时候,一条RecordIO也包含两个内容:prepare新的mutation和commit老的mutation,这样可以节省网络包数量和flush硬盘的次数。
3.4.3   默认Commit策略
    对于已经Prepare但没有commit的写操作,在failover时,Master采用默认commit策略。这个策略能减少协议交互,其副作用是强化了“返回用户失败,但实际不一定失败”。
3.4.4   日志出错检查
    Master的log是通过RecordIO读写,而RecordIO对单条记录有容错功能。怎么保证log数据不损坏或者丢失呢?RecordIO读数据的时候,检查SkippedBytes为0。并在每个记录加上record id,record id必须连续,防止RecordIO有skip掉整块记录。
3.5 流水线和预测执行
    Replication协议将多批请求流水线方式并发执行,其实现基于SEDA(Staged Event-Driven Architecture)[3] 模型。主、备master均分多个阶段,各阶段作为异步任务,统一由后台线程池执行。同一批请求的多个阶段串行执行,多批请求并发执行。阶段间通过queue作为执行速率的同步点,当queue满或者queue空时,相应的阶段暂停或重启。
    两阶段提交协议的后一批请求是依赖于前一批的执行结果的,因此各批请求实际是预测执行,基于前一批的“预测”结果执行后续请求。
    分阶段执行大幅提升了性能,但正确性挑战也增加。Master通过保证处理顺序和完成顺序确保正确性。
3.6      文件列表管理
    XFS Master中当mutation累积到一定数量时,会切分出不同的磁盘MutationLog文件,以控制单个MutationLog文件的大小,便于维护,也利于Learning。同时,Checkpoint将前一次的Checkpoint和当前全部mutation合并成一个更新的Checkpoint文件,并加载新的Checkpoint文件到内存中提供服务。通过Checkpoint动作,对Master内部数据进行压缩,减小内存消耗,并提高Master启动速度。
    XFS Master提供文件列表管理模块,以管理由此产生的多个MutationLog文件和Checkpoint文件。文件列表管理会记录当前活动的和历史以来的各个Checkpoint和MutationLog文件的对应关系,文件的起始SN等信息,并实际管理文件的创建和删除。文件列表本身采用先写临时文件再rename的方式保证数据完整。文件列表管理方便检查磁盘文件可能的错误,并对实现Learning协议提供了较好的支持。
    当XFS机群存储超过2亿文件时,Master对应的Checkpoint文件已经超过15GB。此时,文件放置和删除策略就需要更仔细考虑。XFS Master支持文件划分磁盘存储、按文件类型设定过期时间等。
3.7      错误处理
    在两阶段提交协议的任何一个步骤都可能发生各种错误,比如线程等锁导致延迟,网络忙,磁盘错误,节点出错或者网络Partition等,此时应该如何处理?Master的基本策略是步骤内的错误延迟重试以恢复偶然性错误,在设定时间内无法恢复时启动failover协议,完成Master角色转换。
4          Failover协议:failure handling
    Failover协议处理各种设定时间内不可恢复的错误时的Master角色转换。
4.1      ReplicaView管理
    Master将参与主备机制的各个Master的地址和角色持久的记录在Zookeeper上,称为ReplicaView。ReplicaView管理负责实施Master在ZooKeeper上的角色转换,并形成一份cache,避免对Zookeeper的频繁访问,同时通过version保障内存中cache的数据在不是最新时能检测出来。区分出ReplicaView的管理和Mutation的管理,可以简化协议实现。
4.2      主选举:分布式锁
    各个备Master周期性的从Zookeeper抢锁,直到抢锁成功或者进入错误状态。同时通过Zookeeper的Watcher,监听ReplicaView的状态改变,获得Master节点掉线、加入等事件通知。
    抢锁成功则暂停此抢锁任务,并启动升级任务。升级后,主Master一直持有住锁,直到出现其掉线等异常。备抢锁时如果遇到Zookeeper初始化失败,或者连接异常(SessionExpire)等,会避免进入 failover流程,而保持为备的状态继续重试抢锁。这样避免出现过多的降级为Newbie,影响系统可用性。
    思考:如果不用锁,能否有其它方案完成主选举?应对网络partition时可用性是否更高?
4.3      主备切换:主丢锁时,备抢锁成功,升级成主
    当主丢锁时,两个备的prepare数据可能不一致。有可能抢到锁的备比另一个备少一个(或者一批)prepare的mutation。这样,当写入下一条数据的时候,把上一条数据回滚了,这个没关系,因为这条数据我们没有返回用户成功。
    备一旦抢锁成功,会进入升级流程,其主要步骤包括:
1)         暂停抢锁,持有锁。这样保证只有当前master在升级,并减少无谓的抢锁动作。
2)         进入升级状态。其标志是创建UpgradeToPrimaryTask,并设置相应的指针作为标志位,如果有正在执行的UpgradeToPrimaryTask,则忽略。一旦进入升级状态,备不再接收主广播过来的mutations。
3)         等待启动机会。如果当前没有正在进行或者pending的需要备处理的广播请求,可以立即启动。如果已经有,则升级任务暂不启动,而是拒绝任何新的广播请求,等待当前正在运行的广播任务结束,在其结束的callback动作中返回错误,并将队列中所有等待的备广播任务终止并返回错误码,然后再启动升级流程。
4)         更新内部角色。首先修改master内部的角色为PRIMARY。修改前,确认角色不是NEWBIE等。如果是,则是UpgradeToPrimaryTask运行期间主遇到致命错误,需放弃升级。
5)         更新Zookeeper上的主备信息,并确认拥有最新数据。更新前,必须校验Zookeeper上可能的状态,确保是允许的组合,其中最重要的是验证当前抢到锁的Master必须是Zookeeper上的主或者备的身份,以保证当前Master是拥有最新数据的。更新动作会在一个原子操作中将ReplicaView中原来的主改为为备,并把自己设置为主,并确保设置期间自己拥有ReplicaView的最新数据。升级中,新任主根据ReplicaView的version值,确认自己拥有最新ReplicaView数据,以便用ReplicaView的version和commit SN共同作为mutation的唯一标识。
6)         允许新请求。一旦更新主备信息,新的写请求就可能到达升级状态的主。此时,主可以接收请求,但buffer在queue中,只要升级任务不结束,就暂不处理请求。
7)         广播备的最后一批Prepared的请求。由于两阶段提交协议中采用默认commit策略,此时备中prepared的请求可能已经被前任主返回给用户成功,因此备必须将最后一批Prepared的请求执行commit。此时的广播会形成一次完整的两阶段提交协议。广播时,注意前任主可能也作为备收到广播请求(主可能降级为备),而前任主的降级也是一个复杂的过程,因此,适当的重试能提高广播的成功率。如果广播时有备失败,则从Zookeepr删除备,如果删除备失败,则新的主需降级为备。
8)         新的主Apply Mutations。只要新的主自身没有遇到致命错误导致降级,则无论广播是否成功,都Apply Mutations,以实现“默认commit”。如果广播失败,则说明成功的备数量不够,新的主保持主的身份,但不能提供写服务。注意Apply Mutations之前,不能提供服务,读和写都不行,因为此时用户可能读不到最新的一批数据,而这批数据用户可能已经收到成功状态。新的主在Apply时,需要保证commit SN等重要资源单调增长而不回退。对于类似fileid,由于其中有编码时间戳信息,升级时必须避免时间回退导致的全局的最大fileid回退。
9)         切换内存状态和各项任务,支持从备到主。主备的内存状态有不同。比如备的内存中存储了上一批prepare的数据,在Apply完成后准备成为主时,需要清空相应内存。任务方面,比如主会周期性的获取用户Quota等信息,并产生mutation广播到备。
10)     触发scheduler和MetaServer前来新的主注册。Master中存储了scheduler上报的全部NodeServer,以及全部MetaServer的分组信息,这是提供读写服务的前提。
11)     完成升级流程,准备服务。如果此前成功,且备的数量足够,则提供服务,开始处理buffer住的请求,提供服务。如果广播失败,则保持主的身份,但不能提供写服务。如果有其它致命错误,则放弃,开始降级。
12)     XFS的其他模块出错时delay重试,并通过Zookeeper中的ReplicaView获知新的主,将请求转发到新的主,保证基于XFS SDK开发的应用无缝切换。前任主丢锁后,会对SDK、MetaServer、Scheduler等模块的请求返回对应错误码,使得各个模块知道有发生主备切换,主动获得新的主。
    事实上,备升级过程中,如果有任何新的错误发生,都可能终止升级流程,重新进入降级流程。而XFS其他各个模块对Master主备切换时的重试等策略,才使得Master的主备切换得以产生效果。
4.4      主备切换:主丢锁,降级为备
    主如果丢锁,则必须降级为备,停止服务,以防止网络Partition等造成两个主同时提供服务,导致丢失用户数据。
    主丢锁时,主启动降级为备的流程。同时各个备都会收到LockReleased事件,均立刻尝试抢锁。如果主和zookeeper心跳超时,则主知道已经丢锁。
    思考:如果主丢锁,但不知道已经丢锁,而继续提供服务,而同时备抢到锁开始服务,岂不是有两个主在提供服务了?
    回答:Zookeeper协议保证不会出现这种情况(基础架构部改进的协议对这方面有新的增强)。ZooKeeper客户端通过心跳保持和ZooKeeper服务端的连接,在失去联系时,Zookeeper客户端丢锁。Zookeeper会保证在客户端丢锁前,其它进程无法抢到锁。
    思考:能否主直接降级为Newbie?为什么这里仅仅降级为备?
4.5      主/备降级成Newbie
    主和备遇到致命错误时(比如磁盘错误),会主动降级为Newbie。
    如果备掉线,主在超时时间内无法广播到备,也会将备踢出ReplicaView。另外,主发现备的数据不是最新时,会将备踢出ReplicaView。随后,备会检测到自己在ReplicaView已经是Newbie的状态,于是主动降级为Newbie。
    主备降级为Newbie时需要注意的问题是DegradeToNewbie任务属于高优先级任务,会终止其他任务。事实上,所有任务均有优先级关系,互相决定是否能取消。
    如果磁盘类型错误导致,在进行一系列退出逻辑后,Master会core掉,等待监控拉起,或者人工介入。而对于非磁盘类错误,则会保持在Newbie的身份,避免core掉,以便尽快Learning成备。
4.6      重启
    Master初始化的时候,如果从ZooKeeper的ReplicaView中读到自己是主或备,说明它的Checkpoint+MutationLog是最新的数据,这时候它可以重建好内存数据结构后直接当备。备会开始去抢锁,如果抢到锁,它就开始当主。
    如果这个Master没有最新的数据,那么只能按Newbie方式启动,之后向主Learning。
4.7      Newbie自杀
    当全部Master均遇到致命错误变为Newbie时,系统将没有主供Newbie学习,从而无法产生主,系统永远无法恢复为可服务状态。此时,最后一个变成Newbie的Master试图自杀,并以备的身份重启,此时其在Zookeeper上的ReplicaView必然是主或者备的身份,意味着其拥有最新数据(思考:为什么?)。因此,这个Newbie将能抢锁成功,升级为主,并将另外两个Newbie学习成备,使得系统重新进入可用状态。
    思考:能否增加Newbie变成备的逻辑,而非Newbie自杀?
5          Learning协议:failure recovery
    Failover协议中主备出错时,可能成为Newbie。主备广播将忽略Newbie,使得Newbie的数据更加滞后。因此,当出现Newbie时,系统进入一个比较危险的状态:可用的Master减少。所以,我们设计Learning协议,让Newbie自动从主Master学习到最新的数据,追赶成为备,使Newbie从此前的错误中自动恢复。
    Learning协议也使运行时增加新的Master节点成为可能。新加的Master以Newbie身份运行,向主Master学习到最新的数据,成为备开始服务。
    Learning协议也支撑Master的Rolling Update。当升级某个Master时,剩余的Master继续服务,已经产生不少新数据。新Master必须通过Learning才能获得最新数据,加入主备服务的行列。
5.1      Learning协议概述
    Learning协议的主要流程为:
1)         主Master选择Newbie,启动learning,这个Newbie成为当前的学习者(learner)。
2)         Learner把它最新数据的序列号发给主,如果一点数据都没有就发0。
3)         主根据当前相差数据的大小选择发送数据的策略。如果差得很多,就先发送Checkpoint文件,如果快赶上了,就发送MutationLog文件。
4)         Learner从主下载Checkpoint或者MutationLog文件,并从磁盘加载Checkpoint文件到内存,并Reply日志。
5)         当只差少量数据的时候,主进入同步对齐(sync_log)阶段:此时,需要暂时停止写请求,等待学习者追上后,把它加入ReplicaView,再开始处理写请求。这时候新的写请求就必须保证也写入新学成的备了。
    Learning协议中,主Master中运行LearningServer,通过RPC Streaming提供文件下载,完成Learning同步对齐。Newbie开始学习时,启动一个LearningTask,与LearningServer间建立一个学习的session,完成学习过程。
    LearningServer作为一个被动的状态机运行,主要通过Newbie发送的获取最新Checkpoint/MutationLog文件列表的请求驱动。同时,为了检测Newbie错误或者学习速度太慢,会启动异步Task周期性检查Learner状态,并在同步对齐阶段启动定时器,以终止太慢的学习者。由此,Learner请求、各类出错、超时事件,以及修改Zookeeper的callback等,也成为LearningServer的状态驱动源。下图概述了LearningServer的状态转换。

5.2      Newbie的初始化和注册
    Master启动时,首先确认自己在Zookeeper上配置的machine list中,否则core掉。所有Master启动时均指定secondary身份,master根据读到的ReplicaView中的身份决定启动时的真正角色。如果则ReplicaView中为Newbie,则按Newbie启动,并向主注册。
    Newbie启动RegisterTask,持续尝试注册。如果主出错时,newbie无法连上主,则需要持续重试连接zookeeper读取的新的主,并向新的主发送注册请求。主收到Newbie的注册请求时,将其加入内部的Newbie列表,并记录其最新的SN,统计其出错次数等信息。
5.3      Learning启动
    主周期性检测,看是否有Newbie,并尝试启动Learning,因为Learning是高优先级任务。Learning过程由主发起,以利于从全局观点挑选比较合适的学习者。目前的策略是挑选相差数据少并且出错次数少的Learner。为简单,主在任意时刻只启动一个Newbie进行学习。
    主挑选Newbie启动学习时,会主动发起START命令。后续可能发出STATUS命令检查Newbie状态,以便检查已经出错的学习者。主期望提前终止学习过程时,会发出CANCEL命令。
5.4      文件传输阶段:Learning的“断点续传”
    文件传输阶段中,Newbie的主要逻辑是:
1)         Newbie的LearningTask通过发送自己的commit sn到主,获取到文件列表。
2)         Newbie的LearningTask启动文件下载过程,通过streaming rpc同步远程文件到本地。
3)         Newbie文件同步后,本地读取日志并apply。
4)         将learning回来的文件加到文件列表管理。
5)         Newbie的LearningTask发现主返回的文件标识为最后一个文件,则文件传输阶段结束。
    此时,Primary通过RPC streaming被动响应,发送Newbie所缺的文件。发送中,主不做传输速率控制,因为Learning是非常紧急的操作,有learning时可降低线上请求的QPS。
    由于文件传输阶段可能是一个漫长的过程,因此,Learning中通过学习过程的“断点续传”,减少出错导致的损失。体现在:
6)         多个文件的可续传。Learning中需要传输的文件可能较多。LearingTask通过逐个文件下载并Apply,之后再获取下个文件的方式,可以在重新启动学习过程时,从此前的SN继续学习,避免重复传输已成功的文件。
7)         单个文件的断点续传。当Checkpoint文件到15GB,30GB时,单个文件传输出错的概率增加。LearningTask在RPC Streaming之上记录传输进度,并对单个文件支持断点续传。
5.5      同步对齐阶段
    同步对齐是Learning中最需要仔细考虑的一个阶段。
1)         Primary发现除了当前mutation log外的其余文件都已经传输完成时,如果此文件的mutation数量不到1万条了,则准备进入同步对齐阶段。如果超过1万条,则新切一个mutation log文件,等待Newbie传输、写、并apply这个文件的内容。主重复新切最后一个文件最多3次后,准备进入同步对齐状态。(思考:切3次文件能降低到多小?)
2)         进入同步状态,需要执行下述动作:
a)         主等待,服务完当前一批线上写请求后,暂停服务,进入对齐阶段
b)         返回此文件,并标志为最后一个文件
c)         启动计时器等待学习者完成。
3)         Newbie收到最后一个文件,下载,写磁盘,读数据,apply。此时Newbie已经有最新一批请求处于prepare状态,之前的请求都已经commit。Newbie再获取一次文件列表,传入当前commit sn和prepare sn。
4)         Primary在同步对齐阶段收到Newbie最后一次请求时,如果确认Prepare SN和commit SN均已经追上,即知道Newbie学习完成了。此时,在当前请求返回空文件,标识Primary已经知道newbie学习完成。
5)         Newbie收到返回空文件列表,即修改自己角色为secondary,并启动UpgradeToSecondary任务,其中执行修改抢锁线程等系列流程。
6)         Primary返回空文件响应后,不等待Newbie,即开始进入SYNC_NEWBIE_READY状态,开始将当前Newbie加入Zookeeper中的ReplicaView。
7)         成功添加Newbie到ReplicaView后,主退出同步状态,开始正常服务。
    这个阶段的复杂性在于上述每步都可能出错,概述中LearningServer状态转换图给出了部分错误的处理。
    思考:有没有不需停止写服务的对齐方法?
5.6      出错处理
    为简化错误处理,Learning中Newbie和主的错误都会导致结束当前学习的Session,由于Learning具有的“断点续传”特性,结束的代价可以接受。
    Newbie出错:Newbie遇到错误会主动结束当前LearningTask。Primary启动学习任务后,即启动检测任务,如果Newbie已终止Learning,或者无响应,或者学习速度太慢,则Primary主动结束当前Learning Session。
      Primary出错:Newbie向主获取文件列表时,或者下载文件时,如果发现主无响应,则主动结束当前Learning任务,并立即启动RegisterTask向新升级的主注册,等待新升级的主发起新的一轮学习过程。
6          经验和教训
6.1      错误处理策略:宁愿core,不能错;能恢复,不愿core
    主备协议的设计与实现中难免有bug。出现bug时Master的策略是core掉,可以避免错误扩散,并有监控程序自动拉起,可修复大部分随机错误,使系统再次恢复可用。
    对于可能恢复的外部错误,比如Zookeeper出错或者网络partition,Master则尽最大努力恢复错误,或者切换到Newbie状态,避免简单粗暴的直接core掉。一个例子是主丢锁时引入DegradeToSecondary等细化角色转换,而非core掉。这是因为Master core的成本非常高,在5亿文件时,内存占用会达到约30GB,core一次的代价高昂,重启耗时也是超过10~20分钟的量级,造成系统较长时间处于危险期。
6.2      异步状态机
    Master内部各个协议或者任务均是显式或者隐式的状态机实现。LearningServer的状态转换就是一个状态机的例子,通过状态机利于分析复杂交互过程。状态机均是事件驱动,异步实现避免等待阻塞线程,共用网络线程和后台线程池,减少系统线程数。唯一的缺点是增加了实现复杂性。
6.3      应对运维误操作
    运维误操作属于拜占庭错误,行为不可预测。协议设计主流程中不考虑误操作问题,但有考虑一些常见的误操作类型,提供针对性处理。比如最严重的误操作就是误删除Master的checkpoint和mutation log文件,应对措施是主备广播时,prepare SN避免大幅回退。
6.4      周期性的身份确认
    Master周期性地校验自身和在Zookeeper上的角色,确认两者一致或者属于合法的角色值,并在出错时启动降级流程。这种机制对某些情况属于必须的垃圾回收型机制,比如主踢掉备后即可继续服务,并不会对备发指令(因为有可能备宕机无法接收指令),备检测到自己在Zookeeper上已经是Newbie,即可完成降级过程。同时,这种机制也能应对某些随机的bug,使Master最终处于正确的角色。
6.5      优雅退出
    Master尽最大限度的支持优雅退出。考虑到内部多种状态机,这样会比较复杂,但好处是:
1)         减少failover时间。Master在优雅退出的第一步就是主动关闭到Zookeeper的连接,以便Zookeeper可以立即通知其他Master抢锁,避免Zookeeper等待master超时。
2)         利于测试。因为Master的测试需要模拟各种错误情况,能够在一个进程中方便的起停不同的Master实例能方便模拟测试场景,机群中压测时也需要反复杀死Master。
6.6      监控与调试
    Master提供HTTP页面展示主备的内部状态,并提供RPC接口报告Master整体的可读、可写、不可用等状态,利于获知Master状态。
    Master对内部事件记录了详细的日志,作为出bug时调试的主要依据。
6.7      测试
    主备协议的状态多,步骤多,又都是异步的实现,容易出bug。同时,主备协议的复杂性主要在应对各种出错情况,正好出错情况难模拟,导致难以测试。
    Master借助GMock模拟出错场景,提供单元测试,每个用例模拟一种出错场景。通过约40种出错场景,覆盖主要的错误情况。
    同时,XFS Master执行高并发下多次failover测试,即压测环境下,周期性(比如10分钟一次)kill一个Master,确认Master能正常完成主备切换,同时XFS的各个模块能自动从错误中恢复,对XFS的应用可以屏蔽错误。
7          评测
7.1      正确性
    分布式协议难以保证设计和实现的正确性。Master主备机制的复杂性超过可以形式化证明的程度。另外,即使能证明设计的正确性,也无法证明实现的正确性。
    因此,XFS Master中换了一个思路,希望确定出一些规则,类似程序设计中的不变式(Invariant),保证在协议出错时可以检测出错误。各个位置检测到有违背规则时,Master立即core掉。
    最重要的一条规则就是:Commit时,保证commit SN全局单调连续增长。注意是连续增长,使得一旦有错误导致SN不连续时,一定可以检测出来。容易证明,当主备Master的commit SN都从1开始连续单调增长时,只要commit SN相同,则执行过的MutationLog序列相同。
    相关的重要规则是:主Master在一个原子操作中保证:当仅当有version确保自己拥有最新的ReplicaView数据时,才更新ReplicaView。由此ReplicaView的version和commit SN共同成为mutation的标识,保证执行序列相同。
    如果主备的执行序列相同,mutation的内存执行结果也相同,则主备的数据必定一致。然而,mutation的内存操作可能有bug导致不一致,比如线上遇到过主备对quota处理策略不同导致的不一致。因此,引入另一个重要规则:周期性的执行主备checkpoint文件的checksum检测。
    备Master会从主Master中获取历史各次Checkpoint时的commit SN和对应磁盘文件的checksum,并从本机另起一个检测线程,加载本机Checkpoint文件,并重放日志至commit SN处,将结果新写成Checkpoint文件,校验其checksum和主Master checksum的是否一致。
    通过保障主、备按同样的单调递增顺序Apply日志,可以保证主备有同样的操作序列。再保证Apply后的Checkpoint文件的checksum一致,可以检查执行序列+内存数据结构Apply操作的正确性。上述规则相加,可以保证任何协议错误都能被检验出来。
7.2      性能
    Master推荐的部署模式是一主两备,64位release版。实测一主两备的性能(机型TS5):
1) 2亿文件时,master峰值写操作(创建文件)qps 55800+ (mutation广播并实际写硬盘)
2) Kill 主master后,重新恢复服务需约150ms
3) 主和Newbie相差15万条mutation时,learning时间约340ms
7.3      部署情况
    主备机制中,2011年4月起Replication协议上线,8月起failover和learning协议上线,均部署到全部的超过10个XFS机群。
从2011年8月起,XFS Master借助主备机制,实现了Rolling update,支持了各种非预期错误,使得线上服务的可用性上升了一个台阶。
8          相关工作
    Google在GFS论文中也提到Master Replication机制,未详述,但从行文推测是类似两阶段提交协议。2009年的采访[4]中提到GFS的主备方案有演进,从1小时量级的手动failover时间缩短至自动的10秒量级,并在开发新的文件系统。
    Microsoft Research Asia和Microsoft Research Silicon Valley有一篇合作文章PacificA [5],其设计是XFS Master主备机制的重要参考。
    本文中主Master广播mutation到备,备按确定的顺序执行mutation以达到主备数据一致的思路来自Lamport 1978年提出的state machine replication。关于state machine replication,人们研究了诸多基于良性故障模型或者拜占庭故障模型的方案,通过两阶段提交、三阶段提交、或者Paxos实现主备一致,通过协议模型优化或者良好的工程实践提升性能。本文采用良性故障模型,但对某些常见误操作做了处理;本文采用两阶段提交完成主备广播,但用Paxos的开源实现Zookeeper选举主Master;本文集成了batching、piggybacking、pipelining、async state machine等良好的工程实践获得了极高的性能。
Hadoop中HDFS的NameNode High Availability机制也有不少工作,主要工作包括:
1)         HDFS中集成了SecondaryNameNode,通过周期性的拉取主NameNode的EditLog(增量日志),形成FsImage(即Checkpoint),主NameNode宕机时,SecondaryNameNode可以顶上。这个方案简单,但可能丢失最近N分钟的数据,failover通常人工介入。
2)         Facebook提出AvatorNode,作为NameNode的Hot standby,通过NFS共享EditLog,可以1分钟内完成failover。
3)         Yahoo! 提出Backup Node + Linux HA完成NameNode的HA。
4)         Cloudera 提出用DRDB + Linux HA 完成NameNode HA。
5)         IBM Research给出Master metadata replication方案,并自己实现选举协议。
6)         Ebay存储最新几分钟的EditLog到Zookeeper,以便节点出错时恢复。
7)         淘宝将NameNode数据持久存储在MySQL集群中实现NameNode HA。
8)         百度的HDFS2也集成了类似AvatorNode的HA方案,具体情况未知。
另外,Hadoop 社区在2012年3月将NameNode HA合入trunk 。
9          结论
    XFS Master的主备机制维持Master的多个副本,以便出错时切换到备用Master,持续提供服务,去除XFS的单点。
    Master主备机制通过三套子协议完成设计目标:通过基于两阶段提交的Replication协议提高了数据可靠性;通过failover协议处理各种错误,完成主备切换,提升Master的可用性;通过learning协议完成滞后或者新加Master的数据自动对齐,支持错误节点的自动恢复和运行时增加Master节点,简化了运维。
    XFS Master主备机制达到了5.58万的峰值写qps,几百毫秒级的failover和learning,支持了Master的Rolling Update。这套协议自2011年4月起陆续在全部的超过10个XFS机群部署运行。