Posted on 2012-03-28 18:00
小明 閱讀(9211)
評論(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
請參考: