MongoDB BSON Column 列式压缩格式详解从 Simple8b 编码到 BSONColumnBuilder 与块解码器【免费下载链接】mongoThe MongoDB Database项目地址: https://gitcode.com/GitHub_Trending/mo/mongoBSON Column 是 MongoDB 内核中一套面向 BSON 数据的高密度列式压缩表示其核心思想是将同类值序列编码为 delta / delta-of-delta 后存入 Simple-8b 块用控制字节区分字面量、delta 序列与交错interleaved序列并为重复值保留专门的游程编码RLE选择器。本文基于仓库中src/mongo/bson/column/目录的实现文档与源码完整讲解该格式的编码结构、三种解码/聚合路径迭代器、块解码器、路径解码以及 Simple8b 的底层块布局读完后可理解 BSON 数据如何在二进制层面被压缩、解码与聚合计算。格式总览控制字节 Simple8b 块BSON Column 数据以 BinData 子类型 7Column的 BSON 元素承载BSONColumn 类的注释总结了该格式的主要能力隐式字段名索引式 key 不落盘、类型专属的 delta / delta-of-delta 压缩、double 的缩放取整存储、缺失值missing/skip的内部编码、重复值的 RLE以及对象/数组按标量子流交错的压缩。编码由 BSONColumnBuilder 完成从文档和源码结构看其数据组织为若干“序列sequence”每个序列以一个控制字节开头指明该序列的性质字面量序列以原始 BSON 形式写入一个元素序列的第一个元素总是字面量其余元素以 delta 数值编码Simple8b delta 序列控制字节后跟 116 个 64 位 Simple8b 块kMaxNumSimple8bPerControl 16见 bsoncolumn_util.h交错序列用于对象/数组以“引用对象 多条交错 delta 流”编码。控制字节的分类逻辑集中在 bsoncolumn_util.hinline bool isUncompressedLiteralControlByte(uint8_t control) { return (control 0xE0) 0 || control (uint8_t)stdx::to_underlying(BSONType::minKey) || control (uint8_t)stdx::to_underlying(BSONType::maxKey); } inline bool isInterleavedStartControlByte(char control) { return control kInterleavedStartControlByteLegacy || // 0xF0 control kInterleavedStartControlByte || // 0xF1 control kInterleavedStartArrayRootControlByte; // 0xF2 } inline bool isSimple8bControlByte(uint8_t control) { return control ! stdx::to_underlying(BSONType::eoo) !isUncompressedLiteralControlByte(control) !isInterleavedStartControlByte(control); }可见低 3 位为 0 的控制字节以及 minKey/maxKey 对应的值表示字面量0xF0旧版对象交错、0xF1对象交错、0xF2以数组为根的交错是交错序列起始字节其余值含 eoo 除外是 Simple8b 序列控制字节其低 4 位1给出块数numSimple8bBlocksForControlByte。对 double 类型控制字节高 4 位还携带“缩放指数”scale indexkControlByteForScaleIndex {0x90, 0xA0, 0xB0, 0xC0, 0xD0, 0x80}与scaleIndexForControlByte()负责解析bsoncolumn_util.h#L19-L23, L68-L87。快速上手编码与两种解码路径README 给出的通用用法展示了最小闭环// Using the bson column builder to encode values BSONColumnBuilder cb; cb.append(elem1); cb.append(elem2); BSONBinData binData cb.finalize(); // Using the BSONColumn iterator to decode values BSONColumn col(binData.data, binData.length); ASSERT_EQ(col.size(), 2); auto it col.begin(); ASSERT_EQ(*it, elem1); it; ASSERT_EQ(*it, elem2); it; ASSERT_FALSE(it.more()); // The block decoder requires defining an Appendable or Materializer which receives all decoded values // from BSONColumn, see bsoncolumn_helpers.h for definitions of these concepts BSONColumnBlockBased col2(binData.data, binData.length); boost::intrusive_ptr allocator{new BSONElementStorage()}; std::vectorBSONElement collection; col2.decompressBSONElementMaterializer, std::vectorBSONElement(collection, allocator); ASSERT_EQ(collection.size(), 2); ASSERT_EQ(collection[0], elem1); ASSERT_EQ(collection[1], elem2);解码有两条路径BSONColumn::Iterator逐元素物化接口类似BSONObj支持begin()/end()、operator[]O(N) 索引查找、size()、release()。返回的BSONElement由列内部引用计数的BSONElementStorage持有生命周期不超过BSONColumn本身多次遍历会累积内存直到析构或调用release()。BSONColumnBlockBased面向批量解码对整个同类型块迭代解码效率更高且额外提供按路径path解码的decompress()重载。Delta 与数值编码哪些类型走 delta、delta-of-delta所有能表示成数值形式的BSONElement都会被转换后以 delta 或 delta-of-delta 形式写入 Simple8b。具体类型划分由 bsoncolumn_util.h 三个内联函数定义判定函数类型含义usesDeltaOfDelta()oid、date、timestamp这类单调/缓变值对使用 delta-of-delta进一步压低差值onlyZeroDelta()regEx、dbRef、codeWScope、symbol、object、array、null、undefined、minKey、maxKey无法数值化的类型允许 delta 序列但 delta 只允许为 0即“第一个字面量的重复”uses128bit()numberDecimal、binData、string≤16 字节、code按 128 位整数处理短字符串因此可参与 delta 编码其余数值型int32/int64/double/bool 等走 64 位编码。值得注意的是 delta 的算术实现显式做了“按无符号运算再回转型”来保证溢出行为是回绕而非未定义行为// src/mongo/bson/column/bsoncolumn_util.h inline int64_t calcDelta(int64_t val, int64_t prev) { // Do the subtraction as unsigned and cast back to signed to get overflow defined to wrapped // around instead of undefined behavior. return static_castint64_t(static_castuint64_t(val) - static_castuint64_t(prev)); } inline int64_t expandDelta(int64_t prev, int64_t delta) { return static_castint64_t(static_castuint64_t(prev) static_castuint64_t(delta)); }解码端由 bsoncolumn.h 中的DecodingState::Decoder64 / Decoder128完成它们各自持有一个Simple8buint64_t/Simple8buint128_t迭代器游标与“上一编码值”materialize()负责把解码出的数值还原回BSONElementloadUncompressed加载字面量、loadControl加载控制字节、loadDelta加载 delta。Decoder64还额外保存scaleIndex与deltaOfDelta标记scale index 在读到 Simple8b 控制字节时才有效用于 double 的缩放还原。编码端在 bsoncolumnbuilder.hEncodingState内部以std::variantEncoder64, Encoder128维护当前编码器——根据最近元素类型切换 64/128 位编码器appendDelta()计算差值后交给Simple8bBuilderuint64_t/uint128_t组块。double 走特殊路径_appendDouble()先按当前 scale index 缩放取整若值放不下false则回退为不压缩存储_tryRescalePending()可在必要时把已缓存的 pending 值连同新值一起换到新的 scale index 重新编码这是文档中“doubles are scaled and rounded to nearest integer”的实现落点。Simple8b块布局、扩展选择器与 RLESimple8b 将数值序列紧凑编码为 64 位块序列。每个块低 4 位是选择器selector决定其余 60 位的解释方式例如选择器 1 表示 60 个 1 位值选择器 14 表示 1 个 60 位值。MongoDB 在标准 Simple8b 基础上做了三处扩展完整注释表见 simple8b_helpers.h#L16-L53Selector value: 0 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 | 15 (RLE) Integers coded: 0 | 60 30 20 15 12 10 8 7 6 5 4 3 2 1 | up to 1920 Value Bits/integer: 0 | 1 2 3 4 5 6 7 8 10 12 15 20 30 60 | Last Value added扩展选择器 7 与 8尾随零压缩选择器 7、8 的 8/7 个值存在 4 个浪费位MongoDB 把紧随基本选择器之后的 4 个“leftover”位用作扩展编码尾随零个数扩展 7 至多 15 个尾零扩展 8 中Selector8Large用 5 个位计数并以 4 为倍率至多 124 个尾零见kTrailingZerosMaxCount {0, 15, 60, 124}simple8b_helpers.h#L86-L89。这对 128 位值如字符串的差值很关键当 delta 的高位部分变化而低位大量为零时delta 可以被压缩进 60 个有效位。RLE 选择器 15kRleSelector 15表示“重复上一个值”用 4 位扩展位指定重复的 120 值块个数kRleMultiplier 120计数为(selectorExtension 1) * 120单个 RLE 块最多表达 1920 次重复simple8b_helpers.h#L61-L64, L252-L256。这正是 README 所述“保留一个独立 Simple8b 选择器用 4 位指定 120 值重复块数量”的实现。skip缺失编码槽位全 1 表示该位置为 missing 值常量simple8b::kSingleSkip 0xFFFFFFFFFFFFFFFE、kSingleZero 0xE分别表示“单个缺失块”“单个零值块”simple8b.h#L325-L332解码器借此快速跳过整段缺失。编解码基本接口如下builder 迭代器BufBuilder buffer; auto writeFn buffer { buffer.appendNum(simple8bBlock); return true; }; Simple8bBuilderuint64_t builder; builder.append(elem1, writeFn); builder.append(elem2, writeFn); builder.flush(writeFn); Simple8buint64_t decoder(buffer.release(), buffer.len()); auto it decoder.begin(); auto end decoder.end(); ASSERT_EQ(*it, elem1); it; ASSERT_EQ(*it, elem2); it; ASSERT_FALSE(it.more());Simple8bT读取端实现见 simple8b.h_loadBlock()按| Base Selector (0-3) | Selector Extension (4-7) | Bits for Values (8-63) |的布局解析块_loadValue()中若槽位值等于掩码全 1 则判定为 skipRLE 块则只加载剩余计数并沿用上一个值。除逐值迭代外simple8b.h#L342-L393 还提供基于预计算查表表的批量函数visitAll回调访问所有值、count、dense是否无缺失、last块序列最后一个值、sum与prefixSum对 delta 序列求运行和。README 指出这些批量实现的TableDecoder、ParallelTableDecoder、OneDecoder、SimpleDecoder位于 simple8b.inl针对不同表大小做了优化并通过一组静态定义按块大小分派具体实现——块解码器和聚合函数正是借此避免逐值循环。交错模式对象与数组的“引用对象 交错 delta 流”对对象/数组序列BSONColumnBuilder 采用交错模式序列以一个**引用对象reference object**字面量开头它包含该序列所有嵌套字段的超集且字段顺序即各 delta 流的交错顺序引用对象本身不作为待还原的元素解码其后每个对象编码为“引用对象中每个标量字段一条 delta 流”对象里缺失的字段在流中对应 missing 槽位各流的 Simple8b 块按各自组块完成的顺序写入同一 buffer交错含义所在由于块内元素个数可推解码端无需额外顺序信息。从源码结构看构建端的状态机很清晰InternalState::Interleaved有两个模式——kDeterminingReference引用对象尚未确定边接收对象边用BSONColumnBuilder::mergeObj()合并出新字段期间对象先缓存在bufferedObjElements和kAppending引用对象已定型新对象直接对其做 delta 编码遇到不兼容子字段则退出交错模式。主要逻辑在BSONColumnBuilder::_appendObj()与_finishDetermineSubObjReference()bsoncolumnbuilder.h#L510-L522每个标量子字段对应一个SubObjState内含独立的EncodingState与controlBlocks缓冲用于最终按正确顺序回写控制块。解码端BSONColumn::Iterator通过std::variantRegular, Interleaved _mode维护两种状态it时分别调用_incrementRegular()或_incrementInterleaved()bsoncolumn.h#L244-L255。首次遇到交错起始控制字节时执行_initializeInterleaving()遍历引用对象找出全部标量子字段为每个子字段建立带Simple8b解码器的DecodingState并按InterleavedSchema见 interleaved_schema.h重建对象层级交错段结束则_drainAndVerifyDecoders()校验所有子解码器同步耗尽。块解码路径则由BlockBasedInterleavedDecompressor承担见下节。块解码Appendable / Materializer 概念与路径解码块解码器的抽象定义在 bsoncolumn_helpers.hAppendable表示能接收列解码可能产出的所有BSONElement类型值bool、int32、int64、Decimal128、double、Timestamp、Date_t、OID、string_view、BSONBinData、BSONCode 及缺失值等的接收方Materializer只负责“把某个原始值定义并分配成具体的存储表示”的那部分逻辑默认提供BSONElementMaterializer物化为BSONElement以及模板类 Collector——给定Materializer和一个 STL 风格容器即满足Appendable其append()各重载都用MONGO_COMPILER_ALWAYS_INLINE标注以压低逐值成本并提供appendMissing()/appendLast()/appendPositionInfo()等辅助接口。BSONColumnBlockBased因此暴露三个decompress()入口bsoncolumn.h#L478-L500decompress(Buffer)Buffer满足Appendable整个列解码进自定义接收方decompressMaterializer, Container(collection, allocator)包装版内部构造Collector后调用 1路径解码decompress(allocator, std::spanstd::pairPath, Container paths)给定一组“从根对象出发的字段路径 容器”把各路径的值分别解码到各自容器。路径解码的实现直接可见于头文件模板bsoncolumn.h#L569-L678先处理前导的 simple8b 块全为 skip 时走decompressAllMissing再按控制字节分派——字面量对象直接append/appendMissing交错段交给internal::BlockBasedInterleavedDecompressor逐路径解码。需要特别留意其适用前提头注释明确约束列内元素必须是对象或 missing字面量只允许空对象其余对象数据必须为交错编码另有decompressIterative()作为基于迭代器的回退实现注释标明它主要用于测试。此外BSONColumnBlockBased::sum()对纯数值列直接求和仅限 NumberInt/NumberLong/NumberDouble/NumberDecimaloperator[]与contains(BSONType)提供索引查找与类型探测。聚合查询不解码全列即可 first/last/min/maxbsoncolumn_expressions.h 提供了一批针对压缩二进制的聚合函数实现位于 bsoncolumn_expressions_internal.hcount()/dense()统计元素总数含缺失/ 判断是否无缺失交错段按“该行所有子流均缺失才算缺失”精确计算first()/last()返回第一个/最后一个非缺失元素min()/max()返回最小/最大元素及其逻辑行号可选传入StringDataComparator*用于字符串比较minmax()一次扫描同时得到最小与最大。这些函数都模板化了CMaterializerrequires MaterializerCMaterializer通过把自定义 collector 传给块解码器间接利用 Simple8b 的表解码器直接从压缩块取得聚合结果而不必逐值物化。README 也提示它们可以作为“如何自定义 collector、以其他格式或附加计算得到解码结果”的范例。注意first/last/min/max的BSONBinData重载都会断言bin.type BinDataType::Column即只能作用于 Column 子类型的二进制。构建器进阶能力前缀 skip、中间 diff 与重开除 README 覆盖的核心用法外从 BSONColumnBuilder 的接口注释还能看到几个生产级能力可帮助理解该格式如何被长期增量使用append的语义细节忽略字段名EOO 视为 skipMinKey/MaxKey 抛InvalidBSONTypeBSONColumnColumn 子类型本身不允许嵌套在 Column 数据内部skip()追加一个“索引 skip”用于表达缺失行与 Simple8b 的 skip 槽位/kSingleSkip块配合intermediate()返回相对上一次intermediate()的二进制 diffBinaryDiff含data()/size()/offset()允许继续追加数据——适合增量写入场景从已有二进制重开的构造函数BSONColumnBuilder(const char* binary, int size)把构建器置于“仿佛已 append 完该列内容并调用过 intermediate()”的状态从而高效向已有列追加数据并计算 diff此构造后不能再调用finalize()BSONColumnBuilder(size_t numPrefixSkips)直接以前置 skip 数量初始化避免逐次skip()。测试与质量保障该目录自带了相当完整的测试与模糊测试矩阵可作为进一步深入阅读的入口功能测试bsoncolumn_test.cpp、bsoncolumn_blockbased_test.cpp、simple8b_test.cpp、interleaved_schema_test.cpp、simple8b_type_util_test.cpp模糊测试bsoncolumn_builder_fuzzer.cpp、bsoncolumn_decompress_fuzzer.cpp、bsoncolumn_decompress_paths_fuzzer.cpp、bsoncolumnbuilder_reopen_fuzzer.cpp、bson_column_validate_fuzzer.cpp、simple8b_fuzzer.cpp基准测试bsoncolumn_bm.cpp、simple8b_bm.cpp。小结BSON Column 是 MongoDB 源码中一套结构完整的列式压缩栈BSONColumnBuilder负责按类型把元素转为字面量、delta、delta-of-delta 或交错 delta 流并交给Simple8bBuilder组块控制字节体系字面量 / Simple8b 计数 / 交错起始 / double 缩放指数串联各序列Simple8b 的扩展选择器与 120 值 RLE 块分别解决 128 位差值的低位冗余和长重复段问题。解码侧则按场景三选一逐元素用BSONColumn::Iterator批量全量或按路径用BSONColumnBlockBased的三种decompress()聚合统计用bsoncolumn_expressions.h的 first/last/min/max。理解这一栈的关键文件依次是 README.md、bsoncolumn_util.h、simple8b.h、bsoncolumn.h 与 bsoncolumnbuilder.h。需要说明的是README 中提到的更详细格式规范文档为外部链接仓库内以本文列出的源码与注释为准部分块解码路径如路径解码仍有明确标注的适用限制使用前应核对头文件中的约束说明。【免费下载链接】mongoThe MongoDB Database项目地址: https://gitcode.com/GitHub_Trending/mo/mongo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考