Redis 之父关于 CRC64 的神秘往事！

大家好，我是 yes。



昨天表弟说有个学妹问他 Redis 为什么要用 CRC16(key) mod 16384 来计算 key 所处槽的位置，我想这 CRC 一般都是用来校验的，通过多项式转换成二进制再通过模2除法得到余数，这里用来做个 Hash 函数好像用的也没啥毛病（对于CRC不太了解的同学可以先去查查）。



于是我就去查，看看 Redis 的作者 antirez 有没有相关的介绍，这一查就查到了一位叫 mattsta 的老哥的 14 年写的文章，这老哥的文章可太有意思了，他认为 Redis 现在实现的 CRC 算法太简陋了，他有能提升 4 倍性能的增强版 CRC 算法 - CRCSpeed，因此他写了这篇文章进行了一波分析。



看完之后我马上去看了我本地 5.0 版本的源码，发现 CRC 算法并没有采纳他的增强版，还是老的实现。我又去看了最新 6.0 的版本，发现 CRC-64 改成了 CRCSpeed 的实现，在2020年4月28号提交的，提交者是 antirez，这就让我越发的好奇了，这2014到2020跨度有点大啊，到底发生了啥？





然后我又去看 mattsta 的 Github ，他还是 Redis 的 Contributor，于是我追踪了整个事情发展的历史脉络，事情越来越有意思了。我已经迫不及待地想和大家一起再来看一遍这哥们的文章，过一遍这件事。



不过我先到感谢一下我的表弟，不然我都没机会看到这篇文章，来表弟给大家打个招呼！



“大家好！我是表弟”。 好了表弟你可以走了。



表弟骂骂咧咧的退出群聊：“工具人就是工具人”。



接下来我就要用我蹩脚的英语来翻译了，如有纰漏敬请指正。



Fancy CRCing You Here



这老哥文章标题就有那味儿！ Fancy CRCing You Here，我还特意去找了我专八同学来翻译一下。





然后这老哥文章的第一句话就很为人着想。





简单的翻译就是 short 的人直接点链接看结果，那我肯定不 short 的啊，紧接着这老哥就抛出了以下的话：





Redis 的 CRC-64 的实现有很多人拷贝到他们的项目中使用，CRC-16 也有少量拷贝。这算法是能用啊，但是可以有更好的实现。



我看了下 Github 上有 2353 个项目用到了 Redis 的 CRC-64 实现，325 个项目用到了 Redis 的 CRC-16 实现。





这位老哥为他们感到惋惜，唉他们值得更好的CRC算法呀。紧接着老哥开启了第一波输出。





简单翻一下就是：



• Redis 决定忽略吞吐量和延迟方面的提高，因为他们更喜欢像1999年那样编码。



• 代价就是他们过时的传统设计慢了40倍。大家干得漂亮啊。（不知道这老哥是笔误还是故意把4倍在开头写成40倍的，我就揣测下:），那个超链接跳过去就是标注着 antirez 写的 CRC-64 的实现，粗暴直接，我很喜欢)。



• 哎，如果现在有人写了一个代替 redis 和 memcached 的实现就好了啊。



然后老哥就开始放招。



What’s Wrong



他先说了下 CRC 本质上是无法并行的，因为下一次迭代的值取决于前一次迭代。然后又指出了 Redis 中的哪几个地方使用到 CRC。





CRC-64 用在了三个地方：



• 在跨实例迁移键时添加校验和，（并验证上述校验和）



• 为 RDB 输出添加一个校验和，用于复制和持久化（是可选项，可通过配置禁用，因为性能低）



• 用于内存测试



CRC-16 用在了一个地方：



• 作为集群中分配集群槽的键的散列函数



mattsta 接着放招：





简单翻译下：这 Redis 的实现极其简单（这个 extremely 单词我很是喜欢）。就是一个简单的查表法，然后循环一个字节一个字节比过去，时间复杂度是O(N)。



马上这位老哥就抛出如何做才好。



What’s Better





简单翻译下：我在网上乱翻了一番，想看看其他人是如何实现 CRC-64 的。但是大部分是拷贝 Redis 的（哎，恨其不争）。



然后 mattsta 发现了 stackoverflow 有个叫 Mark 的哥们自己写了个高速版 CRC-64 实现，他将 Mark 的实现和 Redis 的实现进行了对比，发现 Mark 的版本比 Redis 版本快了400% ，分别是1.6 GB/s 和400 MB/s。





但是！ Mark 和 Redis 实现的 CRC-64 属于不同的版本，没错 CRC-64 算法有很多变体，于是 mattsta 把枪口暂时对准了 CRC。





原谅我的孤陋寡闻，我一直以为 pretty 和 girl 比较配，原来还能用来和 awful搭，我学到了，嗯。pretty f...。



然后 mattsta 说我们不能直接用 Mark 的实现，但是我们可以看看是Mark 的实现。



What’s Improved



mattsta 先展示了下 Redis 的实现，就是每个字节循环操作，然后查表。





然后他又贴出了快版本的实现。





可以看到也是查表法，不过一次不是处理 1 个字节而是 8 个字节。





mattsta 用了一个我觉得很搞笑的形容 tiger prepping to devour your entrails 。这新版本的代码看起来像一只老虎准备吃掉你的内脏！再坚持一会儿！这还是个超链接，我点过去真的是一只老虎图！





哈哈哈，容我先笑一会儿。这老哥很有意思！



然后他说强调了下算法的快的原因，就是利用多维数组查表，每次循环可以处理8个字节。





因此对于 500 MB 的输入来说 Redis 的版本需要 5 亿次循环，而新版本只要 6250 万次。





这个slicing-by-8是英特尔公司的研究人员于 2006 年发布，也就是说利用 8 个查找表，每个查找表包含另一个 256 字节的查找表来实现一次能处理 8 个字节的 CRC-64 算法。简单的说还是空间换时间的操作。





于是这位老哥找到了灵感，他要自己实现一个和 Redis 匹配的 CRC 算法。



Result





简单翻译下：就是经过一年的努力，mattsta 终于做出符合 Redis 匹配的 CRC-64 算法快速版本，而且作为额外奖励，也能用在CRC-16上噢，并且可以摒弃老版本源代码中一堆静态查找表。可以在需要的时候再动态生成，而不是总是拖着它们使代码膨胀。



我们来看看老版本的代码确实有一堆，我截了一小段。





也就是 mattsta 写的快速 CRC 实现版本-crcspeed，不仅速度更快，而且清减了代码。



然后 mattsta 来了一波不要相信我说的话，咱们来让数据说话（傲娇.jpg）。







通过 mattsta 自己的笔记本测出的 crcspeed 从耗时、吞吐量和每字节所需CPU周期三方面来看都优于 Redis 的实现。



Real-World Impact



mattsta 又指出 crcspeed 能给Redis 带来啥呢？





简单的翻译下就是：Redis 在生成 RDB 的时候会 fork 出子进程，因此采用的是写时复制，所以内存的增长取决于写入的负载，那么快速的结束 RDB 退出 fork 的子进程，用在 COW 的内存就会更少，而生成 RDB 的时候又用到了CRC-64 作为校验，那么 CRC-64 校验越快，RDB 生成的就越快，用于 COW 复制而使用的内存就越少。



并且





CRC-16来映射槽的时候，如果用户正在做一些古怪的事情，比如使用300 MB 的按键，那么快速的 CRC-16可以减少400% 的集群槽分配开销！



这个 If users are doing wacky things，我很是赞同，不管公司内部还是公司外部，你所实现的接口都要怀揣着使用者会以最大的恶意来调用去看待。





mattsta 说这是一个有效和高效的多方面的双赢！



我本以为文章都这里就差不多了，然而并没有。



Minor Notes





可以看出 mattsta 是不想造轮子的，但是实在是没有轮子啊！于是他只能自己实现一个，这是个新轮子！



Resources Consulted



然后他列出了他所参考的一些资源，他首先感谢了「A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS」这篇文章。



让我们学一下感谢参考资料的正确姿势。





看到没，这才是感谢的正确姿势！我们来看下它所感谢的文章的样子。





有一说一，确实，纯路人。身为一个txt，编写良好、格式良好，有趣。在风格、布局和语气的所有方面都经过了专家的深思熟虑。



夸一番 mattsta 觉得还不够，还得加一点自己的想法。





简单的翻一下：在某种程度上，互联网已经失去了保存写的好的、格式良好的、信息丰富的指南以及常见问题的解答和平易近人的研究论文的能力。我们应该努力把那部分世界夺回来。这种损失该归咎于什么呢？对风格的过分依赖？CSS？还是 JavaScript？PHP？。



世界上最好的语言警告！





看到没，这才叫感谢。mattsta 追求纯干货，别给我整一些花里胡哨的！



而且这篇文章还让 mattsta 确信他没有能力实现一个 CRC-64 算法，因此实际上他是依靠 pycrc 来实现的。



然后这位老哥又说 yahyahyah，linux kernel 也是这样用的。





老哥还找到一篇介绍 slicing by 8 的放在英特尔网上的论文，不过现在已经没了。所以先嘲讽了一波英特尔，还顺带还吐槽了傻*谷歌代码，每次打开这个 pdf 都自动下载，而不是在线浏览。





这老哥真的对我胃口哈哈哈。mattsta 的文章还没结束，下面写的是一些关于实现的细节。有兴趣的朋友到时候可以看看，文末会放链接。我就不再跟下去了。



我们再来看身为 Redis Contributor 为何 mattsta 会写这一篇文章？不应该提 pr 直接解决吗？难道这算法有什么致命之处使得 Antirez 不接受？我们来追踪一下！



追踪事情的来龙去脉



首先这篇文章写于2014-12-22





mattsta 在 2013-12 开始了对 redis.io 的第一次提交。





随后 mattsta 就开始了对 Redis 的输出，在2014-04-01，提出了相关的 issue，并且附上了自己的对比。





提出的 issue 没有受到团队成员的响应，寂寞如雪，只有一位金毛小哥，为其打 call。这个issue 此时还是 open 的。



然后在当年，2014-11-23，mattsta创建了 crcspeed 库，并且提交了实现。





并在2014-12-22提交了pr，竟然和写文章是同一天！而且是先写了文章再提的 pr。一开始我以为是提了pr迟迟得不到采纳，然后才一怒之下写的文章。





可以看到隔了一天有团队人员回应了，他说我不知道这是否会被合并(我认为它应该) ，但是，该死的！这是一个伟大的提升！牛皮克拉斯！



2014-12-23，mattsta 又对 pr 做了一些补充说明。然而没有回应。



直到2015-01-10，mattsta 对 pr 又做了一波更新。





终于在2015-02-25号，等到了 antirez 的回复。





antirez 说，很有意思但是我想看到固定的大于 5% 收益的可重现的测试用例，即使是综合性的测试也没事，只要明显的能在 Redis 中反映出来即可，我相信从集群的 crc16 入手测试能很简单的证明效果，现在对于合并更快的实现不是很急，不过如果有一天你完成了这样的测试，我将会很感激。



然后给这个pr加了个标 review - and - merge。



还加了个ps: 通常来说证明一个东西的性能提升是很重要啊，我在这里做了个例外，因为我看它单独的测试确实快了很多，我相信即使 Redis 没有使用上这个经验，但是迟早我们也会受益于它



简单的说就是 mattsta 你得搞个 Redis 相关的测试来证明它真的使得 Redis 性能提升了啊，这样我才能合并啊，不过我做个例外，是认可你这个的，给你打个标！(但是没有真正的合并)。



也就是说 antirez 其实是认可 mattsta 的实现的，但是 mattsta 没有给出和 Redis 相关的测试，所以还不能合并这个 pr。



这个 pr 就到这里过了，再也没有更新，也还是 Open 的。



mattsta 也没有继续说啥，对 Redis 输出到2015年初之后就不再输出了。而 CRC-16 到现在还使用的是老版本，CRC-64 是 antirez 在时隔六年的2020-04-28做的修改，使用的就是 mattsta 的crcspeed。

再回头看



可以到 mattsta 在 2014-04-01就提了 issue，然后没有任何回应的情况下自己研究，找了许多资料，最后实现了 crcspeed，也肝出了一篇文章，之后在同一天提了PR，然后过了近两个月的时间得到 antirez 的回复，由其没有关于 Redis 的实质上的测试，因此不给合并，但被给予肯定。



但我个人猜测 mattsta 可能还是有点生气的，这么一个通用的东西，我都给了横向对比测试了！这原理我也分析的这么清楚了！这明摆着肯定是 ok 的，你还要我测试啥！不合并拉倒！(再次傲娇.jpg)。



而 antirez 所在的角度不一样，他是 Redis 的亲爸爸。你说的没错，我认可你，但是你得拿出实质性的证明给我看看你帮我的 Redis 提升了多少。



其实双方我都能理解，所处角色不同。最终我们终于得知整个事情的来龙去脉，再附上一直 mattsta 的靓照，看来发量不错。





这篇文章讲述的就是这么个事儿。其实我就是带着八卦之心来看为何身为 Contributor 的 mattsta 提的明显正确的 pr 没有被 merge，至于什么 CRC 的我不关心哈哈哈哈。



当然 mattsta 的钻研之心值得我们学习，当然还有他那搞笑的形容和五彩斑斓的感谢。而 antirez 对 pr 的严谨也值得我们效仿。



链接



https://matt.sh/redis-crcspeed



https://github.com/mattsta?tab=repositories



我是 yes，从一点点到亿点点，我们下篇见。