Ceph Bulestore磁盘空间分配初探

本文作者 / spikehe(何诚)

爱好acg，小甲师兄的首席大弟子~

在大佬中夹缝求生的实习boy

最近跟着小甲师兄优化Ceph块存储缓存，涉及IO映射和磁盘空间分配，想到Ceph Bluestore就是绕过标准文件系统，直接对裸盘空间进行管理的，因此学习了一下以做参考，同时结合源码对Bluestore整体做一个了解。

Ceph存储引擎简介

Ceph整体的存储层框架可以从图1中看到， IO请求在RBD等客户端发出，在Message层统一解析后会被OSD层分发到各个PG，每个PG都拥有一个队列，线程池会对每个队列进行处理。而ObjectStore封装了所有对底层存储引擎的IO操作，存储引擎在整个存储架构的底部，负责空间分配，IO的映射和最终落盘。

图1. Ceph存储架构

Ceph L版之前默认使用FileStore作为后端存储引擎，同时支持kvstore，memstore等，L版之后推荐使用Bluestore。

FileStore构建在文件系统上，采用文件系统常用的写日志方式（FileJoutnal）来保证ACID，在FileStore的写路径中，所有写事务在被FileJournal处理以后都会立即返回。事物每次用ODIRECT和ODSYNC同步写入到journal文件，完成后该事务会被放到FileStore的op queue中。事务通常有若干个写操作组成，进程crash时，journal为OSD recover提供了完备的输入，保障了断点恢复等场景。

FileStore会存在多个thread从op queue里获取op，然后真正apply到文件系统上对应的Object(Buffer IO)。当FileStore将事务落到disk上之后，后续这个Object的读请求才会继续。当FileStore完成一个op后，对应的Journal可以丢弃这部分日志。这种双写的方式极大地耗了磁盘的吞吐量，存在写放大的问题。

图2. FileStore工作流程

而Bluestore抛弃了标准的POSIX文件系统，实现在用户态下使用linux aio直接对裸设备进行I/O操作（Block Device），并且自身实现了一个极简的文件系统BlueFS来支持RocksDB进行空间分配信息等元数据信息的持久化。相对于FileStore，Bluestore不仅避免了写放大问题，也避免了标准文件系统一些额外的开销。

图3. Bluestore架构

Ceph Bluestore IO映射简介

Bluestore中有若干结构体实现：

Onode：代表一个Object，根据min_alloc_size（可配置）逻辑上可划分为若干块；

lextent：Object的逻辑范围；

blob：Onode申请的一组磁盘空间，可以被多个lextent映射；

pextent：一段连续的物理磁盘空间，默认最小单位为4K字节，一个blob的磁盘空间可以由多段不连续的pextent组成。

图4. IO映射

以写操作举例，写操作经过上层处理后传递到Bluestore::queue_transactions函数中，在一个Object的操作范围内，经过调用最终有_do_write来处理：

其中length和offset是相对于一个Object逻辑范围的偏移量。

根据min_alloc_size的大小，一次IO对齐后可分为大写和小写，分别由_do_write_big和_do_write_small来处理，后续流程如下：

图5. 写操作流程

Ceph Bluestore Allocator分析

如IO流程所示，Bluestore需要新的空间分配时都需要通过_do_alloc_write函数调用Allocator类进行空间分配。

Allocator只负责在内存中将空闲空间标记为已分配，不关心磁盘空间使用情况的持久化，BlueFS将其记录在文件系统的日志中，Bluestore通过FreelistManager将其存储在k/v中，并在对象metadata中记录对象的磁盘空间信息。

Ceph N版本之前，Allocator的实现有StupidAllocator和BitmapAllocator，StupidAllocator为默认配置，而BitmapAllocator性能不佳，N版后有了新版本的BitmapAllocator，新版代码的作者提交时有一份跟Stupid Allocator详细的性能对比，具体可见：

https://docs.google.com/presentation/d/1_1Otkgv76fbCU2Zogjz748sEAG-1Nfiidbb6mgTON-A/edit#slide=id.p，下文将对三种Allocator的实现略作总结。

Stupid Allocator

Stupid Allocator基于区间树实现，空间分配通过增删改树节点实现；

老版Bitmap Allocator

位图管理磁盘空间的基本思路是，使用一个bit位的两种状态0或者1来表示一个空闲或已分配两种状态。

老版BitmapAllocator结合树形结构和位图法，其中有几个变量设置需要了解：一个zone是单个线程单次操作可以请求的，最大连续可分配空间，一个zone多个bmapEntry，一个bmapEntry为64位8字节；

图6. 老版BitMapAllocator类图

按默认配置：

• Block 大小为4K字节的一段磁盘空间；

• BmapEntry 为一长整型，整型的每个bit位代表一个Block；

• Zone 一组空间上连续的Block的集合，Block数目默认为1024；

• Span 一组空间上连续的Zone的集合，Zone数目默认为1024；

osd启动时通过加载kv中的记录，可以在内存中构造以下的树结构：

图7. 老版BitMapAllocator树结构

树中每个节点都会统计自己子树中包含的空闲磁盘空间和已分配磁盘空间，这在分配连续大块的磁盘空间时可以跳过空间不足的子树，快速定位到剩余空间能够满足要求的子树，从而提高分配效率。

但是老版Bitmap Allocator树形结构的实现中，各个节点空间都单独开辟，使用指针连接，用的是离散的内存空间。

新版Bitmap Allocator

新版的BitmapAllocator相对于旧版，避免了在内存中使用指针和树形结构，尽量使用vector连续内存空间，并充分利用了intel 64位机器CPU缓存的特性，在初始化时L0~L2共3级位图就占用了固定的内存大小。

以下翻译了一下新版BitmapAllocator作者的部分描述：

• Allocator尝试将数据与英特尔的X86L1 cpu缓存线对齐，以最大限度地提高性能；

• Allocator尝试在整个64位值上操作，而不是在可能的情况下操作单个位。L1 / L2层提供的树状数据结构可以更快地查找；

• Allocator未来可以支持多个并发分配请求处理，例如，通过独立保护子树（每L2位锁定（或一组位），尚未实现；

• Allocator具有固定的内存消耗。

• 这种方法可能无法很好地优化连续分配。最坏的情况下，可能需要完整枚举L0位图，但是，这种情况很少。

图8. 新版BitMapAllocator设计

 理解CPU缓存

要理解新版Bitmap Allocator为什么能提高性能，可以先理解下CPU缓存。以下摘自维基百科：

“CPU高速缓存是用于减少处理器访问内存所需平均时间的部件。在金字塔式存储体系中它位于自顶向下的第二层，仅次于CPU寄存器。其容量远小于内存，但速度却可以接近处理器的频率。

缓存之所以有效，主要是因为程序运行时对内存的访问呈现局部性（Locality）特征。这种局部性既包括空间局部性（Spatial Locality），也包括时间局部性（Temporal Locality）。有效利用这种局部性，缓存可以达到极高的命中率。

程序员通常无法直接干预对缓存的操作，但是可以根据缓存的特点对程序代码实施特定优化，从而更好地利用缓存。”

linux下可以通过getconf命令查看cpu cache相关的信息

现在intel 64位的机器通常有三级缓存，通过getconf我们可以看到：

L1指令缓存/数据缓存大小 32768/1024 = 32 KB

L2大小 262144/1024 = 256KB

L3大小 15728640/1024/1024 = 15M

CACHE_LINE大小 64 Bytes

CPU缓存与主存交换数据每次大小是固定的，我们称其为CPU Cache Line（缓存行），在64位系统下通常是64字节，即每次CPU 把内存的数据载入 cache 时，会把临近的共 64 Byte 的数据也一同载入。

可以利用CPU cacheline来提高程序性能，提高缓存命中率，写出对cpu友好的程序（Mechanical Sympathy）。

查看程序缓存命中率：

这篇文章举了若干程序运行实例，很好的体现了cpu cache的机制；

http://igoro.com/archive/gallery-of-processor-cache-effects/。

另外有一个直观的例子来体现CPU缓存是如何影响程序效率：

Loop2的运行时间和缓存命中率是显著优于loop1的。Loop1遍历内部循环中数组中的“j”(外部)行，对于每次通过内部循环的行，缓存行都将被刷新来加载一行地址，而loop2按相邻地址顺序遍历，充分利用了缓存行的空间局部性。

新版的CephBluestore BitmapAllocator，根据CPU缓存的特点，通过使用连续内存空间，一个线程一次操作在一个缓存行内，避免缓存伪共享等方式提高了程序执行效率。