Posted on 2012-03-28 18:00
小明 阅读(9043)
评论(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
请参考: