小明思考

高性能服务器端计算
posts - 70, comments - 428, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

那些leveldb使用的奇技淫巧1-内存管理

Posted on 2012-03-28 18:00 小明 阅读(7426) 评论(1)  编辑 收藏 引用 所属分类: C/C++Cloud computing

leveldb(http://code.google.com/p/leveldb) 是Google一款基于key-value的数据库,其作者是google大牛jeff dean的作品,功力深厚,有很多细节的处理值得我们去学习。

背景
我们都知道,对于一个高性能的服务器端程序来说,内存的使用非常重要。C++提供了new/delete来管理内存的申请和释放,但是对于小对象来说,直接使用new/delete代价比较大,要付出额外的空间和时间,性价比不高。
另外,我们也要避免多次的申请和释放引起的内存碎片。一旦碎片到达一定程度,即使剩余内存总量够用,但由于缺乏足够的连续空闲空间,导致内存不够用的假象。
c++ STL为了避免内存碎片,实现一个复杂的内存池,leveldb中则没有那么复杂,只是实现了一个"一次性"内存池Arena。
在leveldb里面,并不是所有的地方都使用了这个内存池,主要是memtable使用,主要是用于临时存放用户的更新数据,由于更新的数据可能很小,所以这里使用内存池就很合适。

原理
为了避免小对象的频繁分配,需要减少对new的调用,最简单的做法就是申请大块的内存,多次分给客户。
leveldb用一个vector<char *>来保存所有的内存分配记录,默认每次申请4k的内存,记录下剩余指针和剩余内存字节数,每当有新的申请,如果当前剩余的字节能满足需要,则直接返回给用户,如果不能,对于超过1k的请求,直接new返回,小于1K的请求,则申请一个新的4k块,从中分配一部分给用户。
但是这样的一个问题就是当前块剩余的部分就浪费了,改进的方法,针对每个block都记录剩余字节,这样就需要遍历来查找合适的block,要付出一些性能的代价。google的做法是浪费就浪费吧:-)
至于释放,需要释放整个内存池来释放所占内存,这个和leveldb的需求有关,memtable不需要释放单次内存,flush到硬盘后整个memtable销毁。





具体实现
让我们来看看具体实现。

定义:<util/arena.h>
class Arena {
 
public:
  Arena();
  
~Arena();

  
//分配内存
  char* Allocate(size_t bytes);

  
//对齐分配
  char* AllocateAligned(size_t bytes);

  
// 当前的内存使用量
  size_t MemoryUsage() const {
    
return blocks_memory_ + blocks_.capacity() * sizeof(char*);
  }

 
private:
  
//分配内存,不能直接分配
  char* AllocateFallback(size_t bytes);
  
//新生成一个BLOCK
  char* AllocateNewBlock(size_t block_bytes);

  
//当前free指针
  char* alloc_ptr_;
  
//当前BLOCK剩余字节大小
  size_t alloc_bytes_remaining_;

  
//保存所有分配的内存
  std::vector<char*> blocks_;

  
//已经分配的总内存大小
  size_t blocks_memory_;

  
//禁止copy构造
  Arena(const Arena&);
  
void operator=(const Arena&);
};

实现<util/arena..cc>

//默认BLOCK size
static const int kBlockSize = 4096;

inline 
char* Arena::Allocate(size_t bytes) {
  
//如果申请量能满足需要,直接分配
  if (bytes <= alloc_bytes_remaining_) {
    
char* result = alloc_ptr_;
    alloc_ptr_ 
+= bytes;
    alloc_bytes_remaining_ 
-= bytes;
    
return result;
  }
  
return AllocateFallback(bytes);
}

char* Arena::AllocateFallback(size_t bytes) {
  
//大于1KB,直接分配一个新的BLOCK
  if (bytes > kBlockSize / 4) {
    
char* result = AllocateNewBlock(bytes);
    
return result;
  }

  
//申请一个新的BLOCK,浪费少于当前申请bytes的剩余空间 
  alloc_ptr_ = AllocateNewBlock(kBlockSize);
  alloc_bytes_remaining_ 
= kBlockSize;

  
//设置free指针和剩余大小
  char* result = alloc_ptr_;
  alloc_ptr_ 
+= bytes;
  alloc_bytes_remaining_ 
-= bytes;
  
return result;
}

其他
对于那些不使用arena来分配的内存,怎么去优化呢?leveldb使用tcmalloc进行优化。tcmalloc是google-perftool中的一个工具,用于替代glibc的默认new实现。
看看leveldb的Makefile就知道,使用tcmalloc很简单,只需要加入-ltcmalloc重新编译就可以了。

# If Google Perf Tools are installed, add compilation and linker flags
# (see http:
//code.google.com/p/google-perftools/)
ifeq ($(GOOGLE_PERFTOOLS), 1)
GOOGLE_PERFTOOLS_LDFLAGS
=-ltcmalloc
else
GOOGLE_PERFTOOLS_LDFLAGS
=
endif

顺便提一下,redis使用的是jemalloc来提高malloc的效率

这里有一个性能比较,看起来tcmalloc的性能最好。

Allocator   CPU Time (min)  Commit Memory  Region Support  
MSVC malloc       2:59          543 MB              No
ptmalloc      2:01          480 MB         Yes
ned malloc        2:01          652 MB         Yes
tc malloc         1:39          454 MB         No
je malloc     1:59          496 MB         No

请参考:


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理