Ceph的crush算法与一致性hash对比介绍

天翼云开发者社区
• 阅读 202

本文分享自天翼云开发者社区《Ceph的crush算法与一致性hash对比介绍》,作者:l****n

首先,我们先回顾下一致性hash以及其在经典存储系统中的应用。

一致性hash的基本原理 一致性hash的基本思想是,有一个hash函数,这个hash函数的值域形成了一个环(收尾相接:the largest hash value wraps around to the smallest hash value),然后存储的节点也通过这个hash函数随机的分配到这个环上,然后某个key具体存储到哪个节点上,是由这个key取hash函数对应到环的一个位置,然后沿着这个位置顺时针找到的第一个节点负责这个key的存储。这样环上的每个节点负责和它前面节点之间的这个区间的数据的存储。

Ceph的crush算法与一致性hash对比介绍

如上图所示,hash函数的总区间是[A, Z],有3个存储节点分别对应到F、M和S的位置上,那么hash值为A或者Z的key将会顺时针查找它遇到的第一个节点,因此会存储到节点1上,同理hash值为K的key存储到第二个节点上。咱们再观察下一致性hash在增删节点的时候,数据迁移的情况,在上图的场景中,如果删除节点2的话,节点1上面的不会发生变化,原来存储在节点2上的(F,M]区间会迁移存储到节点3上;在上图的场景中,如果在U位置增加一个节点的话,原来存储到节点1上的(S, F]区间会分割成两个区间其中(S, U]会存储到新的节点上,而(U, F]不发生变化还是存储到节点1上。从上面的例子中可以看到,一致性hash在增删节点的时候,只影响与其相邻的节点,并且需要迁移的数据最少。

上面这种朴素的一致性hash有两个问题,第一个问题是如果节点较少,节点在环上的分布可能不均匀,导致每个节点的负载不均衡,比如上图中场景,如果节点3故障被剔除的话,节点1和节点2的负载会非常的不均衡;第二个问题是不支持异构的机型,比如如果有的存储节点是4TB的,有的存储节点是8TB的,每个节点对应环上的一个位置,无法感知到节点的权重。为了解决这两个问题,一般都是把每个节点对应到环上的多个位置,称为vnode,vnode足够多的话,可以认为是均衡打散的,如果有节点故障下线的话,这个节点在环上对应的vnode存储的数据就可以均匀分给其他的vnode,最终存储到对应的node上,因此在增删节点的时候,负载都是在所有的节点中均匀分摊。另外针对异构的机型,比如说4TB和8TB的节点,8TB的节点的vnode是4TB节点的2倍就可以了。

如果vnode节点和环上的点一一对应的话,可以认为是一致性hash的一个特殊的场景,比如说上图中的例子,这个hash环一个有A到Z 25个点(A、Z重合了),如果有25个vnode和其对应的话,这样一致性hash只需要记录每个物理node节点到vnode的映射关系就可以了,会非常的简单。开源swift对象存储使用的是这种一致性hash,参考:https://docs.openstack.org/swift/latest/ring_background.html

在分布式系统中为了保障可靠性一般都是多副本存储的,在dynamo存储系统中,用一致性hash算法查找到第一个vnode节点后,会顺序的向下找更多vnode节点,用来存储多副本(中间会跳过同台机器上的vnode,以达到隔离故障域的要求),并且第一个vnode是协调节点。在开源swift对象存储系统中,节点会先分组,比如3个一组,形成一个副本对,然后vnode会分配到某组机器上,一组机器上会有很多的vnode,并且这组机器上的vnode的leader节点在3台机器上会打散,分摊压力。

crush算法的核心思想 crush算法是一个伪随机的路由选择算法,输入pg的id,osdmap等元信息,通过crush根据这个pool配置的crush rule规则的伪随机计算,最终输出存储这个pd的副本的osd列表。由于是伪随机的,只要osdmap、crush rule规则相同,在任意的机器上,针对某个pg id,计算的最终的osd列表都是相同的。

crush算法支持在crush rule上配置故障域,crush会根据故障域的配置,沿着osdmap,搜索出符合条件的osd,然后由这些osd抽签来决定由哪个osd来存储这个pg,crush算法内部核心是这个称为straw2的osd的抽签算法。straw2的名字来源于draw straw(抽签:https://en.wikipedia.org/wiki/Drawing_straws)这个短语,针对每个pg,符合故障域配置条件的osd来抽检决定谁来存储这个pg,osd抽签也是一个伪随机的过程,谁抽到的签最长,谁赢。并且每个osd的签的长度,都是osd独立伪随机计算的,不依赖于其他osd,这样当增删osd节点时,需要迁移的数据最少。

Ceph的crush算法与一致性hash对比介绍

如上图的一个示例,这是针对某个pg的一次抽签结果,从图中可以看到osd.1的签最长,所以osd.1赢了,最终osd.1会存储这个pg,在这个时候,如果osd.4由于故障下线,osd.4的故障下线并不会影响其他osd的抽签过程,针对这个pg,最终的结果还是osd.1赢,因此这个pg不会发生数据的迁移;当然,在上图从场景中,如果osd.1下线的话,osd.1上的pg会迁移到其他的osd上。增加osd节点的情况类似,比如在上图的场景中,如果新增加一个osd.5节点的话,每个osd都是独立抽签,只有osd.5赢的那些pg才会迁移到osd.5上,对其他的pg不会产生影响。因此,理论上,crush算法也和一致性hash一样,在增加删除osd节点的时候,需要迁移的数据最少。

另外straw2抽签算法也是支持异构的机型的,比如有的osd是4TB,有的osd是8TB,straw2的抽签算法会保证,8TB的osd抽签赢的概率是4TB的osd的两倍。背后的原理是,每个osd有个crush weight,crush weight正比于osd的磁盘大小,比如8TB的osd的crush weight是8左右,4TB的osd的crush weight是4左右。然后每个osd抽签的过程是,以osd的crush weight为指数分布的λ,产生一个指数分布的随机数,最后再比大小。

另外在ceph中,每个osd除了crush weight,还有个osd weight,osd weight的范围是0到1,表示的含义是这个osd故障的概率,crush算法在伪随机选择pg放置的osd的时候,如果遇到故障的osd,会进行重试。比如说某个osd weight是0的话,说明这个osd彻底故障了,通过上面straw2步骤计算出来的pg会retry重新分配到其他的osd上,如果某个osd的osd weight是0.8的话,这个osd上20%的pg会被重新放置到其他的osd上。通过把osd weight置为0,可以把某个osd节点从集群中临时剔除,通过调整osd weight也可以微调osd上的pg的分布。

总结 ceph分布式存储系统数据分布的基石crush算法,是一个伪随机的路由分布算法,对比一致性hash,它的核心的优点是元数据少,集群增删osd节点时,要迁移的数据少,并且crush算法支持异构的机型,支持各种级别的故障域的配置,它的缺点是在实际应用中发现,由于pg会占用一定的资源,一般每个osd最多200个pg左右,导致整个集群中pg数并不会特别的多,pg在osd上分布并不是非常的均衡,经常需要微调。

参考: https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf https://github.com/ceph/ceph/pull/20196 https://docs.openstack.org/swif

点赞
收藏
评论区
推荐文章
Stella981 Stella981
2年前
Redis都有哪些数据类型
string这是最基本的类型了,就是普通的set和get,做简单的kv缓存hash这个是类似map的一种结构,这个一般就是可以将结构化的数据,比如一个对象(前提是这个对象没嵌套其他的对象)给缓存在redis里,然后每次读写缓存的时候,可以操作hash里的某个字段。key150value{“id”:
Wesley13 Wesley13
2年前
Java中HashMap的实现原理
总结:HashMap的实现原理:1.利用key的hashCode重新hash计算出当前对象的元素在数组中的下标2.存储时,如果出现hash值相同的key,此时有两种情况。(1)如果key相同,则覆盖原始值;(2)如果key不同(出现冲突),则将当前的keyvalue放入链表中3.获取时,直接找到hash值对应
Stella981 Stella981
2年前
Consistent hashing一致性算法原理
最近在整理redis分布式集群,首先就整理一下分布式算法原理。常见的分区规则有哈希分区和顺序分区两种,Redis采用的是哈希分区规则。节点取余分区使用特定的数据,如Redis的键或用户ID为key,节点数量为N,则:hash(key)%N,计算出哈希值,然后决定映射到哪个节点上,如节点数为4时,哈希值的结果可能为0、1、2,3.现假
Stella981 Stella981
2年前
Hash冲突和一致性
对于hash算法,有几个问题避无可避的。问题1:hash冲突的问题?1\.背景介绍:在数据量很大的时候,就会出现hash之后的数值,指向相同的位置,也就是所谓的hash冲突。这个取决于hash算法的好坏,以及数据量的大小,hash算法越差,数据量越大,hash冲突的概率就会越大。2\.然而一旦出现了hash冲突,我们该怎么办
Wesley13 Wesley13
2年前
oracle获取hash值
_ORACLE_中提供了几种_HASH_的函数,主要包括下面三种_MD4_,_MD5_,_SH1_。我知道常用的函数调用方法如下:_1,_这个函数不知道具体的哪种算法,不过这个应该是最常用的一个_HASH_函数了_selectdbms\_utility.get\_hash\_value('1',1,100)fromdual;__2,_
Wesley13 Wesley13
2年前
MySQL的btree索引和hash索引的区别
Hash索引结构的特殊性,其检索效率非常高,索引的检索可以一次定位,不像BTree索引需要从根节点到枝节点,最后才能访问到页节点这样多次的IO访问,所以Hash索引的查询效率要远高于BTree索引。可能很多人又有疑问了,既然Hash索引的效率要比BTree高很多,为什么大家不都用Hash索引而还要使用BTree索引呢?
Stella981 Stella981
2年前
CodeForces985F:Isomorphic Strings (字符串&hash)
题意:取出字符串Str里的两个串S,T,问对应位置的的字符在否有一一映射关系。hash:对于每个字符s‘a’‘z’,我们任意找一个i,满足Sis,(代码里用lower\_bound在区间找到最小的位置i)其对应的字符为Tit。然后我们判断这段区间里s的hash值是否等于t的hash值。不难证明26个字母都满足时对应hash相同时,才有
Wesley13 Wesley13
2年前
Java之一致性hash算法原理及实现
一致性哈希算法是分布式系统中常用的算法。比如,一个分布式的存储系统,要将数据存储到具体的节点上,如果采用普通的hash方法,将数据映射到具体的节点上,如key%N,key是数据的key,N是机器节点数,如果有一个机器加入或退出这个集群,则所有的数据映射都无效了。一致性哈希算法,解决了普通余数Hash算法伸缩性差的问题,可以保证在上线、下线服务
传统数据存储
通常情况下,业务系统产生的大量日志都是集中存储处理的。集中存储是指有一个由大型主机或多台主机组成的中心节点,数据集中存储在这个中心节点上,整个系统的所有业务单元都集中部署在这个中心节点上。数据计算几乎完全依赖于一台中大型中央计算机的处理能力。系统的所有功能
VictoriaMetrics常见性能问题排查
VM集群由以下子模块组成vmstorage:存储原始数据,并根据指定时间范围和标签过滤条件等返回查询数据集vminsert:接收数据写入,并根据指标名和标签按一致性hash分发至集群中vmstorage节点vmselect:执行查询请求,从数据所在的vmstorage节点获取数据每个模块可以独立扩缩容。其中vmstorage各节点之间不互相通信,属于sharenothing架构。如此可以增加集群可用性,也简化了集群维护、扩容。
天翼云开发者社区
天翼云开发者社区
Lv1
天翼云是中国电信倾力打造的云服务品牌,致力于成为领先的云计算服务提供商。提供云主机、CDN、云电脑、大数据及AI等全线产品和场景化解决方案。
文章
586
粉丝
11
获赞
40