ceph-crush algorithm(一)

2017-06-02 18:28:17
CRUSH简介

CRUSH是ceph的一个模块，主要解决可控、可扩展、去中心化的数据副本分布问题.
CRUSH全称Controlled Replication Under Scalable Hashing，是一种数据分发算法，类似于哈希和一致性哈希。
哈希的问题在于数据增长时不能动态加Bucket，一致性哈希的问题在于加Bucket时数据迁移量比较大，
其他数据分发算法依赖中心的Metadata服务器来存储元数据效率较低，CRUSH则是通过计算、接受多维参数的来解决动态数据分发的场景

CRUSH实现了一种伪随机数据分布算法，它能够在层级结构的存储集群中有效的分布对象的副本,它的参数是object id或object group id，并返回一组存储设备(用于保存object副本)
CRUSH需要cluster map(描述存储集群的层级结构)、和副本分布策略(rule)

算法基础

在学习CRUSH之前，需要了解以下的内容。
CRUSH算法通过每个设备的权重来计算数据对象的分布。对象分布是由cluster map和data distribution policy决定的。
cluster map描述了可用存储资源和层级结构(比如有多少个机架，每个机架上有多少个服务器，每个服务器上有多少个磁盘)。
data distribution policy由placement rules组成。rule决定了每个数据对象有多少个副本，这些副本存储的限制条件(比如3个副本放在不同的机架中)。
每个rule就是一系列操作，take操作就是就是选一个bucket，select操作就是选择n个类型是t的项，emit操作就是提交最后的返回结果。
select要考虑的东西主要包括是否冲突、是否有失败和负载问题.

CRUSH算法还通过输入一个整数x，输出则是一个包含n个目标的列表R，例如三备份的话输出可能是[1, 3, 5]。
(osd0, osd1, osd2 … osdn) = CRUSH(x)
CRUSH利用多参数HASH函数，HASH函数中的参数包括x，使得从x到OSD集合是确定性的和独立的。
CRUSH只使用了cluster map、placement rules、x。CRUSH是伪随机算法，相似输入的结果之间没有相关性。

  • Cluster map
    Cluster map由device和bucket组成，它们都有id和权重值。Bucket可以包含任意数量item。item可以都是的devices或者都是buckets。
    管理员控制存储设备的权重。权重和存储设备的容量有关。Bucket的权重被定义为它所包含所有item的权重之和。
    CRUSH基于4种不同的bucket type，每种有不同的选择算法。

  • 副本分布
    副本在存储设备上的分布影响数据的安全。cluster map反应了存储系统的物理结构。CRUSH placement policies决定把对象副本分布在不同的区域(某个区域发生故障时并不会影响其他区域)。每个rule包含一系列操作(用在层级结构上)
    这些操作包括：
    1.take(a) ：选择一个item，一般是bucket，并返回bucket所包含的所有item。这些item是后续操作的参数，这些item组成向量i。
    2.select(n, t)：迭代操作每个item(向量i中的item)，对于每个item(向量i中的item)向下遍历(遍历这个item所包含的item)，都返回n个不同的item(type为t的item)，并把这些item都放到向量i中。select函数会调用c(r, x)函数，这个函数会在每个bucket中伪随机选择一个item。
    3.emit：把向量i放到result中。

    存储设备有一个确定的类型。每个bucket都有type属性值，用于区分不同的bucket类型(比如”row”、”rack”、”host”等，type可以自定义)。rules可以包含多个take和emit语句块，这样就允许从不同的存储池中选择副本的storage target

  • 冲突、故障、超载
    select(n, t)操作会循环选择第 r=1,…,n 个副本，r作为选择参数。在这个过程中，假如选择到的item遇到三种情况(冲突，故障，超载)时，CRUSH会拒绝选择这个item，并使用r’(r’和r、出错次数、firstn参数有关)作为选择参数重新选择item。
    1.冲突：这个item已经在向量i中，已被选择。
    2.故障：设备发生故障，不能被选择。
    3.超载：设备使用容量超过警戒线，没有剩余空间保存数据对象。
    故障设备和超载设备会在cluster map上标记(还留在系统中)，这样避免了不必要的数据迁移。

  • MAP改变和数据迁移
    当添加移除存储设备，或有存储设备发生故障时(cluster map发生改变时)，存储系统中的数据会发生迁移。好的数据分布算法可以最小化数据迁移大小。

CRUSH总结

  • 算法总结
    CRUSH与一致性哈希最大的区别在于接受的参数多了cluster map和placement rules，这样就可以根据目前cluster的状态动态调整数据位置，同时通过算法得到一致的结果

  • 算法补充
    前面介绍了bucket根据不同场景有四种类型，分别是Uniform、List、Tree和Straw，他们对应运行数据和数据迁移量有不同的tradeoff，目前大家都在用Straw因此不太需要关注其他。
    目前erasing code可以大大减小三备份的数据量，但除了会导致数据恢复慢，部分ceph支持的功能也是不能直接用的，而且功能仍在开发中不建议使用。

    有兴趣的读者可以拜读下Sega本人的博士论文作品:
    长论文包含了RADOS、CRUSH等所有内容的介绍，但篇幅相当长，如果感兴趣可以阅读，标题为《CEPH: RELIABLE, SCALABLE, AND HIGH-PERFORMANCE DISTRIBUTED STORAGE》，地址 http://ceph.com/papers/weil-thesis.pdf

    CRUSH论文标题为《CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data》，地址 http://ceph.com/papers/weil-crush-sc06.pdf ，介绍了CRUSH的设计与实现细节

    RADOS沦为标题为《RADOS: A Scalable, Reliable Storage Service for Petabyte-scale Storage Clusters》，地址为 http://ceph.com/papers/weil-rados-pdsw07.pdf ，介绍了RADOS的设计与实现细节

    CephFS论文标题为《Ceph: A Scalable, High-Performance Distributed File System》，地址为 http://ceph.com/papers/weil-ceph-osdi06.pdf ，介绍了Ceph的基本架构和Ceph的设计与实现细节

ref
ceph的CRUSH数据分布算法介绍
CRUSH详解
大话Ceph–CRUSH那点事儿

您的鼓励是我写作最大的动力

俗话说，投资效率是最好的投资。 如果您感觉我的文章质量不错，读后收获很大，预计能为您提高 10% 的工作效率，不妨小额捐助我一下，让我有动力继续写出更多好文章。