PacificA严格来说不是一个算法，而是一个分布式一致性框架。它采用配置集群和存储集群的方式，实现数控分离，这点和SDN有点像。其中配置集群负责管理，具体说来是采用了ETCD方案，而ETCD又是采用raft算法来实现一致性的。具体说来，选主的过程可以概括为：从者失联，自立为王；主者失联，下野流放。还有一点有意思的是，这里也应用了一种叫做租约机制的玩意，形象的说就是一厢情愿。所谓一厢，指的是授权者颁布lease时，不会管接收方的状态。就像男孩子追女孩子一样，虽然有点傻，但一般男生在一段时间内会信守承诺，克服重重困难。但和所有靠谱承诺一样，都是会是有期限的。所以lease期限到后，双方都不认了，这时授权者又可以重新颁发lease，接收方也不相信这个lease的有效性。比如说，一台服务器发出lease,我在30秒内部改变数据，那么其他client就可以放心的在这30s内访问数据，不用担心数据不一致问题。30s后，其他client再收到lease就视而不见了。
PacificA算法是微软亚洲研究院提出的一种用于日志复制系统的分布式一致算法，与其他的一致性算法相比，PacificA算法主要用于数据的一致性管理，并另辟蹊径采用其他一致性组件来进行配置一致性管理。
配置管理与数据管理分离：引入额外一致性组件来维护Configuration
强一致性：任意时刻读取到的数据都是最新数据
少数派Replica可用时仍可读写：每个副本都有全量数据因此只要有一个副本存在即可保证读写
去中心化的故障检测：通过节点间的契约机制来进行故障检测
Replica Group：互为副本的一组数据的集合，其中有一个primary，其余都是secondary
Configuration: Repica Group的元数据，如副本有哪些，谁是primary等
Configuration Manager: 配置一致性管理工具
Serial Number(SN): 代表Update的执行顺序，每次update增加1
Prepared List: Update操作的序列
Committed List: 已经提交的update序列，是Prepared List的前缀
该算法中，查询只能在primary上进行，primary获取自身的数据，直接返回即可
更新也是在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。
从读写流程可以推导出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，保证不会出现数据不一致的情况。
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剔除
当一个scondary故障时，primary在向该secondary发送lease请求时会超时，primary向Configuration Manage发送Reconfiguration请求将该secondary从Configuration中移除
当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才能对外提供服务。
网络分区场景下，primary认为secondary故障，secondary认为primary故障，但由于lease period小于grace period，所以primary会先与secondary发现故障，并向Congfiguration Manager发送请求移除secondary
新节点加入时，首先会先成为secondary candidate, 然后追平primary的preparedList,然后申请成为secondary。还有一种情况是之前故障的节点恢复加入，这个时候会复用之前的preparedlist并追平secondary的preparedlist, 然后申请成为secondary。
在pacificA算法中，要保证primary不变式Primary Invariant，即
同一个时刻只有一个副本认为自己是primary
configuration Manager也认为其是primary。
从前面的故障恢复可以看到pacificA算法通过lease（契约）机制保证了这个不变式
重新配置不变式：当一个新的primary在T时刻完成reconfiguration,那么T时刻之前任意节点（包括原primary）的committedList都是新的primary当前committedList的前缀。
该不变式保证了reconfiguration过程中没有数据丢失，由于update机制保证了任意的sencondary都有所有的数据，而reconfiguration重新选primary要求新的primary commit其所有的prepareList,因此这个不变式可以得到保证。
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，使得在故障恢复后数据不会有丢失。
原文链接: https://www.yukx.com/arithmetic/article/details/2051.html 优科学习网PacificA算法分析-分布式一致性框架
