PacificA算法分析
- 2019 年 10 月 30 日
- 筆記
PacificA算法是微软亚洲研究院提出的一种用于日志复制系统的分布式一致算法，与其他的一致性算法相比，PacificA算法主要用于数据的一致性管理，并另辟蹊径采用其他一致性组件来进行配置一致性管理。
1. 特点
- 配置管理与数据管理分离：引入额外一致性组件来维护Configuration
- 强一致性：任意时刻读取到的数据都是最新数据
- 少数派Replica可用时仍可读写：每个副本都有全量数据因此只要有一个副本存在即可保证读写
- 去中心化的故障检测：通过节点间的契约机制来进行故障检测
2. 名词
- Replica Group：互为副本的一组数据的集合，其中有一个primary，其余都是secondary
- Configuration: Repica Group的元数据，如副本有哪些，谁是primary等
- Configuration Manager: 配置一致性管理工具
- Serial Number(SN): 代表Update的执行顺序，每次update增加1
- Prepared List: Update操作的序列
- Committed List: 已经提交的update序列，是Prepared List的前缀
3. 读写流程
3.1 查询(query)
该算法中，查询只能在primary上进行，primary获取自身的数据，直接返回即可
3.2 更新(update)
更新也是在primary上发起，流程如下
- primary为updateRequest分配一个SN
- primary发送prepare请求到各secondary,请求中包含updateRequest和SN
- 各secondary接收到请求，并将updateRequest和SN加入到PreparedList中，返回ACK给primary
- 当primary收到所有secondary的ack后，则执行该update，并将commit point移动到该commit。
- 返回执行成功
可以看到当一个update执行成功后，primary上对应的数据已经commit，secondary上数据也被加入到了更新队列中。在这种情况下
- 读操作读取的是primary上的commitList,可以拿到更新的数据。
- secondary中虽然数据没有被commit，但是也被加入到了prepared List中，当主节点挂掉时仍能保证数据不丢失。
- secondary上的数据不能自己commit，而必须由于primary来触发。这是为了应对由于异常情况导致update没有执行成功，secondary自主commit导致未更新成功数据被commit，且数据领先与primary。
3.3 Committed Invariant
从读写流程可以推导出committed不变式"Committed Invariant"
- Secondary Committed List为Primary committed List的前缀, 即primary commit领先于secondary。
- Primary Committed List为Secondary PreparedList的前缀，即Sencodary拥有primary commit的所有数据（虽然没有committed）。其实当没有在进行update操作时，Secondary的PreparedList和Primary的CommittedList是应该是一样长的。
?这里想到一个异常情况，当update执行过程中，primary挂掉了，导致更新失败，secondary已经被prepare了update，这时一个secondary被选为新的primary，将其所有的update commit，那之前失败的update操作数据不就出现在了数据中，导致与预期不符？
这里与同事讨论了一下，认为pacificA算法中一个primary或secondary是一个数据实体，不应该是一个执行实体，所以当primary挂掉后，update任务不会执行失败，而是等待选出新的primary，并在其上commit这个update，保证不会出现数据不一致的情况。
4. 故障检测和恢复
pacificA通过契约(lease)的方式来进行primary和secondary间的互相检测。primary会定期(lease period)向各节点请求契约，如果某个节点没有回复，则说明该节点已经故障，primary会向Configuration Manager请求移除该secondary。 如果过了(grace period), 一个secondary没有收到primary的请求，则认为primary故障，该secondary会向Configuration请求移除Primary，并将自己设置为primary。这里要注意
- 当多个secondary均发现primary故障，则按照first win原则，先请求的成为primary
- 当出现网络分区时，primary会要求剔除secondary， secondary要求剔除primary，但由于lease period< grace period，可以保证primary先于secondary发现故障，并将secondary剔除
4.1 secondary故障
当一个scondary故障时，primary在向该secondary发送lease请求时会超时，primary向Configuration Manage发送Reconfiguration请求将该secondary从Configuration中移除
4.2 primary故障
当primary故障时， secondary在超过grace period没有收到primary的请求，就会向Configuration Manager发送Reconfiguraiont请求
要求将primary从configuration中移除并将自己选为primary。多个secondary竞争成为primary时，遵循first win原则。
当一个secondary被选为primary后 ,它会向所有的secondary发送prepare请求，要求所有的sencodary均以其pareparedList为准进行对齐，当收到所有secondary的ack后，primary将自己的commit point移动到最后，这个时候primary才能对外提供服务。
4.3 网络分区的场景
网络分区场景下，primary认为secondary故障，secondary认为primary故障，但由于lease period小于grace period，所以primary会先与secondary发现故障，并向Congfiguration Manager发送请求移除secondary
4.4 新节点加入
新节点加入时，首先会先成为secondary candidate, 然后追平primary的preparedList,然后申请成为secondary。还有一种情况是之前故障的节点恢复加入，这个时候会复用之前的preparedlist并追平secondary的preparedlist, 然后申请成为secondary。
4.5 Primary Invariant
在pacificA算法中，要保证primary不变式Primary Invariant，即
- 同一个时刻只有一个副本认为自己是primary
- configuration Manager也认为其是primary。 从前面的故障恢复可以看到pacificA算法通过lease（契约）机制保证了这个不变式
4.6 Reconfiguration Invariant
重新配置不变式：当一个新的primary在T时刻完成reconfiguration,那么T时刻之前任意节点（包括原primary）的committedList都是新的primary当前committedList的前缀。
该不变式保证了reconfiguration过程中没有数据丢失，由于update机制保证了任意的sencondary都有所有的数据，而reconfiguration重新选primary要求新的primary commit其所有的prepareList,因此这个不变式可以得到保证。
5. 算法总结
PacificA是一个读写都满足强一致的算法，它通过三个不变式保证了读写的primary的唯一性，读写的强一致性，故障恢复的可靠性。
它把数据的一致性和配置的一致性分开，使用额外的一致性组件（Configuration Manager）维护配置的一致性，结合lease机制保证了Primary Invariant，使得在同一时刻有且仅有一个primary。 update操作时，要求所有的secondary均prepare当前update，primary commit当前update，保证了Committed Invariant, 使得读操作可以获取到最新数据，primary故障时，secondary也有全量的数据。
故障恢复机制保证了当secondary被选为primary时，其commit包含之前primary或secondary的commit，保证了Reconfiguration Invariant，使得在故障恢复后数据不会有丢失。
