FreelistManager有什么用

這篇文章主要講解了“FreelistManager有什么用”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“FreelistManager有什么用”吧！

前言

BlueStore直接管理裸設備，需要自行管理空間的分配和釋放。Stupid和Bitmap分配器的結果是保存在內存中的，分配結果的持久化是通過FreelistManager來做的。

一個block的狀態可以為占用和空閑兩種狀態，持久化時只需要記錄一種狀態即可，便可以推導出另一種狀態，BlueStore記錄的是空閑block。主要有兩個原因：一是回收空間的時候，方便空閑空間的合并；二是已分配的空間在Object中已有記錄。

FreelistManager最開始有extent和bitmap兩種實現，現在默認為bitmap實現，extent的實現已經廢棄。空閑空間持久化到磁盤也是通過RocksDB的Batch寫入的。FreelistManager將block按一定數量組成段，每個段對應一個k/v鍵值對，key為第一個block在磁盤物理地址空間的offset，value為段內每個block的狀態，即由0/1組成的位圖，1為空閑，0為使用，這樣可以通過與1進行異或運算，將分配和回收空間兩種操作統一起來。

<a name="chapter1"></a>通用接口

FreelistManager最主要的接口就是allocator和release。

virtual void allocate(
	uint64_t offset, uint64_t length,
	KeyValueDB::Transaction txn) = 0;

virtual void release(
    uint64_t offset, uint64_t length,
    KeyValueDB::Transaction txn) = 0;

<a name="chapter2"></a>數據結構

class BitmapFreelistManager : public FreelistManager {
	// rocksdb key前綴：meta_prefix為 B，bitmap_prefix為 b
	std::string meta_prefix, bitmap_prefix;
	
	// key-value DB的指針，封裝了rocksdb的操作
	KeyValueDB *kvdb;
	
	// rocksdb的merge操作：按位異或(xor)
	ceph::shared_ptr<KeyValueDB::MergeOperator> merge_op;
	
	// enumerate操作時加鎖
	std::mutex lock;

	// 設備總大小
	uint64_t size;
	
	// 設備總block數
	uint64_t blocks;

	// block大小：bdev_block_size，默認min_alloc_size
	uint64_t bytes_per_block;
	
	// 每個key包含多少個block， 默認128
	uint64_t blocks_per_key;
	
	// 每個key對應空間大小
	uint64_t bytes_per_key;

	// block掩碼
	uint64_t block_mask;
	
	// key掩碼
	uint64_t key_mask;

	bufferlist all_set_bl;

	// 遍歷rocksdb key相關的成員
	KeyValueDB::Iterator enumerate_p;
	uint64_t enumerate_offset;
	bufferlist enumerate_bl;
	int enumerate_bl_pos; 
};

<a name="chapter3"></a>初始化

BlueStore在初始化osd的時候，會執行mkfs，初始化FreelistManager(create/init），后續如果重啟進程，會執行mount操作，只會對FreelistManager執行init操作。

int BlueStore::mkfs()
{
	......
	r = _open_fm(true);
	......
}

int BlueStore::_open_fm(bool create)
{
	......
	fm = FreelistManager::create(cct, freelist_type, db, PREFIX_ALLOC);

	// 第一次初始化，需要固化meta參數
	if (create) {
		fm->create(bdev->get_size(), min_alloc_size, t);
	}

	......
	int r = fm->init(bdev->get_size());
}

// create固化一些meta參數到kvdb中，init的時候，從kvdb讀取這些參數
int BitmapFreelistManager::create(uint64_t new_size, uint64_t min_alloc_size,
		KeyValueDB::Transaction txn)
{
	txn->set(meta_prefix, "bytes_per_block", bl); // min_alloc_size
	txn->set(meta_prefix, "blocks_per_key", bl); // 128
	txn->set(meta_prefix, "blocks", bl);
	txn->set(meta_prefix, "size", bl);
}

// create/init 均會調用下面這個函數，初始化block/key的掩碼
void BitmapFreelistManager::_init_misc()
{
	// 128 >> 3 = 16，每個block用1個bit表示。
	// 即一個key的value對應128個block，需要16字節。
	bufferptr z(blocks_per_key >> 3); 
	memset(z.c_str(), 0xff, z.length());
	all_set_bl.clear();
	all_set_bl.append(z);
	
	// 0x FFFF FFFF FFFF F000
	block_mask = ~(bytes_per_block - 1); 
	bytes_per_key = bytes_per_block * blocks_per_key;
	
	// 0xFFFF FFFF FFF8 0000
	key_mask = ~(bytes_per_key - 1);
}

<a name="chapter4"></a>Merge

異或Merge接口實現：

https://github.com/ceph/ceph/blob/master/src/os/bluestore/BitmapFreelistManager.cc#L21

// 繼承rocksdb merge接口：異或操作(xor)
struct XorMergeOperator : public KeyValueDB::MergeOperator {
	 // old_value不存在，那么new_value直接賦值為rdata。
    void merge_nonexistent(const char *rdata, size_t rlen,
                           std::string *new_value) override {
        *new_value = std::string(rdata, rlen);
    }
    
    // old_value存在，則與rdata逐位異或xor。
    void merge(const char *ldata, size_t llen, const char *rdata, size_t rlen,
               std::string *new_value) override {
        assert(llen == rlen);
        *new_value = std::string(ldata, llen);
        for (size_t i = 0; i < rlen; ++i) {
            (*new_value)[i] ^= rdata[i];
        }
    }
    // We use each operator name and each prefix to construct the
    // overall RocksDB operator name for consistency check at open time.
    string name() const override { return "bitwise_xor"; }
};

異或Merge接口應用：

https://github.com/ceph/ceph/blob/master/src/kv/RocksDBStore.cc#L91

bool Merge(const rocksdb::Slice& key,
	     const rocksdb::Slice* existing_value,
	     const rocksdb::Slice& value,
	     std::string* new_value,
	     rocksdb::Logger* logger) const override 
{
	// for default column family
	// extract prefix from key and compare against each registered merge op;
	// even though merge operator for explicit CF is included in merge_ops,
	// it won't be picked up, since it won't match.
	for (auto& p : store.merge_ops) {
		if (p.first.compare(0, p.first.length(),
					  key.data(), p.first.length()) == 0 &&
			  key.data()[p.first.length()] == 0) {
			// 如果old_value存在，那么直接merge，否則直接替換。
			if (existing_value) {
				p.second->merge(existing_value->data(), existing_value->size(),
							  value.data(), value.size(),
							  new_value);
			} else {
				p.second->merge_nonexistent(value.data(), value.size(), new_value);
			}
			break;
		}
	}
	return true;
}

最終調用Rocksdb的Batch的Merge方法。Batch可以實現簡單寫入和條件寫入的原子操作。

<a name="chapter5"></a>Allocate

分配和釋放空間兩種操作是完全一樣的，都是調用異或(Xor)操作，我們著重看_xor函數。

void BitmapFreelistManager::allocate(uint64_t offset, uint64_t length, KeyValueDB::Transaction txn)
{
	_xor(offset, length, txn);
}

void BitmapFreelistManager::release(uint64_t offset, uint64_t length, KeyValueDB::Transaction txn)
{
	_xor(offset, length, txn);
}

void BitmapFreelistManager::_xor(uint64_t offset, uint64_t length, KeyValueDB::Transaction txn)
{
	// 注意offset和length都是以block邊界對齊
	uint64_t first_key = offset & key_mask;
	uint64_t last_key = (offset + length - 1) & key_mask;

	if (first_key == last_key) { // 最簡單的case，此次操作對應一個段
		bufferptr p(blocks_per_key >> 3); // 16字節大小的buffer
		p.zero(); // 置為全0
		unsigned s = (offset & ~key_mask) / bytes_per_block; // 段內開始block的編號
		unsigned e = ((offset + length - 1) & ~key_mask) / bytes_per_block; // 段內結束block的編號

		for (unsigned i = s; i <= e; ++i) { // 生成此次操作的掩碼
			p[i >> 3] ^= 1ull << (i & 7); // i>>3定位block對應位的字節， 1ull<<(i&7)定位bit，然后異或將位設置位1
		}

		string k;
		make_offset_key(first_key, &k); // 將內存內容轉換為16進制的字符
		bufferlist bl;
		bl.append(p);
		bl.hexdump(*_dout, false);
		txn->merge(bitmap_prefix, k, bl); // 和目前的value進行異或操作

	} else { // 對應多個段，分別處理第一個段，中間段，和最后一個段，首尾兩個段和前面情況一樣

		// 第一個段
		{
			// 類似上面情況
			......

			// 增加key，定位下一個段
			first_key += bytes_per_key;
		}

		// 中間段，此時掩碼就是全1，所以用all_set_bl
		while (first_key < last_key) {
			string k;
			make_offset_key(first_key, &k);
			all_set_bl.hexdump(*_dout, false);

			txn->merge(bitmap_prefix, k, all_set_bl); // 和目前的value進行異或操作

			// 增加key，定位下一個段
			first_key += bytes_per_key;
		}

		// 最后一個段
		{
			// 和前面操作類似
		}
	}
}

xor函數看似復雜，全是位操作，仔細分析一下，分配和釋放操作一樣，都是將段的bit位和當前的值進行異或。一個段對應一組blocks，默認128個，在k/v中對應一組值。例如，當磁盤空間全部空閑的時候，k/v狀態如下: (b00000000，0x00), (b00001000, 0x00), (b00002000, 0x00)……b為key的前綴，代表bitmap。

<a name="chapter6"></a>Release

釋放空間和分配空間都是一樣的操作。

void BitmapFreelistManager::release(uint64_t offset, uint64_t length, KeyValueDB::Transaction txn)
{
	_xor(offset, length, txn);
}

感謝各位的閱讀，以上就是“FreelistManager有什么用”的內容了，經過本文的學習后，相信大家對FreelistManager有什么用這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！