設計一個自動補完的後端
問題描述
設計一個能夠自動補完的後端系統，就像Google或亞馬遜
設計目的
像往常一樣，我們首先須要讓設計目標更加明確。花兩分鐘問自己這些問題：
- 這個系統需要處理多大的查詢數量(以秒計)？
- 期待的延遲？
- 這些查詢的文本是無邊界的嗎(像是Google)？或是有一些事先定義好的種類(像是亞馬遜的商品建議)？
- 我們想要怎樣顯示這些補全的建議？
- 其他
這些問題的答案會引導整個設計的選擇，例如：
- 如果這個系統是為了一個熱門網站設計的，那麼查詢次數很可能每秒超過100K。這在現實生活中已經是非常大的量了，這個數字告訴我們兩件事：
- 這個系統要能夠擴容到支援100K次的查詢，這不是單一台機器能夠承受的量。
- 系統需要消化這100K的查詢以便更新整個自動補全的結果，這通常可以透過非同步的方式處理。
- 自動補全系統通常對於延遲很敏感，也就是說我們期待他的P95延遲在10ms。這個數字表示我們不必要把所有的資料的快取在記憶體，無論是跨資料中心的網路呼叫或使用SSD的隨機存取都是幾個ms的等級。但是，我們應該盡量多使用記憶體來減少延遲和資料庫的負載。一個小提醒，如果使用的是關係型資料庫例如MySQL，那必須要使用足夠好的機器等級，以AWS RDS來說，需要使用
db.r4.8xlarge並且搭配幾個讀取複本來處理每秒100K的查詢。 - 假設我們要處理的是純文本輸入像是Google的自動補完，那表示字彙量很可能會很大。
- 如果當使用者輸入1到M個字元而我們要顯示最熱門的N個推薦，那麼N和M的值會決定整個設計走向。舉例來說，當
N = M = 5，如果我們決定預先計算所有推薦，那我們只需要使用(26 + 262 + 263 + 264 + 265) * 5 *avg_len_of_word的空間，約小於0.5GB，這樣的使用量可以輕鬆被保存在記憶體中。另一方面，當N = M = 10，這就需要超過1K TB的空間，這也就是說我們需要很多機器來將這些資料保存在記憶體。
作法
其中一種可行的架構看起來會像：
K-V pairs
因為有延遲限制的前提，所以動態產生推薦清單不太實際。我們需要預先計算結果，並將其用鍵值對的方式儲存起來；鍵是使用者輸入的前綴，而值是最熱門的推薦清單。例如：("mic", ["michael jordan", "microsoft"])，這表示當前綴是mic的時候，有兩個最熱門的推薦：michael jordan和microsoft。選用鍵值對而不是其他更省空間的作法，如Trie的理由是，鍵值對更方便保存/利用。
Search log
搜尋記錄保留使用者產生的原始資料，這些資料來源是可信任的，之後會被用來計算鍵值對。用上述的例子，如果使用者輸入mic，並且使用者最後要的結果是microsoft，這表示另一個使用者輸入mic也有可能是想要microsoft，這背後的演算法是貝葉斯推斷(Bayesian inference)。
Offline Job
我們需要一個背景任務來將搜尋記錄轉換成鍵值對，這通常是運行一個map-reduce形式的批次處理任務。接著我們將產生的鍵值對推送到一個分散式存儲，例如：Redis或HBase；我們也需要將鍵值對推送到前方的伺服器來更新他們的快取。實務上，我們可以透過MQ如Kafka來可靠的推送結果。我們需要直接更新伺服器的理由是，這樣可以減少熱門資量在資料庫上的負載。
Servers
這些伺服器負責快取那些預先計算的結果和處理所有來自使用者的查詢。當輸入的字段沒有命中自己的本地快取，伺服器就查詢後端的分散式鍵值存儲。如果資料量超過一台機器的記憶體所能承受，我們就需要透過雜湊的方式將那些前綴分片在不同機器上，並且，為了能兼顧擴容，我們需要像下圖般維護複本；這個設計很常見也與其他設計問題相似。你可以在我其他文章內找到更多關於分片/複本的介紹。
在上圖中，我們使用第一個字母來做分片(這可能導致分片不平衡)。我們儲存所有首字母是a的鍵值對在節點一和節點二，首字母是b的放在節點二和三，而首字母是c的則是放在節點一和三，並且我們將這些資訊放在一個註冊表中。實務上，這個註冊表可以放在支援Paxos-like協定的任何伺服器群集(包含Zab和Raft)。路由層隱藏所有資料分片的複雜度；首先讀取/快取註冊表，接著透過輪詢的方式發送請求到對應節點，例如：將a開頭的搜尋關鍵字依序送到節點一和二。
個人化資料
在這個架構中，我們並沒有處理個人化資料。如果使用者在Google中搜尋，搜尋結果可能會參考個人興趣，這可以透過結合過去的搜尋歷史來產生。
CDN
另一個設計選擇是，我們通常會導入CDN來減少延遲。我在這篇文章先忽略這個討論，你可以參考另一篇文章來了解為什麼需要CDN。
