partition split设计文档

Published: Feb 6, 2020 by 何昱晨

关于partition split的基本概念和操作示例可以参照 administration/partition-split,这里将主要描述partition split的设计和实现细节。


功能简介

Pegasus在创建table时需要指定partition个数,且该个数为2的幂次。然而,在原有设计中,表的partition个数并不会随着数据量变化而动态变化。在用户的数据量和访问QPS增加,当前partition个数无法满足需求之前,我们需要人工地增加partition数目,避免阈值达到后的服务降级。

为了简化系统的设计和实现,我们这里要求增加后的partition个数必须是之前的2倍。若原partition个数为8,split后partition个数将变成16。具体来说,原partition序号为 [0, 7],split后partition序号为 [0, 15],0号partition将分裂为0号与8号,以此类推。

下图显示了表id为1,0号partition在split前后的示意图:

 +------+   +------+    +------+
 | 1.0  |   | 1.0  |    | 1.0  |
 +------+   +------+    +------+   
 primary    secondary   secondary
                |
                |
 +------+   +------+    +------+
 | 1.0  |   | 1.0  |    | 1.0  |
 | 1.8  |   | 1.8  |    | 1.8  |
 +------+   +------+    +------+   
 primary    secondary   secondary
                |
                |
 +------+   +------+    +------+   +------+   +------+    +------+
 | 1.0  |   | 1.0  |    | 1.0  |   | 1.8  |   | 1.8  |    | 1.8  |
 +------+   +------+    +------+   +------+   +------+    +------+ 
 primary    secondary   secondary  primary    secondary   secondary

整体流程

为了方便描述和画示意图,我们将整体流程分为下面3个部分:

  • 开始partition split
  • replica执行partition split
  • 注册child partition

Start partition split

  
+--------+  split   +------------+ partition_count*2 +-----------+  
| client ----------> meta_server --------------------> zookeeper |
+--------+          +------------+                   +-----------+
                          |
                          | on_config_sync
                          |
                 +--------v----------+
                 | primary partition |
                 +-------------------+
                    

开始partition split的流程如上图所示:

  1. client发送partition split请求给meta server;
  2. meta_server收到请求后,将执行如下操作:
    • 检查请求的参数,如app是否存在、partition_count是否正确等,若参数检查正常则继续执行,否则返回错误给client;
    • 修改zookeeper以及meta内存中的partition_count为新partition_count;
    • 在meta_server内存中为新增的partition初始化数据结构partition_config,并将其ballot设为-1;
    • 返回ERR_OK给client
  3. 每个partition的primary通过与meta server之间的config_sync发现meta_server同步的partition_count为本地partition_count的2倍,则开始执行本replica group的split

Execute partition split

partition split是指replica group中的每个replica一分为二的过程。一般来说,一个replica group会包括一个primary和两个secondary共三个replica,分裂后,会新增三个replica,并分别对应前面的一主两备。我们称之前的三个replica为parent,新增的为child。

partition split的过程与learn比较类似,但也有一定的区别。learn是potential secondary从primary上拷贝数据,它们位于两台不同的机器;而split是三个child分别从它们对应的parent复制数据,child与parent在同一台机器上,并在同一个盘上。因此,child可以:

  • 直接复制parent内存中的mutation,而无需对mutation进行序列化和反序列化;
  • 直接读取private log并replay private log,而无需再拷贝private log;
  • 直接apply parent生成的rocksdb checkpoint,而无需进行sst文件的拷贝。
+--------+                          +-------+
| parent |                          | child |
+--------+                          +-------+
    |         4. create child           |
    |---------------------------------->|
    |                                   |
    |         5. async learn            |
    |---------------------------------->|
    |           (2pc async)             |
    |                                   |
    |      6. finish async learn        |
    |<----------------------------------|
    |     (send to primary parent)      |
    |                                   |
    |  7. all child finish async learn  |
    |-----------------------------------|
    | (2pc sync, wait for sync_point)  |
    |                                   |
    |  8. update child partition_count  |
    |---------------------------------->|
    |                                   |
    | 9. update partition_count ack     |
    |<--------------------------------->|
    |                                   |

replica执行partition split的流程如上图所示:

  1. primary parent创建自己的child,child的ballot以及app_info.partition_count设为与parent相等,同时,让child的数据与parent位于同一块磁盘。并且,通过group_check通知各个secondary创建他们的child;
  2. child异步learn parent的状态
    • 复制parent的prepare list;
    • apply parent的checkpoint;
    • 读取private log并relay log;
    • 复制parent内存中的mutation;
    • 在这期间,parent收到的写请求也会异步地复制给child
  3. 当child完成异步复制之后,会给primary parent发送通知
  4. 当primary parent收到所有child的通知之后,将写请求改为同步复制
    • 在此后的2PC过程中,secondary都必须收到child的回复后才能向primary回复ACK,而primary也必须收到child的确认才可以commit
    • 我们将同步复制模式后的第一个decree称为同步点,当同步点mutation commit后,所有的child已拥有所需的全部数据
  5. primary通知所有的child更新partition_count为新partition_count,并把该信息写入磁盘文件.app_info中
  6. 当primary收到所有child更新partition_count成功的ack后,准备向meta_server注册child

Register child

+----------------+ 10. register child +-------------+                         +-----------+
|                |------------------->|             | 11. update child config |           |
| parent primary |                    | meta_server |------------------------>| zookeeper |
|                |<-------------------|             |                         |           |
+----------------+        ack         +-------------+                         +-----------+
        |
        | 12. active child
+-------v---------+
|  child primary  |
+-----------------+

注册child的流程如上图所示:

  1. primary向meta server注册child partition
    • 将child的ballot设为ballot(parent) + 1
    • parent暂时拒绝读写访问,此时,parent和child都不响应client的读写请求
    • 向meta_server发送注册child的请求
  2. meta_server收到注册请求后,将更新child的partition_configuration,并将它写入zookeeper和内存,然后返回ERR_OK给primary parent
  3. primary从meta_server收到注册成功的回复,先激活child:
    • 将对应的child的状态由PS_PARTITION_SPLIT改为PS_PRIMARY;
    • 这个升级为PS_PRIMARY的child会通过group_check让其它机器上的child升级为PS_SECONARY。此时, child partition可以开始提供正常的读写服务
  4. primary parent通知所有的seconadary更新app_info.partition_count,并恢复读写服务。

在第13步之前,parent与child所对应的所有读写请求都由parent处理;在第13步之后,parent将拒绝child对应的请求。

split过程中如何处理client请求

我们引入partition_version这个概念,来保证client读写数据的正确性,即,不要把数据写错地方,不要读到错误的数据,不要读不到数据。

partition_version是primary内存中的一个变量,一般应为partition_count – 1,在split过程中拒绝读写时候会被设置为-1

client在向server端发读写请求时,会在请求的header中带上所访问的hash_key的hash值,primary将此hash值与partition_version进行按位与操作,检查结果是否等于partitionId。 检查的过程用伪代码表示如下:

if partition_version == -1
    return ERR_OBJECT_NOT_FOUND
elif partition_version & hash ! = partition
    return ERR_PARENT_PARTITION_MISUSED
return ERR_OK

client收到ERR_OBJECT_NOT_FOUND时,会从meta_server更新当前partition的信息;收到ERR_PARENT_PARTITION_MISUSED时,会更新table所有partition的信息。信息更新后,再向正确的partition重发请求

下面举一个例子来分析partition_version的作用:
假设split前,table的partition个数为4,split后为8,client需要读写hash_key的hash值为5的key-value,

  1. split前,hash % partition_count = 5%4 = 1,访问replica1,正确
  2. split命令发出后
    partition_count(meta) = 8 
    ballot(replica5) = -1 
    partition_count(replica1) = 4  
    partition_version(replica1) = 4–1 = 3
    
    • 对于之前加入的client,由于缓存,partition_count(client-old) = 4,会访问replica1
    • 对于此时新加入的client,它从meta得到新的状态,partition_count(client-new) = 8,通过hash % partition_count = 5%8 = 5得知应该访问replica5,但是,ballot(replica5) = -1,client知道replica5暂不存在,所以根据hash % (partition_count / 2) = 1,会访问replica1,replica1收到请求后,检查hash & partition_version(replica1) = 5&3 = 1,正确
  3. split完成后
    partition_count(replica1) = partition_count(replica5) = 8
    partition_version(replica1) = partition_version(replica5) = 7
    
    • 对于之前的cilent,由于缓存的原因,继续访问replica1,但replica1收到请求后,检查hash & partition(replica1) = 5 % 8 = 5,由于5不等于partitionId,所以拒绝访问,并通知client从meta_server更新config,client更新后,将会访问replica5,读写也正确
    • 对于此时新加入的client,将会直接访问replica5,读写也正确

上面描述的交互依赖于一个前提,即request header中的hash必须是希望访问的hash_key的hash值,而这个假设对于绝大部分请求都成立,除了全表scan。在full_scan时,request header中的hash是partitionId,因此可能会得到冗余数据。
因此,我们为full_scan增加一步检查操作,replica server从rocksdb中读到数据后,检查数据的hash,滤除无效数据。这样,除了在split的过程中,client不会读到无效数据。由于full_scan本身不具备原子性和一致性,想完全解决一致性问题很难,而split是一个非频繁操作,我们只要让split避开full_scan的时间段就可以了。

partition_version除了用于client的访问控制,还用于无效数据清理。 partition split结束后,历史数据会同时存在于parent和child,但实际上应该分别只保留一半数据。我们同样可以使用partition_version & hash == partitionId把无效数据区分出来,并通过rocksdb filter回收清理这些数据。

异常处理

在执行partition split时,我们需要检查partition的健康状态,我们认为只有在partition健康的情况下,才会开始split。一个典型的“不健康”场景是partition正在执行learn,或者secondary数量过少。并且,replica是通过on_config_sync检查partition_count是否翻倍来判断是否需要执行split,而on_config_sync是周期性执行的,replica完全可以等到partition健康再进行split。

在执行partition split过程中,parent的ballot不能发生变化,一旦发生变化,将抛弃这个partition所有的child,重新开始split过程。即在split过程中,如果发生replica迁移,无论是因为故障还是负载均衡的原因,我们都认为本次split失败,在之后的on_config_sync中重新split。

若在partition split过程中,meta_server发生故障,meta group会选出一个新的leader,会从zookeeper中得到新的partition_count,并通过on_config_sync开始split