深入Ceph原理包含核心算法Crush说明和通信机制原理(五)(上)

简介: 深入Ceph原理包含核心算法Crush说明和通信机制原理(五)(上)

深入Ceph原理


一、Crush算法与作用



CRUSH 算法,全称 Controlled Replication Under Scalable Hashing (可扩展哈希下的受控复制),它是一个可控的、可扩展的、分布式的副本数据放置算法, 通过CRUSH 算法来计算数据存储位置来确定如何存储和检索数据。


  • 保障数据分布的均衡性
  • 集群的灵活伸缩性
  • 支持更大规模的集群


二、Crush算法说明



PG 到 OSD 的映射的过程算法称为 CRUSH 算法,它是一个伪随机的过程,可以从所有的 OSD 中,随机性选择一个OSD 集合。


Crush Map 将系统的所有硬件资源描述成一个树状结构,然后再基于这个结构按照一定的容错规则生成一个逻辑上的树形结构,树的末级叶子节点device 也就是 OSD ,其他节点称为 bucket 节点,根据物理结构抽象的虚拟节点,包含数据中心抽象、机房抽象、机架抽象、主机抽象。



1b878792ede148b5a416b5a6202eb90c.png


三、Crush算法原理



1、Ceph的存储结构


Ceph 为了保存对象,会先构建一个池( pool ),把 pool 可以比喻成一个仓库,一个新对象的保存就类似于把一个包裹放到仓库里面。


2、PG的分配存储


对象是如何保存至哪个 PG 上?假设 Pool 名称为 rbd ,共有 256 个 PG ,每个 PG 编个号分别叫做 0x0, 0x1, 0x2 ,... 0xFF 。 具体该如何分配?这里可以采用 Hash 方式计算。假设有两个对象名, 分别为bar 和 foo 的,根据对象名做 Hash 计算:


HASH ( ‘bar’ ) = 0x3E0A4162
HASH ( ‘foo’ ) = 0x7FE391A0


通过 Hash 得到一串随机的十六进制的值, 对于同样的对象名,计算出的结果能够永远保持一致,但我们预分配的是256 个 PG ,这就需要再进行取模处理, 所得的结果会落在【 0x0 , 0xFF 】区间:


0x3E0A4162 % 0xFF ===> 0x62
0x7FE391A0 % 0xFF ===> 0xA0


实际在Ceph中, 存在很多个Pool,每个Pool里面存在若干个PG,如果两个Pool里面的PG编号相同,该如何标识区分?Ceph会对每个pool再进行编号,一个PG的实际编号是由pool_id + . + pg_id组成。


3、OSD的分配存储


Ceph 的物理层,对应的是服务器上的磁盘, Ceph 将一个磁盘或分区作为 OSD ,在逻辑层面,对象是保存至PG 内,现在需要打通 PG 与 OSD 之间的联系, Ceph 当中会存在较多的 PG 数量,如何将 PG平均分布各个OSD 上面,这就是 Crush 算法主要做的事情: 计算 PG -> OSD 的映射关系。

上述所知, 主要两个计算步骤:


POOL_ID (对象池) + HASH (‘对象名称 ’ ) % pg _ num (归置组)==> PG _ ID (完整的归置组编号)
CRUSH ( PG _ ID )==> OSD (对象存储设备位置)


4、为什么需要采用Crush算法


如果把 CRUSH ( PG _ ID )改成 HASH ( PG_ID ) % OSD_NUM 能否适用? 是会存在一些问题。


1 )如果挂掉一个 OSD ,所有的 OSD_NUM 余数就会发生变化,之前的数据就可能需要重新打乱整理, 一个优秀的存储架构应当在出现故障时, 能够将数据迁移成本降到最低,


CRUSH 则可以做到。


2 )如果增加一个 OSD, OSD_NUM 数量增大, 同样会导致数据重新打乱整理,但是通过CRUSH可以保障数据向新增机器均匀的扩散, 且不需要重新打乱整理。


3 )如果保存多个副本,就需要能够获取多个 OSD 结果的输出, 但是 HASH 方式只能获取一个, 但是通过CEPH 的 CRUSH 算法可以做到获取多个结果。


5、Crush算法如何实现


每个 OSD 有不同的容量,比如是 4T 还是 800G 的容量,可以根据每个 OSD 的容量定义它的权重,以 T为单位, 比如4T 权重设为 4 , 800G 则设为 0.8 。

那么如何将 PG 映射到不同权重的 OSD 上面?这里可以直接采用 CRUSH 里面的 Straw 抽签算法,这里面的抽签是指挑取一个最长的签,而这个签值就是OSD 的权重。


image.png


主要步骤:


  • 计算HASH: CRUSH_HASH( PG_ID, OSD_ID, r ) ==> draw把r当做一个常数,将PG_ID, OSD_ID一起作为输入,得到一个HASH值。
  • 增加OSD权重: ( draw &0xffff ) * osd_weight ==> osd_straw 将计算出的HASH值与OSD的权重放置一起,这样就能够得到每个OSD的签长, 权重越大的,数值越大。
  • 遍历选取最高的权重:high_draw


Crush 目的是随机跳出一个 OSD ,并且要满足权重越大的 OSD ,挑中的概率越大。如果样本容量足够大, 随机数对选中的结果影响逐渐变小, 起决定性的是OSD 的权重, OSD 的权重越大, 被挑选的概率也就越大。


Crush 所计算出的随机数,是通过 HASH 得出来,可以保障相同的输入会得出同样的输出结果。 所以Crush 并不是真正的随机算法, 而是一个伪随机算法。


这里只是计算得出了一个 OSD ,在 Ceph 集群中是会存在多个副本,如何解决一个 PG 映射到多个OSD的问题?


将之前的常量 r 加 1 , 再去计算一遍,如果和之前的 OSD 编号不一样, 那么就选取它;如果一样的话,那么再把r+2 ,再重新计算,直到选出三个不一样的 OSD 编号。


image.png


假设常数 r=0 ,根据算法 (CRUSH_HASH & 0xFFFF) * weight 计算最大的一个 OSD ,结果为 osd.1 的0x39A00,也就是选出的第一个 OSD ,然后再让 r=1 , 生成新的 CRUSH_HASH 随机值,取得第二个OSD,依次得到第三个 OSD 。


目录
相关文章
|
17天前
|
存储 算法 Java
解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用
在Java中,Set接口以其独特的“无重复”特性脱颖而出。本文通过解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用。
36 3
|
29天前
|
机器学习/深度学习 算法 机器人
多代理强化学习综述:原理、算法与挑战
多代理强化学习是强化学习的一个子领域,专注于研究在共享环境中共存的多个学习代理的行为。每个代理都受其个体奖励驱动,采取行动以推进自身利益;在某些环境中,这些利益可能与其他代理的利益相冲突,从而产生复杂的群体动态。
131 5
|
6天前
|
负载均衡 算法 应用服务中间件
5大负载均衡算法及原理,图解易懂!
本文详细介绍负载均衡的5大核心算法:轮询、加权轮询、随机、最少连接和源地址散列,帮助你深入理解分布式架构中的关键技术。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
5大负载均衡算法及原理,图解易懂!
|
12天前
|
算法 数据库 索引
HyperLogLog算法的原理是什么
【10月更文挑战第19天】HyperLogLog算法的原理是什么
15 1
|
18天前
|
机器学习/深度学习 人工智能 算法
[大语言模型-算法优化] 微调技术-LoRA算法原理及优化应用详解
[大语言模型-算法优化] 微调技术-LoRA算法原理及优化应用详解
52 0
[大语言模型-算法优化] 微调技术-LoRA算法原理及优化应用详解
|
1月前
|
机器学习/深度学习 算法
机器学习入门(三):K近邻算法原理 | KNN算法原理
机器学习入门(三):K近邻算法原理 | KNN算法原理
|
17天前
|
算法
PID算法原理分析
【10月更文挑战第12天】PID控制方法从提出至今已有百余年历史,其由于结构简单、易于实现、鲁棒性好、可靠性高等特点,在机电、冶金、机械、化工等行业中应用广泛。
|
18天前
|
机器学习/深度学习 算法 数据建模
计算机前沿技术-人工智能算法-生成对抗网络-算法原理及应用实践
计算机前沿技术-人工智能算法-生成对抗网络-算法原理及应用实践
21 0
|
18天前
|
算法 JavaScript 前端开发
垃圾回收算法的原理
【10月更文挑战第13天】垃圾回收算法的原理
20 0
|
23天前
|
算法
PID算法原理分析及优化
【10月更文挑战第6天】PID控制方法从提出至今已有百余年历史,其由于结构简单、易于实现、鲁棒性好、可靠性高等特点,在机电、冶金、机械、化工等行业中应用广泛。