带你读《存储漫谈:Ceph原理与实践》——2.2.2 CRUSH 算法因子

简介: 带你读《存储漫谈:Ceph原理与实践》——2.2.2 CRUSH 算法因子

2.2.2  CRUSH 算法因子


上述介绍可以看出,CRUSH 算法在 Ceph 存储系统的数据寻址中占有核心地位,Ceph 存储系统通过 CRUSH 算法规则来控制数据的分布策略,Ceph 存储系统的 CRUSH算法能够控制对象文件在存储集群中随机均匀地分布。

CRUSH 算法包含两个关键输入因子:层次化的 Cluster Map 以及数据分布策略Placement Rules。


1. 层次化的 Cluster Map


层次化的 Cluster Map 反映了存储系统层级的物理拓扑结构。

Ceph 存储集群通过 Cluster Map 定义了 OSD 守护进程的静态拓扑关系(层级信息),使得 CRUSH 算法在选择 OSD 时具备了主机、机架、机房等信息的感知能力。通过Cluster Map 规则定义,Ceph 存储系统允许数据副本可以分布在不同的主机、不同的机架,甚至不同的机房中,提高了数据存储的安全性。

Cluster Map 由设备(device)和桶(bucket)组成,device 是最基本的存储设备,也就是 OSD,通常 1 个 OSD 对应 1 个磁盘存储设备,bucket 表示存放设备的容器,可以包含多个设备或子类型的 bucket。

存储设备(device)的权重由管理员设置,以控制设备负责存储的相对数据量,device的权重值越高,对应的磁盘就会被分配写入更多的数据。大型存储系统中的存储设备(磁盘)通常存在容量大小不等或者性能高低不一的情况,系统管理员可以依据存储设备的利用率和负载来设定权重,随机数据分布算法,以此控制数据的最终分布,实现存储系统设备的数据量均衡,进而平衡存储系统的 I/O 负载,最终提高存储集群整体的性能和可靠性。

桶的权重是它所包含的所有元素(device 及 bucket)权重的总和。Bucket 可以包含很多种类型,例如,Host 就代表一个主机节点,可以包含多个 device ;Rack 代表机架,包含多个 host 节点。Ceph 中默认有 OSD、host、Chassis、Rack、row、PDU、Pod、Room、Datacenter、Region、root,共计 11 个层级(同时也允许用户定义自己新的类型),它们含义如下。

OSD           磁盘设备,对应 OSD 守护进程

host           包含若干个 OSD 的主机

Chassis           包含若干个刀片服务器的机箱

Rack           包含若干个主机的机架

row            包含若干个主机的一排机柜

PDU           为机柜分配的电源插排

Pod           一个数据中心中的机房单间

Room          含若干个机柜和主机的机房

Datacenter        包含若干机房的数据中心

Region          包含若干数据中心的区域

root           bucket 分层结构的根

通常 OSD、host、Rack 层级较为常用。

下面举例说明 bucket 的用法。

host test1{            // 类型 host,名字为 test1
 id -2             //bucket 的 ID,一般为负值
 # weight 3.000        // 权重,默认为子 item 的权重之和
 alg straw           //bucket 随机选择的算法
 hash 0             //bucket 随机选择的算法使用的 hash 函数
 
     // 这里 0 代表使用 hash 函数 jenkins1
 item osd.1 weight 1.000 //item1: osd.1 和权重
 item osd.2 weight 1.000
 item osd.3 weight 1.000
}
host test2{ 
 id -3 
 # weight 3.00
 alg straw
 hash 0 
 item osd.3 weight 1.000
 item osd.4 weight 1.000
 item osd.5 weight 1.000
}
root default{          //root 的类型为 bucket,名字为 default
 id -1             //ID 号
 # weight 6.000
 alg straw 
 hash 0
 item test1 weight 3.000
 item test2 weight 3.000
}

根据上面 Cluster Map 的语法定义,图 2-2 给出了比较直观的层级化的树形结构。

如图 2-2 所示,Ceph 的 Cluster Map 是一个由 bucket 和 device 共同组成的树形存储层次结构,叶子节点是 device(也就是 OSD),其他的节点称为 bucket 节点,这些 bucket都是逻辑上的概念,是对物理结构的抽象(如对数据中心的抽象、机房的抽象、机架的抽象、主机的抽象等),树形结构只有一个最终的根节点,称为 root 节点,root 也是一个抽象的逻辑概念。

image.png

图 2-2 Ceph 的 Cluster Map 层级结构

在上面的 Cluster Map 中,有一个 root 类型的 bucket,名字为 default ;root 下面有两个 host 类型的 bucket,名字分别为 test1 和 test2,其下分别各有 3 个 OSD 设备,每个 device 的权重都为 1.000,说明它们的容量大小都相同。host 的权重为子设备之和,即test1 与 test2 的权重均为 3.000,它是自动计算的,不需要设置;同理,root 的权重为 6.000。

2. 数据分布策略 Placement Rules


Placement Rules 决定了一个 PG 的对象(副本或纠删码策略)如何选择 OSD,通过这些自定义的规则,用户可以设置副本在集群中的分布。

Ceph 存储系统的 Placement Rules 定义格式如下。

take(a)
choose
 choose fifirstn {num} type {bucket-type}
 chooseleaf fifirstn {num} type {bucket-type} 
 If {num} == 0, choose pool-num-replicas buckets (all-available).
 If {num} > 0 && < pool-num-replicas, choose that many buckets.
 If {num} < 0, it means pool-num-replicas - |{num}|.
Emit

Placement Rules 的执行流程如下。

(1)take 操作选择一个 bucket,一般是 root 类型的 bucket。

(2)choose 操作有不同的选择方式,其输入都是上一步的输出。

a)choose firstn 深度优先选择出 num 个类型为 bucket-type 的子 bucket。

b)chooseleaf 先选择出 num 个类型为 bucket-type 的子 bucket,然后递归到叶子节点,选择一个 OSD 设备。

i. 如果 num 为 0,num 就为 Pool 设置的副本数;

ii. 如果 num 大于 0,小于 Pool 的副本数,那么就选出 num 个;

iii. 如果 num 小于 0, 就选出 Pool 的副本数减去 num 的绝对值。

(3)emit 输出结果。

由上述流程可以看出,Placement Rules 主要定义以下 3 个关键操作。

(1)从 CRUSH Map 中的哪个节点开始查找;

(2)使用哪个节点作为故障隔离域;

(3)定位副本的搜索模式(广度优先或深度优先)。


3. 示例

(1)3 个副本分布在 1 个 row 下的 3 个 cabinet 中。

在图 2-3 中,最下面的长方形图例代表一台主机,里面的圆柱形图例代表 OSD,cabinet 图例代表一个机柜,row 图例代表一排机柜,顶端的 root 是根节点,可以把它理解成一个数据中心。

image.png

图 2-3 Ceph 数据分布示意(Cluster Map)

自顶而下来看,顶层是一个 root bucket,每个 root 下有 4 个 row 类型 bucket,每个 row 下面有 4 个 cabinet,每个 cabinet 下有若干个 OSD 设备(图中有 4 个 host,每个host 有若干个 OSD 设备,但是在本 CRUSH Map 中并没有设置 host 这一级别的 bucket,而是直接把 4 个 host 上的所有 OSD 设备定义为一个 cabinet)。

该场景下,Placement Rules 定义如下。

rule replicated_ruleset {
 ruleset 0              //ruleset 的编号 ID
 type replicated           // 类型 replicated 或者 erasure code 
 min_size 1             // 副本数最小值
 max_size 10             // 副本数最大值
 step take root           // 选择一个 root bucket,做下一步的输入
 step choose fifirstn 1 type row    // 选择一个 row,同一排
 step choose fifirstn 3 type cabinet // 选择 3 个 cabinet,3 副本分别在不同的 cabinet
 step choose fifirstn 1 type osd    // 在上一步输出的3个cabinet中,分别选择一个OSD
 step emit
}

根据上面的 Cluster Map 和 Placement Rules 定义,选择算法的执行过程如下。

1)选中 root bucket 作为下一个步骤的输入;

2)从 root 类型的 bucket 中选择 1 个 row 类的子 bucket,其选择的算法在 root 的定义中设置,一般设置为 straw 算法;

3)从上一步的输出 row 中,选择 3 个 cabinet,其选择的算法在 row 中定义;

4)从上一步输出的 3 个 cabinet 中,分别选出一个 OSD,并输出。最终实现效果为可选择出 3 个 OSD 设备,分布在 1 个 row 上的 3 个 cabinet 中。

(2)主副本分布在 SSD 上,其他副本分布在 HDD 上。

如图 2-4 所示的 Cluster Map 定义了 2 个 root 类型的 bucket,一个是名为 SSD 的root 类型的 bucket,其 OSD 存储介质都是 SSD 固态硬盘,它包含 2 个 host,每个 host上的存储设备都是 SSD 固态硬盘;另一个是名为 HDD 的 root 类型的 bucket,其 OSD 存储介质都是 HDD 硬盘,它有 2 个 host,每个 host 上的设备都是 HDD 硬盘。

image.png

image.png

图 2-4 Ceph 数据分布示意(Cluster Map)

该场景下,Placement Rules 定义如下。

rule ssd-primary {
 ruleset 0
 type replicated
 min_size 1
 max_size 10
 step take ssd              // 选择 SSD 这个 root bucket 为输入
 step chooseleaf fifirstn 1 type host   // 选择一个 host,
并递归选择叶子节点 OSD
 step emit               // 输出结果
 step take hdd             // 选择 HDD 这个 root bucket 为输入
 step chooseleaf fifirstn -1 type host // 选择总副本数减一个 host
 // 并分别递归选择一个叶子节点 OSD
 step emit               // 输出结果
}

根据上面的 Cluster Map 和 Placement Rules 定义,选择算法的执行过程如下。

1)首先 take 操作选择 ssd 为 root 类型的 bucket ;

2)在 SSD 的 root 中先选择一个 host,然后以该 host 为输入,递归至叶子节点,选择一个 OSD 设备;

3)输出选择的设备,也就是 SSD 设备;

4)选择 HDD 作为 root 的输入;

5)选择 2 个 host(副本数减 1,默认 3 副本),并分别递归选择一个 OSD 设备,最终选出 2 个 HDD 设备;

6)输出最终结果。

最终实现效果为输出 3 个设备,一个是 SSD 类型的磁盘,另外两个是 HDD 磁盘。通过上述规则,就可以把 PG 的主副本存储在 SSD 类型的 OSD 上,其他副本分布在 HDD 类型的磁盘上。

相关文章
|
21天前
|
存储 算法 Java
解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用
在Java中,Set接口以其独特的“无重复”特性脱颖而出。本文通过解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用。
38 3
|
1月前
|
机器学习/深度学习 算法 机器人
多代理强化学习综述:原理、算法与挑战
多代理强化学习是强化学习的一个子领域,专注于研究在共享环境中共存的多个学习代理的行为。每个代理都受其个体奖励驱动,采取行动以推进自身利益;在某些环境中,这些利益可能与其他代理的利益相冲突,从而产生复杂的群体动态。
143 5
|
9天前
|
负载均衡 算法 应用服务中间件
5大负载均衡算法及原理,图解易懂!
本文详细介绍负载均衡的5大核心算法:轮询、加权轮询、随机、最少连接和源地址散列,帮助你深入理解分布式架构中的关键技术。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
5大负载均衡算法及原理,图解易懂!
|
9天前
|
开发者 容器
Flutter&鸿蒙next 布局架构原理详解
本文详细介绍了 Flutter 中的主要布局方式,包括 Row、Column、Stack、Container、ListView 和 GridView 等布局组件的架构原理及使用场景。通过了解这些布局 Widget 的基本概念、关键属性和布局原理,开发者可以更高效地构建复杂的用户界面。此外,文章还提供了布局优化技巧,帮助提升应用性能。
72 4
|
9天前
|
存储 Dart 前端开发
flutter鸿蒙版本mvvm架构思想原理
在Flutter中实现MVVM架构,旨在将UI与业务逻辑分离,提升代码可维护性和可读性。本文介绍了MVVM的整体架构,包括Model、View和ViewModel的职责,以及各文件的详细实现。通过`main.dart`、`CounterViewModel.dart`、`MyHomePage.dart`和`Model.dart`的具体代码,展示了如何使用Provider进行状态管理,实现数据绑定和响应式设计。MVVM架构的分离关注点、数据绑定和可维护性特点,使得开发更加高效和整洁。
144 3
|
15天前
|
算法 数据库 索引
HyperLogLog算法的原理是什么
【10月更文挑战第19天】HyperLogLog算法的原理是什么
21 1
|
22天前
|
容器
Flutter&鸿蒙next 布局架构原理详解
Flutter&鸿蒙next 布局架构原理详解
|
21天前
|
机器学习/深度学习 人工智能 算法
[大语言模型-算法优化] 微调技术-LoRA算法原理及优化应用详解
[大语言模型-算法优化] 微调技术-LoRA算法原理及优化应用详解
55 0
[大语言模型-算法优化] 微调技术-LoRA算法原理及优化应用详解
|
23天前
|
存储 监控 分布式数据库
百亿级存储架构: ElasticSearch+HBase 海量存储架构与实现
本文介绍了百亿级数据存储架构的设计与实现,重点探讨了ElasticSearch和HBase的结合使用。通过ElasticSearch实现快速检索,HBase实现海量数据存储,解决了大规模数据的高效存储与查询问题。文章详细讲解了数据统一接入、元数据管理、数据一致性及平台监控等关键模块的设计思路和技术细节,帮助读者理解和掌握构建高性能数据存储系统的方法。
百亿级存储架构: ElasticSearch+HBase 海量存储架构与实现
|
1月前
|
前端开发 Java 应用服务中间件
21张图解析Tomcat运行原理与架构全貌
【10月更文挑战第2天】本文通过21张图详细解析了Tomcat的运行原理与架构。Tomcat作为Java Web开发中最流行的Web服务器之一,其架构设计精妙。文章首先介绍了Tomcat的基本组件:Connector(连接器)负责网络通信,Container(容器)处理业务逻辑。连接器内部包括EndPoint、Processor和Adapter等组件,分别处理通信、协议解析和请求封装。容器采用多级结构(Engine、Host、Context、Wrapper),并通过Mapper组件进行请求路由。文章还探讨了Tomcat的生命周期管理、启动与停止机制,并通过源码分析展示了请求处理流程。

热门文章

最新文章