Ceph 02

Ceph

CRUSH算法简介

CRUSH即Controlled Replication Under Scalable Hashing，Ceph 使用 CRUSH 算法把客户端数据保存为存储池内对象， 可以计算出哪个归置组（PG）应该持有指定的对象(Object)，然后进一步计算出哪个 OSD 守护进程持有该归置组。 CRUSH 算法使得 Ceph 存储集群能够动态地伸缩、再均衡和修复。

Hash算法

散列法（Hashing）或哈希法是一种将字符组成的字符串转换为固定长度的数值或索引值的方法，称为散列法，也叫哈希法。由于通过更短的哈希值比用原始值进行数据库搜索更快，这种方法一般用来在数据库中建立索引并进行搜索，同时还用在各种解密算法中。
比如想要搜索人名，直接搜索有太多可能，而通过Hash算法可以将人名用更少量的数字表示，这样，下次搜索名字时，就先搜索哈希并对数据库中的每个值进行一一对应。通常来讲，寻找数字比寻找未知长度的字符串要来得快得多。毕竟寻找数字时每一位只有10种可能，而名字的长度未定，且每一位都有更多种可能。

是什么

随着大规模分布式系统的出现，系统必须能够平均的分布数据和负载，最大化系统的利用率，并且能够处理系统的扩展和系统故障。一般的分布式系统都会采用一个或者多个中心服务用来控制数据的分布，这种机制使得每次IO操作都会先去一个地方查询数据在集群中的元数据信息。当集群的规模变大或者系统的workload比较大时，这些中心服务器必然会成为性能上的瓶颈。Ceph摒弃了这种做法，而是通过引入CRUSH算法，将数据分布的查询操作变成了计算操作，并且是在client端完成。

CRUSH是受控复制的分布式hash算法，是ceph里面用于控制数据分布的一种方法，能够高效稳定的将数据分布在普通的结构化的集群中。它是一种伪随机的算法，在相同的环境下，相似的输入得到的结果之间没有相关性，相同的输入得到的结果是确定的。它只需要一个集群的描述地图和一些规则就可以根据一个整型的输入得到存放数据的一个设备列表。Client在有IO操作的时候，可能会执行CRUSH算法。

与哈希和一致性哈希相比，哈希的问题在于数据增长时不能动态加Bucket，一致性哈希的问题在于加Bucket时数据迁移量比较大，其他数据分发算法依赖中心的Metadata服务器来存储元数据效率较低，CRUSH则是通过计算、接受多维参数的来解决动态数据分发的场景。CRUSH能够处理存储设备的添加和移除，并最小化由于存储设备的的添加和移动而导致的数据迁移。

CRUSH有两个关键优点：
1. 任何组件都可以独立计算出每个object所在的位置(去中心化)。
2. 只需要很少的元数据(cluster map)，只要当删除添加设备时，这些元数据才需要改变。

CRUSH通过 Object --> PG --> OSD 模型，在分配过程（-->）中进行伪随机计算，相对随机平均地把数据分布储存到各个底层上；且在查找数据时是通过底层计算得到储存位置的；同时对数据进行增删转移时也不会有过多的改变。

结构

CRUSH是基于一张描述当前集群资源状态的map（Crush map）按照一定的规则（Rules）得到这个OSD列表的。Ceph将系统的所有硬件资源描述成一个树状结构，然后再基于这个结构按照一定的容错规则生成一个逻辑上的树形结构作为Crush map，树的叶子节点是OSD。

OSD MAP：包含当前所有pool的状态和OSD的状态。OSD Map管理当前ceph中所有的OSD，OSD Map规定了crush算法的一个范围，在这个范围中选择OSD结合。OSDMap其实就是一个树形的结构，叶子节点是device，其他的节点称为bucket节点，这些bucket都是虚构的节点，可以根据物理结构进行抽象，当然树形结构只有一个最终的根节点称之为root节点，中间虚拟的bucket节点可以是数据中心抽象、机房抽象、机架抽象、主机抽象等。

Bucket类型

不同Bucket的算法复杂度和数据迁移大小不同，CRUSH定义了4种类型的buckets来代表集群架构中的叶子节点：一般的buckets、列表式buckets、树结构buckets以及稻草类型buckets。每个类型的bucket都是建立在不同的内部数据结构和充分利用不同函数的基础上，这些buckets在计算和重构效率上发挥着不同的权衡性。

一般 Buckets（Uniform Buckets）：适用于具有相同权重的item，而且bucket很少添加删除item。它的查找速度是最快的。

列表式 Buckets（List Buckets）：它的结构是链表结构，所包含的item可以具有任意的权重。CRUSH从表头开始查找副本的位置，它先得到表头item的权重Wh、剩余链表中所有item的权重之和Ws，然后根据hash(x, r, item)得到一个[0~1]的值v，假如这个值v在[0~Wh/Ws)之中，则副本在表头item中，并返回表头item的id。否者继续遍历剩余的链表。

树结构 Buckets（Tree Buckets）：链表的查找复杂度是O(n)，决策树的查找复杂度是O(log n)。item是决策树的叶子节点，决策树中的其他节点知道它左右子树的权重，节点的权重等于左右子树的权重之和。CRUSH从root节点开始查找副本的位置，它先得到节点的左子树的权重Wl，得到节点的权重Wn，然后根据hash(x, r, node_id)得到一个[0~1]的值v，假如这个值v在[0~Wl/Wn)中，则副本在左子树中，否者在右子树中。继续遍历节点，直到到达叶子节点。Tree Bucket的关键是当添加删除叶子节点时，决策树中的其他节点的node_id不变。决策树中节点的node_id的标识是根据对二叉树的中序遍历来决定的(node_id不等于item的id，也不等于节点的权重)。

稻草类型 Buckets（Straw Buckets）：这种类型让bucket所包含的所有item公平的竞争(不像list和tree一样需要遍历)。这种算法就像抽签一样，所有的item都有机会被抽中(只有最长的签才能被抽中)。 hash(x, r, i))。

参考：

https://blog.csdn.net/scaleqiao/article/details/46958467
https://www.cnblogs.com/chenxianpao/p/5568207.html
https://blog.csdn.net/xingkong_678/article/details/51526627