在 LevelDB 中，SSTable（Sorted Strings Table）是存储键值对数据的文件格式。前面的文章LevelDB 源码阅读：一步步拆解 SSTable 文件的创建过程 介绍了 SSTable 文件的创建过程，我们知道了 SSTable 文件由多个数据块组成，这些块是文件的基本单位。

这些数据块起始可以分两类，一种是键值对数据块，一种是过滤块数据块。相应的，为了组装这两类数据块，LevelDB 实现了两类 BlockBuilder 类，分别是 BlockBuilder 和 FilterBlockBuilder。这篇文章，我们来看看 BlockBuilder 的实现。

先来看一个简单的示意图，展示了 LevelDB 中 DataBlock 的存储结构，图的源码在 leveldb_datablock.dot。

LevelDB DataBlock 存储结构

LevelDB 中，内存表中的键值对在到达一定大小后，会落到磁盘文件 SSTable 中。并且磁盘文件也是分层的，每层包含多个 SSTable 文件，在运行时，LevelDB 会在适当时机，合并、重整 SSTable 文件，将数据不断往下层沉淀。

这里 SSTable 有一套组织数据的格式，目的就是保证数据有序，并且能快速查找。那么 SSTable 内部是怎么存储这些键值对的，又是怎么提高数据的读、写性能的。以及整个 SSTable 文件的实现中有哪些优化点？

本文接下来我们会仔细分析 SSTable 文件的创建过程，一步步拆解来看看这里到底怎么实现的。在开始之前，我先给一个大的图，大家可以先留个印象。

SSTable 构建文件的步骤概览

计算机系统中，缓存无处不在。从 CPU 缓存到内存缓存，从磁盘缓存到网络缓存，缓存无处不在。缓存的核心思想就是空间换时间，通过将热点数据缓存到高性能的存储中，从而提高性能。因为缓存设备比较贵，所以存储大小有限，就需要淘汰掉一些缓存数据。这里淘汰的策略就非常重要了，因为如果淘汰的策略不合理，把接下来要访问的数据淘汰掉了，那么缓存命中率就会非常低。

缓存淘汰策略有很多种，比如 LRU、LFU、FIFO 等。其中 LRU(Least Recently Used) 就是一种很经典的缓存淘汰策略，它的核心思想是：当缓存满了的时候，淘汰掉最近最少使用的数据。这里基于的一个经验假设就是”如果数据最近被访问过，那么将来被访问的几率也更高“。只要这个假设成立，那么 LRU 就可以显著提高缓存命中率。

在 LevelDB 中，实现了内存中的 LRU Cache，用于缓存热点数据，提高读写性能。默认情况下，LevelDB 会对 sstable 的索引 和 data block 进行缓存，其中 sstable 默认是支持缓存 990 (1000-10) 个，data block 则默认分配了 8MB 的缓存。

LevelDB 实现的 LRU 缓存是一个分片的 LRU，在细节上做了很多优化，非常值得学习。本文将从经典的 LRU 实现思路出发，然后一步步解析 LevelDB 中 LRU Cache 的实现细节。