CRUSH:受控的、可扩展的数据副本分散存储方案(Part 2)

deltamaster posted @ Feb 01, 2012 04:06:15 PM in 未分类 with tags CRUSH Ceph decentralization 分布式 , 2115 阅读

 

** 以下内容为翻译
** 原文及版权声明: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基于四种不同类型的桶,每种对应一种不同的选择算法,来解决增删设备时导致的数据移动和总体计算复杂度。

 

* 本文在CC BY-SA(署名-相同方式共享)协议下发布。
  • 无匹配

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter