SSDB 的存储基石:LevelDB SSTable 文件格式全解析

数据库KV存储数据存储【免费下载链接】ssdbSSDB - A fast NoSQL database, an alternative to Redis项目地址https://gitcode.com/gh_mirrors/ss/ssdb点击查看免费下载SSDB 是构建在 LevelDB 之上的 NoSQL 数据库其磁盘持久化能力完全依赖 LevelDB 的 SSTableSortedStringTable文件。本文基于 LevelDB 官方的表格式文档 table_format.md 及其配套实现源码系统拆解 SSTable 文件的总体布局、BlockHandle 内部指针、Data/Index/Meta 各类数据块、固定长度的 Footer 以及 filter 与 stats 两个元数据块的二进制格式并结合 table_builder.cc、table.cc 等实现给出从写入到读取的完整调用链。读完本文你将能够按字节级格式手工解读一个 SSTable 文件并理解 SSDB 中 Bloom 过滤器是如何落到磁盘格式里的。文件总体布局一个 SSTable 文件由五类结构线性排布而成官方文档中的布局图如下beginning_of_file [data block 1] [data block 2] ... [data block N] [meta block 1] ... [meta block K] [metaindex block] [index block] [Footer] (fixed size; starts at file_size - sizeof(Footer)) end_of_file各部分职责Data blocks文件中所有 key/value 对按排序顺序依次存放并被切分成若干数据块紧密排列在文件开头。每个数据块由 block_builder.cc 的代码生成随后可以optional被压缩。Meta blocks数据块之后存放若干元数据块。官方文档定义了 filter 和 stats 两种类型且允许未来继续扩展新类型。每个 meta block 同样使用block_builder.cc的格式组织也可以被压缩。metaindex block对每一个其他 meta block 记录一条索引项键是 meta block 的名字值是定位该 meta block 的 BlockHandle。它是元数据目录。index block对每一个 data block 记录一条索引项。键是一个满足大于等于该数据块最后一个 key、且小于下一个数据块第一个 key的字符串值是该数据块的 BlockHandle。Footer文件最末尾的定长结构包含 metaindex 块与 index 块的 BlockHandle 以及一个 magic number。因为定长所以打开文件时可以从file_size - sizeof(Footer)处直接定位。这种数据在前、目录在后的设计意味着读取任意一个数据块只需两次间接跳转——从 Footer 拿到 index block 的 handle在 index block 中二分找到目标数据块 handle再到文件对应偏移处读取。BlockHandle文件内部指针文件中所有结构之间的引用都通过一种称为 BlockHandle 的内部指针完成其编码极其简洁offset: varint64 size: varint64varint64 是变长整型编码小数值占用更少的字节。在 format.h 中BlockHandle类封装了offset_与size_两个uint64_t字段并声明了编码上限// Maximum encoding length of a BlockHandle enum { kMaxEncodedLength 10 10 };即单个 BlockHandle 最多编码为 10varint64 最大 10 字节 10 字节。EncodeTo与DecodeFrom的实现见 format.cc解码失败时返回Corruption(bad block handle)这是整个文件自校验体系的起点之一。Data block 的内部结构前缀压缩与 restart point文档第 1 节指出数据块由block_builder.cc格式化。block_builder.cc 的文件头注释给出了块内精确的字节格式An entry for a particular key-value pair has the form: shared_bytes: varint32 unshared_bytes: varint32 value_length: varint32 key_delta: char[unshared_bytes] value: char[value_length] shared_bytes 0 for restart points. The trailer of the block has the form: restarts: uint32[num_restarts] num_restarts: uint32核心机制是前缀压缩每个 key 只保存与上一个 key 不共享的后缀key_delta以显著节省空间每隔 K 个 keyblock_restart_interval默认 16设置一个 restart point该点存完整 key。块尾部追加 restart 点偏移数组和数组长度使得查找时可以在 restart 数组上二分再顺序前缀解压兼顾空间与查找效率。写入路径上TableBuilder::Add在 table_builder.cc 中将 key/value 送入data_block当CurrentSizeEstimate()达到options.block_size默认 4KB时触发Flush()。注意一个容易忽略的细节index block 使用独立的index_block_options且block_restart_interval 1见 table_builder.cc意味着索引块几乎不做前缀压缩换取随机定位时的解码速度。Meta block 与 metaindex元数据的自描述目录meta block 让 SSTable 可以携带格式本身的扩展信息而不破坏兼容性。metaindex block 作为目录的目录其条目形如键: filter.N meta block 的名字 值: 指向该 meta block 的 BlockHandle在 table_builder.cc 的 Finish() 中可以看到写入顺序先写 filter block再构建 metaindex block把filter. filter_policy-Name()作为键、filter block handle 作为值最后才写 index block 与 Footer。读取侧对应 table.cc 的 ReadMeta()从 metaindex 中 Seek 到filter.Name并解码出 filter block handle。值得注意的是ReadMeta对读取错误采取静默忽略策略meta info is not needed for operation元数据损坏不会阻断基本读写。index block如何选出最短的索引键文档规定 index block 的键大于等于该数据块最后一个 key且小于下一个数据块第一个 key。这个大于等于并不要求取最后一个 key 本身——TableBuilder会推迟写入索引项直到看到下一个数据块的第一个 key从而调用comparator-FindShortestSeparator()生成尽可能短的最短分隔键。table_builder.cc 的注释给出了经典例子若两块的分界 key 是 the quick brown fox 与 the who则索引键可以只用 the r。这能进一步压缩 index block 的体积而 index block 在打开表时会被整体载入内存对大文件的内存占用有实际意义。表尾最后一个块的索引键则用FindShortestSuccessor()生成见 Finish()。Footer定长 48 字节与 magic numberFooter 是打开文件的第一步。文档给出的布局为metaindex_handle: char[p]; // metaindex 块的 BlockHandle index_handle: char[q]; // index 块的 BlockHandle padding: char[40-p-q]; // 零填充凑足 40 字节 magic: fixed64; // 0xdb4775248b80fb57 (little-endian)两个 BlockHandle 各按kMaxEncodedLength(10 字节) 预留空间不足部分零填充因此Footer 恒为 2×10 8 48 字节与 format.h 中的声明一致// Encoded length of a Footer. Note that the serialization of a // Footer will always occupy exactly this many bytes. enum { kEncodedLength 2*BlockHandle::kMaxEncodedLength 8 };magic number0xdb4775248b80fb57的来历写在 format.h 注释中对 LevelDB 项目主页 URL 执行sha1sum取前 64 位。Table::Opentable.cc首先检查文件大小是否达到 48 字节然后从size - Footer::kEncodedLength处读取并校验 magic失败即返回Corruption(not an sstable (bad magic number))——这是区分文件损坏和根本不是 SSTable的第一道闸门。块尾部1 字节类型 32 位 CRC每个落盘块数据块、meta 块、metaindex 块、index 块后面都跟随 5 字节 trailer由 format.h 定义// 1-byte type 32-bit crc static const size_t kBlockTrailerSize 5;写入时TableBuilder::WriteRawBlocktable_builder.cc依次追加块内容、压缩类型字节、以及覆盖块内容类型字节的 CRC32C经crc32c::Mask混淆以防弱位损坏。读取时ReadBlockformat.cc在options.verify_checksums开启下逐块校验不一致返回Corruption(block checksum mismatch)。关于压缩文档说的是optionally compressed而 1.20 版本实际只实现两档kNoCompression与kSnappyCompression。且 WriteBlock 中有一个实用策略——只有当 Snappy 压缩率超过 12.5% 才真正存储压缩结果否则退化为不压缩避免对不可压缩数据白白付出解压 CPU。解压后的块与 index 块会被标记cachable可进入block_cache。filter Meta Block2KB 粒度与偏移数组这是与读放大控制最相关的部分。当打开数据库时指定了FilterPolicy每个 SSTable 都会带一个 filter blockmetaindex 中记录一条从filter.N到 filter block handle 的映射其中N是FilterPolicy::Name()的返回值Bloom 过滤器即name加位数。filter 的分组粒度。filter i 覆盖的是文件偏移落在如下范围内的所有数据块的全部 key[ i*base ... (i1)*base-1 ]当前base固定为 2KB。举例若数据块 X 和 Y 的起始偏移都在[0KB .. 2KB-1]内则 X、Y 中的所有 key 会一起调用FilterPolicy::CreateFilter()生成一个过滤器作为 filter block 的第一个 filter 存储。源码中这个常数即 filter_block.cc 的kFilterBaseLg 11base 1 11FilterBlockBuilder::StartBlock直接用block_offset / kFilterBase定位组号。filter block 的字节布局[filter 0] [filter 1] [filter 2] ... [filter N-1] [offset of filter 0] : 4 bytes [offset of filter 1] : 4 bytes [offset of filter 2] : 4 bytes ... [offset of filter N-1] : 4 bytes [offset of beginning of offset array] : 4 bytes lg(base) : 1 byte尾部的偏移数组使得数据块偏移 → 对应 filter的映射是 O(1)index block_offset base_lg_。FilterBlockReader的构造filter_block.cc从块尾先读 1 字节base_lg_再读 4 字节得到偏移数组起点反推出数组长度KeyMayMatch则在取不到合法 filter 时保守地返回 trueErrors are treated as potential matches宁可多读一次数据块也不允许漏查。filter 数据块本身按kNoCompression写入见 Finish()。在 SSDB 中这一步由 ssdb_impl.cpp 的leveldb::NewBloomFilterPolicy(10)完成——每 key 10 比特的 Bloom 过滤器随每个 SSTable 落盘这正是 SSDB 作为点查型数据库减少无效磁盘读的关键配置。stats Meta Block规划中文档还定义了 stats meta block 的用途键为统计项名字值为统计项内容计划记录 data size、index size、key size (uncompressed)、value size (uncompressed)、entry 数量、data block 数量等指标。但需要明确当前版本的实现边界该节标注TODO(postrelease)而在本仓库源码中table_builder.cc 对应位置同样只有一行// TODO(postrelease): Add stats and other meta blocks即1.20 版本构建出的 SSTable 实际不会写入 stats blockmetaindex 中仅包含 filter 一项。阅读旧文档或新版本行为时不要将这两段 TODO 误认为已实现功能。写入与读取的完整调用链将上述格式串联起来SSTable 的生命周期如下写入TableBuildertable_builder.ccAdd(key, value)追加到data_block同时向filter_block记录 key块满则Flush()Flush()→WriteBlock→ 可选 Snappy 压缩 →WriteRawBlock写块内容 5 字节 trailer更新 handle 的 offset/size并触发filter_block-StartBlock(offset)开新 filter 组Finish()依次写 filter block、metaindex block、index block、Footer顺序与文件布局一致。读取Tabletable.ccTable::Open从文件尾读 48 字节 Footer校验 magic再据index_handle一次性ReadBlock加载 index block含 CRC 校验受paranoid_checks影响ReadMeta若设置了 filter policy读 metaindex block定位filter.Name条目再读 filter block 交给FilterBlockReader点查时先以block_offset查 filterKeyMayMatch命中后经 index block 的二分迭代器two-level iterator定位数据块最后做前缀解压解码。小结SSTable 格式的设计可以概括为三条原则定长 Footer 提供 O(1) 的文件入口48 字节 magic 双保险BlockHandle 的 varint 编码让所有内部引用紧凑而自描述metaindex 使元数据可无限扩展——filter、未来的 stats乃至第三方扩展块都不需要改动核心布局。对维护 SSDB 或基于 LevelDB 的项目而言理解这套格式的价值在于你能用 hexdump 解释一个.ldb文件的任何字节能判断损坏发生在哪一层magic、CRC、handle、重启数组也能解释为什么 SSDB 的block_size、Bloom filter 位数等配置会以这样的方式最终作用于磁盘。赞分享数据库KV存储数据存储【免费下载链接】ssdbSSDB - A fast NoSQL database, an alternative to Redis项目地址https://gitcode.com/gh_mirrors/ss/ssdb点击查看免费下载相关推荐SSDB 的存储基石:LevelDB 写前日志(WAL)文件格式与读写实现详解SSDB 的存储基石:LevelDB 写前日志 WAL 文件格式与读写实现详解 本篇以 SSDB 仓库内嵌的 LevelDB 1.20 引擎文档 log_for数据库KV存储数据存储LevelDB 深入解析SSTableTable文件格式与 TableCache 缓存机制LevelDB 深入解析SSTableTable文件格式与 TableCache 缓存机制 导读 本篇基于 LevelDB 官方源码的核心文件 db/ta人工智能AI 应用AI AgentSSDB 的存储基石leveldb 1.20 持久化键值存储 API 详解与调优实践SSDB 的存储基石leveldb 1.20 持久化键值存储 API 详解与调优实践 本文基于 SSDB 仓库内置的 leveldb 1.20 用户文档 d数据库KV存储数据存储上一篇OptiScaler完整指南如何跨显卡品牌享受顶级画质增强技术下一篇如何利用IPED元数据查看器快速定位数字证据终极免费工具使用指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考