Posted on 2012-03-28 18:00
小明 閱讀(9211)
評論(1) 編輯 收藏 引用 所屬分類:
C/C++ 、
Cloud computing
leveldb(
http://code.google.com/p/leveldb) 是Google一款基于key-value的數(shù)據(jù)庫，其作者是google大牛jeff dean的作品，功力深厚，有很多細節(jié)的處理值得我們?nèi)W(xué)習(xí)。
背景我們都知道，對于一個高性能的服務(wù)器端程序來說，內(nèi)存的使用非常重要。C++提供了new/delete來管理內(nèi)存的申請和釋放，但是對于小對象來說，直接使用new/delete代價比較大，要付出額外的空間和時間，性價比不高。
另外，我們也要避免多次的申請和釋放引起的內(nèi)存碎片。一旦碎片到達一定程度，即使剩余內(nèi)存總量夠用，但由于缺乏足夠的連續(xù)空閑空間，導(dǎo)致內(nèi)存不夠用的假象。
c++ STL為了避免內(nèi)存碎片，實現(xiàn)一個復(fù)雜的內(nèi)存池，leveldb中則沒有那么復(fù)雜，只是實現(xiàn)了一個"一次性"內(nèi)存池Arena。
在leveldb里面，并不是所有的地方都使用了這個內(nèi)存池，主要是memtable使用，主要是用于臨時存放用戶的更新數(shù)據(jù)，由于更新的數(shù)據(jù)可能很小，所以這里使用內(nèi)存池就很合適。
原理為了避免小對象的頻繁分配，需要減少對new的調(diào)用，最簡單的做法就是申請大塊的內(nèi)存，多次分給客戶。
leveldb用一個vector<char *>來保存所有的內(nèi)存分配記錄，默認每次申請4k的內(nèi)存，記錄下剩余指針和剩余內(nèi)存字節(jié)數(shù)，每當(dāng)有新的申請，如果當(dāng)前剩余的字節(jié)能滿足需要，則直接返回給用戶，如果不能，對于超過1k的請求，直接new返回，小于1K的請求，則申請一個新的4k塊，從中分配一部分給用戶。
但是這樣的一個問題就是當(dāng)前塊剩余的部分就浪費了，改進的方法，針對每個block都記錄剩余字節(jié)，這樣就需要遍歷來查找合適的block，要付出一些性能的代價。google的做法是浪費就浪費吧：-）
至于釋放，需要釋放整個內(nèi)存池來釋放所占內(nèi)存，這個和leveldb的需求有關(guān),memtable不需要釋放單次內(nèi)存，flush到硬盤后整個memtable銷毀。
具體實現(xiàn)讓我們來看看具體實現(xiàn)。
定義：<util/arena.h>
class Arena {
public:
Arena();
~Arena();
//分配內(nèi)存
char* Allocate(size_t bytes);
//對齊分配
char* AllocateAligned(size_t bytes);
// 當(dāng)前的內(nèi)存使用量
size_t MemoryUsage() const {
return blocks_memory_ + blocks_.capacity() * sizeof(char*);
}
private:
//分配內(nèi)存，不能直接分配
char* AllocateFallback(size_t bytes);
//新生成一個BLOCK
char* AllocateNewBlock(size_t block_bytes);
//當(dāng)前free指針
char* alloc_ptr_;
//當(dāng)前BLOCK剩余字節(jié)大小
size_t alloc_bytes_remaining_;
//保存所有分配的內(nèi)存
std::vector<char*> blocks_;
//已經(jīng)分配的總內(nèi)存大小
size_t blocks_memory_;
//禁止copy構(gòu)造
Arena(const Arena&);
void operator=(const Arena&);
};
實現(xiàn)<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，浪費少于當(dāng)前申請bytes的剩余空間
alloc_ptr_ = AllocateNewBlock(kBlockSize);
alloc_bytes_remaining_ = kBlockSize;
//設(shè)置free指針和剩余大小
char* result = alloc_ptr_;
alloc_ptr_ += bytes;
alloc_bytes_remaining_ -= bytes;
return result;
}
其他對于那些不使用arena來分配的內(nèi)存，怎么去優(yōu)化呢？leveldb使用tcmalloc進行優(yōu)化。tcmalloc是google-perftool中的一個工具，用于替代glibc的默認new實現(xiàn)。
看看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
請參考: