LevelDB内存管理器Arena

本文主要介绍开源项目LevelDB中的内存管理器（也可称为内存池）Arena的实现，LevelDB的大部分内存管理依赖于C++语言的默认实现，也就是不对内存进行管理。只是在MemTable的实现中用到了一个简单的内存管理器(Arena)。

Arena目的

LevelDB中MemTable的内部实现Skip List写入时，需要分配新节点，大量节点的直接分配（调用malloc/free或者new/delete）可能会带来较多的内存碎片（大量很小的键值对插入），且每个调用平均的开销比较大影响运行效率，关乎数据库的性能。

因此，LevelDB为每个MemTable都绑定了一个Arena来管理内存，在MemTable进行minor compact后，MemTable销毁时进行统一释放。

设计思想

Arena的内存分配的方式，首先使用new预分配一块比较大的内存，需要使用小块内存时，从这块大内存里面继续分配，此时分配只需要移动指针或者更新变量的，非常高效。

主要涉及的变量：

// 当前能使用内存的起始位置（已经通过new分配下来了）
char* alloc_ptr_;
// 当前已申请的剩余字节数
size_t alloc_bytes_remaining_;
// 保存每次通过new分配下来的内存起始位置
std::vector<char*> blocks_;

1）需要分配的字节数不大于当前已申请的剩余字节数，直接从剩余的字节中分配，调整alloc_ptr_及alloc_bytes_remaining_的值；

2）需要分配的字节数大于当前已申请的剩余字节数，且大于1KB，通过new向操作系统申请需要的内存空间，blocks_保存起始地址，alloc_ptr_及alloc_bytes_remaining_不变；

3）需要分配的字节数大于当前已申请的剩余字节数，且不大于1KB，通过new向操作系统申请4KB内存空间（之前已申请的剩余字节数将浪费），blocks_保存起始地址，并从该4KB内存中拿出需要的内存空间，调整alloc_ptr_及alloc_bytes_remaining_的值。该种情况将造成一定内存空间的浪费。

对于释放内存，Arena不支持单独释放某个块，而是只能销毁整个Arena。这是和Arena的使用场景有关的，Arena存储的是内存中的键值对，对于LevelDB来说，只有插入操作，没有实际的删除操作，所以不需要释放一块内存。而当一个Arena里的数据dump到SSTable后，只需要释放Arena里所有的内存。

Arena的内存分配如下图所示（转自知乎）：

结构声明

// from LevelDB util/arena.h
class Arena {
 public:
  Arena();

  Arena(const Arena&) = delete;
  Arena& operator=(const Arena&) = delete;

  ~Arena();

  // Return a pointer to a newly allocated memory block of "bytes" bytes.
  char* Allocate(size_t bytes);

  // Allocate memory with the normal alignment guarantees provided by malloc.
  char* AllocateAligned(size_t bytes);

  // Returns an estimate of the total memory usage of data allocated
  // by the arena.
  size_t MemoryUsage() const {
    return memory_usage_.load(std::memory_order_relaxed);
  }

 private:
  char* AllocateFallback(size_t bytes);
  char* AllocateNewBlock(size_t block_bytes);

  // Allocation state
  // 剩余能分配内存的起始地址
  char* alloc_ptr_;
  // 剩余能分配的内存字节数
  size_t alloc_bytes_remaining_;

  // Array of new[] allocated memory blocks
  // 已分配的块的指针保存在一个vector中
  std::vector<char*> blocks_;

  // Total memory usage of the arena.
  //
  // TODO(costan): This member is accessed via atomics, but the others are
  //               accessed without any locking. Is this OK?
  std::atomic<size_t> memory_usage_;
};

接口实现分析

// from LevelDB util/arena.cc
// 分配内存的函数
inline char* Arena::Allocate(size_t bytes) {
    // 如果当前块剩余的内存足够，更新free指针，返回内存指针
    if (bytes <= alloc_bytes_remaining_) {
        char* result = alloc_ptr_;
        alloc_ptr_ += bytes;
        alloc_bytes_remaining_ -= bytes;
        return result;
    }
    // 否则退化的方式分配
    return AllocateFallback(bytes);
}

// 检查要分配的size是否大于1/4的block(也就是1K)，
// 若大于则直接new所需大小的内存，将指针保存在vector中并返回内存指针。
// 从这里可以看出，vector保存的内存块的指针大小可能>4K，也就是对大内存块直接分配。
// 前面两个条件若都不满足，则需要new一个基本块(=4K)，
// 将new出来的新块作为当前块，从这块当中分配内存并调整当前内存指针位置。
// 原来当前块的剩余内存就被浪费掉了。
char* Arena::AllocateFallback(size_t bytes) {
  if (bytes > kBlockSize / 4) {
    // Object is more than a quarter of our block size.  Allocate it separately
    // to avoid wasting too much space in leftover bytes.
    char* result = AllocateNewBlock(bytes);
    return result;
  }

  // We waste the remaining space in the current block.
  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) {
  char* result = new char[block_bytes];
  blocks_.push_back(result);
  // memory_usage_为整个内存池使用内存的总大小（不），这里只计算了已分配内存块的总大小和
  // 存储各个内存块指针所用的空间。并未计算alloc_ptr_和alloc_bytes_remaining_
  // 等数据成员的大小。
  memory_usage_.fetch_add(block_bytes + sizeof(char*),  // sizeof(char*)可理解为指vector新增的元素内存
                          std::memory_order_relaxed);
  return result;
}

// 因为 SkipList 中会涉及一些原子操作，所以 AllocateAligned
// 分配的内存需要和指针的大小（一般是 8 字节）对齐
// 对齐含义：分配内存的起始地址是指针的大小的倍数
char* Arena::AllocateAligned(size_t bytes) {
  const int align = (sizeof(void*) > 8) ? sizeof(void*) : 8;
  static_assert((align & (align - 1)) == ,
                "Pointer size should be a power of 2");
  // 取模运算转化成位运算公式:a%(2^n) 等价于
  // a&(2^n-1),而&操作比%操作具有更高的效率
  // 求余运算要用到除法，除法是比较费时的。因此高性能的程序需要对求余进行转换。
  size_t current_mod = reinterpret_cast<uintptr_t>(alloc_ptr_) &
                       (align - 1);  // 计算出alloc_ptr_ % align
  size_t slop =
      (current_mod ==  ?  : align - current_mod);  // 内存对齐还需要向前移动的大小
  size_t needed = bytes + slop;
  char* result;
  if (needed <= alloc_bytes_remaining_) {
    result = alloc_ptr_ + slop;
    alloc_ptr_ += needed;
    alloc_bytes_remaining_ -= needed;
  } else {
    // AllocateFallback always returned aligned memory
    // 操作系统底层决定的（每次均返回new出来的内存起始地址），分配内存遵循字节对齐
    result = AllocateFallback(bytes);
  }
  assert((reinterpret_cast<uintptr_t>(result) & (align - 1)) == );
  return result;
}

参考

• LevelDB源码分析之内存管理类arena https://blog.csdn.net/chdhust/article/details/51869270

• operator new在C++中的各种写法 https://blog.csdn.net/maryfei/article/details/107492073

• [LevelDB] 基础1：中庸之道 —— arena内存管理 https://zhuanlan.zhihu.com/p/210100808