最近，知名博主 @drdrxp (張炎潑) 一條關(guān)于SlimTrie介紹的微博引發(fā)了熱議
高可用架構(gòu)聯(lián)系了 XP 老師，通過本文首次介紹了 SlimTrie 的詳細(xì)實(shí)現(xiàn)。本文作者李文博，吳義譜、張炎潑對本文亦有貢獻(xiàn)。
李文博，目前就職于白山云科技有限公司，從事云存儲研發(fā)工程師。在白山主要有 s2 分布式對象存儲系統(tǒng)的日常建設(shè)和 ec 冷數(shù)據(jù)存儲集群開發(fā)的實(shí)戰(zhàn)經(jīng)歷，在分布式存儲服務(wù)方向有一些積累和經(jīng)驗(yàn)。
吳義譜，目前就職于白山CWN云存儲部門，2016年加入白山，主要負(fù)責(zé)分布式對象存儲的研發(fā)工作，熟悉了解行業(yè)內(nèi)主流的分布式存儲系統(tǒng)，積累了豐富的云存儲相關(guān)技術(shù)，并運(yùn)用這些技術(shù)攻克了實(shí)際中遇到的難點(diǎn)，運(yùn)用EC(Erasure Code)技術(shù)解決了冷數(shù)據(jù)在保證可靠性的同時降低33%成本，運(yùn)用haystack技術(shù)解決百億級別小文件的訪問IO瓶頸問題，運(yùn)用paxos技術(shù)解決幾十億集群管理和leader選舉問題。
張炎潑 (xp)，30 年軟件開發(fā)經(jīng)驗(yàn)，物理系背叛者，設(shè)計(jì)師眼中的美工，bug maker，vim 死飯，懸疑片腦殘粉。曾就職新浪, 美團(tuán)?，F(xiàn)在白山云，不是白云山 。
上一篇 SlimTrie 設(shè)計(jì)篇 [1] 中，我們介紹了單機(jī)百億文件的索引設(shè)計(jì)思路，今天我們來具體介紹下它代碼級別的實(shí)現(xiàn)。文中我們要解決的問題是: 在一臺通用的100TB的存儲服務(wù)器的內(nèi)存中, 索引100億個小文件。
而最終我們通過SlimTrie對存儲系統(tǒng)中靜態(tài)文件的索引, 內(nèi)存開銷只占 Btree的 13%, 查詢速度卻是 Btree 的 2.6倍!
索引的一點(diǎn)背景知識
索引可以被認(rèn)為是業(yè)務(wù)數(shù)據(jù)（用戶文件）之外的一些"額外"的數(shù)據(jù), 在這些額外的數(shù)據(jù)幫助下, 可以在大量的數(shù)據(jù)中快速找到自己想要的內(nèi)容. 就像一本數(shù)學(xué)課本的2個"索引": 一個是目錄, 一個是關(guān)鍵詞索引.現(xiàn)實(shí)系統(tǒng)中，存儲系統(tǒng)中的索引需要做到：
足夠小 : 一般實(shí)現(xiàn)為將索引信息全部存儲在內(nèi)存中可以達(dá)到比較好的性能。訪問索引的過程中不能訪問磁盤, 否則延遲變得不可控(這也是為什么leveldb或其他db在我們的設(shè)計(jì)中沒有作為索引的實(shí)現(xiàn)來考慮).
足夠準(zhǔn)確 : 對較小的文件, 訪問一個文件開銷為1次磁盤IO操作。
分析下已有的2種索引類型, hash-map類型的和tree類型的,Hash map類索引利用hash函數(shù)的計(jì)算來定位一個文件：
優(yōu)勢 ：快速，一次檢索定位數(shù)據(jù)。非常適合用來做 單條 數(shù)據(jù)的定位。
劣勢 ：無序。不支持范圍查詢。必須是等值匹配的，不支持“>”、“<”的操作。
內(nèi)存開銷: O(k * n)。
查詢效率: O(k)。
而基于Tree 的索引中代表性的有: B+tree, RBTree, SkipList, LSM Tree, 排序數(shù)組 :
優(yōu)勢 : 它對保存的key是排序的；
劣勢 : 跟Hash map一樣, 用Tree做索引的時候, map.set(key = key, value = (offset, size)) 內(nèi)存中必須保存完整的key, 內(nèi)存開銷也很大: O(k * n)；
內(nèi)存開銷: O(k * n)；
查詢效率: O(k * log(n))；
以上是兩種經(jīng)典的索引都存在一個無法避免的問題： key的數(shù)量很大時，它們對內(nèi)存空間的需求會變的非常巨大：O(k * n) 。
如果100億個key（文件名）長度為1KB的文件。那么僅這些key的索引就是 1KB * 100億 = 10,000GB。導(dǎo)致以上的經(jīng)典數(shù)據(jù)結(jié)構(gòu)無法將索引緩存在內(nèi)存中。而索引又必須避免訪問磁盤IO，基于這些原因我們實(shí)現(xiàn)了一套專為存儲系統(tǒng)設(shè)計(jì)的SlimTrie索引.
索引數(shù)據(jù)大小的理論極限
如果要索引n個key, 那每條索引至少需要 log 2 (n) 個bit的信息, 才能區(qū)分出n個不同的key. 因此理論上所需的內(nèi)存空間最低是log 2 (n) * n * n, 這個就是我們空間優(yōu)化的目標(biāo). 在這里, 空間開銷僅僅依賴于key的數(shù)量，而不會受key的長度的影響!
我們在實(shí)現(xiàn)時將所有要索引的key拆分成多組，來限制了單個索引數(shù)據(jù)結(jié)構(gòu)中 n的大小, 這樣有2個好處:
n 和 log 2 (n) 都比較確定, 容易進(jìn)行優(yōu)化；
占用空間更小, 因?yàn)? a * log(a) + b * log(b) <(a+b) * log(a+b)；
SlimTrie索引結(jié)構(gòu)的設(shè)計(jì)
我們最終達(dá)到每個文件的索引平均內(nèi)存開銷與key的長度無關(guān)， 每條索引一共10 byte, 其中:
6 byte是key的信息;
4 byte是value: (offset, size); // value的這個設(shè)定是參考通常的存儲實(shí)現(xiàn)舉的一個例子，不一定是真實(shí)生產(chǎn)環(huán)境的配置。
實(shí)現(xiàn)思路：從Trie開始
在研究Trie索引的時候, 我們發(fā)現(xiàn)它的空間復(fù)雜度(的量級)、順序性、查詢效率(的量級)都可以滿足預(yù)期, 雖然實(shí)現(xiàn)的存儲空間開銷仍然很大，但有很大的優(yōu)化空間。
Trie 就是一個前綴樹, 例如，保存了8個key（"A", "to", "tea", "ted", "ten", "i", "in", and "inn"）的Trie的結(jié)構(gòu)如下：
Trie的特點(diǎn)在于原生的前綴壓縮, 而Trie上的節(jié)點(diǎn)數(shù)最少是O(n), 這在量級上跟我們的預(yù)期一致。但Trie仍然需要每個節(jié)點(diǎn)都要保存若干個指針(指針在目前普遍使用的64位系統(tǒng)上單獨(dú)要占8字節(jié))。
SlimTrie的設(shè)計(jì)目標(biāo)
功能要求：
SlimTrie能正確的定位存在的key，但不需要保證定位不存在的key。
SlimTrie支持范圍定位key。
SlimTrie的內(nèi)存開銷只與key的個數(shù)n相關(guān)，不依賴于key的長度k 。
SlimTrie查詢速度要快。
限制：
SlimTrie只索引靜態(tài)數(shù)據(jù)。 數(shù)據(jù)生成之后在使用階段不修改, 依賴于這個假設(shè)我們可以對索引進(jìn)行更多的優(yōu)化。
SlimTrie支持最大16KB的key 。
SlimTrie在內(nèi)存中不保存完整的key的信息。
最終 性能目標(biāo)對比其他幾種常見的數(shù)據(jù)結(jié)構(gòu)應(yīng)是：
SlimTrie的術(shù)語定義
key：某個用戶的文件名，一般是一個字符串。
value: 要索引的用戶數(shù)據(jù), 這里value是一組(offset, size)。
n: key的總數(shù): <= 2 15 。
k: key的平均長度 < 2 16 。
Leaf 節(jié)點(diǎn): SlimTrie中的葉子節(jié)點(diǎn), 每個Leaf對應(yīng)一個存在的key。
LeafParent 節(jié)點(diǎn)：帶有1個Leaf節(jié)點(diǎn)的節(jié)點(diǎn)。 SlimTrie中最終Leaf節(jié)點(diǎn)會刪掉，只留下LeafParent節(jié)點(diǎn)。
Inner 節(jié)點(diǎn): SlimTrie中的Leaf和LeafParent節(jié)點(diǎn)之外的節(jié)點(diǎn)。
SlimTrie的生成步驟
我們通過一個例子來看看SlimTrie的生成: 如果一步步將Trie的存儲空間壓縮, 并在每一步處理后都驗(yàn)證去掉某些部分后, 它仍然滿足我們的查詢的準(zhǔn)確性要求. 然后在這個例子的基礎(chǔ)上，給出完整的算法定義。
SlimTrie的生成分為3部分：
1. 先用一個Trie來構(gòu)建所有key的索引。
2. 在Trie的基礎(chǔ)上進(jìn)行裁剪, 將索引數(shù)據(jù)的量級從O(n * k)降低到O(n)。
3. 通過3個compacted array來存儲整個Trie的數(shù)據(jù)結(jié)構(gòu), 將內(nèi)存開銷降低。
1 SlimTrie原始Trie的建立
假設(shè)有一組排序的key用來構(gòu)建索引：”abd”, “abdef”, “abdeg”, “abdfg”, “b123”, “b14”，首先創(chuàng)建一個標(biāo)準(zhǔn)的Trie：
查詢遵從標(biāo)準(zhǔn)的Trie的查詢流程：
例如從Trie中查詢”abdfg”，首先定位到根節(jié)點(diǎn)，然后從查詢key中取出第1個字符”a”, 在根節(jié)點(diǎn)上找到一個匹配的分支”a”，定位到第2層節(jié)點(diǎn)”a”，再從被查詢的key中取出第2個字符”b”，匹配第2層中節(jié)點(diǎn)”a”的分支”b”，依次向下，直到遇到一個Leaf節(jié)點(diǎn)，結(jié)束查詢。
2 SlimTrie的裁剪
基于SlimTrie的設(shè)計(jì)可以看出： 多分支的SlimTrie節(jié)點(diǎn)是關(guān)鍵的 ，單分支的節(jié)點(diǎn)對定位一個存在的key沒有任何幫助。所以可以針對節(jié)點(diǎn)類型，進(jìn)行幾次單分支節(jié)點(diǎn)的裁剪。
并且在每次剪裁后，我們會依次展示剪裁過的Trie依舊滿足我們設(shè)計(jì)目標(biāo)中對查詢的功能需要。
LeafParent節(jié)點(diǎn)的裁剪
上圖中，”abdfg”中的”g”節(jié)點(diǎn)不需要保留, 因?yàn)榇嬖诘膋ey的前綴如果是”abdf”, 它最后1個字符只能是”g”，所以將”abdfg”的”g”去掉。
同理，”b123”中的”3”也去掉。得到裁剪之后的結(jié)果：
圖中使用正則表達(dá)式的風(fēng)格表示路徑：
“.” 代表任意字符； “{1}” 代表1個； ”f.{1}“ 代表f后面越過（Step）一個字符。
剪掉單分支LeafParent節(jié)點(diǎn)后依舊滿足查詢需求：
還以查詢key ”abdfg”為例，假設(shè)目前定位到節(jié)點(diǎn)”abd”，要繼續(xù)查詢key中的字符”f”，發(fā)現(xiàn)Trie中有分支”f”，并且”f”之后的可以略過”g”的查詢，則查詢直接定位到”abdf.”節(jié)點(diǎn)，查詢結(jié)束。
Inner 節(jié)點(diǎn)的裁剪
繼續(xù)觀察上圖, a分支下的”b”, “d”節(jié)點(diǎn)是不需要的, 因?yàn)橐粋€存在的key如果以”a”開頭, 它的接下來的2個字符一定是”b”, “d”，同樣b節(jié)點(diǎn)后面去掉1分支，得到第2次 裁剪后的結(jié)果：
剪掉單分支Inner節(jié)點(diǎn)后依舊滿足查詢需求：
繼續(xù)以查詢”abdfg”為例，假設(shè)開始查詢，定位到根節(jié)點(diǎn)，要查詢key中第1個字符”a“，根節(jié)點(diǎn)有1個分支”a”與之匹配，并且可以越過2個字符，此時查詢定位到節(jié)點(diǎn)”a..”上，并繼續(xù)查詢key的第3個字符”f”，最終也定位到節(jié)點(diǎn)”a..f.”上。查詢結(jié)束。
去掉尾部Step
最后，去掉所有單分支LeafParent節(jié)點(diǎn)節(jié)點(diǎn)后綴，以及指向這個節(jié)點(diǎn)的路徑的Step數(shù)（例如“a..f.”和“b.2.”中尾部被Step掉的字符不需要記錄。但同時包含分支的LeafParent節(jié)點(diǎn)需要保留Step數(shù)，例如“a..”，指向它的分支“a.{2}”中的Step數(shù)還必須記錄）
去掉LeafParent節(jié)點(diǎn)的Step數(shù)后 依舊滿足查詢需求 ：
當(dāng)查詢一個存在的key：”abdfg”時，假設(shè)定位到了“a..”節(jié)點(diǎn)（對應(yīng)查詢字符串中的”abd“），繼續(xù)查找下一個字符”f“時，因?yàn)閗ey”abdfg”是存在于Trie中的，所以被查詢的key中f后面剩下的字符數(shù)（1個”g“）跟分支“f.{1}”中記錄的需要Step掉的字符數(shù)一定是相等的，所以當(dāng)查詢到節(jié)點(diǎn)”a..f”時，發(fā)現(xiàn)它是1個LeafParent節(jié)點(diǎn)，則直接略過被查詢key中剩余的字符。最終結(jié)束查詢。
裁剪之后的SlimTrie：
每個節(jié)點(diǎn)都有大于1個子節(jié)點(diǎn), 除LeafParent節(jié)點(diǎn)之外。
SlimTrie的大小跟key的長度無關(guān). 也就是說任意長度的key的集合都可以使用有限大小的SlimTrie來索引: SlimTrie最多有2n-1個節(jié)點(diǎn): 最多節(jié)點(diǎn)是出現(xiàn)在所有inner節(jié)點(diǎn)都是二分的時候（空間復(fù)雜度為O(n)）
3 SlimTrie的壓縮
現(xiàn)在我們在結(jié)構(gòu)上已經(jīng)將SlimTrie裁剪到最小, 接下來還要在實(shí)現(xiàn)上壓縮SlimTrie實(shí)際的內(nèi)存開銷。樹形結(jié)構(gòu)在內(nèi)存中多以指針的形式來實(shí)現(xiàn), 但指針在64位系統(tǒng)上占用8個字節(jié), 相當(dāng)于最差情況下, 內(nèi)存開銷至少為 8*n個字節(jié)，這樣的內(nèi)存開銷還是太大了，所以我們使用2個約束條件來壓縮內(nèi)存開銷：
key的個數(shù)n：n <2 15；目的是通過id來替代指針，將節(jié)點(diǎn)id值限制在16bit內(nèi)。節(jié)點(diǎn)id分配規(guī)則是：從根節(jié)點(diǎn)開始，逐層向下，按照節(jié)點(diǎn)從左到右的順序編號。
4 bit的word：創(chuàng)建Trie時，將每個長度為k的字符串，視為2 * k個4 bit的word，而不是k個8 bit的byte，作為SlimTrie上節(jié)點(diǎn)的單位。這樣做的目的是減少分支數(shù)量，限制存儲分支信息的bitmap的大小。
另外為了更具體的說明這個例子，我們假設(shè)value是1個4 byte的記錄, 來展示SlimTrie中每個節(jié)點(diǎn)對應(yīng)的信息，其中只有 綠色 是需要記錄的, 如下圖：
上面的表格中, 因?yàn)?個節(jié)點(diǎn)”是否leaf“的信息跟”是否有value“是對等的，所以leaf信息不需要記錄。而最終的索引需要的 總存儲量是:
分支信息 + 子節(jié)點(diǎn)位置 + Step 信息 + value
總共小于: 16bit * (n-1) + 16bit * (n-1) + 16bit * (n-1) + 4byte * n；
因此總存儲量小于 10 * n byte；其中去掉4 * n 個byte的value信息， 大約每個Key 6字節(jié)。 接下來我們來解釋下如何在實(shí)現(xiàn)上達(dá)成6 字節(jié)這個目標(biāo)：
SlimTrie內(nèi)部的數(shù)據(jù)結(jié)構(gòu)
通過上面的表格我們看到，如果要完整的表達(dá)SlimTrie的結(jié)構(gòu)，需要存儲4個映射表：
uint16 id → uint16 branch
每個節(jié)點(diǎn)的分支有哪些； 因?yàn)槭褂昧? bit的word, 所以每個節(jié)點(diǎn)最多只有16個分支，每個節(jié)點(diǎn)的分支表使用一個16 bit的bitmap存儲；
uint16 id → uint16 offset
每個節(jié)點(diǎn)的第一個子節(jié)點(diǎn)id；
uint16 id → uint16 step
每個節(jié)點(diǎn)被查詢到之后需要越過源查詢key后面幾個word； 因?yàn)閗ey的最大長度設(shè)定為16 KB，所以step最大是2 * 16 KB = 2 15；
uint16 id → uint32 value
實(shí)際存儲的數(shù)據(jù)，也同時表示了是否是LeafParent節(jié)點(diǎn)；
把SlimTrie抽象成這幾個映射表后，所需的數(shù)據(jù)結(jié)構(gòu) 就變得清楚了：
整數(shù)作為下標(biāo)，整數(shù)為元素的數(shù)組，例如 branch可以定義為 uint16_t branch[n]。但是，并不是每個節(jié)點(diǎn)id都存在分支，這個數(shù)組中很多位置是空的。如果用數(shù)組來保存會造成一半的空間浪費(fèi)（Inner節(jié)點(diǎn)數(shù)量最多只占一半）。所以我們需要一個更加緊湊的數(shù)據(jù)結(jié)構(gòu)來保存這幾個映射表，這里我們引入了一個數(shù)據(jù)結(jié)構(gòu)：compacted array。
compacted array：壓縮數(shù)組
compacted array類似數(shù)組，但不為 不存在 的數(shù)組元素分配空間。在實(shí)現(xiàn)上，為了標(biāo)識空的數(shù)組元素，使用了1個bitmap，雖然每個要存儲的信息平均多分配了1個bit，但整體空間開銷非常接近于我們的預(yù)期。
使用壓縮數(shù)組來保存SlimTrie的邏輯結(jié)構(gòu), 壓縮數(shù)組用來保存最大大小不超過2 16 個條目的信息，首先定義壓縮數(shù)組的結(jié)構(gòu)：
因?yàn)槲覀兪褂?6 bit的id代替指針, 這就要求每個組里的節(jié)點(diǎn)(node)數(shù)量不能超過65536(2 16)，由于SlimTrie生成時會產(chǎn)生至多 n-1 個中間節(jié)點(diǎn)(在滿二叉的情況下總結(jié)點(diǎn)數(shù)是 2n-1), 所以我們需要限制每個組的原始數(shù)據(jù)條目數(shù)n 小于2 15 =3 2768。
compacted array的內(nèi)存額外開銷
除了數(shù)據(jù)items數(shù)組之外，每個compacted array的額外數(shù)據(jù)包括：
4個 uint16 的成員屬性，以及跟元素總數(shù)相關(guān)的bitmap 和 offset，分別占(n / 64) * 8 byte 和 (n / 64) * 2 byte；
于是每個compacted array的總的內(nèi)存額外開銷是 (0.15 * n + 8) byte；
到這里，可以近似認(rèn)為SlimTrie的空間開銷是(6 * 1.15 * n + 24) byte。
對于SlimTrie，我們只需要3個compacted array來保存其結(jié)構(gòu)：內(nèi)部節(jié)點(diǎn)(inners)，用戶數(shù)據(jù)（LeafParent）和Step信息：
inners數(shù)組:
inners的每個元素是4 byte, 其中2 byte是一個bitmap來保存最多15個子節(jié)點(diǎn)的branch. 另外一個2 byte的uint16表示它第一個子節(jié)點(diǎn)id(offset)，因?yàn)橐粋€節(jié)點(diǎn)的所有子節(jié)點(diǎn)id是連續(xù)的，所以只需要保存第一個子節(jié)點(diǎn)。
在訪問SlimTrie時, branch_bitmap和第一個子節(jié)點(diǎn)的id（offset），幾乎所有的情況下都需要同時對其訪問，因此把他們放到一個compacted array中，減少compacted array查詢的次數(shù)（雖然查詢開銷不大，但我們也非常關(guān)注每個點(diǎn)的優(yōu)化！）。
LeafParent數(shù)組:
LeafParent的一個item保存4 byte的用戶數(shù)據(jù)value 。
Step數(shù)組:
Step數(shù)組中的每個元素是單分支節(jié)點(diǎn)裁剪掉的節(jié)點(diǎn)數(shù)，使用一個2 btye的uint16表示。
最終SlimTrie的所有信息在內(nèi)存中的組織方式如下：
內(nèi)存開銷分析
假設(shè) ：
共有n個key，也就是LeafParent節(jié)點(diǎn)(或value)的個數(shù)；
每個value是4字節(jié) ；
至多存在n - 1個Inner節(jié)點(diǎn)；(全二分時最多)
并且Step 只存在于指向Inner節(jié)點(diǎn)的分支，因此最多也是n - 1個；
再考慮compacted array的額外開銷，最終整體的內(nèi)存開銷如下：
在存儲系統(tǒng) 中使用SlimTrie作為數(shù)據(jù)索引的場景里, 如果用 32G內(nèi)存, 大約可以索引32億個文件。
SlimTrie的查詢實(shí)現(xiàn)
SlimTrie的查詢類似于普通Trie的查詢，在創(chuàng)建過程中已經(jīng)逐步描述了查詢在裁剪之后的Trie中的處理方式, 現(xiàn)在將整個過程統(tǒng)一用下面這個c語法的偽代碼來描述查詢過程，其中幾個函數(shù)get_value，get_branches，get_step實(shí)際上會通過compacted array的"get"操作來訪問SlimTrie的3個映射表來實(shí)現(xiàn)。
其中src是1個4 bit word的數(shù)組：
索引合并優(yōu)化
到目前為止索引的空間利用率已經(jīng)非常高了，但是，它還是一個不安全的設(shè)計(jì)！因?yàn)樗鼪]有給出一個最壞情況保證：如果文件超過32億個怎么辦？如果出現(xiàn)了超出的情況，最好的結(jié)果恐怕也是內(nèi)存開始使用swap，系統(tǒng)反應(yīng)變慢3個數(shù)量級。
因此我們需要對算法給出一個穩(wěn)定下界，妥善處理超多文件的情況， 所以可以在準(zhǔn)確度和內(nèi)存開銷方面做一個折中：這里有一個假設(shè)是, 磁盤的一次IO, 開銷是差不多的, 跟這次IO的讀取的數(shù)據(jù)量大小關(guān)系不大，所以可以在一次IO中讀取更多的數(shù)據(jù)來有效利用IO ：
對一個存在的key, 我們的索引將返回一個磁盤上的offset, 我們一定可以在這個offset和之后的64KB的磁盤空間上找到這個文件，也就是說, 我們的索引不允許索引過小的文件, 只將文件的位置定位到誤差64KB的范圍內(nèi)。
最差情況是全部文件都是小文件(例如10K, 1K), 這時索引個數(shù) = 100T / 64KB =~ 20億條。按照每條索引10 字節(jié)計(jì)算，需要20GB內(nèi)存空間。
SlimTrie索引的內(nèi)存開銷測試
首先我們用一個基本的實(shí)驗(yàn)來證明我們實(shí)現(xiàn)的內(nèi)存開銷和上文說到的理論是相符的。實(shí)驗(yàn)選取Hash 類數(shù)據(jù)結(jié)構(gòu)的map 和 Tree 類數(shù)據(jù)結(jié)構(gòu)的B-Tree 與 SlimTrie 做對比，計(jì)算在同等條件下，各個數(shù)據(jù)結(jié)構(gòu)建立索引所占用的內(nèi)存空間。
實(shí)驗(yàn)在go語言環(huán)境下進(jìn)行，map 使用 golang 的 map 實(shí)現(xiàn)，B-Tree使用Google的BTree implementation for Go ( https://github.com/google/btree ) 。 key 和 value 都是 string 類型（我們更多關(guān)心它的大小而不是類型）。實(shí)驗(yàn)的結(jié)果數(shù)據(jù)如下 ：
上圖中可以看到:
SlimTrie 作為索引在內(nèi)存的節(jié)省上碾壓 map 和 B-Tree。
SlimTrie 作為索引其內(nèi)存占用的決定因素是 key的數(shù)量，與key的大小無關(guān)。
SlimTrie 作為Key-Value map的內(nèi)存開銷測試
看過以上比較，SlimTrie 似乎勝得過于輕松，其根本原因是 SlimTrie “開掛” 似地縮減了索引的 key 的空間。這一點(diǎn)上面也提到了，SlimTrie 作為索引有一個前提約束是，索引只提供完整的 value 信息而不提供 key 的信息。這一點(diǎn)在作為數(shù)據(jù)定位的索引時，是可以接受的，也正是因?yàn)檫@一點(diǎn) SlimTrie 在和 map 的內(nèi)存占用比較中得以大獲全勝。
現(xiàn)在如果拋開 “索引” 這個用處，在通用場景下，讓SlimTrie作為索引, 同時也記錄完整的key的信息, 將他實(shí)現(xiàn)為一個通用的key-value map, 看看 SlimTrie 這個數(shù)據(jù)結(jié)構(gòu)的性能。這里需要將 key + value 當(dāng)做 SlimTrie 的一個 value 去使用就可以做到。
此次試驗(yàn)，我們同樣選取了幾組 key 和 value 的大小，在 同之前一樣的 go 語言環(huán)境下進(jìn)行了測試，SlimTrie 的 value 是這樣一個結(jié)構(gòu)：
因?yàn)檫@次測試所有的數(shù)據(jù)結(jié)構(gòu)都保存了完整的key和value信息，所以我們只看memory overhead(除了key, value本身數(shù)據(jù)之外, 額外需要的空間)。測試得到的數(shù)據(jù)，見下面的圖表：
兩者進(jìn)行對比，可以明顯看出，SlimTrie 所占用的空間額外開銷仍然遠(yuǎn)遠(yuǎn)小于 map 和 B-Tree 所占的內(nèi)存，在 map 和 btree 中, 每個 key 能夠節(jié)省大約 50 Byte, 而SlimTrie是6字節(jié)左右 .
SlimTrie的查詢性能測試
內(nèi)存占用空間大獲全勝之后，我們還對 SlimTrie 的查詢進(jìn)行了測試，同時與 map 、Btree 進(jìn)行了比較。在與內(nèi)存測試相同的go語言環(huán)境下進(jìn)行實(shí)驗(yàn)。為了公平也同樣對比的是SlimTrie實(shí)現(xiàn)的key-value map跟 golang map, btree的性能對比.
存在的 key 的查詢效率對比
越小越優(yōu):
不存在的 key 的查詢效率對比
越小越優(yōu):
可以看出 SlimTrie 的查詢效率與 無序的hash類型的Map 相比有差距, 但對比同樣是保持了順序性的btree相比, 性能是Btree的 2.6倍 左右.
查詢時間隨k和n的變化
另一方面，在上圖中，我們也能夠看到，SlimTrie 的實(shí)際查詢的耗時在 150ns 左右，加上優(yōu)秀的空間占用優(yōu)化，作為存儲系統(tǒng)的索引依然有非常強(qiáng)的競爭力。
內(nèi)存開銷隨k和n的變化
上圖中我們可以看出, 不論是隨著key的數(shù)量增大或是key的長度變長, 單條索引的內(nèi)存開銷都非常穩(wěn)定地保持在6~7個字節(jié)范圍內(nèi)。
總結(jié)
SlimTrie 為未來而生。當(dāng)下信息爆炸增長，陳舊的索引模式已無法適應(yīng)海量數(shù)據(jù)新環(huán)境，存儲系統(tǒng)海量數(shù)據(jù)的元信息管理面臨巨大挑戰(zhàn)，而SlimTrie 提供了一個全新的解決方法，為海量存儲系統(tǒng)帶來一絲曙光，為云存儲擁抱海量數(shù)據(jù)時代注入了強(qiáng)大動力，讓我們看到了未來的無限可能。
作為索引，SlimTrie 的優(yōu)勢巨大，可以在10GB內(nèi)存中建立1PB數(shù)據(jù)量的索引，空間節(jié)約驚人，令以往的索引結(jié)構(gòu)望塵莫及；時間消耗上，SlimTrie 的查找性能與 sorted Array 接近，超過經(jīng)典的B-Tree。拋下索引這個身份，SlimTrie 在各項(xiàng)性能方面表現(xiàn)依舊不俗，作為一個通用 Key-Value 的數(shù)據(jù)結(jié)構(gòu)，內(nèi)存額外開銷仍遠(yuǎn)遠(yuǎn)小于經(jīng)典的 map 和 Btree 。
SlimTrie 不僅為我們解決了眼前的困境，也讓我們看到了未來的可能。它的成功不會停下我們開拓的腳步，這只是個開始，還遠(yuǎn)沒有結(jié)束。
參考鏈接：
1. https://openacid.github.io/tech/algorithm/slimtrie-design
2. https://github.com/openacid/slim （項(xiàng)目地址）
本文作者李文博，吳義譜、張炎潑對本文亦有貢獻(xiàn)。轉(zhuǎn)載本文請注明出處，GIAC全球互聯(lián)網(wǎng)架構(gòu)大會深圳站將于2019年6月舉行，屆時將有系統(tǒng)優(yōu)化等專題深入探討相關(guān)話題，敬請期待。
參考閱讀：
QMQ順序消息設(shè)計(jì)與實(shí)現(xiàn)
經(jīng)典開源代碼分析——Leveldb高效存儲實(shí)現(xiàn)
聊聊Java String.intern 背后你不知道的知識
Redis作者：近期核心功能的一些思考和澄清
技術(shù)原創(chuàng)及架構(gòu)實(shí)踐文章，歡迎通過公眾號菜單「聯(lián)系我們」進(jìn)行投稿。轉(zhuǎn)載請注明來自高可用架構(gòu)「ArchNotes」微信公眾號及包含以下二維碼。
高可用架構(gòu)
改變互聯(lián)網(wǎng)的構(gòu)建方式
長按二維碼 關(guān)注「高可用架構(gòu)」公眾號
