大家好，我是 yes。

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

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

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

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

Fancy CRCing You Here

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

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

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

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

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

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

簡單翻一下就是：

• Redis 決定忽略吞吐量和延遲方面的提高，因為他們更喜歡像1999年那樣編碼。

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

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

然后老哥就開始放招。

What’s Wrong

他先說了下 CRC 本質(zhì)上是無法并行的，因為下一次迭代的值取決于前一次迭代。然后又指出了 Redis 中的哪幾個地方使用到 CRC。

CRC-64 用在了三個地方：

• 在跨實例遷移鍵時添加校驗和，（并驗證上述校驗和）

• 為 RDB 輸出添加一個校驗和，用于復(fù)制和持久化（是可選項，可通過配置禁用，因為性能低）

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

CRC-16 用在了一個地方：

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

mattsta 接著放招：

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

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

What’s Better

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

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

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

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

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

What’s Improved

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

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

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

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

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

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

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

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

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

Result

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

我們來看看老版本的代碼確實有一堆，我截了一小段。

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

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

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

Real-World Impact

mattsta 又指出 crcspeed 能給Redis 帶來啥呢？

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

并且

CRC-16來映射槽的時候，如果用戶正在做一些古怪的事情，比如使用300 MB 的按鍵，那么快速的 CRC-16可以減少400% 的集群槽分配開銷！

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

mattsta 說這是一個有效和高效的多方面的雙贏！

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

Minor Notes

可以看出 mattsta 是不想造輪子的，但是實在是沒有輪子?。∮谑撬荒茏约簩崿F(xiàn)一個，這是個新輪子！

Resources Consulted

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

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

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

有一說一，確實，純路人。身為一個txt，編寫良好、格式良好，有趣。在風(fēng)格、布局和語氣的所有方面都經(jīng)過了專家的深思熟慮。

夸一番 mattsta 覺得還不夠，還得加一點自己的想法。

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

世界上最好的語言警告！

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

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

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

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

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

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

追蹤事情的來龍去脈

首先這篇文章寫于2014-12-22

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

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

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

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

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

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

2014-12-23，mattsta 又對 pr 做了一些補充說明。然而沒有回應(yīng)。

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

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

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

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

還加了個ps: 通常來說證明一個東西的性能提升是很重要啊，我在這里做了個例外，因為我看它單獨的測試確實快了很多，我相信即使 Redis 沒有使用上這個經(jīng)驗，但是遲早我們也會受益于它

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

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

這個 pr 就到這里過了，再也沒有更新，也還是 Open 的。

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

再回頭看

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

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

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

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

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

鏈接

https://matt.sh/redis-crcspeed

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

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