CRUSH：受控的、可扩展的数据副本分散存储方案(Part 2)
deltamaster
posted @ Feb 01, 2012 04:06:15 PM
in 未分类
with tags
CRUSH Ceph decentralization 分布式
, 4392 阅读
** 以下内容为翻译
** 原文及版权声明：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基于四种不同类型的桶，每种对应一种不同的选择算法，来解决增删设备时导致的数据移动和总体计算复杂度。
Sep 14, 2021 10:07:26 PM
I really appreciate this wonderful post that you have provided for us. I assure this would be beneficial for most of the people. 123movie
Oct 01, 2021 12:36:34 AM
Great post, and great website. Thanks for the information! Complete Business Funding List
Oct 02, 2021 08:23:34 PM
Positive site, where did u come up with the information on this posting? I have read a few of the articles on your website now, and I really like your style. Thanks a million and please keep up the effective work. see more info
Oct 10, 2021 01:37:30 AM
This is such a great resource that you are providing and you give it away for free. I love seeing blog that understand the value of providing a quality resource for free. รับทำ seo สายเทา
Oct 18, 2021 03:25:48 AM
I definitely enjoying every little bit of it. It is a great website and nice share. I want to thank you. Good job! You guys do a great blog, and have some great contents. Keep up the good work. Top 10 umrah package uae
Nov 04, 2021 09:25:49 PM
Thank you very much for this great post. 오피톡
Nov 23, 2021 11:31:09 PM
KitaabNow is an <a href="https://kitaabnow.com/">online book store in pakistan</a> with a huge variety of Academic Books and Stationery items.
Oct 03, 2022 04:22:37 PM
ICICI Bank balance enquiry can also be made through a missed call. To use the missed call services, register for ICICI Bank missed call banking by send. ICICI Bank balance enquiry can also be made through a missed call. To use the missed call services, register for ICICI Bank missed call banking by send. <a href="https://manabook.in/icici-bank-account-balance-check/">icici bank balance check</a> CICI Bank Balance Enquiry Using Toll free number. Dial 9594612612 or 022-?30256767 from your mobile number. After 2-3 rings, the call will get disconnected.CICI Bank Balance Enquiry Using Toll free number. Dial 9594612612 or 022-?30256767 from your mobile number. After 2-3 rings, the call will get disconnected.ICICI Bank balance enquiry can also be made through a missed call. To use the missed call services, register for ICICI Bank missed call banking by send. CICI Bank Balance Enquiry Using Toll free number. Dial 9594612612 or 022-?30256767 from your mobile number. After 2-3 rings, the call will get disconnected.
Oct 27, 2022 03:52:13 PM
The Andhra Pradesh government (AP YSR government), through the CM Jagan Mohan Reddy, has offered a relief scheme to cater for the debts and financial needs. AP women for women in the SC/ST/OBC and women in BPL categories. YSR Asara Scheme Status 2023 They qualify for the YSR Aasara scheme benefits. The government plans to release more Rs. 6345.87 Crore to benefit 9 33,180 self-help groups in AP state. The groups have 90 lakh registered members.
Jan 16, 2024 09:56:53 PM
Thumbs up guys your doing a really good job