[ceph学习-7]crush算法(2)

层次化的Cluster Map:

Cluster Map由设备(device)和桶(bucket)组成,他们都有数值型的标识符(id)和权重(weight value)。bucket可以包含任意数量的devices或者其他buckets,使他们形成存储的树状结构中的内部节点,device总是这个树结构的叶子节点。管理员对存储设备赋予权重,控制该device的相对数据的存储能力。尽管一个大型系统往往包含了存储能力和性能特点不尽相同的设备,但是随机的数据分布,在统计意义上将device的使用情况与负载(load)关联起来,可以将设备的负载占总体的比例保持在平均的水平上。这就使得这个描述数据放置规则的权重是取决于设备容量的。而bucket的权重则是其包含的所有项(item)的权重之和。

bucket 可以以任意形式组织成树型结构来描述可用的存储结构。数据通过类似伪随机的散列函数递归选择嵌套项目,将数据放到层次结构中。在传统的散列技术下,任何目标设备数量的改变,都会导致一次很大规模的数据迁移,相比,CRUSH以及四种不同的bucket type。每种有不同的选择算法,来解决增删device时导致数据移动和总体计算的复杂度。

副本分布策略
CRUSH的设计使得数据均匀的分布在带有权重的device上,在统计意义上保持了device和bandwidth(带宽)的均衡,副本在树形结构的存储device的分布影响着数据的安全。通过对于系统本质的物理结构的映射,CRUSH能够建模,从而定位潜在的相关设备的故障源。典型的故障源包括物理位置上接近、共享电源、共享网络。通着将这些信息反映给Cluster Map中,CRUSH placement policies (位置策略)能够将对象副本发布在不同的区域(故障域)中,同时维持预期的数据分布形式。例如,为了应对出现并发故障的可能性,也许会需要确保数据副本在不同的机架、机柜、电源、CPU、位置的device上。
CRUSH可以被用于不同的数据副本策略和不同的硬件配置下,为了适应这样的场景需求,CRUSH为其适应的每个副本策略或placement policies 定义placement Rule.以保证系统或管理员可以确切的指定副本如何定位。
每条规则包含用户简单执行环境的用户树形结构的指令序列,这些操作包括:
tack(a).选择一个item(a),一般是bucket,并返回bucket所包含的所有item。这些item是后续操作的参数,这些item组成向量i;
select(n,t);迭代操作每个item(向量i中的item),对于每个item(向量i中的item)向下遍历(遍历这个item所包含的item),都返回n个不同的item(type为t的item),并把这些item都放到向量i中。
select函数会调用c(r,x)函数,这个函数会在每个bucket中伪随机选择一个item.
emit:把向量i放到result中。

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

[ceph学习-6]crush算法(1)

crush算法类似一致性算法,一致性算法使用了一个散列到服务器平台的散列表,crush可以存在层级结构的服务器上(shelves,racks,rows),并允许用户制定。例如将复制到不同的货架上而不是仅在primary上。

crush(Controoled Replication Under Scalable Hashing)是一种伪随机数据分布算法,它能够在层级结构的存储集群中有效的分布对象的副本。它的参数为object id或object group。id,并返回一组存储设备(用于保存object副本)。Crush需要cluster map(描述存储集群的层级结构)、和副本分布策略(rule).
CRUSH的优点:任何组件都可以独立计算出每个object所在的位置(去中心化).只需要少量的元数据(cluster map),只要当删除添加设备时,这些元数据才需要改变

crush算法是通过对每个设备的权重在存储设备间分发数据,大致是均匀分布的。数据分发是有一个层次化的cluster map 控制的,Cluster Map描述了可用的存储资源,由建立集群映射的一些逻辑元素组成。例如,某个Cluster Map可能描述了一个大型的装置,包含了一排机柜,每个机柜有许多磁盘架,每个磁盘架上有许多存储设备。数据分配策略是有placement Rules定义的。 Placement Rules 指定了从及群众中选中的副本目标的数量,以及放置这些副本的限制条件。例如,某个Placement Rule也许会指定三个镜像副本要被放置在不同的物理机柜上,以免这些副本共享同一条供电线路。

CRUSH算出x到一组OSD集合:
给出一个整型输入x,CRUSH会输出一个有序的、包含n个不相同的存储目标的R向量。

CRUSH使用一个多参数的整形hash函数,参数列表包含x,使得从x到osd集合是完全独立且确定性的,仅仅依赖Cluster Map、Placement RUles和输入参数x。数据分发是伪随机的,输出结果与输入结果或者设备中现象有的对象之间没有明显的相关性。
CRUSH提供了一个去集中化(集群化)的副本发布方案,包含某对象的共享副本的这些设备也是相对其他对象也是独立的。

[ceph学习-5]一致性hash算法

一致性hash算法,1997年麻省理工学院提出的一种分布式hash(DHT)实现算法,设计目标是为了解决因特网中热点(Hot spot)问题。hash算法的判断从四个方面来判断:平衡性、单调性、分散性、负载。

普通的hash(硬hash)采用简单的取模方式,进行散列。一致性hash算法实现的基本原理是将节点和key值都按照一样hash算法映射到0-2^32的环上。到有一个缓存的请求到来时,计算key值k对应的hash(K),如果该值正好对应之前某个机器节点的hash值,则直接写入该机器节点,如果没有对应的节点,顺时针查到到下一个节点,进行写入。如果超过2^32还没有对应节点,则从0开始查找。
一致性算法Consistent-hashing:URL:

Consistent-hashing 一致性hash算法
libconshash 源码使用了红黑树来存放虚拟节点信息。
1 首先对node的标志(“%s-%03d”, node->iden, 节点名 replica_idx,节点索引number)进行md5计算,然后对整数进行4字节的整数hash算法( MurmurHash, 一种非加密型哈希函数, 由Austin Appleby在2008年发明,并且有多个变种 特点:对于规律性较强的key,MurmurHash的随机分布特性表现更良好),得到了一个长整数

for(i = 0 ;i<4;i++){Md5是一个16字节长度的数组,将16字节的数组每四个字节一组,分别对应一个虚拟结点.

。 2 然后根据__conhash_add_replicas 生成n->replicas数量的虚节点插入红黑树 。__conhash_get_rbnode(node, hash); 分配一个虚拟节点,然后插入红黑树中。util_rbtree_insert
3 __conhash_del_replicas 将虚节点从红黑树中删除
每次操作都是对每个虚拟节点vnode单独调用malloc和free。利用红黑树添加删除的时间负载度为O(logW).数组的实现因为每次都要重新初始化HASH环,因此时间复杂度为O(WNlog(WN))(N为节点数)。缺点为相对于数组实现来说,每个虚拟节点要浪费至少两个指针(红黑树节点的左右字数指针,以及一个颜色标记)的空间。

HAproxy的一致性hash算法
以cache为例,实现思想:
1. 根据server(cache)某个参数计算出的key,将server映射到2^31-1的环形空间中;object对象根据自身的key存储到相近的cache server中;当cache A server down之后,只会影响环中其key附近的object;

2. 由于cache server无法均匀的映射到环形空间中(不均衡问题),所以引入虚拟节点的概念,每台cache server分配X个虚拟节点映射到环中。

HAProxy 利用EBtree来管理node,而不是rbtree。优点是:是删除操作的复杂度是O(1)

chash_init_server_tree 虚拟节点的分配函数。
虚拟节点的个数为

即1台server会有512个虚拟节点;

hash key的计算
每个虚拟节点的hash key按如下公式计算:

其中,puid为server配置的id号,SRV_EWGHT_RANGE=4K;

chash_hash()是一个32位的Thomas Wang的HASH算法(homas Wang在Jenkins的基础上,针对固定整数输入做了相应的Hash算法)

添加/删除节点。
采用EBtree管理节点,添加删除节点在chash_queue_dequeue_srv()中实现;
chash_queue_dequeue_srv()相应操作函数为:

对应的文件为Eb32tree.c文件的函数

旧版本HAProxy曾经使用过红黑树,用于任务调度、负载均衡等方面。但是Willy Tarreau认为,在事件响应非常频繁的情况下,任务插入、删除的频率非常高,这时候使用红黑树存在性能瓶颈,尤其不能接受红黑树删除节点的时间复杂度为O(log n)。因此,他发明了一种新的数据结构,叫做弹性二叉树(elastic binary tree),简称ebtree。

ebtree是不平衡的二叉搜索树(BST),而红黑树、AVL树等都是平衡的BST。传统的BST最怕的就是退化成线性搜索,因此,红黑树等BST插入、删除时都需要对树进行平衡化,而平衡化是一个从叶子节点开始,向根节点方向递归向上的过程,时间复杂度是O(log n)。

有鉴于此,ebtree为了实现删除节点时O(1)的时间复杂度,必然放弃保持树的平衡,为了拒绝由此而来的副作用——退化成线性搜索(或者更准确地说,退化成不受限制的线性搜索),不可避免地引入了一些新的成员和新的思路。

[ceph学习-4]数据的可靠性,一致性

数据保存在一块盘中是无法保障数据可靠性,通常采用多副本的方法,副本越多,越可靠。在确定副本数下,副本丢失后的恢复速度,是可靠性的关键因素。如果数据修复的速度够快,可以抢在另一块盘损坏之前,修复丢失后数据。
一致性hash方案中,如果将一块磁盘同一个hash区间一一绑定,因此数据恢复时,只能先更坏坏盘,然后从其他副本处读数据,写入新磁盘,时间尺度交大。

如果方案中,让节点同hash区间一一对应,在节点内部,在将数据分散存储到一块磁盘中,那么当需要恢复副本时,节点将损坏的磁盘的数据对象分散存放到其他磁盘上。这样可以先发起修复,从其他副本那里获得数据,并发的向多个磁盘恢复数据,磁盘的吞吐会得到缓解,但网络将会成为瓶颈。千兆网络最大支持120MBps,比磁盘快一倍。另一个问题是,数据在节点内部任意分散到各磁盘上,那么节点就需要维护一个key->磁盘的映射。也就是节点内的局部元数据。这个元数据需要服务器自己维护,由于单台服务器资源有限,元数据的可靠性、可用性和一致性的维持非常麻烦。一旦这个元数据丢失了,这个节点上的所有数据都找不到,需要从其他副本那里恢复丢失的数据,但恢复起来更困难。更现实的做法是直接扫描各磁盘,逆向的重建元数据。

副本恢复最快,影响最小的方法,不让数据对象绑死在一台节点上,只要数据对象可以存放到任意一台节点,那么便可以在节点之间多对多的数据副本恢复。集群规模越大,速度越快。基于元数据的方案,每个对象同节点,乃至硬盘的映射是任意的。

有一些基于混合方案的衍生方案可以解决hash在副本修复速度问题:将hash环划分成若干slot(bucket),数量远远大于将来集群可能拥有的节点数、或磁盘数。如2^32。slot到节点或磁盘的映射通过一个映射表维护,各副本集群中的slot分布互不相同,当一个磁盘损坏时,找出所包含的slot,将这些slot分散到其他节点和磁盘上。这样便可以并发的从其他节点上以slot为单位进行副本恢复,在磁盘更换后,再将一些slot,可以是原来的,也可以是随机的迁移到磁盘,以达到数据平衡。

确保数据对象一致性最实用的方法是W+R>N。即N个副本中,一个版本写入确保W个成功,而读取时确保R个成功,只要满足W+R>N的情况,便可以保证始终可以读到最后写入成功的版本。元数据在节点下线时可以采用另外挑选一台合适的节点,写入副本,更新相应元数据操作。一致性hash方案,无法随意的将副本写入到其他节点上,有2中方法,1是将副本或者key写入一个队列,等节点恢复后,发起修复操作,从其他副本获取数据,补上缺失副本。这个队列必须足够可靠,否则等到一致性检查时才能修复。2是按照一定规则写入其他节点,等回复后原样迁回,但调度会比较复杂。

[ceph学习-3]关于扩展

元数据:当节点增加是,系统可以更多的将新来的请求引导到新加入的节点。合适的调度平衡策略可以确保系统平衡的使用各节点的存储空间。

一致性hash模型:原始的hash表一点需要扩容,需要rehash。在基于hash的分布式存储系统中,意味着所有的数据必须重新迁移一遍。一致性hash算法中,当新节点加入后,会映射到hash换上。原来的区段会被新节点截断,新加入的节点会占据被切割出来的hash区间。为了完成这个转换,这部分数据需要迁移到新的服务器上。与原始的hash相比,一致性hash只需要被传输被新服务器抢走的那部分数据。

一致性hash模型在平衡性上,如果不是成倍的增加节点,会存在数据不平衡的问题,为了平衡数据,需要迁移更多的数据,每台节点都需要迁出一些数据,以确保每个节点的数据量都差不多。虚拟节点的引入便是起到这个作用。于是实际的数据迁移量同时增加的容量数成正比,系数是当前存储系统的空间使用率。

一个1p的系统,3个副本,70%的容量,扩容200T,那么需要迁移大约(200*70%)*3 = 420T的数据,才能使数据保持平衡。如果常见的存储服务器(2T*10),则需要21台存储。如果都参与迁移,将是一个很耗时的工作,更复杂的是迁移中出错。
元数据方案一般情况下不需要数据迁移,迁移只有存储服务器更替时。用户数据对象可以存储在任何一个节点上,因而可以把一台节点需要迁移的数据分散到其他节点上。并且可以从其他副本那里多对多的并发传输数据