10.1 基本原理
緩存機制一直是性能優(yōu)化的重要方式碰凶，LevelDB在讀取SSTable烈涮、Block中均采用了緩存烈疚。
LevelDB的緩存機制可謂“白手起家”适揉，由最下層的Hash類到最上層的TableCache都由作者編寫完成留攒。先來看下類圖：
- LRUHandle代表緩存記錄，
- HandleTable是專門用于存儲LRUHandle的哈希表嫉嘀，
- LRUCache則是基于HandleTable實現(xiàn)的LRU緩存炼邀，
- SharedLRUCache繼承自Cache抽象類，其內(nèi)部實現(xiàn)了簡單的一級緩存剪侮，并通過LRUCache實現(xiàn)二級緩存拭宁，
- TableCache則是SSTable文件緩存洛退。
10.2 LRUHandle
// An entry is a variable length heap-allocated structure. Entries
// are kept in a circular doubly linked list ordered by access time.
struct LRUHandle {
void* value;
void(*deleter)(const Slice&, void* value);
LRUHandle* next_hash;
LRUHandle* next;
LRUHandle* prev;
size_t charge; // TODO(opt): Only allow uint32_t?
size_t key_length;
uint32_t refs;
uint32_t hash; // Hash of key(); used for fast sharding and comparisons
char key_data[1]; // Beginning of key
Slice key() const {
// For cheaper lookups, we allow a temporary Handle object
// to store a pointer to a key in "value".
if (next == this) {
return *(reinterpret_cast<Slice*>(value));
}
else {
return Slice(key_data, key_length);
}
}
};
關(guān)于LRUHandle說明如下：
- Deleter：刪除器。當refs == 0時杰标，調(diào)用deleter完成value對象釋放兵怯。
- char Key_data[1]。實際上腔剂，這只是一個指向Key值的指針媒区，指向內(nèi)存的實際大小由Key值的長度決定。
- Next\prev\next_hash掸犬。Next\prev用于雙向鏈表袜漩，而next_hash則是指向相同hash值的下一條記錄。
另外湾碎，這是LRUCache專用的結(jié)構(gòu)宙攻，因此名為LRUHandle。
10.3 HandleTable
HandleTable其實應(yīng)該叫做LRUHandleTable介褥，它只支持LRUHandle記錄座掘。
class HandleTable {
public:
LRUHandle* Lookup(const Slice& key, uint32_t hash);
LRUHandle* Insert(LRUHandle* h);
LRUHandle* Remove(const Slice& key, uint32_t hash);
};
Insert時，如果存在相同hash值柔滔、相同key值的記錄存在溢陪，插入新記錄，并返回之前的記錄廊遍。
HandleTable是哈希表，但比較奇怪的是贩挣，查找喉前、插入、刪除動作除了傳入key外王财，還要自備hash值卵迂。這樣做是因為，hash值除了HandleTable中使用绒净，在外部做多級緩存時也需要见咒，后面會提到。
HandleTable內(nèi)部維護了一個LRUHandle*的數(shù)組挂疆，默認大小為4改览。隨著插入數(shù)據(jù)的增多，該數(shù)組會自動增長缤言，并將原數(shù)組中的數(shù)據(jù)重新分配到新的數(shù)組中宝当。Resize的觸發(fā)條件為元素個數(shù)>數(shù)組大小。
10.4 LRUCache
有了LRUHandle胆萧、HandleTable庆揩，我們僅僅具備了一個可以存儲LRUHandle結(jié)構(gòu)的Hash表。和LRU緩存并沒有建立聯(lián)系，那么订晌，如何通過上面的結(jié)構(gòu)完成LRU緩存(LRUCache)呢?
如果由我來完成LRUCache虏辫，那么會考慮如下問題：
- LRU的判定標準是什么？是指定時間內(nèi)使用的數(shù)據(jù)锈拨、最近使用的N條數(shù)據(jù)砌庄，還是通過其他設(shè)定規(guī)則判定LRU？
- Hash表是key值無序的推励，怎樣體現(xiàn)每條記錄的先后順序鹤耍？
- 性能上如何保證？
來看作者的實現(xiàn)：
class LRUCache {
public:
LRUCache();
~LRUCache();
// Separate from constructor so caller can easily make an array of LRUCache
void SetCapacity(size_t capacity) { capacity_ = capacity; }
// Like Cache methods, but with an extra "hash" parameter.
Cache::Handle* Insert(const Slice& key, uint32_t hash,
void* value, size_t charge,
void(*deleter)(const Slice& key, void* value));
Cache::Handle* Lookup(const Slice& key, uint32_t hash);
void Release(Cache::Handle* handle);
void Erase(const Slice& key, uint32_t hash);
private:
void LRU_Remove(LRUHandle* e);
void LRU_Append(LRUHandle* e);
void Unref(LRUHandle* e);
// Initialized before use.
size_t capacity_;
// mutex_ protects the following state.
port::Mutex mutex_;
size_t usage_;
uint64_t last_id_;
// Dummy head of LRU list.
// lru.prev is newest entry, lru.next is oldest entry.
LRUHandle lru_;
HandleTable table_;
};
回答上面的問題：
- SetCapacity指定的緩存數(shù)量验辞，判定標準為最近使用的N條記錄稿黄。
- Lru_維護了雙向鏈表，lru_.prev指向最新的數(shù)據(jù)跌造，lru_.next指向最舊的數(shù)據(jù)杆怕。
- Table_針對每條記錄的查找時間為O(1), 插入時如不執(zhí)行數(shù)組大小重分配，時間復(fù)雜度也為O(1).lru_的插入壳贪、刪除時間均為O(1)陵珍。
- LRUCache的插入、刪除動作除了操作table_外违施，還要操作lru_互纯，其他并無特殊之處。
10.5 SharedLRUCache
請看類圖1.1磕蒲，SharedLRUCache并不繼承自LRUCache留潦，而是采用組合的方式使用；SharedLRUCache繼承了Cache辣往，這說明SharedLRUCache才是作者認為外部可用的緩存兔院。
SharedLRUCache自身建立了一級緩存，隨后通過調(diào)用LRUCache完成二級緩存站削。
static const int kNumShardBits = 4;
static const int kNumShards = 1 << kNumShardBits; //16
class ShardedLRUCache : public Cache {
private:
//LRUCache數(shù)組
LRUCache shard_[kNumShards];
port::Mutex id_mutex_;
uint64_t last_id_;
static inline uint32_t HashSlice(const Slice& s) {
return Hash(s.data(), s.size(), 0);
}
static uint32_t Shard(uint32_t hash) {
return hash >> (32 - kNumShardBits);
}
public:
explicit ShardedLRUCache(size_t capacity)
: last_id_(0) {
const size_t per_shard = (capacity + (kNumShards - 1)) / kNumShards;
for (int s = 0; s < kNumShards; s++) {
shard_[s].SetCapacity(per_shard);
}
}
virtual ~ShardedLRUCache() { }
virtual Handle* Insert(const Slice& key, void* value, size_t charge,
void(*deleter)(const Slice& key, void* value)) {
const uint32_t hash = HashSlice(key);
return shard_[Shard(hash)].Insert(key, hash, value, charge, deleter);
}
virtual Handle* Lookup(const Slice& key) {
const uint32_t hash = HashSlice(key);
return shard_[Shard(hash)].Lookup(key, hash);
}
virtual void Release(Handle* handle) {
LRUHandle* h = reinterpret_cast<LRUHandle*>(handle);
shard_[Shard(h->hash)].Release(handle);
}
virtual void Erase(const Slice& key) {
const uint32_t hash = HashSlice(key);
shard_[Shard(hash)].Erase(key, hash);
}
virtual void* Value(Handle* handle) {
return reinterpret_cast<LRUHandle*>(handle)->value;
}
virtual uint64_t NewId() {
MutexLock l(&id_mutex_);
return ++(last_id_);
}
};
可以看到坊萝，SharedLRUCache維護了一個大小為16的LRUCache數(shù)組，通過hash值的高4位進行分組许起，實現(xiàn)一級緩存十偶，進而再調(diào)用LRUCache實現(xiàn)二級緩存。這樣做和采用一個LRUCache實現(xiàn)的好處是降低了數(shù)據(jù)再分配园细、重組的幾率扯键，提升了性能。
但嚴格來講珊肃，SharedLRUCache實現(xiàn)并不是精確的LRU緩存荣刑，因為如果hash值不夠均勻馅笙，大量的數(shù)據(jù)被聚集到一個LRUCache中時，該緩存被頻繁換入換出厉亏，而更老的其他LRUCache中的數(shù)據(jù)卻仍然得以保留董习。當然，對于一般應(yīng)用來說爱只，SharedLRUCache具備統(tǒng)計上的LRU皿淋。
10.6 TableCache
TableCache是SSTable文件緩存，LevelDB的所有SSTable文件查找均通過該類完成恬试，該類在LevelDB中只有一個實例窝趣。來看接口聲明：
Iterator* NewIterator(const ReadOptions& options,
uint64_t file_number,
uint64_t file_size,
Table** tableptr = NULL);
// Evict any entry for the specified file number
void Evict(uint64_t file_number);
NewIterator通過傳入指定的文件編號返回Iterator，該Iterator提供了完整的數(shù)據(jù)庫文件查詢功能训柴。
Iterator* TableCache::NewIterator(const ReadOptions& options,
uint64_t file_number,
uint64_t file_size,
Table** tableptr) {
if (tableptr != NULL) {
*tableptr = NULL;
}
//從緩存中查找指定文件
char buf[sizeof(file_number)];
EncodeFixed64(buf, file_number);
Slice key(buf, sizeof(buf));
Cache::Handle* handle = cache_->Lookup(key);
if (handle == NULL) //指定文件不存在哑舒，打開文件并添加至緩存
{
std::string fname = TableFileName(dbname_, file_number);
RandomAccessFile* file = NULL;
Table* table = NULL;
Status s = env_->NewRandomAccessFile(fname, &file);
if (s.ok()) {
s = Table::Open(*options_, file, file_size, &table);
}
if (!s.ok()) {
assert(table == NULL);
delete file;
// We do not cache error results so that if the error is transient,
// or somebody repairs the file, we recover automatically.
return NewErrorIterator(s);
}
TableAndFile* tf = new TableAndFile;
tf->file = file;
tf->table = table;
handle = cache_->Insert(key, tf, 1, &DeleteEntry);
}
//根據(jù)table構(gòu)建迭代器并返回
Table* table = reinterpret_cast<TableAndFile*>(cache_->Value(handle))->table;
Iterator* result = table->NewIterator(options);
result->RegisterCleanup(&UnrefEntry, cache_, handle);
if (tableptr != NULL) {
*tableptr = table;
}
return result;
}
Evict含義為”驅(qū)逐“，當Compaction時幻馁，過期的文件將會被移除洗鸵，此時調(diào)用Evict從移除該文件緩存。
void TableCache::Evict(uint64_t file_number) {
char buf[sizeof(file_number)];
EncodeFixed64(buf, file_number);
cache_->Erase(Slice(buf, sizeof(buf)));
}
至此仗嗦，數(shù)據(jù)文件緩存已備忘完成膘滨。等等，最開始還提到除SSTable外稀拐，Block也采用了緩存機制火邓，實現(xiàn)如何？
LevelDB在打開數(shù)據(jù)庫時德撬，需指定一個Options參數(shù)铲咨，其中包含了如下成員：
// If non-NULL, use the specified cache for blocks.
// If NULL, leveldb will automatically create and use an 8MB internal cache.
// Default: NULL
Cache* block_cache;
作者注釋：如果值非NULL，則用用戶指定的緩存方式緩存數(shù)據(jù)塊砰逻，否則創(chuàng)建一個大小為8M的內(nèi)部緩存鸣驱，這個內(nèi)部緩存指的其實就是SharedLRUCache泛鸟。
10.7 總結(jié)
LevelDB的緩存機制并不復(fù)雜蝠咆，除了定制的緩存，還采用了索引北滥、重啟點機制刚操、布隆過濾器、壓縮等等一系列性能優(yōu)化方法再芋。
至此菊霜，我們從部件上拆解了LevelDB，再來看各個接口實現(xiàn)如讀寫操作等并沒有什么難度济赎。關(guān)于壓縮流程鉴逞，本應(yīng)單獨開辟一個章節(jié)講解记某，但log機制、mainfest构捡、version機制等已經(jīng)涉及7液南、8，也就不再贅述了勾徽。
轉(zhuǎn)載請注明：【隨安居士】http://www.reibang.com/p/b4ff071467fb
