猪小花1号

个人签名

282篇博客

PacificA协议小结

猪小花1号2018-09-03 09:59

作者:李小翠

简介

大规模分布式存储系统往往采用廉价的商用机器或硬件,失效出错是常态,因此容错是这类系统实现可用性和可靠性的关键。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 periodgrace 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

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