当前位置: 首页 > news >正文

谈谈BlueStore的BitmapAllocator

背景

BlueStore在ceph里面承担了数据在底层磁盘上的读写任务,那它的功能里自然就有一块是管理磁盘空间使用的。说白了,就是记录&管理磁盘里哪些空间已经使用了,哪些空间还没有被使用。
目前官方的ceph里使用BitmapAllocator来管理磁盘空间使用。
简单的说就是用一个二进制bit来表面一个磁盘区间是否被使用了。
咱们先说几个关键术语:

bdev_block_size:磁盘块大小,IO的最小单元,默认4K。
min_alloc_size:最小分配单元,SSD默认16K,HDD默认64K。
max_alloc_size:最大分配单元,默认0不限制,即一次连续的分配结果只包含一个extent。
alloc_unit:分配单元(AU),一般设置为min_alloc_size。

一次allocate的单元就是alloc_unit,咱们就按64KB计算。这个二进制就只需要1个Bit。1个字节的bit位就可以表示512KB。那这么来说一个1TB的磁盘就需要2MB的内存空间。每次allocate平均就需要遍历整个2MB内存的一半(一共2MB,平均一次就取一半计算)。效率略低。
后面就有了改良版的BitmapAllocator。
初始版的BitmapAllocator是使用一个字节序列来标识整个磁盘空间。改良版是使用3个字节序列来标识磁盘空间。
如下:
在这里插入图片描述
分别有3个字节序列,分别是L0,L1,L2,其中L0最接近磁盘。
记住下面这些概念

每一层自己都有slot,每个slot的大小都是64Bit,每个slot里面有children。
L2和L0层1个slot管理自己slot里面的64个children,L1层1个slot管理32个children L2 L0
一个children是1个bit;L1层一个children是2个bit 每个children管理下层8个slot
一个L0的children就是1个AU(Alloc_Unit),默认64KB(HDD)
一个L1的children,管理L0里8个slot,L0里1个slot管理64个children,也就是说L1的一个children对应L0
864个children
一个L2的children,管理L1里8个slot,L1层1个slot管理32个children,也就是说L2的一个children对应L1
8
32个children

1个L0的childre 对应 64KB 1个L1的solt对应4MB
1个L1的children 对应 86464KB=32MB 1个L1的solt对应1G
1个L2的children 对应 83232MB = 8G 1个L2的solt 对应 512GB
如果4TB的磁盘,在L2层就需要8个slot

生命周期&使用sample

// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
// vim: ts=8 sw=2 smarttab
/** In memory space allocator test cases.* Author: Ramesh Chander, Ramesh.Chander@sandisk.com*/
#include <iostream>
#include <boost/scoped_ptr.hpp>
#include <gtest/gtest.h>#include "common/Cond.h"
#include "common/errno.h"
#include "include/stringify.h"
#include "include/Context.h"
#include "os/bluestore/Allocator.h"using namespace std;typedef boost::mt11213b gen_type;class AllocTest : public ::testing::TestWithParam<const char*> {public:boost::scoped_ptr<Allocator> alloc;AllocTest(): alloc(0) { }void init_alloc(int64_t size, uint64_t min_alloc_size) {std::cout << "Creating alloc type " << string(GetParam()) << " \n";alloc.reset(Allocator::create(g_ceph_context, GetParam(), size,min_alloc_size));}void init_close() {alloc.reset(0);}
};TEST_P(AllocTest, mytest)
{uint64_t block = 64*1024;//4TBuint64_t size = 4L*1024*1024*1024*1024L;init_alloc(size, block);alloc->init_add_free(0, size);PExtentVector extents;alloc->allocate(512L*1024*1024*1024, block, 0, (int64_t)0, &extents);std::cout<<"-------"<<std::endl;alloc->allocate( block*3, block, 0, (int64_t)0, &extents);std::cout<<"xxxxxxxxxxxx"<<std::endl;alloc->allocate( block*4, block, 0, (int64_t)0, &extents);
}INSTANTIATE_TEST_SUITE_P(Allocator,AllocTest,::testing::Values("stupid", "bitmap", "avl", "hybrid", "btree"));

以上代码参考在src/test/objectstore/Allocator_test.cc

相关类图

AllocatorLevel是基础类,磁盘分配器需要实现这个类

class AllocatorLevel01Loose : public AllocatorLevel01
class AllocatorLevel01 : public AllocatorLevel
class AllocatorLevel02 : public AllocatorLevelclass BitmapAllocator : public Allocator,public AllocatorLevel02<AllocatorLevel01Loose> 

分配原理

在构造函数里

BitmapAllocator::BitmapAllocator(CephContext* _cct,int64_t capacity,int64_t alloc_unit,std::string_view name) :Allocator(name, capacity, alloc_unit),cct(_cct)
{_init(capacity, alloc_unit, false);
}static const slot_t all_slot_set = 0xffffffffffffffff;
static const slot_t all_slot_clear = 0;

在_init里面会把L2,L1,L0的每个solt(8个字节,64个bit,刚好是一个long long 无符号整数)都置成0。
之后
init_add_free 的时候
又把L2,L1,L0层的每个槽位都置成为0xffffffffffffffff

每次分配空间的时候,就先从L2找,
如果L2的槽位是0,就说明这个槽位已经完全都分配了,查找下一个槽位
如果L2的槽位是上0xffffffffffffffff,就说明整个槽位都还没有分配过任何空间,完全是空闲的,把free_pos设为0,然后去L1查找
如果L2的槽位既不是0也不是0xffffffffffffffff,说明这个槽位分配过数据,但是又没有完全分配,计算出free_pos后,传递给L1进行allocate
上面的逻辑是我从代码里分析来的,但是我感觉很疑惑,为什么

如果L2的槽位是上0xffffffffffffffff,就说明整个槽位还完全没有分配

0xffffffffffffffff不是all_slot_set 么?它不应该代表已经完全都分配了么??!!
希望熟悉这块的小伙伴不吝赐教。
第一次进入_allocate_l1之后,第一个槽位是0xffffffffffffffff,在上面进行分配空间,这部分逻辑可以参考:https://zhuanlan.zhihu.com/p/643938193
另外l1._allocate_l1 的返回值如果是true,就说明在L1对应的8个solt都已经分配完全了。如果真的返回true,那就需要修改L2上对应pos的bit为0。代表已经分配过了。

我任务这里面最麻烦的就是不知道什么时候0代表已经分配,什么时候1代表已经分配。

参考资料

https://zhuanlan.zhihu.com/p/643938193

相关文章:

  • D - New Friends(AtCoder Beginner Contest 350)
  • 海外仓快递系统哪个好?教你快速选到适合自己的管理系统
  • # linux 中使用 visudo 命令,怎么保存退出?
  • 【网络】高级IO(select||poll||epoll)
  • 中断处理过程介绍
  • 9. C++通过epoll+fork的方式实现高性能网络服务器
  • 前端面试题日常练-day37 【面试题】
  • 合并featurecount产生的多个表达矩阵文件
  • busco,checkM2:基因组或MAG完整度分析
  • Web开发——HTMLCSS
  • HTTP方法、状态码和请求过程
  • 安装 Android Studio 2024.1.1.6(Koala SDK35)和过程问题解决
  • Python开发 —— 错误ModuleNotFoundError: No module name
  • Java原生JDBC概览
  • 快速排序算法备考
  • 《Javascript数据结构和算法》笔记-「字典和散列表」
  • 【技术性】Search知识
  • 0x05 Python数据分析,Anaconda八斩刀
  • 11111111
  • canvas 高仿 Apple Watch 表盘
  • JAVA_NIO系列——Channel和Buffer详解
  • linux安装openssl、swoole等扩展的具体步骤
  • react 代码优化(一) ——事件处理
  • Selenium实战教程系列(二)---元素定位
  • sessionStorage和localStorage
  • SQLServer插入数据
  • Stream流与Lambda表达式(三) 静态工厂类Collectors
  • V4L2视频输入框架概述
  • 给新手的新浪微博 SDK 集成教程【一】
  • 工作手记之html2canvas使用概述
  • 关于 Linux 进程的 UID、EUID、GID 和 EGID
  • 开发了一款写作软件(OSX,Windows),附带Electron开发指南
  • 前端技术周刊 2019-01-14:客户端存储
  • 浅谈web中前端模板引擎的使用
  • 使用parted解决大于2T的磁盘分区
  • 手写双向链表LinkedList的几个常用功能
  • 思否第一天
  • 异常机制详解
  • 栈实现走出迷宫(C++)
  • 掌握面试——弹出框的实现(一道题中包含布局/js设计模式)
  • # 达梦数据库知识点
  • ${ }的特别功能
  • (11)工业界推荐系统-小红书推荐场景及内部实践【粗排三塔模型】
  • (2)STL算法之元素计数
  • (arch)linux 转换文件编码格式
  • (pojstep1.1.1)poj 1298(直叙式模拟)
  • (八)Flask之app.route装饰器函数的参数
  • (超详细)语音信号处理之特征提取
  • (剑指Offer)面试题41:和为s的连续正数序列
  • (七)Knockout 创建自定义绑定
  • (亲测有效)解决windows11无法使用1500000波特率的问题
  • (删)Java线程同步实现一:synchronzied和wait()/notify()
  • (十一)c52学习之旅-动态数码管
  • (四) 虚拟摄像头vivi体验
  • (原創) 如何讓IE7按第二次Ctrl + Tab時,回到原來的索引標籤? (Web) (IE) (OS) (Windows)...