2014-7-29 00:10| 发布者: tianzc| 查看: 434| 评论: 0
| 摘要：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机群部署运行。 |
