leveldb 笔记三:Arena 内存管理

Posted by YuanBao on May 2, 2017

不同于 redis 的内存管理方式(利用 jemalloc 或者 tcmalloc 做一层轻封装),LevelDB 根据自己的需求自行定制了一个简单的内存管理器 Arena,这个管理器将在后续 memtable 中被作为成员所使用。当每次向 memtable 中增加 Key/Value 时,memtable 将通过其 Arena 成员来为这些键值对分配空间。你暂时先不需要了解这个详细的过程,我们先讲一下这个简单的 Arena 实现原理。

Allocate 内存分配函数

根据代码来看,一个 Class Arena 拥有以下几个变量:

char* alloc_ptr_;                   // 指向当前 block 内还未使用的起始地址
size_t alloc_bytes_remaining_;      // 当前的 block 里还有多少字节可以使用
std::vector<char*> blocks_;         // 已经申请了的所有的内存块
port::AtomicPointer memory_usage_;  // 总的内存使用量统计

这里面出现了一个非常奇怪的变量类型 AtomicPointer,先不用管这个类型干什么的,现在就把它当做一个普通的 void* 指针就可以了 (有关 AtomicPointer 话题涉及到太多内容,先按下不表)。下图展示了 Arena 是怎么使用这几个变量的:

可以看到,Arena 每次都先从内存中申请一个 block(一般是 4KB,由参数 kBlockSize 定义),然后将其放进 vector 中进行管理。当外部需要调用 Arena 申请内存时,Arena 都从当前这个 block 中,也就是图中的 block 3 中收集可用的内存返回给外部。其中 alloc_ptr 指向的位置就是未使用的内存开始的位置,从 block3 指针到 alloc_ptr 之间的都是已经使用过的内存。而当前块中还未被使用的内存数量即使用 alloc_bytes_remaining_ 来表示。

结合上图来看 Arena 的内存收集函数 Allocate:

inline char* Arena::Allocate(size_t bytes) {
  assert(bytes > 0);
  if (bytes <= alloc_bytes_remaining_) {  // Fast path当前块能装得下这么多bytes
    char* result = alloc_ptr_;
    alloc_ptr_ += bytes;                  // 从当前块中分配
    alloc_bytes_remaining_ -= bytes;      // 计算当前块的剩余字节数
    return result;
  }
  return AllocateFallback(bytes);         //Slow path
}

如果当前块的剩余空间,也就是 alloc_bytes_remaining_ < bytes 时, Arena 就调用 AllocateFallback 来进行后续处理,猜一下也知道 AllocateFallback 肯定会去申请一块新的 block,因为当前的 block 放不下了嘛。

char* Arena::AllocateFallback(size_t bytes) {
  if (bytes > kBlockSize / 4) {              // 如果所需的空间大于块的1/4  
    char* result = AllocateNewBlock(bytes);  // 直接申请一个 bytes 大小的块
    return result;
  }

  //否则,申请一个kBlockSize的块,原来块的剩余空间就被浪费了
  alloc_ptr_ = AllocateNewBlock(kBlockSize); 
  alloc_bytes_remaining_ = kBlockSize;       

  char* result = alloc_ptr_;                 //申请完了进行分配
  alloc_ptr_ += bytes;
  alloc_bytes_remaining_ -= bytes;
  return result;
}

这个时候可以看出了 Arena 内存申请的策略:

  1. 如果当前块中的空间不够,并且需求大于 kBlockSize 的 1/4,那么直接为其单独申请一个块,然后返回(并不修改 alloc_ptralloc_bytes_remaining_ 的值,仍然指向上一个块的剩余空间,如果下次的 Allocate 请求小于 alloc_bytes_remaining_,仍可以从上一个块分配空间;
  2. 如果需求小于 kBlockSize 的 1/4,那么照例申请一个 kBlockSize 大小的新块来存放,上一个块剩下的空间就被浪费了。
  3. 每个块最多后 1/4 的空间会被浪费,这也是灵活性和空间利用率不可兼得。

AllocateAligned 函数

除此之外 Arena 也提供了一个内存对齐的收集函数 AllocateAligned。相比于前面的 Allocate 函数,这个函数首先计算一下为了能对其内存,要多收集多少字节的内存空间,然后再进行空间收集。举个例子说明就很好理解了,假如现在 alloc_ptr_ 指向的内存位置是 13。而当前系统的指针长度是 8,也就是需要 8 字节对齐,那么调用函数 Allocate(20) 如下:

  1. 由于当前的可用空间是从 alloc_ptr_ 也就是 地址 13 开始的,要想让返回给使用者的内存起始指针 result 对齐到 8 字节,这个指针只能指向地址 16。
  2. 因此本次 Allocate(20) 调用需要收集 16 + 20 - alloc_ptr = 23 字节的空间。
  3. 返回的 result 指针将指向地址 16。

明白了这个,再来看 AllocateAligned 的代码就很好理解了:

char* Arena::AllocateAligned(size_t bytes) {
  const int align = (sizeof(void*) > 8) ? sizeof(void*) : 8;
  assert((align & (align-1)) == 0); //align一定是2的幂次
  size_t current_mod = reinterpret_cast<uintptr_t>(alloc_ptr_) & (align-1);
  size_t slop = (current_mod == 0 ? 0 : 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 {
    result = AllocateFallback(bytes);
  }
  assert((reinterpret_cast<uintptr_t>(result) & (align-1)) == 0);
  return result;
}

内存释放

说到这里,可能很多人发现了 Arena 的一个问题,那就是仅有 Allocate 函数,没有 release 函数。其实可以发现 Arena 的 blocks 中保存的所有内存块都将在 Arena 析构的时候全部归还给操作系统的内存管理器。也就是只有在析构的时候才会 delete 掉这些 blocks。这种方式明显会让人觉得反直觉,如果一个内存管理器仅提供 malloc 函数,不提供 free 函数给用户,难道不担心内存使用只增不减吗?

其实这个问题跟 levelDB 本身使用 Arena 的方式有关,也可以说是跟 levelDB 本身的业务场景有关。事实上 Arena 作为 memtable 长度一个成员是与 memtable 具有相同的生命周期的。每次新建一个 memtable 的同时都会新建一个 Arena 管理器,而每次释放一个 memtable 的过程都会析构掉其 Arena 管理器。而 memtable 总是存在于内存中,并且时时刻刻总会存在一个(不考虑 Immutable)。因此,Arena 被设计成这个样子也就可以理解啦。

如果这个时候还不能明白这点,等以后看完 memtable 之后再回来回顾一下就能恍然大悟了。