昨天 Amplitude 發表了一篇關於擴展分析的文章，脈絡是在使用 Set data type(集合資料型別) 的情境下。部落格文章在此：https://amplitude.com/blog/2015/08/25/scaling-analytics-at-amplitude/

在 Hacker News 上，有人問為什麼不改用 Redis：https://news.ycombinator.com/item?id=10118413

Amplitude 的開發者們有他們不使用 Redis 的一套理由，一般來說，如果你有一個非常特定的問題，並希望以最好的方式來擴展它，實作一個垂直整合的解決方案是合理的。我並不排斥重新造輪子，有時候你就是需要一個非常特定的輪子，而通用型系統可能無法提供。此外，打造自己的解決方案能讓你掌控自己的成果，激發你的創造力，並增強你身為開發者對自身能力的信心，讓你在未來無論出現什麼臭蟲，都能在沒有外部協助的情況下進行除錯。

另一方面，從零開始打造系統軟體當然是一件非常複雜的事，如果希望持續積極地開發某個東西，就需要不斷地投入開發；如果沒有專屬的團隊負責，那就意味著會得到一段停滯不前、不再演進的程式碼。如果它非常垂直且高度專門化，很可能這個新系統只能處理整個應用問題中的一小部分，卻又必須作為一個額外的元件來管理。此外，如果它主要是由一位或少數幾位程式設計師打造，而他們之後離開了公司，那麼要修復與演進它就會是一個非常大的問題：既沒有可觀的外部社群，也沒有原始的開發者。

基本上，在內部自行打造並非本身就有好壞之分，要視情況而定。當然，是否值得從零開始實作某個東西、何時又不值得，是一種需要敏銳判斷力的事。優秀的開發者都明白這一點。

就我個人而言，無論 Amplitude 開發者最終的解決方案是什麼，閱讀他們的過程以及他們為何不使用 Redis 都是很有趣的。他們提出的其中一個疑慮是 Redis 中 Set 資料型別的額外開銷。我認為他們有這樣的疑慮是對的，Redis 的 Sets 確實可以更節省記憶體，而在讀到 Amplitude 的文章數週前，我就已經開始探索提升 Sets 記憶體效率的方法。今天我想與大家分享這些計畫。

資料型別的雙重表示法

原則上，原本只有樸素的資料結構，或多或少是按照演算法教科書所建議的方式實作的：資料結構的每個節點都是透過動態配置來實作。配置的額外開銷、肥大的指標、低落的快取局部性，是這種基本解法的主要限制。

Pieter Noordhuis（皮耶特·諾德胡斯）和我後來為 Redis 的抽象資料型別實作了專門的版本，使其非常節省記憶體，使用單次配置來容納數十個或數百個元素於單一配置中，有時還會使用特製的編碼來更有效地利用空間。這些資料結構的版本對於某些操作具有 O(N) 的時間複雜度，或者有時僅限於具有特定格式（數字）或大小的元素。

舉例來說，當你建立一個 Hash 時，它一開始會以一種對少量元素而言很節省記憶體的方式來表示。之後如果元素數量達到特定門檻，就會被轉換成真正的 hash table(雜湊表)。這意味著 Redis 資料型別的記憶體效率很大程度上取決於它儲存的元素數量。

下一步：Redis lists

在某個時間點，Twitter 的開發者們意識到，沒有理由要從以單一配置中的元素陣列來表示 List 中的項目，轉換為實際的 linked list(鏈結串列)，後者的記憶體效率要低得多。介於兩者之間還有另一種選擇：由代表少數項目的陣列所組成的 linked list。他們的實作並未處理在中間刪除項目時的重組問題。我和皮耶特·諾德胡斯過去曾試圖釐清這是否值得，但我們隱約覺得重組所付出的努力可能無法被節省的空間所抵銷，而一個不會重組的此類概念實作，作為 Redis lists 的通用實作來說又太過脆弱：在中間刪除幾個元素，你的記憶體使用量就會劇烈變化。

幸好，Matt Stancliff（馬特·史坦克利夫）以非常出色的方式實作了這個想法，並包含了重組的部分，經過一些實驗後，他證明了新的實作從效能的角度來看至少與 Redis 目前的實作一樣好，而從記憶體使用量的角度來看則要好得多。此外，lists 的記憶體效率不再是串列大小的函數，而且只需處理單一表示法。

Lists 算是有點特別，因為要以小型陣列的鏈結串列來達成，確實是一種可能無法輕易對應到其他資料型別的最佳表示法。有可能對 Sets 及其他資料型別做類似的事嗎？

Redis Sets

Sets 的記憶體使用量有點特別。它們不像 Redis 其他資料結構那樣，對於由字串組成的集合擁有專門的表示法。因此，即使是一個非常小的 Set 也會消耗大量記憶體。專門的表示法其實是存在的，而且非常出色，但僅在 Set 僅由數字組成且數量較少時才會生效：在這種情況下，我們會以一種稱為「intset」的特殊編碼來表示 Set。它是一個有序的整數線性陣列，因此我們可以使用二分搜尋來測試成員是否存在。陣列會根據集合中最大的元素自動改變每個元素的大小，因此表示一個包含字串 1、20、30、15 的集合，每個元素僅需一個位元組加上一些額外開銷，因為這些字串可以被表示為數字，且落在 8 位元的範圍內。然而，只要在集合中加入「a」，它就會被轉換成一個完整的 hash table：

127.0.0.1:6379> sadd myset 1 2 3 4 5
(integer) 5
127.0.0.1:6379> object encoding myset
"intset"
127.0.0.1:6379> sadd myset a
(integer) 1
127.0.0.1:6379> object encoding myset
"hashtable"

整數的 Sets 是 Redis 中一種非常常用的資料型別，因此擁有這樣的機制確實非常有用。但為什麼我們沒有像處理其他所有資料那樣，為由非數字字串組成的小型集合提供專門的表示法呢？嗯，想法是，擁有一種具有*三種*表示法的資料型別，從 Redis 內部的角度來看並不是一件好事。如果你查看 t_zset.c 或 t_set.c，就會看到處理多種表示法需要一些細心處理。你越想抽象化以處理 N 種表示法，就越無法使用某些最佳化。此外，List 的故事顯示，擁有一種兼具所有優點的單一表示法是可能的。你在掃描包含 N 個元素的小型聚合體時所損失的，在更好的快取局部性上又能贏回來，因此嘗試一些看起來像是悲慘的時間／空間權衡的做法，實際上並非如此。

特製化 Redis hash tables

大型的 hashes、非數字的（或大型的）sets，以及大型的 sorted sets，目前都是由 hash tables 來表示。實作位於 dict.c 檔案中。它是一個以相當直觀的方式實作的 hash table，使用 chaining(鏈結法)來解決碰撞。這個 hash table 實作中特別之處只有兩點：它為了重新雜湊而從不阻塞，重新雜湊的過程是以漸進式的方式處理的。這是我在 VMware 贊助的前幾個月內完成的，就延遲而言當然是一大勝利。dict.c 還實作了一個由皮耶特·諾德胡斯發明的稱為「scanning」的特殊原語，它是一種無額外開銷且無狀態的基於游標的迭代器，但具有合理的保證。除此之外，Redis 的 hash table 預期鍵與值都是指向某個東西的指標，以及用於比較和釋放鍵、釋放值的方法。

這就是你會想要設計通用 hash table 的方式：到處都是指標和方法（函式指標）來處理值。然而，Redis 的資料結構有一個有趣的特性：複雜資料結構中的每個元素在語意上永遠都是字串。Hashes 是字串欄位與字串值之間的對映。Sets 是字串的無序集合，依此類推。

如果我們實作一個被設計為僅儲存字串鍵與字串值的 hash table，會發生什麼事呢？嗯……看起來有一種簡單的方法可以讓這樣的 hash table 非常節省記憶體。我們可以將 load factor(負載因子)設為大於 1 的某個值，例如 10，而如果 hash table 中有 5 個 bucket(雜湊桶)，每個 bucket 平均將包含 10 個元素。

因此每個 bucket 將會像是 key-value 項目的線性陣列，帶有前綴長度，方式與我們目前為小型資料型別所使用的編碼非常相似。像是這樣：

0: <3>foo<3>bar<5>hello<6>world!<0>
1: <8>user:103<3>811 … <0>
2: … <0>

依此類推。編碼可以是特製的，或者只是像 MessagePack 這類現有的編碼。因此，你在每個 bucket 中額外付出的工作，有望能被你獲得的更好局部性所彌補。

在此資料結構之上實作 scanning 和漸進式重新雜湊也是可行的，我已經做了初步的分析，雖然不可能直接複製 dict.c 中的實作，但有可能找到其他方法來達到相同的效果。

請注意，從技術上講，在這樣的 hash table 中儲存指標是可能的：從 hash table 實作的角度來看，它們就只是字串，而且可以在 hash table 型別中標示，那些是需要特殊處理的指標（例如 free-value 函式指標或類似的東西）。然而，只有透過測試才能知道這是否值得。

然而，要將此用於 Sets 以外的用途，或至少要*僅*使用這種表示法、汰除我們目前擁有的小型表示法，還有一些必須解決的問題。例如，目前的小型表示法有一個非常有趣的特性：它們本身就已經是自身的序列化，無需額外的工作：我們利用這一點將資料儲存到 RDB 檔案中、在 Redis Cluster 中的節點之間傳輸資料等等。這個特製化的 hash table 最好也能具有相同的特性，或者至少每個單獨的 bucket 都應該已經處於序列化格式，而無需任何後處理工作。如果不是這樣，我們也可以僅在擴展之後用這種新的 dictionaries 來取代通用的 hash tables，這本身就已經是一大勝利。

結論

這是一個初步的想法，需要一些時間來改進設計，之後透過實作來驗證，並進行深入的負載測試，以確保在某些合理的負載下不會出現巨大的效能衰退。如果一切順利，我們最終可能會得到一個比過去節省得多記憶體的 Redis 伺服器。這樣的 hash table 也可能被用來儲存主要的 Redis dictionary，以使每個鍵的額外開銷小得多。