坑：時間和空間的平衡
這篇文章非常長，希望你能看完，要是看完有很酣暢的感覺就最好了。這一篇的 坑 主要來說說架構中 時間和空間的平衡 吧，這里的時間指代比較廣，可能是 開發時間 ，但大部分指的是執行時間，也就是算法的 時間復雜度 了，而 空間 就是算法中經常說的 空間換時間 中的 空間 了，一個好的系統，設計出來必然是各種 時間復雜度 和 空間復雜度 平衡出來的結果，架構設計的過程，并不僅僅是模塊的堆疊，在走到岔路口的時候，更多的是 時間和空間平衡 之后選的一個技術方案，這一篇，我會用一個 搜索提示服務設計 的實際例子，來說一下架構設計的過程中， 時間和空間 的各種矛盾，怎么分析，怎么選擇，最后淌過這些 時空的坑 。
0. 搜索提示是什么
搜索提示是搜索引擎的重要組成部分，雖然一般是作為一個單獨的服務來對外提供服務，但在一個搜索系統中，搜索提示是非常重要的組成部分，我還沒看到哪個比較成熟的搜索引擎沒有搜索提示功能的。
首先，我們看看搜索提示是什么，大家肯定都用過，就是下面這些個東西
1. 搜索提示的場景和目的
搜索提示一般情況下是為了提高用戶的搜索體驗，更快的選擇合適的搜索詞，提高檢索的效率的，但是因為搜索框的流量實在是太大了，所以搜索提示也扮演著廣告變現的責任，互聯網嘛，有流量就有變現，比如下面這個圖，明顯就是一個廣告啦。
2. 初步技術選型
2.1 搜索提示的需求
要實現一個搜索提示系統，首先需要確定的是需要提示出來什么東西，有兩種提示方式。
- 一種是提示出其他的搜索詞，這也是大部分的搜索提示所做的，提示出其他用戶的類似搜索詞。
- 還有一種是提示出現有的結果集有的東西，這種實現方式比較少見，比如一個生鮮類的電商網站，商品數量比較少，那么沒必要去提示一些用戶的搜索詞，直接把商品名稱（比如蘋果，桃子，橘子）提示出來就行了，這種提示方式我們這里不討論，因為實現起來比較簡單。
2.2 技術棧
既然知道需求了，那么開始選擇技術棧了。
- 首先，既然有其他用戶的搜索詞，那么必然有一個離線的數據收集和處理的系統來完成其他用戶的搜索日志處理，生成需要的數據。
- 其次，需要一個單獨的API服務，來提供搜索提示的功能，輸入為不完整的搜索詞，輸出為根據這個搜索詞提示出來的其他搜索詞，檢索方式的話，一般都是使用前綴匹配的方式了，這個大家都比較認可。
- 最后，需要前端有個js代碼來實時調用后臺的API，這個不在我們的討論范圍內。
整個系統的結構圖應該是下面這個樣子，離線模塊處理完日志數據以后，推送到API模塊中，給前面的前端提供服務。
好了，框框設計好了。也就是架構圖完成了哦，真是牛逼的架構啊，三個框，離線，在線，前端全齊了。
接下來，我們來看看在線API部分的設計吧，我們先假設離線數據都已經準備好了，就是一堆用戶的搜索詞，如何快速的前綴匹配這些詞就成了API設計部分的關鍵了，有這么幾種實現方式。
- 粗暴的短平快方式
用redis保存所有信息，每條信息類似
{KEY:北 VALUE:北京，北京大學，北大，北京遇上西雅圖}
{KEY:北京 VALUE:北京，北京大學，北京遇上西雅圖} ….
每次來了請求的話，直接查詢redis給出結果返回，就是占點空間，最好還需要一臺單獨的服務器。
- 優雅點的實現方式
前綴匹配嘛，最先想到的數據結構就是 Trie樹 了，所以所有的Key可以用 Trie樹 來保存和檢索，速度也挺快的，而且空間占用比較少。
- 復雜點的實現方式
既然是檢索嘛，就直接用搜索引擎的倒排索引技術來實現嘛，速度也夠，而且數據量也可以支持得很大。
3. 時間與空間的平衡一
實際工程應用中，這三種實現方式我都見過，而且有些實現方式是把這三種結合起來使用了，后面的文章我會說到。
具體使用哪一種需要看你的實際場景，這三種實現方式差不多正好對應三種場景。
- 如果你是個小型的電商或者論壇之類的，每天的搜索量也不是很大，而且在可見的未來也不會變得很大，而且也不差錢，那么直接第一種，說不定一天就能擼出來，速度還不錯，但是這種有一些缺陷，首先，value值不能太復雜，影響效率，所以可擴展性不是很強，而現在的電商搜索提示中往往還有很多其他信息需要保存，redis作為緩存服務器提供高并發服務的前提是數據量比較小，最好在2K以內，這樣的話用redis就有點不合適了。 這種方案是個存空間的選擇了，用空間換取了檢索時間和開發時間，多虧有redis這種神器。
- 如果是個大型的搜索引擎或者電商，搜索日志已經是巨量了，而且搜索詞多種多樣，那么第三種倒排索引技術為基礎的實現方式可能是更好的選擇，而且既然是大搜，技術都是現成的，索引分片，集群都是現成的，直接改了上就是。 這種方式用長期的開發時間和檢索速度上稍微的降低換取了內存空間，如果從頭開始做的話，時間成本比較高。
- 大部分時候，第二種實現方式是大家都采用的方式，首先沒有第一種那么粗暴，并且能完成方案一的所以功能，單機就能達到較好的效果，也不用索引分片，也不用集群，所以工程復雜性不是很高，也能在較短的時間內實現出來。其次第二種方案可擴展性較強，后面掛個倒排文件就可以變成簡化版的第三方案。 這種方式用算法換取了內存空間，用O(n)替代了O(1)，換取了內存空間，也是標準的計算機領域的時間換空間了。
通過一番分析下來，決定使用第二種實現方式，就是Trie樹的方式了，好了，API的基本選型確定了，那么開始設計，準備寫代碼吧。
4. Trie樹的多種結構
既然確定了 Trie樹 的實現方式，那么首先要了解一下 Trie樹 吧，以及 Trie樹 的各種結構，看看具體用哪個吧。
4.1 基本Trie樹
Trie樹 又叫 字典樹 ，本質上是一個多叉樹，每一個節點就是一個多叉的結構，如果是英文的匹配，那么是一個 26叉樹 ，每個節點一個26長度的數組，每個節點的數據結構如下
type TrieNode struct{
flag bool //是否是一個完整的詞
hasNextbool //是否還有后繼字符
nexts [26]*TrieNode
}
而 Trie樹 畫出來就是下面這個樣子。
從畫出來的圖，很直觀的可以看出來這棵樹的構造方法和遍歷方法，如果是純英文的話，每個節點都有一個26長度的數組，來了一個字符，通過字符的編號直接就可以遍歷到下一個節點，查找的時候復雜度就是O(K)，K表示查找的字符串長度，這種數據結構簡單明了，實現起來也很容易。
4.2 優化后的Trie樹
基本Trie樹的數據結構有個問題，就是內存使用得太多了，如果是中文查找的話，需要把所有的中國字都編號到這個數組中，內存就爆了，于是有一種優化方法，就是把數組變成變長的，這種Trie樹的節點數據結構變成下面的樣子了，節點查找變成一個順序查找或者二分查找了。
type TrieNode struct{
flag bool //是否是一個完整的詞
hasNextbool //是否還有后繼字符
nexts []*TrieNode //變成變長數組了
}
4.3 雙數組Trie樹
所謂雙數組Trie樹，當然就是通過兩個數組來實現這棵樹了，這兩個數組分別叫 base數組 和 check數組 ，一個是基礎數組，一個是檢查數組。
Trie樹實際上是一種 有限狀態機 ，通過 狀態轉移矩陣 在各個狀態之間跳轉，雙數組Trie樹極大的節省了空間，大致就是下面這個樣子，我后面會有一篇專門的文章來說Trie樹實現的，這里就不詳細展開了，實在等不及的可以自己先搜索一下相關資料看看雙數組Trie樹吧。
5. 時間與空間的平衡二
OK，三種Trie樹的實現方式都說了，現在要開始抉擇了，我們先看看這三種數據結構的時間和空間。
第一種空間占用大，特別是中文的情況，檢索的時間效率為O(n)，其中n為 每次請求 的字符串的長度，這種實現方式基本上屬于新人練手的水平，純粹為了了解這個數據結構或者大學生做做課程設計，工程化的可能性幾乎為0。
第二種空間基本不浪費，但檢索的時間效率如果按照二分進行每個節點的查找的話，每個節點的查找時間變成了O(lg(n))，整體的查找時間變成K*O(log(n))，同樣插入效率也變低了。
第三種情況空間不浪費，時間效率也為O(n)。
初看，肯定選第三種了，但是！！第三種實現方式有個致命的缺陷，就是無法向下遍歷（ 具體可以自己看看雙數組的實現方式 ），也就是說我輸入 北京 ，找不到 北京大學，北京愛上西雅圖 ，因為它已經不是一個樹型結構了，無法向下遍歷了。所以如果不對第三種結構進行改造的話，是無法滿足我們的功能的。
要改造，最簡單的辦法就是在每個詞后面掛一個鏈表，表示這個詞的后繼詞都是什么，像下圖這樣。
如果按上圖那么來的話，需要輔助的空間來存儲后繼詞，那么問題又來了，又是一次時間和空間的抉擇了，是選擇 K*O(log(n)) 的第二種方案，然后后繼詞實時遍歷樹來獲取(又要耗費一定的時間)，還是選擇選擇第三種方案，用空間換取時間呢？
好，既然這樣，我們來仔細算算這個賬，我們以每個節點都存一個中文來算，雖然常用的漢字大概2500個，但其中最常用的才500左右。
先看第二種方案，那么我們大概估算出，每個節點的平均數組長度大概600 （實際上除了第一層的節點，后面的節點數組長度完全達不到這個量級，用600屬于極限估算了） ，600的二分查找大約需要7到8次，取個平均值4次，那么每次查詢的時間就是 4*K（K是字符串的長度） ，如果我們定好最長的提示詞不超過8個字（太長也沒意義），那么首先這個樹的高度就是8了，如果50萬的詞量的話，使用多少內存大概能算出來，然后每次遍歷下級節點的時間就是 600^(8-K) （如果數組的每個元素都有值），我去，這么大，嚇死了，好，我們即便假設每個節點的數組長度平均為60，要遍歷完也要 60^(8-K) ，也嚇尿了，所以實時遍歷所有子節點的方式不可取，而且后繼詞最多也就提示出10個，遍歷出這么多詞還要排序，遍歷全部節點實在是沒有必要，所以，第二種方案要么放棄，要么也要改造，如何改造呢？
因為詞基本上都是離線算好的，稍微把節點的數據結構優化一下，在節點中加一個字段，表示哪個子節點有需要的數據（排序前10的詞），這樣往下遍歷的時候就直接遍歷相應的下標就可以了，就能把 60^(8-K) 這種遍歷減少到幾十次，從而找到10個提示詞，我們把這個結構叫 二次優化的Trie樹 。
這一輪的時間和空間的比拼，第三個方案感覺就要勝利了，但第二個方案的優化版貌似也還能接受，一個耗費空間，查詢速度快，一個節省空間，查詢速度慢點。
這里多說一下，其實上面只是預估的辦法比較搓，這么寫是為了說預估的技能，最直接的就是拿著日志統計一遍，得到一堆不超過8位長度的搜索詞，同時也能算法兩個方案的內存使用規模和大概的查找效率，這樣的預估辦法最準確，但是在大部分時候我們并沒有這么多數據，所以只能做一些基本的預估。
6. 離線數據處理
好了，我們先把檢索部分放一放，來看看離線數據處理部分吧。我們先要確定一下什么東西需要在離線部分算好，什么東西需要在線處理？
- 首先，日志的清洗肯定是離線部分了，我們先要把沒有搜索結果的詞去掉，然后去掉太長的詞（假定超過8的都不要），然后保留有一定熱度的詞（比如每天搜索量超過10次的詞），等等一些規則以后，假如剩下了50萬的詞，那這50萬就是我們的基礎數據了。
- 其次， Trie樹 的構建是離線構建好還是實時往服務推送由服務端去構建呢？
- 還有，排序的時候是離線給每個搜索詞打個分，然后實時排序呢？還是離線把序都排好，服務端直接使用結果呢？
7. 時間與空間的平衡三
雖然是離線處理，但一樣有時間和空間的選擇。
我們先來看構建部分， Trie樹的構建是離線構建好還是實時往服務推送由服務端去構建 ，首先我們需要確定的是這個 搜索提示 服務需不需要實時更新，一般情況下， 搜索提示 沒有那么強的實時性要求，一般一天或者兩天更新一次體驗也不會太差，所以做實時更新的搜索提示，要不就是你實在是太蛋疼了，要不就是遇到了一個特別讓人蛋疼的產品經理（ 臥槽，黑了一下產品經理啊 ）。所以我們使用離線構建的方式構建好兩個數組和輔助的數據結構，都存在磁盤上，服務端啟動的時候讀取文件就行了，這是用離線時間換取的服務端的時間，是很劃得來的。
再來看看排序的部分，很明顯，排序離線做好也比較合適，排序的位置基本不會有太大的變化，但是如果排序離線做好的話，那么輔助的數據結構就會比較大了，因為每個前綴后面跟著的10個詞都要排好序放在輔助結構中，但如果我們只是把每個詞打個分（比如就按熱度給個分），然后用第二個方案 （優化的Trie樹） 的存儲方式，在線的時候去排序，那么輔助結構就會小很多，兩種情況的結構大概就是下面這樣的區別。
左邊的是全排序好了的，直接使用，雙數組Trie樹+輔助結構方式；右邊的是只是打了分的，優化的Trie樹，遍歷出結果以后實時排序的。
離線排序的空間占用大，即便優化一下，把詞都放一個地方單獨存著，輔助結構中只保存詞的編號，一樣也比較占地方，但是查詢速度快啊。在線排序的方式不怎么占地方，就是每個節點多了一個分數的字段，需要實時排序一下，雖然是實時排序，但個數就10個，不管是快排還是堆排，都很快的，所以時間效率也慢不到哪去。
8. 整體的時空平衡
綜合衡量一看，我個人覺得兩種方式都能接受，具體選哪一個就仁者見仁了。
- 如果搜索詞的量比較穩定，不會有太大的變化，那么使用 雙數組Trie樹+輔助數據結構+離線構建Trie樹+離線排序 的方式更合適。
- 如果搜索詞雖然現在是50萬，但很可能會增加得比較多，或者像下圖一樣，搜索提示的頁面還會承載很多其他的數據的話，那么使用 二次優化的Trie樹+離線構建Trie樹+離線打分+實時排序 的實現方式更合適，因為能節省更多的內存給后續擴充詞語用或者給其他數據用。
- 還有如果對速度要求苛刻，那么就第一種，如果沒那么苛刻，那就第二種
架構設計沒有好壞，只有合適不合適。
9. 總結
上面分析了這么一大堆，淌過三個的 時間與空間的坑 ，終于基本確定了技術方案了，這其實也是系統架構設計中經常會要遇到的選擇了，架構師們把這些選擇做完以后，可以開始細分模塊設計開發了，所以，一個小小的系統就這么多選擇，各種空間和時間的平衡，你說架構師哪那么好當？呵呵，你以為就畫完這篇文章的第一圖就架構結束了啊。
這里只是用 搜索提示 作為一個例子來說明系統設計的時候需要時時刻刻關注 時間 和 空間 這兩個因素的平衡，現在很多人設計系統的時候基本上不太關注 時間 ，因為高配的服務器，幾十上百GB的內存隨便用，所以大多數都把設計往 空間 上去靠，用更多的空間來換取執行效率，這本身并沒有什么問題，誰不希望更快啊，但是有時候預估一下，有可能雖然犧牲了一點時間效率，但是換來了不少的空間，這樣的系統在數據量變大時有更多的可擴展空間，我覺得是非常值得的交換。
再有，對 數據結構和算法的了解 以及 預估算能力 其實是 平衡時間和空間 的重要技能，也是架構設計中避坑的基本技能，所以有公司的面試題會出現 請你估算一下黃河出海口的面積 這類估算題，因為 預估算能力 也是重要的架構技能吧。
10. 更深入一下
上面只是這個系統的一小部分，搜索提示需要做的遠不止如此，想想下面幾個場景，如果是你，你要如何設計呢？如何平衡時間和空間呢？歡迎討論哈：）
- 需要拼音支持，就像這樣
- 需要拼音首字母支持
- 某些搜索提示需要更加詳細的信息
- 需要對每個用戶的搜索歷史進行搜索提示【這個比較難點】
來自：http://blog.jobbole.com/109906/