固定链接 BlueStore源码分析之Stupid分配器

BlueStore源码分析之Stupid分配器

BlueStore源码分析之Stupid分配器


layout: post
title: “BlueStore源码分析之Stupid分配器”
date: 2019-10-10
description: “BlueStore源码分析之Stupid分配器”

tag: Ceph

前言

前面介绍了BlueStore的BitMap分配器,我们知道新版本的Bitmap分配器的优势在于使用连续的内存空间从而尽可能更多的命中CPU Cache以提高分配器性能。在这里我们了解一下基于区间树的Stupid分配器(类似于Linux Buddy内存管理算法),并对比分析一下其优劣。

目录

伙伴算法

Linux内存管理算法为了能够快速响应请求,尽可能的提高内存利用率同时减少外部内存碎片,引入了伙伴系统算法Buddy-System。该算法将所有的空闲页分组为11个链表,每个链表分别包含1、2、4、8、16、32、64、128、256、512、1024个连续的页框块,每个页框块的第一个内存页的物理地址是该块大小的整数倍。伙伴的特点是:两个块大小相同、两个块地址连续、第一块的第一个页框的物理地址是两个块总大小的整数倍(同属于一个大块,第1块和第2块是伙伴,第3块和第4块是伙伴,但是第2块和第3块不是伙伴)。具体内存分配和内存释放可自行Google。

优点:

  • 较好的解决外部碎片问题,不能完全解决。
  • 针对大内存分配设计,可以快速的分配连续的内存。

缺点:

  • 合并的要求过于严格,只能是满足伙伴关系的块才可以合并。
  • 一块连续的内存中仅有一个页面被占用,就导致整个内存不具备合并的条件。
  • 算法页面连续性差,DMA申请大块连续物理内存空间可能失败,此时需要CMA(Contiguous Memory Allocator, 连续内存分配器)。
  • 浪费空间,可以通过slab、kmem_cache等解决。

数据结构

Stupid分配器使用了区间树组织数据结构,高效管理Extent(offset, length)

每颗区间树的下标为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分配器后,调用者会向Allocator中加入或者删除空闲空间。

插入删除

区间树实现代码:

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

insert函数代码:

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

erase函数代码:

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

最核心的实现是向区间树中插入以及删除区间,代码如下:

区间树插入Extent

回顾第一节伙伴算法,两种合并的方式是有区别的

  • 伙伴算法要求比较严格,参考第一节。
  • Stupid Extent合并比较松散,只要满足两个Extent空间连续就可以。

区间树删除Extent

区间树删除Extent比较简单,在原来Extent删除传入的Extent,然后计算最终Extent是否落入其他区间树,如果落入则从此区间树删除,加入新的区间树。

空间分配

空间分配的函数定义如下:

其中hint是一个很重要的参数,表示分配的起始地址要尽量大于hint的值。

核心流程为4个2层for循环大致为:优先从hint地址依次向高级区间树开始分配长度大于等于want_size的连续空间,如果没有,则优先从hint地址依次向低级区间树开始分配长度大于等于alloc_unit的连续空间(长度会大于alloc_unit)。

简单的空间分配图如下:

详细的空间分配流程图如下:

空间回收

空间释放的函数定义如下:

流程很简单,先加锁,然后循环调用_insert_free插入到对应区间树里面,会涉及到相邻空闲空间的合并,但是会导致分配空间碎片的问题。

优劣分析

CPU Cache

Stupid底层使用BtreeMap来存储一系列的Extent,内存不一定是连续的,同时在分配空间遍历区间树时,虽然区间树里面的Extent是有序的,但是由于内存不一定是连续或者相邻的两个Extent内存跨度可能很大,都会导致CPU-Cache预读不到下一个Extent,从而不能很好的利用CPU-Cache。

Bitmap分配器在BlueStore初始化时就初始化好了3层,而且大小是固定的,同时分配空间是依次顺序分配,从而可以充分的利用CPU-Cache的功能。从而提高分配器的性能。

伪空间碎片

基于Extent的Stupid分配器存在伪空间碎片(物理空间是连续的,但是分配器中却不连续)问题:

一个24K的连续空间,经过6次4K分配和乱序的6次4K释放后,可能会变成8K + 4K + 8K + 4K四块空间。

其中两个4K的区间由于和周边块大小一样,所以落到不同的区间树中,导致很难被合并,24K的连续空间变成了四块不连续空间。

Bitmap分配器由于初始化时就分配好了3层所有内存,而且3层都是有序的的同时分配空间是顺序遍历的,在释放空间的时候设置相应位就可以,不影响连续性,所以不存在这个问题。

据Bitmap作者的性能对比实验来看,Bitmap分配器要好于Stupid,等Bitmap稳定后,可以设置BlueStore的默认分配器为Bitmap。

参考资源

作者:史明亚

您的留言将激励我们越做越好