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

deltamaster posted @ Jan 31, 2012 03:44:30 PM in 未分类 with tags Ceph CRUSH 分布式 存储 decentralization , 3201 阅读

 

** 以下内容为翻译
** 原文及版权声明: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级数据量)。
* 本文在CC BY-SA(署名-相同方式共享)协议下发布。

登录 *


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