LevelDB 源码阅读:DataBlock 的前缀压缩和重启点机制分析

0 Comment

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

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

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

LevelDB DataBlock 存储结构LevelDB DataBlock 存储结构

阅读全文

LevelDB 源码阅读:一步步拆解 SSTable 文件的创建过程

0 Comment

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

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

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

SSTable 构建文件的步骤概览SSTable 构建文件的步骤概览

阅读全文

LevelDB 源码阅读:LRU Cache 高性能缓存实现细节

2 Comments

计算机系统中,缓存无处不在。从 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 的实现细节。

阅读全文