Ceph的原理与实现
目录
说明
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集群中。
参考
- CRUSH: Controlled,Scalable,Decentralized Placement of Replicated Data
- RADOS A Scalable, Reliable Storage Service for Petabyte-scale
- Dynamic Metadata Management for Petabyte-scale File Systems
- Ceph: A Scalable, High-Performance Distributed File System
