CRUSH：可控、可扩展的复本数据非中心化的定位算法
摘要
快速兴起的分布式存储系统正面临着在数以千计的存储设备之间分配PB级的数据问题。在这样的系统中，需要将数据与负载分布，以充分利用可用的资源，并最大化系统的性能，同时能够适应系统的增长，管理硬件设备的失效。我们开发了 CRUSH 算法，一种可扩展的，准随机的数据分布函数，专门在对象文件系统中用来做数据与设备之间的影射，这样的影射不依赖于集中的目录。因为大系统天生就是动态的，CRUSH 设备用来适应存储设备的增加与删除，并最小化数据的移动。本算法可广泛用于各种数据复制与可靠性机制中，并根据用户定义的策略对数据进行分布，使得数据复本在不同的失效域中分离。
1 简介
基于对象的存储系统是最近兴起的架构，这种构架即要保证很强的可管理性，又要有可扩展性以及性能[Azagury et al. 2003]。与传统的基于块的磁盘设备不同，基于对象的存储设备（OSDs）在内部进行磁盘分配的管理，暴露的接口使得其他部分可以读写不同大小的，有名的对象。在这样的系统中，每个文件的数据被分成了小块的有名的对象，并在整个集群中分布。对象在多个设备之间复制（或者部署了其他的冗余策略）用来防止在设备失效出现时导致数据丢失。基于对象的存储系统通过将大的数据列表替换为对象列表，并分布到底层的块设备，简化了数据的布局问题。尽管通过压缩文件分配元数据及其复杂性从而提升了系统的可扩展性，但是在数以千计的设备之间进行数据分布这样的问题依然存在，并且这些设备之间还有容量与性能特性上的差异。
大多系统都是简单地将新数据写到一个未使用太多的设备中。这样的方案的主要问题就是数据写入后就很少移动。就算数据完美分布，但当存储系统扩展时，都会变得不平衡。因为新的磁盘要么是空的，要么只包括新数据。这样，根据负载情况，要么是旧磁盘或者是新磁盘一直处于忙状态。极少数的情况下才会充分使用新旧磁盘，并因此能够充分使用可用的资源。
一种可靠的解决方案，就是将所有的数据随机地在系统中可用的存储设备之间进行分配。这导致概率性地数据平衡分布，并混合使用新旧设备。当新的设备加入时，已经存在的数据的部分会被迁移到新的设备上以恢复平衡。这种方式有一个关键的好处就是，平均上，所有的设备都有相似的负载，因此系统在任何可能的负载下都能够表现良好[Santos et al. 2000]。另外，在一个大的存储系统中，单个的大文件会被随机分布到一个大的设备集合中，因此可以提供高层次的并行化以及集合带宽。然而，简单的基于哈希的分布，无法处理设备数量变化的情况，这样会导致数据大量重整。另外，现有的随机分配方案将磁盘数据在不同的设备之间进行复本化，极容易招致因偶然的设备失效导致数据丢失的问题。
我们因此开发了 CRUSH （Controlled Replication Under Scalable Hashing，基于可扩展的哈希下的受控复本算法）。这是一个准随机的数据分布算法，可以可靠高效地将对象复本在异构的，结构化的存储集群中进行分布。CRUSH 实现为一种准随机，确定性的函数，其将输入值（一般为对象或者对象组ID）影射为设备列表，并用这些设备列表存储对象。CRUSH 仅需要很少的，即集群设备组成的层级描述以及复本定位策略的相关知识。这不同于传统的方式，因为它不依赖于任何的单文件或者单对象目录。这种方式有两个关键的好处：一个是，它是完全分布的，大系统中的任何部分都可以独立计算对象的位置；其二是，所需要有元数据大多都是静态的，只有当设备添加与删除时才会有变化。
CRUSH设计的目标就是用来优化数据分布，并充分利用系统资源，在设备添加或者删除时，有效地组织数据，并对数据复本定位施加灵活的限制，使得数据安全性在意外的或者相关的硬件失效情况下能得到保证。CRUSH支持很多的数据安全机制，包括 n 路复本（镜像），RAID 校验方案或者其他形式的代码擦除，以及混合方式（如 RAID-10）。这些特性使得 CRUSH 成为管理超大规模（几个PB）存储系统中的对象分布的理想方案。在这样的存储系统中，可扩展性，性能，可靠性是极为重要的。
2 相关工作
其于对象的存储对于提升系统的可扩展性最近受到了广泛的关注。很多的研究以及生产系统已经接纳了基于对象的方式，包括像 Seminal NASD 文件系统[Gobioff et al. 1997]， Panasas 文件系统 [Nagle et al.2004]，Lustre [Braam 2004]， 及其他的如[Rodeh and Teperman 2003； Ghemawat et al. 2003] 之类的文件系统。其他的基于块的分布式文件系统，像 GPFS [Schmuck and Haskin 2002]，以及FederatedArray of Bricks（FAB）[Saito et al. 2004] 都面临着相同的数据分布挑战。在这些文件系统，利用半随机或者启发式的方法来进行新数据的分布，并存储在可用的存储空间中，但是数据很少进行重新定位以保证随时的数据平衡。更重要的是，所有这些系统都是通过某种元数据目录来定位数据，而 CRUSH 只依赖于很少的集群描述以及确定性的影射函数来进行数据定位。这种差异在写数据时尤其明显。因为系统利用 CRUSH 就能够计算任何新数据的存储目标，而不需要通过中心控制分配器来执行。Sorrento [Tang et al. 2004] 存储系统使用一致性哈希[Kargeret al. 1997] 与 CRUSH 相近，但是缺少对于设备权重的控制，以及数据良好的平衡，也没有失效域的概念来保证数据安全。
尽管在系统层面，利用显式的分配影射[Anderson et al. 2001； Anderson et al. 2002]中的数据迁移问题已经被研究得非常多了，但是在这样的方案中，需要非常多的元数据，但是 CRUSH 这样的函数式方法却不需要。Choy， et al. [1996]描述了用于在磁盘上进行数据分布的算法，该算法在磁盘添加时有一个最优化的数值，但是却不支持权重，复本以及磁盘移除。Brinkmann， et al. [2000]利用哈希在异构集群中来分布数据，但是其中的集群是静态的。SCADDAR [Goel et al. 2002]解决了磁盘添加与删除问题，但是只支持有限的复本策略集。以上没有一个方式包含像 CRUSH 这样的灵活性，以及通过失效域来保护数据的可靠性。
CRUSH与RUSH[Honicky and Miller 2004] 算法族最相似，并基于这些算法开发的。RUSH 有一系列的算法通过影射函数而不是显式的元数据来有效地进行数据分布，并支持有权重的设备的加入与删除。尽管有这些基本的特点，但是还有一系统的问题使得 RUSH 在实践中不够有效。CRUSH 完全实现了 RUSHP 和 RUSHT中有用的元素而解决了之前未提到的可靠性与复本问题，同时又提供了更好的性能与灵活性。
3 CRUSH 算法
CRUSH算法根据设备的权重来在多个存储设备之间进行数据对称分配，近似于一个概率性分布。分布是受到一个有层级的 cluster map 的控制的，clustermap 代表了存储集群中可用的资源以及组成这个集群的组件逻辑构成。例如，根据服务器机柜来描述一个大的集群，而机柜中又部署了大量的磁盘架，磁盘架中都是存储设备。数据分布策略根据定位规则来定义，这些规则定义包括从集群中挑选几个复本目标，以及对复本定位上的一些限制。如可能指定三个镜像的复本存储在不同的物理机柜里，因为它们不会使用同一个电力线路。（译注：这样数据就存储在不同的失效域中，某个设备的电力失效，不会导致数据不可用。）
假设输入一个单独的整数值 x，CRUSH 则输出一个在 n 个不同的存储设备中的有序的列表 ~R。CRUSH 利用一个强的多端输入（包括 x）整型哈希函数，生成一个完全确定的，并且是独立的使用 clustermap，定位规则， x 等进行计算而得的影射。这种分布是一种准随机的，即使输入相似，输出之间是没有明显在关联关系的，也跟存储设备上存储的数据无关。我们说 CRUSH 产生了“逆集群”（declustered) 的复本分布，存储设备集之间共享某个存储项，是与所有其他的存储项是无关的。
3.1 层级式的集群影射
集群影射由设备与桶（devices and buckets）构成，两者都有权重以及整数标识符。桶可以包括任意数量的设备以及其他的桶，使得它们也可以在存储层级中成为内部结点，并且设备总是叶子结点。存储设备被管理员赋予了权重，以对应设备可用于存储数据的相对数量。尽量大的系统包括大量的不同容量与性能的设备，但是随机数据的分布静态地将设备的使用情况与负载相关联。这样的设备负载将其计算成为其存储数据的一部份。这导致了一个一维的定位方式，权重主要是由磁盘的容量组成，桶权重则是其所有元素权重的总合。
桶也可能任意地在层级中进行组合，以表示所有的可用设备。如，可以创建一个最低层的架子桶，表示所有已经安装的相同的设备，然后将架子桶组合成“机柜桶”，将所有安装在同一个背板中的架子桶组合起来。在大的系统中，机柜桶又可以组成“行桶”或者“房间桶”。通过这样的递归方式，用准随机的的哈希方式，将数据存放在这些设备中。与传统的方式比较起来，目标组合中的数量的变化，会导致数据会产生大量的重整操作，而 CRUSH 是基于4个不同的桶类型，每一个都有不同的选择算法，以解决由于设备增删而导致的数据移动问题，以及减低整个的计算复杂度。
3.2 复本定位
CRUSH 设计原则，就是静态地使用存储中的设备与带宽的同时，利用权重将数据统一地进行分布。在存储设备中的复本定位对于数据的安全性也有关键影响。为了反映后台物理设备的组织与安装，CRUSH 可能进行建模——因此去解决这样的数据安全问题——潜在的有设备失效关联的资源。典型的资源包括物理距离，共享的电源模块，以及共享的网络。通过将这些信息编码到集群影射中，CRUSH 的定位策略就可以将对象复本在不同的失效域中进行分离，同时保证数据希望的分布状态。例如，为了解决同时失效的可能，需要将保证数据存储在不同的机架、不同的背板，不同的电源，不同的控制器，或者不同的物理位置上的设备中。
为了协调 CRUSH 可能用到的不同的方案，包括数据复制策略以及底层物理配置，CRUSH 为每种复制策略，或者分布策略定义了“定位规则”，使得存储系统或者管理员精确地指定对象复本如何进行存放。如，其中一个规则为一个 2-路 的镜像选择一对目标，一个是为一个3路的镜像选择三个目标，一个是为在6个设备上组成一个 RAID-4，等等。每一个规则都包括运行在一个简单环境中的一系列的应用于层级之上的操作，这由算法1的中伪代码进行描述。
表1：一个简单的例子，将三个复本在分布到同一行中的三个机柜中
输入 CRUSH 函数中的整数 x，是一个典型的对象名或者其他标识符。具有这样的标识符的一组对象的复本将会被存储在相同的设备中。take(a) 操作在存储层级中选择一个项目（通常为桶），并将其赋值给一个向量 ~i ，该向量再作为另一个操作的输入。select(n，t) 操作于向量 ~i 中的每元素，并在以当前点为根的子树中，选择 n 个不同的，类似为 t 的项目。存储设备有固定可知的类型，系统中的每个桶都有一个类型域用于区别不同类型的桶（比如，代表“行”的以及代表“机柜”）。对 i ∈~i，select(n，t) 在所请求的项目r ∈ 1， . . . ，n中进行迭代， 并递归向下，经过所有的中间桶，利用函数 c(r，x)（在第3.4节为每种桶类型都定义了相应的 c(r，x)），在每个桶中，准随机地选择一个内嵌的项目。直到找到一个类型为 t 的项目。结果 n|~i| 个不同的项目，放回到输入 ~i，要么作为后续 select(n，t) 操作的输入，或者通过 emit 操作移入结果向量。
作为例子，在表 1 中定义的规则，从在图1中的层级中的根开始，执行第一次 select( 1，row) 选择一个类型上 row 的桶（选择了 row2）。后续的操作 select(3，cabinet) 选择三个不同的机柜，这些机柜内嵌在之前所选择的 row2 之下（cab21，cab23，cab24），最后，select(1，disk) 在三个作为输入向量的机柜中桶中选择一个单独的磁盘，这个磁盘又分别内嵌在这几个桶下面。最终的结果是三个磁盘分布在三个机柜中，但都处于同一个行中（row）。这样方式可以使得复本能够同时分开，并限制在指定的容器类型中（如 行，机柜，机架）中，这样的特性即保证了可靠性，又保证了性能。包括多个 take 操作的规则，emit 块使得存储目标可以显式地从不同的存储池中抽取，正如远程复制方案（复本被存放在远程的站点），或者分层部署（如快速的近线存储，以及慢速的大容易存储阵列）中所期望的。
图1：包含行，机柜、机架与磁盘的四层集群影射的部分视图。粗线表示被 select 按表1中所构造的定位规则所选择的项目。
3.2.1 冲突，失效与过载
select(n，t) 操可能遍历从开始点之下的多个存储层级，以定位 n 个不同的指定类型 t 的项目，递归过程部分地由 r =1....n 来参数化，即复本个数个设备。在这个过程中，CRUSH 可能重新发起，并选择一个经过编辑过的 r'，这主要是基于三个原因：1，如果项目已经在当前的选择集中（冲突，select(n，t) 结果必须是不同的）；2，如果设备失效，或者设备过载。失效或者过载设备会在集群影射中进行标志，但是还会留在层级中，以避免不必要的数据移动。通过概率性地利用准随机重新发起集群影射，CRUSH 会有选择性地转移过载设备的数据——典型地由过载使用报告触发。对于失效或者过载的设备，CRUSH 会一致地在存储集群中进行项目重新分布，只需要重新在开始点发起 select(n， t) 操作即可 (看算法1 第11行)。在冲突的情况下，另一个 r' 向量首先用来在内部层级中进行递归，以尝试进行本地搜索（看算法1第14行），由此避免扭曲了在子树中整体的数据分布，因为在这个子树中，冲突才最有可能（如桶数量小于n）发生。
3.2.2 复本等级
校验与代码删除场景与复制相比有一些定位需求上的不同。主复本复制方案中，常常需要在复本目标失效后，前一个复本要成为新的主复本。在这种情况下，CRUSH 可以通过在r'=r+f 中重新选择，使用“前n个”作为合适的目标。这里 f 是当前 select(n，t) 失效的定位尝试次数（看算法1第16行）。然而，对于校验与代码擦除场景，在CRUSH 输出的存储设备的等级以及位置都是关键的，因为每一个目标存储了数据对象的不同数据位。特别情况下，如果存储设备失效了，它可以被 CRUSH 的输出列表 ~R 就地替代，这样其列表中的其他的设备保留原来的等级（如在 ~R 中的位置，看图2）。在这种情形下，CRUSH 重新利用 r′= r+ frn 进行选择。这里的 fr 是在 r 中失败尝试次数。这样，就可以为每个复本等级定义一系列的候选者，它在失效概率上是不相关的。相反，RUSH 没有处理失效设备的特定手段；其他已经存在的哈希分布函数，只是隐含地使用“最先的n个”这样的方法，在最终的结果中来跳过失效的设备。这使得它们不能用于处理校验下的场景。
图2：当 r = 2 (b) 的情情况下，在包括 CRUSH 的输出 n 为 6 的 ~R 的盒子中，select(6，disk) 的重新选择行为。左边展示了“最先 n 个”设备的方式，在这样的方式中，已经存在的设备 (c，d，e， f ) 的等级可能会变化。在右边，每个等级的设备在概率上都是独立地可能成为潜在的目标序列；在这里 fr = 1，r'=r+frn=8（设备 h）。
3.3 影射变更与数据移动
在一个大的文件系统中，对于数据分布的一个关键问题，就是在于存储资源增加或者删除时的反映。CRUSH 保留了一致的数据与负载分布方式，以避免负载的不对称，并与可用资源使用不足关联起来。当一个设备失效时，CRUSH 将其标志起来，但是还保留在层级中，但是其不再被选中，而其内容由分布算法统一处理（看3.2.1节）。这样的集群影射更新产生了一种优化结果，即最小化了数据移动因子 wfailed/W（这里 W是所有设备的权重），即总共需要被重新影射到新的设备中的数据占比，因为这里仅有失效设备的数据会被移动。
如果由于存储设备的增加与删除导致集群的层级有修改时，情况变得更复杂。CRUSH 的影射过程——这个过程使用集群影射（clustermap）作为一个有权重的层级决策树——会导致额外的数据移动，从而导致其超过理论的 Dw/W 最优水平。在层级树中的每一级，当相对子树的权重变化会改变分布，某些数据对象就需要从权重下降的子树中移动到那结权重上升的子树中。因为准随机的定位决策在每个层级中的每个结点都是静态独立的，在那个点上数据移动到子树中可以有一致的分布，而不需要重新将其影射到最终对其权重变更负责的叶子项目中。只在定位过程后续的（更深）的层级上，数据（通常不同的）才会移动以保证正确的相对分布。这产生的效果在图3中的二叉树中进行解释。在层级中的数据移动的下界为Dw /W，数据以 Dw 的权重部份存在新添加的设备中。数据移动随着高度 h 的增加而增加，一个保守的渐近上限为 h Dw /W。当 Dw 相对于 W 很小时，移动的数据接近这个上限，因为数据对象在递归的每一步移动到子树中，有一个非常小的概率会被影射到一个相对小权重的项目中。
图3：由于结点的添加以及接下来的权重移动导致数据在二叉树中移动。
3.4 桶类型
总的来说，CRUSH的设计目标是能够实现两个有竞争性的目标：效率以及算法的可扩展性，在集群由于存储设备的添加与删除而发生变动时，通过数据最小的移动以恢复分布的平衡。为了实现这样的目标，CRUSH 在集群构架中定义了4中类型的桶来表示内部结点（非叶子结点）：均桶、列表桶、树桶以及抽签桶。每个桶类型都基于不同的内部数据结构以及使用不同的函数c(r，x) 用来实现在复本定位的过程中，准随机地选择内部项目，以此来形成计算与重新组织效率之间的平衡。一致桶严格限制包括的项目必须具有相同的权重（就好像传统的基于哈希的分布函数），而其他的桶类型则可以包括拥有任意权重的项目。这些不同在表2中列出。
表2：当项目添加或者删除时，影射速度与重组效率在不同的桶类型下的总结
3.4.1 均桶
在大系统中，设备很少单独地添加。相反，新的存储一般都是按相同设备同时部署的，常常是额外添加服务器背板的一个机架，或者是整个机柜。设备达到生命周期末期时，常常也一个类型整体地一起退役（单个失效的不算），因此很自然地将它们做为一个单元进行处理。CRUSH 的均桶就是用来表示这样场景下的相同的设备类型。这么做的关键的好处是与性能相关的：CRUSH 可以以常数时间将复本影射到均桶中。在那些一致性限制不合适的场合，可以使用其他的桶类型。
给定 CRUSH 一个输入值 x 以及一个复本数 r，我们就可以从 m 个一致桶中利用函数 c(r，x) = (hash(x)+rp) mod m 选择一个项，这里 p 是一个随机（但是确定的）选择的大于 m 的质数。对于任何 r ≤ m 我们都可以利用一个简单的数值理论选择一个不同的项。对于 r > m 的情况，这样的保证就不靠谱了，这意味着有两个不同复本 r带有相同的输入 x时有可能产生相同的项。在实践中，这并不表示一个大于零的冲突概率，或者说定位函数需要重来一次（看3.2.1节）。如果均桶的数量变更，就会有一个在设备之间完全的数据重整，就像传统的基于哈希的分配策略一样。
3.4.2 列表桶
列表桶将他们的桶以链表的形式连接起来，并且可以包括不同的权重。为了定位一个复本，CRUSH 在列表头放置最近添加的项并比较其余项的权重和。根据 hash(x， r， item)的值，要么是当前的项以恰当的概率被选择，要么过程会递归向后检测列表其他的项。这种方法是从RUSHP 中继承过来的，在应用时会重回到定位问题“最新添加的项或者是旧项？”对于一个扩张的集群而言，这是一个很自然的选择：要么对象以一定的概率定位到一个最新的设备里，或者让它存在最近的旧设备中。结果是，在添加新桶时，数据迁移来讲都是优化的（译注：就是数据移动很少）。但是当项目被移除或者放到列表尾时，会导致明显的不必要的数据移动，这样导致列表桶适合于集群不会（或者极少）收缩的环境下。
RUSHP 算法大致相当于一个两层的 CRUSH 层级中，组成一个单列表的桶，桶中包括许多的均桶。固定的集群表示导致不能使用定位规则，或者不能使用 CRUSH 的失效域以保证可控的数据定位并增强的可靠性。
3.4.3 树桶
像其他的链表一样，列表桶对于小集群的项是很高效的，但是对于大集合就不太适合了，在那种情况下 O(n) 的运行时间太多。树桶，从 RUSHT 继承而来，通过将这些项存储在一个二叉树中来解决这个问题，因此可以定位时间压缩到 O(logn)，使得它适合于管理大量的设备与内嵌有大量桶的场合。RUSHT 相当于一个两层的 CRUSH 层级，其中包括一个树桶，桶中包含许多的均桶。
树桶按照权重组织成二叉搜索树，项目都在叶子结点中。每个内部结点都知道其左右两个子树的权重，并按一个固定的策略进行了标注（下面描述）。为了在桶中选择一个项，CRUSH 从根开始，并计算输入键 x 的哈希值，复本数据 r，桶标识符以及当前树结点的标注（最开始为 root）。结果与左右子树的权重比较，以此来决定要选择哪个子结点以继续查找。这个过程一直重复，直到到达叶子结点，在叶子结点上，与桶的相关的项就被选中了。在这种桶类型中，只需要计算 logn 次哈希与比较就可以定位一个项。
桶在二叉树中的结点用一个简单的固定的策略来进行标注，以避免在树增长或者收缩时导致标注变化。最左边的树标志为 1。当树扩张时，旧的根点变成新的根结点的左子树，新的根结点就被标注为旧的根点的标注向左移一位（1， 10， 100， 始此等等）。树右边的标注与左边的形成镜像，并且在左点的标注前加1。一个带标注的 6 结点的二叉树显示在图4中。这样的策略保证了新项的加入桶（或者从桶中删除），树都会增长（收缩），对于到达已经存在的叶子结点项的路径，只需要在定位决策树之前，即根结点处添加（删除）额外的结点即可。当一个对象已经存放在一个特定的子树下，它最终的影射只依赖于权重以及在子树中的标注，并且只要子树的项不变时就不会更改。尽管层级的决生策树引入了一些额外的在内嵌项之间的数据迁移，但是这个策略保证这种移动会有一个较合理的层级，就算桶的数量很大的情况下，也能够提供高效的影射。
图4：组成二叉树的每个树桶的结点标注策略。
3.4.4 抽签桶
列表与树桶都是结构化的，因此可以通过计算有限几个哈希值并与权重进行比较，以期选择一个项目。通过这样的方式，问题得以以如下的方式分而治之，即要么是给一个特定的项目优先顺序（如列表开始的项），要么是完全不用考虑整个项目子树的需要。这样就可从提升复本定位过程的性能，但是当桶因为添加、删除、或者重新分配项目权重时导致变化时，也引入了亚优化的重组行为。
抽签桶类型使得所有的项目可以公平地竞争复本的定位，这类似于抽签的过程。为了存放一个复本，一个随机长度的签会被分配给桶中的项目。而具最长签的项目会胜出。刚开始，每个项的签长度都是固定的，并基于 CRUSH 输入x ，复本数，以及桶项目 i 的哈希值确定。每个签长度都会按照项目的权重的某个比例 f (wi) 进行扩展，因此大权重的项目更有可能胜出，如 c(r，x) = maxi ( f (wi)hash(x， r， i))。尽管这样的过程几乎比列表桶要慢两倍，比起树桶来说就更慢了（它的扩展是对数比例的），但是抽签桶产生了优化的内嵌项目修改时的数据移动问题。
如何来选择桶的类型，可以基于集群的增长模式，即在影射函数的计算与数据移动效率之间进行恰当的选择。当桶的类型倾向于固定（如同种磁盘的机架），那么均桶是最快的。如果桶是扩展的，列表桶在添加的项处于列表头时，其提供了很好的数据移动效率。这使得CRUSH恰当将数据迁移到新设备上，而不需要在其他的桶之间进行数据重整。不好的一面就是影射速度是O(n)，并且当旧项目录被移除或者重赋权重时，会导致额外的数据迁移。当在移除设备时并且数据重组的效率是关键因素（例如，接近于层级中根的存储）时，那么抽签桶则提供了很好的子树之间数据迁移的行为。树桶则是所以上所有的组合，即提供了相当不错的性能，同时也有很好的重整效率。
4 评测
CRUSH 基于包括平衡在内的许多的目标，带权重地在异构存储设备之间进行数据分布，在设备删除与添加之时最小的数据移动（包括单个设备的失效），通过将复本分布在不同的失效域中来提升系统的可靠性，以及灵活的集群描述与规则系统，用以说明可用存储并分布数据。我们通过模拟将对象分配到设备中，并检测最终的分布情况，利用这种方式评估了预期的 CRUSH 配置相对于 RUSHP 与RUSHT 风格的集群下的行为。RUSHP 与 RUSHT 通过一个列表桶或者包括了许多均桶的树桶的两层的CRUSH 层次结构来模拟。尽管RUSH 的固定集群表示，导致不能使用定位规则或者在不同的失效域中进行分离（而CRUSH利用这个来提升数据的安全性），但是我们考虑的是它的性能与数据移动行为。
4.1 数据分布
CRUSH 的数据分布应该是随机的——与对象标识符 x或者存储目标无关——结果在同权重的不同的设备之间是平衡的。我们实验性地测试了对象在包含了不同桶类型之间的分布情况，并比较了不同设备使用上的不同，以及二项式概率分布，并期望从统一随机过程中取得理论上的结果。当以概率 pi = wi/ W 分布 n 个对象给定的设备 i 上，我们希望取得通过二项式 b(n， p) 即 m = np，且标准差为 s =pnp(1− p) 所预期的设备使用率。在一个具有很多设备的大型系统中，我们估计 1− p ≃ 1，因此标准差是 ≃ √m，也就是说，即使数据对象数目非常大，那么使用率也是非常高的。正如所预期的，我们发现 CRUSH 分布的一致性与在同构的集群或者混合的系统中的平均二项式方差是匹配的。
4.1.1 过载保护
尽管 CRUSH 在具有大的对象系统中取得了很好的平衡（在设备利用率上有很小的差异），任何的随机过程，这将转换成一个非零的概率，在特定的设备上分配空间都将明显地要比平均情况下要大。与已经存在的概率性影射算法（包括RUSH）不同，CRUSH 包括了一个每设备的过载修正机制，因此可以重新分布设备数据的任何部分。这可以用在设备在有过载危险的情况下，将一部份的数据进行回撤，有选择地“调整”过载的设备。当1000个设备集群中，达到99%的容量时，我们发现 CRUSH 的影射执行时间增长少于20%，尽管过载调整在 47% 的设备中发生，而方差下降1/4，而这正是我们预期的。
4.1.2 方差以及部分失效
之前的研究[Santos et al. 2000]显示了数据的随机分布的性能可与经过仔细数据分块的性能匹敌。在我们对 CRUSH 作为对象存储系统[Weil et al. 2006]数据分配的一部分的性能测试结果来看，我们发现随机对象定位所导致的写性能惩罚大概在5%，这主要是不同的 OSD 之间的负载导致的，并与 OSD 的使用差异相关。但是在实践中这样的差异主要与同种负载相关（通常是写），在这种情况下，仔细分块策略是最有效的。更多的情况下，负载是混合的，并在他们到达磁盘后就开始出现随机了（或者至少与磁盘的布局是无关的），这导致了一个与设备的负载与性能（尽管仔细布局）的相似的差异，并类似地降低了总体的吞吐量。我们发现 CRUSH 缺乏元数据以及可靠的分布来面对可能存在的负载类型，有时性能惩罚远超过在小负载的情况下的情形。这个分析假设的设备容量在不同时间或多或少是静态的。然而真实的系统经验显示，分布式存储的性能常被一些小部分慢的、过载的，有碎片，或者性能很差的设备给拖下来。传统情况下，显式的分配方案可以手工地避免这样的问题，而类哈希的分布函数一般来说都不能。CRUSH 利用现在的过载保护机制，将性能不佳的设备看成是“半失效”的，人为分散一定数量的数据及负载，以此来避免性能瓶颈，并不时地修正负载不平衡的状态。通过将复本的读操作的分布，存储系统本身恰当粒度的负载平衡可以进一步缓合负载的差异，这正如DSPTF 算法 [Lumb et al. 2004]所展示的。这种方式，尽管是一种补充，并不在本论文说讨论的 CRUSH 影射函数之内。
图5：在加入或者删除存储设备时，两级到四级，7290个设备的 CRUSH 层级的数据重组效率，与 RUSHP 和 RUSHT进行比较，1是最优的。
4.2 重组与数据移动
我们在一个有7290个设备的集群中，使用 CRUSH 以及RUSH 测评了由于设备删除与添加而导致的数据移动。CRUSH 集群有四级深度，9行，每行9机柜，每机柜9机架，每机架10个存储设备，总共 7290 个设备，RUSHT 与 RUSHP 与两级的 CRUSH 利用单树或者列表树的影射等同（并相应地）包括729 个均桶，每个桶10个设备。结果与理论的优化的移动数量 moptimal = Dw/W 进行比较，这里 Dw 是 添加或者删除的设备的权重，而W 是总的权重。如果增加一倍的系统容量，我们需要将已经存有的数据的一半移动到设备上，数据重组为次优。
图5 显示了按照移动因子mactual/moptimal来说明的相对的重组效率，这里，1表示优化下的对象数量被移动了，而更大的值表示了额外的移动。X 轴表是添加或者删除 OSDs 数量，Y 轴是移动规模。在所有的情形下，更多的权重变化（相对于整个系统）导致更有效率的重组。RUSHP （单独的大列表桶）占了绝大多数，在设备添加时有最小的（最优化的）移动，并在移除时占有大多数移动（对于最严重的性能惩罚，请看下面的4.3节）。多层级的CRUSH列表桶（只限添加设备）或者抽签桶，有次优的移动效率。CRUSH的树桶有轻微的性能损耗，但也比普通的 RUSHT 好几乎25%（主要是因为在每个树桶中9项目的二叉树有点不平衡）。而在CRUSH 层级的列表桶中删除设备则有最差的效率，这个是与预期相符的（参考3.3节）。
图6显示了对内嵌的项目进行增加删除时，不同的桶类型所表现的重组效率。移动因子在一个修改的树桶中不超过 logn，即树的深度。向抽签桶或者列表桶中添加项目接近最优情况。均桶修改导致了数据的完全重整。对于列表尾的修改（如删除最老的设备）相似地压缩的数据移动，这部分主要是由于桶的大小。尽管有确定的限制，但是列表桶在整个的存储层级中都是比较合适的桶类型，在这种场景下，删除比较少发生，规模大小对性能的影响就最小化了。一个混合的方案包括均桶，列表桶，树桶以及抽签桶在多个的重组场景下能够最小化数据移动，同时能够保证很好的影射性能。
图6：对不同的桶类型下添加删除项目时的重组效率。1 是最优的，抽签桶与列表桶一般是最优的，尽管从列表桶尾部删除项目时，桶导致了较差的行为。树桶的变化在桶大小的对数的范围内。
图7：CRUSH 与 RUSHT 的计算时间相对于层级大小以对数增加。
图8：将复本映射到单个的 CRUSH 桶的低层速度与桶大小的对比。均桶会有常数时间，树桶有对象时间，而列表桶与抽签桶是线性时间。
4.3 算法性能
计算 CRUSH的性能在设计上是非常快的，对于一个有 n 个OSDs 设备的系统中为 O(logn)，因此设备可以快速地对对象进行定位，或者，在集群变化后，能够为已经存储对象重新计算适当的存储目标。我们验证了 CRUSH 在不同的集群大小里数百万个影射，相对于RUSHP 和 RUSHT的性能。图7显示针对的一组集群复本，其中包括8个项目的树桶与均桶（层级深度不相同）的平均的影射时间（以毫秒计），并与有固定两层的 RUSH 进行了比较。X 轴是系统的设备数量，并以对数方式呈现，这样可以与存储层级深度进行对应。CRUSH 的性能是设备数据相关的对数。RUSHT 稍微强于 CRUSH，主要是因为较简单的代码复杂度，同时在列表桶与抽签桶上比较相近。RUSHP 在这次测试中以线性方式扩展（在32768个设备中需要比 CRUSH 多25倍的时间），尽管在实践中，新加入的设备的磁盘以指数化增加时，我们可以取得一个稍微近线性的规模提升[Honicky and Miller 2004]。这些测试由 2.8GHz 的 Pentium 4来执行，整体的影射时间为数十毫秒。
CRUSH 的性能依赖于存储层级的深度，以及构建集群的桶的类型。图8比较了c(r，x)，作为桶大小（X轴）的函数，从每种桶类型中选择一个复本的时间（Y轴）。在最高层，CRUSH 的以O(logn)方式扩展，即与层级深度之间为线性关系，在单个桶上为O(n)（列表与抽签桶线性扩展）并不会超过固定的最大大小。什么时间什么地方使用单个桶类型依赖于预期添加、删除或者重新分配权重的设备的数量。列表桶提供了比抽签桶稍微强一些的性能，尽管当删除时有可能会导致数据的完全重整。树桶对于大数量或者有变化的集群环境中，它能够提供较好的计算与重新组织的代价。
对于CRUSH 的核心，即性能，无论是执行时间还是执行结果，使用的都是整数哈希。准随机的数据计算使用多个整数输入哈希函数，其基于 Jenkin’s 32-bit 哈希 mix [Jenkins1997]。在当前的形式中，CRUSH 影射函数的时间的45%是花在哈希的计算上，这导致哈希成为总体执行速度与分布质量的关键，并作为优化的目标。
4.3.1 被忽略的老化问题
CRUSH 将失效的设备留在存储层级中，主要是因为失效常常是一个临时事件（失效的磁盘常常被换掉）。同时这样，也保证了不会发生无效率的数据移动。如果存储系统的年龄问题被忽略的话，当设备失效而不补替换就会成为一个大问题。尽管 CRUSH 会将数据分布到未失效的设备上，但是会导致一些性能惩罚，这是因为在定位算法中有更高的定位取消概率。我们评测了 1000个设备的集群的影射速度，并在不同的百分比上存在失效设备。在一个相对极端的设备失效场景下，即一半的设备都无法使用，影射的计算时间增加了 71%。（这样的情形可能导致很大的问题，因为每个设备的负载由于负载加倍而导致IO性能的严重下降。）
4.4 可靠性
数据安全在大的存储集群中是极为重要的，因为在这样的集群中有大量的设备，因此硬件失效是一种常规问题，而不是意外问题。像 CRUSH 算法这样的随机化分布策略，会存在所谓的“逆集群”复本，这也是引起很大兴趣的地方。因为它扩展了多个设备之间进行数据共享的数量。它有两个完全竞争以及相反的效果。首先，对于失效的恢复可以并行进行，因为在大量的结点中，每个结点所分到的数据位就相对较小，从而压缩的恢复时间，以及缩小了对于额外失效的脆弱性窗口。第二，对于大结点集合，则意味着两个有共享数据的设备同时失效的可能性的上升。对于2-路镜像，这两个因素相互导致对方不可用，而全体数据的安全性在多于两个复本下由于“逆集群”化而更加高[Xin et al. 2004]。但是，多个设备失效问题的关键是，一般来说，可以认为它们是无关的——在多数情况下，一个独立的事件，像电源失效或者物理干扰会影响多个设备，因此大的结点集群，由于“逆集群”复本，能够极大地增加数据丢失的风险。CRUSH 将复本在多个失效域中进行分隔（而这在 RUSH 中不存在，或者不存在基于哈希的方案）正是防止这些并发，相关的失效问题的出现而导致数据丢失而进行的特别设计。尽管，很明显风险是下降了的，但是却很难对其对系统可靠性进行定量，这主要是因为没有特定的集群配置以及与之相关的历史失效数据来进行分析。虽然我们希望在未来去做这样的研究，但是这不是本论文要讨论的问题。
5 未来的工作
CRUSH 作为 Ceph 的一部份进行开发，这是一个PB 级的分布式文件系统[Weil et al. 2006]。当前的研究包括一个智能的，可靠的分布式对象存储系统，它极大依赖于 CRUSH的特性。当前 CRUSH 所使用的最初的规则结构，只是到足够支持当前我们能够想到的数据分布策略的复杂程度。一些系统会有一些特定的需求，这会需要一个更加强大的规则结构。
尽管数据安全考虑的主要是并发性失效问题，也是设计 CRUSH 的最初动机，但是对于真实系统的研究也需要，以此来确定他们的特点以及频率，这需要Markov或者其他的定量模型可以被用来精确地评估系统的平均数据丢失时间（MTTDL）。
CRUSH 的性能高度依赖于足够强的多输入整数哈希函数。因为它同时也会影响算数上的正确性——即分布结果的质量——也会影响速度，对于用于CRUSH快速哈希技巧的研究也要。
6 结论
分布式文件系统对于数据定位提出了不寻常的可扩展挑战。CRUSH通过将利用准随机的哈希函数来应对了这些挑战，这些准随机函数通过取消传统方法中需要分配元数据的方案，代之以通过层级化的有权重地描述可得的存储来分发数据。集群影射的层级结构能够反映底层的物理组织以及安装的基础结构，像存储设备如何组成机架，机柜，以及数据中心的行，以此允许用来定义定位规则。同时，可以利用广泛的，各种类型的策略来将数据复本影射到用户所定义的失效域中（比如独立的电源与网络基础结构）。通过这样，CRUSH 可以减轻由于关联设备失效所带来的系统脆弱性，这是通过复本技术进行的“逆集群”化的准随机系统中的典型特点。CRUSH 同时也解决了设备过载所带来的风险，这些风险在这些方法中是天生存在的，CRUSH 通过将数据从过载的设备中有选择性地进行分散，这样能够最小化计算代价。
CRUSH 以计算效率以及必要的元数据方面，极为有效的方式完成以上的目标。影射计算具有 O(logn) 的运行时间，即只需要几十毫秒就可以为数千个设备进行计算。再与效率、可靠性、灵活性结合，使得 CRUSH 成为大型分布式存储系统的理想选择。
7 致谢
R.J. Honicky 在 RUSH 上的优秀工作，激发了我们开发 CRUSH。与 Richard Golding， TheodoreWong，以及存储系统研究中心的员工与学生之间进行的讨论，对于促进并优化算法非常有帮助。CRUSH 工作部分获得Lawrence Livermore National Laboratory的支持。
8 Availability
CRUSH的源代码在 LGPL 下发布，并可在此获得：http://www.cs.ucsc.edu/~sage/crush（注：已不可用）
参考文献
ANDERSON， E.， HALL， J.， HARTLINE， J.， HOBBS， M.， KARLIN， A. R.， SAIA， J.， SWAMINATHAN， R.， AND
WILKES， J. 2001. An experimental study of data migration algorithms.In Proceedings of the 5th International Workshop on Algorithm Engineering， Springer-Verlag， London， UK， 145–158.
ANDERSON， E.， HOBBS， M.， KEETON， K.， SPENCE， S.， UYSAL， M.， AND VEITCH， A. 2002. Hippodrome: running circles around storageadministration. In Proceedings of the 2002 Conference on File and StorageTechnologies (FAST).
AZAGURY， A.， DREIZIN， V.， FACTOR， M.， HENIS， E.， NAOR， D.， RINETZKY， N.， RODEH， O.， SATRAN， J.，
TAVORY， A.， AND YERUSHALMI， L. 2003. Towards an object store. In Proceedings ofthe 20th IEEE / 11th NASA Goddard Conference on Mass Storage Systems and Technologies， 165–176.
BRAAM， P. J. 2004. The Lustre storage architecture. http://www.lustre.org/documentation.html， Cluster
File Systems， Inc.， Aug.
BRINKMANN， A.， SALZWEDEL， K.， AND SCHEIDELER， C. 2000. Efficient， distributed data placement strategies for storage areanetworks. In Proceedings of the 12th ACM Symposium on Parallel Algorithmsand Architectures (SPAA)， ACM Press， 119–128. Extended Abstract. CHOY， D. M.， FAGIN， R.， AND STOCKMEYER， L. 1996. Efficientlyextendible mappings for balanced data distribution. Algorithmica 16， 215–232.
GHEMAWAT， S.， GOBIOFF， H.， AND LEUNG， S.-T. 2003. TheGoogle file system. In Proceedings of the 19th ACM Symposium on OperatingSystems Principles (SOSP ’03)， ACM.
GOBIOFF， H.， GIBSON， G.， AND TYGAR， D. 1997. Security fornetwork attached storage devices. Tech. Rep. TR CMU-CS-97-185， Carniege Mellon， Oct.
GOEL， A.， SHAHABI， C.， YAO， D. S.-Y.， AND ZIMMERMAN， R. 2002. SCADDAR: An efficient randomized technique toreorganize continuous media blocks. In Proceedings of the 18thInternationalConference on Data Engineering (ICDE ’02)， 473–482.
GRANVILLE， A. 1993. On elementary proofs of the Prime NumberTheorem for Arithmetic Progressions， without characters. In Proceedings of the 1993 Amalfi Conference onAnalytic Number Theory， 157–194.
HONICKY， R. J.， AND MILLER， E. L. 2004. Replication under scalable hashing: A familyof algorithms for scalable decentralized data distribution. In Proceedingsof the 18th International Parallel & Distributed Processing Symposium (IPDPS2004)， IEEE. JENKINS， R. J.， 1997. Hashfunctions for hash table lookup. http://burtleburtle.net/bob/hash/evahash.html.
KARGER， D.， LEHMAN， E.， LEIGHTON， T.， LEVINE， M.， LEWIN， D.， AND PANIGRAHY， R. 1997. Consistenthashing and random trees: Distributed caching protocols for relieving hot spotson theWorldWideWeb. In ACM Symposium on Theory of Computing， 654–663.
LUMB， C. R.， GANGER， G. R.， AND GOLDING， R. 2004. D-SPTF:Decentralized request distribution in brick-based storage systems. In Proceedingsof the 11th International Conference on Architectural Support for Programming Languagesand Operating Systems (ASPLOS)， 37–47.
NAGLE， D.， SERENYI， D.， AND MATTHEWS， A. 2004. ThePanasas ActiveScale storage cluster—delivering scalable high bandwidth storage.In Proceedings of the 2004 ACM/IEEE Conference on Supercomputing (SC ’04).
RODEH， O.， AND TEPERMAN， A. 2003. zFS—a scalable distributed file system usingobject disks. In Proceedings of the 20th IEEE / 11th NASA Goddard Conferenceon Mass Storage Systems and Technologies， 207–218.
SAITO， Y.， FRØLUND， S.， VEITCH， A.， MERCHANT， A.， AND SPENCE， S. 2004. FAB:Building distributed enterprise disk arrays from commodity components. In Proceedingsof the 11th International Conference on Architectural Support for ProgrammingLanguages and Operating Systems (ASPLOS)， 48–58.
SANTOS， J. R.， MUNTZ， R. R.， AND RIBEIRO-NETO， B. 2000. Comparingrandomdata allocation and data striping in multimedia servers. In Proceedingsof the 2000 SIGMETRICS Conference on Measurement and Modeling of ComputerSystems， ACM Press， Santa Clara， CA， 44–55.
SCHMUCK， F.， AND HASKIN， R. 2002. GPFS: A shareddisk file system for largecomputing clusters. In Proceedings of the 2002 Conference on File andStorage Technologies (FAST)， USENIX， 231–244.
TANG， H.， GULBEDEN， A.， ZHOU， J.， STRATHEARN， W.， YANG， T.， AND CHU， L. 2004. A self-organizing storage cluster for paralleldata-intensive applications. In Proceedings of the 2004 ACM/IEEE Conferenceon Supercomputing (SC ’04).
WEIL， S. A.， BRANDT， S. A.， MILLER， E. L.， LONG， D. D. E.， AND MALTZAHN， C. 2006. Ceph: Ascalable， high-performance distributed filesystem. In Proceedings of the 7th Symposium on Operating Systems Design and Implementation(OSDI).
XIN， Q.， MILLER， E. L.， AND SCHWARZ， T. J. E. 2004. Evaluationof distributed recovery in large-scale storage systems. In Proceedings ofthe 13th IEEE International Symposium on High Performance Distributed Computing(HPDC)， 172–181.