• Ceph Paxos算法实现
• Ceph PG一致性保证

Raft是个一致性算法，涉及一致性问题，不得不提CAP帽子理论。该理论认为强一致性C、高可用性A和分区容错性P在分布式系统中不能三者兼顾，只能满足其中两项。分布式系统一般都要求满足P，所以只能在C和A之间做权衡。以3副本写数据为例，如果满足C，那么在其中一台Server故障的情况下，客户将无法继续写数据，否则3台Server的数据将不一致，也就是说要牺牲A。如果满足A，即在其中一台Server故障的情况下，客户能够继续写数据，那么此时故障的Server将无法处理新写入的数据，从而导致3台Server的数据不一致，即牺牲了C。Raft是最终一致性算法，在C中做了让步，如果一台Server故障，那么可能还可以继续提供服务，也可能需要过一小段时间后才能提供服务。当故障Server重启后有方法让3台Server的数据重新到达一致的状态。C和A并非非此即彼，大部分情况是在相互权衡，各让一步。

Ceph Paxos算法实现

Paxos实现主要包含3个阶段：Leader选举阶段、Recovery阶段和正常运行阶段。Paxos先选出一个Leader来负责所有客户端的写请求，选举过程中还划定了一个Quorum集合，集合内的每个成员都是当初投票给当前Leader的节点，正常运行时只要将提案发送给Quorum集合内的成员即可。Leader当权后的第一件事情就是要将Quorum中每个成员的状态达成一致，这就是Recovery阶段。展开Recovery阶段前，先说说正常运行阶段。

Paxos中一个客户端请求称为一个提案，这个提案要apply到每台Server。为保证网络延迟、Server宕机等问题后集群各节点的状态仍然能够达成一致，Paxos分两个步骤来处理提案：先在多数派中复制提案，再Apply提案。Paxos能够保证已在多数派中复制的提案，出现故障后，仍然可以在每台Server中Apply提案。Apply提案会改变Server的状态，如果跳过第一步直接Apply提案，将会导致Server状态不一致。举个简单的例子，如果Leader接收到客户端的提案后先在本机Apply提案，然后再通知其它Server Apply提案，Leader在Apply完提案但还没通知其它Server时宕机，那么Leader的状态已经改变，其余Sever重新组成多数派继续处理其它的提案。原Leader重新加入后，因为Apply提案的顺序不同，所以它的状态已经无法和其它Server的状态保持一致了。正常运行中，Paxos处理提案的主要流程如下：

1. Leader先将提案写入本地数据库，再发送给各Quorum成员；
2. Peon 将提案写入本地数据库，回复Leader。
3. Leader 检查是否多数派已接受提案，如果是则：(1) 递增last_committed变量；(2) Apply提案。last_committed变量代表对应的提案是最近的已经复制到多数派的提案，这两项内容在一个Transaction中完成，写入数据库后通知Peon。
4. Peon 同样递增last_committed变量，并Apply提案。

Recovery阶段的主要目的是让Quorum成员的状态达到一致。由于Leader选举规则是让rank值最小的Server当选Leader，所以Leader拥有的提案可能并不是最全的，其它Peon的提案也参差不齐，有的比Leader多，有的比Leader少。通过以下步骤将所有Server的提案保持一致：

1. Leader先检查本地数据库是否存在last_committed+1的提案(已写入到本地，但还没有Apply的提案)，如果存在，用uncommitted_v代表这个未提交但已经写入数据库的提案。然后，向Quorum成员发送OP_COLLECT请求获取对方的first_committed、last_committed变量；
2. Peon除了回复Leader自己的first_committed和last_committed外，还要做两个检查。首先检查自己的last_committed是否大于Leader，如果是，则同时返回多出的提案；其次检查本地数据库是否存在last_committed+1的提案，如果存在一并回复给Leader。
3. Leader 如果Peon有多出的提案，Leader将多出的提案Apply到本地数据库，补齐自己；如果Peon缺少部分提案，Leader将多出的提案发送给Peon，Peon Apply缺失的提案，补齐Peon；如果Peon的uncommitted_v大于Leader，Leader更新uncommitted_v; 最后收集完所有Quorum成员的提案后，重新提交未提交的提案。

考虑一个场景：3台Server，标记为S1、S2和S3，其中S1为Leader。 CASE1 Leader在将提案P1写入本地数据库但还未来得及复制给S2和S3时宕机，S2和S3重新选举，S2和S3组成新Quorum集合。由于S2和S3中并没有P1提案，所以提案P1被忽略。

CASE2 Leader在将提案P1写入本地数据库并且复制给S2和S3中的一个或两个时宕机了，S2和S3重新选举，S2和S3组成新Quorum集合。由于S2和S3中至少有一台Server包含了P1提案，新Leader会重新提交该提案。

CASE3 Leader在将提案P1写入本地数据库，复制给S2和S3，Apply到本地数据库但还没来得及通知S2和S3时宕机，S2和S3重新选举，S2和S3组成新Quorum集合。由于S2和S3中至少有一台Server包含了P1提案，新Leader会重新提交该提案。

CASE2和CASE3中，由于新Leader重新提交了提案P1，所以S1恢复后3台Server在last_committed+1位置的提案相同。CASE1中如果新Leader接收到提案P2复制到本地后宕机，S1、S2、S3重启，S1重新当选Leader，此时S1中last_committed+1的提案为P1，S2中last_committed+1的提案为P2，在相同的位置两者的提案不相同，此时如何处理？按照目前的实现，会选择S2的未提交提案P2。所以，如果提案已经复制给了多数派，那么该提案可以恢复。否则，可能会丢失，也可能会恢复。

Ceph PG一致性保证

再简单回顾下Paxos保证一致性的过程。
首先要保证每台Server的状态一致，只要保持每台Server Apply提案的顺序一致。为避免某些Server Apply了提案而另外一些Server没有Apply提案造成状态不一致的问题，采用了先在多数派中复制提案，再Apply提案的措施。一个提案只要复制到多数派，那么Paxos就能够保证无论发生什么故障，该提案最终都会被Apply到所有节点。

可以将Ceph的PG也看成一个小集群，在多副本策略的情况下PG也要保证各Server的数据一致。同Paxos实现一样，PG的运行过程也可以分为3个阶段：Leader选举、Recovery阶段和正常运行阶段。每个阶段的实现有所不同，PG的Leader选举阶段中Leader并不是选出来的而是空降来的，OSDMap的变化可能会引起PG到OSD映射的改变，映射的改变直接决定了新Leader的人选。PG中的Leader称为Primary OSD，其它Server称为Replica OSD，正常工作流程如下：

1. Primary OSD接收来自客户端的写请求，将写请求和对应的日志项转换成一个Transaction，再将Transaction发送给所有Replica OSD，同时Apply Transaction；
2. Replica OSD直接将Transaction Apply到本地，再回复Primary OSD；
3. Primary OSD接收到所有Replica OSD的回复后，回复客户端。

对比Paxos实现，可以发现PG存在“很严重”的一致性问题，PG省略了将用户请求复制到多数派的过程，每台Server接收到请求后直接Apply到本地。考虑上文中的CASE1，如果Primary OSD接收到请求将其成功Apply到本地后宕机，而其它Replica OSD没有接收到该请求。此时其它Replica OSD重新选出新Primary OSD，继续处理客户端请求，等旧Primary OSD重新加入集群后，因为旧Primary OSD Apply了一个其它Server中没有的请求，按照Paxos的数据恢复方法旧Primary OSD无法和其它Server达到一致状态了。

Paxos恢复数据的方法是依次Apply提案。举个例子，假设Paxos操作一个变量i，i的初始值为1，Primary OSD已经Apply但其它Server没有Apply的提案为：i=0，Primary OSD宕机期间其它Server处理的提案为：i*=2。那么Primary OSD重新加入集群后继续Apply i*=2的提案的结果为0，而其它Server的结果为2，所以无法达成一致。不过，PG恢复数据的方式和Paxos不同，PG直接将数据i拷贝给旧Priamry OSD，从而旧Primary OSD仍然能够和其它Server达成一致。

PG中有大量的数据，例如i，j，k…，如何确定哪些数据需要恢复哪些不需要恢复？ PG中i代表一个Object，通过比较各Server的PG Log来确定需要恢复的Object。Paxos实现中先复制的那份提案可以理解为一份日志，日志的日志项由两部分内容组成：索引和提案内容，还没提交的提案的索引为last_committed+1。PG Log也是一份各Server单独维护的日志，日志项包含两部分内容：索引和操作(Op)。不同的是，PG Log的索引是矢量时钟，由OSDMap的epoch版本号和PG自增的版本号两部分组成，这样的好处是不会出现相同的索引号对应到不同的日志内容。因为正常运行时日志的索引号由Primary OSD确定，Primary OSD故障后，OSDMap必然有变动否则不会产生新Primary OSD，从而新Primary OSD的日志索引中OSDMap的版本号和旧Primary OSD的版本号不同，并且高于旧版本号，因为OSDMap变动后epoch是递增的。另一个不同点是，日志项内容是轻量级的，只包含操作(Op)不包含数据。因为日志项中不包含实际数据，所以对缺失日志的Server无法通过Apply日志来恢复数据，PG Log只能用来做部分的回滚操作（例如，Op为创建一个Object，回滚时可以删除该Object）或者确定缺失的Object。

实际上，PG的Recovery阶段又细分成两个子阶段：Peering阶段和Recovery阶段。Peering阶段通过收集各Server的PG Log确定一个权威Log，通过将各Server的PG Log和权威Log的比较确定应该恢复的Object。Recovery阶段执行数据复制操作，这个阶段中Primary OSD已经可以开始处理客户端请求了。Peering阶段的主要步骤如下：

Primary OSD根据past interval和新OSDMap确定一个PriorSet，PriorSet中的成员用于参与数据恢复。恢复数据的目的是让新OSDMap的up集合中各Server的状态达成一致。这是因为up集合由CRUSH算法直接计算得到，是最终正常运行时PG的Server成员。由于PG中Primary OSD不是选出来的，所以新up集合中的Server可能原先都不包含PG的数据，所以恢复过程需要由旧Server来共同参与。旧Server由past interval提供，past interval包含PG对应的旧Server。 Primary OSD拉取PriorSet各成员的pg info，并根据各成员的pg info计算出一个权威Log，权威Log包含最全的日志项。pg info是PG Log的一个简单描述，例如描述PG Log的最后一条日志的索引号。 如果权威log对应的Server不是Primary OSD自己，则向权威Server请求自己缺少的日志项。

PG如何处理上文CASE1提到的Apply不同请求的情况？ 举个例子，假设有3台Server，分布标记为S1、S2和S3，初始S1为Primary OSD，3台Server的PG Log如下：

    S1(Priamry): A1, A2, A3
    S2: A1, A2
    S3: A1, A2

日志项中字母代表OSDMap的epoch版本号，数字代表PG自己的版本号。假设在S1将A3 Apply到本地后宕机，S2和S3没有接收到A3请求。S1宕机后，S2和S3重新选出Primary OSD，继续处理来自客户端的请求。此时，各Server的PG Log如下：

    S1(宕机): A1, A2, A3
    S2: A1, A2, B3, B4, B5
    S3: A1, A2, B3, B4, B5

S1重启加入集群，开始Peering操作。此时会选择一个权威日志（比如S2的日志），S1从S2中拉取缺少的日志（从位置A3开始），S2将日志[B3, B4, B5]发送给S1，同时标记前一条日志为A2而不是A3。S1接收到S2的

1. S1选出一个权威日志，例如S2的日志；
2. S1发现自己不是拥有权威日志的Server，向S2请求从位置A3开始的日志；
3. S2将日志[B3, B4, B5]发送给S1，并标记前一条日志为A2，而不是A3;
4. S1将来自S2的日志Merge到自己，Merge前先拎出有分歧的日志项A3，然后将日志项追加到自己的日志中。所以此时S1的日志为：[A1, A2, B3, B4, B5]
5. S1检查有分歧的日志项A3，依据日志项的内容做不同的操作，具体参考_merge_object_divergent_entries函数。简单来说，假设A3是对Object O1的操作，如果A3后面的日志没有再对O1的操作了，则判断A3操作的内容。如果A3是创建Object，那么对应要删除该Object；如果A3的操作是可以回滚的，那么就回滚该操作；如果A3的操作是不可回滚的，那么将O1添加到missing列表，在Recovery阶段从其它Server中复制数据。

PG的数据恢复还有很多其它内容，本节主要是为了跟Paxos做个比较，故而不够全面。