leveldb自己实现了cache缓冲区替代算法，参见代码cache.h和cache.c文件。leveldb中table_cache等都是以class cache作为底层实现。
cache.h中，我们看到cache类是一个抽象类，声明了lookup;insert;release;value;erase等函数，同时声明了一个全局函数

extern Cache* NewLRUCache(size_t capacity);

用来构造cache派生类对象，并返回派生类指针。那么cache的派生类究竟是什么呢？很容易在cache.cc中发现了ShardedLRUCache类，继承自cache，这是leveldb缓冲区算法的默认实现。

ShardedLRUCache成员变量 static const int kNumShardBits = 4; static const int kNumShards = 1 << kNumShardBits; private: LRUCache shard_[kNumShards]; //暂时不明 port::Mutex id_mutex_; //互斥锁 uint64_t last_id_; //不明

LRUCache的实现我们暂且不知道，但看起来ShardedLRUCache应该是一个封装类，真正的cache是LRUCache，而且是16个。先看ShardedLRUCache函数：

 //返回key的hash值 static inline uint32_t HashSlice(const Slice& s) { return Hash(s.data(), s.size(), 0); } //取hash的前四位 static uint32_t Shard(uint32_t hash) { return hash >> (32 - kNumShardBits); } public: //构造ShardedLRUCache对象，初始化LRUCache成员变量 //设置容量,并且容量和16对齐 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() { } //插入操作 //先取key的hash值 HashSlice(key)，hash值得前四位（Shard(hash)）决定key所在的LRUCache数组 //将key插入shard_[Shard(hash)] 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
     
      (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
      
       (handle)->value; } virtual uint64_t NewId() { MutexLock l(&id_mutex_); return ++(last_id_); }
      
     

从ShardedLRUCache的成员函数，我们还是获得了很多关于ShardedLRUCache的信息。ShardedLRUCache是一个封装类，真正的cache是LRUCache数组，ShardedLRUCache完成的操作就是计算key的hash值，并以hash值得高四位决定key所在的LRUCache数组，然后调用LRUCache的函数完成cache操作。

LRUCache: // Initialized before use. size_t capacity_; //容量 // mutex_ protects the following state. port::Mutex mutex_; //互斥锁 size_t usage_; //使用量 // Dummy head of LRU list. // lru.prev is newest entry, lru.next is oldest entry. LRUHandle lru_; //不明 HandleTable table_; //不明 LRUCache成员变量如上，再看看LRUCache的函数 //删除e节点 void LRUCache::LRU_Remove(LRUHandle* e) { e->next->prev = e->prev; e->prev->next = e->next; } //附加e节点 void LRUCache::LRU_Append(LRUHandle* e) { // Make "e" newest entry by inserting just before lru_ //添加的新节点在lru_之前 e->next = &lru_; e->prev = lru_.prev; e->prev->next = e; e->next->prev = e; } //查找操作 //table_保存着key所在handle的指针信息 //查找完要把handle提到链表的最前面，是一种为了高效查找的策略 Cache::Handle* LRUCache::Lookup(const Slice& key, uint32_t hash) { MutexLock l(&mutex_); LRUHandle* e = table_.Lookup(key, hash); if (e != NULL) { e->refs++; LRU_Remove(e); LRU_Append(e); } return reinterpret_cast
      
       (e); }
      

可以确定，LRUCache封装了一个LRUHandle链表的信息，lru_是这个链表的头结点，table_是一个辅助定位链表中各LRUHandle节点的结构。

LRUHandle结构体：
下面我们终于来到了cache的最底层，LRUHandle结构真正包含了所缓冲的数据

struct LRUHandle { //value数据 void* value; //delete函数指针 void (*deleter)(const Slice&, void* value); //下面就是关于LRUHandle链表的实现 //可以看明的有key的hash值 //key的数据 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
       
        (value)); } else { return Slice(key_data, key_length); } } };
       

节点的定义我们看完了，链表的操作我们还是要回到上层LRUCache去体会。

在ShardedLRUCache中我们知道插入一个key是要通过hash值决定key所在的LRUCache数组，之后把key交给数组中相应的LRUCache对象处理，这就调用了
LRUCache::Insert函数