数据编码与压缩

30次阅读

共计 1240 个字符,预计需要花费 4 分钟才能阅读完成。

内存数据结构

这个就太多了。。略

IO:json/xml(无类型,unicode 支持不好等), 二进制编码

  • JSON 演化 mmessagePack
    不流行,因为需要在编码数据中包含对象名称. 只是删除空白和标点的感觉
  • thrift BinaryProtocal 字段名替换为序号

    {
        "userName": "Martin",
        "favoriteNumber": 1337,
        "interests": ["daydreaming", "hacking"]
    }

  • pb(thrift 的 compactProtocal 和这个一样)

    field 和 type 在单个字节。数据的优化数据最高位标识是否还有后续,这个 1337 有错误,是下面的

  • Avro
    数据变更兼容:
    thrift 和 protocal 可以换换名字。但是不能换编号,可以增加编号,旧的编号删了也不能再用,后加的向前兼容不能设为必选。
    模式和数据编码分别传送,一个传一个模式,大批数据,无编号,读者模式与作者模式匹配,读者解析作者模式

    只能添加或删除有默认值的字段
    以上数字的转变全是基于 VLQ 可变长二进制数字编码 的变体。最低位加 0 表示整数,1 表示负数,然后 7 位一个分割。从最后开始,每个后面有第一位是 1,否则是 0.

压缩

  • 压缩算法对比

![clipboard.png](/img/bVbr5Th)

![clipboard.png](/img/bVbr5TX)

https://catchchallenger.first-world.info/wiki/Quick_Benchmark:_Gzip_vs_Bzip2_vs_LZMA_vs_XZ_vs_LZ4_vs_LZO
https://www.percona.com/blog/2016/04/13/evaluating-database-compression-methods-update/
  • snappy/LZ77/LZSS
    DC 动态词典编码:用它在词典中的位置号码代替。静态需要实现知道词典,讲下动态的
    前向缓冲区(数据流将要处理的所有字符)的开始字符串与滑动窗口中的字符串进行最长匹配,无移动窗口,若找到 < 匹配字符串在滑动窗口的位置,长度,移除前置缓冲区中匹配部分移除后续第一个字符 >,LZSS 增加匹配长读限制


    如何快速最长匹配字符串:简单的将窗口中所有字符顺序组合存入 hash,也可以存固定长度,比如 2,匹配多个后再继续向后比较这多个。
    snappy 将整个数据切割为 32k 一个大小的块,块只见那无关联,2 个字节就可表示匹配字符串的相对位置,匹配长度至少为 4,hash 字符串长度也固定为 4. 输出字符串的压缩形式为 编码方案,匹配字符串起始位置差值,匹配字符串长度

  • EC 编码:N 个数据块和校验,可以任意丢 k 个相互恢复
    因为我们都是多副本,
    N 个 Data 块,生成 K 个 Parity 块,N+ K 中可任意丢 K 个
    可靠性相同时比多副本冗余度低
    只有一份数据可读,修复较复杂
    提高可靠性:增加 K,增加 N 和 K,提高修复速度
    https://blog.csdn.net/shelldo…

正文完
 0