partition split

[shengofsun]

partition split

最主要的考虑点

split的动作，在primary和secondary之间最好在同样的decree点之后发生。这样，对于某条写请求，可以明确的界定是由parent分片负责还是child分片负责。

如果没有规定一个固定的decree点，某个请求在不同副本间可能会由不同的partition负责，会有一些胡乱。

一种思路：2pc split

如果把split动作做成一个mutation, 走一致性协议。那么究竟在哪个点进行split,副本间就可以达到统一的共识了。事实上一致性协议就是干这件事情的，它本来就是用来保证主从之间的“复制状态机”的，如果把split也作为一种主从间的状态变化的话，这种做法是非常自然的。

mutation重放的问题

1. 对于一条已经commit的split message 我们只要强制要求这条message必须flush/durable就行。这样replica在重启的时候是不会重放这条mutation的。

2. 如果replica group发生了configuration变化，mutation也不会发生重放。这是我们的一致性协议保证的：

   • 一个没有commit的mutation, 只会把ballot变一下然后重新2pc, 而把原来的message给覆盖掉。
   • 一个已经commit了的message, 不会因为replica group的变化而重放。

3. 退一步讲：果给每一条split的mutation指定好partition version，也就是说“本split希望partition count是从几变到几”，那么即使一个mutation要执行两次，貌似也不会有影响？因为我们可以在apply这条mutation的时候判断这个split还有没有必要做。

   而且由于一致性协议的保证，这条mutation即便进行了重放，在三个副本之间的行为也是一模一样的。

primary如何apply "split mutation"

1. 首先像所有的write mutation一样，先prepare，等所有的副本都prepare之后，primary就可以commit了。

2. commit时候，replica要：

   • 初始化一个新的空replica
   • clone一份storage_engine出来; 如果是rocksdb, 需要打hardlink
   • clone一份private log出来
   • clone replica相关的所有数据结构：replica config, primary context, secondary context，cold_backup_context, replica_config
   • 对于context里面涉及到的一些task需要做一些更为细致的讨论。对于常规任务类型的task，需要重新启动一个新的task: 比如各种timer, 以及冷备的rpc，热备的任务等等。其他的一些任务则需要把task置空

   replica的commit过程就有点像进程的fork：复制内存镜像，对内核的数据结构做修改；我们需要做的是复制数据，对各种控制行为做修改。

   可能这里会觉得commit的过程过于繁琐。但不管怎样的split方案，一个replica一分为二后，里面所对应的各种控制行为该怎么变化都是需要细致的考虑的。

   这也是我喜欢2pc的原因，精确的相同decree点上的split, 能让我们更好的对“split前后parent、child”的行为做思考和控制。

3. primary在commit之后，split结束。

secondary如何applit "split mutation"

secondary的split过程和primary基本相同。但由于是2pc, primary在split结束后，secondary还没有split。

只有等新的一条mutation后发出后，才会推动secondary的commit。这条mutattion可能是一条普通的写，也可能是一条group check。但这条mutation一定得是parent发出的一条mutation; 如果是child, 它会发现其他副本还不存在这个partition而被拒绝掉，这里我们需要特殊处理下：

• 在prepare阶段，如果因为partition version太低而发生的partition不存在，primary应该delay重试，而不是踢掉secondary。

split时候的一些其他问题

1. 需要修改下clientlet, 让child partition标志为还没有被任何线程access过，因为parent和child可能会被分派到不同的线程池

split的时候发生replica group变化

因为replica的所有状态变化都是线性的，所以这里可以明确的讨论：

• 变化发生在split之前，这个变化和split没有关系
• 变化发生在split之后。
  • 首先：split已经commit, 所以重放是不会发生的。
  • 其次，如果一个secondary升级成primary。那么就需要考虑这条mutation在这个secondary这里有没有提交。提交了就没啥影响；如果没有提交，就会因为提交而secondary也发生split。

split之前的learner和split之后的primary

设想一种场景：learner的decree在split之前，而primary已经是split之后了；在这种情况下，如果简单的learn会导致learner面对"split的mutation"无所适从。

这里我们可以简单处理：如果partition的version不一致，强制要求"learn from scratch"。

另一种方式是跳过split的控制命令。

和meta的交互

meta在下发split消息的时候，可以通过config sync，也可以通过单独的命令。

当primary在完成split的时候，需要通知meta说split已经完成，这时meta会更新remote-storage, 把parent和child的partition configuration都更新一下，在此之前，child的partition configuration为空。

config-sync的时候，如果因为partition version不一致而导致replica-server上缺乏一些partition，可以暂时先忽略掉。因为split的mutation是走过两阶段提交的，这条mutation一定会发生，而不会丢失。

和client的交互

和之前的设计应该可以维持一致。

优化

1. replica clone的时候阻塞write线程池的问题：应该可以拿到后台线程做的。
2. split的时候不停写：只要保证split后面的东西暂时不commit就可以了。
   • 可以放宽读写一致性的要求：在三副本prepare完了之后就立马回复client端成功(目前实现一下可能要改接口)

另一种思路：控制命令式split(TBD)

大概想了下：split如果没有同步点，在prepare的时候会比较混乱。如果也走这种“通知secondary-等待回复”的流程，其实和走2pc也差不多。

另外需要考虑下，primary split完成、通知meta修改partition config，primary挂了之后的一些情况

[qinzuoyan]

我比较同意，咱们不要做过度优化，在保证正确性的前提下，用风险最小的方案。另外这个季度只有一个月了，在时间上我们也要抓紧了。

[hycdong]

总结一下5月30号对partition split功能讨论的结果。

方案讨论

讨论的有以下三种方案：

1. 远南的思路 - child异步learn，partition都完成split后向meta register child partition
   拒绝写时间：从primary向meta发出register child partition请求 -> 收到meta register ERR_OK
2. 两阶段提交，且将split请求添加到mutation log中，只要primary完成split将向meta register所有child partition
   停写时间为：split 请求发出 -> primary register all child partition
3. 两阶段提交，请求不基于mutation log实现，所有partition都完成split后向meta register child partition
   停写时间为：split请求发出 -> primary register all child partition

三种方案各有利弊：

• 方案1：
  • 优点：工作量较小，拒绝客户端写耗时最短
  • 缺点：异步learn较为复杂，增加逻辑理解难度
• 方案2：
  • 优点：逻辑理解较为简单，与方案三相比停写时间稍短
  • 缺点：需要对多个模块进行修改，corner case较多
• 方案3：
  • 优点：逻辑理解较为简单
  • 缺点：停写时间较长

讨论结论

为了保证正确性，尽快实现功能，现在暂时将采用方案1，但仍会对方案二的corner case进行思考，若停写时间能够在可接受范围，并且能够梳理清逻辑且实现不复杂，可以改为方案2，对该方案的讨论和需要理顺的corner case如下

2pc + mutation方案讨论

方案概述

通过mutation log和两阶段提交实现split功能大致分为以下4个步骤：

1. primary prepare
2. secondary prepare
3. 收到所有secondary prepare完成后primary commit
4. secondary异步commit

其中，第3步完成后及认为split完成，而commit阶段需要大致完成如下步骤：

1. 根据parent创建一个新的replica实例
2. 给当前rocksdb打checkpoint
3. 复制private log文件，mutation等结构
4. （仅primary）向meta发送register all child replica

方案所需特殊处理和边界思考

以下思考为对讨论的总结，更详细的可参见@伟杰的第一个comment

• 需要对在primary注册child partition到secondary commit之间的写请求进行特殊处理
• 出错处理思考：
  • 如何处理split时的learner
  • 如何处理对split mutation的replay问题

[hycdong]

Partition split is developed and tested, I will split my code into several pull requests and merge them into master. Here are the normal partition split process:

1. shell -> meta to start partition split
2. meta
   • update partition count */= 2 on zk and meta server split: meta start partition split #286
3. replica
   • parent notice partition count changed in on_config_sync
   • parent init child replica instance split: parent replica create child replica #291
   • parent prepare its own state (prepare list, mutation, private log) feat(split): parent replica prepare states #299
   • child async learn
   • child notify parent primary finish split
   • child group update partition count
   • group child catch, check sync_point and stop read and write
   • primary -> meta to register child partition
4. meta
   • meta register child on zk
   • meta register child on meta server local
   • send ack to primary
5. replica
   • parent group update partition count
   • parent active child
   • primary recover read and write