1. 分布式存储概述
2. Ceph概述
   

在这一章中我们将会讨论Ceph是如何实现分布式存储中数据的分片和复制功能的。

PG，翻译成中文叫归置组，其作用是将一个数据对象的副本归置在一起。在Ceph的每一个Pool（数据池）中，有多个PG，每一个PG会映射到若干个OSD，每一个PG映射到的OSD的数量取决于每一份数据副本的数量（我们经常说Ceph集群是3副本的、是2副本的其实说的就是每一个数据对象副本的数量）。一个数据对象要存入Ceph集群中，首先要选择一个Pool，随后根据哈希算法选定一个PG，而PG到OSD的映射依据CRUSH算法是固定的，数据对象经过一定的复制策略（镜像或者纠删码）复制成多个副本，最后才写入到这组OSD中。

从上面的过程中不难看出PG是OSD的逻辑组合，而一个Pool中又有多个PG。每个PG的OSD组合是有可能重叠的，这就意味着PG和OSD实际上是一个多对多的关系，即一个PG中有多个OSD，一个OSD又会包含多个PG。这样的架构结合CRUSH算法能够达到使得数据对象均匀的分布在集群的每一个OSD上的目的。这在下一小节中会有详细的介绍，我们先宏观的理解一下为什么是这样。既然一个OSD上有多个PG，那么一个OSD上就会拥有多个数据对象，且来自每个PG的数据对象是各不相同的。集群中的每一个OSD上拥有的不同的数据对象越多，也就是数据被打得越分散。

举个例子来看，现在有一个三副本的Ceph集群，Pool1有4个PG，分别为PG14；集群中有8个OSD，分别为OSD18。现在PG3下的OSD有OSD5、OSD6和OSD7；而PG4下的OSD有OSD6、OSD7和OSD8。那么单独看OSD6，它上面就存储了来自PG3和PG4的数据对象。

讯享网

在上一小节中，我们讨论了Ceph中是如何使用PG来组织数据的，并且提到这样的架构结合CRUSH算法能够实现数据对象在OSD之间的均匀分布。接下来，我们就讨论CRUSH算法到底做了什么。

首先，数据为什么要在OSD之间均匀分布，这么做的好处是什么？如果数据分布的不均匀，也即有一些OSD上的数据很多，那么显然有一些OSD的资源利用是不充分的；其次，这可能会导致链式反应，即存储了大量数据的OSD崩溃，会导致大量的数据迁移，大量的数据迁移到数据量少的OSD中，又可能会导致这些OSD崩溃，整个集群就像是多米诺骨牌一样，一个接着一个倒下，这显然是不可接受的。

说到数据均匀分布，我们第一个想到的应该是hash，假设我们现在有n个OSD，那么我们可以这么描述我们的哈希算法： ，输入数据对象的id，得到一个OSD的id，模运算是为了使得OSD的id不超过OSD数量。这样的话确实可以将不同的数据对象分别分配到不同的OSD中，但是考虑到在分布式存储中，存储节点的伸缩、扩容是非常频繁的，当我们往集群中加入了一个新的节点，导致了n的变化，那么我们之前的映射就会全部失效，当大量的对象被映射到了一个新的节点之后，会伴随大量的数据迁移，效率很低。

为了解决节点数量的变化导致数据大量迁移的问题，常用的解决办法是一致性哈希算法。一致性哈希算法将每一份数据、每一个存储节点那都映射到一个哈希环中，数据对象将在环上顺时针寻找距离它最近的存储节点。这样即使有节点的新增或者当机，也不会产生大量的数据迁移：以下图为例，当节点A当机，原来分配到节点A的key-1将会分配到顺时针距离最近的节点B中。使用一致性哈希算法的优势在于，当节点数量变化只会使得跟当机节点相关的一部分数据的变化，从而解决了节点数量变化时数据大量迁移的问题。

但是一致性哈希也有它的问题：数据可能会分布不均匀。由于每一份数据都会寻找顺时针的最近节点，考虑最极端的情况，数据都在左半边，节点都在右半边，那么所有数据都会映射到右半边的第一个节点，这就违背了我们希望数据均匀分布的期望。当然，我们可以使用加入虚拟节点的策略，即，在哈希环的不同位置上创建节点的多个镜像，来解决这个问题，但这不是本文要讨论的范畴。

一致性哈希算法在Ceph这类分布式存储架构下并不奏效，因为分布式存储拥有数据的分片和复制特性，一个数据对象需要被映射到多个存储节点当中，而一致性哈希只能把数据对象映射到一个存储节点，所以CRUSH算法诞生了。CRUSH算法和一致性哈希算法的作用和目的是接近的。首先，CRUSH算法保证数据在集群的存储节点上是尽可能均匀分布的；其次，CRUSH算法保证当有新的OSD加入，或OSD当机的情况时，数据的迁移是最小的。CRUSH将PG映射到一组存储节点，所以CRUSH也可以看作是一个输入为，输出 的一个一致性哈希算法。

在CRUSH算法中，OSD被组织称了一个多叉树森林，森林中的每一棵树表达了各个OSD在物理上的位置。举个例子，一个IDC有多个机房，一个机房又有多个机柜，每一个机柜上面都摆放着多个存储节点，在这个场景下，各个OSD的物理位置可以用下面这张图来表示。

CRUSH算法要选择的目标----OSD都在树的叶子节点上。想要选到一个OSD，就需要从树的根开始做深度优先遍历，直到达到叶子节点。CRUSH算法实际上也是这么做的，但是如果说只是简单的做深度优先遍历，那么每一次选到的OSD不就是一样的了吗？以上图为例，每次我们从idc1中选择OSD时，都会选到OSD1，从idc2选择时，都会选到OSD3，这样数据分布就不均匀了。CRUSH算法引入了权重，来处理这个问题，每一个OSD都有一个权重 ，表示这个OSD承受数据负载的能力（这个值通常是管理员根据机器的配置来手动配置的）。每个非叶子节点的权重，都是其子节点的权重之和。当CRUSH执行深度优先遍历到任意一层的时候，都会根据pg_id、当前层节点的权重等参数执行一个伪随机算法来决定该从哪个节点深入到下一层，直到遍历到叶子节点，找到一个目标的OSD，这样就保证了每一次选到的OSD都可能是不同的，使得数据副本在各个OSD上均匀分布。所以说，CRUSH算法是一个深度优先遍历+伪随机的算法。

既然CRUSH是伪随机的，那么就有可能在一次选择中选中重复的OSD。如果说我们有一个三副本的集群，CRUSH每次会选择三个OSD，但是其中如果有两个重复了，那数据就不是三副本了，而是两副本了，因此重复的OSD是不可接受的。同样的，CRUSH在一次选择中也有可能选到“高负载”的或者已经挂了的机器，遇到这种选到“不满足条件”的节点的情况应该如何处理呢？CRUSH采用了非常简单粗暴的方式----重试。如果说一次选择失败了，那就在这一层继续重试，重试达到了一定次数还没成功，那就干脆退回到根重新再来。

由于数据在ceph中是分片的，每个分片又有多个复制，数据副本的放置策略讨论的问题是：如何放置这些分片，才能够保证数据的可靠性。即，如何放置分片，才能够保证在一部分节点当机时，我们的数据不丢失？这里就要引入一个叫做失效域的概念，所谓失效域，就是我们预设整个分布式存储系统发生故障的最大单位，注意，是最大单位。举个例子，我们可以预设整个系统里面的失效域是OSD，也就是我们认为这个系统最糟糕的情况就是OSD故障了，OSD之上的机柜、机房、idc都不可能或者极小概率出现故障；我们当然也可以预设整个系统里面的失效域是idc，即我们认为整个idc是有概率整个挂掉的，且我们也有极高的数据可靠性需求，必须要做跨idc的容灾。当我们说失效域是OSD，表达的意思其实是，我们希望同一个数据对象的副本分布在不同的OSD上，这样一个OSD挂了，我们还有其他的OSD还有数据副本，数据不至于丢失；当我们说失效域是idc时，我们希望同一个数据对象的副本分布在不同的idc上，这样就算一个idc挂了，我们在其他的idc还有数据副本。如何定义失效域取决于系统中对数据可靠性的要求，在Ceph中定义失效域是非常灵活的，我们可以定义上一节物理层次结构中的任意一层作为失效域。

接下来，我们来研究当集群中有节点当机或者有新的节点加入时会发生什么，来进一步理解Ceph中数据副本的放置策略。假设我们有一个失效域为OSD的集群，各个节点的权重如下图所示。

当一个OSD出现故障时，这个OSD仍然会留在树中，并不会被移除，但是这个故障的OSD并不会被CRUSH算法选中了。当一个OSD当机时，Ceph会重新运行CRUSH算法，将这个OSD上的数据对象迁移到其他健康的OSD中。举个例子，当OSD2出现故障，OSD2上所有的PG会重新执行CRUSH算法，将这个PG映射到一组新的OSD中。注意这里重新映射并不会导致大量的数据迁移，因为CRUSH算法是一致的，对于一个PG在不出现任何故障的情况下，每次得到的OSD集合都是一样的。当OSD2出现故障时，CRUSH算法在选中OSD2时会进行重试，选中一个新的OSD，那些没有故障的OSD仍然会出现在结果中。所以，这里重新映射的含义其实是将OSD2经过重新映射替换为一个健康的OSD。重新映射从而导致的数据迁移，宏观上来看也只是把OSD2中的数据迁移到了其他健康的OSD中，从权重的角度出发，这一次故障仅仅导致1/7的数据发生迁移。

当一个新的OSD被加入集群时，情况会更复杂一些，因为这会直接导致树的结构变化，树的结构变化会导致权重发生变化，权重变化了会影响数据的放置策略。举个例子，当机柜5下新增了一个OSD8，其权重被设定为1，那么这会导致从根节点到OSD8上所有的节点权重+1，这会影响idc1下所有的数据副本重新分布，当CRUSH算法重新执行后，更多的数据将会分布到权重更高的机房3中。

数据复制的目的是提高数据的可靠性，在分布式存储领域，有两种数据复制策略：镜像和纠删码（Erasure Code）

镜像策略非常的简单，就是将一个数据块复制成n个完全相同的数据块。这种策略可以容忍至多n-1个数据块的丢失。镜像策略虽然很简单，但是存在一个问题：存储利用率很低。一份数据本来只占1份存储空间，经过复制之后就占了n份存储空间，存储利用率只有1/n。因此，就有人考虑有没有一种在提供类似保障级别的前提下，存储利用率更高的复制算法，纠删码就此被引入分布式存储。假设现在有n个数据块，纠删码算法在这n个块的基础上加上m个校验块，组成总共n+m个数据块，它可以容忍最多m个数据块的丢失，切存储利用率达到n/(m+n)，相较于镜像策略有显著的提升。然而，纠删码的数据恢复和写入速度都不如镜像策略，这是因为纠删码的内部实现导致的。在数据恢复时纠删码策略会通过未丢失的校验块和数据块恢复数据；而在写入数据时，纠删码策略会重新计算校验块，这都会造成额外的开销。

由于两种复制策略不同的特性，它们往往被用于不同的场景下。镜像策略由于性能较好，常被用于存放热数据的场景；纠删码由于存储利用率较高，因此被用于存放冷数据或是只读数据。Ceph同时兼容了这两种复制策略，当使用镜像策略的时候还需要考虑各个副本之间数据的一致性，这将在下一小节中进行介绍。

当使用镜像复制策略时，由于各个数据副本之间是对等的，因此需要保证同一个数据副本在不同的OSD上是一致的。在数据写入阶段，通过类似“同步复制”的机制，保证客户端在收到写入成功的返回之后，数据副本在OSD之间是一致的。

当数据对象写入时，它被复制成若干个副本，每个副本都会放在一个OSD上（通过CRUSH算法做映射，详见“CRUSH算法”一节）。存放相同数据对象的这一组OSD被称为一个PG（详见“PG”一节）。这一组OSD可以看作是一个小的OSD集群，这个集群拥有一个主节点（主节点被定义为CRUSH算法返回结果序列中的第一个OSD）所有的写操作会打到主OSD上，主OSD再通过一些同步策略，将这次写入同步到所有的从OSD上。

Ceph中的主从同步策略有以下三种：

1. 主复制（Primary Copy）：当主OSD收到写请求，会并行的将此次更新同步到从OSD，当收到所有从OSD的ack之后，会由主节点返回写入成功到客户端，读操作由主OSD处理
2. 链式复制（Chain）：当主OSD收到写请求，会将写请求首先发送到第一个从OSD，第一个从OSD收到后发送到第二个从OSD，以此类推，直到最后一个从OSD写入成功，由最后一个从OSD返回写入成功到客户端，读请求由最后一个OSD处理
3. 分叉复制（Splay）：这种方式实际上是上面两种方法的“杂交版”，当主OSD收到写请求，会并行的将此次更新同步到从OSD，当最后一个OSD写入成功，之后返回写入成功到客户端，读请求由最后一个OSD处理

这三种复制策略，各有优劣。从写入延迟的角度来看，链式复制延时最高，因为链式复制的数据副本是依次传递的，传递到最后一个OSD写入成功后才会返回ack，而主复制和分叉复制策略的数据副本都是并行传递的；从负载均衡的角度来看，读写都集中在主OSD上，而链式复制和分叉复制都由最后一个从OSD分担读请求。这三种复制策略本质上都是同步复制，从而保证了数据副本在不同OSD之间的强一致性，无论采用哪种复制策略，只有当数据副本在每一个OSD上都被持久化了，客户端才会收到写入成功的ack。

1. 一份数据在写入时会经过分片分成若干个数据对象，其中每一个数据对象经过复制策略（镜像或纠删码）复制成若干个数据副本，数据对象通过哈希算法映射到PG，PG又经过CRUSH算法映射到若干个OSD用来存放同一个数据对象的数据副本。PG是OSD的逻辑组合，PG和OSD是多对多的关系，OSD上存放的PG实例数量越多，数据在整个集群内就越分散。
2. CRUSH算法将PG映射到不同的OSD组合使得数据对象在OSD之间均匀分布，同时当集群的OSD数量发生变化时，可以保证尽可能少的数据迁移，具有去中心化、高性能等优点。与此同时，其缺点也是非常明显的----当集群需要升级，且升级涉及到CRUSH算法，可能会导致大量的数据迁移，这为集群的升级增添了阻碍。
3. 数据副本在写入PG时，会先写入PG内的主OSD，再由主OSD通过主从同步，同步到从OSD。主从同步策略有主复制、链式复制和分叉复制三种。这三种策略都要求数据副本的强一致性，但是在负载均衡、写入延时等方面各有优劣。

1. 一致性哈希的原理
2. RADOS论文原文
3. CRUSH论文原文