深入解读Ceph分布式存储核心：CRUSH算法，一种基于哈希的数据分布算法，实现高效、可扩展的数据放置。
原文标题：分布式存储Ceph中的CRUSH算法
原文作者：牧羊人的方向
冷月清谈：
CRUSH算法是一种基于哈希的数据分布算法，它根据数据唯一标识符、集群拓扑结构和备份策略计算数据位置，避免了查表操作，实现了去中心化和高并发。Cluster Map描述了集群的拓扑结构，由树状层级关系表示，叶子节点是存储设备，中间节点是buckets，根节点是root。Placement Rule定义了数据分布策略，包括take、select和emit操作。
映射过程包括File到Object、Object到PG以及PG到OSD的映射。File被切割成Object，Object通过哈希映射到PG，PG通过CRUSH算法映射到OSD。
CRUSH调制包括编辑CRUSH Map和数据重平衡。可以通过编辑CRUSH Map来调整数据分布策略，通过数据重平衡来均衡集群负载。
怜星夜思：
2、在实际应用中，如何选择合适的bucket类型？
3、除了Ceph，还有哪些分布式存储系统使用了CRUSH算法或类似的算法？
原文内容
CRUSH算法是一种基于hash的数据分布算法，在Ceph集群中以cluster map作为输入将数据映射到所有的存储设备之间。本文简单介绍Ceph中的CRUSH算法原理。
1、Ceph中的CRUSH算法
CRUSH（Controlled Replication Under Scalable Hashing）是一种基于hash的数据分布算法，以数据唯一标识符、当前存储集群的拓扑结构以及数据备份策略作为CRUSH输入，可以随时随地通过计算获取数据所在的底层存储设备的位置并直接与其通信，从而避免查表操作，实现去中心化和高度并发。
CRUSH算法基于权重将数据映射到所有的存储设备之间，这个过程高度依赖于集群的拓扑描述cluster map和不同的数据分布策略placement rule。CRUSH的计算过程仅使用x、cluster map和placement rule作为hash函数的输入，如果cluster map不发生变化那么结果基本是确定的；同时使用的hash函数是伪随机的，所以CRUSH选择每个目标存储对象的概率相对独立，从而可以保证数据在整个集群间均匀分布。
Cluster map是Ceph集群拓扑结构的逻辑描述形式，通常由树状层级关系表示，包括device和bucket，每个叶子节点是最小的物理存储设备device、所有的中间节点统称为buckets、根节点为root是整个集群的入口。Device和buckets都有唯一的数字ID和属性描述标识其在集群中所处的位置和层级，每个节点同时设置权重值用于CRUSH算法的选择过程进行调整，上一级节点的权重是所有子节点权重之和。
-
操作take(a)，从cluster map中选择指定编号的bucket，并以此作为后续步骤的输入。例如系统默认的placement rule总是以cluster map中的root节点作为输入开始执行的。
-
操作select(n,t)，从输入的bucket当中随机选择指定类型和数量的条目，迭代每个元素i，并且在这个点中的子树中选择了n个t类型的项。存储设备有一个绑定类型，并且每个bucket在系统中拥有一个用于分辨buckets中classes的类型区域。对于每个i，select(n,t)都会从1到n迭代调用，同时通过任何中间buckets降序递归，它伪随机地选择一个通过函数c(r,x)嵌套的项，直到它找到请求t中的一个项。去重后的结果项n|i|会返回给输入变量i，同时也会作为随后被调用的select(n,t)操作的输入参数，或者被移动到用于触发操作的结果向量中。
-
操作emit，emit输出最终选择结果给上级调用者并返回
-
Union bucket：CRUSH中的一般类型Bucket会被当成一个设备集合一样进行使用
-
List bucket：它的结构是链表结构，所包含的item可以具有任意的权重
-
Tree bucket：树状buckets是一种加权二叉排序树，数据项位于树的叶子节点。每个递归节点有其左子树和右子树的总权重，并根据一种固定的算法进行标记。
-
Straw bucket：Straw类型bucket允许所有项通过类似抽签的方式来与其他项公平“竞争”。定位副本时，bucket中的每一项都对应一个随机长度的straw，且拥有最长长度的straw会获得胜利
这些bucket的差异总结如表所示，unique算法执行效率最高但是抵御结构变化能力最差；straw算法执行效率较低但是抵御结构变化能力最好；list和tree算法执行效率和抵御结构变化能力基于二者之间。
1）File和object的映射
File按照一定的大小对进行切割得到object，相当于RAID中的条带化处理。切割以后，对object进行编号，也即oid（Object ID)。每个file都有一个唯一的元数据ino，然后再把file切分后产生的序号连缀在一起，即可构成oid。比如元数据为fileName的文件成分为三个Object，oid即为fileName0,fileName1,fileName2。需要注意的是ino必须唯一。
每个Object都要独立的映射到PG里，可以将oid进行哈希，这样会得到一个近似均匀分布的伪随机值，然后需要考虑的是把Object放到PG里面去了。假设PG数为m，那么最简单的就是在m个PG中随机的选一个，那么可以设定一个长度为m-1的掩码，然后将HASH得到的伪随机值于mask按位相与，最终得到PG序号(pgid)
3）PG和OSD的映射
Object与PG的映射其实是静态的，也就是一个Object通过这个运算一定会映射到某个PG里面，而PG与OSD这一层的映射公式需要满足动态特性，可以让PG根据需要动态迁移到不同的OSD组合上，由CRUSH算法来实现。
参考《》部分介绍
Ceph将集群的cluster map和所有的placement rule合并成一张CRUSH map，因此基于CRUSH map可以独立实施数据备份和备份策略。
1）获取CRUSH map
ceph osd getcrushmap -o {compiled-crushmap-filename}
2）反编译CRUSH map
crushtool -d {compiled-crushmap-filename} -c {decompiled-crushmap-filename}
3）编辑crush map，得到反编译后的crush map，直接以文本形式进行编辑
rule replicated_ruleset #规则集的命名，创建pool时可以指定rule集
{
ruleset 0 #rules集的编号，顺序编即可
type replicated #定义pool类型为replicated(还有esurecode模式)
min_size 1 #pool中最小指定的副本数量不能小1\
max_size 10 #pool中最大指定的副本数量不能大于10
step take default #定义pg查找副本的入口点
step chooseleaf firstn 0 type host #选叶子节点、深度优先、隔离host
step emit #结束
}
4）编译CRUSH map
crushtool -c {decompiled-crushmap-filename} -o {compiled-crushmap-filename}
5）模拟测试，验证修改是否符合预期
crushtool -imycrushmap --test --min-x 0 --max-x 9--num-rep 3 --resultset 0 --showing mappings
6）注入集群，使之生效
ceph osd setcrushmap -i {compiled-crushmap-filename}
如果集群数据分布不平衡，可以手动调整每个OSD的reweight触发PG在OSD之间进行迁移，以恢复数据平衡。数据重平衡操作可以逐个OSD或者批量执行。
1）查看整个集群的空间利用率统计
ceph osd df tree
2）找到空间利用率较高的OSD，逐个执行
ceph osd reweight {osd_id} reweight
也可以批量执行，一种是按照OSD当前空间的利用率，另一种是按照PG在OSD之间的分布。可以先测试执行命令，触发PG迁移数量的相关统计，方便进行调整：
ceph osd test-reweight-by-utilization {overload}{max_change}\{max_osds} {--no-increasing}
到这里，分布式存储中的Crush算法已经介绍完毕。
参考资料：
-
CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data,Sage A. Weil
-
Ceph设计原理与实现，谢型果等著
-
https://www.cnblogs.com/chenxianpao/p/5568207.html
-
https://www.cnblogs.com/dy2903/p/8513713.html
-
https://www.jianshu.com/p/cc3ece850433
-
https://amoldighe.github.io/2018/01/20/exploring-ceph/