levelDB源码剖析(3)--levelDB的内存管理策略

levelDB的内存管理策略

---

levelDB的内存管理类Arena

源代码位置：utils/arena.cc utils/arena.h

对于数据库而言，内存管理策略是十分重要的，因为其正是需要为存入的数据分配内存，倘若直接使用new/delete这样每次插入数据都单独去分配内存，效率是很低的，同时由于每条插入的数据的大小并不一致，导致会出现许多的内存碎片。

对于levelDB这样一个billion级别的数据库，显然其不能采取这样的策略。

在levelDB中，由于只有MemTable位于内存且需要频繁的插入，所以它最需要内存管理，levelDB中用于内存管理的类为Arena，每个MemTable都绑定一个Arena。而其余的部分则直接使用new/delete，因为这些部分要么是不频繁，要么是块本身就很大。

Arena类

基本思想：先分配出一大块内存，然后当需要用到内存时，就在这一大块内存中移动指针，这样就能解决小块内存频繁调用new和内存碎片的问题，不过缺点是有一部分内存被浪费掉。

我们可以先来看一下arena类的头文件捏。从头文件中可以很明显的看到其用于内存分配的方法就是公有函数Allocate和AllocateAligned，区别是后者提供内存对齐，这对效率也有提升。

头文件

// utils/arena.h

class Arena
{
public:
    Arena();                                  //默认构造函数
    Arena(const Arena &) = delete;            //关闭复制构造函数
    Arena &operator=(const Arena &) = delete; //关闭使用=的拷贝构造函数
    ~Arena();                                 //析构函数

    //返回一个指针指向新分配的内存区域，即内部的分配内存的方法
    char *Allocate(size_t bytes);

    //同Allocate，但是提供了内存对齐策略
    char *AllocateAligned(size_t bytes);

    //返回目前从内存中申请的内存大小，由于memory_usage_是原子操作
    //此处的memory_order_relaxed表示宽松内存序，即任何一个线程可以任意更新
    //不用同步到其他线程中，下一个访问该元素的线程获取到更新之后的值
    size_t MemoryUsage() const
    {
        return memory_usage_.load(std::memory_order_relaxed);
    }

private:
    char *AllocateFallback(size_t bytes);       //获取新分配的内存，被AllocateAligned和Allocate调用
    char *AllocateNewBlock(size_t block_bytes); //new函数的包装，被AllocateFallback调用

    char *alloc_ptr_;                  //当前内存块未使用内存的首地址
    size_t alloc_bytes_remaining_;     //当前内存块中未使用空间的大小
    std::vector<char *> blocks_;       //存储每一次向系统请求分配的内存块的指针
    std::atomic<size_t> memory_usage_; //记录已申请全部内存使用的数目，注意此操作是原子的
};

头文件定义了Arena这个类，在类中只有3个公有方法，分别用于返回小内存、对齐的小内存、当前类占用的空间。

实现文件

分析完了头文件，我们接下来看一下它的cpp实现。

/*=============类的构造析构等基础函数=============*/

static const int kBlockSize = 4096; //一个内存块的大小

// 构造函数，默认的构造函数直接对内部的几个元素进行初始化
Arena::Arena()
    : alloc_ptr_(nullptr), alloc_bytes_remaining_(0), memory_usage_(0) {}

// 析构函数，注意，由于类中存在一个vector数组存储了每次分配的内存的块的指针
// 所以析构的时候遍历这个数组然后逐个delete
Arena::~Arena()
{
    for (size_t i = 0; i < blocks_.size(); i++)
    {
        delete[] blocks_[i];
    }
}

/*=============公有接口=============*/

// 分配小内存的函数，这个函数是此类对外的接口，被写成内联函数效率更高
inline char *Arena::Allocate(size_t bytes)
{
    // 首先，断言申请的内存数目是否合法
    assert(bytes > 0);
    // 当从内存申请的整块中仍然存在空间时，就直接从这个块中分配
    if (bytes <= alloc_bytes_remaining_)
    {
        char *result = alloc_ptr_;
        alloc_ptr_ += bytes;
        alloc_bytes_remaining_ -= bytes;
        return result;
    }
    // 否则调用AllocateFallback进行分配（从内存中申请空间去分配）
    return AllocateFallback(bytes);
}

// 采用对齐的方式去分配内存，只比Allocate多出计算需要分配内存的步骤
char *Arena::AllocateAligned(size_t bytes)
{
    // 首先设置对齐的字节数，(sizeof(void *)可以计算出当前机器的每个指针的字节数
    // 最多8字节对齐，当当前机器指针的字节数不足8字节时，会使用当前机器的字节数
    const int align = (sizeof(void *) > 8) ? sizeof(void *) : 8;

    // 静态断言，在编译时执行断言
    // a&(a-1)的功能是去掉右边的1(二进制)，所以当不是2的幂次方时，去掉1后就非0
    static_assert((align & (align - 1)) == 0,
                  "Pointer size should be a power of 2");

    // 下面这里的位运算等价于求余运算
    // 因为上面这个断言已经确保了align是2个幂次方，因此align-1是一个右侧均为1的掩模
    // 两者相与的结果就可以快速求出alloc_ptr_%align
    // 但注意，此时两者能够等价的重要原因是align是2的幂次方
    // 此处还有强制类型转换，也就是把取模结果转换成uintptr_t
    size_t current_mod = reinterpret_cast<uintptr_t>(alloc_ptr_) & (align - 1);

    // 当取模结果不是0就表示需要分配的内存是2的整数幂，所以需要额外分配一些内存
    size_t slop = (current_mod == 0 ? 0 : align - current_mod);

    // 计算出总的需要的内存
    size_t needed = bytes + slop;

    /*-------- 至此，计算出需要对齐时分配的内存后，就与Allocate无异 --------*/

    char *result;

    // 当从内存申请的整块中仍然存在空间时，就直接从这个块中分配
    if (needed <= alloc_bytes_remaining_)
    {
        result = alloc_ptr_ + slop;
        alloc_ptr_ += needed;
        alloc_bytes_remaining_ -= needed;
    }
    else
    {
        // 此处存在一点点区别，AllocateFallback申请的参数时bytes而不是对齐后的need
        // 这是因为AllocateFallback调用的是new/delete，总是内存对齐的
        result = AllocateFallback(bytes);
    }

    // 这里再做一下断言，保证对齐
    assert((reinterpret_cast<uintptr_t>(result) & (align - 1)) == 0);
    return result;
}

/*=============私有接口=============*/

// 私有方法：回调函数，用于当当前块内内存不足时申请内存的策略
char *Arena::AllocateFallback(size_t bytes)
{
    // 当需要的内存超过kBlockSize的1/4，（默认1kb时），申请和bytes相同大小的内存
    // 这样做是因为当需要用到的内存已经超过块大小的1/4了，那么之前剩余的块可能还有不少
    // 如果新分配一个块那么就可能会浪费比较多的内存
    if (bytes > kBlockSize / 4)
    {
        char *result = AllocateNewBlock(bytes);
        return result;
    }

    // 当需要的内存不足kBlockSize的1/4，（默认1kb时），就申请一个整个的块（默认4kb）
    // 然后从这里面分配内存
    // 但注意，进入到此函数里只说明原来的块不足以分配现在需要的内存，但其可能仍然剩余内存
    // 此处的策略是直接把原来的内存块中可能剩余的内存给浪费掉
    // 毕竟此时需要分配的内存不到1/4个块，说明原来的块也剩下不了多少内存了
    alloc_ptr_ = AllocateNewBlock(kBlockSize);

    // 下面这几部就是分配了一个块后做块内的内存分配
    alloc_bytes_remaining_ = kBlockSize;
    char *result = alloc_ptr_;
    alloc_ptr_ += bytes;
    alloc_bytes_remaining_ -= bytes;
    return result;
}

// 私有方法：向系统申请内存
char *Arena::AllocateNewBlock(size_t block_bytes)
{
    // 就是对new的一层包装，同时更新一下类内的参数
    char *result = new char[block_bytes];
    blocks_.push_back(result);
    memory_usage_.fetch_add(block_bytes + sizeof(char *),
                            std::memory_order_relaxed);
    return result;
}

实际上总体来说思路如下:

1、当调用AllocateAligned或Allocate时，先判断当前分配内存块中剩余的内存是否有足够的内存去分配新的内存（以及计算内存对齐）；如果足以容纳，则直接从当前内存块中提取内存作为所需内存使用。若是不足以容纳则调用AllocateFallback去申请内存并分配。

2、在AllocateFallback中，先判断需要申请的内存是否大于1K，若是大于1K，直接AllocateNewBlock向系统申请足够的内存以供使用。若是小于1K，则调用AllocateNewBlock分配一个块，并在这个块中分配需要的内存。

3、AllocateNewBlock使用系统new操作符向系统申请内存，并更新类内参数。当所分配的内存为4kb时，会将这个申请的内存作为新的内存块(此时旧的内存块中即使还有内存未使用，也不会再拿来使用，因为alloc_ptr_会指向新申请的内存块)。然后再向新申请的内存块提取内存以供使用。

这里Level对于小于1K的内存申请才向内存池提取内存，主要是连续多次申请小的内存会容易导致内存碎片，影响系统的性能。并且多次的new和delete比较耗时(不断的构造和析构)，会付出额外的空间和时间。

---

总结部分

方法/变量	作用
Arena()	构造函数
~Arena()	析构函数
char* Allocate(size_t bytes)	提供bytes大小的内存
char* AllocateAligned(size_t bytes)	提供内存对齐的bytes大小的内存
size_t MemoryUsage() const	返回当前申请的内存大小
char* AllocateFallback(size_t bytes)	当块中内存不够时向系统申请内存接口，由Allocate或AllocateAligned调用
char* AllocateNewBlock(size_t block_bytes)	系统new的包装函数，由AllocateFallback调用
alloc_ptr_	当前内存块中未使用空间的首地址
alloc_bytes_remaining_	当前内存块中剩余的空间
blocks_	new出来的内存的首地址组成的vector数组
memory_usage_	向系统已申请的内存大小

编程小技巧

a & (a - 1)：去掉a在二进制表示中最右边的1

A & (B - 1) = A % B：此公式仅在B是2的幂次方时成立