kiwi binlog 设计与 raft 流程

[AlexStocks]

PikiwiDB binlog设计草稿.pptx

[AlexStocks]

PaPacificA：

1 总体架构

feature list:

• 配置管理与数据管理分离：引入额外一致性组件来维护Configuration
• 强一致性：任意时刻读取到的数据都是最新数据
• 少数派 Replica 可用时仍可读写：每个副本都有全量数据因此只要有一个副本存在即可保证读写，这样就可以保证其高可用性(AP) 的同时数据也是一致的。
• 去中心化的故障检测：通过节点间的契约机制来进行故障检测。
• First Win：由于读写流程采用了类似于 W=N 形式的 RWN，所以进行 Membership change 时，configuration manager 不用 secondary 的数据 fresh 程度，直接采用 first win 策略选举其中一个 secondary 为 primary。

some key words:

• Replica Group：互为副本的一组数据的集合，其中有一个primary，其余都是secondary
• Configuration: Replica Group的元数据，如副本有哪些，谁是primary等
• Configuration Manager: 配置一致性管理工具
• Serial Number(SN): 代表Update的执行顺序，每次update增加1
• Prepared List: Update操作的序列
• Committed List: 已经提交的update序列，是Prepared List的前缀

2 Membership change

租约与配置管理

把 membership change 这个逻辑剥离出来为一个独立的控制面 Role，极为合理，大大简化了 log-based 系统的设计。

2.1 多个 secondary 竞争 primary：first win

2.2 租约与故障检测

2.2.1 primary 故障

当 primary 故障时， secondary 在超过 grace period 没有收到 primary 的请求，就会向 Configuration Manager 发送 Reconfiguration 请求

要求将 primary 从 configuration 中移除并将自己选为 primary。多个 secondary 竞争成为 primary 时，遵循 first win 原则。

当一个 secondary 被选为 primary 后 ,它会向所有的 secondary 发送 prepare 请求，要求所有的 secondary 均以其 prepared List 为准进行对齐，当收到所有secondary 的 ack 后，primary 将自己的 commit point 移动到最后，这个时候primary 才能对外提供服务。

2.3 Add Replica

新节点加入时，首先会先成为 secondary candidate, 然后追平 primary 的prepared List, 然后申请成为 secondary。还有一种情况是之前故障的节点恢复加入，这个时候会复用之前的 prepared list 并追平 secondary 的 prepared list, 然后申请成为 secondary。

3 log replication

3.1 一致性

PacificA 的数据复制类似于 RocketMQ 的 nameserver 的 RWN，W = N，R = 1

3.2 一个 log replication 例子

3.3 多机房

多机房部署时，数据复制发生冲突：last win。PacificA 本质上对多机房复制不友好，因为 write 是所有节点都要 write 成功。

4 Read & Write

4.1 Read

该算法中，查询只能在primary上进行，primary获取自身的数据，直接返回即可

4.2 Write

更新也是在primary上发起，流程如下:

• 1 primary 为 update Request 分配一个 SN
• 2 primary 发送 prepare 请求到各 secondary，请求中包含 update Request、SN、configuration version ("It then sends the request with its configuration version and the serial number in a prepare message to all replicas. ")
• 3 各 secondary 接收到请求，校验 configuration version 成功则将 update Request 和 SN 加入到 Prepared List 中，返回 ACK 给 primary；否则返回失败；
• 4 当 primary 收到所有 secondary 的 ack 后，则执行该 update，并将 commit point 移动到该 SN。
• 5 返回执行成功

补充：step3 来自于文档这一段：

从这个图也可以看出，如果两个 replica 的某个位置 log entry 的 configuration version 与 sn 相同，则内容一定相同。

Raft 也有如下类似结论：

上面 Step3 可以认为：

• 1 PacificA 的 commit 与 apply 同时执行
• 2 所有 secondary 的 prepared list 一致
• 3 所有 applied ID == committed ID

可以看到当一个update执行成功后，primary上对应的数据已经commit，secondary上数据也被加入到了更新队列中。在这种情况下

• 读操作读取的是primary上的commitList,可以拿到更新的数据。
• secondary 中虽然数据没有被 commit，但是也被加入到了prepared List 中，当主节点挂掉时仍能保证数据不丢失。
• secondary 上的数据不能自己 commit，而必须由于 primary 来触发。这是为了应对由于异常情况导致update没有执行成功，secondary自主 commit 导致未更新成功数据被 commit，且数据领先 primary。

4.3 三个不变式

4.3.1 Primary Invariant

• 同一个时刻只有一个副本认为自己是 primary
• configuration Manager 也认为其是 primary。

从前面的故障恢复可以看到pacificA算法通过lease（契约）机制保证了这个不变式

4.3.2 Reconfiguration Invariant

• 重新配置不变式：当一个新的 primary 在 T 时刻完成 reconfiguration，那么 T 时刻之前任意节点（包括原primary）的 committed List 都是新的 primary 的 committed List 的前缀。

该不变式保证了 reconfiguration 过程中没有数据丢失，由于 update 机制保证了任意的 secondary 都有所有的数据，而 reconfiguration 重新选 primary 要求新的 primary commit 其所有的 prepare List, 因此这个不变式可以得到保证。

4.3.3 Committed Invariant

从读写流程可以推导出 committed 不变式 "Committed Invariant"。

• Secondary Committed List 为 Primary committed List 的前缀, 即 primary commit 领先于 secondary。
• Primary Committed List 为 Secondary PreparedList 的前缀，即 Secondary 拥有 primary commit 的所有数据（虽然没有committed）。其实当没有在进行 update 操作时，Secondary 的 PreparedList 和 Primary的CommittedList 是应该是一样长的。

Secondary 跃升为 Primary 后，把 prepared list 中未 committed 部分的 log entry 都推进为 committed，然后所有 secondary 都把自己的 wal 进行 append 或者 truncate，向 new primary 看齐。committed invariant 第二条确保了任何一个 secondary 的 prepared list 的数据量大于等于所有 secondary 的 committed list。

4.3.4 总结

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，使得在故障恢复后数据不会有丢失。

翻译：
基于复制协议，实现必须有效地支持三种类型的操作。

• 查询处理：在对应于提交列表的状态上处理查询。

• 协调期间的状态传输：使副本上的准备列表与新主服务器相同。二级副本上的一些未提交条目可能在状态传输过程中被移除。

• 恢复期间的状态传输：从副本传输所需部分的准备列表到加入服务器。加入服务器上的一些未提交条目可能在状态传输过程中被移除。

5 Systems

采用PacificA框架或者等效原理的开源组件有 Kafka & Pegasus：

[AlexStocks]

raft 和 PacificA：如果发生了 membership change，follower 变成 leader 后，new leader 都是以自己的全部的 wal log 为准进行 log replication，不管这里面的 log entry 是否被 committed

[AlexStocks]

PacificA 像 Raft 一样，依赖不同机器之间物理时钟不要误差太大。

其意思是：假设时钟漂移为零，只要宽限期与租约期相同或更长，租约就保证在主服务器上比在二级副本上先到期。二级副本仅在对旧主服务器的租约到期时提出配置更改以尝试承担主服务器的角色。因此，旧主服务器在新主服务器建立之前已经辞职是保证的；因此，主不变性成立。

如果时间发生了错乱，只可能导致脏读（读到旧值），但不会发生错读（读到除了 新值、旧值 意外的其他错误值）。

[AlexStocks]

PacificA WAL:

发生 failover 后，old primary 分配出去的 sn 可能会被 new primary 重新分配给 new request。

committed list 和 prepared 但未 committed 部分分开存储。

committed wal 采用 append only 方式更新，而 prepared list 不包含 committed 部分则采用 mmap 方式存储。

还有一个优化手段：secondary 从 primary 收到的任何 log entry 都立马 apply 到状态机，此时 secondary 的状态机可能比 primary 还 fresh。当 primary 宕机新 primary 就绪后，也不用推进 prepared list 了，代价就是发生 reconfiguration 时，其他 secondary 向 primary 进行全量复制。

另外一个代价就是：secondary 不得提供 query 服务。

secondary 数据比 primary 还 fresh，这当然也不利于存算分离。