Ceph作为最近关注度比较高的统一分布式存储系统，其有别于其他分布式系统就在于它采用Crush（Controlled Replication Under Scalable Hashing）算法使得数据的存储位置都是计算出来的而不是去查询专门的元数据服务器得来的。另外，Crush算法还有效缓解了普通hash算法在处理存储设备增删时带来的数据迁移问题。接下面我会分三篇博文介绍这个重量级的算法，第一篇主要回答三个问题：什么是CRUSH？它能做什么？它是怎么工作的？第二篇主要介绍CRUSH中一个重要的概念Bucket。第三篇主要介绍如何通过CRUSH控制数据迁移。
1. 什么是CRUSH？
随着大规模分布式系统的出现，系统必须能够平均的分布数据和负载，最大化系统的利用率，并且能够处理系统的扩展和系统故障。一般的分布式系统都会采用一个或者多个中心服务用来控制数据的分布，这种机制使得每次IO操作都会先去一个地方查询数据在集群中的元数据信息。当集群的规模变大或者系统的workload比较大时，这些中心服务器必然会成为性能上的瓶颈。Ceph摒弃了这种做法，而是通过引入CRUSH算法，将数据分布的查询操作变成了计算操作，并且是在client端完成。
2. CRUSH能干什么？
如上面介绍的，它主要是ceph用来控制数据分布的。通过下图，我们看一下它在整个IO流程中处于什么位置。
Ceph的后端是一个对象存储（RADOS），所以所有的数据都会按照一个特定的size（ceph系统默认是4M）被切分成若干个对象，也就是上面的Objects。每一个Object都有一个Objectid（oid），Objectid的命名规则是数据所在image的block_name_prefix再跟上一个编号，这个编号是顺序递增的。通过(poolid, hash(oid) & mask)，每个object都可以得到它对应的pgid。有了这个pgid之后，Client就会执行CRUSH算法得到一个OSD列表（OSD1，OSD2，OSD3）。然后对它们进行筛选，根据副本数找出符合要求的OSD，比如OSD不能是failed、overloaded的。知道数据要存在哪些OSD上之后，Client会向列表中的第一个OSD（primary osd）发起IO请求。然后这个OSD按照读写请求分别做相应的处理。
所以一句话说明CRUSH的作用就是，根据pgid得到一个OSD列表。
CRUSH是基于一张描述当前集群资源状态的map（Crush map）按照一定的规则（rules）得到这个OSD列表的。Ceph将系统的所有硬件资源描述成一个树状结构，然后再基于这个结构按照一定的容错规则生成一个逻辑上的树形结构作为Crush map。数的叶子节点是OSD。
3.1 Crush map
一个Crush map一般包括四个部分：
[plain]view plain
copy