当前位置： 金毛 >> 金毛形态特征 >> Redis作者Antirez与C
大家好，我是yes。
昨天表弟说有个学妹问他Redis为什么要用CRC16(key)mod来计算key所处槽的位置，我想这CRC一般都是用来校验的，通过多项式转换成二进制再通过模2除法得到余数，这里用来做个Hash函数好像用的也没啥毛病（对于CRC不太了解的同学可以先去查查）。
于是我就去查，看看Redis的作者antirez有没有相关的介绍，这一查就查到了一位叫mattsta的老哥的14年写的文章，这老哥的文章可太有意思了，他认为Redis现在实现的CRC算法太简陋了，他有能提升4倍性能的增强版CRC算法-CRCSpeed，因此他写了这篇文章进行了一波分析。
看完之后我马上去看了我本地5.0版本的源码，发现CRC算法并没有采纳他的增强版，还是老的实现。我又去看了最新6.0的版本，发现CRC-64改成了CRCSpeed的实现，在年4月28号提交的，提交者是antirez，这就让我越发的好奇了，这到跨度有点大啊，到底发生了啥？
然后我又去看mattsta的Github，他还是Redis的Contributor，于是我追踪了整个事情发展的历史脉络，事情越来越有意思了。我已经迫不及待地想和大家一起再来看一遍这哥们的文章，过一遍这件事。
不过我先到感谢一下我的表弟，不然我都没机会看到这篇文章，来表弟给大家打个招呼！
“大家好！我是表弟”。好了表弟你可以走了。
表弟骂骂咧咧的退出群聊：“工具人就是工具人”。
接下来我就要用我蹩脚的英语来翻译了，如有纰漏敬请指正。
FancyCRCingYouHere这老哥文章标题就有那味儿！FancyCRCingYouHere，我还特意去找了我专八同学来翻译一下。
然后这老哥文章的第一句话就很为人着想。
简单的翻译就是short的人直接点链接看结果，那我肯定不short的啊，紧接着这老哥就抛出了以下的话：
Redis的CRC-64的实现有很多人拷贝到他们的项目中使用，CRC-16也有少量拷贝。这算法是能用啊，但是可以有更好的实现。
我看了下Github上有个项目用到了Redis的CRC-64实现，个项目用到了Redis的CRC-16实现。
这位老哥为他们感到惋惜，唉他们值得更好的CRC算法呀。紧接着老哥开启了第一波输出。
简单翻一下就是：
Redis决定忽略吞吐量和延迟方面的提高，因为他们更喜欢像年那样编码。
代价就是他们过时的传统设计慢了40倍。大家干得漂亮啊。（不知道这老哥是笔误还是故意把4倍在开头写成40倍的，我就揣测下:），那个超链接跳过去就是标注着antirez写的CRC-64的实现，粗暴直接，我很喜欢)。
哎，如果现在有人写了一个代替redis和memcached的实现就好了啊。
然后老哥就开始放招。
What’sWrong他先说了下CRC本质上是无法并行的，因为下一次迭代的值取决于前一次迭代。然后又指出了Redis中的哪几个地方使用到CRC。
CRC-64用在了三个地方：
在跨实例迁移键时添加校验和，（并验证上述校验和）
为RDB输出添加一个校验和，用于复制和持久化（是可选项，可通过配置禁用，因为性能低）
用于内存测试
CRC-16用在了一个地方：
作为集群中分配集群槽的键的散列函数mattsta接着放招：
简单翻译下：这Redis的实现极其简单（这个extremely单词我很是喜欢）。就是一个简单的查表法，然后循环一个字节一个字节比过去，时间复杂度是O(N)。
马上这位老哥就抛出如何做才好。
What’sBetter简单翻译下：我在网上乱翻了一番，想看看其他人是如何实现CRC-64的。但是大部分是拷贝Redis的（哎，恨其不争）。
然后mattsta发现了stackoverflow有个叫Mark的哥们自己写了个高速版CRC-64实现，他将Mark的实现和Redis的实现进行了对比，发现Mark的版本比Redis版本快了%，分别是1.6GB/s和MB/s。
但是！Mark和Redis实现的CRC-64属于不同的版本，没错CRC-64算法有很多变体，于是mattsta把枪口暂时对准了CRC。
原谅我的孤陋寡闻，我一直以为pretty和girl比较配，原来还能用来和awful搭，我学到了，嗯。prettyf...。
然后mattsta说我们不能直接用Mark的实现，但是我们可以看看是Mark的实现。
What’sImprovedmattsta先展示了下Redis的实现，就是每个字节循环操作，然后查表。
然后他又贴出了快版本的实现。
可以看到也是查表法，不过一次不是处理1个字节而是8个字节。
mattsta用了一个我觉得很搞笑的形容tigerpreppingtodevouryourentrails。这新版本的代码看起来像一只老虎准备吃掉你的内脏！再坚持一会儿！这还是个超链接，我点过去真的是一只老虎图！
哈哈哈，容我先笑一会儿。这老哥很有意思！
然后他说强调了下算法的快的原因，就是利用多维数组查表，每次循环可以处理8个字节。
因此对于MB的输入来说Redis的版本需要5亿次循环，而新版本只要万次。
这个slicing-by-8是英特尔公司的研究人员于年发布，也就是说利用8个查找表，每个查找表包含另一个字节的查找表来实现一次能处理8个字节的CRC-64算法。简单的说还是空间换时间的操作。
于是这位老哥找到了灵感，他要自己实现一个和Redis匹配的CRC算法。
Result简单翻译下：就是经过一年的努力，mattsta终于做出符合Redis匹配的CRC-64算法快速版本，而且作为额外奖励，也能用在CRC-16上噢，并且可以摒弃老版本源代码中一堆静态查找表。可以在需要的时候再动态生成，而不是总是拖着它们使代码膨胀。
我们来看看老版本的代码确实有一堆，我截了一小段。
也就是mattsta写的快速CRC实现版本-crcspeed，不仅速度更快，而且清减了代码。
然后mattsta来了一波不要相信我说的话，咱们来让数据说话（傲娇.jpg）。
通过mattsta自己的笔记本测出的crcspeed从耗时、吞吐量和每字节所需CPU周期三方面来看都优于Redis的实现。
Real-WorldImpactmattsta又指出crcspeed能给Redis带来啥呢？
简单的翻译下就是：Redis在生成RDB的时候会fork出子进程，因此采用的是写时复制，所以内存的增长取决于写入的负载，那么快速的结束RDB退出fork的子进程，用在COW的内存就会更少，而生成RDB的时候又用到了CRC-64作为校验，那么CRC-64校验越快，RDB生成的就越快，用于COW复制而使用的内存就越少。
并且
CRC-16来映射槽的时候，如果用户正在做一些古怪的事情，比如使用MB的按键，那么快速的CRC-16可以减少%的集群槽分配开销！
这个Ifusersaredoingwackythings，我很是赞同，不管公司内部还是公司外部，你所实现的接口都要怀揣着使用者会以最大的恶意来调用去看待。
mattsta说这是一个有效和高效的多方面的双赢！
我本以为文章都这里就差不多了，然而并没有。
MinorNotes可以看出mattsta是不想造轮子的，但是实在是没有轮子啊！于是他只能自己实现一个，这是个新轮子！
ResourcesConsulted然后他列出了他所参考的一些资源，他首先感谢了「APAINLESSGUIDETOCRCERRORDETECTIONALGORITHMS」这篇文章。
让我们学一下感谢参考资料的正确姿势。
看到没，这才是感谢的正确姿势！我们来看下它所感谢的文章的样子。
有一说一，确实，纯路人。身为一个txt，编写良好、格式良好，有趣。在风格、布局和语气的所有方面都经过了专家的深思熟虑。
夸一番mattsta觉得还不够，还得加一点自己的想法。
简单的翻一下：在某种程度上，互联网已经失去了保存写的好的、格式良好的、信息丰富的指南以及常见问题的解答和平易近人的研究论文的能力。我们应该努力把那部分世界夺回来。这种损失该归咎于什么呢？对风格的过分依赖？CSS？还是JavaScript？PHP？。
世界上最好的语言警告！
看到没，这才叫感谢。mattsta追求纯干货，别给我整一些花里胡哨的！
而且这篇文章还让mattsta确信他没有能力实现一个CRC-64算法，因此实际上他是依靠pycrc来实现的。
然后这位老哥又说yahyahyah，linuxkernel也是这样用的。
老哥还找到一篇介绍slicingby8的放在英特尔网上的论文，不过现在已经没了。所以先嘲讽了一波英特尔，还顺带还吐槽了傻*谷歌代码，每次打开这个pdf都自动下载，而不是在线浏览。
这老哥真的对我胃口哈哈哈。mattsta的文章还没结束，下面写的是一些关于实现的细节。有兴趣的朋友到时候可以看看，文末会放链接。我就不再跟下去了。
我们再来看身为RedisContributor为何mattsta会写这一篇文章？不应该提pr直接解决吗？难道这算法有什么致命之处使得Antirez不接受？我们来追踪一下！
追踪事情的来龙去脉首先这篇文章写于-12-22
mattsta在-12开始了对redis.io的第一次提交。
随后mattsta就开始了对Redis的输出，在-04-01，提出了相关的issue，并且附上了自己的对比。
提出的issue没有受到团队成员的响应，寂寞如雪，只有一位金毛小哥，为其打call。这个issue此时还是open的。
然后在当年，-11-23，mattsta创建了crcspeed库，并且提交了实现。
并在-12-22提交了pr，竟然和写文章是同一天！而且是先写了文章再提的pr。一开始我以为是提了pr迟迟得不到采纳，然后才一怒之下写的文章。
可以看到隔了一天有团队人员回应了，他说我不知道这是否会被合并(我认为它应该)，但是，该死的！这是一个伟大的提升！牛皮克拉斯！
-12-23，mattsta又对pr做了一些补充说明。然而没有回应。
直到-01-10，mattsta对pr又做了一波更新。
终于在-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输出到年初之后就不再输出了。而CRC-16到现在还使用的是老版本，CRC-64是antirez在时隔六年的-04-28做的修改，使用的就是mattsta的crcspeed。
再回头看可以到mattsta在-04-01就提了issue，然后没有任何回应的情况下自己研究，找了许多资料，最后实现了crcspeed，也肝出了一篇文章，之后在同一天提了PR，然后过了近两个月的时间得到antirez的回复，由其没有关于Redis的实质上的测试，因此不给合并，但被给予肯定。
但我个人猜测mattsta可能还是有点生气的，这么一个通用的东西，我都给了横向对比测试了！这原理我也分析的这么清楚了！这明摆着肯定是ok的，你还要我测试啥！不合并拉倒！(再次傲娇.jpg)。
而antirez所在的角度不一样，他是Redis的亲爸爸。你说的没错，我认可你，但是你得拿出实质性的证明给我看看你帮我的Redis提升了多少。
其实双方我都能理解，所处角色不同。最终我们终于得知整个事情的来龙去脉，再附上一直mattsta的靓照，看来发量不错。
这篇文章讲述的就是这么个事儿。其实我就是带着八卦之心来看为何身为Contributor的mattsta提的明显正确的pr没有被merge，至于什么CRC的我不关心哈哈哈哈。
当然mattsta的钻研之心值得我们学习，当然还有他那搞笑的形容和五彩斑斓的感谢。而antirez对pr的严谨也值得我们效仿。
链接