BlueStore源碼分析之Stupid分配器

前言

前面介紹了 BlueStore的BitMap分配器，我們知道新版本的 Bitmap分配器的優(yōu)勢在于 使用連續(xù)的內(nèi)存空間從而盡可能更多的命中CPU Cache以提高分配器性能。在這里我們了解一下基于區(qū)間樹的 Stupid分配器（類似于Linux Buddy內(nèi)存管理算法），并對比分析一下其優(yōu)劣。

目錄

• 伙伴算法
• 數(shù)據(jù)結構
• 初始化
• 插入刪除
• 空間分配
• 空間回收
• 優(yōu)劣分析

伙伴算法

Linux內(nèi)存管理算法為了能夠快速響應請求，盡可能的提高內(nèi)存利用率同時減少外部內(nèi)存碎片，引入了伙伴系統(tǒng)算法 Buddy-System。該算法將所有的空閑頁分組為11個鏈表，每個鏈表分別包含 1、2、4、8、16、32、64、128、256、512、1024個連續(xù)的頁框塊，每個頁框塊的第一個內(nèi)存頁的物理地址是該塊大小的整數(shù)倍。 伙伴的特點是：兩個塊大小相同、兩個塊地址連續(xù)、第一塊的第一個頁框的物理地址是兩個塊總大小的整數(shù)倍（同屬于一個大塊，第1塊和第2塊是伙伴，第3塊和第4塊是伙伴，但是第2塊和第3塊不是伙伴）。具體內(nèi)存分配和內(nèi)存釋放可自行Google。

優(yōu)點：

• 較好的解決外部碎片問題，不能完全解決。
• 針對大內(nèi)存分配設計，可以快速的分配連續(xù)的內(nèi)存。

缺點：

• 合并的要求過于嚴格，只能是滿足伙伴關系的塊才可以合并。
• 一塊連續(xù)的內(nèi)存中僅有一個頁面被占用，就導致整個內(nèi)存不具備合并的條件。
• 算法頁面連續(xù)性差，DMA申請大塊連續(xù)物理內(nèi)存空間可能失敗，此時需要 CMA(Contiguous Memory Allocator, 連續(xù)內(nèi)存分配器)。
• 浪費空間，可以通過slab、kmem_cache等解決。

數(shù)據(jù)結構

Stupid分配器使用了區(qū)間樹組織數(shù)據(jù)結構，高效管理 Extent(offset, length)。

class StupidAllocator : public Allocator {
    CephContext* cct;
    // 分配空間用的互斥鎖
    std::mutex lock;
    // 空閑空間總大小
    int64_t num_free;
    // 最后一次分配空間的位置
    uint64_t last_alloc;
    // 區(qū)間樹數(shù)組，初始化的時候，free數(shù)組的長度為10，即有十顆區(qū)間樹
    std::vector<interval_set_t> free;
    // extent: offset, length
    typedef mempool::bluestore_alloc::pool_allocator<
        pair<const uint64_t, uint64_t>>
        allocator_t;
    // 有序的 btree map，按順存放extent。
    typedef btree::btree_map<uint64_t, uint64_t, std::less<uint64_t>,
                             allocator_t> interval_set_map_t;
    // 區(qū)間樹，主要的操作有 insert、erase等。
    typedef interval_set<uint64_t, interval_set_map_t> interval_set_t;
};

每顆區(qū)間樹的下標為 index(0-9)，index(1-9)表示的空間大小為： [2^(index-1) * bdev_block_size, 2^(index) * bdev_block_size)，

• free[0]: [0, 4k)
• free[1]: [4k, 8k)
• free[2]: [8k, 16k)
• free[3]: [16k, 32k)
• free[4]: [32k, 64k)
• free[5]: [64k, 128k)
• free[6]: [128k, 256k)
• free[7]: [256k, 512k)
• free[8]: [512k, 1024k)
• free[9]: [1024k, 2048k)

初始化

初始化Stupid分配器后，調(diào)用者會向Allocator中加入或者刪除空閑空間。

// 增加空閑空間
void StupidAllocator::init_add_free(uint64_t offset, uint64_t length) {
    std::lock_guard<std::mutex> l(lock);
    // 向 free 中插入空閑空間
    _insert_free(offset, length);
    // 更新空閑空間大小
    num_free += length;
}
// 刪除空閑空間
void StupidAllocator::init_rm_free(uint64_t offset, uint64_t length)
{
    std::lock_guard<std::mutex> l(lock);
    interval_set_t rm;
    rm.insert(offset, length);
    for (unsigned i = 0; i < free.size() && !rm.empty(); ++i) {
        interval_set_t overlap;
        overlap.intersection_of(rm, free[i]);
        // 刪除相應空間
        if (!overlap.empty()) {
            free[i].subtract(overlap);
            rm.subtract(overlap);
        }
    }
    num_free -= length; // 更新可用空間
}

插入刪除

區(qū)間樹實現(xiàn)代碼:

https://github.com/ceph/ceph/blob/master/src/include/interval_set.h

insert函數(shù)代碼:

https://github.com/ceph/ceph/blob/master/src/include/interval_set.h#L445

erase函數(shù)代碼:

https://github.com/ceph/ceph/blob/master/src/include/interval_set.h#L516

最核心的實現(xiàn)是向區(qū)間樹中插入以及刪除區(qū)間，代碼如下：

區(qū)間樹插入Extent

// 根據(jù)區(qū)間的長度，選取將要存放的區(qū)間樹，長度越大，bin值越大。
unsigned StupidAllocator::_choose_bin(uint64_t orig_len)
{
    uint64_t len = orig_len / cct->_conf->bdev_block_size;
    // cbits = (sizeof(v) * 8) - __builtin_clzll(v)
    // __builtin_clzll 返回前置的0的個數(shù)
    // cbits 結果是最高位1的下標(從0開始)，len越大，值越大
    int bin = std::min(int)cbits(len), (int)free.size() - 1);
    return bin;
}
void StupidAllocator::_insert_free(uint64_t off, uint64_t len)
{
    // 計算該段空閑空間屬于哪個區(qū)間樹
    unsigned bin = _choose_bin(len);
    while (true) {
        // 空閑空間插入?yún)^(qū)間樹
        free[bin].insert(off, len, &off, &len);
        unsigned newbin = _choose_bin(len);
        if (newbin == bin)
            break;
        // 插入數(shù)據(jù)后，可能合并區(qū)間，導致區(qū)間長度增大，可能要調(diào)整bin，此時需要將舊的刪除，然后插入新的bin
        // 區(qū)間合并有兩種情況：一是合并在原有區(qū)間前面；而是合并在原有區(qū)間后面。
        free[bin].erase(off, len);
        bin = newbin;
    }
}

回顧第一節(jié)伙伴算法， 兩種合并的方式是有區(qū)別的：

• 伙伴算法要求比較嚴格，參考第一節(jié)。
• Stupid Extent合并比較松散，只要滿足兩個Extent空間連續(xù)就可以。

區(qū)間樹刪除Extent

區(qū)間樹刪除Extent比較簡單，在原來Extent刪除傳入的Extent，然后計算最終Extent是否落入其他區(qū)間樹，如果落入則從此區(qū)間樹刪除，加入新的區(qū)間樹。

空間分配

空間分配的函數(shù)定義如下：

allocate(uint64_t want_size, uint64_t alloc_unit, 
        uint64_t max_alloc_size, int64_t hint,PExtentVector* extents);
allocate_int(uint64_t want_size, uint64_t alloc_unit, int64_t hint,
                         uint64_t* offset, uint32_t* length)

其中 hint是一個很重要的參數(shù)，表示分配的起始地址要盡量大于hint的值。

核心流程為4個2層for循環(huán)大致為：優(yōu)先從hint地址依次向高級區(qū)間樹開始分配長度大于等于 want_size的連續(xù)空間，如果沒有，則優(yōu)先從hint地址依次向低級區(qū)間樹開始分配長度大于等于 alloc_unit的連續(xù)空間(長度會大于alloc_unit)。

簡單的空間分配圖如下：

詳細的空間分配流程圖如下：

空間回收

空間釋放的函數(shù)定義如下：

release(const interval_set<uint64_t> &release_set)

流程很簡單，先加鎖，然后循環(huán)調(diào)用 _insert_free插入到對應區(qū)間樹里面，會涉及到相鄰空閑空間的合并，但是會導致分配空間碎片的問題。

優(yōu)劣分析

CPU Cache

Stupid底層使用BtreeMap來存儲一系列的Extent，內(nèi)存不一定是連續(xù)的，同時在分配空間遍歷區(qū)間樹時，雖然區(qū)間樹里面的Extent是有序的，但是由于內(nèi)存不一定是連續(xù)或者相鄰的兩個Extent內(nèi)存跨度可能很大，都會導致CPU-Cache預讀不到下一個Extent，從而不能很好的利用CPU-Cache。

Bitmap分配器在BlueStore初始化時就初始化好了3層，而且大小是固定的，同時分配空間是依次順序分配，從而可以充分的利用CPU-Cache的功能。從而提高分配器的性能。

偽空間碎片

基于Extent的Stupid分配器存在偽空間碎片（ 物理空間是連續(xù)的，但是分配器中卻不連續(xù)）問題：

一個24K的連續(xù)空間，經(jīng)過6次4K分配和亂序的6次4K釋放后，可能會變成 8K + 4K + 8K + 4K四塊空間。

其中兩個4K的區(qū)間由于和周邊塊大小一樣，所以落到不同的區(qū)間樹中，導致很難被合并，24K的連續(xù)空間變成了四塊不連續(xù)空間。

Bitmap分配器由于初始化時就分配好了3層所有內(nèi)存，而且3層都是有序的的同時分配空間是順序遍歷的，在釋放空間的時候設置相應位就可以，不影響連續(xù)性，所以不存在這個問題。

據(jù)Bitmap作者的 性能對比實驗來看，Bitmap分配器要好于Stupid，等Bitmap穩(wěn)定后，可以設置BlueStore的默認分配器為Bitmap。

作者：史明亞

• 現(xiàn)在注冊滴滴云，有機會可得30元無門檻滴滴出行券

• 新購云服務1月5折 3月4.5折 6月低至4折

• 滴滴云使者招募，推薦最高返傭50%