专栏首页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 条评论
登录 后参与评论

相关文章

  • LevelDB 完全解析(1):MemTable

    MemTable,顾名思议,就是内存表。每个 LevelDB 实例最多会维护两个 MemTable: mem_ 和 imm_。mem_ 可以读写,imm_ 只读...

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

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

    linjinhe
  • LevelDB 完全解析(3):SSTable

    SSTable 全称 Sorted String Table,顾名思义,里面的 key-value 都是有序保存的。除了两个 MemTable,LevelDB ...

    linjinhe
  • LevelDB 完全解析(4):Manifest

    内容上,Manifest 文件保存了整个 LevelDB 实例的元数据,比如:每一层有哪些 SSTable。 格式上,Manifest 文件其实就是一个 lo...

    linjinhe
  • LevelDB 完全解析(6):Filter

    LevelDB 可以设置通过 bloom filter 来减少不必要的读 I/O 次数。

    linjinhe
  • LevelDB 完全解析(11):Compaction

    因为 LevelDB 的增删改都是通过追加写来实现的,所以需要通过后台线程的 compaction 来:

    linjinhe
  • LevelDB 完全解析(8):读操作之 Get

    LevelDB 通过 leveldb::DB::Get 接口对外提供点查询的能力,具体的实现是 leveldb::DBImpl::Get。接口声明如下:

    linjinhe
  • LevelDB 完全解析(7):初始化

    options - 打开/创建 LevelDB 实例的配置参数。 dbname - 保存数据的目录名。 dbptr - 初始化成功的 LevelDB 实例保...

    linjinhe
  • LevelDB 完全解析(9):写操作

    以上,便是 LevelDB 的写入流程。写入队列 + 合并写操作,逻辑和代码都十分简洁。比较不足的是,整个写入过程都是单线程的。

    linjinhe
  • LevelDB 完全解析(10):读操作之 Iterator

    通过前面的文章,我们了解到 LevelDB 的数据是保存在内部多个不同组件的,并且每个组件的数据格式都不一样。

    linjinhe
  • 漫谈 LevelDB 数据结构(三):LRU 缓存( LRUCache)

    LRU 是工程中多见的一个数据结构,常用于缓存场景。近年来,LRU 也是面试中一道炙手可热的考题,一来工程用的多,二来代码量较少,三来涉及的数据结构也很典型。L...

    青藤木鸟
  • LevelDB:读操作

    前面写了两篇文章介绍 LevelDB 的整体架构和接口使用。这篇文章,我们从代码的角度看看 LevelDB 的设计与实现,先从读操作开始。

    linjinhe
  • LevelDB 完全解析(0):基本原理和整体架构

    之前零零散散写过几篇和 LSM-Tree、LevelDB 有关的文章。之后也看了一些代码和论文,笔记也做了一些,但大都比较零乱、随意,没花功夫整理。

    linjinhe
  • WiscKey:LSM-Tree 写放大优化WiscKey 简介WiscKey 带来的好处WiscKey 面临的问题和挑战参考文档

    WiscKey 的提出,主要是为了优化 LSM-Tree 的写放大问题。此前已经有不少论文讨论过这个问题,如 LSM-trie 和 PebblesDB,但是大部...

    linjinhe
  • gobox中的simplecache和levelcache

    1、在使用时,如果set的值是引用类型,那么改变引用的对象的值时,cache中的内容也会改变,这一点要特别注意。

    李海彬
  • 【深入浅出leveldb】LRU与哈希表

    注意:当refs为0时,需要调用deleter清理函数,类似于shared_ptr。

    公众号guangcity
  • cmake:vs2015/MinGW静态编译leveldb

    leveldb是google的开源项目(https://github.com/google/leveldb), 在linux下编译很方便,然而官方版本却没有提供...

    用户1148648
  • leveldb实现分析

    | 导语  leveldb是google开源的单机key-value存储引擎。基于Log-Structured-Merge Tree的实现。本文先介绍leve...

    腾讯Bugly
  • 谈一谈若干的K-V NoSQL应用:LevelDB、Redis、Tair、RockesDB

    NoSQL、尤其是key-value NoSQL在日常开发中扮演了非常重要的角色,除非对于关系型数据或者事务之类的有着非常强的诉求,不妨就根据业务特点试一下No...

    邹志全

扫码关注云+社区

领取腾讯云代金券