CubeFS技术揭秘 ｜ 元数据子系统设计
作者简介：TangZhixiang, CubeFS maintainer之一，目前就职于OPPO，负责纠删码系统。
引言
前面CubeFS存储技术揭秘-元数据管理【1】的文章中介绍了CubeFS元数据系统的设计理念，文章中有提到传统的文件系统存在元数据节点单点的瓶颈问题，CubeFS可扩展的元数据设计有效的解决单点瓶颈问题。本文将从更详细的角度介绍元数据系统在可靠性、可扩展性以及访问性能的一些实现和思考。阅读本篇文章之前，你需要了解CubeFS的系统架构，以及各个关键组件的职责和系统的名词概念。
元数据系统设计
这一章会介绍CubeFS的元数据服务的设计思想，你可以了解到以下信息：
- CubeFS的可扩展性元数据服务的设计原理
- CubeFS元数据服务的关键数据结构
- CubeFS元数据可靠性的实现方案
元数据分片
每个挂载的文件系统对应一个volume，一个volume代表一个虚拟文件系统，用户所有的文件元数据信息都存储在元数据分片(meta partition，简称mp)中，CubeFS的元数据采用range方式进行分片，每个mp负责一段范围的inode (inode用于标识文件和目录，每个文件或目录在文件系统中都有一个唯一的inode），最后一个mp可以支持分裂，这是CubeFS支持元数据水平扩展的关键设计。
下面展示mp的分裂过程，每个volume创建会初始化分配3个mp，假设每个mp负责1000个inode（生产环境每个mp负责1600万个inode），最后一个mp会负责的inode。
集群某个MetaNode节点内存使用率达到阈值(一般设定为内存总量的75%)，Master组件的后台任务会定期检查每个volume的最后一个mp, 如果最后mp落在内存使用率超过阈值的MetaNode上、最后一个mp所在的MetaNode是只读状态、最后一个mp负责的inode分配到一定数量等场景，Master就会将最后一个mp分裂成两个mp；假设某个时刻集群的mp分布如下图所示：
分裂以后的结果如下图所示，原本mp3负责[2001,+∞)的inode，分裂以后会新创建一个mp4，新的mp4负责[3001,+∞）范围的inode分配，而原来的mp3就负责[2001,3000]的inode。新创建的mp落在那个MetaNode上，在负载均衡部分详细说明。
值得说明的是，inode的分配过程可以理解为轮询策略。对于一个volume，它包含多个mp；客户端每当创建一个新的文件时，客户端会轮询请求到不同的mp上分配inode。假设先后创建两个文件A、B，文件A会在mp1上分配编号为100的inode，而文件B会在mp2上分配编号为1100的inode。如果一个mp上所管理的inode已全部消耗完，则自动切换为只读状态。
数据结构
CubeFS的元数据采用BTree存储，每个mp中维护了两颗BTree，分别是inodeTree和DentryTree。BTree的实现采用谷歌开源的golang版本【2】，该版本BTree写入时候会采用COW的方式来提升数据写入性能，并使用回收列表来分配新的树节点，以减少内存开销。如果您想深入了解其他特性，可以查看源代码。
其中inodeTree的示意图如下，使用inode id作为BTree的索引。
为方便读者理解，这里展示的是下图所示的结构。实际上，BTree采用slice实现，不需要使用指针。此外，inode id是inodeInfo结构体中的一个字段。
每个文件会对应唯一的inode，inode记录了文件的详细元数据，包括inode id、文件类型、创建时间等。
下面的inodeInfo提供了每个文件的详细元数据信息，相关的注释已经做了说明。CubeFS支持多副本和纠删码两种存储，其中Extents表示文件在多副本中的位置信息，而ObjExtents表示文件在纠删码引擎中的位置信息
type inodeInfo struct {
sync.RWMutex
inode uint64 // inode id
Type uint32 // 文件的类型和权限
Uid uint32 // 用户id
Gid uint32 // 组id
Size uint64 // 文件大小
Generation uint64 // 版本号，每次修改会增加
CreateTime int64 // 创建时间
AccessTime int64 // 访问时间
ModifyTime int64 // 修改时间
LinkTarget []byte // 保存软链接对应源文件的路径名
NLink uint32 // 硬链接的数量
Flag int32 // 标记是否可以删除
Extents *SortedExtents // 文件在三副本的位置信息
ObjExtents *SortedObjExtents // 文件纠删码的位置信息
}
Extents 是在多副本系统中的位置信息，是一个[]ExtentKey的数组，记录文件在多个不同Extent(存储文件数据的结构,在DataNode节点上，由DP管理，详细可以阅读副本子系统文章)的位置信息，一个文件会分片写入不同的Extent里面。
// ExtentKey defines the extent key struct.
type ExtentKey struct {
FileOffset uint64 // 该分片文件中的偏移量
PartitionId uint64 // 数据分片的id
ExtentId uint64 // extent的id
ExtentOffset uint64 // 该分片在extent中位置
Size uint32 // 文件大小
CRC uint32 // crc校验值
}
ObjExtents 是在纠删码系统中的位置信息，是[]ObjExtentKey 的数组，同样一个文件也会切成多个blob(纠删码系统定义的编码对象大小)写入纠删码系统，所以会有多个ObjExtentKey 信息。
// ExtentKey defines the extent key struct.
type ObjExtentKey struct {
Cid uint64 // 纠删码集群的clusterId，纠删码支持多个clusterid部署
CodeMode uint8 // 纠删码编码模式
BlobSize uint32 // 纠删码系统中每个blob的大小
BlobsLen uint32 // bid的数量，就是blobs的长度
Size uint64 // 文件大小
Blobs []Blob // 每个bid在纠删码中的位置信息，这里不展开介绍了
FileOffset uint64 // 文件中的偏移量
Crc uint32 // crc校验值
}
每个dentry代表一个目录项，其中包含了父目录的inode和该文件（或目录）的名称等信息。dentry的详细结构如下
// Dentry defines the dentry struct.
type Dentry struct {
ParentId uint64 // 父目录的的inode
Name string // 当前目录项的名字
inode uint64 // 当前文件的inode
Type uint32 // 文件类型和权限
}
DentryTree的主要作用是加速文件查询。它的索引由parentId和name一起构成。查询时，先比较parentId，如果相同，则继续比较name。每个文件的dentry保存在父目录inode所在的分区，这样一个目录下的所有子文件的dentry信息都会保存在同一个mp中。这种设计考虑了一定的亲和性，查询目录下的文件会集中在一个mp中，而不需要访问整个集群的所有mp。 
思考：
这里大家也可以思考能不能使用B+tree来保存InodeTree和DentryTree
可靠性
多个mp会分配到三个MetaNode节点上，通过Raft算法来保证元数据的可靠性。采用了Mutil-Raft算法来降低节点之间的心跳开销。每个MetaNode节点上会存在多个mp，选举一个主节点来处理读写请求。
每五分钟，MP会进行一次快照以持久化元数据。每个快照都会生成一个新文件，并在无异常情况下替换旧文件 (但为了防止数据损坏，旧文件会先做备份)。两次快照操作之间的所有元数据变更都会记录在Raft的WAL日志中，以保证在节点故障后可以快速恢复到故障时刻的状态。快照恢复过程如下：在故障发生后，首先加载前一个快照时刻的数据，然后根据apply index值重放WAL日志中的日志，以恢复内存中的数据。
注意：这里的快照不是Raft的快照，而是单个mp自身的快照 快照文件记录的详细信息如下(文章基于V3.3.0以前版本，V3.3.0以后快照增加了事务相关内容)：
- apply: 表示 Raft的最大的apply index 值
- inode：文件元数据信息，采用BTree结构
- dentry： 文件目录项dentry信息，采用BTree结构
- cursor：当前mp已经分配出去最大的inode ID
- extent：扩展属性，目前用于对象存储，采用BTree结构
- multipart：存储对象存储分片上传信息，采用BTree结构
- .sign：是dentry、extend、inode、multipart的crc32值，用做校验。
负载均衡
mp均衡创建
为保证每个MetaNode上的mp数量均衡，新创建的mp会选择一个合适的MetaNode节点。选择MetaNode的策略基于节点的权重分配，权重值与MetaNode的剩余未使用内存大小呈正相关，剩余内存越大，权重越大；此外，选取过程还增加了一定的随机策略，以避免新扩容的MetaNode在短时间内被大量分配mp，该策略可有效提高系统的稳定性和可靠性。
分配策略
- 先选择zone，如果volume不跨zone，则zoneNum =1，否则如果集群当前的zone数目小于副本数3，则zoneNum =2，否则zoneNum = 3，这里zone可以理解为可用区；
- 然后从zone中选择nodeset，nodeset是一组节点的集合，可以作故障域区分；
- 获取nodeset里面所有可写的MetaNodes，要求MetaNode处于active状态（MetaNode会定期向master做心跳，超过心跳间隔时间未上报会被设置为false，默认是18s）、内存使用率未超过0.75、mp的数量不超过阈值并且不是只读；
- 筛选MetaNodes所有节点中，可用内存的最大值作为maxTotal，这个作为基准值；
- 每个节点初始化会带一个InitCarry，这个[0.0 - 1.0]之间；
- 每个节点有个weight值，内存未使用节点的weight是1，已经使用weight=（maxTotal-used）/maxTotal；
- 最后每个节点carry=InitCarry+weight，按照carry值从大到小排列；
- 选择carry值最大的几个Metanode返回，被选中的MetaNode的carry值会--，降低下次被选中概率。 随着集群规模扩大，会不断有新MetaNode节点扩容进来，而旧MetaNode节点上的mp数量一定比新MetaNode上的mp数量多。当mp倾斜严重时，可通过mp下线策略，将旧节点上面的mp下线，系统会重新创建新的mp副本，新的mp副本大概率会分配到新扩容的MetaNode节点。
主mp均衡分布
前面说过每个mp会有三个副本，三副本会通过 Raft 协议选择一个leader mp，leader mp会承担文件的读写请求（对一致性要求不高场景可开启follower read），CubeFS 的Raft 采用lease read的方式优化读请求，来减少每次readIndex读产生的开销。
所有读写请求都会集中到leader mp上，这意味着在一个Metanode节点上，若leader mp的数量越多，该节点承担的读写压力越大。假设某时刻集群中的mp分片分布如下：MetaNode1有3个主mp，而MetaNode3和MetaNode4上没有主mp，这将导致多个MetaNode间负载不均。
通过主动均衡策略，可将leader mp均衡分布到不同节点。正常情况下Raft组的leader mp在集群MetaNode多个节点间是均衡的，但随着MetaNode节点由于各种原因（进程启停、负载过高、硬件故障等，可能导致leader mp在集群中的分布逐渐倾斜；通过主动均衡机制，可有效应对应Leader mp分布失衡导致的集群稳定性问题。
小结
本章介绍了CubeFS的元数据设计的思想，通过分裂提供元数据的扩展特性，此外还介绍元数据的详细数据结构以及如何通过快照和 Raft 来保证元数据的可靠性。相信通过本章的介绍你会对CubeFS的元数据系统有更深的理解。
文件访问的关键流程
假设挂载的路径为 CubeFS/mnt ，初始化volume会分配3个mp，这里假设每个mp负责1000个inode。初始化会创建一个根目录“/”, 开始会随机选择一个mp写入，这里假设选择的是mp1，对应会分配inode :1。每次创建新文件，客户端会维护一个自增的epoch值，每次写入epoch会自增，通过%count（mp）来选择mp分配inode。如果进一步创建目录A就好在mp2上分配inode：1001，创建目录B就会在mp3上分配inode:2001。
如果按照【目录A、目录B、file1、目录C、file2、file3、file4】的顺序创建文件，最终的inode的分布情况如下。
创建文件
现在需要在目录/A/下面创建一个新文件file5,核心流程如下：
- fuse客户端启动后会定期拉取volume下面mp的信息，包括每个mp负责的inode范围、mp对应MetaNode的成员和ip地址。
- 根目录的inode默认为1，客户端根据每个mp负责的inode范围，可以快速定位inode:1落在mp1上。在mp1中DentryTree记录{ParentId：1，Name:"A"，inode:1001}的索引可以快速找到目录A的inode值为1001。客户端会缓存已经查找过的Dentry值以便下次快速定位。
- 在mp2中查找/A/file5是否存在，mp2的DentryTree没有记录{ParentId：1001，Name:"file5"}的索引，此时会返回一个文件不存在的错误。
- 客户端请求创建一个新的inode给file5，根据轮询策略这个请求会发送给mp3，mp3会创建一个inode为2003的文件元数据，并且在保存在内存的Inode B-Tree中。
- inode创建成功后，会在file5的父目录A对应mp中插入一条dentry记录，如果dentry插入失败，会同步删除上一次创建的inode，保证操作的原子性。
最终新的创建的inode和dentry会插入到对应mp的BTree中。
读取文件
假设需要读文件/A/file5，读文件流程和创建文件流程一致，关键流程如下：
- 从根目录开始查找file5的父目录A，目录A对应dentry已经在创建file5的流程里已经缓存到客户端，可以直接找到目录A在mp2上
- 在mp2中找到file5对应dentry信息{ParentId:1001,Name:"file5",Inode:2003}
- 根据客户端缓存的mp信息，可以快速定位inode：2003在mp3上
- 会创建一个Streamer结构，从mp3获取文件最新的元数据信息，并更新到Streamer的cache缓存中，根据文件元数据获取文件数据存储的位置信息ExtentKey或者ObjExtentKey，下图假设file5的数据存储在DataNode1的dp1。
文件列表
如果需要获取目录A下面的文件列表，元数据访问的关键流程如下：
- 从根目录/开始找到目录A，由于根目录的inode为1，客户端又保存了每个mp管理的inode信息，可以快速在mp1中找到目录A对应的dentry信息{ParentId：1，Name:"A"，inode:1001}
- 在mp2中列举目录A下面的所有文件信息，因为mp2的dentryTree记录了所有子文件的dentry信息,目录C的dentry{ParentId：1001，Name:"C"，inode:1002}，file2的dentry{ParentId：1001，Name:"file4"，inode:1003}，file5的dentry{ParentId：1001，Name:"C"，inode:2003}，
- 分别访问各个子文件所在的mp，获取对应的元数据信息；例如根据目录C的inode:1002和file4的inode:1003在mp2中获取目录C和file4的详细元数据，根据file5的inode:2003在mp3上获取file5的详细元数据 下图展示的mp2中的dentryTree的结构，根据inode找到对应mp流程和读取文件流程类似，这是不再画图展示。
删除文件
假设需要删除刚才创建的/A/file5,关键流程如下：
- 同样从根目录开始查找，找到文件对应父目录，这里因为客户端会缓存目录A的dentry信息，所以能够直接找到目录的A所在的mp
- 在mp2中删除file5对应的dentry值{ParentId:1001,Name:"file5",Inode:2003}
- 向file5所在的mp3发起inode的删除，mp3通过raft达成一致性协议后，对应inode的NLink--
- 如果inode的NLink值为0，标准inode为Delete状态，并且加入每个mp的freeList列表，后台用于异步释放文件的内容数据
- mp会启动一个后台协程，定期清理freeList里面inode的数据
- 每次从freeList中取出一批inode，执行删除流程，文件数据的删除流程请阅读CubeFS源码解读-副本子系统【3】
- 执行删除前，将删除的inode号写入mp根目录下的INODE_DEL文件进行持久化(做记录)
- 将各个inode的ExtentKey按照DP做聚合，以此来减少发送给每个DP的删除请求。
元数据节点存储实例展示
MetaNode节点存储的目录结构,包括两个大目录meta和Raft，meta中保存每个MetaNode上面所有mp对应的元数据信息。而Raft则记录每个mp对应的Raft信息。其中expired_patition表示被迁移到其他MetaNode的mp，会有后台任务定期清理expired_partition_*对应的mp目录。expired_raft_*对应是V3.3.0版本以后增加的，V3.3.0版本之前可能无法看到。
├── meta
│ ├── constcfg
│ ├── expired_partition_357 // 被迁移到其他MetaNode的partition
│ ├── expired_partition_358
│ ├── partition_308
│ ├── partition_309
│ ├── partition_310
│ ├── partition_314
└── Raft
├── expired_raft_357
├── expired_raft_358
├── 308
├── 309
├── 310
├── 314
meta目录
constcfg
保存 Raft 的监听、复制和心跳端口信息，采用mutil- Raft ，MetaNode上面所有mp通过一个统一的端口发送心跳
{"listen":"17210"," Raft ReplicaPort":"17240"," Raft HeartbetPort":"17230"}
partition
每个mp对应元数据目录的记录如下：
├── EXTENT_DEL_V2_0
├── inode_DEL
├── .snapshot
├── .snapshot_backup
├── meta
├── .meta
└── snapshot
├── apply
├── dentry
├── extend
├── inode
└── multipart
└── .sign
inode_DEL 记录删除的inode号
EXTENT_DEL_V2_0
记录删除的Extent信息，可能是ExtentKey 或者ObjExtentKey 。
meta
meta记录当前mp的元数据，主要记录mp管理的inode、所归属的volume信息、以及mp对应副本组的节点信息
{
"end": 9223372036854775807,//最大inode值，最后一个partition取无限大
"partition_id": 418,
"partition_type": 0,
"peers": [
{
"addr": "127.0.0.1:17210",
"id": 4
},
{
"addr": "127.0.0.2:17210",
"id": 8
},
{
"addr": "127.0.0.3:17210",
"id": 116
}
],
"start": 33554433, // 最小的inode值
"vol_name": "smux-test"
}
start-end是一段inode区间，同一个volume里面的inode对应mp是连续的，下图展示是某个卷上面三个mp负责的元数据信息。 
snapshot
快照保存的一些信息
- apply : 70466|33554433,| 号前面表示 Raft 的最大的apply index 值，**|**后面是cursor值，表示已经分配出去的inode id。
- 如果cursor大于meta的最后end的值，表示当前mp的inode用尽，会切只读
- cursor会定期（默认一分钟）做一次持久化, 后续版本会优化成和 Raft 快照一起保存
- dentry ：dentry信息，采用BTree结构
- inode：inode信息，采用BTree结构
- extend：扩展属性，目前用于对象存储，采用BTree结构
- multipart：对象存储分片上传，采用BTree结构
- .sign：是dentry、extend、inode、multipart的crc32值，用做校验。
├── apply //一个实例70466|33554433
├── dentry
├── extend
├── inode
└── multipart
└── .sign // 一个实例 206325109 0 3523407757 3523407757
Raft目录
保存 Raft 元数据和 WAL 日志
- META是保存term、vote、commit、snapTerm、snapIndex等信息
.
├── 0000000000000001-0000000000000001.log
└── META
参考文献
【2】谷歌开源版本BTree