跨机房同步设计文档

Published: Jun 9, 2019 by 吴涛

关于热备份的基本概念和使用可以参照 administration/duplication,这里将主要描述跨机房同步的设计方案和执行细节。


背景

小米内部有些业务对服务可用性有较高要求,但又不堪每年数次机房故障的烦恼,于是向 pegasus 团队寻求帮助,希望在机房故障时,服务能够切换流量至备用机房而数据不致丢失。因为成本所限,在小米内部以双机房为主。

通常解决该问题有几种思路:

  1. 由 client 将数据同步写至两机房。这种方法较为低效,容易受跨机房专线带宽影响,并且延时高,同机房 1ms 内的写延时在跨机房下通常会放大到几十毫秒,优点是一致性强,但需要 client 实现。服务端的复杂度小,客户端的复杂度大。

  2. 使用 raft/paxos 协议进行 quorum write 实现机房间同步。这种做法需要至少 3 副本分别在 3 机房部署,延时较高但提供强一致性,因为要考虑跨集群的元信息管理,这是实现难度最大的一种方案。

  3. 在两机房下分别部署两个 pegasus 集群,集群间进行异步复制。机房 A 的数据可能会在 1 分钟后复制到机房 B,但 client 对此无感知,只感知机房 A。在机房 A 故障时,用户可以选择写机房 B。这种方案适合 最终一致性/弱一致性 要求的场景。后面会讲解我们如何实现 “最终一致性”。

基于实际业务需求考虑,我们选择方案3。

+-------+    +-------+
| +---+ |    | +---+ |
| | P +--------> S | |
| +-+-+ |    | +---+ |
|   |   |    |       |
| +-v-+ |    |       |
| | S | |    |       |
| +---+ |    |       |
+-------+    +-------+
  dead         alive

只用两机房,使用 raft 协议进行进行跨机房同步依然无法避免机房故障时的停服。(5节点同理)
          +---+                     +---+
          | A |                     | B |
          +-+-+                     +-+-+
            |                         |
+--------------------------------------------------+
|    +------v-------+          +------v-------+    |
|    |  pegasus A   <---------->  pegasus B   |    |
|    +--------------+          +--------------+    |
+--------------------------------------------------+

 虽然是各写一个机房,但理想情况下 A B 都能读到所有的数据。

架构选择

即使同样是做方案 3 的集群间异步同步,业内的做法也有不同:

  1. 各集群单副本:这种方案考虑到多集群已存在冗余的情况下,可以减少单集群内的副本数,同时既然一致性已没有保证,大可以索性脱离一致性协议,完全依赖于稳定的集群间网络,保证即使单机房宕机,损失的数据量也是仅仅几十毫秒内的请求量级。考虑机房数为 5 的时候,如果每个机房都是 3 副本,那么全量数据就是 3*5=15 副本,这时候简化为各集群单副本的方案就是几乎最自然的选择。

  2. 同步工具作为外部依赖使用:跨机房同步自然是尽可能不影响服务是最好,所以同步工具可以作为外部依赖部署,单纯访问节点磁盘的日志(WAL)并转发日志。这个方案对日志 GC 有前提条件,即日志不可以在同步完成前被删除,否则就丢数据了,但存储服务日志的 GC 是外部工具难以控制的。所以可以把日志强行保留一周以上,但缺点是磁盘空间的成本较大。同步工具作为外部依赖的优点在于稳定性强,不影响服务,缺点在于对服务的控制能力差,很难处理一些琐碎的一致性问题(后面会讲到),难以实现最终一致性

  3. 同步工具嵌入到服务内部:这种做法在工具稳定前会有一段阵痛期,即工具的稳定性影响服务的稳定性。但实现的灵活性肯定是最强的。

最初 Pegasus 的热备份方案借鉴于 HBase Replication,基本只考虑了第三种方案。而事实证明这种方案更容易保证 Pegasus 存储数据不丢的属性。

基本概念

  • duplicate_rpc
  • cluster id
  • timetag
  • confirmed_decree
+----------+     +----------+
| +------+ |     | +------+ |
| | app1 +---------> app1 | |
| +------+ |     | +------+ |
|          |     |          |
| cluster1 |     | cluster2 |
+----------+     +----------+

pegasus 的热备份以表为粒度。支持单向和双向的复制。为了运维方便,两集群表名必须一致。为了可扩展性和易用性,两集群 partition count 可不同。

                                    +------------+
                                    | +--------+ |
                               +------>replica1| |
                               |    | +--------+ |
+------------+                 |    |            |
| +--------+ |                 |    | +--------+ |
| |replica1| |                 +------>replica2| |
| +--------+ |                 |    | +--------+ |
|            +----------------->    |            |
| +--------+ |                 |    | +--------+ |
| |replica2| |                 +------>replica3| |
| +--------+ |                 |    | +--------+ |
+------------+                 |    |            |
                               |    | +--------+ |
                               +------>replica4| |
  cluster A                         | +--------+ |
                                    +------------+

                                      cluster B

duplicate_rpc

如上图所示,每个 replica (这里特指每个分片的 primary,注意 secondary 不负责热备份复制)独自复制自己的 private log 到远端,replica 之间互不影响。复制直接通过 pegasus client 来完成。每一条写入 A 的记录(如 set / multiset)都会通过 pegasus client 复制到 B。为了将热备份的写与常规写区别开,我们这里定义 duplicate_rpc 表示热备写。

A->B 的热备写,B 也同样会经由三副本的 PacificA 协议提交,并且写入 private log 中。

集群间写冲突

假设 A,B 两集群故障断连1小时,那么 B 可能在1小时后才收到来自 A 的热备写,这时候 A 的热备写可能比 B 的数据更老,我们就要引入“数据时间戳”(timestamp)的概念,避免老的写却覆盖了新的数据。

实现的方式就是在每次写之前进行一次读操作,并校验数据时间戳是否小于写的时间戳,如果是则允许写入,不是的话就忽略这个写。这个机制通常被称为 “last write wins”, 这个问题也被称作 “active-active writes collision”, 是存储系统做异步多活的常见问题和解法。

显然从“直接写”到“读后写”,多了一次读操作的开销,损害了我们的写性能。有什么做法可以优化? 事实上我们可以引入多版本机制: 多个时间戳的写可以共存, 读的时候选取最新的读。具体做法就是在每个 key 后带上时间戳, 如下:

hashkey sortkey 20190914 => value
hashkey sortkey 20190913 => value
hashkey sortkey 20190912 => value

每次读的时候可以只读时间戳最大的那一项。这种多版本读写性能更好, 但是需要改动数据编码, 我们会在后面讨论数据编码改动的问题。

两集群的写仅用时间戳会出现极偶然的情况: 时间戳冲突, 换句话说就是两集群恰好在同一时间写某个 key。为了避免两集群数据不同的情况, 我们引入 cluster_id 的概念。运维在配置热备份时需要配置各个集群的 cluster_id, 例如 A 集群为 1, B 集群为 2, 如下:

[duplication-group]
 A=1
 B=2

这样当 timestamp 相同时我们比较 cluster_id, 如 B 集群的 id 更大, 则冲突写会以 B 集群的数据为准。我们将 timestamp 和 cluster_id 结合编码为一个 uint64 整型数, 引入了 timetag 的概念。这样比较大小时只需要比较一个整数, 并且存储更紧凑。

timetag = timestamp << 8u | cluster_id << 1u | delete_tag;

confirmed_decree

热备份同时也需要容忍在 replica 主备切换下复制的进度不会丢失,例如当前 replica1 复制到日志 decree=5001,此时发生主备切换,我们不想看到 replica1 从 0 开始,所以为了能够支持 断点续传,我们引入 confirmed_decree。replica 定期向 meta 汇报当前进度(如 confirmed_decree=5001),一旦 meta 将该进度持久化至 zookeeper,当 replica 故障恢复时即可安全地从 confirmed_decree=5001 重新开始热备份。

流程

热备份相关的元信息首先会记录至 meta server 上,replica server 通过 duplication sync 定期同步元信息,包括各个分片的 confirmed_decree。

+----------+  add dup  +----------+
|  client  +----------->   meta   |
+----------+           +----+-----+
                            |
                            | duplication sync
                            |
                      +-----v-----+
                      |  replica  |
                      +-----------+

每个 replica 首先读取 private log,为了限制流量,每次只会读入一个日志块而非一整个日志文件。每一批日志统一传递给 mutation_duplicator 进行发送。mutation_duplicator 是一个接口类,目前只实现用 pegasus client 将日志分发至目标集群,未来如有需求也可接入 HBase 等系统。

+----------------------+      2
|  private_log_loader  +--------------+
+-----------^----------+              |
            | 1            +----------v----------+
 +----------+------+       | mutation_duplicator |
 |                 |       +----=----------------+
 |                 |            |
 |   private log   |            |
 |                 |     +------=----------------------+  pegasus client
 |                 |     | pegasus_mutation_duplicator +----------------->
 +-----------------+     +-----------------------------+        3

每个日志块的一批写中可能有多组 hashkey,不同的 hashkey 可以并行分发而不会影响正确性,从而可以提高热备份效率。而如果 hashkey 相同,例如 set<hashkey=”h”, sortkey=”s1”, value=”v1”> 与 set<hashkey=”h”, sortkey=”s2”, value=”v2”> 有先后关系,则它们必须串行依次发送。

当前我们的策略是每一个日志块的所有写发完毕后,再重复读日志块,发日志的过程。往后可能再做优化。

日志完整性

在引入热备份之前,Pegasus 的日志会定期被清理,无用的日志文件会被删除(通常日志的保留时间为5分钟)。但在引入热备份之后,如果有被删除的日志还没有被复制到远端集群,两集群就会数据不一致。我们引入了几个机制来保证日志的完整性,从而实现两集群的最终一致性:

GC Delay

Pegasus 认为 last_durable_decree 之后的日志即可被删除回收(Garbage Collected),因为它们已经被持久化至 rocksdb 的 sst files 中,即使宕机重启数据也不会丢失。但考虑如果热备份的进度较慢,我们则需要延后 GC,保证数据只有在 confirmed_decree 之后的日志才可被 GC。

当然我们也可以将日志 GC 的时间设置的相当长,例如一周,因为此时数据必然已复制到远端集群(什么环境下复制一条日志需要超过 1 周时间?)。最终我们没有选择这种方法。

Broadcast confirmed_decree

虽然 primary 不会 GC 那些未被热备的日志,但 secondary 并未遵守这一约定,这些丢失日志的 secondary 有朝一日也会被提拔为 primary,从而影响日志完整性。所以 primary 需要将 confirmed_decree 通过组间心跳(group check)的方式通知 secondary,保证它们不会误删日志。

+---------+            +-----------+
|         |            |           |
| primary +----------->+ secondary |
|         |            |           |
+---+-----+            +-----------+
    |       confirmed=5001
    |                  +-----------+
    |                  |           |
    +----------------->+ secondary |
                       |           |
      group check      +-----------+

这里有一个问题:由于 secondary 滞后于 primary 了解到热备份正在进行,所以在创建热备份后,secondary 有一定概率误删日志。这是一个已知的设计bug。我们会在后续引入新机制来修复该问题。

Replica Learn Step Back

当一个 replica 新加入3副本组中,由于它的数据滞后于 primary,它会通过 replica learn 来拷贝新日志以跟上组员的进度。此时从何处开始拷贝日志(称为 learn_start_decree)就是一个问题。

learnee confirmed_decree=300

+-----------------------------------+
|   +---rocksdb+---+                |
|   |              |                |
|   |  checkpoint  |                |
|   |              |                |
|   +-------last_durable_decree=500 |
|                                   |
|   +--+--+--+--+--+--+             |
|   |  |  |  |  |  |  | private log |
|   +--+--+--+--+--+--+             |
|  201                800           |
|                                   |
+-----------------------------------+

如上图显示,primary(learnee) 的完整数据集包括 rocksdb + private log,且 private log 的范围为 [201, 800]。

假设 learner 数据为空,普通情况下,此时显然日志拷贝应该从 decree=501 开始。因为小于 501 的数据全部都已经在 rocksdb checkpoint 里了,这些老旧的日志在 learn 的时候不需要再拷贝。

但考虑到热备份情况,因为 [301, 800] 的日志都还没有热备份,所以我们需要相比普通情况多复制 [301, 500] 的日志。这意味着热备份一定程度上会降低 learn 的效率,也就是降低负载均衡,数据迁移的效率。

原来从 decree=501 开始的 learn,在热备份时需要从 decree=301 开始,这个策略我们称为 “Learn Step Back”。注意虽然我们上述讨论的是 learner 数据为空的情况,但 learner 数据非空的情况同理:

learner

+-----------------------------------+
|   +--+rocksdb+---+                |
|   |              |                |
|   |  checkpoint  |                |
|   |              +                |
|   +------+last_durable_decree=500 |
|                                   |
|   +--+--+--+                      |
|   |  |  |  |  private log         |
|   +--+--+--+                      |
|  251      400                     |
|                                   |
+-----------------------------------+

我们假设 learner 已经持有 [251, 400] 的日志,下一步 learnee 将会复制 [301, 800] 的日志,与 learner 数据为空的情况相同。新的日志集将会把旧的日志集覆盖。

Sync is_duplicating to every replica

不管是考虑 GC,还是考虑 learn,我们都需要让每一个 replica 知道“自己正在进行热备份”,因为普通的表不应该考虑 GC Delay,也不应该考虑在 learn 的过程中补齐未热备份的日志,只有热备份的表需要额外考虑这些事情。所以我们需要向所有 replica 同步一个标识(is_duplicating)。

这个同步不需要考虑强一致性:不需要在 is_duplicating 的值改变时强一致地通知所有 replica。但我们需要保证在 replica learn 的过程中,该标识能够立刻同步给 learner。因此,我们让这个标识通过 config sync 同步。

Apply Learned State

原先 learner 收到 [21-60] 之间的日志后首先会放入 learn/ 目录下,然后简单地重放每一条日志并写入 rocksdb,并不会写入日志中。为了保证日志完整性,我们会将 learn/ 目录 rename 至 plog 目录,替代之前所有的日志。

                     +----+
                     | 60 |
                     +----+
                     | 59 |
                     +----+
                     +----+
  +----+             |....|   +----+
  | 51 |             +----+   | 62 |
  +----+             +----+   +----+
  | 50 |             | 21 |   | 61 |
  +----+             +----+   +----+

+-----------+     +---------+--------+
|   plog/   |     |  learn/ | cache  |
+-----------+     +---------+--------+

在 learn 的过程中,还可能有部分日志不是以文件的形式复制到 learner,而是以内存形式拷贝到 “cache” 中(我们也将此称为 “learn cache”),如上图的 [61,62]。原先这些日志只会在写入 rocksdb 后被丢弃,现在它们还需要被写至 private log 中。

最终在这样一轮 learn 完成后,我们得到的日志集如下:

                  +----+
                  | 62 |
                  +----+
                  | 61 |
                  +----+
                  | 60 |
+-----------+     +----+
|   plog/   |     | 59 |
+-----------+     +----+
                  +----+
                  |....|
                  +----+
                  +----+
                  | 21 |
                  +----+