CRUSH（Controlled Replication Under Scalable Hashing）是一种基于伪随机控制数据分布、复制的算法。Ceph是为大规模分布式存储系统（PB级的数据和成百上千台存储设备）而设计的，在大规模的存储系统里，必须考虑数据的平衡分布和负载（提高资源利用率）、最大化系统的性能，以及系统的扩展和硬件容错等。CRUSH就是为解决以上问题而设计的。在Ceph集群里，CRUSH只需要一个简洁而层次清晰的设备描述，包括存储集群和副本放置策略，就可以有效地把数据对象映射到存储设备上，且这个过程是完全分布式的，在集群系统中的任何一方都可以独立计算任何对象的位置；另外，大型系统存储结构是动态变化的（存储节点的扩展或者缩容、硬件故障等），CRUSH能够处理存储设备的变更（添加或删除），并最小化由于存储设备的变更而导致的数据迁移。

CRUSH基本原理

         众所周知，存储设备具有吞吐量限制，它影响读写性能和可扩展性能。所以，存储系统通常都支持条带化以增加存储系统的吞吐量并提升性能，数据条带化最常见的方式是做RAID。与ceph的条带化最相似的是RAID 0或者是“带区卷”。Ceph条带化提供了类似于RAID 0的吞吐量，N路RAID镜像的可靠性以及更快速的恢复能力。

         在磁盘阵列中，数据是以条带（stripe）的方式贯穿在磁盘阵列所有硬盘中的。这种数据的分配方式可以弥补OS读取数据量跟不上的不足。

1. 将条带单元（stripe unit）从阵列的第一个硬盘到最后一个硬盘收集起来，就可以称为条带（stripe）。有的时候，条带单元也被称为交错深度。在光纤技术中，一个条带单元被叫作段。

2.数据在阵列中的硬盘上是以条带的形式分布的，条带化是指数据在阵列中所有硬盘中的存储过程。文件中的数据被分割成小块的数据段在阵列中的硬盘上顺序的存储，这个最小数据块就叫做条带单元。

        决定Ceph条带化数据的3个因素：

◎ 对象大小：处于分布式集群中的对象拥有一个最大可配置的尺寸（例如，2MB、4MB等），对象大小应该足够大以适应大量的条带单元。

 ◎ 条带宽度：条带有一个可以配置的单元大小，Ceph Client端将数据写入对象分成相同大小的条带单元，除了最后一个条带之外；每个条带宽度，应用是对象大小的一小部分，这样使得一个对象可以包含多个条带单元。

 ◎ 条带总量：Ceph客户端写入一系列的条带单元到一系列的对象，这就决定了条带的总量，这些对象被称为对象集，当Ceph客户端写入的对象集合中的最后一个对象之后，它将会返回到对象集合中的第一个对象处。

Object与PG

         Ceph条带化之后，将获得N个带有唯一oid（即object的id）。Object id 是进行线性映射生成的，即由file的元数据、Ceph条带化产生的object的序号连缀而成。此时object需要映射到PG中，该映射包括两部分。

          1.由Ceph集群指定的静态Hash函数计算Object的oid，获取到其Hash值。
          2.将该Hash值与mask进行操作，从而获得PG IＤ

          根据PADOS的设计，假定集群中设定的PG总数为M（M一般为2的整数幂），则mask的值为M-1。由此，Hash值计算之后，进行按位与操作是想从所有PG中近似均匀地随机选择。基于该原理以及概率论的相关原理，当用于数量庞大的Object以及PG时，获得到的PG ID是近似均匀的。

         计算PG的ID示例如下：
          1.Client输入pool ID和对象ID（如pool='liverpool'，object-id='john'）。
          2.CRUSH获得对象ID并对其Hash运算。
          3.CRUSH计算OSD个数，Hash取模获得PG的ID（如0x58）。
          4.CRUSH获得已命名pool的ID（如liverpool=4）。
          5.CRUSH预先考虑到pool ID相同的PG ID（如4.0x58）。

PG与OSD

         由PG映射到数据存储的实际单元OSD中，该映射是由CRUSH算法来确定的，将PG ID作为该算法的输入，获得到包含N个OSD的集合，集合中第一个OSD被作为主OSD，其他的OSD则依次作为从OSD。N为该PG所在POOL下的副本数目，在生产环境N一般为3；OSD集合中的OSD将共同存储和维护该PG下的Object。需要注意的是，CRUSH算法的结果不是绝对不变的，而是受其他因素的影响。其影响因素主要有以下两个。
         一是当前系统状态。也就是上文逻辑结构中曾经提及的Cluster Map（集群映射）。当系统中的OSD状态、数量发生变化 时，Cluster Map可能发生变化，而这种变化将会影响到PG到OSD之间的映射。
          二是存储策略配置。这里的策略主要与安全相关。利用策略配置，系统管理员可以指定承载同一个PG的3个OSD分别位于数据中心的不同服务器乃至机架上，从而进一步改善存储的可靠性。

         因此，只有在Cluster Map和存储策略都不发生变化的时候，PG和OSD之间的映射关系才是固定不变的。在实际使用中，策略一经配置通常不会改变。而系统状态的改变或者是因为设备损坏，或者是因为存储集群规模扩大。好在Ceph本身提供了对于这种变化的自动化支持，因而，即便PG与OSD之间的映射关系发生了变化，并不会对应用造成困扰。事实上，Ceph正是需要有目的的利用这种动态映射关系。正是利用了CRUSH的动态特性，Ceph才可以将一个PG根据需要动态迁移到不同的OSD组合上，从而自动化地实现高可靠性、数据分布re-blancing等特性。

        之所以在此次映射中使用CRUSH算法，而不是其他Hash算法，原因之一是CRUSH具有上述可配置特性，可以根据管理员的配置参数决定OSD的物理位置映射策略；另一方面是因为CRUSH具有特殊的“稳定性”，也就是当系统中加入新的OSD导致系统规模增大时，大部分PG与OSD之间的映射关系不会发生改变，只是少部分PG的映射关系会发生变化并引发数据迁移。这种可配置性和稳定性都不是普通Hash算法所能提供的。因此，CRUSH算法的设计也是Ceph的核心内容之一。

PG与Pool

          Ceph存储系统支持“池”（pool）的概念，这是存储对象的逻辑分区。

          Ceph Client端从Ceph mon端检索Cluster Map，写入对象到pool。Pool的副本数目，Crush规则和PG数目决定了Ceph将数据存储的位置，如图：

调用关系图

            Pool至少需要设定以下参数：
                    ◎  对象的所有权/访问权
                    ◎  PG数目
                    ◎  该Pool使用的CRUSH规则
                    ◎   对象副本的数目

CRUSH关系分析

          从本质上讲，CRUSH算法是通过存储设备的权重来计算数据对象的分布的。在计算过程中，通过Cluster Map（集群映射）、Data Distribution Policy（数据分布策略）和给出的一个随机数共同决定数据对象的最终位置。

Cluster Map

        Cluster Map记录所有可用的存储资源及相互之间的空间层次结构（集群中有多少个机架、机架上有多少服务器、每个机器上有多少磁盘等信息）。所谓的Map，顾名思义，就是类似于我们生活中的地图。在Ceph存储里，数据的索引都是通过各种不同的Map来实现的。另一方面，Map使得Ceph集群存储设备在物理层作了一层防护。例如，在多副本结构上，通过设备合理的Map（故障域设置为Host级），可以保证在某一服务器死机的情况下，有其他副本保留在正常的存储节点上，能够继续提供服务，实现存储的高可用。设置更高的故障域级别（如Rack、Row等）能保证整机柜或同一排机柜在掉电情况下数据的可用性和完整性。

1.Cluster Map的分层结构

         Cluster Map由Device和Bucket构成。它们都有自己的ID和权重值，并且形成一个以Device为叶子节点、Bucket为躯干的树状结果。

CRUSH架构图

            Bucket拥有不同的类型，如Host、Row、Rack、Room等，通常我们默认把机架类型定义为Rack，主机类型定义为Host，数据中心（IDC机房）定义为Data Center。Bucket的类型都是虚拟结构，可以根据自己的喜好设计合适的类型。Device节点的权重值代表了存储设备的容量与性能。其中，磁盘容量是权重大小的关键因素。

          OSD的权重值越高，对应磁盘会被分配写入更多的数据。总体来看，数据会被均匀写入分布于集群所有磁盘，从而提高整体性能和可靠性。无论磁盘的规格容量，总能够均匀使用。

          关于OSD权重值的大小值的配比，官方默认值设置为1TB容量的硬盘，对应权重值为1.可以在/etc/init.d/ceph原码里查看相关的内容。

2.恢复与动态平衡

          在默认设置下，当集群里有组件出现故障时（主要是OSD，也可能是磁盘或者网络等），Ceph会把OSD标记为down，如果在300s内未能回复，集群就会开始进行恢复状态。这个“300s”可以通过"mon osd down ourt interval“配置选项修改等待时间。PG（Placement Groups）是Ceph数据管理（包括复制、修复等动作）单元。当客户端把读写请求（对象单元）推送到Ceph时，通过CRUSH提供的Hash算法把对象映射到PG。PG在CRUSH策略的影响下，最终会被映射到OSD上。

Data Distribution Policy

             Data Distribution Policy由Placement Rules组成。Rule决定了每个数据对象有多少个副本，这些副本存储的限制条件（比如3个副本放在不同的机架中）。一个典型的rule如下所示：

rule replicated_ruleset     {  ##rule名字
      ruleset 0                    #rule的ID
      type replicated        ##类型为副本模式，另外一种模式为纠删码（EC）
      min_size 1              ##如果存储池的副本数大于这个值，此rule不会应用
      max_size 10           ##如果存储池的副本数大于这个值，此rule不会应用
      step take default    ##以default root 为入口
      step chooseleaf firstn 0 type host   ##隔离城为host级，即不同副本在不同的主机上
      step emit                 ##提交

}

根据实际的设备环境，可以定制符合自己需求的Rule。

CRUSH中的伪随机

            CRUSH(x) -> (osd1,osd2……osd N)

          CRUSH使用了多参数的Hash函数在Hash之后，映射都是按既定规则选择的，这使得从x到OSD的集合是确定的和独立的。CRUSH只使用Cluster Map、Placement Rules、X。CRUSH是伪随机算法，相似输入的结果之间没有相关性。

            PGP是PG的逻辑承载体，是CRUSH算法不可缺少的部分。在Ceph集群里，增加PG数量，PG到OSD的映射关系就会发生变化，但此时存储在PG里的数据并兴地发生迁移，只有当PGP的数量也增加时，数据迁移才会真正开始。关于PG和PGP的关系，假如把PG比作参加宴会的人，那么PGP就是人坐的椅子，如果人员增加时，人的座位排序就会发生变化，只有增加椅子时，真正的座位排序变更才会落实。因此，人和椅子的数量一般都保持一致。所以，在ceph里，通常把PGP和PG设置成一致的。

查看PG映射OSD的集合，即PG具体分配到OSD的归属。

ceph pg dump | grep ^22\. | awk '{print $1 "\t" $17}'

           在Ceph集群里，当有数据对象要写入集群时，需要进行两次映射，第一次从object-->PG，第2次是PG-->OSD set 。每一次的映射都是与其他对象无相关的，这充分体现了CRUSH的独立性（充分分散）和确定性（可确定的存储位置）。