昨天 Amplitude 發表了一篇關於擴展分析系統的文章，背景是使用 Set 資料型別。原文在此：https://amplitude.com/blog/2015/08/25/scaling-analytics-at-amplitude/

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

Amplitude 開發團隊有他們不使用 Redis 的理由，一般來說，如果你有一個非常特定的問題，並想用最理想的方式來擴展它，實作一個垂直整合的解決方案是合理的。我並不反對重造輪子，有時候你就是需要一個非常特定的輪子，而通用型系統不一定能提供。再者，打造自己的解決方案能讓你完全掌握自己做的東西，激發創造力，也能提升你身為開發者對自身能力的信心，讓你在未來無論出現什麼 bug，都能不需要外部協助就自行除錯。

另一方面，從零開始打造系統軟體當然是一件非常複雜的事，如果希望持續積極地開發，就需要不斷投入；如果沒有專門的團隊來維護，那就意味著會得到一個停滯不前、不會演進的程式碼。而且如果它非常垂直、非常專門，很可能這個新系統只能處理整個應用問題中的一小部分，卻還是得把它當作一個額外的元件來管理。此外，如果它主要是由一兩位後來離開公司的程式設計師所打造，那麼要修復和演進它就會是個非常大的問題：既沒有可觀的外部社群，也找不到原來的開發者。

基本上，在內部自行開發東西本身沒有好壞之分，要看情況。當然，能否判斷何時值得從零開始實作、何時不值得，是一種敏銳度。優秀的開發者都明白這一點。

就我來看，無論 Amplitude 開發團隊最終的解決方案是什麼，閱讀他們的過程以及他們為何不使用 Redis 的原因都很有意思。他們提出的一個顧慮是 Redis Set 資料型別的額外開銷（overhead）。我認為他們有這樣的顧慮是對的，Redis 的 Sets 確實可以更省記憶體，而在讀到 Amplitude 那篇文章的幾週前，我就已經開始探索提升 Sets 記憶體效率的方法。今天我想跟大家分享這些計畫。

資料型別的雙重表示

原則上，原本只有單純的資料結構，實作方式或多或少就跟演算法教科書建議的一樣：資料結構的每個節點都是動態配置出來的。配置本身的額外開銷、肥大的指標、糟糕的快取局部性，是這種基本解法最大的限制。

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

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

下一步：Redis Lists

有個時候，Twitter 的開發者意識到，實在沒必要從用單次配置容納 List 中所有元素的陣列，轉換成實際上記憶體效率低很多的鏈結串列。中間其實有個折衷：用一個由陣列組成的鏈結串列，每個陣列代表少數幾個項目。他們的實作在從中間移除元素時不會處理重組（defragmentation）。我和 Pieter 過去曾試著去評估這樣做是否值得，但我們隱約覺得，重組所付出的努力可能無法被節省下來的空間所抵銷，而一個不會重組的實作，作為通用的 Redis lists 實作來說又太過脆弱：只要從中間移除幾個元素，記憶體使用量就會劇烈變化。

幸好 Matt Stancliff 以非常出色的方式實作了這個想法，包含了重組的部分，經過一些實驗後，他證明新的實作在效能方面至少不輸給 Redis 當時的實作，而在記憶體使用上則好得多。而且 lists 的記憶體效率不再是 list 大小的函數，也只需要處理單一的表示法。

Lists 有點特別，因為用「由小陣列組成的鏈結串列」確實是一種最佳化的表示法，但不一定能輕易套用到其他資料型別上。有可能對 Sets 和其他資料型別也做類似的事嗎？

Redis Sets

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

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"

整數集合在 Redis 中是非常常用的資料型別，所以有這個機制其實非常有用。但為什麼我們沒有像其他資料型別那樣，為由非數字字串組成的小集合提供特製的表示法呢？嗯，原本的想法是，從 Redis 內部的角度來看，讓一個資料型別擁有 *三種* 表示法並不是件好事。如果你去看 t_zset.c 或 t_set.c，就會發現要處理多種表示法需要格外小心。你越想把處理 N 種表示法的邏輯抽象掉，就越無法使用某些最佳化。此外，List 的故事顯示，有可能用單一表示法就獲得所有好處。你在掃描包含 N 個元素的小聚合體時所損失的，會因為更好的快取局部性而補回來，所以可以去嘗試那些看起來像是慘烈的時間／空間權衡，但實際上並非如此的作法。

特製化 Redis 雜湊表

大的 hashes、非數字的（或大型的）sets，以及大的 sorted sets，目前都是用雜湊表來表示。實作就是 dict.c 檔案裡的那個。它是一個以相當簡單的方式實作的雜湊表，用鏈結法（chaining）來解決碰撞。這個雜湊表實作特別的地方只有兩點：它在重新雜湊（rehashing）時絕不會阻塞，重新雜湊的過程是漸進式地處理的。這是我在 VMware 贊助的頭幾個月內做的，當然在延遲方面是一大勝利。dict.c 還實作了一個由 Pieter Noordhuis 發明的特殊原語，叫做「scanning」，它是一種沒有額外開銷也沒有狀態、但有合理保證的基於游標的迭代器。除此之外，Redis 的雜湊表預期鍵和值都是指向某個東西的指標，以及用來比較和釋放鍵、釋放值的方法。

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

如果我們實作一個專門設計來只儲存字串鍵和字串值的雜湊表，會發生什麼事呢？嗯……看起來有個簡單的方法可以讓這樣的雜湊表非常省記憶體。我們可以把負載因子（load factor）設成大於 1 的某個值，例如 10，那麼如果雜湊表中有 5 個桶（bucket），每個桶平均就會包含 10 個元素。

所以每個桶會像是 key-value 項目的線性陣列，帶有前置的長度，方式非常類似我們目前對小型資料型別所使用的編碼。像是這樣：

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

依此類推。編碼可以是特製的，或直接使用現有的像是 MessagePack。所以在這裡，你在每個桶中多做的額外工作，有望能被你獲得的更好局部性所抵銷。

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

要注意的是，嚴格來說，在這樣的雜湊表中儲存指標也是可能的：從雜湊表實作的角度來看，它們就只是字串，而可以在雜湊表的型別中標示這些是指標，需要特別處理（例如釋放值的函式指標之類的）。不過是否值得這麼做，只有透過測試才能知道。

然而要把這個做法用在 sets 以外的用途，或者至少要 *只* 使用這種表示法、汰除我們目前擁有的小型表示法，還有一些問題必須解決。舉例來說，目前的小型表示法有一個非常有趣的特性：它們本身就已經是自身的序列化形式，不需要額外的工作：我們利用這點來把資料存進 RDB 檔案、在 Redis Cluster 的節點之間傳輸資料等等。這個特製的雜湊表最好也能有同樣的特性，或者至少每個單獨的桶本身就已經是序列化格式，不需要任何後處理工作。如果做不到這點，我們也可以只在擴展之後，用這種新的字典來取代通用的雜湊表，這本身就已經是一大勝利。

結論

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