Leveldb源码 Arena 内存池

发表于2016年2月1日由971774262@qq.com

概述

一个高性能的服务器端程序，内存的使用非常重要。多次的申请和释放引起的内存碎片，一旦碎片到达一定程度，即使剩余内存总量够用，但由于缺乏足够的连续空闲空间，导致内存不够用的假象。为了避免小块内存的频繁分配，最简单的做法就是申请大块的内存，多次分给客户。

一般的策略都是：
小块内存–>从内存池里拿;不够的话，内存池向系统申请新的大块。
大块内存–>直接问系统拿。

如果对这块感兴趣可以自行研究一下：ptmalloc、tcmalloc、Jemalloc、Nginx内存池。

Redis默认使用jemalloc，我们公司的项目也是使用jemalloc。

Redis的Makefile片段：

# Default allocator
ifeq ($(uname_S),Linux)
	MALLOC=jemalloc
else
	MALLOC=libc
endif

# Backwards compatibility for selecting an allocator
ifeq ($(USE_TCMALLOC),yes)
	MALLOC=tcmalloc
endif

ifeq ($(USE_TCMALLOC_MINIMAL),yes)
	MALLOC=tcmalloc_minimal
endif

ifeq ($(USE_JEMALLOC),yes)
	MALLOC=jemalloc
endif

ifeq ($(USE_JEMALLOC),no)
	MALLOC=libc
endif

好，言归正传。leveldb中实现了一个”一次性”的简单的内存池Arena，不是所有的地方都使用了这个内存池，主要是memtable（skiplist）使用。

原理

leveldb用一个vector<char *>来保存所有的内存分配记录，默认每次申请4k的内存，记录下剩余指针和剩余内存字节数。每当有新的申请，如果当前剩余的字节能满足需要，则直接返回给用户;如果不能，对于超过1k的请求，直接跟系统要（new），小于1K的请求，则申请一个新的4k块，从中分配一部分给用户。

但是这样的一个问题就是前一块剩余的部分就浪费了，改进的方法，针对每个block都记录剩余字节，这样就需要遍历来查找合适的block，要付出一些性能的代价。 leveldb的Arena没对每个块做记录做优化，原因很简单：没必要。

LevelDB是一个持久化存储的KV系统，和Redis这种内存型的KV系统不同，LevelDB不会像Redis一样狂吃内存，而是将大部分数据存储到磁盘上。Arena本身的应用场景只是memtable，当Memtable写入的数据占用内存到达指定数量，则自动转换为Immutable Memtable，等待Dump到磁盘中，系统会自动生成新的Memtable供写操作写入新数据。Flush到硬盘后整个memtable就销毁了，内存整个就释放了，没必要为了那点内存做那么复杂的设计，且这样做还会付出一些性能的代价。

若系统安装了tcmalloc，leveldb整体还是会用tcmalloc做内存分配的，
Leveldb的Makefile(build_detect_platform)片段：

    # Test whether tcmalloc is available
    $CXX $CXXFLAGS -x c++ - -o $CXXOUTPUT -ltcmalloc 2>/dev/null  <<EOF
      int main() {}
EOF
    if [ "$?" = 0 ]; then
        PLATFORM_LIBS="$PLATFORM_LIBS -ltcmalloc"
    fi

额，又走远了。接下来让我们一起读一下这个简单的内存池。

代码

arena.h

// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file. See the AUTHORS file for names of contributors.

#ifndef STORAGE_LEVELDB_UTIL_ARENA_H_
#define STORAGE_LEVELDB_UTIL_ARENA_H_

#include <vector>
#include <assert.h>
#include <stddef.h>
#include <stdint.h>
#include "port/port.h"

namespace leveldb {

class Arena {
 public:
  Arena();
  ~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.
  //虽然使用的是AtomicPointer（memory_usage_），但并没有使用原子特性。
  //返回的是一个内存使用量估值（estimate）
  size_t MemoryUsage() const {
	return reinterpret_cast<uintptr_t>(memory_usage_.NoBarrier_Load());
  }

 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
  std::vector<char*> blocks_;

  // Total memory usage of the arena.
  //内存使用量（估值）
  //AtomicPointer原子指针类，leveldb根据各平台分别定义，涉及内存屏障（Memory barrier），有兴趣可以google以下
  port::AtomicPointer memory_usage_;

  // No copying allowed
  Arena(const Arena&);
  void operator=(const Arena&);
};

inline char* Arena::Allocate(size_t bytes) {
  // The semantics of what to return are a bit messy if we allow
  // 0-byte allocations, so we disallow them here (we don't need
  // them for our internal use).
  assert(bytes > 0);
  if (bytes <= alloc_bytes_remaining_) {
	char* result = alloc_ptr_;
	alloc_ptr_ += bytes;
	alloc_bytes_remaining_ -= bytes;
	return result;
  }
  return AllocateFallback(bytes);
}

}  // namespace leveldb

#endif  // STORAGE_LEVELDB_UTIL_ARENA_H_

arena.cc

// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file. See the AUTHORS file for names of contributors.

#include "util/arena.h"
#include <assert.h>

namespace leveldb {

//一般系统的内存页为4K.
static const int kBlockSize = 4096;

Arena::Arena() : memory_usage_(0) {
  alloc_ptr_ = NULL;  // First allocation will allocate a block
  alloc_bytes_remaining_ = 0;
}

Arena::~Arena() {
  for (size_t i = 0; i < blocks_.size(); i++) {
    delete[] blocks_[i];
  }
}

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.
	//申请大于1K直接问系统分配
    char* result = AllocateNewBlock(bytes);
    return result;
  }

  // We waste the remaining space in the current block.
  //申请小于1k，分配4k，再从4k中取所需，记录当前块剩余和剩余指针
  //当然对于分配后的上一个块可能存在浪费（unused）
  alloc_ptr_ = AllocateNewBlock(kBlockSize);
  alloc_bytes_remaining_ = kBlockSize;

  char* result = alloc_ptr_;
  alloc_ptr_ += bytes;
  alloc_bytes_remaining_ -= bytes;
  return result;
}

char* Arena::AllocateAligned(size_t bytes) {
  //几字节内存对齐
  const int align = (sizeof(void*) > 8) ? sizeof(void*) : 8;
  //对齐字节数为2的次幂，2的次幂二进制1的为1。
  assert((align & (align-1)) == 0);   // Pointer size should be a power of 2
  //为内存对齐求余
  size_t current_mod = reinterpret_cast<uintptr_t>(alloc_ptr_) & (align-1);
  //为内存对齐跳过slop字节
  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 {
    // AllocateFallback always returned aligned memory
    result = AllocateFallback(bytes);
  }
  assert((reinterpret_cast<uintptr_t>(result) & (align-1)) == 0);
  return result;
}

char* Arena::AllocateNewBlock(size_t block_bytes) {
  char* result = new char[block_bytes];
  blocks_.push_back(result);
  memory_usage_.NoBarrier_Store(
      reinterpret_cast<void*>(MemoryUsage() + block_bytes + sizeof(char*)));
  return result;
}

}  // namespace leveldb

参考：
http://www.cppblog.com/sandy/archive/2012/03/28/leveldb-trick1.html

此条目发表在leveldb分类目录，贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。