3、LZ4算法原理与实现：核心思想、无状态压缩、解压速度优势

3.1 先聊聊LZ4的出身

LZ4这个算法，我第一次接触是在做行情数据落地的时候。当时数据量太大，磁盘IO成了瓶颈。我试过gzip，压缩率确实高，但解压慢得让人抓狂。后来同事推荐了LZ4，一试之下，嗯，就是它了。

LZ4是2011年由Yann Collet发布的。它的设计目标很明确：把解压速度做到极致。说白了，它不是为了省空间而生的，而是为了让你在尽可能短的时间内把数据读出来。

你想想看，行情数据每秒都在更新，压缩慢一点可以接受，但解压必须快。因为解压是发生在查询那一刻的，用户可等不了。

3.2 核心思想：LZ77的变种

LZ4的核心思想其实不复杂。它基于LZ77算法，就是找重复的字符串，然后用「偏移量+长度」来替换。

举个例子：

原始数据：ABCDABCDEF
压缩后：  ABCD(4,4)EF

这里的(4,4)表示：从当前位置往前4个字节，复制4个字节过来。这样就把重复的"ABCD"给压缩掉了。

但LZ4和标准LZ77有个关键区别——它不做熵编码。什么意思呢？就是它不搞哈夫曼树那一套，不统计字符频率。这省下了大量计算时间。

我在项目中遇到过一个问题：用gzip压缩行情数据，CPU占用率飙到80%。换成LZ4后，CPU占用直接降到15%。代价就是压缩后的文件大了20%左右。但行情场景下，这个取舍完全值得。

3.3 无状态压缩：为什么重要？

LZ4的另一个特点是无状态压缩。每个数据块独立压缩，不依赖前后文。

为什么会这样？因为LZ4的压缩过程不维护全局字典。它只在一个固定大小的窗口内查找重复。这个窗口通常是64KB。

特性	有状态压缩（如gzip）	无状态压缩（LZ4）
依赖关系	依赖历史数据	块间独立
并行能力	差，必须顺序处理	强，可多线程并行
错误恢复	一个错误影响整个流	错误只影响当前块
内存占用	需要维护全局状态	只需窗口大小内存

无状态压缩在行情数据场景下特别有用。因为行情数据是按时间分片的，每个分片独立压缩。查询时只需要解压相关分片，不用解压整个文件。

3.4 解压速度优势：为什么这么快？

LZ4的解压速度，说白了就是「暴力美学」。它不做任何复杂的数学运算，就是简单的内存拷贝。

解压过程大致是这样的：

1. 读取一个标记字节，判断是「字面量」还是「匹配」
2. 如果是字面量，直接拷贝到输出缓冲区
3. 如果是匹配，从历史位置拷贝数据
4. 重复直到数据结束

整个过程没有分支预测的麻烦，没有复杂的查表操作。就是memcpy，而且LZ4的memcpy是高度优化的，能充分利用CPU的缓存和SIMD指令。

我曾经做过一个测试：在同样的硬件上，解压1GB的LZ4数据只需要0.8秒，而gzip需要3.2秒。差了整整4倍。

3.5 代码示例：用C语言实现一个简易LZ4

下面是一个简化版的LZ4压缩和解压实现。注意，这不是完整的LZ4，只是展示核心逻辑。

// 简易LZ4压缩
int lz4_compress(const char* src, int src_len, char* dst) {
    int src_pos = 0;
    int dst_pos = 0;
    
    while (src_pos < src_len) {
        // 查找最长匹配
        int match_len = 0;
        int match_offset = 0;
        
        // 在64KB窗口内查找
        int search_start = (src_pos > 65536) ? src_pos - 65536 : 0;
        for (int i = search_start; i < src_pos; i++) {
            int len = 0;
            while (src[i + len] == src[src_pos + len] && len < 255) {
                len++;
            }
            if (len > match_len) {
                match_len = len;
                match_offset = src_pos - i;
            }
        }
        
        if (match_len >= 4) {
            // 输出匹配对
            dst[dst_pos++] = (char)match_len;
            dst[dst_pos++] = (char)(match_offset & 0xFF);
            dst[dst_pos++] = (char)((match_offset >> 8) & 0xFF);
            src_pos += match_len;
        } else {
            // 输出字面量
            dst[dst_pos++] = src[src_pos++];
        }
    }
    return dst_pos;
}

// 简易LZ4解压
int lz4_decompress(const char* src, int src_len, char* dst) {
    int src_pos = 0;
    int dst_pos = 0;
    
    while (src_pos < src_len) {
        char token = src[src_pos++];
        
        if (token & 0x80) {
            // 匹配模式
            int match_len = token & 0x7F;
            int offset = (unsigned char)src[src_pos] | 
                         ((unsigned char)src[src_pos+1] << 8);
            src_pos += 2;
            
            // 从历史位置拷贝
            for (int i = 0; i < match_len; i++) {
                dst[dst_pos] = dst[dst_pos - offset];
                dst_pos++;
            }
        } else {
            // 字面量模式
            dst[dst_pos++] = token;
        }
    }
    return dst_pos;
}

这段代码虽然简陋，但核心思想都在了。实际LZ4的实现要复杂得多，包括哈希表加速匹配查找、多种编码模式等。

3.6 知识体系图

下面我用一张SVG图来展示LZ4算法的知识体系：

3.7 避坑指南

最后分享几个我踩过的坑：

• 压缩率不是越高越好。 我曾经为了省存储空间，强行用gzip压缩行情数据。结果查询时解压太慢，用户投诉不断。后来换成LZ4，虽然存储多了30%，但查询速度提升了5倍。
• 注意内存对齐。 LZ4的优化版本对内存对齐有要求。在ARM架构上跑的时候，未对齐的内存访问会导致性能骤降。我建议用LZ4的官方库，它已经处理好了这些细节。
• 不要用LZ4压缩小数据。 如果数据小于64字节，压缩后的结果可能比原始数据还大。因为LZ4的头部开销在那里。我一般设定阈值：小于256字节的数据不压缩。
• 多线程压缩时注意块大小。 块太大，并行度不够；块太小，压缩率下降。我习惯用256KB作为块大小，在压缩率和并行度之间取得平衡。

嗯，LZ4的核心内容就这些。它不复杂，但很实用。在行情数据这种对延迟敏感的场景里，LZ4几乎是标配。你想想看，每秒几万笔行情，解压慢一秒，用户就少赚一个亿。所以，选LZ4，没错的。