PacificA协议小结

作者：李小翠

简介

大规模分布式存储系统往往采用廉价的商用机器或硬件，失效出错是常态，因此容错是这类系统实现可用性和可靠性的关键。PacificA是微软大规模分布式存储系统开发的一个通用复制框架，提供强一致性，可以适配不同的复制策略。PacificA的设计特点有：

1. 一个通用和抽象（general and abstract）的复制框架，正确性易验证，不同实例可以使用不同策略
2. 配置管理和数据复制分离。Paxo负责配置管理，主从策略负责数据复制
3. 错误检测和配置更新是在数据复制的交互过程中完成的，去中心化

系统框架

这里面数据存储的最小单位是数据段（数据的集合，是实际存储在磁盘上的文件）。

复制组（replica goup）：分布在不同存储节点上的相同数据段（下图中的Data Node1中的Data1和Data Node3中的Data1构成一个复制组.

副本（replica）：每个数据段为一个副本.

主副本（primary）/从副本（secondary）：这个是由复制组的配置信息（configuration）指定的。如果复制组信息的变化（比如replica的移除或增加），都会导致配置信息的变化.

版本（version）：用来追踪configuration的变化.

存储集群：负责数据的查询（query）和更新（update）,通过使用多副本的方式保证数据的可靠性和可用性.

配置管理集群：维护副本信息，比如，replica的移除和增加、当前副本的版本等。该集群使用Paxos协议维护该数据的一致性.

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点了.

下图简单演示了这个过程：

由图中可以直观的看到：

如果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）

实践中的日志复制

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的。

网易云大礼包：https://www.163yun.com/gift

本文来自网易实践者社区，经作者李小翠授权发布。