CEPH分布式存储中CRUSH算法来源及优点

      CEPH是近几年软件定义存储的新贵，以其面向海量存储、提供高可靠、易扩展、高性能的设计理念，在Openstack开源生态中逐渐绽放光彩。CEPH的原型设计及开发者Sage.A.Weil是一个充满传奇经历的电脑极客，CEPH首次出现在其博士论文中。与Linux一样，CEPH的开源给它点燃了强大的生命力，其开放、共享的自由精神，让它如熄火燎原，迅速发展状态。

       任何事物的发展与其时代背景息息相关，没有时代大环境的支持，大多的事物及思想也如昙花一现，瞬间淹没在时代发展的浪潮中。在地球文明的这次迭代中，人类不断探索和演进，通过文字、图表和代码固化传递知识，一次又一次突破自然和自我的限制，创造了一个美好的时代。

       如何让社会更加美好是当前人类发展的动力和进步的原因，发展中不断积累的信息及生产的数据在由量变得到质变的转换后，成为了新的苦恼。任何一个事物的出现，大部分的是为了解决遇到的问题，并且在解决问题过程当中不断的迭代。Crush就是Ceph为解决海量数据存储分布而优化适配的一种Hash算法。

       Crush不是一种全新的算法而是基于存储及使用环境的一种设备方法。在正式分析crush前，介绍一下Ceph的架构。ceph的架构如图：

其底层是对象存储Rados，对外提供RADOSGW(对象网关）,RBD（块存储）,CEPH-FS(文件系统）及LIBRADOS(rados调用库）。RADOS是一个对象存储，其需要解决海量数据的分布和维护数据的增、删、改、查。CRUSH就是控制RADOS中数据分布的核心。

      HASH是一种将数据管理的思想，主旨是将广域的信息通过一定方法映射到小的数据集中。对于简单的使用，需要解决HASH冲突，解决HASH冲突的方法不在此学习和介绍。CRUSH是将海量的数据通过特定化的控制分布到不同的服务器上。在Sage A weil的论文中对于Crush的描述如下。

     CRUSH(controlled Replication Under Scalable Hashing), a pseudo-random data distribution algorithm that efficiently and robustly distributes object replicas across a heterogeneous, structured storage cluster. CRUSH is implemented as a pseudo-random, deterministic fucntion that maps an input value, typically an object or object group dentifier, to a list of devices on which to store object replicas.This differ form conventional approaches int that data placement does not rely on any sort of pre-file or pre-object directory-CRUSH needs only a compact, hierarchical description of the devices comprising the storage cluster and knowledge of the replica placement policy. This approach has two key advantages: first, it is completely distributed such that any party in a large system can independdenty ccalculate the location of any object; and second, what little metadat is required is mostly static., changing only when devices are added or removed.

      表述的意思主要是：CRUSH是一种伪随机算法，根据输入值及已定义的对象或对象组，得到要存储到的存储设备集合，当它的依赖的对象或对象集合发生变化时，这个描述集合的元数据才发生变化。极其轻量的元数据和根据描述集合获得存储集合是CRUSH算法的关键优点。

      因此与CRUSH算法相关的两个主题是：CRUSH算法和依赖的cluster Map。在论文中对于CRUSH算法及cluster Map的描述主要如下。

    Cluster Map: The cluster map is composed of devices and buckets, both of which has numerical identifiers and weight  values associated with them.Buckets can contain any number of devices or other buckets, allowing them to form interior nodes in a storage herarchy in which devices are always are the leaves. 

    CRUSH algorithm: Given a single integer input value x, CRUSH will output an orderd list R of n distinct storage targets. CRUSH utillizes a strong multi-input integer hash function whose inputs include x, making the mapping completly deterministic and independently calculable using only the cluster map, palcement rules, and x.

      集群的Map表由设备和桶构成。设备和桶都根据他们关联的设备进行数字的量化，桶可以包括桶和设备，在他们构成的层次结构中，设备始终位于叶子节点。

      CRUSH算法对于输入的一个整数x，会输出n个不同存储设备的排序的集合列表集R。CRUSH使用x，集群map和放置规则进行独立计算。

       架构是解决问题的核心，在具体实现过程中，更需要解决诸多细节问题，比如怎么减少crush算法在集群变化后数据迁移，如何设计集群内核集群间的数据同步。通过十多年的迭代，CEPH的快速迭代和日渐广泛使用将这些问题一一解决，Ceph已经逐渐成为企业级存储的主流解决方案，深入的对ceph中的原理及代码进行学习对存储架构及实现学习具有重要的参考意义。