SSTable 的分层管理设计

简介: SSTable分层管理通过将文件按层级组织,逐层合并,控制每层容量上限,减少多路归并规模,避免全量重叠,提升查询效率与系统性能,是LevelDB高效读写的核心设计。

SSTable 的分层管理设计

我们知道,SSTable 文件是由 Immutable MemTable 将数据顺序导入生成的。尽管 SSTable 中的数据是有序的,但是每个 SSTable 覆盖的数据范围都是没有规律的,所以 SSTable 之间的数据很可能有重叠。

比如说,第一个 SSTable 中的数据从 1 到 1000,第二个 SSTable 中的数据从 500 到 1500。那么当我们要查询 600 这个数据时,我们并不清楚应该在第一个 SSTable 中查找,还是在第二个 SSTable 中查找。最差的情况是,我们需要查询每一个 SSTable,这会带来非常巨大的磁盘访问开销。

因此,对于 SSTable 文件,我们需要将它整理一下,将 SSTable 文件中存的数据进行重新划分,让每个 SSTable 的覆盖范围不重叠。这样我们就能将 SSTable 按照覆盖范围来排序了。并且,由于每个 SSTable 覆盖范围不重叠,当我们需要查找数据的时候,我们只需要通过二分查找的方式,找到对应的一个 SSTable 文件,就可以在这个 SSTable 中完成查询了。

但是要让所有 SSTable 文件的覆盖范围不重叠,不是一个很简单的事情。为什么这么说呢?我们看一下这个处理过程。系统在最开始时,只会生成一个 SSTable 文件,这时候我们不需要进行任何处理,当系统生成第二个 SSTable 的时候,为了保证覆盖范围不重合,我们需要将这两个 SSTable 用多路归并的方式处理,生成新的 SSTable 文件。

那为了方便查询,我们要保证每个 SSTable 文件不要太大。因此,LevelDB 还控制了每个 SSTable 文件的容量上限(不超过 2M)。这样一来,两个 SSTable 合并就会生成 1 个到 2 个新的 SSTable。

这时,新的 SSTable 文件之间的覆盖范围就不重合了。当系统再新增一个 SSTable 时,我们还用之前的处理方式,来计算这个新的 SSTable 的覆盖范围,然后和已经排好序的 SSTable 比较,找出覆盖范围有重合的所有 SSTable 进行多路归并。这种多个 SSTable 进行多路归并,生成新的多个 SSTable 的过程,也叫作 Compaction。

随着 SSTable 文件的增多,多路归并的对象也会增多。那么,最差的情况会是什么呢?最差的情况是所有的 SSTable 都要进行多路归并。这几乎是一个不可能被接受的时间消耗,系统的读写性能都会受到很严重的影响。

那我们该怎么降低多路归并涉及的 SSTable 个数呢?在 第 9 讲 中,我们提到过,对于少量索引数据和大规模索引数据的合并,我们可以采用滚动合并法来避免大量数据的无效复制。因此,LevelDB 也采用了这个方法,将 SSTable 进行分层管理,然后逐层滚动合并。这就是 LevelDB 的分层思想,也是 LevelDB 的命名原因。接下来,我们就一起来看看 LevelDB 具体是怎么设计的。

首先,从 Immutable MemTable 转成的 SSTable 会被放在 Level 0 层。Level 0 层最多可以放 4 个 SSTable 文件。当 Level 0 层满了以后,我们就要将它们进行多路归并,生成新的有序的多个 SSTable 文件,这一层有序的 SSTable 文件就是 Level 1 层。

接下来,如果 Level 0 层又存入了新的 4 个 SSTable 文件,那么就需要和 Level 1 层中相关的 SSTable 进行多路归并了。但前面我们也分析过,如果 Level 1 中的 SSTable 数量很多,那么在大规模的文件合并时,磁盘 IO 代价会非常大。因此,LevelDB 的解决方案就是,给 Level 1 中的 SSTable 文件的总容量设定一个上限(默认设置为 10M),这样多路归并时就有了一个代价上限。

相关文章
|
存储 Python
海明距离(Hamming Distance)
海明距离(Hamming Distance)是用来衡量两个二进制数之间差异程度的指标,它表示两个二进制数之间最多有多少个比特的差异。海明距离可以用于衡量数据传输或存储中的错误率,以及检测噪声干扰。 海明距离的计算方法是:对于两个 n 位二进制数,将它们进行逐位比较,如果对应位上的数字不同,则计算距离时增加 1。然后将所有位上的距离加在一起,得到海明距离。
3682 1
|
人工智能 自然语言处理 数据挖掘
云上玩转Qwen3系列之三:PAI-LangStudio x Hologres构建ChatBI数据分析Agent应用
PAI-LangStudio 和 Qwen3 构建基于 MCP 协议的 Hologres ChatBI 智能 Agent 应用,通过将 Agent、MCP Server 等技术和阿里最新的推理模型 Qwen3 编排在一个应用流中,为大模型提供了 MCP+OLAP 的智能数据分析能力,使用自然语言即可实现 OLAP 数据分析的查询效果,减少了幻觉。开发者可以基于该模板进行灵活扩展和二次开发,以满足特定场景的需求。
|
8月前
|
存储 数据采集 人工智能
什么是数据湖?一文搞懂数据湖、数据仓库、湖仓一体
本文用通俗语言解析数据湖、数据仓库与湖仓一体三大核心概念:数仓专注结构化、高性能分析;数据湖支持多源原始数据低成本存储;湖仓一体则融合二者优势,实现统一存储、灵活探索与可靠分析。附实战方案与工具推荐。
|
10月前
|
人工智能 开发框架 监控
2026智能体元年:给普通人的3层行动框架与7个核心工具
本文揭示AI正从“问答工具”跃迁为“主动执事”的智能体时代(2025–2026关键窗口)。提出认知—行动—工具三层框架:厘清智能体自主性、多模态与记忆本质;分“观察→体验→构建”渐进实践;精选7类即用工具(如百炼、Dify、LangChain等),助普通人零起点转型参与者。(239字)
1354 1
|
11月前
|
存储 算法 安全
加密算法
加密算法主要分为对称加密(如AES、SM4)、非对称加密(如RSA、SM2)、哈希摘要(如SHA-2、SM3)、电子签名及密码存储技术。对称加密加解密快但需保密密钥;非对称加密使用公私钥,安全性高但速度慢;哈希摘要用于验证数据完整性,不可逆。各类算法在信息安全中各有应用场景。
|
11月前
|
存储 NoSQL 关系型数据库
Geohash 编码
Geohash编码将经纬度转换为字符串,通过不断二分地球经纬度区间,交叉组合生成区域编码,再转为Base32简化表示。它用于高效存储和查询地理位置,广泛应用于Redis、MySQL等系统,具有相同前缀的编码代表相近区域,便于空间索引与检索。
|
JavaScript 前端开发 API
|
存储 虚拟化 云计算
|
人工智能 安全 测试技术
Burp Suite Professional 2025.3 发布,引入 Burp AI 通过人工智能增强安全测试工作流程
Burp Suite Professional 2025.3 发布,引入 Burp AI 通过人工智能增强安全测试工作流程
1292 0
Burp Suite Professional 2025.3 发布,引入 Burp AI 通过人工智能增强安全测试工作流程