title: PacificA协议小结
date: 2017/9/14 23:42:15 tags: - 复制协议 - 强一致 categories: - 一致性协议 --- ## 简介 大规模分布式存储系统往往采用廉价的商用机器或硬件，失效出错是常态，因此容错是这类系统实现可用性和可靠性的关键。PacificA是微软大规模 分布式存储系统开发的一个通用复制框架，提供强一致性，可以适配不同的复制策略。PacificA的设计特点有： 1. 一个通用和抽象（general and abstract）的复制框架，正确性易验证，不同实例可以使用不同策略 2. 配置管理和数据复制分离。Paxo负责配置管理，主从策略负责数据复制 3. 错误检测和配置更新是在数据复制的交互过程中完成的，去中心化 <!-- more --> ## 系统框架 这里面数据存储的最小单位是数据段（数据的集合，是实际存储在磁盘上的文件）。 > ***复制组（replica goup）***：分布在不同存储节点上的相同数据段（下图中的Data Node1中的Data1和Data Node3中的Data1构成一个复制组. > > ***副本（replica）***：每个数据段为一个副本. > > ***主副本（primary）***/***从副本（secondary）***：这个是由复制组的***配置信息（configuration）***指定的。如果复制组信息的变化（比如replica的移除或增加），都会导致配置信息的变化. > > ***版本（version）***：用来追踪configuration的变化. > > ***存储集群***：负责数据的***查询（query）***和***更新（update）***,通过使用多副本的方式保证数据的可靠性和可用性. > > ***配置管理集群***：维护副本信息，比如，replica的移除和增加、当前副本的版本等。该集群使用Paxos协议维护该数据的一致性. ![此处输入图片的描述][1] ### 数据复制（data Replication） PacificA的使用主从框架进行数据复制，保证数据的一致性。queries和updates都发送给primary，其中quries由primary在本地处理，updates由primary通知到所有的secondaries共同处理。 如何能做到强一致？如果满足下列条件，系统就能做到强一致（其实也就是复制状态机的属性）： * 复制组中的servers如果能按相同的顺序处理统一请求集合 * update操作的结果都是确定性的 在PacificA中，为了实现强一致性，primary会给收到的所有update消息编号（这个编号是连续并且单调递增的），然后通知secondary按编号顺序处理这些请求。就这种做法，PacificA做了一个**建模**：replica有一个***prepare list***和***commited point***. > ***prepare list***：用来存放所有request,其中的每个request有一个***sn***号（就是上面所说的消息编号）. > > ***commited point*** ：这个点之前的所有update操作是肯定不会丢失的 > > ***commited list***：prepare list中从起始点到commited point这一点所包含requests。可以保证这个list中的所有请求是不会丢失的（server发生不可容忍的错误除外，比如所有replica永远挂掉了）。 > > ***aplication state***：将commited list中所有的requests按sn顺序作用在***init state***后的结果 **正常情况下（Normal-case）** 查询： > primary收到query，查询commited list中的state，并将查询结果返回 更新： 1. primary给update分配可用的sn号 2. primary给secondaries发送***prepare message***（prepare包含request、configuration version、该request在primary的prepare list中的sn） 3. 当secondary收到prepare message信息后，把这条信息插入到prepare list 4. secondary向primary发送acknowledgement,当primary收到所有secondaries的消息之后，primary移动commited point 5. primary给客户端返回已成功的消息，同时，给从节点发送prepare message（primary本次提交的commited sn）通知secondaries可以移动commited点了. 下图简单演示了这个过程： ![此处输入图片的描述][2] 由图中可以直观的看到： > 如果p是primary，q是replica group中的任何一个secondary,则下列关系成立： > committedq⊆committedp⊆preparedq > 称这个为***提交不变性（Commit Invariant）*** 简短的证明：primary只有在sedondaries都将request插入到prepare list中后才会移动committed point，则有committedp⊆preparedq；secondary只有收到primary的prepare message之后才会移动committed point，这个时候，primary已经移动过自己的committed点了。 ### 配置管理（Configuration Management） 上面说的数据复制都是在没有异常的情况下进行的，对于节点上下线等情况，复制组的configuration会发生变化，此时就需要配置管理介入了。 配置管理维护复制组的信息：节点信息和版本信息 下列三种情况会导致复制组的配置发生变化（需要reconfiguration）： * secondary离线 > 如果primary在***lease period***内未收到从节点对心跳的回应，则认为secondary异常，primary向配置管理汇报更新复制组的configuration，将该点从复制组中移除，并且自己也降级不再作为primary.configuration manager收到消息之后，更新本地配置。此时replica group中无主，secondaries会向configuration manager申请成为新的主. * primary离线 > 如果secondary在***grace period***内未收到primary的心跳，则认为primary异常，secondary向配置管理汇报更新复制组的configuration，将primary从复制组中移除，并将自己升级为主。如果configuration management同意了该请求，该replica提升为主 * 复制组增加新的节点 > 可能的一种情况是，原来离线的节点重新上线，此时primary向配置管理汇报最新拓扑。 上述情况中，replica向configuration manager发送汇报变更的时候，除了要将当前最新的configuration发送过去，**还需要包含当前配置信息的版本**。只有当replica发送过来的当前配置版本和configuration manager中的版本信息相同时，更新请求才会成功，否则失败。 此外，configuration management按照请求的先后顺序进行处理。这是必要的，因为如果同一个replica group的多个replica申请为主成功，configuration management就会将该复制组的version增加，此时，其他请求就会因为当前携带version不同而被拒绝 ### 错误检测（Failure Detection） 上部分已经说明了secondary异常和primary异常如何检测，提到了***lease period***和***grace period*** > ***lease period***：primary会定期发送***beacons***给secondary并等待回答，如果在***lease period***期间内没有获得acknowledgement，那么primary认为lease失效. > > * secondary收到primary信息的时候，会查看configuration，如果确实是primary，它就会回答. > > ***grace period***：如果secondary发现从接到上一个beacon起的***grace period***后，还没有收到primary发送过来的消息，就认为primary的lease失效. 只要lease period<=grace period,就不会产生二主问题。因为主总是先检测到从没有回复这件事情，它会汇报给configuration managemenet并且降级为secondary；secondary检测到primary异常的时候，primary已经降级了. ### Reconcilliation 配置管理小节说reconfiguration的时候，没有说成为新的primary之后应该做什么。 当一个replica成为新的primary的时，需要做的第一件事情是***Reconfiguration***。**其实就是为了同步复制组的信息（不过pacificA中并没有清楚的说明这一过程，只说了最后要达到的效果，日志同步可以参考raft的实现方式）**。 * primary把它prepare list中的uncommitted requests通过prepare message发送给secondaries，并提交**（感觉这种提交好像有问题，因为此时还没有同步到secondaries上，如过提交完挂了怎么办）**，假设commited point是sn * secondary收到信息后，根据primary的sn进行prapare list的截断（不能超过sn） ### Recovery 配置管理小节同样没有提及新节点加入之后应该怎么去达到right status。 * 新加入的时候，replica是以***candidate***的身份加入的 * primary同样给candidate发送prepare messages * candidate在接受prepare messages的同时，还要从其中复制组中的某个replica中分布获取preoare list中的信息，直到candidate可以catch-up * candidate请求primary把它加到configuration中。primary给configuration manager发送添加该点的信息 这个过程就是***recovery*** 不过如果一个全新的server加入，这种状态转换的开销是很大的，pacificA里面提到了其他文章中的一种做法***catch-up recovery*** **（这个pacificA里面只大致说了一下，没有描述的很清楚，我暂时还没有看这篇论文Availability in the Echo file system）** ### 实践中的日志复制 ![此处输入图片的描述][3] pacificA中提及了三种方法 1. Logiccal Replication * 将prepare list和application state分离开，log既保存application log，也保存prepared request。这样做可以减少开销。 * 要实现上述方法，可以在application log entry中添加configuration,sn,lastcommitted sn. 2. Logical-V 这个方法说只有primary在内存中保存这个state，而secondary只增加entry，不改变状态。 3. Layered Replication lower layer做持久化存储，upper layer将应用逻辑转化为对文件的操作。其实这样的话，就可以把replication这个事情交给lower layer去做，比如Bigtable就是基于GFS的。 [1]: http://pacifica.nos-eastchina1.126.net/PacificA%E6%80%BB%E4%BD%93%E6%A1%86%E6%9E%B6.png [2]: http://pacifica.nos-eastchina1.126.net/pacificA%20Prepare%20list.png [3]: http://pacifica.nos-eastchina1.126.net/pacificA%E5%AE%9E%E8%B7%B5%E4%B8%AD%E7%9A%84%E7%B3%BB%E7%BB%9F.png