共计 3431 个字符，预计需要花费 9 分钟才能阅读完成。
丸趣 TV 小编给大家分享一下 ceph 中 CRUSH 数据分布算法有什么用，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！
ceph 的 CRUSH 数据分布算法介绍
CRUSH 是 ceph 的一个模块，主要解决可控、可扩展、去中心化的数据副本分布问题。
1 摘要
随着大规模分布式存储系统 (PB 级的数据和成百上千台存储设备) 的出现。这些系统必须平衡的分布数据和负载(提高资源利用率)，最大化系统的性能，并要处理系统的扩展和硬件失效。ceph 设计了 CRUSH(一个可扩展的伪随机数据分布算法)，用在分布式对象存储系统上，可以有效映射数据对象到存储设备上(不需要中心设备)。因为大型系统的结构式动态变化的，CRUSH 能够处理存储设备的添加和移除，并最小化由于存储设备的的添加和移动而导致的数据迁移。
2 简介
对象存储设备 (object-based storage devices) 管理磁盘数据块的分配，并提供对象的读写接口。在一些对象存储系统中，每个文件的数据被分成多个对象，这些对象分布在整个存储集群中。对象存储系统简化了数据层(把数据块列表换成对象列表，并把低级的数据块分配问题交个各个设备)。对象存储系统的基本问题是如何分布数据到上千个存储设备上。
一个 robust 解决方案是把数据随机分布到存储设备上，这个方法能够保证负载均衡，保证新旧数据混合在一起。但是简单 HASH 分布不能有效处理设备数量的变化，导致大量数据迁移。ceph 开发了 CRUSH（Controoled Replication Under Scalable Hashing），一种伪随机数据分布算法，它能够在层级结构的存储集群中有效的分布对象的副本。CRUSH 实现了一种伪随机 (确定性) 的函数，它的参数是 object id 或 object group id，并返回一组存储设备(用于保存 object 副本)。CRUSH 需要 cluster map(描述存储集群的层级结构)、和副本分布策略(rule)。
CRUSH 有两个关键优点：
任何组件都可以独立计算出每个 object 所在的位置(去中心化)。
只需要很少的元数据(cluster map)，只要当删除添加设备时，这些元数据才需要改变。
3 CRUSH 算法
CRUSH 算法通过每个设备的权重来计算数据对象的分布。对象分布是由 cluster map 和 data distribution policy 决定的。cluster map 描述了可用存储资源和层级结构(比如有多少个机架，每个机架上有多少个服务器，每个服务器上有多少个磁盘)。data distribution policy 由 placement rules 组成。rule 决定了每个数据对象有多少个副本，这些副本存储的限制条件(比如 3 个副本放在不同的机架中)。
CRUSH 算出 x 到一组 OSD 集合(OSD 是对象存储设备)：
(osd0, osd1, osd2 … osdn) = CRUSH(x)
CRUSH 利用多参数 HASH 函数，HASH 函数中的参数包括 x，使得从 x 到 OSD 集合是确定性的和独立的。CRUSH 只使用了 cluster map、placement rules、x。CRUSH 是伪随机算法，相似输入的结果之间没有相关性。
3.1 层级的 Cluster map
Cluster map 由 device 和 bucket 组成，它们都有 id 和权重值。Bucket 可以包含任意数量 item。item 可以都是的 devices 或者都是 buckets。管理员控制存储设备的权重。权重和存储设备的容量有关。Bucket 的权重被定义为它所包含所有 item 的权重之和。CRUSH 基于 4 种不同的 bucket type，每种有不同的选择算法。
3.2 副本分布
副本在存储设备上的分布影响数据的安全。cluster map 反应了存储系统的物理结构。CRUSH placement policies 决定把对象副本分布在不同的区域(某个区域发生故障时并不会影响其他区域)。每个 rule 包含一系列操作(用在层级结构上)。
这些操作包括：
tack(a)：选择一个 item，一般是 bucket，并返回 bucket 所包含的所有 item。这些 item 是后续操作的参数，这些 item 组成向量 i。
select(n, t)：迭代操作每个 item(向量 i 中的 item)，对于每个 item(向量 i 中的 item)向下遍历 (遍历这个 item 所包含的 item)，都返回 n 个不同的 item(type 为 t 的 item)，并把这些 item 都放到向量 i 中。select 函数会调用 c(r, x) 函数，这个函数会在每个 bucket 中伪随机选择一个 item。
emit：把向量 i 放到 result 中。
存储设备有一个确定的类型。每个 bucket 都有 type 属性值，用于区分不同的 bucket 类型(比如”row”、”rack”、”host”等，type 可以自定义)。rules 可以包含多个 take 和 emit 语句块，这样就允许从不同的存储池中选择副本的 storage target。
3.3 冲突、故障、超载
select(n, t)操作会循环选择第 r=1,…,n 个副本，r 作为选择参数。在这个过程中，假如选择到的 item 遇到三种情况 (冲突，故障，超载) 时，CRUSH 会拒绝选择这个 item，并使用 r (r’和 r、出错次数、firstn 参数有关)作为选择参数重新选择 item。
冲突：这个 item 已经在向量 i 中，已被选择。
故障：设备发生故障，不能被选择。
超载：设备使用容量超过警戒线，没有剩余空间保存数据对象。
故障设备和超载设备会在 cluster map 上标记(还留在系统中)，这样避免了不必要的数据迁移。
3.4 MAP 改变和数据迁移
当添加移除存储设备，或有存储设备发生故障时(cluster map 发生改变时)，存储系统中的数据会发生迁移。好的数据分布算法可以最小化数据迁移大小。
3.5 Bucket 的类型
CRUSH 映射算法解决了效率和扩展性这两个矛盾的目标。而且当存储集群发生变化时，可以最小化数据迁移，并重新恢复平衡分布。CRUSH 定义了四种具有不同算法的的 buckets。每种 bucket 基于不同的数据结构，并有不同的 c(r,x)伪随机选择函数。
不同的 bucket 有不同的性能和特性：
Uniform Buckets：适用于具有相同权重的 item，而且 bucket 很少添加删除 item。它的查找速度是最快的。
List Buckets：它的结构是链表结构，所包含的 item 可以具有任意的权重。CRUSH 从表头开始查找副本的位置，它先得到表头 item 的权重 Wh、剩余链表中所有 item 的权重之和 Ws，然后根据 hash(x, r, item)得到一个 [0~1] 的值 v，假如这个值 v 在 [0~Wh/Ws) 之中，则副本在表头 item 中，并返回表头 item 的 id。否者继续遍历剩余的链表。
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，也不等于节点的权重)。
Straw Buckets：这种类型让 bucket 所包含的所有 item 公平的竞争 (不像 list 和 tree 一样需要遍历)。这种算法就像抽签一样，所有的 item 都有机会被抽中(只有最长的签才能被抽中)。每个签的长度是由 length = f(Wi)*hash(x, r, i) 决定的，f(Wi) 和 item 的权重有关，i 是 item 的 id 号。c(r, x) = MAXi(f(Wi) * hash(x, r, i))。
图 1 Tree Buckets 的结构
以上是“ceph 中 CRUSH 数据分布算法有什么用”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注丸趣 TV 行业资讯频道！
