Gorilla压缩算法在mandodb中的应用：如何将16字节数据点压缩至1.37字节

Gorilla压缩算法在mandodb中的应用：如何将16字节数据点压缩至1.37字节

【免费下载链接】mandodb🤔 A minimize Time Series Database, written from scratch as a learning project. 从零开始实现一个 TSDB项目地址: https://gitcode.com/gh_mirrors/ma/mandodb

mandodb是一个从零开始实现的最小化时序数据库（TSDB），专为学习目的而开发。在时序数据库中，数据压缩算法对性能起着至关重要的作用。mandodb采用了Facebook Gorilla压缩算法，能够将每个16字节的数据点（包含时间戳和值）平均压缩至仅1.37字节，极大地提升了存储效率和查询性能。

🧮 Gorilla压缩算法的核心原理

Gorilla压缩算法是Facebook在2015年发表的论文《Gorilla: A fast, scalable, in-memory time series database》中提出的时序数据压缩方案。该算法通过对时间戳和数值分别进行优化编码，实现了极高的压缩比。

Gorilla压缩算法框架示意图，展示了时间戳和值的压缩流程

时间戳压缩：差值的差值（Delta of Delta）

在时序数据中，相邻数据点的时间戳通常具有固定间隔。Gorilla算法通过记录时间戳的差值（delta）而非原始值来减少存储空间，进一步对差值计算差值（delta of delta），使大多数情况下的变化值趋近于零。

t1: 1627401800; t2: 1627401810; t3: 1627401820; t4: 1627401830 -------------------------------------------------------------- // 差值：delta t1: 1627401800; (t2-t1)d1: 10; (t3-t2)d2: 10; (t4-t3)d3: 10; -------------------------------------------------------------- // 差值的差值：delta of delta t1: 1627401800; dod1: 0; dod2: 0; dod3: 0;

根据差值的范围，算法使用不同长度的控制位和数据位进行编码：

• 差值为0：仅用1位表示
• 差值在[-63, 64]：2位控制位 + 7位数据位
• 差值在[-255, 256]：3位控制位 + 9位数据位
• 差值在[-2047, 2048]：4位控制位 + 12位数据位
• 其他情况：4位控制位 + 32位数据位

值压缩：XOR与有效位编码

对于浮点数值，Gorilla算法通过计算当前值与前一个值的XOR结果，利用结果中大量连续零位进行压缩。具体步骤包括：

1. 计算当前值与前值的XOR
2. 统计结果的前置零和后置零数量
3. 仅存储非零有效位部分

IEEE 754浮点数表示及XOR计算结果示意图，展示了相似值之间XOR结果的零位分布

📊 压缩效果与性能分析

Gorilla算法的压缩效果在实际应用中表现卓越。论文数据显示，时间戳差值相同的比例高达96.39%，而值压缩中仅需1位表示的情况占比达59.06%。

时间戳差值分布统计，显示大多数情况下差值为零或较小范围

值压缩结果分布统计，展示不同压缩情况的占比

另一个重要结论是，数据压缩比随着时间的增长而提高，并在约120个数据点后趋于稳定。

压缩率随数据点数量变化的曲线，显示压缩效率随数据量增加而提升

💻 mandodb中的实现与应用

在mandodb中，Gorilla压缩算法被应用于Data Block的数据存储。相关实现可在项目源码中查看，特别是时序数据的写入和压缩逻辑：

// Push 负责写入时序数据 func (s *Series) Push(t uint32, v float64) { // 时间戳压缩逻辑 // ... // 值压缩逻辑 // ... }

mandodb还支持在Gorilla压缩基础上选择ZSTD或Snappy算法进行二次压缩，以进一步减小存储空间：

// 支持的压缩算法类型 const ( NoopBytesCompressor BytesCompressorType = iota // 不压缩 ZstdBytesCompressor // ZSTD压缩 SnappyBytesCompressor // Snappy压缩 )

通过这种多层压缩策略，mandodb能够在保持高性能的同时，显著降低存储成本。实际测试显示，存储8万条时间线共接近1千万数据点的数据块仅占用约28M磁盘空间，相比原始数据节省了约98.5%的存储空间。

🚀 总结与应用建议

Gorilla压缩算法通过巧妙的差值编码和位运算，为时序数据提供了极高的压缩效率，是mandodb实现高性能的关键技术之一。对于需要处理大量时序数据的应用场景，采用类似的压缩策略可以显著提升系统性能和降低存储成本。

在使用mandodb时，可以根据实际需求选择合适的压缩配置：

• 追求极致性能：使用Gorilla算法单独压缩
• 追求最小存储：启用ZSTD或Snappy二次压缩
• 平衡考虑：默认配置已针对大多数场景优化

通过理解和应用Gorilla压缩算法，我们不仅可以更高效地处理时序数据，还能深入领会数据库设计中的空间优化思想。

【免费下载链接】mandodb🤔 A minimize Time Series Database, written from scratch as a learning project. 从零开始实现一个 TSDB项目地址: https://gitcode.com/gh_mirrors/ma/mandodb