大白话先说清楚 Delta 编码不存原值存相邻两个值的差。CPU使用率[50,52,51,53]变成[50,2,-1,2]数字变小了。 Zigzag 编码差值有正有负VarInt 压不好负数-1是全1的64位大数。Zigzag 把符号折叠进去0→0,-1→1,1→2,-2→3,2→4全变小正数VarInt 就能用1字节存了。 VarInt每7位一组打包最高位标记后面还有。差值通常 ±10Zigzag 后最大20一个字节搞定。 随机访问不能逐字节跳但可以分块——每128个点为一块记录每块在压缩流中的起始位置访问第N个就找到所在块从块头解码到第N个位置。 和 Gorilla 差异Gorilla 用XOR位级打包bit packing我们用 DeltaZigzagVarInt 字节流实现简单10倍压缩比85%接近。---代码?php// 依赖PHP 7.4 内置 SplFixedArray无需额外扩展// 如有 ext-ds可把 SplFixedArray 换成 Ds\Vector 性能更好classTsDelta{constBLOCK128;// 随机访问粒度越小随机访问越快索引越大privateSplFixedArray$idx;// 每块在 buf 中的字节偏移privatestring$buf;privatearray$queue[];// 未满一块的缓冲privateint$total0;privateint$nblock0;publicfunction__construct(int$cap){$this-idxnewSplFixedArray((int)ceil($cap/self::BLOCK));}publicfunctionpush(int$v):void{$this-queue[]$v;$this-total;if(count($this-queue)self::BLOCK)$this-seal();}// 把当前 queue 压缩成一个块写入 bufpublicfunctionseal():void{if(!$this-queue)return;$this-idx[$this-nblock]strlen($this-buf);$prev$this-queue[0];$this-buf.self::vi(self::zz($prev));// 块首存绝对值for($i1,$ncount($this-queue);$i$n;$i){$this-buf.self::vi(self::zz($this-queue[$i]-$prev));// 存 delta$prev$this-queue[$i];}$this-queue[];}// 随机访问第 $i 个点O(BLOCK) 解码publicfunctionget(int$i):int{if($i$this-total)thrownew\OutOfRangeException($i);$flushed$this-nblock*self::BLOCK;if($i$flushed)return$this-queue[$i-$flushed];// 还在 queue 里$pos$this-idx[intdiv($i,self::BLOCK)];[$v,$pos]self::vd($this-buf,$pos);$vself::unzz($v);for($j0,$off$i%self::BLOCK;$j$off;$j){[$d,$pos]self::vd($this-buf,$pos);$vself::unzz($d);}return$v;}publicfunctioncompressedBytes():int{returnstrlen($this-buf);}publicfunctioncount():int{return$this-total;}// Zigzag 编码把有符号整数折叠成小的无符号整数// 原理(-11)^(-163) -2 ^ -1 1(11)^(163) 2^0 2privatestaticfunctionzz(int$n):int{return($n1)^($n63);}privatestaticfunctionunzz(int$n):int{return($n1)^-($n1);}// VarInt 编码每次取 7 位最高位1 表示后面还有字节privatestaticfunctionvi(int$n):string{$s;while($n0x7F){$s.chr(($n0x7F)|0x80);$n7;}return$s.chr($n);}privatestaticfunctionvd(string$b,int$p):array{[$v,$s][0,0];do{$cord($b[$p]);$v|($c0x7F)$s;$s7;}while($c0x80);return[$v,$p];}}// ── 演示 ──────────────────────────────────────────────$N100_000;$tsnewTsDelta($N);$raw[];$v50;for($i0;$i$N;$i){$vmax(0,min(100,$vrandom_int(-3,3)));// 模拟 CPU 使用率$raw[]$v;$ts-push($v);}$ts-seal();// 把尾部不满一块的数据也压进去$rawBytes$N*8;// PHP int 在数组里约 8 字节$cmpBytes$ts-compressedBytes();printf(原始: %6d B\n,$rawBytes);printf(压缩后: %6d B\n,$cmpBytes);printf(压缩比: %.2fx (节省 %.1f%%)\n,$rawBytes/$cmpBytes,100*(1-$cmpBytes/$rawBytes));// 验证随机访问foreach(array_rand($raw,5)as$idx){$got$ts-get($idx);assert($got$raw[$idx],idx$idxexpected{$raw[$idx]}got$got);echoget($idx) $got✓\n;}---预期输出 原始:800000B压缩后:~85000B压缩比:~9.4x(节省89.4%)get(47382)63✓...---各部分为什么这么设计 原始数据:[50,52,51,54,53]Delta:[50,2,-1,3,-1]← 数字变小 Zigzag:[100,4,1,6,1]← 全变正数消灭负数 VarInt:每个值1字节(128)← 每个差值只占1字节 ┌───────────────┬────────────┬──────────┐ │ 方案 │ 每点字节数 │ 随机访问 │ ├───────────────┼────────────┼──────────┤ │PHP原生数组 │~70B│O(1)│ ├───────────────┼────────────┼──────────┤ │ SplFixedArray │8B│O(1)│ ├───────────────┼────────────┼──────────┤ │ 本方案 │~0.8B│O(128)│ ├───────────────┼────────────┼──────────┤ │ 真 Gorilla │~0.5B│ 需块索引 │ └───────────────┴────────────┴──────────┘BLOCK大小调节BLOCK128是平衡点。改小如32随机访问更快但索引占更多内存改大如512压缩率微升但每次随机访问要解码更多点。
php方案 流数据的内存压缩存储（Stream Compression in Memory）
大白话先说清楚 Delta 编码不存原值存相邻两个值的差。CPU使用率[50,52,51,53]变成[50,2,-1,2]数字变小了。 Zigzag 编码差值有正有负VarInt 压不好负数-1是全1的64位大数。Zigzag 把符号折叠进去0→0,-1→1,1→2,-2→3,2→4全变小正数VarInt 就能用1字节存了。 VarInt每7位一组打包最高位标记后面还有。差值通常 ±10Zigzag 后最大20一个字节搞定。 随机访问不能逐字节跳但可以分块——每128个点为一块记录每块在压缩流中的起始位置访问第N个就找到所在块从块头解码到第N个位置。 和 Gorilla 差异Gorilla 用XOR位级打包bit packing我们用 DeltaZigzagVarInt 字节流实现简单10倍压缩比85%接近。---代码?php// 依赖PHP 7.4 内置 SplFixedArray无需额外扩展// 如有 ext-ds可把 SplFixedArray 换成 Ds\Vector 性能更好classTsDelta{constBLOCK128;// 随机访问粒度越小随机访问越快索引越大privateSplFixedArray$idx;// 每块在 buf 中的字节偏移privatestring$buf;privatearray$queue[];// 未满一块的缓冲privateint$total0;privateint$nblock0;publicfunction__construct(int$cap){$this-idxnewSplFixedArray((int)ceil($cap/self::BLOCK));}publicfunctionpush(int$v):void{$this-queue[]$v;$this-total;if(count($this-queue)self::BLOCK)$this-seal();}// 把当前 queue 压缩成一个块写入 bufpublicfunctionseal():void{if(!$this-queue)return;$this-idx[$this-nblock]strlen($this-buf);$prev$this-queue[0];$this-buf.self::vi(self::zz($prev));// 块首存绝对值for($i1,$ncount($this-queue);$i$n;$i){$this-buf.self::vi(self::zz($this-queue[$i]-$prev));// 存 delta$prev$this-queue[$i];}$this-queue[];}// 随机访问第 $i 个点O(BLOCK) 解码publicfunctionget(int$i):int{if($i$this-total)thrownew\OutOfRangeException($i);$flushed$this-nblock*self::BLOCK;if($i$flushed)return$this-queue[$i-$flushed];// 还在 queue 里$pos$this-idx[intdiv($i,self::BLOCK)];[$v,$pos]self::vd($this-buf,$pos);$vself::unzz($v);for($j0,$off$i%self::BLOCK;$j$off;$j){[$d,$pos]self::vd($this-buf,$pos);$vself::unzz($d);}return$v;}publicfunctioncompressedBytes():int{returnstrlen($this-buf);}publicfunctioncount():int{return$this-total;}// Zigzag 编码把有符号整数折叠成小的无符号整数// 原理(-11)^(-163) -2 ^ -1 1(11)^(163) 2^0 2privatestaticfunctionzz(int$n):int{return($n1)^($n63);}privatestaticfunctionunzz(int$n):int{return($n1)^-($n1);}// VarInt 编码每次取 7 位最高位1 表示后面还有字节privatestaticfunctionvi(int$n):string{$s;while($n0x7F){$s.chr(($n0x7F)|0x80);$n7;}return$s.chr($n);}privatestaticfunctionvd(string$b,int$p):array{[$v,$s][0,0];do{$cord($b[$p]);$v|($c0x7F)$s;$s7;}while($c0x80);return[$v,$p];}}// ── 演示 ──────────────────────────────────────────────$N100_000;$tsnewTsDelta($N);$raw[];$v50;for($i0;$i$N;$i){$vmax(0,min(100,$vrandom_int(-3,3)));// 模拟 CPU 使用率$raw[]$v;$ts-push($v);}$ts-seal();// 把尾部不满一块的数据也压进去$rawBytes$N*8;// PHP int 在数组里约 8 字节$cmpBytes$ts-compressedBytes();printf(原始: %6d B\n,$rawBytes);printf(压缩后: %6d B\n,$cmpBytes);printf(压缩比: %.2fx (节省 %.1f%%)\n,$rawBytes/$cmpBytes,100*(1-$cmpBytes/$rawBytes));// 验证随机访问foreach(array_rand($raw,5)as$idx){$got$ts-get($idx);assert($got$raw[$idx],idx$idxexpected{$raw[$idx]}got$got);echoget($idx) $got✓\n;}---预期输出 原始:800000B压缩后:~85000B压缩比:~9.4x(节省89.4%)get(47382)63✓...---各部分为什么这么设计 原始数据:[50,52,51,54,53]Delta:[50,2,-1,3,-1]← 数字变小 Zigzag:[100,4,1,6,1]← 全变正数消灭负数 VarInt:每个值1字节(128)← 每个差值只占1字节 ┌───────────────┬────────────┬──────────┐ │ 方案 │ 每点字节数 │ 随机访问 │ ├───────────────┼────────────┼──────────┤ │PHP原生数组 │~70B│O(1)│ ├───────────────┼────────────┼──────────┤ │ SplFixedArray │8B│O(1)│ ├───────────────┼────────────┼──────────┤ │ 本方案 │~0.8B│O(128)│ ├───────────────┼────────────┼──────────┤ │ 真 Gorilla │~0.5B│ 需块索引 │ └───────────────┴────────────┴──────────┘BLOCK大小调节BLOCK128是平衡点。改小如32随机访问更快但索引占更多内存改大如512压缩率微升但每次随机访问要解码更多点。
