CEPH VERSION： Quincy 17.2.6
上一篇分析了BlueStore的各工作线程，在提交线程中经历了一个比较复杂且重要的过程_txc_add_transaction，它完成了从上层ObjectStore::Transaction到BlueStore::TransContext的转换，转换过程中，对于数据变更类的Op，进行了空间的分配和回收操作，这些操作作为kv事务的一部分被原子提交到RocksDB。
本篇来探究这些数据分配、释放过程的细节，探究Allocator的演变过程，理解开发者们在这个问题上所做的诸多努力。
BlueStore中，空间管理分为两个部分：FreelistManager和Allocator，后续简称为fm和alloc。fm用于表示空闲空间的存储结构以及分配、释放空间的存储数据变更策略，它更贴近于空闲空间的物理存储层面；alloc则侧重于内存表示，它着重于空闲空间快速查找与标记的时间复杂度，和在内存占用的空间复杂度上寻求平衡。
在BlueFS中也使用Allocator，但不使用fm，这是没有办法的事情，fm依赖rocksdb保存其freelist信息，BlueFS作为rocksdb的载体，自然不能再依赖fm，否则就形成了环形依赖，所以BlueFS有自己的空闲空间信息存盘机制。
fm一直以来都使用一个实现BitmapFreelistManager，新的版本增加了ZonedFreelistManager，用于支持SMR Device。由于ZonedFreelistManager比较特殊，下面着重讨论更普遍的BitmapFreelistManager。
BlueStore::_open_fm函数调用会触发fm的创建或加载，若是创建流程，函数第一个参数会传入一个KeyValueDB::Transaction t事务对象，fm的一系列初始化kv将附加到此事务，附加的kv如下：
| prefix db CF | Key | Value | 说明 |
|---|---|---|---|
| S | freelist_type | bitmap或null或zoned | 记录所使用的的fm类型 |
| B | bytes_per_block | 512或4K | 设备的Block Size |
| B | blocks_per_key | 默认128 | 每个bitmap key对应多少个block，意味着每个value多少个bit,每个bit对应一个block |
| B | blocks | 总block数量 | 总block数量 |
| B | size | 设备总空间 | 设备总空间 |
| b | 0 | 二进制总128bit 11000000...000 | Block Size以4K为例 预留8K给label + superblock |
- S - BlueStore的全局元数据prefix
- B - fm的元数据prefix
- b - fm的bitmap记录prefix
伴随着fm->allocate的新空间分配，会产生越来越多的b前缀的kv记录
伴随着fm->release的释放操作，原先某个n前缀记录中，Value对应的bit被翻转为0
而fm->allocate的重新分配，又将这些bit翻转为1
所以，allocate和release操作就被统一了，二者都是将offset~length这个区间涉及的对应bit做位翻转(xor)即可。原先没有记录的位置，默认为全0 bit，首次被分配时产生对应kv。
allocate和release操作并不直接修改DB中的kv，而是将kv变更附加到传入的KeyValueDB::Transaction t事务，伴随其余的kv变更一起做原子提交，所以，fm仅仅是提供了allocate和release的kv变更策略。
注意，在新的版本，除了前面创建fm时会将fm meta写到RocksDB外，还会在block设备上的0-4K位置，以bdev label形式记录一份，当然fm的meta只是bdev label的一部分kv。这样做相当于在不同设备不同位置做了super meta的双重备份。
在了解了fm之后，再来看Allocator的实现
最早使用StupidAllocator，它使用10个bin组成free vector，每个bin是一个interval_set，其中管理着一个btree。每一层的bin管理连续N个free Block的集合，跟Linux的Slab管理有些相似。free[0]的btree中，管理着1个Block的空闲区间；free[1]管理着2个Block的空闲空间；free[2]管理4个Block的空间；...;free[8]管理着256个Block的空间，free[9]则管理着512个及以上的Block的空间。
当需要分配空间时，根据待分配的len找到合适的bin予以分配，分配后可能引起某些区间长度减少，从而需要移动到更低的bin。移动到更低的bin有可能引起合并，合并后又可能移动到更高的bin，然后有可能再次引起合并...
释放空间也是如此，有可能引起分区合并，从而移动到新的bin，移动又可能引发合并，再次移动...
所以，StupidAllocator对于碎片化严重的情况，会有些尴尬，分配、释放可能引起很多额外的操作，性能会变差。
N版本实现的新版BitmapAllocator，详见 https://github.com/ceph/ceph/pull/21825
这个版本的BitmapAllocator相对于老版本，大大提高了空闲空间的lookup效率，其原因在于它做了三层lookup设计：借一张图
先从L2查找为1的bit，表示其中可能有空闲，然后从L1中找01或11的，再从它们对应的L0中找为1的bit，这样就快速找到空闲的Block。这样的查找过程还能保证连续的多次分配能够找到尽可能相邻的空闲Block，而内存中也能使用尽可能相邻的bits，大大提高了CPU Cache的命中率，进步一提高了分配效率（比较浅显的理解~）。
这个版本解决了老版本的查找效率问题，成为了N版本之后的默认Allocator。
P版新AvlAllocator
Avl allocator中维护了两棵avl树，它们包含了相同的节点，但是排序方式不同。range_tree以offset排序，而range_size_tree以空闲分段的长度排序（使用
oost::intrusive::avl_multiset，允许重复的key值）。
在分配空间时，先根据range_size_tree找到能满足分配长度的最小空闲分区，得到其offset，然后根据offset在range_tree中删除一个[startoffset, startoffset+length]对应的range，这个range涉及节点的分区记录，即为被分配的区间，用它们构造PExtent。
这样两次查找，然后在AVL树上删除一个或连续多个节点（触发AVL树重平衡），以完成分配过程。
释放空间过程则是在两颗树上插入新节点。
boost::intrusive是C++的侵入式容器，相比STL容器有更好的查询性能，它与对象生命周期独立，所以节点对象的生命周期管理会更加复杂。这相当于用实现复杂度来换更好的性能了。
Avl allocator具有Stupid Allocator一样好甚至更好的lookup效率，又避免了在碎片化程度高时的额外合并、移动操作。唯一缺点是，当空闲分区节点数量庞大时，其内存占用量会很大，特别是硬盘容量巨大时。
Avl allocator作为较小容量高速SSD的OSD的默认allocator，是一个非常好的选择。
在Q版实现了HybridAllocator，这便是为了解决Avl allocator内存超标而设计的。
HybridAllocator继承AvlAllocator，并可能管理了一个BitmapAllocator。当AvlAllocator的内存占用量并不高没超过阈值时，HybridAllocator等同于AvlAllocator；当内存用量超过阈值时，HybridAllocator退化为BitmapAllocator，但仍然使用HybridAllocator来缓存那些比较大的free分区，以加速查找过程。
Q版的BtreeAllocator，这个是一位大神实现的，但不知为何没有被添加为默认的allocator，翻阅了社区的邮件，可能是因为没有足够标准的benchmark工具来证明BtreeAllocator的优越性，所以搁置了。
BtreeAllocator与Avl allocator极其相似，查找、分配、释放逻辑基本一致。差别在于，它使用两棵B树，而AvlAllocator使用AVL树。B树相对AVL树更节约内存，且具有相当的查找效率，但其左右旋等结构变更操作相对于AVL树更复杂。所以二者的取舍是比较难的，理论上那分高下，只能用标准benchmark工具来一决雌雄，但貌似社区还没有这个工具。
不知后续版本如何发展，静观其变吧。
最后再来分析一下BlueFS的空间管理策略。
slow设备是BlueStore和BlueFS共用的，BlueStore的Allocator实例与BlueFS中Slow设备对应的Allocator是同一个实例。作为改进，二者的alloc_size也保持了一致，避免了以前版本alloc size不一致而引起的空间碎片化加剧问题。
WAL和DB设备由BlueFS独占使用，BlueStore不直接使用这片空间。在上图WAL、DB、Block设备齐全的情况下，BDEV_WAL和BDEV_DB各自拥有一个独立的Allocator实例。基于配置，这些Allocator可以是前文所述的各种类型。
没有独立的WAL设备时，BlueFS中也没有与之对应的bdev和allocator。
需要注意的是，当没有独立的DB设备时，BlueFS中将Block设备直接当成共享的DB设备使用，BlueFS中就没有Slow设备了。
当WAL和DB设备均没有的时候，BlueFS中仅有一个设备，它将Block设备直接当成共享的DB设备使用，没有BDEV_WAL和BDEV_SLOW。
一个需要注意的点是：bluefs的allocator构成一个数组，依次对应BDEV_WAL、BDEV_DB、BDEV_SLOW。在分配空间时，若BDEV_WAL allocator分配不出足够的空间，会降级用BDEV_DB allocator分配，若仍然不能够分配足够空间，则再次降级到BDEV_SLOW allocator，若还是不足，才会出现enospc错误。
另一个注意点是：每次_allocate调用，只从一个设备分配空间。例如需要BDEV_WAL allocator分配64K，而只分配出16K，那么，会将这16K还回去，然后尝试从BDEV_DB allocator分配全部64K，注意并不是分配剩下的48K。这样做可以简化日志结构。
不同的文件类型，其开始分配空间的设备是不同的，见下图。
BlueStore在mkfs流程中，会在BlueFS中创建db.wal、db、db.slow几个目录，而后将这些目录通过rocksdb的options传递给rocksDB，rocksDB在写入log文件时，就会选择db.wal目录，写入SST文件时，就会按照配置的db_paths，顺序使用db和db.slow目录。这样，rocksdb上层与bluefs下层在数据分布上达成一致。
BlueFS自身logfile和rocksdb的log file，均有限写入WAL设备；db目录的文件优先写入block.db设备；db.slow目录的设备则写入block设备。
当WAL设备不存在时，rocksdb的log file会写到db目录下。无论block.db设备是否存在，BlueFS的db目录都是存在的，只不过该目录的数据可能写到block设备上去而已。
最后，注意options中的disableWAL是指rocksdb不写log file，BlueFS的log file是无论怎样都存在的，依然会优先向block.wal设备去写。注意区别rocksdb log file、BlueFS log file和block.wal设备几个概念的区别和联系，不可混为一谈。
