分布式存储系统如何支持纠删码

Ceph 介绍

如果你已经比较熟悉 Ceph 的架构,可以直接跳到下一章。

ceph arch

Ceph 是一个去中心化的统一存储系统,同时支持对象、文件与块存储。整体的架构如上。RADOS 提供基于对象的基础存储语义,所有的服务都通过 librados 库来实现更高层级的存储语义,例如通过HTTP提供非结构化数据存储的对象存储服务RGW。

RADOS 主要由元数据结点 MON 和 数据结点 OSD 组成,在 MON 中存储关于集群的拓扑信息,在 OSD
中存储具体的数据文件。在读写过程中的路由,则通过一种高级hash算法CRUSH来完成,所以客户端都是通过将<文件名,集群拓扑>做为参数,执行相同的hash函数来得到”文件存在在哪个机器上“这个信息。

#纠删码(E/C)介绍

纠删码(E/C)广泛应用在存储技术领域,相对于传统的多副本模式,E/C 有更低的冗余率,更低存储成本。


在 E/C 编码中,有“数据块”和“编码块”两个概念。对于一个给定的文件,我们会按照配置(k+m, k 个数据块,m个编码块)将原始文件切割为 K 个数据块,然后根据编码算法来生成额外的 m 块编码块。E/C 算法可以在丢失不超过 M 块数据的情况下,通过数学运算来恢复丢失的数据块(数学原理就是抽象代数中的有限域)。


所以, E/C 编码在存储领域有如下优点:冗余小,成本低,适合做冷备存储。但是也有一些缺点:因为每个数据块都不相同,系统实现要比副本模式更复杂;故障恢复慢,要从多个结点读取数据,且需要额外的CPU load来计算编码; 小文件场景下会加重碎片化。


总之,支持 E/C 是一个存储系统很重要的特性,Ceph 在 Firefly 版本开始支持 E/C 类型的存储池,在 Luminous 版本支持 E/C Overwrite 特性。

如何支持 E/C

基础数据结构的变化

shard_t

在多副本的存储模型下,每个副本的数据都是一样的。但是在 E/C 副本的时候,每个副本保存的数据都是不同的。因此,我们需要额外的标识出每个副本是第几块。

考虑一个场景,一个 PG 从 [1,2,3,4] 变成了 [1,2,4,5],对于 OSD.4 来说,之前负责的是第四块数据,在一次变动后,变成负责第三块数据。在一些时间段,OSD.4 上可能要同时存储同一个PG的二块不同的数据。在支持 E/C 副本之前的Ceph,假定了同一个PG下的数据肯定是一样的,而在 E/C 下就麻烦了。如果只有 pg_id 和 文件名,OSD 没办法区分不同的shard,也不知道如何存储和读取这两块数据。因此,在原先的大量数据结构的基础之上,增加了 shard_id 的概念,来区别同一个PG中不同的块。具体到代码的话,也就是 pg_t -> spg_t 以及大量相应的修改。

1
2
3
4
struct spg_t {
pg_t pgid;
shard_id_t shard;
};

PGLog

对于一个 4+2 的 E/C,只要有4个数据块就可以恢复出丢失的数据。如果在一次写操作时,只有三个数据块写成功了,系统就故障了。这个时候就尴尬了,没办法通过计算补全数据到最新的版本,也没办法回退到上一个版本,数据就完全损坏了。在上述的场景下,多副本模式无论是取新版本还是旧版本,数据都是完整的。

为了解决这个问题,Ceph 对于 E/C 类型的操作,会额外的在操作日志(PGLog)中纪录:该操作是否可以回退,怎么回退。这也带来新的问题:E/C 的 PGlog 内存占用比多副本更大。

读写流程的变化

读操作

读写流程上的变化就比较好理解了。因为多副本下,每个机器上都是一样的数据,对于读操作,负责该请求的机器直接返回本机的数据就可以了。而 E/C 则需要从多个机器上把不同的数据都读回来,通过数据运算得到原始的数据并返回给用户。这带来的问题就是 E/C 的长尾比较明显了,因为一个请求的链路更长,并由最慢的结点决定整个请求的延时。为了优化这个问题,Ceph 也提供了 fast read 特性,也就是向所有副本(K+M个)发起读请求,在收到K个回应之后,就回复客户端。

overwrite 问题

在写操作方面,带来的问题就是“支持更新写比较麻烦”。这个问题详细描述就是:对于一个已经写好的文件(例如一个10M的文件),你现在要更新其中的一部分文件(例如 1M~2M 位置)。如果是多副本,系统直接覆盖就好了。在 E/C 模式下,可能是按照 1~4M 来执行 E/C 编码的,只更新 1~2M 是个非常复杂的数学问题。业界系统一般通过“读回整块文件–>计算新的数据–>写新的数据”的方式来实现。这种方式明显代价极大。在 L 版本之前,Ceph 实际上不支持 E/C 的 overwrite 的,E/C 的副本只能在 1. RGW 这类不会随机写部分文件 2. 作为 cache tier 的冷备 两种场景下。在 L 版本的 BlueStore 文件块引用计数的支持下,开始支持 E/C 的 overwrite。

PGBackend/Listener 抽象

除了上述的读写区别,E/C 与多副本还有大量的不同之处要兼容,例如:

  1. 如何判断副本数据是否静默损坏。多副本的scrub会比对副本之间是否一致,E/C 只能每个副本纪录自己的 CRC。
  2. E/C 下不再是只要有一个副本存在就可以恢复数据(min_size 配置)
  3. 多副本尽量采要新的PGLog,E/C 则不行

对于这些不同之处,Ceph 最开始期望用 PGBackend 来隔离这些差异。详细的文档可以参考 1

CRUSH 侧的支持

最重要的,要知道一点,在 CRUSH 做的所有的事情都是为了一个目的:尽量减少不必要的数据迁移。


在 E/C 模式下,每个OSD的数据都是不相同的。如果是在rep副本模式下,CRUSH 计算一个 pg 的
acting_set 是 [1,2,3,4],如果发生osdmap 变化,它的acting_set变成了 [1,3,2,4],Ceph 并不需要进行数据的迁移,因为每个人的数据是相同的。而切换到 E/C 副本模式,Ceph 就需要进行数据的迁移,将 OSD.2 和 OSD.3 的数据交换。 所以,我们要尽可能的避免这种乱序,在 osdmap 变动的情况下,每个 OSD 还尽量位于之前的位置。


在 CRUSH 算法中,有两个规则来描述如何选择 OSD,一个是 firstn,一个是 indep。在大多数情况下,firstn 满足大多数的路由需求。对于 E/C 副本,我们希望让“数据尽量少的迁移”,也就是说“尽量让每个位置选择的OSD不变”。那么如何在一个随机hash函数下达到这个目的呢?

Ceph 采用了一个很简单,也很巧妙的方式来实现。这个策略就是“让每个位置在独立的空间中选择”。简单来说,firstn 是按照 1, 2, 3, 4, 5, 6 … 这样的顺序来依次选择每个位置的OSD,而 indep 是采用 1n + k, 2n +k , 3*n +k (n 个位置来选择,选择第k个位置)… 这样的顺序来选择每个位置的OSD。

参考文档

  1. http://docs.ceph.com/docs/giant/dev/osd_internals/erasure_coding/pgbackend/