Geo-replication: 从 Copysets 到 Tiered Replication

作者 : 开心源码 本文共2545个字,预计阅读时间需要7分钟 发布时间: 2022-05-12 共172人阅读

对于分布式存储系统,我们都会使用多副本的机制来保证数据的安全性。譬如对于 TiKV 来说,我们默认会使用 3 个副本,假如需要更高等级的安全性,譬如在银行领域,我们则会使用 5 个副本。但无论使用几个副本,我们都会面临一个问题,我们如何在集群中放置这些副本。

机器都是有寿命的,磁盘,内存等硬件在运行的时候也时不时会坏掉。假设现在我们使用 3 个副本,有 N 台机器,假如同时有 3 台机器坏掉,而悲催的是恰好 3 个副本在这 3 台机器上面,那么我们就会面临数据丢失问题。所以我们需要尽量减少数据丢失的概率。

Random replication

最简单的做法就是选择任意 3 台机器来放置副本,但是这个策略其实不好。假设机器坏掉的概率是 1%,对于 3 副原本说,同时坏掉的概率是 0.0001%,看起来这个是很低的,但实际中,我们不光只有一份数据。

在 TiKV 里面我们会将数据切分成多个 region,每个 region 对应一份数据,在实际生产环境中,region 数量是非常多的,少量集群都已经过了百万了,这时候假如有 3 个节点同时损坏,少量 region 副本全丢掉的概率会非常的大。

下图是 Copysets paper 里面给出的数据,可以看到,那么随着节点数的增多,使用随机复制方式的 3 副本掉数据的概率会急剧的增大:

Copysets replication

为理解决 Random replication 的问题,有人提出了 Copysets,也就是论文 Copysets: Reducing the Frequency of Data Loss in Cloud Storage,相比于使用 random 方式,Copysets 引入了 scatter width,将整个集群节点进行分组,而后在分组的集合里面选择节点进行复制。

Copysets 的算法其实比较简单,假设集群数量是 N,复制因子是 R(其实就是选择几个副本),scatter width 是 S,那么:

  1. 创立 S / (R - 1) 个节点排列
  2. 将每个排队分成 R 组
  3. 随机选择一个节点当成副本的 primary 副本
  4. 在分组的包含 primary 节点的集合里面随机选择 secondary 副本

譬如,假设我们有 9 个节点,R 是 3,而 S 是 2,那么就有 2 / (3 - 1) = 1 个排列,譬如 [1, 6, 5, 3, 4, 8, 9, 7, 2],而后我们分成 3 组,也就是 [1, 6, 5], [3, 4, 8], [9, 7, 2]。

对于 3 副本,假设我们选择 1 作为 primary 副本存放的节点,那么剩下两个 secondary 副本只能在 6 和 5 上面选取。

使用 Copysets,能有效的降低丢失数据的概率,根据 Paper 里面形容,在 5000 个节点下面,假如有 1% 的节点同时挂掉,random 丢失的概率是 99.99%,而 Copysets 则是 0.15%。

Tiered Replication

当然,copysets 并不是银弹,它并不能处理集群动态扩容的问题,于是 copysets 的作者,继续研究了另一个处理方案,也就是 Tiered replication,Paper 是 Tiered Replication: A Cost-effective Alternative to Full Cluster Geo-replication。

Tiered Replication 的原理其实也比较简单,依然有 Copysets 的概念 scatter width S,会将整个集群分成多个 Copysets,每个 Copysets 的大小是 R,对于每个节点,必需保证它至少在 S 个 Copysets 里面。另外,Tiered Replication 里面也有 primary 和 backup 节点的区分,通常两个副本会放在 primary 节点里面,而第三个副本则会放到 backup 节点里面。

Tiered Replication 的算法比较简单,大概来说:

  1. 所有节点开始的 scatter width 是 0,也就是没有属于任何 Copysets。
  2. 创立一个 Copysets,选择最小 scatter width 的 R 个节点加进去。
  3. 重复上面的过程,直到所有的节点的 scatter width 至少是 S。

详细的算法可以看 Paper,而源码在这里,使用起来还是很简单的,譬如:

# not rack aware>>> trepl.build_copysets(['node1', 'node2', 'node3'], R=2, S=1)[['node1', 'node2'], ['node1', 'node3']]# rack aware, node1 and node2 can not share a copyset since they're in# the same rack>>> rack_map = { 'node1': 'rack1', 'node2': 'rack1', 'node3': 'rack3' }>>> trepl.build_copysets(      rack_map.keys(), R=2, S=1,      checker=trepl.checkers.rack(rack_map),    )[['node1', 'node3'], ['node2', 'node3']]

对于集群的动态升级,譬如新加入一个节点,就直接按照上面的算法,将这个节点加入到不同的 Copysets 里面,直到这个新加入的节点的 scatter width 为 S。而对于删除节点,一个简单的做法就是将包含这个删除节点的 Copysets 干掉,而在这些 Copysets 里面的其余正常节点的 scatter with 也会减少,而后会创立新的 Copysets 替换老的。在老的 Copysets 里面的正常副本可能会重新复制到其余节点上面。

总结

说了这么多,对 TiKV 来说有什么借鉴意义呢?现在 TiKV 是通过打 label 的方式来支持 Geo-replication 的,假设我有 3 个 Rack,每个 IDC 有 3 台机器,我们会给每个启动在机器上面的 TiKV 进程打上相似 rack = rack1, host = host11 这样的标签,PD 就会将 3 个副本分散到不同 Rack 的不同机器上面,但在 Rack 机器的选择上面,我们还是一个 random 算法。也就是说,即便能保证副本在不同的 Rack 上面,但随着每个 Rack 机器数量的增多,我们 3 副本同时丢失的概率就会增大,所以自然需要一个更好的副本复制策略。假如你对这方面感兴趣,欢迎联络我 tl@pingcap.com。

上一篇 目录 已是最后

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » Geo-replication: 从 Copysets 到 Tiered Replication

发表回复