专栏首页linjinhe的专栏LevelDB 完全解析(5):Cache

LevelDB 完全解析(5):Cache

前文回顾

  • LevelDB 完全解析(0):基本原理和整体架构
  • LevelDB 完全解析(1):MemTable
  • LevelDB 完全解析(2):Log
  • LevelDB 完全解析(3):SSTable
  • LevelDB 完全解析(4):Manifest

根据功能的不同,LevelDB 中有两种 cache:

  1. Block cache:缓存解压后的 data block,可以加快热数据的查询。
  2. Table cache:缓存打开的 SSTable 文件描述符和对应的 index block、meta block 等信息。

在 LevelDB 中,block cache 和 table cache 都是基于 ShardedLRUCache 实现的。

ShardedLRUCache

ShardedLRUCache 是在 LRUCache 上包装了一层分片——根据 key 的哈希值的前 4 位(kNumShardBits)分 16 个(kNumShards) LRUCache。

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

LRUCache

LRU,全称是 Least Recently Used(最近最少使用),是一种利用局部性原理(如果数据最近被访问过,那么将来被访问的几率也更高)的缓存淘汰策略。LRUCache 即是一个基于 LRU 淘汰策略的缓存。当热点数据比较集中时,LRUCache 的效率比较高。

LevelDB 的 LRUCache 的实现由一个哈希表和两个链表组成:

  1. 链表 lru_:维护 cache 中的缓存对象的使用热度。数据每次被访问的时候,都会被插入到这个链表最新的地方。 lru_->next 指向最旧的数据, lru_->prev 指向最新的数据。当 cache 占用的内存超过限制时,则从 lru_->next 开始清理数据。
  2. 链表 in_use_:维护 cache 中有哪些缓存对象被返回给调用端使用。这些数据不能被淘汰。
  3. 哈希表 table_:保存所有 key -> 缓存对象,用于快速查找数据。

LRUCache 的 Insert 和 Lookup 的时间复杂度都是 O(1)。

LRUHandle

LRUHandle 是 LRUCache 中的一个对象。

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;
  bool in_cache;     // Whether entry is in the cache.
  uint32_t refs;     // References, including cache reference, if present.
  uint32_t hash;     // Hash of key(); used for fast sharding and comparisons
  char key_data[1];  // Beginning of key

  Slice key() const {
    // next_ is only equal to this if the LRU handle is the list head of an
    // empty list. List heads never have meaningful keys.
    assert(next != this);

    return Slice(key_data, key_length);
  }
};

重点关注三个 LRUHandle 的指针:

  1. next_hash : 哈希表的实现采用的是拉链法来处理哈希冲突,用 next_hash 维护落到同一个 bucket 的对象。
  2. next / prev : LRUCache 通过链表来维护缓存对象的使用“热度”和是否正在被调用端使用,这两个指针就是用来实现链表的。

HandleTable

HandleTable 是 LevelDB 采用拉链法实现的一个哈希表,主要提供了 LookupInsertRemove 三个接口。没有做什么特殊优化,逻辑很清楚。

当哈希表的元素数量超过 list_ 的长度 length_ ,会调用 Resize 进行重新哈希(rehash)。直接扫描整个哈希表进行全量 rehash,如果哈希表很大,遇到 rehash 可能会导致系统抖动。

缓存淘汰策略

LRU

LRU 是一种常用的缓存淘汰策略,因为大部分情况下,数据的访问都是具有局部性的——最近访问过的数据,短时间内还被访问的概率比较大;而比较久没被访问的数据,短时间内会被访问的概率比较小。

当热点数据比较集中时,LRU 的缓存命中率比较高。但是在某些场景下,LRU 的缓存命中率会急剧下降,比如批量遍历。

LevelDB 在读参数 ReadOptions 提供了一个参数 fill_cache ,让上层控制是否要将 data block 放入到 block cache。

MySQL 的 InnoDB 的 LRU 缓存实现为了避免扫描操作污染 cache,采用了两级的 LRU cache。数据会先进入第一级 cache,一段时间之后还有访问再放到第二级 cache。

FIFO

FIFO,全称 First In First Out,其实就是一个队列,按先进先出的方法淘汰数据。新的数据插入队列尾部(入队),队列满了之后从队列的头部开始删除(出队)。

LFU

LFU,全称 Least Frequently Used,根据数据的访问频率来淘汰数据,适用于“如果数据过去被访问多次,那么将来被访问的频率也更高”的场景。

Random

随机淘汰缓存对象。好处是不用根据 LRU、FIFO、LFU 的要求维护缓存对象的顺序。

Block Cache

一个 SSTable 在被打开的时候,会通过 options.block_cacheNewId 为其分配一个唯一的 cache_id

每个 data block 保存到 block cache 的 key 为 cache_id + offset

由于 SSTable 是只读的,block 的读取和 block cache 的维护非常简单,具体参考 Table::BlockReader

Table Cache

Table cache 的具体实现在 table_cache.h table_cache.cc

Table cache 的 key 是 SSTable 的 file_number,value 是一个 TableAndFile 对象。

TableAndFile 有两个成员变量 filetable,重点是 table

struct TableAndFile {
  RandomAccessFile* file;
  Table* table;
};

Table 内部封装了 index 和 filter,以及其他一些 SSTable 的元数据(参考代码)。

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

  Options options;
  Status status;
  RandomAccessFile* file;
  uint64_t cache_id;
  FilterBlockReader* filter;
  const char* filter_data;

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Linux常用命令:free

    linjinhe
  • 浏览器缓存机制

    linjinhe
  • LevelDB 完全解析(2):Log

    这里的 log 是指 Write Ahead Log。前面说了,LevelDB 写入的数据会先保存到 MemTable。为了防止宕机导致数据丢失,在将数据写入 ...

    linjinhe
  • WordPress速度优化之Mysql Query_cache缓存加速

    WordPress性能优化非常重要,因为网站打开速度快了,看的人自然就多了,看的人多了,收入自然就多了。

    xianba
  • 静态页面设置缓存、动态页面设缓存(不断更新中。。。。)

      1.静态的html页面想要设置使用缓存:<meta http-equiv="expires" content="utc时刻"/>,目前我只明确该方法可行。如...

    ^_^肥仔John
  • 总结Web应用中常用的各种Cache

    cache是提高应用性能重要的一个环节,写篇文章总结一下用过的各种对于动态内容的cache。 文章以Nginx,Rails,Mysql,Redis作为例子,换...

    前朝楚水
  • HTTP缓存

    P.S.关于HTTP Header的更多信息,请查看4.2 Message Headers

    ayqy贾杰
  • 一篇文章让你明白CPU缓存一致性协议MESI

    CPU在摩尔定律的指导下以每18个月翻一番的速度在发展,然而内存和硬盘的发展速度远远不及CPU。这就造成了高性能能的内存和硬盘价格及其昂贵。然而CPU的高度运算...

    程序员追风
  • Arch 安装后,一些基本设置(1)

    1.安装成功后新建普通用户不能使用useradd进行一步添加,应该下载adduser交互式添加新用户,否则用户无法登陆。

    RainMark
  • iOS新闻类App内容页技术探索

    据相关数据显示,截至2017年底,中国手机新闻客户端用户规模达到6.36亿人,移动App已经成为新闻和内容传播的最重要途径之一。而伴随着行业的竞争和发展,App...

    iOS_林夕

扫码关注云+社区

领取腾讯云代金券