CRUSH

CRUSH:Controlled，Scalable，DecentralizedPlacementofReplicatedDataCRUSH：可控、可扩展的复本数据非中心化的定位算法SageA.WeilScottA.BrandtEthanL.MillerCarlosMaltzahnStorageSystemsResearchCenterUniversityofCalifornia，SantaCruz{sage，scott，elm，carlosm}@cs.ucsc.edu摘要快速兴起的分布式存储系统正面临着在数以千计的存储设备之间分配PB级的数据问题。在这样的系统中，需要将数据与负载分布，以充分利用可用的资源，并最大化系统的性能，同时能够适应系统的增长，管理硬件设备的失效。我们开发了CRUSH算法，一种可扩展的，准随机的数据分布函数，专门在对象文件系统中用来做数据与设备之间的影射，这样的影射不依赖于集中的目录。因为大系统天生就是动态的，CRUSH设备用来适应存储设备的增加与删除，并最小化数据的移动。本算法可广泛用于各种数据复制与可靠性机制中，并根据用户定义的策略对数据进行分布，使得数据复本在不同的失效域中分离。1简介基于对象的存储系统是最近兴起的架构，这种构架即要保证很强的可管理性，又要有可扩展性以及性能[Azaguryetal.2003]。与传统的基于块的磁盘设备不同，基于对象的存储设备（OSDs）在内部进行磁盘分配的管理，暴露的接口使得其他部分可以读写不同大小的，有名的对象。在这样的系统中，每个文件的数据被分成了小块的有名的对象，并在整个集群中分布。对象在多个设备之间复制（或者部署了其他的冗余策略）用来防止在设备失效出现时导致数据丢失。基于对象的存储系统通过将大的数据列表替换为对象列表，并分布到底层的块设备，简化了数据的布局问题。尽管通过压缩文件分配元数据及其复杂性从而提升了系统的可扩展性，但是在数以千计的设备之间进行数据分布这样的问题依然存在，并且这些设备之间还有容量与性能特性上的差异。大多系统都是简单地将新数据写到一个未使用太多的设备中。这样的方案的主要问题就是数据写入后就很少移动。就算数据完美分布，但当存储系统扩展时，都会变得不平衡。因为新的磁盘要么是空的，要么只包括新数据。这样，根据负载情况，要么是旧磁盘或者是新磁盘一直处于忙状态。极少数的情况下才会充分使用新旧磁盘，并因此能够充分使用可用的资源。一种可靠的解决方案，就是将所有的数据随机地在系统中可用的存储设备之间进行分配。这导致概率性地数据平衡分布，并混合使用新旧设备。当新的设备加入时，已经存在的数据的部分会被迁移到新的设备上以恢复平衡。这种方式有一个关键的好处就是，平均上，所有的设备都有相似的负载，因此系统在任何可能的负载下都能够表现良好[Santosetal.2000]。另外，在一个大的存储系统中，单个的大文件会被随机分布到一个大的设备集合中，因此可以提供高层次的并行化以及集合带宽。然而，简单的基于哈希的分布，无法处理设备数量变化的情况，这样会导致数据大量重整。另外，现有的随机分配方案将磁盘数据在不同的设备之间进行复本化，极容易招致因偶然的设备失效导致数据丢失的问题。我们因此开发了CRUSH（ControlledReplicationUnderScalableHashing，基于可扩展的哈希下的受控复本算法）。这是一个准随机的数据分布算法，可以可靠高效地将对象复本在异构的，结构化的存储集群中进行分布。CRUSH实现为一种准随机，确定性的函数，其将输入值（一般为对象或者对象组ID）影射为设备列表，并用这些设备列表存储对象。CRUSH仅需要很少的，即集群设备组成的层级描述以及复本定位策略的相关知识。这不同于传统的方式，因为它不依赖于任何的单文件或者单对象目录。这种方式有两个关键的好处：一个是，它是完全分布的，大系统中的任何部分都可以独立计算对象的位置；其二是，所需要有元数据大多都是静态的，只有当设备添加与删除时才会有变化。CRUSH设计的目标就是用来优化数据分布，并充分利用系统资源，在设备添加或者删除时，有效地组织数据，并对数据复本定位施加灵活的限制，使得数据安全性在意外的或者相关的硬件失效情况下能得到保证。CRUSH支持很多的数据安全机制，包括n路复本（镜像），RAID校验方案或者其他形式的代码擦除，以及混合方式（如RAID-10）。这些特性使得CRUSH成为管理超大规模（几个PB）存储系统中的对象分布的理想方案。在这样的存储系统中，可扩展性，性能，可靠性是极为重要的。2相关工作其于对象的存储对于提升系统的可扩展性最近受到了广泛的关注。很多的研究以及生产系统已经接纳了基于对象的方式，包括像SeminalNASD文件系统[Gobioffetal.1997]，Panasas文件系统[Nagleetal.2004]，Lustre[Braam2004]，及其他的如[RodehandTeperman2003；Ghemawatetal.2003]之类的文件系统。其他的基于块的分布式文件系统，像GPFS[SchmuckandHaskin2002]，以及FederatedArrayofBricks（FAB）[Saitoetal.2004]都面临着相同的数据分布挑战。在这些文件系统，利用半随机或者启发式的方法来进行新数据的分布，并存储在可用的存储空间中，但是数据很少进行重新定位以保证随时的数据平衡。更重要的是，所有这些系统都是通过某种元数据目录来定位数据，而CRUSH只依赖于很少的集群描述以及确定性的影射函数来进行数据定位。这种差异在写数据时尤其明显。因为系统利用CRUSH就能够计算任何新数据的存储目标，而不需要通过中心控制分配器来执行。Sorrento[Tangetal.2004]存储系统使用一致性哈希[Kargeretal.1997]与CRUSH相近，但是缺少对于设备权重的控制，以及数据良好的平衡，也没有失效域的概念来保证数据安全。尽管在系统层面，利用显式的分配影射[Andersonetal.2001；Andersonetal.2002]中的数据迁移问题已经被研究得非常多了，但是在这样的方案中，需要非常多的元数据，但是CRUSH这样的函数式方法却不需要。Choy，etal.[1996]描述了用于在磁盘上进行数据分布的算法，该算法在磁盘添加时有一个最优化的数值，但是却不支持权重，复本以及磁盘移除。Brinkmann，etal.[2000]利用哈希在异构集群中来分布数据，但是其中的集群是静态的。SCADDAR[Goeletal.2002]解决了磁盘添加与删除问题，但是只支持有限的复本策略集。以上没有一个方式包含像CRUSH这样的灵活性，以及通过失效域来保护数据的可靠性。CRUSH与RUSH[HonickyandMiller2004]算法族最相似，并基于这些算法开发的。RUSH有一系列的算法通过影射函数而不是显式的元数据来有效地进行数据分布，并支持有权重的设备的加入与删除。尽管有这些基本的特点，但是还有一系统的问题使得RUSH在实践中不够有效。CRUSH完全实现了RUSHP和RUSHT中有用的元素而解决了之前未提到的可靠性与复本问题，同时又提供了更好的性能与灵活性。3CRUSH算法CRUSH算法根据设备的权重来在多个存储设备之间进行数据对称分配，近似于一个概率性分布。分布是受到一个有层级的clustermap的控制的，clustermap代表了存储集群中可用的资源以及组成这个集群的组件逻辑构成。例如，根据服务器机柜来描述一个大的集群，而机柜中又部署了大量的磁盘架，磁盘架中都是存储设备。数据分布策略根据定位规则来定义，这些规则定义包括从集群中挑选几个复本目标，以及对复本定位上的一些限制。如可能指定三个镜像的复本存储在不同的物理机柜里，因为它们不会使用同一个电力线路。（译注：这样数据就存储在不同的失效域中，某个设备的电力失效，不会导致数据不可用。）假设输入一个单独的整数值x，CRUSH则输出一个在n个不同的存储设备中的有序的列表~R。CRUSH利用一个强的多端输入（包括x）整型哈希函数，生成一个完全确定的，并且是独立的使用clustermap，定位规则，x等进行计算而得的影射。这种分布是一种准随机的，即使输入相似，输出之间是没有明显在关联关系的，也跟存储设备上存储的数据无关。我们说CRUSH产生了“逆集群”（declustered)的复本分布，存储设备集之间共享某个存储项，是与所有其他的存储项是无关的。3.1层级式的集群影射集群影射由设备与桶（devicesandbuckets）构成，两者都有权重以及整数标识符。桶可以包括任意数量的设备以及其他的桶，使得它们也可以在存储层级中成为内部结点，并且设备总是叶子结点。存储设备被管理员赋予了权重，以对应设备可用于存储数据的相对数量。尽量大的系统包括大量的不同容量与性能的设备，但是随机数据的分布静态地将设备的使用情况与负载相关联。这样的设备负载将其计算成为其存储数据的一部份。这导致了一个一维的定位方式，权重主要是由磁盘的容量组成，桶权重则是其所有元素权重的总合。桶也可能任意地在层级中进行组合，以表示所有的可用设备。如，可以创建一个最低层的架子桶，表示所有已经安装的相同的设备，然后将架子桶组合成“机柜桶”，将所有安装在同一个背板中的架子桶组合起来。在大的系统中，机柜桶又可以组成“行桶”或者“房间桶”。通过这样的递归方式，用准随机的的哈希方式，将数据存放在这些设备中。与传统的方式比较起来，目标组合中的数量的变化，会导致数据会产生大量的重整操作，而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操作移入结果向量。作为例子，在表