CRUSH：受控的、可扩展的数据副本分散存储方案(Part 3)
** 以下内容为翻译
** 原文及版权声明：http://ssrc.ucsc.edu/Papers/weil-sc06.pdf
** 翻译：softrank.net@gmail.com
** 转载请保留以上信息
** 欢迎各位游客指正翻译中的错误，或提出建议
CRUSH：受控的、可扩展的数据副本分散存储方案
作者：Sage A. Weil Scott A. Brandt Ethan L. Miller Carlos Maltzahn
美国加州大学圣克鲁兹分校存储系统研究中心
{sage, scott, elm, carlosm}@cs.ucsc.edu
3.2 副本位置策略
CRUSH的设计使数据得以均匀地分布在带权重的设备上，在统计意义上保持了存储和设备带宽的均衡使用。副本在树状结构中放置的位置对于数据安全性也有着关键性的影响。通过对于系统本质物理结构的映射，CRUSH能够建模，从而定位潜在的相关设备故障源。典型的故障源包括物理位置上接近、共享电源、共享网络。通过将这些信息编码到Cluster Map中，CRUSH的位置策略能够将对象副本分隔到不同的故障域中，同时维持预期的数据分布形式。例如，为了应对出现并发故障的可能性，也许会需要确保数据副本在不同机架、不同机柜、不同电源、不同控制器、不同物理位置的设备上。
CRUSH可以被用于不同的数据副本策略和不同的硬件配置下，为了适应这样的多样性场景的需求，CRUSH为其使用的每个副本策略或分布策略定义Placement Rule，以保证系统或管理员可以确切地指定数据副本如何定位。例如，某人可能设定了某种规则，在某两个目标上使用双重镜像，在某三个设备上使用三重镜像，在某六个存储设备上使用RAID-4等等[注释1：尽管可以用各种各样的数据冗余机制，我们为了简化问题只讨论以副本形式存放的数据对象，也不损失任何的通用性]。
每条规则包含用户简单执行环境的用于树状结构的指令序列，这个运行环境可以用[算法1]中的伪代码来描述。CRUSH算法的输入参数x通常是对象的名称或者其他标识符，比如将被存放在同一个设备上的一组对象的标识符。take(a)操作从层次结构中选中一个项目（往往是一个桶），并将其赋予
，将作为后续操作的输入。select(n,t)操作对中的每一个元素i进行迭代，选择n个以i节点为根的子树下具有t类型的项。存储设备都有一个已知的、确定的类型，系统中的每个桶有一个类型字段用于区分不同类型的桶（例如，某些代表“rows”，有些代表“cabinets”）。对中的每一个元素i，select(n,t)操作对于1到n之间的每一个数r被迭代调用，n是请求的项数，操作将递归向下经过任何中间节点的桶，用c(r,x)函数（在章节3.4中为每种类型的桶分别定义）伪随机地在每个桶中选中一个被嵌套的项目，直到找到了满足要求类型t的项。结果的
个项，被放回到输入变量，可以作为后续的select(n,t)操作的输入参数，也可以通过emit操作将其移入结果向量。
，将作为后续操作的输入。select(n,t)操作对中的每一个元素i进行迭代，选择n个以i节点为根的子树下具有t类型的项。存储设备都有一个已知的、确定的类型，系统中的每个桶有一个类型字段用于区分不同类型的桶（例如，某些代表“rows”，有些代表“cabinets”）。对中的每一个元素i，select(n,t)操作对于1到n之间的每一个数r被迭代调用，n是请求的项数，操作将递归向下经过任何中间节点的桶，用c(r,x)函数（在章节3.4中为每种类型的桶分别定义）伪随机地在每个桶中选中一个被嵌套的项目，直到找到了满足要求类型t的项。结果的个项，被放回到输入变量，可以作为后续的select(n,t)操作的输入参数，也可以通过emit操作将其移入结果向量。
举例说明，[表1]中定义的规则从[图1]中层次结构的root开始，通过第一次select(1,row)操作选中了一个类型为“row”的桶（它选中了row2）。后续的select(3,cabinet)操作在之前选择的row2下面选择了三个各不相同的cabinet（cab21、cab23、cab24），最后一次select(1,disk)在三个cabinet桶之间进行了迭代，对每个cabinet桶在其子树中各选择了1个disk。结果就是分散在3个cabinet中的3个disk，但都在同一个row中。这种方式使得副本能够被同时分发到指定类型（例如row、cabinet、shelf）的设备上，这对提升可靠性与性能都很有帮助。规则包含多个take、emit块，使存储目标可以从不同的存储池中被显式选取出来，在存在远程副本的场景下（某一个副本被存放在远程站点）或者分层架构中（例如高速的近线存储搭配低速大容量阵列）也许会被采用。
![图1：某四级集群映射层次结构的部分视图，包含row、cabinet、shelf和disk。粗体字标出的表示在[表1]中描述的Placement Rules和假想的映射关系中，被每次select操作选中的项。](/user_files/deltamaster/Image/图1.png)
[图1：某四级集群映射层次结构的部分视图，包含row、cabinet、shelf和disk。粗体字标出的表示在[表1]中描述的Placement Rules和假想的映射关系中，被每次select操作选中的项。]
| 动作序列 |
结果 |
|---|---|
| take(root) | root |
| select(1,row) | row2 |
| select(3,cabinet) | cab21 cab23 cab24 |
| select(1,disk) | disk2107 disk2313 disk 2437 |
| emit |
[表1：一条简单的规则，将三个副本分发到同一个row的三个不同的cabinet中。]
[算法1：CRUSH确定对象x的存放位置]
3.2.1 冲突、故障和过载
select(n,t)操作可能为了定位n个各不相同的t类型的项而从起点开始向下遍历而经过许多层，递归过程的次数由r=1,...,n确定，n是选择的副本个数。处理过程中，CRUSH可能会由于下面三个不同的原因而用修改过的输入r'来拒绝并重选项：某个项已经在当前的集合中了（发生了冲突，select(n,t)的结果必须是各不相同的）；有一个设备失效了；有一个设备过载了。失效或过载的设备会在Cluster Map中进行相应的标记，但为了避免不必要的数据移动，不会从层次结构中移除它们。CRUSH通过根据Cluster Map中指定的概率伪随机地拒绝选择过载设备，来选择性地转移此过载设备上的少部分数据，这个概率则是与报告的过载情况有关的。对于失效或过载的设备，CRUSH通过重新启动select(n,t)开始部分的递归过程（详见[算法1第11行]），均匀地在存储集群中重新分布这些项。而对于冲突的情况，则在递归内层使用r'替换r来进行局部搜索（详见[算法1第14行]），不至于在那些很可能发生冲突的子树中（例如，桶的容量小于n）改变总体的数据分布。
3.2.2 副本排序
与奇偶校验码、擦除码相比，副本方式在存储位置要求上有些许的不同。在主拷贝副本模式中，发生故障时让之前的副本目标（已经有数据的一份拷贝）成为新的主拷贝是可取的。在这种情况下，CRUSH可以通过用r'=r+f进行重选，来使用“前n个”合适的目标，f是当前select(n,t)操作中确定放置位置失败的次数（详见[算法1第16行]）。而对于奇偶校验码或者擦除码模式，CRUSH算法输出的存储设备的顺序就至关重要了，因为每个目标都存放了数据对象的不同比特位。特别地，当某个存储设备发生故障时，它需要在CRUSH的输出列表
的对应位置上被替换，其他列表中的设备要维持位置不变（位置就是指在的对应位置，详见[图2]）。在这种情况下，CRUSH通过
进行重选，其中
是第r此迭代时失败的次数，这样就为每一个向量位置上的项定义了一系列候选项，每个候选项与其他位置上的候选项是无关的。相比之下，RUSH对于发生故障的设备没有特殊处理，就像其他现有的散列分布式函数，它隐式地假设使用“前n个”的策略在结果中跳过失效的设备，在奇偶校验这样的模式下就难以使用了。
的对应位置上被替换，其他列表中的设备要维持位置不变（位置就是指在的对应位置，详见[图2]）。在这种情况下，CRUSH通过进行重选，其中是第r此迭代时失败的次数，这样就为每一个向量位置上的项定义了一系列候选项，每个候选项与其他位置上的候选项是无关的。相比之下，RUSH对于发生故障的设备没有特殊处理，就像其他现有的散列分布式函数，它隐式地假设使用“前n个”的策略在结果中跳过失效的设备，在奇偶校验这样的模式下就难以使用了。
[图2：select(6,disk)当设备r=2(b)被拒绝时的重选行为，方框中包含了CRUSH当n=6台设备时按编号顺序输出的。左边表示“前n个”方案，已有设备（c、d、e、f）的序号可能发生改变。在右边，每个序号都有独立的一系列可能的目标，在这里=1，且=8（设备h）。]
。左边表示“前n个”方案，已有设备（c、d、e、f）的序号可能发生改变。在右边，每个序号都有独立的一系列可能的目标，在这里=1，且=8（设备h）。]3.3 映射变更与数据移动
大型文件系统中数据分布的一个关键问题是增删存储资源时的响应方式。CRUSH始终保持数据的均匀分布，以避免负载的不均衡，以及可用资源没有得到充分利用的情况。当某个设备发生故障的时候，CRUSH会为其置上标记，但仍然将其保留在层次结构中，下次选择时将被CRUSH算法拒绝，并根据位置算法（详见[章节3.2.1]）均匀地将将其内容分发到其他的设备上。这样的Cluster
Map变化使得需要重新映射到新存储目标上的数据最少，这个比例是
（其中W是所有设备的权重总和），因为只有失效设备上的数据被移动了。
（其中W是所有设备的权重总和），因为只有失效设备上的数据被移动了。
当集群的层次结构由于增删存储资源而发生改变时情况要更加复杂。CRUSH的映射过程，将Cluster Map作为带权的决策树，可能导致额外的数据移动，超过理论上最佳的比例
。在层次结构的每一层，每一次相关子树的权值改变，都要改变数据分布，一部分数据对象就需要从权值下降的子树移动到权值上升的子树中。由于层次结构中每个节点上的伪随机位置决策在统计意义上是相互独立的，移入某个子树的数据被均匀地分布在那一点下，而且并不一定需要被重新映射到直接导致权值变化的那个叶子节点中。只有在定位过程相对比较深的层次，才会为维持总体的数据分布而移动数据。在一个二叉树结构中的大致效果在[图3]中进行了展示。
。在层次结构的每一层，每一次相关子树的权值改变，都要改变数据分布，一部分数据对象就需要从权值下降的子树移动到权值上升的子树中。由于层次结构中每个节点上的伪随机位置决策在统计意义上是相互独立的，移入某个子树的数据被均匀地分布在那一点下，而且并不一定需要被重新映射到直接导致权值变化的那个叶子节点中。只有在定位过程相对比较深的层次，才会为维持总体的数据分布而移动数据。在一个二叉树结构中的大致效果在[图3]中进行了展示。
数据移动的最小量是，这一部分数据会被移动到新增的权值为
的设备上。数据的移动量随着层次结构的高度h的增加而增加，数据移动量渐进地趋向
。当相对于W足够小的时候，数据的移动量就趋近于上界，因为递归过程的每一步数据对象移动到一颗子树时，被映射到权值很小的项上的概率很小。
，这一部分数据会被移动到新增的权值为的设备上。数据的移动量随着层次结构的高度h的增加而增加，数据移动量渐进地趋向。当相对于W足够小的时候，数据的移动量就趋近于上界，因为递归过程的每一步数据对象移动到一颗子树时，被映射到权值很小的项上的概率很小。
[图3：在二叉树结构中由于增加一个节点，一系列权值改变造成的数据移动示意图。]
3.4 桶的类型
一般地，CRUSH算法的设计是为了权衡两个互斥的目标：映射算法的效率与可靠性，增删设备导致的集群变更时恢复平衡的数据迁移成本最小化。为此，CRUSH定义了四种不同类型的桶来代表集群层次结构中的中间节点（非叶子节点）：Uniform Bucket、List Bucket、Tree Bucket、Straw Bucket。每种桶都基于一种不同的内部数据结构，并且分别使用了不同的在定位过程中选择嵌套项的伪随机函数c(r,x)，体现了计算效率和数据重组效率之间的不同权衡方法。Uniform Bucket要求桶内所有的项权值必须相等（更像那种传统的散列分布函数），而其他类型的桶可以包含任意权值的项的任意组合。这些区别在[表2]中进行了总结。
| 项目名 | Uniform | List | Tree | Straw |
| 速度 | O(1) | O(n) | O(log n) | O(n) |
| 添加项 | 差 | 最优 | 好 | 最优 |
| 移除项 | 差 | 差 | 好 | 最优 |
[表2：不同类型的桶当从桶中增加或移除项时，映射速度和数据重组效率的总结。]
3.4.1 Uniform Bucket
在大型系统中设备很少一个一个添加，相反，新的存储往往部署一批相同的设备来提供的，通常是一个服务器机架甚至是一整个机柜。超过年限的设备也通常是成组退役（单点故障除外），那么就很自然可以将它们视为一个整体。CRUSH的Uniform Bucket就可以表示这种情况下的一组相同设备。这样做的关键优势与性能有关：CRUSH可以在常数级的时间复杂度内将副本映射到Uniform Bucket。在不满足这种均匀的限制条件的时候，就可以使用其他类型的桶。
给定一个CRUSH输入参数x和副本数量r，我们在大小为m的Uniform Bucket中使用函数c(r,x)=(hash(x)+rp) mod m选择一个项，p是一个比m大的随机选出的（但确定性的）素数。对于任意的
，根据一些数论原理，我们总能够根据输入选出各不相同的项。[注释2：等差数列的素数定理[Granville 1993]说明了，这个函数会提供mφ(m)种不同的方式，将对象x的副本进行分发，每种分发方式的选取都是等概率的，φ()是欧拉φ函数。]对于
的情况这一点就无法保证了，这表示同一个输入的两个不同副本也许会被映射到同一个项中。实际应用中，这就表示位置算法产生冲突并导致后续的回溯动作并不是不可能的（详见[章节3.2.1]）。
，根据一些数论原理，我们总能够根据输入选出各不相同的项。[注释2：等差数列的素数定理[Granville 1993]说明了，这个函数会提供mφ(m)种不同的方式，将对象x的副本进行分发，每种分发方式的选取都是等概率的，φ()是欧拉φ函数。]对于的情况这一点就无法保证了，这表示同一个输入的两个不同副本也许会被映射到同一个项中。实际应用中，这就表示位置算法产生冲突并导致后续的回溯动作并不是不可能的（详见[章节3.2.1]）。
Uniform Bucket的大小如果改变，那么设备中的数据会被完全重组，更像是那种传统的基于散列函数的分布策略。
3.4.2 List Bucket
List Bucket将其中的内容组织为链表，并能容纳任意权重的项。定位一个副本时，CRUSH从存有最近添加的项的链表头部开始，并比较其权重与所有其余项的总和。根据hash(x,r,item)的结果，要么当前项按一定合适概率被选中，要么就继续处理列表中的下一项。这种方式来源于RUSHP，将定位的问题改造为“是最近添加的还是以前添加的项”。在一个不断扩展的集群中这是一种自然而又符合直觉的办法：要么对象按一定合适的概率被分配到最新的设备中，要么对象还是留在以前的设备中。这使增删桶中的项时数据移动最小化。而当列表中间或者末尾的项被移除的时候，会导致大量不必要的数据移动，因此List Bucket适用于从不或很少收缩的桶。
RUSHP算法大致相当于两层的CRUSH层次结构，由一个List Bucket包含许多Uniform Bucket。这种固定的表示形式，不包含Placement Rule的使用，或者CRUSH中为了增强可靠性的、用于控制数据定位的失效域。
3.4.3 Tree Bucket
和任何链式的数据结构一样，List Bucket在比较小的项目集合下还算高效，但对于大的集合就不那么理想了，O(n)的运行时间就显得太多了。由RUSH[T]演变而来的Tree Bucket通过以二叉树形式存放项来解决这个问题，将定位时间降低为O(log(n))，使其适用于管理大得多的设备数量，或者嵌套的桶结构。RUSHT等效于一个两层的CRUSH层次结构，一个Tree Bucket，每个节点是Uniform Bucket。
Tree Bucket是带权的二叉排序树，所有项位于叶子节点。每个内部节点都知道其左右子树的总权重，并以一种固定的策略进行标记（将在后面详述）。要在桶中选出一项，CRUSH从树的根节点开始，计算输入参数x、副本数量r、桶标识符和当前节点（初始是根节点）的标记的散列值。结果将分别与左右子树的权重比进行比较，以决定接下来访问哪个子节点。过程循环至到达叶子节点为止，最终指向的对应桶中的项就被选中了。要定位一个项只需要log(n)次散列计算和节点比较。
桶的二叉树节点总是用一种简单固定的从策略进行二进制值标记，以避免树的增长和收缩导致标记的变化。树最左侧的叶子节点总是被标记为“1”。每次树扩展的时候，旧的根节点就成为新的根节点的左孩子，新根节点的标记是旧根节点标记左移一位（1、10、100……）。右孩子的标记和左孩子标记的基础上在每个标记左侧增加一个“1”。一棵有6个节点的二叉树标记如[图4]所示。这一策略保证了当新的项添加（或删除），桶和树结构增长（或收缩），通向现有叶子节点的项仅通过增加（或删除）根节点，在决策树的初始位置发生变化。一旦某个对象被放置在某个特定的子树中，只要这棵子树中的项保持固定不变，这项的最终映射就只与权值和节点标记有关了，并且节点标记也保持不变。尽管层次化的决策树造成了嵌套项之间一些额外的数据迁移，不过额外的数据迁移还是控制在合理的范围之内，并且能为很大规模的桶提供高效的映射。
[图4：组成Tree Bucket的二叉树节点标记策略。]
3.4.4 Straw Bucket
List Bucket和Tree Bucket的结构，使得选择一个桶中的项只需要有限次的散列值计算和权重比较。这样做时，它们使用分而治之的方法，给特定项提供优先选择的机会（例如，在列表首部的项），或消除了考察整棵子树中所有项的必要。这提升了定位副本过程的性能，不过桶的内容因为设备增删或调整权重而改变的时候，就不能保证数据重组的最优化了。
Straw Bucket让所有项能够通过类似抽签的方法与其他项公平“竞争”。要定位一个副本，每个桶中的项都被分配到一根随机长度的麦秆，抽到最长麦秆的项就胜出了。每根麦秆的初始长度都是某个固定范围内基于CRUSH的输入x、副本数量r、桶中的项i的散列值的一个值。每根麦秆的长度再根据基于项权值的因子
进行缩放，因此权值较大的项比较容易胜出，即
。[注释3：尽管的简单封闭形式还没有找到，但通过程序方式来计算权值因子还是比较简单易行的（源代码可供参考）。只有在桶发生修改时，才需要重新计算一次这个因子。]尽管这一过程要比List Bucket慢上（平均）几乎一倍，比Tree Bucket（对数数量级）更慢，Straw Bucket却提供了修改时嵌套项间的最佳数据移动。
进行缩放，因此权值较大的项比较容易胜出，即。[注释3：尽管的简单封闭形式还没有找到，但通过程序方式来计算权值因子还是比较简单易行的（源代码可供参考）。只有在桶发生修改时，才需要重新计算一次这个因子。]尽管这一过程要比List Bucket慢上（平均）几乎一倍，比Tree Bucket（对数数量级）更慢，Straw Bucket却提供了修改时嵌套项间的最佳数据移动。
桶类型的选择应该是由预期的集群增长模式来指导，以权衡映射方法的运算量和数据移动的效率，我们总该做好这样的权衡。当桶预期是固定的（比如，一个机架的相同磁盘），Uniform Bucket最快。当桶预期只会增长，List Bucket在列表头部添加新项时能提供最少的数据移动，这使CRUSH可以准确地转移恰当的数据量到新添加的设备中而不去影响其他桶中的项，缺点是O(n)的映射速度和当旧项被移除或改变权重时的额外数据移动。在很可能移除设备，并且数据重组效率要求很高的场合（例如，靠近存储层次根节点处），Straw Bucket提供了子树间最少的数据迁移。而Tree Bucket则是全面妥协，提供了出色的性能的同时，也保证了令人满意的数据重组效率。
CRUSH：受控的、可扩展的数据副本分散存储方案(Part 2)
** 以下内容为翻译
** 原文及版权声明：http://ssrc.ucsc.edu/Papers/weil-sc06.pdf
** 翻译：softrank.net@gmail.com
** 转载请保留以上信息
** 欢迎各位游客指正翻译中的错误，或提出建议
CRUSH：受控的、可扩展的数据副本分散存储方案
作者：Sage A. Weil Scott A. Brandt Ethan L. Miller Carlos Maltzahn
美国加州大学圣克鲁兹分校存储系统研究中心
{sage, scott, elm, carlosm}@cs.ucsc.edu
2 相关工作
基于对象的存储作为一种提高存储系统扩展能力的机制，受到了广泛的关注。一些研究项目和生产文件系统已经开始使用这种基于对象的思想，包括影响力很大的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]和Federated Array of Bricks（FAB）[Saito et al. 2004]在数据分布问题上都面临着相似的挑战。在这种系统中，使用半随机或者启发式的方法来将新数据分配到可用的设备，但随着时间推移，数据也很少为了维持负载平衡而被重定向。更重要的是，所有这些系统都通过某种元数据目录来定位数据，而CRUSH则是依赖一个紧凑的集群描述和确定性的映射函数。这种特点的优势在写入数据时尤为显著，使用CRUSH的系统可以独立计算出新数据的存储目标位置，而不需要询问中心分配器。Sorrento[Tang et al. 2004]存储系统使用一致性散列函数[Karger et 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]最为近似，CRUSH算法是以RUSH为基础的。RUSH是这篇文章中提到的算法中，唯一使用映射函数代替元数据列表，并支持带权重的设备的高效添加与移除。尽管已经具备了这些特性，仍然有一系列的问题，导致RUSH还无法应用于实际问题。CRUSH算法完全泛化了RUSHP和RUSHT中有用的元素，并且解决了之前遗留的可靠性问题、副本问题，并实现了性能和灵活性的提升。
3 CRUSH算法
CRUSH算法根据每台设备的权重在存储设备间分发数据，大致是均匀分布的。数据分发是由一个层次化的Cluster Map控制的，Cluster Map描述了可用的存储资源，由建立集群映射的一些逻辑元素所组成。例如，某个Cluster Map可能描述了一个大型装置，包含了一排机柜，每个机柜有许多磁盘架，每个磁盘架上有许多存储设备。数据分配策略是由Placement Rules定义的，Placement Rules指定了从及群众选中的副本目标的数量，以及放置这些副本的限制条件。例如，某个Placement Rule也许会指定三个镜像副本要被放置在不同的物理机柜上，以避免这些副本共享同一条供电线路。
给出一个整型输入值x，CRUSH会输出一个有序的、包含n个各不相同的存储目标的R向量。CRUSH使用一个多输入的整形散列函数，参数列表包含x，使得映射是完全独立且确定性的，仅仅依赖于Cluster Map、Placement Rules和输入参数值x。数据分发是伪随机的，输出结果与输入值或者设备中现有的对象之间没有明显的相关性。我们说CRUSH提供了一个去集群化的副本分布方案，包含某对象的共享副本的这些设备也是相对其他对象而独立的。
3.1 层次化Cluster Map
Cluster Map由设备和桶组成，它们都有数值型的标识符和权值。桶可以包含任意数量的设备或是其他桶，使它们形成存储的树状结构中的内部节点，设备总是这个树结构的叶子节点。每个存储设备都由管理员赋予权值，控制该设备的相对数据存储能力。尽管一个大型系统往往包含了存储能力和性能特点都不相同的设备，但是随机的数据分布，在统计意义上将设备的使用情况与负载关联起来，可以将设备的负载占总体的比例保持在平均的水平上。这就使得这个描述数据放置规则的一位标量（权重）是取决于设备的容量的。而桶的权重则由其包含的所有项的权重总和。
桶可以以任意形式组织成树状结构来描述可用的存储结构。例如某人可以创建名叫“shelf”的桶，以包含一组相同的存储设备，然后将“shelf”组装成“cabinet”，以此将同一个机架上的存储设备组织到一起，“cabinet”也可以被组装成名叫“row”或“room”的桶来适应一个更大的系统。数据通过类似伪随机的散列函数递归选择嵌套项目，将数据存放到层次结构中。在传统的散列技术下，任何目标设备数量的改变，都会导致一次很大规模的数据迁移，相比之下，CRUSH基于四种不同类型的桶，每种对应一种不同的选择算法，来解决增删设备时导致的数据移动和总体计算复杂度。
CRUSH：受控的、可扩展的数据副本分散存储方案(Part 1)
** 以下内容为翻译
** 原文及版权声明：http://ssrc.ucsc.edu/Papers/weil-sc06.pdf
** 翻译：softrank.net@gmail.com
** 转载请保留以上信息
** 欢迎各位游客指正翻译中的错误，或提出建议
CRUSH：受控的、可扩展的数据副本分散存储方案
作者：Sage A. Weil Scott A. Brandt Ethan L. Miller Carlos Maltzahn
美国加州大学圣克鲁兹分校存储系统研究中心
{sage, scott, elm, carlosm}@cs.ucsc.edu
摘要
新兴的大规模分布式存储系统正面临着将PB级的数据分散到成千上万个存储设备上的挑战，这样的系统必须要均匀分布数据与负载，是的系统资源及性能能够得到最大程度的利用，同时应对系统的增长和硬件故障。我们开发了CRUSH算法，它是一个可扩展的伪随机数据分布函数，用于在基于对象的存储系统中，将数据对象高效地与存储设备建立映射，而无需通过查找中心目录的机制。由于大规模的系统向来都是动态化的，因此CRUSH的设计有利于存储设备的增加和移除，并尽可能减少不必要的数据移动。算法能够适应各种数据冗余和可靠性机制的要求，按照用户定义的方式管理数据的分布，增强了跨故障域数据副本的隔离性。
1 简介
基于对象的存储是一种新兴的存储架构，增强了可维护性、可扩展性和性能[Azagury et al. 2003]。与基于块存储的传统硬盘驱动器不同，基于对象的存储设备在内部管理物理块的分配，仅对外提供读写不同大小的命名对象。在这种系统中，每个文件的数据通常都被条带化地分散于相对较少数的命名对象中，分散地存储于存储集群中。对象在多个设备间保留副本（或者使用其他某种数据冗余模式），以防止发生故障时可能导致的数据丢失。基于对象的存储系统用较小的对象列表代替庞大的块映射表，分散了底层块分配问题的处理压力，使得数据的布局更加简化。尽管通过减少文件分配元信息的复杂性，已经极大提高了可扩展性，然而如何在成千上万的设备上（尤其是容量、性能迥异的设备）分发数据的基本问题仍然存在。
大多数系统只是简单地将新数据写入到尚有空余的设备上，这种方法的基本问题是，数据只有在被写入时可能会移动，其他情况几乎不会移动。即便是一种完美的分布，随着系统规模的增长也会变得难以平衡，因为新磁盘要么是空的，要么包含了新数据，要么旧的磁盘忙，要么新的磁盘忙，这取决于系统的负载，而只有在某种极为罕见的特定情况下，才能使得可用资源平衡地得到最大限度的充分利用。
一种健壮的解决方案是将所有数据随机分布在可用的存储设备中。这实现了依概率的均衡数据分布，以及新老数据以类似的方式的混合存放在一起。当新设备添加到系统中时，一些随机的数据样本会被迁移到新的设备上以维持其负载的平衡。这种做法的好处是，平均来讲，所有设备的负载情况都差不多，使得系统在各种可能的负载情况下都能够高效运作[Santos et al. 2000]。此外，在一个大的存储系统中，单个大文件会被随机分布到许多可用的存储设备中，提供了高度的并行性和聚合带宽。然而简单的基于散列函数的分布无法应对设备数量的变化，将造成了大规模的数据迁移。而现有的随机分布模式将磁盘副本随机分配到其他设备上，增加了由于意外的设备故障导致数据丢失的可能性。
我们开发了CRUSH（可扩展散列下的受控复制算法）是一个伪随机数据分布算法，高效且可靠地将数据分发到异构的、结构化的存储集群中。CRUSH是伪随机的、确定性的算法，将一个输入值（往往是对象或对象组标识符）映射到一组存有相应对象副本的设备上。与其他传统方法明显不同的一点是，我们不需要任何形式的文件或对象目录，CRUSH只需要一个包含存储集群及其数据存放策略的紧凑的而层次化的设备描述。这种方式有两个关键的优越性：首先，它是完全分布式的，这意味着一个大型系统的任何参与者都可以独立计算出对象所在的位置；第二，仅需要的少量元数据是静态的，这些元数据仅当增加或移除设备时才发生变化。
CRUSH的设计使得它能够以最佳的方式分发数据，充分地利用资源，在设备增加或移除时高效地组织数据，灵活地限定数据对象副本的存放策略，最大程度地保障设备的意外或相关故障下的数据安全。各种数据安全策略都有广泛的支持，包括n-way复制（镜像）、RAID奇偶校验策略或者其他的校验策略，或者是其他某种混合的方式（例如RAID-10）。这些特性使得CRUSH非常适合在扩展能力、性能和可靠性都非常关键的存储系统中，管理超大规模的数据（PB级数据量）。
