LSM-tree Compaction 策略:leveling、tiering、lazy leveling 与 RocksDB 的实现
拆解 leveling、tiering、lazy leveling 的代价模型,对照 RocksDB 9.7.4 的 leveled、universal、FIFO 源码,用计数模拟器实测 22 种配置的写、读、空间放大,并验证 Monkey 给小层更多 filter 位。
Linux 内核、存储与网络、可观测性、系统架构与大模型基础设施的工程笔记:机制拆解、踩坑复盘与可核对证据,少空谈。
共 14 篇文章 · 返回首页
拆解 leveling、tiering、lazy leveling 的代价模型,对照 RocksDB 9.7.4 的 leveled、universal、FIFO 源码,用计数模拟器实测 22 种配置的写、读、空间放大,并验证 Monkey 给小层更多 filter 位。
用可复现实验测量 Bloom、分块 Bloom、cuckoo、xor 与 Ribbon 的每键位数和误判率,对照 log2(1/ε) 下界解释 1.44 倍从何而来、经典 FPR 公式偏在哪里,并核对 RocksDB 9.10 的 FastLocalBloom 与 Ribbon 实现。
从 O'Neil 1996 与 Dostoevsky 的代价模型推导两类结构的读写空间放大,用计数模拟器在同一负载上实测:B+tree 写放大随缓冲池从 126 降到 8.6,leveled LSM 为 14.4,并对照 RUM 猜想原文与生产数据。
ClickHouse PRIMARY KEY 排序键稀疏索引语义、Data Skipping Index(minmax/set/bloom_filter)与 Mark Range 协同;对照 PostgreSQL B-Tree。24.x LTS。
钉住 covering index 消除的具体开销:第 4 篇 index b-tree 只存 key+rowid,命中后仍要回表这一次二次查找;用本机 3.53.2 实测 SELECT 列是否全部落在索引内如何改变 EQP 输出,并区分语句级自动索引与 sqlite_autoindex_* 约束索引这两个常被混淆的…
LSM-Tree 的核心设计是把随机写转换为顺序写,但这个转换不是免费的。写入经过 MemTable 刷盘、再经过多次 Compaction 合并,每一字节的用户数据在磁盘上可能被反复读写数十次。读取一个 key 时,最坏情况下需要逐层搜索,直到命中或遍历全部层级。与此同时,旧版本数据和墓碑标记占用的额外空间,在 C…
沿 TableCache 与 BlockBasedTable 读路径说明 Block Cache、Table Cache、Full/Ribbon Filter 与 Partitioned Index 如何裁剪点查 I/O;读放大度量与调参边界引用 storage/68,不重复全文推导。
拆 Parquet 的物理结构:file → row group → column chunk → page,footer 里的 FileMetaData(Thrift)与 PAR1 magic。讲清 PLAIN/RLE-bitpacking/字典/DELTA_BINARY_PACKED/BYTE_STREAM_SP…
拆解性能关键的 ring buffer(mmap 双缓冲与 record 提交语义)、perf event array(perf_event_output 路径)、bloom filter(N_HASH 位图)、queue/stack(链式辅助结构)、LPM trie(前缀树),以及 devmap/cpumap 等重…
深入分析存储读取性能优化——索引设计、Bloom Filter 调优、块缓存、压缩的 CPU-I/O 权衡、预读策略与读放大测量
数据库里存了一亿行数据,要找出 userid 42 的那一行。没有索引的做法是全表扫描(Full Table Scan)——从第一个数据页读到最后一个数据页,逐行比对。假设每个数据页 16 KB,一亿行占 20 GB,即使顺序读能跑到 500 MB/s,也需要 40 秒。加一个 B+Tree 索引,三次磁盘 I/O…
从零理解 LSM-Tree 存储引擎的设计哲学:B-Tree 与 LSM-Tree 的本质差异,写放大/读放大/空间放大的三角权衡,以及 WAL、MemTable、SSTable、Compaction、Bloom Filter 各组件的角色与协作关系。从零写一个 LSM-Tree 存储引擎系列第 1 篇。
从零实现 SSTable 和 Bloom Filter:Data Block 前缀压缩与 restart 二分查找、Bloom Filter 双重哈希把误判率压到约 1%、SSTable Builder 和 Reader 的完整 C 代码。从零写一个 LSM-Tree 存储引擎系列第 3 篇。
五篇长文,从 LSM-Tree 的设计哲学讲到完整 KV 引擎实现,最后用 Rust 重写并三方 benchmark 对比。每篇含完整 C 代码、架构图、数学推导。