带你读《存储漫谈Ceph原理与实践》第三章接入层3.1块存储 RBD(五)-阿里云开发者社区

开发者社区> 人民邮电出版社> 正文

带你读《存储漫谈Ceph原理与实践》第三章接入层3.1块存储 RBD(五)

简介: 带你读《存储漫谈Ceph原理与实践》第三章接入层3.1块存储 RBD
+关注继续查看

由于请求出队列的过程涉及大量的实时排序调整,因此服务器在生成dmClock- Server队列时,会基于 QoS的3个时间标签构造 3 棵完全二叉树,每棵二叉树的节点为各个 Client 请求子队列,节点在二叉树中的位置取决于其Client请求子队列队首元素的时间标签,构造规则是父节点的时间标签小于子节点。

请求入队列的执行流程如图3-13所示。若某个Client向Server发送请求,如果 Server中该 Client 的请求子队列中不存在未处理的请求,或子队列并不存在(即新来了一个Client,需要新创建子队列),则不仅需要让请求进入队列,还需将Client加入标签二叉树中,并依据标签时间的大小将其调整到正确位置。如果该Client的请求子队列中存在未处理的请求,则直接将该请求插入队列尾部即可。

 

 image.png

 

图3-13 请求入队列的流程

 

请求出队列的执行流程如图3-14所示。先进入预留时间标签阶段,取预留标签二叉树的 root 节点请求队列,判断其队首元素的预留时间标签是否满足出队条件,若满足,则使 root节点队列的队首元素(req)出队列(并调整该节点在预留二叉树中的位置,同时也要调整该root节点对应 Client 的子队列在权重二叉树和上限二叉树中的位置);否则进入基于上限和权重时间标签阶段,从上限二叉树的 root节点开始,依次开始判断节点队列的队首元素的上限时间标签是否满足出队条件,将满足出队条件的请求的ready位标记为true,再依据权重时间标签大小将权重二叉树中队列队首元素的ready位被标记为true的节点调整到合适位置,让位于权重标签二叉树root 节点的队首元素出队列,最后再去调整该 Client 在权重、上限、预留标签二叉树中的位置。

image.png

图3-14 请求出队列的流程

 

下面以实例形式分析 dmClock算法执行过程。

如表3-3所示,假设某分布式系统中有5Client这些Client的基准时间都为 to=0.0,每个Client的请求队列中有两个请求,QoS模板设置为[rlw],每个请求都以1/r, 1/l,1/w为间隔打标签,若当前时间T=0.024s,请求出队列。

3-3     案例示例数据

 

 

client

 

QoS

request1

request2

R<i,1>

L<i,1>

P<i,1>

R<i,2>

L<i,2>

P<i,2>

1

[20,40,5]

0.05

0.025

0.2

0.1

0.05

0.4

2

[10,30,3]

0.1

0.033

0.333

0.2

0.066

0.666

3

[30,50,2]

0.033

0.02

0.5

0.66

0.04

1

4

[40,60,1.25]

0.025

0.017

0.8

0.05

0.034

1.6

5

[70,100,4]

0.014

0.01

0.25

0.028

0.02

0.5

(1)  构造reservationtag、limittagweighttag二叉树过程(请求入队列的过程),


见图 3-15~图 3-17。

 

 

 image.png

 

图 3-15构造reservatontag_叉树过程

 

image.png

图 3-16构造 mttag_叉树过程

 image.png

 

图 3-17构造 we ghttag_叉树过程

 

(2)  Constraint-based阶段(请求出队列的第一阶段),见图3-18~图3-20。

image.png

 

图 3-18请求在 Constrant-based 阶段出队列- 预留标签_叉树调整过程

 


image.png

图 3-19  请求在Constrant-based 阶段出队列- 上限标签_叉树调整过程


image.png

图 3-20  请求在 Constrant-based 阶段出队列- 权重标签_叉树调整过程

 

 

 

(3)  Weight-based阶段请求出队的过程,见图3-21~图 3-24。

 image.png


图 3-21 找出满足出队条件的Cent

image.png


图 3-21找出满足出队条件的 Cent(续)

 image.png

 

 

图 3-22请求在 weght-based阶段出队列- 权重_叉树的调整过程

 image.png

 

 

图 3-23请求在 weght-based 阶段出队列- 上限时间标签的调整过程

 

 

image.png

 

 

图 3-24请求在 weght-based 阶段出队列- 预留标签时间的调整过程

 



版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
带你读《存储漫谈Ceph原理与实践》第三章接入层3.3.文件存储 CephFS(二)
《存储漫谈Ceph原理与实践》第三章接入层3.3.文件存储 CephFS
16 0
带你读《存储漫谈Ceph原理与实践》第三章接入层3.3.文件存储 CephFS(四)
带你读《存储漫谈Ceph原理与实践》第三章接入层3.3.文件存储 CephFS
18 0
带你读《存储漫谈Ceph原理与实践》第三章接入层3.2对象存储RGW(二)
《存储漫谈Ceph原理与实践》第三章接入层3.2对象存储RGW
14 0
带你读《存储漫谈Ceph原理与实践》第三章接入层3.2对象存储RGW(五)
带你读《存储漫谈Ceph原理与实践》第三章接入层3.2对象存储RGW
31 0
带你读《存储漫谈Ceph原理与实践》第三章接入层3.1块存储 RBD(六)
带你读《存储漫谈Ceph原理与实践》第三章接入层3.1块存储 RBD
15 0
《存储漫谈Ceph原理与实践》第三章接入层3.2对象存储RGW(三)
《存储漫谈Ceph原理与实践》第三章接入层3.2对象存储RGW
12 0
472
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载