CEPH VERSION： Quincy 17.2.6
上一篇分析了BlueStore的各工作線程，在提交線程中經(jīng)歷了一個(gè)比較復(fù)雜且重要的過(guò)程_txc_add_transaction胆描，它完成了從上層ObjectStore::Transaction到BlueStore::TransContext的轉(zhuǎn)換势誊，轉(zhuǎn)換過(guò)程中闸氮，對(duì)于數(shù)據(jù)變更類的Op栖雾，進(jìn)行了空間的分配和回收操作格了，這些操作作為kv事務(wù)的一部分被原子提交到RocksDB棉胀。
本篇來(lái)探究這些數(shù)據(jù)分配村怪、釋放過(guò)程的細(xì)節(jié)秽浇，探究Allocator的演變過(guò)程，理解開(kāi)發(fā)者們?cè)谶@個(gè)問(wèn)題上所做的諸多努力甚负。
BlueStore中柬焕，空間管理分為兩個(gè)部分：FreelistManager和Allocator审残，后續(xù)簡(jiǎn)稱為fm和alloc。fm用于表示空閑空間的存儲(chǔ)結(jié)構(gòu)以及分配击喂、釋放空間的存儲(chǔ)數(shù)據(jù)變更策略维苔，它更貼近于空閑空間的物理存儲(chǔ)層面；alloc則側(cè)重于內(nèi)存表示懂昂，它著重于空閑空間快速查找與標(biāo)記的時(shí)間復(fù)雜度介时，和在內(nèi)存占用的空間復(fù)雜度上尋求平衡。
在BlueFS中也使用Allocator凌彬，但不使用fm沸柔，這是沒(méi)有辦法的事情，fm依賴rocksdb保存其freelist信息铲敛，BlueFS作為rocksdb的載體褐澎，自然不能再依賴fm，否則就形成了環(huán)形依賴伐蒋，所以BlueFS有自己的空閑空間信息存盤(pán)機(jī)制工三。
fm一直以來(lái)都使用一個(gè)實(shí)現(xiàn)BitmapFreelistManager，新的版本增加了ZonedFreelistManager先鱼，用于支持SMR Device俭正。由于ZonedFreelistManager比較特殊，下面著重討論更普遍的BitmapFreelistManager焙畔。
BlueStore::_open_fm函數(shù)調(diào)用會(huì)觸發(fā)fm的創(chuàng)建或加載掸读，若是創(chuàng)建流程，函數(shù)第一個(gè)參數(shù)會(huì)傳入一個(gè)KeyValueDB::Transaction t事務(wù)對(duì)象宏多，fm的一系列初始化kv將附加到此事務(wù)儿惫，附加的kv如下：
| prefix db CF | Key | Value | 說(shuō)明 |
|---|---|---|---|
| S | freelist_type | bitmap或null或zoned | 記錄所使用的的fm類型 |
| B | bytes_per_block | 512或4K | 設(shè)備的Block Size |
| B | blocks_per_key | 默認(rèn)128 | 每個(gè)bitmap key對(duì)應(yīng)多少個(gè)block，意味著每個(gè)value多少個(gè)bit,每個(gè)bit對(duì)應(yīng)一個(gè)block |
| B | blocks | 總block數(shù)量 | 總block數(shù)量 |
| B | size | 設(shè)備總空間 | 設(shè)備總空間 |
| b | 0 | 二進(jìn)制總128bit 11000000...000 | Block Size以4K為例 預(yù)留8K給label + superblock |
- S - BlueStore的全局元數(shù)據(jù)prefix
- B - fm的元數(shù)據(jù)prefix
- b - fm的bitmap記錄prefix
伴隨著fm->allocate的新空間分配伸但，會(huì)產(chǎn)生越來(lái)越多的b前綴的kv記錄
伴隨著fm->release的釋放操作肾请，原先某個(gè)n前綴記錄中，Value對(duì)應(yīng)的bit被翻轉(zhuǎn)為0
而fm->allocate的重新分配更胖，又將這些bit翻轉(zhuǎn)為1
所以筐喳，allocate和release操作就被統(tǒng)一了，二者都是將offset~length這個(gè)區(qū)間涉及的對(duì)應(yīng)bit做位翻轉(zhuǎn)(xor)即可函喉。原先沒(méi)有記錄的位置，默認(rèn)為全0 bit荣月，首次被分配時(shí)產(chǎn)生對(duì)應(yīng)kv管呵。
allocate和release操作并不直接修改DB中的kv，而是將kv變更附加到傳入的KeyValueDB::Transaction t事務(wù)哺窄，伴隨其余的kv變更一起做原子提交捐下，所以账锹，fm僅僅是提供了allocate和release的kv變更策略。
注意坷襟，在新的版本奸柬，除了前面創(chuàng)建fm時(shí)會(huì)將fm meta寫(xiě)到RocksDB外，還會(huì)在block設(shè)備上的0-4K位置婴程，以bdev label形式記錄一份廓奕，當(dāng)然fm的meta只是bdev label的一部分kv。這樣做相當(dāng)于在不同設(shè)備不同位置做了super meta的雙重備份档叔。
在了解了fm之后桌粉，再來(lái)看Allocator的實(shí)現(xiàn)
最早使用StupidAllocator，它使用10個(gè)bin組成free vector衙四，每個(gè)bin是一個(gè)interval_set铃肯，其中管理著一個(gè)btree。每一層的bin管理連續(xù)N個(gè)free Block的集合传蹈，跟Linux的Slab管理有些相似押逼。free[0]的btree中，管理著1個(gè)Block的空閑區(qū)間惦界；free[1]管理著2個(gè)Block的空閑空間挑格；free[2]管理4個(gè)Block的空間；...;free[8]管理著256個(gè)Block的空間表锻，free[9]則管理著512個(gè)及以上的Block的空間恕齐。
當(dāng)需要分配空間時(shí)，根據(jù)待分配的len找到合適的bin予以分配瞬逊，分配后可能引起某些區(qū)間長(zhǎng)度減少显歧，從而需要移動(dòng)到更低的bin。移動(dòng)到更低的bin有可能引起合并确镊，合并后又可能移動(dòng)到更高的bin士骤，然后有可能再次引起合并...
釋放空間也是如此，有可能引起分區(qū)合并蕾域，從而移動(dòng)到新的bin拷肌，移動(dòng)又可能引發(fā)合并，再次移動(dòng)...
所以旨巷，StupidAllocator對(duì)于碎片化嚴(yán)重的情況巨缘，會(huì)有些尷尬，分配采呐、釋放可能引起很多額外的操作若锁，性能會(huì)變差。
N版本實(shí)現(xiàn)的新版BitmapAllocator斧吐，詳見(jiàn) https://github.com/ceph/ceph/pull/21825
這個(gè)版本的BitmapAllocator相對(duì)于老版本又固，大大提高了空閑空間的lookup效率仲器，其原因在于它做了三層lookup設(shè)計(jì)：借一張圖
先從L2查找為1的bit，表示其中可能有空閑仰冠，然后從L1中找01或11的乏冀，再?gòu)乃鼈儗?duì)應(yīng)的L0中找為1的bit，這樣就快速找到空閑的Block洋只。這樣的查找過(guò)程還能保證連續(xù)的多次分配能夠找到盡可能相鄰的空閑Block辆沦，而內(nèi)存中也能使用盡可能相鄰的bits，大大提高了CPU Cache的命中率木张，進(jìn)步一提高了分配效率（比較淺顯的理解~）众辨。
這個(gè)版本解決了老版本的查找效率問(wèn)題，成為了N版本之后的默認(rèn)Allocator舷礼。
P版新AvlAllocator
Avl allocator中維護(hù)了兩棵avl樹(shù)鹃彻，它們包含了相同的節(jié)點(diǎn)，但是排序方式不同妻献。range_tree以offset排序蛛株，而range_size_tree以空閑分段的長(zhǎng)度排序（使用
oost::intrusive::avl_multiset，允許重復(fù)的key值）育拨。
在分配空間時(shí)谨履，先根據(jù)range_size_tree找到能滿足分配長(zhǎng)度的最小空閑分區(qū)，得到其offset熬丧，然后根據(jù)offset在range_tree中刪除一個(gè)[startoffset, startoffset+length]對(duì)應(yīng)的range笋粟，這個(gè)range涉及節(jié)點(diǎn)的分區(qū)記錄，即為被分配的區(qū)間析蝴，用它們構(gòu)造PExtent害捕。
這樣兩次查找，然后在AVL樹(shù)上刪除一個(gè)或連續(xù)多個(gè)節(jié)點(diǎn)（觸發(fā)AVL樹(shù)重平衡）闷畸，以完成分配過(guò)程尝盼。
釋放空間過(guò)程則是在兩顆樹(shù)上插入新節(jié)點(diǎn)。
boost::intrusive是C++的侵入式容器佑菩，相比STL容器有更好的查詢性能盾沫，它與對(duì)象生命周期獨(dú)立，所以節(jié)點(diǎn)對(duì)象的生命周期管理會(huì)更加復(fù)雜殿漠。這相當(dāng)于用實(shí)現(xiàn)復(fù)雜度來(lái)?yè)Q更好的性能了赴精。
Avl allocator具有Stupid Allocator一樣好甚至更好的lookup效率，又避免了在碎片化程度高時(shí)的額外合并绞幌、移動(dòng)操作蕾哟。唯一缺點(diǎn)是，當(dāng)空閑分區(qū)節(jié)點(diǎn)數(shù)量龐大時(shí)，其內(nèi)存占用量會(huì)很大渐苏，特別是硬盤(pán)容量巨大時(shí)。
Avl allocator作為較小容量高速SSD的OSD的默認(rèn)allocator菇夸，是一個(gè)非常好的選擇琼富。
在Q版實(shí)現(xiàn)了HybridAllocator，這便是為了解決Avl allocator內(nèi)存超標(biāo)而設(shè)計(jì)的庄新。
HybridAllocator繼承AvlAllocator鞠眉，并可能管理了一個(gè)BitmapAllocator。當(dāng)AvlAllocator的內(nèi)存占用量并不高沒(méi)超過(guò)閾值時(shí)择诈，HybridAllocator等同于AvlAllocator械蹋；當(dāng)內(nèi)存用量超過(guò)閾值時(shí)，HybridAllocator退化為BitmapAllocator羞芍，但仍然使用HybridAllocator來(lái)緩存那些比較大的free分區(qū)哗戈，以加速查找過(guò)程。
Q版的BtreeAllocator荷科，這個(gè)是一位大神實(shí)現(xiàn)的唯咬，但不知為何沒(méi)有被添加為默認(rèn)的allocator，翻閱了社區(qū)的郵件畏浆，可能是因?yàn)闆](méi)有足夠標(biāo)準(zhǔn)的benchmark工具來(lái)證明BtreeAllocator的優(yōu)越性胆胰，所以擱置了。
BtreeAllocator與Avl allocator極其相似刻获，查找蜀涨、分配、釋放邏輯基本一致蝎毡。差別在于厚柳，它使用兩棵B樹(shù)，而AvlAllocator使用AVL樹(shù)顶掉。B樹(shù)相對(duì)AVL樹(shù)更節(jié)約內(nèi)存草娜，且具有相當(dāng)?shù)牟檎倚剩渥笥倚冉Y(jié)構(gòu)變更操作相對(duì)于AVL樹(shù)更復(fù)雜痒筒。所以二者的取舍是比較難的宰闰，理論上那分高下，只能用標(biāo)準(zhǔn)benchmark工具來(lái)一決雌雄簿透，但貌似社區(qū)還沒(méi)有這個(gè)工具移袍。
不知后續(xù)版本如何發(fā)展，靜觀其變吧老充。
最后再來(lái)分析一下BlueFS的空間管理策略葡盗。
slow設(shè)備是BlueStore和BlueFS共用的，BlueStore的Allocator實(shí)例與BlueFS中Slow設(shè)備對(duì)應(yīng)的Allocator是同一個(gè)實(shí)例啡浊。作為改進(jìn)觅够，二者的alloc_size也保持了一致胶背，避免了以前版本alloc size不一致而引起的空間碎片化加劇問(wèn)題。
WAL和DB設(shè)備由BlueFS獨(dú)占使用喘先，BlueStore不直接使用這片空間钳吟。在上圖WAL、DB窘拯、Block設(shè)備齊全的情況下红且，BDEV_WAL和BDEV_DB各自擁有一個(gè)獨(dú)立的Allocator實(shí)例〉渔ⅲ基于配置暇番，這些Allocator可以是前文所述的各種類型。
沒(méi)有獨(dú)立的WAL設(shè)備時(shí)思喊，BlueFS中也沒(méi)有與之對(duì)應(yīng)的bdev和allocator壁酬。
需要注意的是，當(dāng)沒(méi)有獨(dú)立的DB設(shè)備時(shí)搔涝，BlueFS中將Block設(shè)備直接當(dāng)成共享的DB設(shè)備使用厨喂，BlueFS中就沒(méi)有Slow設(shè)備了。
當(dāng)WAL和DB設(shè)備均沒(méi)有的時(shí)候庄呈，BlueFS中僅有一個(gè)設(shè)備蜕煌，它將Block設(shè)備直接當(dāng)成共享的DB設(shè)備使用，沒(méi)有BDEV_WAL和BDEV_SLOW诬留。
一個(gè)需要注意的點(diǎn)是：bluefs的allocator構(gòu)成一個(gè)數(shù)組斜纪，依次對(duì)應(yīng)BDEV_WAL、BDEV_DB文兑、BDEV_SLOW盒刚。在分配空間時(shí)，若BDEV_WAL allocator分配不出足夠的空間绿贞，會(huì)降級(jí)用BDEV_DB allocator分配因块，若仍然不能夠分配足夠空間，則再次降級(jí)到BDEV_SLOW allocator籍铁，若還是不足涡上，才會(huì)出現(xiàn)enospc錯(cuò)誤。
另一個(gè)注意點(diǎn)是：每次_allocate調(diào)用拒名，只從一個(gè)設(shè)備分配空間吩愧。例如需要BDEV_WAL allocator分配64K，而只分配出16K增显，那么雁佳，會(huì)將這16K還回去，然后嘗試從BDEV_DB allocator分配全部64K，注意并不是分配剩下的48K糖权。這樣做可以簡(jiǎn)化日志結(jié)構(gòu)堵腹。
不同的文件類型，其開(kāi)始分配空間的設(shè)備是不同的星澳，見(jiàn)下圖秸滴。
BlueStore在mkfs流程中，會(huì)在BlueFS中創(chuàng)建db.wal募判、db、db.slow幾個(gè)目錄咒唆，而后將這些目錄通過(guò)rocksdb的options傳遞給rocksDB届垫，rocksDB在寫(xiě)入log文件時(shí)，就會(huì)選擇db.wal目錄全释，寫(xiě)入SST文件時(shí)装处，就會(huì)按照配置的db_paths，順序使用db和db.slow目錄浸船。這樣妄迁，rocksdb上層與bluefs下層在數(shù)據(jù)分布上達(dá)成一致。
BlueFS自身logfile和rocksdb的log file李命，均有限寫(xiě)入WAL設(shè)備登淘；db目錄的文件優(yōu)先寫(xiě)入block.db設(shè)備；db.slow目錄的設(shè)備則寫(xiě)入block設(shè)備封字。
當(dāng)WAL設(shè)備不存在時(shí)黔州，rocksdb的log file會(huì)寫(xiě)到db目錄下。無(wú)論block.db設(shè)備是否存在阔籽，BlueFS的db目錄都是存在的流妻，只不過(guò)該目錄的數(shù)據(jù)可能寫(xiě)到block設(shè)備上去而已。
最后笆制，注意options中的disableWAL是指rocksdb不寫(xiě)log file绅这，BlueFS的log file是無(wú)論怎樣都存在的，依然會(huì)優(yōu)先向block.wal設(shè)備去寫(xiě)在辆。注意區(qū)別rocksdb log file证薇、BlueFS log file和block.wal設(shè)備幾個(gè)概念的區(qū)別和聯(lián)系，不可混為一談开缎。
