Ceph的原理与实现

作者: 李佶澳   转载请保留:原文地址   更新时间:2017/10/28 12:31:51

说明

Ceph分布式文件系统的原理与实现

CRUSH算法

CRUSH算法是Ceph对象存储的核心, 决定了每一个对象(Object)的存放位置。当需要存放一个Object时,只需要知道Object的id、集群架构图和存放策略,就可以计算出应该存放在哪个OSD上。因此Ceph的元数据不需要包含位置信息,每个Client都可以自己计算出对应的OSD,大大减少了对元数据的请求。

CRUSH算法将集群架构图看作Buckets和Devices组成的树形结构,每个Bucket包含多个Device,Bucket也可以包含其它类型的Bucket。一共有四种类型的Buckte,使用四种定位算法。

Uniform Buckets 使用哈希算法,定位速度快O(1),但是当增加或者移除Devices时,需要对数据进行重新分布,适用于Devices数量固定的情况。

List Buckets 将Devices连接成链表,利用当前Device的权重与剩余Devices的权重和的关系选择Device,定位速度O(n)。增加Device时,对数据分布的影响最少,但是删除Devices需要对数据重新分布,适用于Devices数目较少且只增加不减少的情况。

在List Buckets中,利用的是当前Device的权重和在它后面的Device的权重和的关系。增加Device时,只要将新增的Device插入链表头部,就不会改变后续Device链表中的权重关系,因此在重新进行数据分布时,只会存在需要从原有Device移动到新的Device的数据,数据的移动量是最少的。但是在删除Device时,会改变整个链表中的权重关系,导致大量的数据重新分布。

Tree Buckets 二叉树中的内部节点记录了左孩子和右孩子的权重,Devices作为二叉树的叶子节点,定位速度O(log n)。增加或减少Device时,对数据分布的影响都较小,但不是最优的,适用于Devices数目较多且经常抖动的情况。

Straw Buckets 每个Object为所有的Device分配一个签,选择签最长的Device,定位速度O(n)。增加或减少Device时,对数据分布的影响都是最优的,使用与Devices数目较少且经常抖动的情况。

在Straw Buckets中,当增加Device时,只会将数据移动到新的Device上,当删除Device时,只会将数据移动到别的Device上,不存在的额外的数据移动。

通过集群架构的不同层级选择适合各自情况Bucket类型,可以得到一个好的整体结果。例如, Root –> 机柜列 –> 机柜 –> 存储 -> 设备,以机柜列为单位进行扩容或者收缩。机柜列收缩或扩容时,要尽可能减少数据移动,所以Root设置为Straw Bucket,每个机柜列的机柜数目是固定不变的,所以机柜列的设置为Uniform Bucket。

Ceph中Crush的配置方法:http://ceph.com/docs/master/rados/operations/crush-map/

在Crush配置中指定了设备的类型、设备的隶属关系、选取算法和各种选择规则。

RADOS

RADOS是使用CRUSH算法的分布式对象存储。由OSD和MON组成,OSD承担数据的存储、备份以及恢复,MON保证集群架构图与实际情况相符。RADOS的特点之一就是数据的备份、同步以及恢复等都由OSD自发的完成。

MON

RADOS中OSD独自管理数据的能力是建立在CRUSH算法上的, CRUSH算法又是建立在crushmap(包含OSD的数量、组织结构以及存储策略)上的。因此拥有一份最新的crushmap, 对OSD是至关重要的,否则OSD无法确定隶属同一个PG的OSDs,也就无法完成数据的备份、同步等操作。

RADOS中使用一个由MON组成的小集群来生成最新的crushmap。当增/减OSD、修改OSD组织结构、修改存放策略或者发现OSD失效时,更新请求被发送到MON集群, MON生成一份新的crushmap。同时MON集群也对外提供crushmap的访问服务,其它节点可以从MON集群中获取一份最新的crushmap。MON集群中采用Lease机制确保每个MON对外提供的crushmap的一致性,采用Paxos协议选举出一个Leader, 由Leader负责生成新的crushmap。

另外, OSD节点之间互相通信的时候会比较各自拥有的crushmap的epoch, 用最新的crushmap替换旧的crushmap。

当client要从OSD中读取Object时, 如果client中还没有crushmap: client首先从MON集群中读取一份最新的crushmap, 然后计算出存放该Object的PG对应的OSDs, 然后client与目标OSD比较各自的crushmap的epoch, 同步到最新的crushmap。如果client中已经有crushmap,在和OSD通信时,如果OSD的crushmap版本更新, 那么更新client的crushmap。如果client和OSD的crushmap版本一致了,但都不是最新的, 使用旧的crushmap计算出的OSD上可能没有存放要访问的Object, 导致操作失败, 这时候client从Mon集群读取最新的crushmap。

PG

存储Object时,Object首先通过哈希函数被映射到一个PG(placement group), 这个PG又被通过CRUSH算法映射到一组OSD,Object就被存放在PG对应的这组OSD中。

使用PG的第一个好处: PG的数量远远小于Object的数量,可以通过技术手段使从PG到OSD映射开销小于从Object直接映射到OSD的开销。使用PG的第二个好处: PG的数量大于OSD的数量,可以使OSD的负载更加均衡。PG的数量不能太多,否则每个OSD上承担的PG数目太多,会使OSD疲于与PG内其他OSD通信,CEPH文档上推荐每个OSD承担50~100个PG。

Ceph中PG的设置方法:http://ceph.com/docs/master/rados/operations/placement-groups/

数据备份

RADOS提供了三种数据备份模式: Primary-copy, Chain, Splay。

Primary-copy: 写数据时首先写入到Primary, 然后由Primary同时更新备份。读取时,从Primary读取。

Chain: OSDs被看作链表, 第一个OSD作为Primary, 写数据时从链表头开始顺次写入, 然后按照顺序依次更新备份。读取数据时,从链表尾读取。

Splay: 写数据时首先写到Primary, 然后由Primary同时更新备份。读取时,从最后一个被更新的OSD上读取。

Chain和Splay模式将写入和读取分离,减少了Primary的负担。 Primary-copy中Primary承担所有工作。 Chain将备份的负担均分到各个OSD上,但是更新速度慢。 Splay模式具有Primary-copy的更新速度, 同时将读取工作从Primary上分离出去。

在考虑选取哪一种备份模式时,主要考虑写入时延和OSD的网络IO两个因素。如果OSD的网络IO足够,对写入时延要求高,采用Primary-copy或者Splay模式。如果对写入时延要求不高,OSD的网络IO不足,采用Chain模式。

PG成员变更

当PG成员变更时(例如OSD故障、策略变化等), 新的Primary首先与原先的每一个成员通信, 原先的OSD停止当前PG的I/O操作。

故障检测

PG成员之间保持心跳,其它的OSD发现如果某个OSD的心跳消失后,上报给MON集群。

一个OSD如果没有收到其它成员的心跳(例如网络分裂等原因),就停止对外提供这个PG的读取服务,防止Client读取到错误的数据。

数据恢复和数据迁移

OSD故障会导致crushmap变更,OSD拓扑或者策略的改变也会导致crushmap变更,因此数据恢复和数据迁移使用相同的机制,都是由crushmap的变更驱动的。

每个OSD都存放一份PG操作日志,记录当前PG的状态。当OSD收到crushmap的更新时,OSD上承担的PG都要进行一次Peer。OSD向隶属的每个PG的Primary OSD发送操作日志, 如果OSD是Primary, 则像成员请求操作日志。Primary得到所有操作日志后,计算出该PG中应该包含的内容,并分发给每个成员。然后每个成员检查自己保存的数据是否与Primary计算出的结果一致,如果不一致,Primary主导进行查漏补全,是所有成员的存放的数据一致。

成员间数据同步时,由Primary主导的好处时,可以减少磁盘IO。例如如果有3成员A、B、C都要向D请求同一个Object。如果A、B、C独自向D请求,那么D最多需要进行3次磁盘操作。如果由Primary主导,可以控制A、B、C在同一时间段获取Object,那么只有第一次请求Object时需要进行一次磁盘操作,后续紧邻的对Object的请求直接从内存中读取。

并发读写

RADOS中对Object的并发读写遵循POSIX标准, OSD承担串行化的任务[4]。

Metadata

Ceph将元数据的管理和数据的存储分离开了。RADOS是一个单纯的对象存储。文件路径、文件名称以及读写权限管理等元数据的管理由MDS集群(注意不是RADOS中的MON集群)进行管理。

得益于Crush算法,MDS集群不需要记录文件的实际存放位置,只需记录文件对应的inode number和stripe number就可以通过Crush算法计算出文件存放在哪些OSD上。

每个MDS的操作日志都被及时存放到RADOS中, MDS故障时, 可以根据日志文件进行恢复。

元数据按照目录的树状结构分派到MDS上, 然后在运行中根据元数据的使用热度,调整元数据的存储位置,既考虑到了对元数据请求的局部性特点,又实现了整个MDS集群负载的均衡。

例如A目录下的所有文件的元数据都存储在MDS0上, 当发现A目录的元数据请求非常频繁时, 将A目录的元数据复制一份到MDS1上, 分担MDS0的压力。如果A目录下的目录数特别多,而且更新操作频繁,那么以丢失局部性为代价,将A目录下的目录根据哈希结果分布到MDS集群中。

参考

  1. CRUSH: Controlled,Scalable,Decentralized Placement of Replicated Data
  2. RADOS A Scalable, Reliable Storage Service for Petabyte-scale
  3. Dynamic Metadata Management for Petabyte-scale File Systems
  4. Ceph: A Scalable, High-Performance Distributed File System

本文原创首发于网站:www.lijiaocn.com

QQ交流群

区块链实践互助QQ群:576555864

Kubernetes实践互助QQ群:947371129

Prometheus实践互助QQ群:952461804

Kong/Envoy实践互助QQ群:952503851

Ansible实践互助QQ群:955105412

Copyright @2011-2019 All rights reserved. 转载请添加原文连接,合作请加微信lijiaocn或者发送邮件: [email protected],备注网站合作 友情链接: lijiaocn github.com