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 的实现细节。

在 LevelDB 中，所有的写操作首先都会被记录到一个 Write-Ahead Log（WAL，预写日志）中，以确保持久性。接着数据会被存储在 MemTable 中，MemTable 的主要作用是在内存中有序存储最近写入的数据，到达一定条件后批量落磁盘。

LevelDB 在内存中维护两种 MemTable，一个是可写的，接受新的写入请求。当达到一定的大小阈值后，会被转换为一个不可变的 Immutable MemTable，接着会触发一个后台过程将其写入磁盘形成 SSTable。这个过程中，会创建一个新的 MemTable 来接受新的写入操作。这样可以保证写入操作的连续性，不受到影响。

在读取数据时，LevelDB 首先查询 MemTable。如果在 MemTable 中找不到，然后会依次查询不可变的 Immutable MemTable，最后是磁盘上的 SSTable 文件。在 LevelDB 的实现中，不管是 MemTable 还是 Immutable MemTable，内部其实都是用 class MemTable 来实现的。这篇文章我们来看看 memtable 的实现细节。