《Ceph 的数据分布算法.docx》由会员分享，可在线阅读，更多相关《Ceph 的数据分布算法.docx（9页珍藏版）》请在第壹文秘上搜索。
1、1.引言数据分布是分布式存储系统的要解决的首要问题，在分布式存储系统当中，展核心也是最基本的要求就是数据的分布算法或者规则能够解决以下几个问题：(1)数据负载均衡：数据能够均匀地分布在磁盘容量不等的存储节点；(2)故障隔商:保障不同的数据副本分布于不同的故獐隔离域；(3)节点变动与数据迁移：正常节点上的迁移影响达到最小，数据H达到最少.很多分布式存储系统都会用到一致性哈希凭法来支撑其数据的均衡分布.例如在Aamzon的Dyanmo键值存储系统QPenStaCk的Swift对象存储系统.而Ceph的数据分布主要是齐哈希和CRUSH算法支撑的，而CRUSH第法又是其核心箔法.2. Object-P
2、G映射算法2.1 映射过程从客户端维度看Object-PG的过程，需要经过两个关键步骤：(1) File-Object:将文件按照固定粒度大小(2M/4M)进行切分，得到对象(Obj-ID);(2)ObjectPG:通过哈希算法HASH(Obj-ID)%PG.Number,得到PG(PG-ID).首先，通过接口调用保障文件可以平均切分为多个2/4M的对象以及对象的有序标识号.然后，通过哈希算法将有序序列分散，经过取余计算将对象均匀分布在逻辑分区内的PG上。2.2 PG的价值我们知道，在Ceph中的POOl&PG(PlacementGroup)其实是逻辑概念，它是把Ceph的整个存储空间用Poo
3、l划为若干逻辑的分区，每一个Pool又是由很多个PG组成，每一个PG对应于唯一ObjeCt的数据分布控制，它对应于一个OSD的故障隔离组(IPrimary-OSD&2Replic-0SD).结合图2.2所示，我们可以清晰看到PG在数据分布当中的首个核心价值.图2.2FIIe-PG数据映射分布图示结合图2.2,我们回过头来看File.PG的算法过程：首先，从File到ObjeCt的切分过程，会得到一组有序标识的OBjeCtS;然后经过哈希并取余的算法(HASH(Obj-ID)%PG.Number为导到Object对应的PG.Pool和PG的组成结构是个虚拟的概念，在物理节点经常变动的整个过程当中
4、.每一个Pool之内的PG数量是不会发生变化的。不难理解，随着写入文件数量规模理来越大，被切分的一个个有序ObjeCt组会均匀分布在图2.2Pool当中的各个PG上，而且ObjeCt-ID的取值范围远远超过PG.Number,这样就会保障同一个文件当中ObjeCt在整个Pool分布的分散性特点.虽然ObjeCt-PG并不代表数据的物理分布达到了应有的均衡性，但是最起码为后续PG-OSD映射的均衡性英定了基础.读到这里，或许有人会有疑问”为什么不直接完成ObjeCt-OSD的映射，这样不是更直接,住潴更好么？”.那么，顺着这个疑问的思路，我们不妨把算法改变为(HASH(Obj-ID)%OSD_N
5、umber),这里的取余披除数由PG_Number变成了OSD_Number,逻娼节点变成了物理节点，不变的因素变成了经常会发生变化的因素(故障&扩容).一旦发生这种变化，之前存储的所有数据的计算结果大概率发生变化，这样的变化会带来大规模的数据迁移.这显然是与分布式系统数据分布的基本诉求点是相悖的.因此，无论是采用哈希一致性算法还是采用其他数据分布舜法，中间的虚拟对象是必要的.3. PG_OSD映射算法3.1 CIustejMapCeph09clustermap包含的几个主要map分别是MonitormapxOSDmap.CRUSHmap、PGmap.这些clustermap将有助于知晓集群的
6、状态和配置.接下来分别吞看这些Map当中都包含了哪些基础的信息.(1) MOnitOrMap:它包含Monitor基本信息，例如集群ID、monitor节点信息、IP地址和端口号、配首版本、时间战等相关信息.(2) OSDMap:一方面是OSD自身的信息(节点、容量、状态、权重等)；另外一方面是存储池相关的信息(存储池名称、ID、类型、制本级别、PGs).(3) PGMap:一方面是PG自身信息(ID、版本、时间裁、OSDmap的最新版本号、容量)；另外一方面是对象信息(数量、状态、时间联、OSDSetS等).(4)CRUSHMap:它保存的信息包括集群设备列表、bucket歹IJ表、故障域(
7、failuredomain)分层结构、保存数据时用到的为故障域定义的规则(rules)等.PGJDSD的映射过程主要依赖于PGMap&CRUSHMap.接下来我们来看看CRUSHMap究竟是一个什么样的数据结构.将代码的结构化逻辑提取出来之后，如下所示：早力“devices”：由“types“：一j“buckets”：由“rules”：一1tunables:nchoose_argsn:1.一这里面,4,device即OSD实例,types=root,region,datacenter,room,pod、pdu、row、rack、chassis,host、osd.从types可选项的数据结构不难
8、看出它是一个分层的树形结构，从上到下包含了根、区域、数据中心、机房、主机、磁盘系列分层对釜.如图3.1.2所示:图3.1CRUSHMap说明示意图图中，黑色的节点我们称之为Bucket,绿色的节点称之为1.eaf,那么“buckets就保存了一棵具有所有OSD信息的完整的树形结构.早（id:bucket-type；alg：weight：item：bucket-type:类型（磁盘、主机、机柜），用来指定该BUCket在CRUSH分层结构中的位声；alg:Ceph提供多个bucket类型的算法选择用来寻址其下面的叶子节点；weight:bucket下面所有节点的权至息积信息，所有的磁盘无论其容量
9、大小都要被加入到集群中被同等地利用.CRUSH给每个OSD分配一个权主.OSD的权*越高，说明它的物理存储容量越大。权重表示设备容量之间的相对差异；item:bucket下面所有干节点bucket以及叶子节点的列表信息，包含权更.接下来再看CRUSHMaP当中的*,rules,CRUSHm叩包含了若干CRUSHrules来决定存幡池内的数据存放方式.它们定义了存储池的属性,以及存储池中数据的存放方式.它们指定了复制(replication)和放百(PlaCement)策略.steptakestepchoosefirstnnumtypebusket-type)StepChooseleaffirs
10、tn(num)type(bucket-type)steptake:获取一个bucket名称，开始遍历其树.stepchoose:选择某类型的若干(N)bucket,这里数字N通常是存储池的副本份数.stepChooseleaf:首先选择指定bucket类型的一组bucket,然后从每个bucket的子树中选择叶子节点.该组中bucket的数目N通常是该存储池的副本份数.3.2 CRUSH寻址算法从上一节的介绍当中，我们基本了解了CRUSHMaP的数据结构以及不同参数的串要意义.本节我们基于以上基础，来分析从PG到OSD的具体过程.这个过程就是要在CRUSH树形结构中解决“从哪里出发？途经哪几条
11、路？到达哪些终点目标？”这几个问题；那么为了解决这几个问题需要如下输入PGMap.CRUSHM叩、Rule,如图3.2所示：图3.2CRUSH寻址流程示意图如图，PG_0SD逻揖过程当中的PG要解决三个问题：(1)Where:从嘟里开始寻找OSD,原点在哪里？我们在上一节内容当中的CRUSHMaP的定义当中看到了.其中“rules的实例会明确定义PG寻找OSD的原点应该是嘟一个Bucket实例.这个我们在做Ceph集群规划配笈的时候可以输入我们相应的规则，默认为根节点。(2)How:如何寻找OSD的路由，原点下面有很多分支，路由如何选择？同样在CRUSHMap当中的rules的实例当中会定义.
12、具体为stepchoosefirstnnumtypebusket-type”,只不过这里需要一些输入。根据我们的规则确定副本数和故障隔离区类型获得了num&busket-type,可以启动计算了.在计算的过程当中还要调用CRUSH算法，而CRUSH算法就需要PGJD.BucketsTree等这些数据结构实例以及相应参数num的输入，才可以最终得到相应数目的Buckets.(3)Which:如何寻找到具体的OSD?既然Bucket都定了，那么我们只需要在How的循环过程中寻找每个Bucket下面的1.eaf节点.如何能定位到这个叶子节点，这就需要遍历Bucket数据结构里面定义的Item数据结构
13、了。按照前文的解释,Item本身是一个包含了Bucket下面所有OSD及其权函Weight的集合，目标是权重展大，但是如何遍历就取决于Items的几种数据结构组织模式，也就是BUCket实例参数当中的alg(Uniform.1.ist、Tree、StraW),不同的数据结构在寻址豆杂性以及集群变化后的受影响程度上都会有较大的差异.后面的章节我们继续这个问题.3.3 Bucketalg前面的章节介绍,我们基本解决了从PG到OSD这个路径当中的大部分问糜,只剩下唯一的问题就是用什么样的算法去遍历BUCket下面的所有1.eaf节点，以确定最终的OSD,这里就需要搞清楚BUCket下面所有节点的数据
14、组合类型(Bucketalg)以及它相应的算法特性.Bucketalg定义的是Bucket的组织模式，主要有四种类型：Uniform.1.ist、Tree、Straw.(1) Uniform:当所有存储设备的权里都统一时可以使用这种类型的bucket.当权重不统一时不能使用.在这种类型的bucket中添加或者删除设备将会导致大量数据重新放置,效率较差。适用于所有子节点权至相同的情况，而且bucket很少添加删除节点，这种情况强找速度应该是最快的.(2)1.ist:这种桶把它们的内容汇聚为微表.它基于RUSHP算法，一个列表就是一个自然、直观的扩张集群：对象会按一定概率被重定位到屐新的设备、或者
15、像从前一样仍保留在较老的设备上.结果是优化了新条目加入桶时的数据迁移.然而，如果从链表的中间或末尾删除了一些条目，将会导致大量没必要的挪动.所以这种桶适合永不或极少缩减的场景.(3)Tree:它用一种二进制搜索捌，规模效率远高于列表.列表buckets对于少量的数据项还是高效的,当链表达到较大规模时，其时间豆杂度就太大了.树状buckets由RUSHT发展而来，它通过将这些大量的数据项储存到一个二叉树中来解决这个问题.它将定位的时间复杂度由0(n)降低到O(Iogn),这使得它们更适合管理更大规模的设备或嵌套桶.(4)Straw:这种类型让Bucket所包含的所有item公平的竞争，而不需要遍历.这种算法就像抽签一样，所有的item都有机会被抽中，但是长签被抽中的概率更高.每个签的长度是基于。SD权重基础之上又加入了随机因子参与被计凭出来的权电,可以将有限的权重序列变为散列化长度的抽签。这种Bucket是Ceph曾默认使用的Bucket,所以它也是经过大规模测试的，稳定性较好。虽然它的查询性能不如1.iSt和Tree,但它在控制数据迁移方面是最优的.后续优化之后又出现了Straw2.对比来看,从查询豆杂度、添加节点以及删除节点三个维度来看各个alg类型的优略：类型时间豆杂度添加节点删除节点U
