大家好，我是 yes。

昨天表弟說(shuō)有個(gè)學(xué)妹問(wèn)他 Redis 為什么要用 CRC16(key) mod 16384 來(lái)計(jì)算 key 所處槽的位置，我想這 CRC 一般都是用來(lái)校驗(yàn)的，通過(guò)多項(xiàng)式轉(zhuǎn)換成二進(jìn)制再通過(guò)模2除法得到余數(shù)，這里用來(lái)做個(gè) Hash 函數(shù)好像用的也沒(méi)啥毛?。▽?duì)于CRC不太了解的同學(xué)可以先去查查）。

于是我就去查，看看 Redis 的作者 antirez 有沒(méi)有相關(guān)的介紹，這一查就查到了一位叫 mattsta 的老哥的 14 年寫(xiě)的文章，這老哥的文章可太有意思了，他認(rèn)為 Redis 現(xiàn)在實(shí)現(xiàn)的 CRC 算法太簡(jiǎn)陋了，他有能提升 4 倍性能的增強(qiáng)版 CRC 算法 - CRCSpeed，因此他寫(xiě)了這篇文章進(jìn)行了一波分析。

看完之后我馬上去看了我本地 5.0 版本的源碼，發(fā)現(xiàn) CRC 算法并沒(méi)有采納他的增強(qiáng)版，還是老的實(shí)現(xiàn)。我又去看了最新 6.0 的版本，發(fā)現(xiàn) CRC-64 改成了 CRCSpeed 的實(shí)現(xiàn)，在2020年4月28號(hào)提交的，提交者是 antirez，這就讓我越發(fā)的好奇了，這2014到2020跨度有點(diǎn)大啊，到底發(fā)生了啥？

然后我又去看 mattsta 的 Github ，他還是 Redis 的 Contributor，于是我追蹤了整個(gè)事情發(fā)展的歷史脈絡(luò)，事情越來(lái)越有意思了。我已經(jīng)迫不及待地想和大家一起再來(lái)看一遍這哥們的文章，過(guò)一遍這件事。

Fancy CRCing You Here

這老哥文章標(biāo)題就有那味兒！Fancy CRCing You Here，我還特意去找了我專(zhuān)八同學(xué)來(lái)翻譯一下。

然后這老哥文章的第一句話(huà)就很為人著想。

簡(jiǎn)單的翻譯就是 short 的人直接點(diǎn)鏈接看結(jié)果，那我肯定不 short 的啊，緊接著這老哥就拋出了以下的話(huà)：

Redis 的 CRC-64 的實(shí)現(xiàn)有很多人拷貝到他們的項(xiàng)目中使用，CRC-16 也有少量拷貝。這算法是能用啊，但是可以有更好的實(shí)現(xiàn)。

我看了下 Github 上有 2353 個(gè)項(xiàng)目用到了 Redis 的 CRC-64 實(shí)現(xiàn)，325 個(gè)項(xiàng)目用到了 Redis 的 CRC-16 實(shí)現(xiàn)。

這位老哥為他們感到惋惜，唉他們值得更好的CRC算法呀。緊接著老哥開(kāi)啟了第一波輸出。

簡(jiǎn)單翻一下就是：

• Redis 決定忽略吞吐量和延遲方面的提高，因?yàn)樗麄?strong style="line-height: 1.75em;color: rgb(74, 74, 74);">更喜歡像1999年那樣編碼。

• 代價(jià)就是他們過(guò)時(shí)的傳統(tǒng)設(shè)計(jì)慢了40倍。大家干得漂亮啊。（不知道這老哥是筆誤還是故意把4倍在開(kāi)頭寫(xiě)成40倍的，我就揣測(cè)下:），那個(gè)超鏈接跳過(guò)去就是標(biāo)注著 antirez 寫(xiě)的 CRC-64 的實(shí)現(xiàn)，粗暴直接，我很喜歡)。

• 哎，如果現(xiàn)在有人寫(xiě)了一個(gè)代替 redis 和 memcached 的實(shí)現(xiàn)就好了啊。

然后老哥就開(kāi)始放招。

What’s Wrong

他先說(shuō)了下 CRC 本質(zhì)上是無(wú)法并行的，因?yàn)橄乱淮蔚闹等Q于前一次迭代。然后又指出了 Redis 中的哪幾個(gè)地方使用到 CRC。

CRC-64 用在了三個(gè)地方：

• 在跨實(shí)例遷移鍵時(shí)添加校驗(yàn)和，（并驗(yàn)證上述校驗(yàn)和）

• 為 RDB 輸出添加一個(gè)校驗(yàn)和，用于復(fù)制和持久化（是可選項(xiàng)，可通過(guò)配置禁用，因?yàn)樾阅艿停?/p>

• 用于內(nèi)存測(cè)試

CRC-16 用在了一個(gè)地方：

• 作為集群中分配集群槽的鍵的散列函數(shù)

mattsta 接著放招：

簡(jiǎn)單翻譯下：這 Redis 的實(shí)現(xiàn)極其簡(jiǎn)單（這個(gè) extremely 單詞我很是喜歡）。就是一個(gè)簡(jiǎn)單的查表法，然后循環(huán)一個(gè)字節(jié)一個(gè)字節(jié)比過(guò)去，時(shí)間復(fù)雜度是O(N)。

馬上這位老哥就拋出如何做才好。

What’s Better

簡(jiǎn)單翻譯下：我在網(wǎng)上亂翻了一番，想看看其他人是如何實(shí)現(xiàn) CRC-64 的。但是大部分是拷貝 Redis 的（哎，恨其不爭(zhēng)）。

然后 mattsta 發(fā)現(xiàn)了 stackoverflow 有個(gè)叫 Mark 的哥們自己寫(xiě)了個(gè)高速版 CRC-64 實(shí)現(xiàn)，他將 Mark 的實(shí)現(xiàn)和 Redis 的實(shí)現(xiàn)進(jìn)行了對(duì)比，發(fā)現(xiàn) Mark 的版本比 Redis 版本快了400% ，分別是1.6 GB/s 和400 MB/s。

但是！Mark 和 Redis 實(shí)現(xiàn)的 CRC-64 屬于不同的版本，沒(méi)錯(cuò) CRC-64 算法有很多變體，于是 mattsta 把槍口暫時(shí)對(duì)準(zhǔn)了 CRC。

原諒我的孤陋寡聞，我一直以為 pretty 和 girl 比較配，原來(lái)還能用來(lái)和 awful搭，我學(xué)到了，嗯。pretty f...。

然后 mattsta 說(shuō)我們不能直接用 Mark 的實(shí)現(xiàn)，但是我們可以看看是Mark 的實(shí)現(xiàn)。

What’s Improved

mattsta 先展示了下 Redis 的實(shí)現(xiàn)，就是每個(gè)字節(jié)循環(huán)操作，然后查表。

然后他又貼出了快版本的實(shí)現(xiàn)。

可以看到也是查表法，不過(guò)一次不是處理 1 個(gè)字節(jié)而是 8 個(gè)字節(jié)。

mattsta 用了一個(gè)我覺(jué)得很搞笑的形容 tiger prepping to devour your entrails 。這新版本的代碼看起來(lái)像一只老虎準(zhǔn)備吃掉你的內(nèi)臟！再堅(jiān)持一會(huì)兒！這還是個(gè)超鏈接，我點(diǎn)過(guò)去真的是一只老虎圖！

哈哈哈，容我先笑一會(huì)兒。這老哥很有意思！

然后他說(shuō)強(qiáng)調(diào)了下算法的快的原因，就是利用多維數(shù)組查表，每次循環(huán)可以處理8個(gè)字節(jié)。

因此對(duì)于 500 MB 的輸入來(lái)說(shuō) Redis 的版本需要 5 億次循環(huán)，而新版本只要 6250 萬(wàn)次。

這個(gè)slicing-by-8是英特爾公司的研究人員于 2006 年發(fā)布，也就是說(shuō)利用 8 個(gè)查找表，每個(gè)查找表包含另一個(gè) 256 字節(jié)的查找表來(lái)實(shí)現(xiàn)一次能處理 8 個(gè)字節(jié)的 CRC-64 算法。簡(jiǎn)單的說(shuō)還是空間換時(shí)間的操作。

于是這位老哥找到了靈感，他要自己實(shí)現(xiàn)一個(gè)和 Redis 匹配的 CRC 算法。

Result

簡(jiǎn)單翻譯下：就是經(jīng)過(guò)一年的努力，mattsta 終于做出符合 Redis 匹配的 CRC-64 算法快速版本，而且作為額外獎(jiǎng)勵(lì)，也能用在CRC-16上噢，并且可以摒棄老版本源代碼中一堆靜態(tài)查找表?？梢栽谛枰臅r(shí)候再動(dòng)態(tài)生成，而不是總是拖著它們使代碼膨脹。

我們來(lái)看看老版本的代碼確實(shí)有一堆，我截了一小段。

也就是 mattsta 寫(xiě)的快速 CRC 實(shí)現(xiàn)版本-crcspeed，不僅速度更快，而且清減了代碼。

然后  mattsta 來(lái)了一波不要相信我說(shuō)的話(huà)，咱們來(lái)讓數(shù)據(jù)說(shuō)話(huà)（傲嬌.jpg）。

通過(guò) mattsta 自己的筆記本測(cè)出的 crcspeed 從耗時(shí)、吞吐量和每字節(jié)所需CPU周期三方面來(lái)看都優(yōu)于 Redis 的實(shí)現(xiàn)。

Real-World Impact

mattsta 又指出 crcspeed 能給Redis 帶來(lái)啥呢？

簡(jiǎn)單的翻譯下就是：Redis 在生成 RDB 的時(shí)候會(huì) fork 出子進(jìn)程，因此采用的是寫(xiě)時(shí)復(fù)制，所以?xún)?nèi)存的增長(zhǎng)取決于寫(xiě)入的負(fù)載，那么快速的結(jié)束 RDB 退出 fork 的子進(jìn)程，用在 COW 的內(nèi)存就會(huì)更少，而生成 RDB 的時(shí)候又用到了CRC-64 作為校驗(yàn)，那么 CRC-64 校驗(yàn)越快，RDB 生成的就越快，用于 COW 復(fù)制而使用的內(nèi)存就越少。

并且

CRC-16來(lái)映射槽的時(shí)候，如果用戶(hù)正在做一些古怪的事情，比如使用300 MB 的按鍵，那么快速的 CRC-16可以減少400% 的集群槽分配開(kāi)銷(xiāo)！

這個(gè)If users are doing wacky things，我很是贊同，不管公司內(nèi)部還是公司外部，你所實(shí)現(xiàn)的接口都要懷揣著使用者會(huì)以最大的惡意來(lái)調(diào)用去看待。

mattsta 說(shuō)這是一個(gè)有效和高效的多方面的雙贏！

我本以為文章都這里就差不多了，然而并沒(méi)有。

Minor Notes

可以看出 mattsta 是不想造輪子的，但是實(shí)在是沒(méi)有輪子啊！于是他只能自己實(shí)現(xiàn)一個(gè)，這是個(gè)新輪子！

Resources Consulted

然后他列出了他所參考的一些資源，他首先感謝了「A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS」這篇文章。

讓我們學(xué)一下感謝參考資料的正確姿勢(shì)。

看到?jīng)]，這才是感謝的正確姿勢(shì)！我們來(lái)看下它所感謝的文章的樣子。

有一說(shuō)一，確實(shí)，純路人。身為一個(gè)txt，編寫(xiě)良好、格式良好，有趣。在風(fēng)格、布局和語(yǔ)氣的所有方面都經(jīng)過(guò)了專(zhuān)家的深思熟慮。

夸一番 mattsta 覺(jué)得還不夠，還得加一點(diǎn)自己的想法。

簡(jiǎn)單的翻一下：在某種程度上，互聯(lián)網(wǎng)已經(jīng)失去了保存寫(xiě)的好的、格式良好的、信息豐富的指南以及常見(jiàn)問(wèn)題的解答和平易近人的研究論文的能力。我們應(yīng)該努力把那部分世界奪回來(lái)。這種損失該歸咎于什么呢？對(duì)風(fēng)格的過(guò)分依賴(lài)？CSS？還是 JavaScript？PHP？。

世界上最好的語(yǔ)言警告！

看到?jīng)]，這才叫感謝。mattsta 追求純干貨，別給我整一些花里胡哨的！

而且這篇文章還讓 mattsta 確信他沒(méi)有能力實(shí)現(xiàn)一個(gè) CRC-64 算法，因此實(shí)際上他是依靠 pycrc 來(lái)實(shí)現(xiàn)的。

然后這位老哥又說(shuō) yahyahyah，linux kernel 也是這樣用的。

老哥還找到一篇介紹 slicing by 8 的放在英特爾網(wǎng)上的論文，不過(guò)現(xiàn)在已經(jīng)沒(méi)了。所以先嘲諷了一波英特爾，還順帶還吐槽了傻*谷歌代碼，每次打開(kāi)這個(gè) pdf 都自動(dòng)下載，而不是在線瀏覽。

這老哥真的對(duì)我胃口哈哈哈。mattsta 的文章還沒(méi)結(jié)束，下面寫(xiě)的是一些關(guān)于實(shí)現(xiàn)的細(xì)節(jié)。有興趣的朋友到時(shí)候可以看看，文末會(huì)放鏈接。我就不再跟下去了。

我們?cè)賮?lái)看身為 Redis Contributor 為何 mattsta 會(huì)寫(xiě)這一篇文章？不應(yīng)該提 pr 直接解決嗎？難道這算法有什么致命之處使得 Antirez 不接受？我們來(lái)追蹤一下！

追蹤事情的來(lái)龍去脈

首先這篇文章寫(xiě)于2014-12-22

mattsta 在 2013-12 開(kāi)始了對(duì) redis.io 的第一次提交。

隨后 mattsta 就開(kāi)始了對(duì) Redis 的輸出，在2014-04-01，提出了相關(guān)的 issue，并且附上了自己的對(duì)比。

提出的 issue 沒(méi)有受到團(tuán)隊(duì)成員的響應(yīng)，寂寞如雪，只有一位金毛小哥，為其打 call。這個(gè)issue 此時(shí)還是 open 的。

然后在當(dāng)年，2014-11-23，mattsta創(chuàng)建了 crcspeed 庫(kù)，并且提交了實(shí)現(xiàn)。

并在2014-12-22提交了pr，竟然和寫(xiě)文章是同一天！而且是先寫(xiě)了文章再提的 pr。一開(kāi)始我以為是提了pr遲遲得不到采納，然后才一怒之下寫(xiě)的文章。

可以看到隔了一天有團(tuán)隊(duì)人員回應(yīng)了，他說(shuō)我不知道這是否會(huì)被合并(我認(rèn)為它應(yīng)該) ，但是，該死的！這是一個(gè)偉大的提升！牛皮克拉斯！

2014-12-23，mattsta 又對(duì) pr 做了一些補(bǔ)充說(shuō)明。然而沒(méi)有回應(yīng)。

直到2015-01-10，mattsta 對(duì) pr 又做了一波更新。

終于在2015-02-25號(hào)，等到了 antirez 的回復(fù)。

antirez 說(shuō)，很有意思但是我想看到固定的大于 5% 收益的可重現(xiàn)的測(cè)試用例，即使是綜合性的測(cè)試也沒(méi)事，只要明顯的能在 Redis 中反映出來(lái)即可，我相信從集群的 crc16 入手測(cè)試能很簡(jiǎn)單的證明效果，現(xiàn)在對(duì)于合并更快的實(shí)現(xiàn)不是很急，不過(guò)如果有一天你完成了這樣的測(cè)試，我將會(huì)很感激。

然后給這個(gè)pr加了個(gè)標(biāo) review - and - merge。

還加了個(gè)ps: 通常來(lái)說(shuō)證明一個(gè)東西的性能提升是很重要啊，我在這里做了個(gè)例外，因?yàn)槲铱此鼏为?dú)的測(cè)試確實(shí)快了很多，我相信即使 Redis 沒(méi)有使用上這個(gè)經(jīng)驗(yàn)，但是遲早我們也會(huì)受益于它

簡(jiǎn)單的說(shuō)就是 mattsta 你得搞個(gè) Redis 相關(guān)的測(cè)試來(lái)證明它真的使得 Redis 性能提升了啊，這樣我才能合并啊，不過(guò)我做個(gè)例外，是認(rèn)可你這個(gè)的，給你打個(gè)標(biāo)！(但是沒(méi)有真正的合并)。

也就是說(shuō) antirez 其實(shí)是認(rèn)可 mattsta 的實(shí)現(xiàn)的，但是 mattsta 沒(méi)有給出和 Redis 相關(guān)的測(cè)試，所以還不能合并這個(gè) pr。

這個(gè) pr 就到這里過(guò)了，再也沒(méi)有更新，也還是 Open 的。

mattsta 也沒(méi)有繼續(xù)說(shuō)啥，對(duì) Redis 輸出到2015年初之后就不再輸出了。而 CRC-16 到現(xiàn)在還使用的是老版本，CRC-64 是 antirez 在時(shí)隔六年的2020-04-28做的修改，使用的就是 mattsta 的crcspeed。

再回頭看

可以到 mattsta 在 2014-04-01就提了 issue，然后沒(méi)有任何回應(yīng)的情況下自己研究，找了許多資料，最后實(shí)現(xiàn)了 crcspeed，也肝出了一篇文章，之后在同一天提了PR，然后過(guò)了近兩個(gè)月的時(shí)間得到 antirez 的回復(fù)，由其沒(méi)有關(guān)于 Redis 的實(shí)質(zhì)上的測(cè)試，因此不給合并，但被給予肯定。

但我個(gè)人猜測(cè) mattsta 可能還是有點(diǎn)生氣的，這么一個(gè)通用的東西，我都給了橫向?qū)Ρ葴y(cè)試了！這原理我也分析的這么清楚了！這明擺著肯定是 ok 的，你還要我測(cè)試啥！不合并拉倒！(再次傲嬌.jpg)。

而 antirez 所在的角度不一樣，他是 Redis 的親爸爸。你說(shuō)的沒(méi)錯(cuò)，我認(rèn)可你，但是你得拿出實(shí)質(zhì)性的證明給我看看你幫我的 Redis 提升了多少。

這篇文章講述的就是這么個(gè)事兒。其實(shí)我就是帶著八卦之心來(lái)看為何身為 Contributor 的 mattsta 提的明顯正確的 pr 沒(méi)有被 merge，至于什么 CRC 的我不關(guān)心哈哈哈哈。

當(dāng)然 mattsta 的鉆研之心值得我們學(xué)習(xí)，當(dāng)然還有他那搞笑的形容和五彩斑斕的感謝。而 antirez 對(duì) pr 的嚴(yán)謹(jǐn)也值得我們效仿。

鏈接

https://matt.sh/redis-crcspeed

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

歡迎添加大白微信，交流學(xué)習(xí)、扯淡吹牛，來(lái)！