今天看CRUSH数据分布算法，想从头捋一遍，便于从宏观到细节地理解ceph的设计。
首先，CRUSH算法是什么？ceph作为一个分布式存储系统，CRUSH算法是其实现数据分布的核心。
在分布式存储系统中，数据分布算法对分布式存储系统至关重要。一般分为两类，一类是基于集中式的元数据查询方式，即要实现分布式B+树，一个是实现分布式Hash表。这两种算法没有固定的优劣之分，其效率高低和其数据结构息息相关，一般的评价指标是查找，插入，更新，删除操作的效率。
B树的查找，更新和删除操作的复杂度都为O(logN)；对于Hash表，更新，插入，删除都可以在常数时间内完成，但哈希数据结构牺牲了范围查询功能。所以分布式B+树存储系统同时支持随机读取和顺序扫描，分布式Hash存储系统由于只支持随机读取，一般选择相对较好的磁盘。
接下来，解释一下几个概念B-Tree，B+Tree，Hash，一致性Hash。
平衡多路查找树B-Tree
B-Tree是为磁盘等外存储设备设计的一种平衡查找树。
系统从磁盘读取数据到内存时是以磁盘块block为基本单位的，位于同一个磁盘块中的数据会被一次性读取出来，而不是选取一部分读取。
拿InnoDB存储引擎举例说明更好理解，InnoDB存储引擎中有页（Page）的概念，页是其磁盘管理的最小单位。默认每个page的大小为16KB。而系统一个磁盘块的存储空间往往没有这么大，因此InnoDB每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小16KB。InnoDB在把磁盘数据读入内存时会以页为基本单位，在查询数据时，如果一个页中的每条数据都有助于定位数据记录的位置，会减少磁盘I/O次数，提高查询效率。B-Tree结构的数据可以让系统高效的找到数据所在的磁盘块。
B+Tree
B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构，InnoDB存储引擎用B+Tree实现其索引结构。B-Tree每个节点不急包含key值，同时也包含data值。而在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点，非叶子节点上只存储key值信息，这样可以加大每个节点存储的key的数量，降低B+Tree的高度。
普通Hash算法
如key%N，key是数据的key，N是机器节点数，如果有一个机器加入或退出这个集群，则所有的数据映射都无效了，如果是持久化存储则要做数据迁移，如果是分布式缓存，则其他缓存就失效了。
一致性hash算法
A：按照常用的hash算法来将对应的key哈希到一个具有2^32次方个节点的空间中，即0 ~ (2^32)-1的数字空间中。现在我们可以将这些数字头尾相连，想象成一个闭合的环形。
B：映射服务器节点，将各个服务器使用Hash进行一个哈希，具体可以选择服务器的ip或唯一主机名作为关键字进行哈希，这样每台机器就能确定其在哈希环上的位置。假设我们将四台服务器使用ip地址哈希后在环空间的位置。
C：映射数据。现在我们将objectA、objectB、objectC、objectD四个对象通过特定的Hash函数计算出对应的key值，然后散列到Hash环上,然后从数据所在位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器。
D：服务器的删除与添加。如果此时NodeC宕机了，此时Object A、B、D不会受到影响，只有Object C会重新分配到Node D上面去，而其他数据对象不会发生变化。如果在环境中新增一台服务器Node X，通过hash算法将Node X映射到环中，通过按顺时针迁移的规则，那么Object C被迁移到了Node X中，其它对象还保持这原有的存储位置。通过对节点的添加和删除的分析，一致性哈希算法在保持了单调性的同时，还是数据的迁移达到了最小，这样的算法对分布式集群来说是非常合适的，避免了大量数据迁移，减小了服务器的的压力。
E：虚拟节点。到目前为止一致性hash也可以算做完成了，但是有一个问题还需要解决，那就是平衡性。从下图我们可以看出，当服务器节点比较少的时候，会出现一个问题，就是此时必然造成大量数据集中到一个节点上面，极少数数据集中到另外的节点上面。为了解决这种数据倾斜问题，一致性哈希算法引入了虚拟节点机制，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。具体做法可以先确定每个物理节点关联的虚拟节点数量，然后在ip或者主机名后面增加编号。例如上面的情况，可以为每台服务器计算三个虚拟节点，于是可以分别计算 “Node A#1”、“Node A#2”、“Node A#3”、“Node B#1”、“Node B#2”、“Node B#3”的哈希值，于是形成六个虚拟节点。同时数据定位算法不变，只是多了一步虚拟节点到实际节点的映射，例如定位到“Node A#1”、“Node A#2”、“Node A#3”三个虚拟节点的数据均定位到Node A上。这样就解决了服务节点少时数据倾斜的问题。每个物理节点关联的虚拟节点数量就根据具体的生产环境情况在确定。
关于Ceph
Ceph使用树型层级结构描述OSD的空间位置以及权重(同磁盘容量相关)大小。OSD节点在层级结构中也被称为Device，它位于层级结构的叶子节点，所有非叶子节点称为Bucket。Device节点的权重代表存储节点的性能，磁盘容量是影响权重大小的重要参数。Bucket节点的权重是其子节点的权重之和。
Ceph分布数据的过程：首先计算数据x的Hash值并将结果和PG数目取余，以得到数据x对应的PG编号。然后，通过CRUSH算法将PG映射到一组OSD中。最后把数据x存放到PG对应的OSD中。这个过程中包含了两次映射，第一次是数据x到PG的映射。如果把PG当作存储节点，那么这和文章开头提到的普通Hash算法一样。不同的是，PG是抽象的存储节点，它不会随着物理节点的加入或则离开而增加或减少，因此数据到PG的映射是稳定的。
Bucket随机选择算法解决了如何从Bucket中选择出需要的子item问题。定义了4种不通的Bucket选择算法，每种选择算法基于不同的数据结构，采用不同伪随机函数。
CRUSH算法的目的是，为给定的PG(即分区)分配一组存储数据的OSD节点。选择OSD节点的过程，要考虑以下几个因素：
1.PG在OSD间均匀分布。假设每个OSD的磁盘容量都相同，那么我们希望PG在每个OSD节点上是均匀分布的，也就是说每个OSD节点包含相同数目的PG。假如节点的磁盘容量不等，那么容量大的磁盘的节点能够处理更多数量的PG。
2.PG的OSD分布在不同的故障域。因为PG的OSD列表用于保存数据的不同副本，副本分布在不同的OSD中可以降低数据损坏的风险。
hash(x,r,i)
x:要计算的PG的id号
r:选择的副本序号
i:bucket的id号
如果出现了冲突，失效或者过载怎么办？即当对于一个给定的pg_id, r=0,r=1时，都选出了osd2，那么继续往后取，直到取到副本数够了为止。
参考资料
【1】https://zhuanlan.zhihu.com/p/98030096
【2】https://www.cnblogs.com/shanno/p/3958298.html
【3】《Ceph 源码分析》
