Ceph的数据分布算法架构解读.docx

《Ceph的数据分布算法架构解读.docx》由会员分享，可在线阅读，更多相关《Ceph的数据分布算法架构解读.docx（11页珍藏版）》请在第一文库网上搜索。

1、分布式存储技术解读系列之二Ceph的数据分布算法架构解读1. 引言数据分布是分布式存储系统的要解决的首要问题，在分布式存储系统当中，最核心也是最基本的要求就是数据的分布算法或者规则能够解决以下几个问题：(1)数据负载均衡：数据能够均匀地分布在磁盘容量不等的存储节点；(2)故障隔离：保障不同的数据副本分布于不同的故障隔离域；(3)节点变动与数据迁移：正常节点上的迁移影响达到最小，数据量达到最少。很多分布式存储系统都会用到一致性哈希算法来支撑其数据的均衡分布。例如在AainZOn的DyanmO键值存储系统，OPenStaCk的SWift对象存储系统O而Ceph的数据分布主要是靠哈希和CRUSH算法

2、支撑的，而CRUSH算法又是其核心算法。2. Object_PG映射算法2.1 映射过程从客户端维度看Object-PG的过程，需要经过两个关键步骤：(1) Fi1eObject：将文件按照固定粒度大小(2M/4M)进行切分，得到对象(Obj-ID)；(2) ObjectPG：通过哈希算法HASH(Obj-ID)%PG_Number,得到PG(PG-ID)o首先，通过接口调用保障文件可以平均切分为多个2/4M的对象以及对象的有序标识号。然后，通过哈希算法将有序序列分散，经过取余计算将对象均匀分布在逻辑分区内的PG上。2.2 PG的价值我们知道，在CePh中的POO1&PG(P1acementG

3、roup)其实是逻辑概念，它是把Ceph的整个存储空间用Poo1划为若干逻辑的分区，每一个Poo1又是由很多个PG组成，每一个PG对应于唯一ObjeCt的数据分布控制，它对应于一个OSD的故障隔离组(IPrimary-OSD&2RepIic-OSD)。结合图2.2所示，我们可以清晰看到PG在数据分布当中的首个核心价值。Z/二:/，1图2.2FI1jPG数据映射分布图示结合图2.2,我们回过头来看Fi1e_PG的算法过程：首先，从FiIe到Objeet的切分过程，会得到一组有序标识的ObjeCts；然后经过哈希并取余的算法(HASH(Obj-ID)%PG_Number)得到ObjeCt对应的PG

4、oPooI和PG的组成结构是个虚拟的概念，在物理节点经常变动的整个过程当中，每一个POOI之内的PG数量是不会发生变化的。不难理解，随着写入文件数量规模越来越大，被切分的一个个有序Object组会均匀分布在图2.2Poo1当中的各个PG上，而且ObjeCt-ID的取值范围远远超过PG_Number,这样就会保障同一个文件当中ObjeCt在整个POo1分布的分散性特点。虽然Object-PG并不代表数据的物理分布达到了应有的均衡性，但是最起码为后续PG-OSD映射的均衡性奠定了基础。读到这里，或许有人会有疑问“为什么不直接完成Objeet-OSD的映射，这样不是更直接，性能更好么？”。那么，顺着

5、这个疑问的思路，我们不妨把算法改变为(HASH(Obj-ID)%OSD_Number),这里的取余被除数由PG_Number变成了OSD_Number,逻辑节点变成了物理节点，不变的因素变成了经常会发生变化的因素（故障&扩容）。一旦发生这种变化，之前存储的所有数据的计算结果大概率发生变化，这样的变化会带来大规模的数据迁移。这显然是与分布式系统数据分布的基本诉求点是相悖的。因此，无论是采用哈希一致性算法还是采用其他数据分布算法，中间的虚拟对象是必要的。3. PG_OSD映射算法3.1 C1uster_MapCePh的C1UStermap包含的几个主要map分别是Monitormap、OSDmap

6、、CRUSHmap.PGmap0这些C1UStermap将有助于知晓集群的状态和配置。接下来分别看看这些MaP当中都包含了那些基础的信息。（1） MonitorMap：它包含MOnitOr基本信息，例如集群ID、monitor节点信息、IP地址和端口号、配置版本、时间戳等相关信息。（2） OSDMap：一方面是OSD自身的信息（节点、容量、状态、权重等）；另外一方面是存储池相关的信息（存储池名称、ID、类型、副本级别、PGs）0（3） PGMap：一方面是PG自身信息（ID、版本、时间戳.、OSDmap的最新版本号、容量）；另外一方面是对象信息（数量、状态、时间戳、OSDsets等）。（4）

7、CRUSHMap：它保存的信息包括集群设备列表、bucket列表、故障域(fai1uredomain)分层结构、保存数据时用到的为故障域定义的规则(ru1es)等。PG_OSD的映射过程主要依赖于PGMap&CRUSHMapo接下来我们来看看CRUSHMaP究竟是一个什么样的数据结构。将代码的结构化逻辑提取出来之后，如下所示：这里面,device”即OSD实例，types”=root、region、datacenterroom、pod、Pdu、row、rack、chassis、host、osdo从“types”可选项的数据结构不难看出它是一个分层的树形结构，从上到下包含了根、区域、数据中心、机

8、房.、主机、磁盘系列分层对象。如图3.12所示:图3.1CRUSHMap说明示意图图中，黑色的节点我们称之为BUCket,绿色的节点称之为1eaf,那么“buckets”就保存了一颗具有所有OSD信息的完整的树形结构。 bucket-type：类型（磁盘、主机、机柜.）,用来指定该BUCket在CRUSH分层结构中的位置； a1g：CePh提供多个bucket类型的算法选择用来寻址其下面的叶子节 weight：bucket下面所有节点的权重累积信息，所有的磁盘无论其容量大小都要被加入到集群中被同等地利用。CRUSH给每个OSD分配一个权重。OSD的权重越高，说明它的物理存储容量越大。权重表示设

9、备容量之间的相对差异； item：bucket下面所有干节点bucket以及叶子节点的列表信息，包含权重。接下来再看CRUSHMap当中的“ru1es”,CRUSHmap包含了若干CRUSHru1es来决定存储池内的数据存放方式。它们定义了存储池的属性，以及存储池中数据的存放方式。它们指定了复制(rep1ication)和放置(p1acement)策略。 steptake：获取一个bucket名称，开始遍历其树O stepchoose：选择某类型的若干(N)bucket,这里数字N通常是存储池的副本份数。 stepchoose1eaf：首先选择指定bucket类型的一组bucket,然后从每个

10、bucket的子树中选择叶子节点。该组中bucket的数目N通常是该存储池的副本份数。3.2 CRUSH寻址算法从上一节的介绍当中，我们基本了解了CRUSHMaP的数据结构以及不同参数的重要意义。本节我们基于以上基础，来分析从PG到OSD的具体过程。这个过程就是要在CRUSH树形结构中解决“从哪里出发？途径哪几条路？到达哪些终点目标？“这几个问题；那么为了解决这几个问题需要如下输入“PGMap、CRUSHMapsRu1evo如图3.2所示：图3.2CRUSH寻址流程示意图如图，PG_OSD逻辑过程当中的PG要解决三个问题：(1) Where：从哪里开始寻找OSD,原点在哪里？我们在上一节内容当

11、中的CRUSHMaP的定义当中看到了。其中“ru1es”的实例会明确定义PG寻找OSD的原点应该是哪一个BUCket实例。这个我们在做CePh集群规划配置的时候可以输入我们相应的规则，默认为根节点。(2) How：如何寻找OSD的路由，原点下面有很多分支，路由如何选择？同样在CRUSHMap当中的“ru1es”的实例当中会定义。具体为“stepchoosefirstnnumtype(buskettype,只不过这里需要一些输入。根据我们的规则确定副本数和故障隔离区类型获得了num&busket-type,可以启动计算了。在计算的过程当中还要调用CRuSH算法，而CRUSH算法就需要PGD、BU

12、CketSTree等这些数据结构实例以及相应参数num的输入，才可以最终得到相应数目的Bucketso(3) Which：如何寻找到具体的OSD?既然BUCket都定了，那么我们只需要在HOW的循环过程中寻找每个BUCket下面的1eaf节点。如何能定位到这个叶子节点，这就需要遍历BUCket数据结构里面定义的Item数据结构了。按照前文的解释，Iten1本身是一个包含了BUCket下面所有OSD及其权重Weight的集合，目标是权重最大，但是如何遍历就取决于ItenIS的几种数据结构组织模式，也就是BUCket实例参数当中的a1g(Uniform、1iSt、Tree、Straw),不同的数据

13、结构在寻址复杂性以及集群变化后的受影响程度上都会有较大的差异。后面的章节我们继续这个问题。3.3 Bucketa1g前面的章节介绍，我们基本解决了从PG到OSD这个路径当中的大部分问题，只剩下唯一的问题就是用什么样的算法去遍历Bucket下面的所有1eaf节点，以确定最终的OSDo这里就需要搞清楚Bucket下面所有节点的数据组合类型(Bucketa1g)以及它相应的算法特性。Bucketa1g定义的是BUCket的组织模式，主要有四种类型:Uniforn1、1iSt、Tree、Strawo(1) Uniform：当所有存储设备的权重都统一时可以使用这种类型的bucket,当权重不统一时不能使

14、用。在这种类型的bucket中添加或者删除设备将会导致大量数据重新放置，效率较差。适用于所有子节点权重相同的情况，而且bucket很少添加删除节点，这种情况查找速度应该是最快(2) 1ist：这种桶把它们的内容汇聚为链表。它基于RUSHP算法，一个列表就是一个自然、直观的扩张集群：对象会按一定概率被重定位到最新的设备、或者像从前一样仍保留在较老的设备上。结果是优化了新条目加入桶时的数据迁移。然而，如果从链表的中间或末尾删除了一些条目，将会导致大量没必要的挪动。所以这种桶适合永不或极少缩减的场景。(3) Tree：它用一种二进制搜索树，规模效率远高于列表。列表buckets对于少量的数据项还是高

15、效的，当链表达到较大规模时，其时间复杂度就太大了。树状buckets由RUSHT发展而来，它通过将这些大量的数据项储存到一个二叉树中来解决这个问题。它将定位的时间复杂度由0(n)降低到O(IC)gn),这使得它们更适合管理更大规模的设备或嵌套桶。(4) Straw：这种类型让BUCket所包含的所有item公平的竞争,而不需要遍历。这种算法就像抽签一样，所有的item都有机会被抽中，但是长签被抽中的概率更高。每个签的长度是基于OSD权重基础之上又加入了随机因子参与被计算出来的权重，可以将有限的权重序列变为散列化长度的抽签。这种BUCket是CePh曾默认使用的BUCket,所以它也是经过大规模测试的，稳定性较好。虽然它的查询性能不如1iSt和Tree,但它在控制数据迁移方面是最优的。后续优化之后又出现了StraW2。对比来看，从查询复杂度、添加节点以及删除节点三个维度来看各个a1g类型的优略：类型时间复杂度添加节点删除节点Uniform0(1)PoorPoor1ist0(n)Optima1PoorTree0(1ogn)GoodGoodStraw0(n)BetterBetter从以上各种数据结构类型的三个维度对比来看，StraW在各个维度都比较均衡的类型，也更适合大规模的分布式存储系统，因此通常都会采用Straw来作为Bucket