文章归档

Smaz的小对象压缩技术

基于小对象的压缩算法。一个叫做 Smaz 的项目,https://github.com/antirez/smaz 目前应用在redis数据库上面。

与传统的压缩算法不同的是,Smaz更适合小对象的压缩,比如几个字节到几十个字节不等。除开字典的硬编码部分,压缩过程和解压过程加起来120行代码,非常的短小精罕,却有不俗的表现。平均测试能够达到40%~50%左右的压缩效果。

当然,代码在某些方面不是完美的,也不健壮,但是很实用。 antirez坚持追求高速度而放弃部分的安全性。一些相关讨论,请看

http://news.ycombinator.com/item?id=540048

 

核心代码

Smaz的核心代码只有两部分:

  1. 字典的设计
  2. Hash函数

字典方面,Smaz 采用了硬编码的方式,antirez应该是对大量的相关语料进行统计,分析,进而得出最常用的字符组合

C++代码
  1. /* Reverse compression codebook, used for decompression */
  2. static char *Smaz_rcb[254] = {
  3. " ", "the", "e", "t", "a", "of", "o", "and", "i", "n", "s", "e ", "r", " th",
  4. " t", "in", "he", "th", "h", "he ", "to", "", "l", "s ", "d", " a", "an",
  5. "er", "c", " o", "d ", "on", " of", "re", "of ", "t ", ", ", "is", "u", "at",
  6. " ", "n ", "or", "which", "f", "m", "as", "it", "that", "n", "was", "en",
  7. " ", " w", "es", " an", " i", "r", "f ", "g", "p", "nd", " s", "nd ", "ed ",
  8. "w", "ed", "http://", "for", "te", "ing", "y ", "The", " c", "ti", "r ", "his",
  9. "st", " in", "ar", "nt", ",", " to", "y", "ng", " h", "with", "le", "al", "to ",
  10. "b", "ou", "be", "were", " b", "se", "o ", "ent", "ha", "ng ", "their", """,
  11. "hi", "from", " f", "in ", "de", "ion", "me", "v", ".", "ve", "all", "re ",
  12. "ri", "ro", "is ", "co", "f t", "are", "ea", ". ", "her", " m", "er ", " p",
  13. "es ", "by", "they", "di", "ra", "ic", "not", "s, ", "d t", "at ", "ce", "la",
  14. "h ", "ne", "as ", "tio", "on ", "n t", "io", "we", " a ", "om", ", a", "s o",
  15. "ur", "li", "ll", "ch", "had", "this", "e t", "g ", "e", " wh", "ere",
  16. " co", "e o", "a ", "us", " d", "ss", "n", "r", "="", " be", " e",
  17. "s a", "ma", "one", "t t", "or ", "but", "el", "so", "l ", "e s", "s,", "no",
  18. "ter", " wa", "iv", "ho", "e a", " r", "hat", "s t", "ns", "ch ", "wh", "tr",
  19. "ut", "/", "have", "ly ", "ta", " ha", " on", "tha", "-", " l", "ati", "en ",
  20. "pe", " re", "there", "ass", "si", " fo", "wa", "ec", "our", "who", "its", "z",
  21. "fo", "rs", ">", "ot", "un", "<", "im", "th ", "nc", "ate", "><", "ver", "ad",
  22. " we", "ly", "ee", " n", "id", " cl", "ac", "il", "</", "rt", " wi", "div",
  23. "e, ", " it", "whi", " ma", "ge", "x", "e c", "men", ".com"
  24. };

然后将这些字符串尽可能的均匀分散到每一个slot中,提高查询的速度,Hash的设计看起来很简单

C++代码
  1. h1 = h2 = in[0]<<3;
  2. if (inlen > 1) h2 += in[1];
  3. if (inlen > 2) h3 = h2^in[2];

不过要弄清楚里面的原理可不容易,你可以看一下解码用的字典,每一个组合的分布是非常的均匀的,说明 Hash的效果理想

C++代码
  1. static char *Smaz_cb[241] = {
  2. "�02s,266",
  3. "�03had232�02leW",
  4. "�03on 216",
  5. "",
  6. "�01yS",
  7. "�02ma255�02li227",
  8. "�03or 260",
  9. "",
  10. "�02ll230�03s t277",
  11. "�04fromg�02mel",
  12. "",
  13. "�03its332",
  14. "�01z333",
  15. "�03ingF",
  16. "�01>336",
  17. "�01 �00�03   (�02nc344",
  18. "�02nd=�03 on312",
  19. "�02ne213�03hat276�03re q",
  20. "",
  21. /* ...... */
  22. "�03, a224"
  23. };

引用 Marc Lehmann 的一句话:"... the hashing function might seem strange, just believe me, it works ! "

Hash的设计应该是与统计分析的结果相关的,而且h1与h2等存在一定的独立性。举个假设,先处理h1,看字典的分布状态,再接着处理h2,让字 典的分布更趋于均匀,h3类推等等。这样就可以得到很好的效果。当然,很多细微的技术不是一下子就能领悟出来的,设计的精妙在于过程,而不是成果

 

应用场景

小对象的压缩有什么好处?

好处是明显的,应用场合也有很多,传统的数据压缩算法解决不了所有问题,例如集群环境下的socket通信以及千万级别的持久服务,并发处理数十万的客户链接,如果每次通信携带的数据长度是是50bytes左右。

(10*100000*50/1024/1024)*50% M/s = 20M/s

这个数据对于提升机房紧张的带宽资源是相当可观的。

 

这个还好,redis改进后的lzf算法更诡异

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>