in LevelDB 分布式数据库 ~ read.

LevelDB组件-Cache

LevelDB组件-Cache

Leveldb中使用了一种基于LRUCache的缓存机制,用于缓存:

  • 已打开的SST文件对象和相关元数据(TableCache);
  • SST中的DataBlock的内容(BlockCache);

使得在发生读取热数据时,尽量在cache中命中,避免IO读取。

当热点数据比较集中时,效果最好;当全表扫描、范围扫描时,意义不大。

Cache 实现

LRUHandle: Cache中存储的entry,除了保存key-value以为还保存了一些维护信息。

HandleTable: leveldb自己实现的hash,随机读的速度比 g++4.4.3 的内置哈希表提高了约 5%。

LRUCache: LRUCache的实现。内部实现,不对外暴露接口。

ShardedLRUCache: leveldb对外暴露的LRUCache。

ShardedLRUCache

ShardedLRUCache 是在 LRUCache 上包装了一层,用于分片

根据 key 的哈希值的前 4 位(kNumShardBits)分 16 个(kNumShards) LRUCache。

分片的作用是减少多线程对同一个 LRUCache 对象的争用。

即,每当操作一个Key时,首先进行Hash,而后取前4位,求解得到当前Key在哪个 LRUCache 中,进而操作对应的 LRUCache。

class ShardedLRUCache : public Cache {
 private:
  LRUCache shard_[kNumShards];   // 16
  port::Mutex id_mutex_;   //id生成锁
}

LRUCache

LeastRecentlyUsed ,最近最少使用

![Cache](https://raw.githubusercontent.com/ccyuki/vnote_img/main/personal/written/leveldb组件-cache.md/323034514230738.png =685x)

实现包括三部分:

  1. 链表 lru_:维护热度信息,保存的是Hash表中Entry的位置iterator。数据每次被访问的时候,都会被插入到这个链表最新的地方。
  2. 链表 in_use_:维护 cache 中有哪些缓存对象被返回给调用端使用。这些数据不能被淘汰。
  3. 哈希表 table_:保存所有 key -> Entry 数据,用于快速查找数据。
class LRUCache {
 public:
  LRUCache();
  ~LRUCache();
  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);
  void Prune();

 private:
  // Entries have refs==1 and in_cache==true.
  LRUHandle lru_ GUARDED_BY(mutex_);

  // Entries are in use by clients, and have refs >= 2 and in_cache==true.
  LRUHandle in_use_ GUARDED_BY(mutex_);

  HandleTable table_ GUARDED_BY(mutex_); //hash表,用于存储entry。
};

LruHandle

采用双向链表实现

struct LRUHandle {
  void* value;  // 存储的 value 对象的指针,可以存储任意类型的值
  void (*deleter)(const Slice&, void* value); // 当refs == 0时,调用deleter完成value对象释放。
  LRUHandle* next_hash;  // 作为HashTable中的节点,指向hash值相同的节点(解决hash冲突采用拉链法)
  LRUHandle* next; // 作为LRUCache中的节点,指向后继
  LRUHandle* prev; // 作为LRUCache中的节点,指向前驱
  size_t charge;   // 分配的可以消耗的内存量
  size_t key_length;
  bool in_cache;     // Whether entry is in the cache.
  uint32_t refs;     // 引用计数
  uint32_t hash;     // `key()` 对应的哈希,用于快速分区和比较
  char key_data[1];  // 存储 key 的开始地址,结合 `key_length` 获取真正的 key
  // GCC 支持 C99 标准,允许定义 char key_data[] 这样的柔性数组(Flexible Array)。
  // C++ 标准并不支持柔性数组的实现,这里定义为 key_data[1],这也是 c++ 中的标准做法。

  Slice key() const {
    return Slice(key_data, key_length);
  }
};

HandleTable

拉链法实现的HashTable

基于Yujie Liu等人的论文《Dynamic-Sized Nonblocking Hash Table》实现。

class HandleTable {
 public:
  HandleTable() : length_(0), elems_(0), list_(nullptr) { Resize(); }
  ~HandleTable() { delete[] list_; }

 private:
  // list 数组的长度,即哈希桶的个数
  uint32_t length_;

  // 存储的元素总个数,当 elems > length 时,扩展 list 数组并重新 hash
  uint32_t elems_;

  // 存储 entry 的数组,即哈希桶,初始大小为 4,动态扩展,成倍增长
  LRUHandle** list_;
  }
};
ResizeHash

当Hash冲突时,以list_双向链表形式存储,初始Bucket为4,随数据量增大,为保证增/删/查 的性能,需动态扩展,进行ResizeHash;

基于论文实现的ResizeHash,可以不阻塞其它并发读写请求,理论基础是“一个Bucket的数据是可以冻结的”。

当下面两种情况出现时,会发生ResizeHash。即“cache中维护的数据量过大”:

  • 整个cache中,数据项(Entry)的个数超过预定的阈值(默认初始状态下哈希桶的个数为4个,每个桶中可存储32个数据项,即总量的阈值为哈希桶个数乘以每个桶的容量上限);
  • 当cache中出现了数据不平衡的情况。当某些桶的数据量超过了32个数据,即被视作数据发生散列不平衡。当这种不平衡累积值超过预定的阈值(128);

Resize的过程:

  1. 计算新哈希表的哈希桶个数(扩大一倍);
  2. 创建一个空的哈希表,并将旧的哈希表(主要为所有哈希桶构成的数组)中的每个哈希桶都被“冻结”;
  3. 用“被冻结”的哈希桶信息对新的哈希表进行内容构建;

完成新哈希表构建的整个过程中,哈希表并不是拒绝服务的,所有的读写操作仍然可以进行。

当有新的读写请求发生时,若被散列之后得到的哈希桶仍然未构建完成,则“主动”进行构建,并将构建后的哈希桶填入新的哈希表中。后台进程构建到该桶时,发现已经被构建了,则无需重复构建。

![resize](https://raw.githubusercontent.com/ccyuki/vnote_img/main/personal/written/leveldb组件-cache.md/124205810223733.png =534x)

因此如上图所示,哈希表扩张结束,哈希桶的个数增加了一倍,于此同时仍然可以对外提供读写服务,仅仅需要哈希桶级别的封锁粒度就可以保证所有操作的一致性跟原子性。

void Resize() {
  // 初始化时,哈希桶的个数为 4
  uint32_t new_length = 4;

  // 随着不同哈希值的增加动态扩展,每次扩展为原容量的两倍
  while (new_length < elems_) {
    new_length *= 2;
  }

  // 按照新容量申请内存,分配给新链表,并将原数据复制过去
  LRUHandle** new_list = new LRUHandle*[new_length];
  memset(new_list, 0, sizeof(new_list[0]) * new_length);
  uint32_t count = 0;
  for (uint32_t i = 0; i < length_; i++) {
    LRUHandle* h = list_[i];
    while (h != nullptr) {
      LRUHandle* next = h->next_hash;
      uint32_t hash = h->hash;
      LRUHandle** ptr = &new_list[hash & (new_length - 1)];
      h->next_hash = *ptr;
      *ptr = h;
      h = next;
      count++;
    }
  }
  assert(elems_ == count);

  // 释放原数组
  delete[] list_;

  // 更新哈希表数据
  list_ = new_list;
  length_ = new_length;
}

TableCache

已打开的SST文件对象和相关元数据,MetaIndexBlock

![TableCache](https://raw.githubusercontent.com/ccyuki/vnote_img/main/personal/written/leveldb组件-cache.md/283883315231064.png =648x)

  • key: SSTable的文件名,file_number
  • Value:TableAndFile
    • RandomAccessFile:指向磁盘SST文件的文件句柄
    • Table:指向内存中当前 File 对应的Table结构指针,保存了SSTable的index等元数据
struct TableAndFile {
  RandomAccessFile* file;
  Table* table;
};

struct Table::Rep {
  ~Rep() {
    delete filter;
    delete[] filter_data;
    delete index_block;
  }

  Options options;
  Status status;
  RandomAccessFile* file;  // SST 文件句柄
  uint64_t cache_id;       // BlockCache 的 id : from open sst
  FilterBlockReader* filter;
  const char* filter_data;

  BlockHandle metaindex_handle;  // Handle to metaindex_block: saved from footer
  Block* index_block;      // MetaIndexBlock
};

BlockCache

SST中的DataBlock的内容

![BlockCache](https://raw.githubusercontent.com/ccyuki/vnote_img/main/personal/written/leveldb组件-cache.md/587622319229866.png =472x)

  • key:sst文件的 cache_id + 这个block在文件中的offset。
  • value:DataBlock的数据。

调用

  • 通过sstable的key range,确定Key所在的level及sstable文件。
  • 查找TableCache,获取Index信息
    • TableCache::Get-> TableCache::FindTable
      • 找到,返回value,获取到Table*指针。
      • 未找到,打开SSTable文件,将其index部分载入TableCache。
  • 根据Table* 查找 BlockCache,获取具体block记录
    • TableCache::Get-> Table::InternalGet -> Table::BlockReader
    • 通过 index_block 判断记录是否存在,否直接返回。
    • 如果存在,通过 cache_id 查找 BlockCache
      • 找到,返回 block 内容;
      • 找不到,从文件获取。