背景紧接上篇，通过 PickCompaction 确定了 需要 Compaction 的层级 level 及文件 确定了 level + 1 层文件 确定了 level + 2 层文件 接下来，我们来分析后续的 Compaction 操作 分析leveldb 并不是之间直接将 level 与 level + 1 层进行进行 Compaction ，而是有一个优化：根据所选文件进行判断这是否是一次简单的压缩 123456789// c 代表上一次 PickCompaction 操作是否有需要 Compaction 的文件// c == nullptr 代表当前无文件需要处理if (c == nullptr) { // Nothing to do } else if (!is_manual && c->IsTrivialMove()) { ... } else { ... } is_manual 是前文提到过的：是否是通过 leveldb 对外接口手动触发 Compaction ，默认是 ...

背景leveldb 是一个写效率十分高的存储引擎, 一次写操作只需要顺序写日志(WAL)，内存跳表插入(logn) 但是如此以来读性能就有所下降，在最差的情况下可能需要查找以下所有文件 1MemTable --> Immutable MemTable --> Level 0 files --> Level 1 files -->Level 2 files ......-->Level 6 files 所以引入 Compaction 可以带来如下好处 平衡读写差异，将相关文件进行合并 删除过时数据，减少数据量 分析Compaction 是通过后台线程调用 BackgroundCompaction 来触发，上一章中我们分析了如何触发 Compaction 并分析了当中的 Minor Compaction ，本文将关注当中的 Major Compaction (SSTable 当中的 Compaction) BackgroundCompaction 主要有两个部分组成 Minor Compaction1234if (imm_ != nullptr) & ...

背景 图片来自于SmartKeyerror 此图为 SSTable 的总览图，如图所示主要由下面几个模块构成 Data Block ： 具体的数据块，存储 (key value)，并在存储时通过前缀压缩等方法进行优化 Meta Block ： 为了方便查询所建立的过滤块，leveldb中使用的是布隆过滤器，该过滤块可以快速判断 key 是否存在 Metaindex Block ： 对 Meta Block 块的索引块，默认 Meta Block 为 4K 大小 Index Block ：对 Data Block 块的索引块 Footer ：存储 Metaindex Block 与 Index Block 的偏移地址 分析触发 Compaction接下来我们将从 leveldb 的源码部分看看一个 SSTable 究竟是如何产生的 首先是一个大致的调用逻辑: leveldb 会在对外接口 open 中去调用 MaybeScheduleCompaction 函数，从名字中得知，此函数应该是调度触发压缩(Compaction)，为什么是Maybe呢？ 12345678910111 ...

背景一般来说，哈希表的实现是通过两个部分实现的 12hash = hashfunc(key)index = hash % table_size 使用求模来减少存储空间，所以必然会导致不同的数据离散到相同的索引下标处，此时就发生了哈希冲突。 解决方案主要分为两大类 链式法 （Separate Chaining） 开放地址法（Open Addressing） 链接技术将采用额外的数据节点来处理冲突。当冲突发生时，在冲突位置建立链表，通过链表串联起离散到相同下标的节点。在最坏的状况下，会退化为单链表，性能损失严重，哈希攻击便是采用这种形式。 开放地址就是开放哈希表中的所有地址，不使用额外的空间。如果遇到冲突，寻找其他位置存储。 开放地址法线性探测如果哈希到索引为 x 处，如果此处有元素，则查看 x + 1 处，如果没有则放在这里，如果有，则以此类推查看 x + 2，x + 3, … 二次探查这是线性探测的改进，每次的步长变为平方倍数。 Double hashing另一种改进的开放寻址法称为重哈希(Double hashing)或者叫二度哈希（Rehashing） 而在 LevelD ...

背景Bloom Filter 是一种空间效率很高的随机数据结构，它利用位数组表示一个集合，并能判断一个元素是否属于这个集合。 Bloom Filter 的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。 leveldb 中利用布隆过滤器判断指定的 key 值是否存在于 sstable 中，若过滤器表示不存在，则该 key 一定不存在，由此加快了查找的效率。 优劣相对于其他表示数据集的数据结构，如平衡二叉搜索树、Trie 树、哈希表，甚至更简单的数组或者链表。大都需要对数据项本身存储。但是 Bloom Filter 并不存储数据项本身，而是用高效紧凑的位数组来存。 如此设计，使得 Bloom Filter 的大小与数据项本身大小（如字符串的长短）无关。可以理解为在哈希表基础上，忽略了冲突处理，从而省下了额外开销。 对于 Bloom Filter ，其误判率应该和以下参数有关： 哈希函数的个数 k 底层位数组的长度 m 数据集大小 n 当 k = ln2 * (m/n) ...

背景LRU （Last Recent Used）是一个重要的缓存替换算法，常用于缓存场景,一般的实现是使用一个哈希表（unordered_map）和一个双向链表，哈希表解决索引问题，双向链表维护访问顺序。 内部实现LevelDB的LRUCache设计有4个数据结构，是依次递进的关系，分别是： LRUHandle HandleTable LRUCache ShardedLRUCache LRUHandle 是 LRUCache 中的数据节点，HandleTable 是 LRUCache 为了实现可扩展哈希性而自定义的哈希桶，LRUCache 便是核心类，内部维护了一条冷数据双向链表，一条热数据双向链表，以及 HandleTable来索引节点，此时LRU的缓存管理数据结构已经实现。而 ShardedLRUCache 是为了在多线程访问时提升效率，内部有16个LRUCache，查找key的时候，先计算属于哪一个LRUCache，然后在相应的LRUCache中上锁查找。 模块分析首先是 LevelDB 的导出接口 Cache 123456789101112131415161718192 ...