需要澄清的問題

1. 是否是前綴匹配 (是）
2. 要返回多少個(gè)條目 （5）
3. 是按popularity做選擇嗎 （是）
4. 是否要支持多語言 （先不用）
5. 是否要支持特殊字符和大小寫敏感 （只考慮英文字母）
6. 多少DAU （1 billion）

功能性需求

輸入蜘醋，一段想要搜索內(nèi)容的前綴
輸出蝌箍，返回可能匹配的top 10 suggestion

非功能性需求

10億用戶撰豺，平均每人每天搜索5次，平均每次輸入10個(gè)字符
QPS = 1B * 5 * 10 / 100K = 200K
PEAK QPS 200K * 5 = 1M

性能：
因?yàn)榇蜃炙俣纫埠芸欤绻憫?yīng)時(shí)間過長(zhǎng)，就會(huì)影響用戶體驗(yàn)医舆。
比如用戶已經(jīng)輸了apple, 你還剛能返回 app的結(jié)果竭翠，
所以 latency < 100ms

可擴(kuò)展：
支持水平擴(kuò)展持隧，應(yīng)對(duì)高峰流量

高可用：
可以容錯(cuò)，當(dāng)部分服務(wù)離線逃片，斷網(wǎng)屡拨，服務(wù)依然可用

high-level 設(shè)計(jì)

服務(wù)應(yīng)該分為2個(gè)部分，在線去接受用戶的query請(qǐng)求褥实，離線去計(jì)算所有 query的popularity呀狼，并且把結(jié)果放進(jìn)cache，供線上服務(wù)最快使用损离。
這樣設(shè)計(jì)的思想是哥艇，這個(gè)服務(wù)是一個(gè)讀多寫少的服務(wù)，而且用戶對(duì)數(shù)據(jù)的實(shí)時(shí)性不那么敏感僻澎。

1. 數(shù)據(jù)收集服務(wù)： 當(dāng)用戶搜索敲下回車后貌踏，往日志里添加一條記錄。每天定時(shí)任務(wù)去計(jì)算所有搜索詞條被搜過的次數(shù)窟勃，并排序
2. 搜索建議服務(wù)： client端發(fā)送HTTP請(qǐng)求祖乳，返回符合前綴的TOP 10熱門搜索詞條。

如果數(shù)據(jù)量很斜酢：

select * from frequency_query where query like 'prefix%' order by frequency desc limit 5

上述sql 眷昆，可以對(duì)query建索引。

進(jìn)一步優(yōu)化

第一種優(yōu)化思路 是我們可以用key/ value store去做存儲(chǔ)汁咏。那么我們需要做的事情就是在離線亚斋，把所有QUERY的前綴集合，都當(dāng)做KEY攘滩，然后把top5 維護(hù)好寫進(jìn) K/V STORE里帅刊。

1649681694(1).png

那么當(dāng)用戶在搜索框中輸入QUERY 敲擊回車，數(shù)據(jù)收集服務(wù) 會(huì)更新 query -> cnt 的表漂问。然后每天更新一次數(shù)據(jù)赖瞒，構(gòu)建出 prefix -> top 10的表 供搜索建議服務(wù)使用。
在構(gòu)建prefix -> top 10级解，可以用分布式計(jì)算框架冒黑，比如MAP的是時(shí)候，就把一個(gè)單詞拆成多個(gè)前綴勤哗，到REDUCE那抡爹，去篩選TOP10。

這種優(yōu)化思路的好處是現(xiàn)成的KEY / VALUE 的數(shù)據(jù)庫是比較多的芒划。缺點(diǎn)是比較耗存儲(chǔ)冬竟。

當(dāng)然還有另一種優(yōu)化思路欧穴，就是用trie樹，優(yōu)點(diǎn)是節(jié)約空間泵殴，缺點(diǎn)是沒有現(xiàn)成的數(shù)據(jù)庫可以使用涮帘。所以需要自己序列化和反序列化。
當(dāng)然如果把整個(gè)數(shù)據(jù)結(jié)構(gòu)緩存進(jìn)內(nèi)存里笑诅，那么性能也是足夠好的调缨。

1649684125(1).png

我們把上面這顆trie樹，大概序列化為“C2,A2,R1,T,P,O1,D”

如果您注意到吆你，我們并沒有在每個(gè)節(jié)點(diǎn)中存儲(chǔ)頂級(jí)建議及其計(jì)數(shù)弦叶。 我們很難儲(chǔ)存這些信息; 由于我們的trie是自上而下存儲(chǔ)的，所以在父節(jié)點(diǎn)之前沒有創(chuàng)建子節(jié)點(diǎn)妇多，所以沒有簡(jiǎn)單的方法來存儲(chǔ)它們的引用伤哺。 對(duì)于這個(gè)，我們必須重新計(jì)算上面所有有計(jì)數(shù)的項(xiàng)者祖。 這可以在我們構(gòu)建trie時(shí)完成立莉。 每個(gè)節(jié)點(diǎn)將計(jì)算出它的首選建議，并將其傳遞給它的父節(jié)點(diǎn)七问。 每個(gè)父節(jié)點(diǎn)將合并其所有子節(jié)點(diǎn)的結(jié)果蜓耻，以確定其最優(yōu)建議。

1649686673(1).png

那么在反序列化的時(shí)候烂瘫，需要做MERGE所有孩子的CNT操作媒熊，然后存下TOP5。
每一次MERGE的時(shí)間復(fù)雜度 大概是（假設(shè)有K個(gè)孩子）k + 5 * logk

TIRE樹如何更新坟比？

離線更新，然后先發(fā)布到 secondary的內(nèi)存中嚷往，再做一個(gè)主從切換葛账。

如何做一個(gè)過濾層？

我們需要?jiǎng)h除皮仁，暴力的籍琳，色情的，或危險(xiǎn)的搜索建議內(nèi)容贷祈。 我們?cè)赥rie Cache前面添加一個(gè)過濾器層來過濾掉 不必要的建議趋急。 有了一個(gè)過濾器層，我們可以靈活地刪除結(jié)果基于不同的過濾規(guī)則势誊。 另外需要一個(gè)異步任務(wù)從數(shù)據(jù)庫中物理地刪除不需要的建議以便在下一個(gè)更新周期中使用正確的數(shù)據(jù)集來構(gòu)建trie呜达。

1649685415(1).png

如何分片

a.基于范圍的分區(qū):如果我們根據(jù)短語的第一個(gè)字母將它們存儲(chǔ)在單獨(dú)的分區(qū)中會(huì)怎么樣? 所以我們把所有以字母A開頭的項(xiàng)保存在一個(gè)分區(qū)中把以字母B開頭的項(xiàng)保存在另一個(gè)分區(qū)中，以此類推粟耻。 我們甚至可以把某些不太經(jīng)常出現(xiàn)的字母組合成一個(gè)分區(qū)查近。 我們應(yīng)該靜態(tài)地提出這種分區(qū)方案眉踱，以便始終能夠以可預(yù)測(cè)的方式存儲(chǔ)和搜索術(shù)語。

這種方法的主要問題是,它可能導(dǎo)致不平衡的服務(wù)器,例如,如果我們決定把所有條款從字母“E”成一個(gè)分區(qū),但后來我們意識(shí)到我們有太多的條件,從字母“E”,我們不能適應(yīng)一個(gè)分區(qū)霜威。

我們可以看到谈喳，上述問題將發(fā)生在每一個(gè)靜態(tài)定義方案。 不可能計(jì)算出我們的每個(gè)分區(qū)是否靜態(tài)地適合一臺(tái)服務(wù)器戈泼。

b.根據(jù)服務(wù)器的最大容量進(jìn)行分區(qū):假設(shè)我們根據(jù)服務(wù)器的最大內(nèi)存容量對(duì)trie進(jìn)行分區(qū)婿禽。 只要服務(wù)器有可用的內(nèi)存，我們就可以一直將數(shù)據(jù)存儲(chǔ)在服務(wù)器上大猛。 每當(dāng)一個(gè)子樹不能裝入服務(wù)器時(shí)扭倾，我們就在那里分割我們的分區(qū)，將這個(gè)范圍分配給這個(gè)服務(wù)器胎署，然后轉(zhuǎn)移到下一個(gè)服務(wù)器吆录，重復(fù)這個(gè)過程。 假設(shè)我們的第一個(gè)三服務(wù)器可以存儲(chǔ)從“A”到“AABC”的所有術(shù)語琼牧，這意味著我們的下一個(gè)服務(wù)器將存儲(chǔ)從“AABD”開始的術(shù)語恢筝。 如果我們的第二個(gè)服務(wù)器可以存儲(chǔ)到' BXA '，下一個(gè)服務(wù)器將從' BXB '啟動(dòng)巨坊，以此類推撬槽。 我們可以保留一個(gè)哈希表來快速訪問這個(gè)分區(qū)方案:

服務(wù)器1,A-AABC
服務(wù)器2,AABD-BXA
服務(wù)器3 BXB-CDA

對(duì)于查詢，如果用戶輸入了“A”趾撵，我們必須查詢服務(wù)器1和服務(wù)器2侄柔，以找到最前面的建議。 當(dāng)用戶輸入' AA '時(shí)占调，我們?nèi)匀恍枰樵兎?wù)器1和服務(wù)器2暂题，但當(dāng)用戶輸入' AAA '時(shí)，我們只需要查詢服務(wù)器1究珊。

我們可以在我們的trie服務(wù)器前面有一個(gè)負(fù)載均衡器薪者，它可以存儲(chǔ)這個(gè)映射并重定向流量。 此外剿涮，如果要從多個(gè)服務(wù)器查詢言津，要么需要在服務(wù)器端合并結(jié)果來計(jì)算總的最優(yōu)結(jié)果，要么讓客戶端這樣做取试。 如果我們希望在服務(wù)器端這樣做悬槽，我們需要在負(fù)載均衡器和trie服務(wù)器之間引入另一層服務(wù)器(我們稱它們?yōu)榫酆掀?。 這些服務(wù)器將聚合來自多個(gè)trie服務(wù)器的結(jié)果瞬浓，并將頂部的結(jié)果返回給客戶機(jī)初婆。

基于最大容量的分區(qū)仍然可以將我們引向熱點(diǎn)，例如，如果有很多以“cap”開頭的術(shù)語的查詢烟逊，那么持有它的服務(wù)器將比其他服務(wù)器有更高的負(fù)載渣窜。

c.根據(jù)詞的哈希進(jìn)行分區(qū):每個(gè)詞都會(huì)被傳遞給一個(gè)哈希函數(shù)，哈希函數(shù)會(huì)生成一個(gè)服務(wù)器號(hào)宪躯，我們會(huì)將詞存儲(chǔ)在該服務(wù)器上乔宿。 這將使我們的術(shù)語分布變得隨機(jī)，從而最小化熱點(diǎn)访雪。 這個(gè)方案的缺點(diǎn)是详瑞，為了找到一個(gè)詞的提前輸入建議，我們必須詢問所有的服務(wù)器臣缀，然后聚合結(jié)果坝橡。

客戶端優(yōu)化

• 客戶端應(yīng)該只在用戶沒有按任何鍵200ms的情況下嘗試敲擊服務(wù)器。

• 如果用戶一直在輸入精置，客戶端可以取消正在進(jìn)行的請(qǐng)求计寇。

• 最初，客戶端可以等待用戶輸入幾個(gè)字符脂倦。

• 客戶端可以從服務(wù)器預(yù)取一些數(shù)據(jù)番宁，以服務(wù)將來的請(qǐng)求。

  
  
  1649686067(1).png

• 客戶可以在本地存儲(chǔ)建議的最近歷史記錄赖阻。近期歷史有很高的重用率蝶押。

• 與服務(wù)器建立早期連接是最重要的因素之一。只要用戶打開搜索引擎網(wǎng)站火欧，客戶端就可以打開與服務(wù)器的連接棋电。因此，當(dāng)用戶鍵入第一個(gè)字符時(shí)苇侵，客戶端不會(huì)在建立連接上浪費(fèi)時(shí)間赶盔。

• 為了提高效率，服務(wù)器可以將部分緩存推送給cdn和互聯(lián)網(wǎng)服務(wù)提供商(isp)榆浓。

如何解決熱門事件

構(gòu)建另外一個(gè)系統(tǒng)招刨，專門處理近2小時(shí)的熱門搜索，這套系統(tǒng)因數(shù)據(jù)量小哀军，就實(shí)時(shí)的在內(nèi)存里維護(hù)2小時(shí)的熱門數(shù)據(jù)的trie。
熱門詞的發(fā)現(xiàn)：比較2小時(shí)內(nèi)打却，CNT明顯高于歷史的CNT的詞條杉适。把這些詞條存下來，構(gòu)建TRIE柳击，來反向匹配用戶請(qǐng)求猿推。
隨后用戶的請(qǐng)求會(huì)匯總2個(gè)系統(tǒng)的結(jié)果，一個(gè)是普通的搜索建議，另一個(gè)是熱門的搜索建議蹬叭。

follow up

你如何擴(kuò)展你的設(shè)計(jì)以支持多種語言?

為了支持其他非英語查詢藕咏，我們將Unicode字符存儲(chǔ)在trie節(jié)點(diǎn)中。

如果一個(gè)國(guó)家的搜索結(jié)果與其他國(guó)家不同呢?

在這種情況下秽五，我們可以為不同的region建立不同的trie孽查。 改善響應(yīng)時(shí)間，我們可以在cdn中存儲(chǔ)嘗試坦喘。