数据湖大数据数据存储【免费下载链接】icebergApache Iceberg项目地址https://gitcode.com/gh_mirrors/icebe/iceberg点击查看免费下载本指南完整解读 Apache Iceberg 仓库中 Mumbling Bitmap 规范版本 1。Mumbling 是一种面向有界总大小场景典型如行级删除向量 deletion vector设计的压缩位图格式其思想源于 Roaring Bitmap但通过描述符数组descriptor array与 PFOR 编码将每个容器的元数据开销压缩到极致。读完本文你将掌握 Mumbling Bitmap 的二进制布局、容器与描述符的编解码规则、PFOR 单字节数组压缩算法以及这些规范在 Iceberg 核心模块中的实际实现与调用链。背景与设计动机为什么需要 Mumbling BitmapApache Iceberg 的行级删除向量deletion vectorDV用于标记数据文件内被逻辑删除的行位置。这类位图有两个鲜明特征总量有界且很小单个删除向量通常只有不到 100,000 个条目因此位图的总大小必须受到严格限制才能作为元数据内嵌存储需要极低的单容器开销删除向量会随 manifest 一起序列化任何冗余的元数据字节都会被放大到海量数据文件上。Mumbling Bitmap 正是为这种小、内嵌、有界的用例而设计。在 Iceberg 核心模块中删除向量作为 manifest 信息的一部分存储见 ManifestInfo.java 中的manifestDeletionVector()接口与 ManifestInfoStruct.java 中通过MumblingBitmaps.read(ByteBuffer.wrap(dv))完成反序列化的实现格式本身即遵循本规范。总体设计与 Roaring Bitmap 的对比与核心取舍Mumbling Bitmap 与 Roaring Bitmap 共享同一个基本思路把位图划分为固定大小256 bit的区域每个区域称为一个容器container。每个容器要么是稀疏sparse的存储 0-255 范围内的偏移值列表要么是稠密dense的存储 32 字节的位集合。与 Roaring 的主要差异在于尺度与寻址方式Mumbling 中每个容器至多 32 字节稀疏容器 0-31 字节稠密容器固定 32 字节整个位图被限制为至多2,097,152 个值8,192 个容器 × 每个容器 256 bit容器不是通过键key 基数cardinality 偏移offset三元组跟踪而是通过描述符数组descriptor array跟踪每个容器对应一个描述符字节该字节在数组中的下标位置隐式编码了容器内位置的高位即 Roaring 中的 key。设计取舍可以归纳为两点每个描述符都必须存在即使容器为空0 长度也要占一个描述符字节由于需要表达空状态描述符无法直接编码容器基数最高可达 256因此引入PFOR 编码来压缩描述符数组的开销。偏移不直接存储容器的偏移可以由相对较小的描述符数组计算得出而根据 key 查找描述符只需一次数组索引descriptors[pos 8]。规范还对比过另一种备选方案直接存储偏移、用相邻偏移之差推导容器长度。该方案被否决原因一是偏移值递增导致数组编码效果更差二是描述符剩余的比特位无法被利用。二进制格式布局一个 Mumbling Bitmap 由三部分顺序拼接而成Header头部Descriptor array描述符数组Containers容器数据格式中所有整数均为无符号数按**小端序little endian**存储。Header字段大小说明格式版本1 字节版本 1 为0x01基数Cardinality3 字节置位set bit的总数容器数量2 字节位图中容器的个数由于容器数量上限为 8,192因此基数上限为2,097,1528,192 个容器 × 每容器 256 bit。这一约束同样体现在实现中MumblingBitmap.java 在构造时校验containerCount 8192与cardinality 2_097_152测试工具 MumblingTestUtil.java 也强制相同的上限。描述符数组Descriptor array描述符数组每容器一个字节长度等于容器数量。字节的最高 3 个比特位决定容器类型并决定其余低位比特如何解释MSB 模式容器类型说明剩余比特含义000稀疏Sparse0-31 字节的稀疏容器容器长度 / 置位个数001稠密Dense32 字节的稠密容器必须为 0在 v1 中描述符字节编码其对应容器的大小。最高两个比特位保留给未来版本使用对于稠密容器如果低位比特被置位实现必须忽略它们即仅把描述符视为0x20。规范给出的示例描述符Hex二进制含义000000 00000 个值的稀疏容器050000 01015 个值的稀疏容器1F0001 111131 个值的稀疏容器200010 0000稠密容器存储 32 字节描述符数组使用 附录 A 中定义的patched frame of referencePFOR编码。之所以选择 PFOR是因为它可以高效存储大部分容器大小接近、偶有较大值的分布形态且其二进制表示本身就能为每个值节省至少 2 个比特位。在 Iceberg 实现中PFOREncoding.java 负责描述符数组的编解码MumblingBitmap在首次查询时调用PFOREncoding.decode(data, HEADER_SIZE, descriptorArray, 0, containerCount)惰性解码。容器Containers容器区由拼接的容器数据组成每个容器存储位图的一个 256 bit 区域。位图位置被拆分为两部分前 16 位标识所在容器容器索引后 8 位标识容器内的对应位置。容器可以是稀疏或稠密类型由其对应的描述符字节编码。置位少于 32 个的容器必须为稀疏置位 32 个或以上的必须为稠密。测试工具 MumblingTestUtil.java 中的cardinality校验也贯彻了这一规则若 32 字节容器的置位不足 32会抛出 Invalid dense container: %s values should be sparse。稀疏容器Sparse containers稀疏容器编码至多 31 个置位位置其余位置均为未置位。每个置位位置存储为一个无符号字节0-255表示相对容器起始位置的偏移。位置列表必须升序排列这使得查询某个位置是否置位时可以在遇到更高位置或到达列表末尾时提前停止稀疏容器的长度不存储在容器内部而是由对应描述符字节的值给出。示例描述符容器字节置位位置0零字节无300 22 FF0, 34, 2553100 01 02 ... 1E0, 1, 2, ..., 30稠密容器Dense containers稠密容器将容器内每个比特编码为 0未置位或 1置位存放在一个 32 字节数组中。数组第一个字节包含比特 0-7下一个字节包含 8-15依此类推比特位置按从最高有效位到最低有效位排列容器内第 0 个位置是第一个字节的最高位第 255 个位置是最后一个字节的最低位。示例描述符容器字节置位位置32FF FF FF FF 00 ... 000-3132FF FF FF FF 80 ... 000-3232FF FF 00 ... 00 FF FF0-15, 240-25532AA AA ... AA AA偶数位置0, 2, 4, ...以上四个示例全部被还原为单元测试见 TestMumblingBitmap.java 中的testDenseSpecExample1至testDenseSpecExample4。位图查询操作Mumbling Bitmap 用描述符数组跟踪容器。为支持快速查找实现应解码描述符数组并据此生成偏移数组offset array。访问某个位置所属的容器需要先通过描述符数组找到其类型与偏移。描述符数组的下标即位置除以 256 的商let container_index: u16 (pos 8) as u16容器的偏移等于其前面所有容器长度之和长度由各容器描述符确定let descriptor: u8 descriptors[container_index] let offset: usize offsets[container_index]容器内的对应位置是位图位置的最低 8 位let pos_in_container: u8 (pos 0xFF) as u8在 Java 实现 MumblingBitmap.java 中isSet(int pos)完整实现了这套逻辑containerIndex pos 8、posInContainer pos 0xFF稠密容器按byteIndex posInContainer 3、bitShift 7 - (posInContainer 0b111)逐位判断稀疏容器则顺序扫描升序列表遇到大于目标位置的值即返回false。decodeDescriptors()方法通过descriptorsToOffsets把容器长度数组转换为绝对偏移数组例如descriptorsToOffsets(0, [1, 1, 2])产生[0, 1, 2, 4]整个解码过程是惰性的构造函数只校验版本与边界只有首次调用isSet时才解码描述符并构建偏移数组这是该类唯一维护的派生状态。附录 APFOR 单字节数组编码PFORPatched Frame of Reference编码用于压缩无符号字节数组是描述符数组的压缩手段。分块规则将值数组切分为256 个值一组的块chunk最后一个块可以是余数更短。每个块的长度不显式编码——解码时根据剩余值数量自然推导实现 PFOREncoding.java 中chunkLength Math.min(CHUNK_SIZE, count - valuesEncoded)。每个块的结构每个块独立编码由以下四部分拼接而成Header3 字节主值数组Primary value array异常偏移Exception offsets异常值数组Exception value array编码过程的核心思想是先用块内最小值做归一化把每个值减去最小值再选择一个主位宽b1容纳块中大多数值放不进b1位的**异常值exception**被单独收集其位置记录在偏移数组中其超出b1的高位比特打包进异常值数组。Header 布局Header 存储块编码的关键参数b1主值数组中每个值的位宽b2异常值数组中每个值的位宽至多为8 - b1e无法容纳于b1位的异常值个数m从每个值中减去的常量通常为块内最小值。Header 将b1与b2打包进一个字节随后依次是e和m字节比特字段00-3b104-7b210-7e20-7mJava 实现中PFOREncoding.java 的writeHeader写入(b2 4) | (b1 0b1111)、e、base三个字节解码端decodeChunk以同样的位布局读出b1、b2、excCount、base。编码步骤编码一个块的过程找出块内最小值m将块内每个值减去m归一化选择位宽b1和b2见下文将每个值的低b1位打包进32 * b1字节的主数组收集无法容纳于b1位的异常值及其偏移写出异常偏移数组每个异常 1 字节对每个异常将其剩余的b2位打包进ceil(e*b2/8)字节。位宽选择算法规范推荐的b1、b2选择方式对每个值求出存储它所需的最少比特数统计需要每种位宽0-8的值个数并找出最大位宽对每个候选位宽b计算该位宽下的总大小令e为异常个数即更大位宽对应计数之和令b2为异常位宽即最大位宽减去b总大小为32*b e ceil(e*b2/8)选择使总大小最小的位宽b1。实现中的chooseBitWidthPFOREncoding.java正是按此公式穷举候选位宽且平局时偏好更大的位宽以减少异常个数size bestSize时更新。打包顺序与补齐值打包时第一个值占据最高有效位MSB-first。如果某个打包段不满整字节则用 0 填充到下一个字节边界。例如位宽b 2时数组[3, 2, 1, 2, 3]存储为二进制1110 0110 1100 0000即十六进制E6 C0。对应实现见 BitPacking.java其中packWord2将 8 个 2 位值按 MSB-first 拼入 16 位字。b1 8的特殊情况当b1为 8 时每个值原样存储为一个字节此时不存在异常e必须为 0b2必须为 0并推荐实现直接存储原始值即m为 0。PFOREncoding.java 对此特例做了专门处理写入b18, b20, e0, m0的头部后直接以原始字节复制值。编码示例长度编码字节数组hex解码后的值说明25600 00 00256 个值全部为 0每个值 0 位m 0无异常5100 00 0551 个值全部为 5每个值 0 位m 5无异常880 02 00 04 07 FF FE[0, 0, 0, 0, FF, 0, 0, FE]每个值 0 位m 02 个异常每异常 8 位302 00 06 18[6, 7, 8]每个值 2 位m 6无异常432 01 06 09 01 E0[6, 34, 8, 7]每个值 2 位m 61 个异常每异常 3 位这些示例均可与测试对照随机与边界场景分别由 TestPFOREncoding.java 与 TestPFOREncodingRandom.java 覆盖后者借助 PFORRandomData.java 生成随机数据验证编解码往返一致性。在 Iceberg 核心模块中的实现与使用路径Mumbling Bitmap 的规范实现位于 Iceberg 核心模块org.apache.iceberg.mumbling包core/src/main/java/org/apache/iceberg/mumbling/包含四个类MumblingBitmap.javaByteBuffer上只读的位图视图实现ManifestBitmap接口提供cardinality()、isSet(int pos)、buffer()MumblingBitmaps.java静态工厂read(ByteBuffer)从序列化字节流还原ManifestBitmapPFOREncoding.java附录 A 规范的完整编解码实现含encode/decode与最坏情况大小估算estimateEncodedSize每块 3 字节头 每值 1 字节BitPacking.java1-7 位宽的按位打包/解包按 8 值一组展开为专用方法packBits1至packBits7MSB-first 排列。在删除向量的使用路径上删除向量作为 manifest 的一个字段ManifestInfo.DV存储见 ManifestInfoStruct.java 的ManifestInfo.DV字段访问时通过 ManifestInfo.java 的manifestDeletionVector()延迟加载实际反序列化发生在ManifestInfoStruct.manifestDeletionVector()ManifestInfoStruct.java调用MumblingBitmaps.read(ByteBuffer.wrap(dv))。文件适配层 TrackedFileAdapters.java 同样实现了manifestDeletionVector()为读取端提供统一的位图访问入口。总结Mumbling Bitmap 是 Iceberg 为小规模、有界、内嵌删除向量量身定制的压缩位图格式以 256 bit 容器为基本单元、以 1 字节描述符 PFOR 编码把容器元数据开销压到每个容器不足一字节配合块内归一化与位宽选择通常仅需 0-3 位/值并用隐式 key 省去 Roaring 中每容器 4 字节的键与偏移开销。整个格式在 core/src/main/java/org/apache/iceberg/mumbling/ 中有完整、经过随机与规范示例双重测试的实现任何需要嵌入 manifest 的删除向量读取端都可以通过MumblingBitmaps.read直接使用。赞分享数据湖大数据数据存储【免费下载链接】icebergApache Iceberg项目地址https://gitcode.com/gh_mirrors/icebe/iceberg点击查看免费下载相关推荐Duix.Avatar免费开源AI数字人本地部署教程3分钟克隆你的数字分身Duix.Avatar免费开源AI数字人本地部署教程3分钟克隆你的数字分身 上传一段10秒左右的视频就能得到一段你自己出镜的口播视频这就是 Duix.Av数据湖大数据数据存储iOS 10越狱如何用Yalu102解锁你的64位苹果设备iOS 10越狱如何用Yalu102解锁你的64位苹果设备 对于iOS 10用户来说Yalu102是一个备受关注的越狱工具它专门为64位设备提供iOS数据湖大数据数据存储Zstandard 压缩格式规范深度解析v0.3.9Zstandard 压缩格式规范深度解析v0.3.9 本文基于 MongoDB 仓库内置的 Zstandardzstdv0.3.9 格式规范文档 zst数据库文档数据库后端上一篇WAN2.2-14B-Rapid-AllInOne MEGA版视频生成模型的集成化革命下一篇Label Studio RESTful API终极指南资源命名与状态码规范详解创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
