如果你用谷歌或者百度進(jìn)行搜索就會(huì)發(fā)現(xiàn)，當(dāng)你在這些搜索引擎的框內(nèi)鍵入某些內(nèi)容時(shí)，它們可以根據(jù)輸入的內(nèi)容智能展現(xiàn)輸入提示建議。本文作者正是帶著這樣的想法實(shí)現(xiàn)了一個(gè)具備類(lèi)似功能的系統(tǒng)。

本文將展現(xiàn)如何設(shè)計(jì)一個(gè)大規(guī)模的自動(dòng)完成輸入提示建議的系統(tǒng)，就像 google 搜索一樣，整個(gè)設(shè)計(jì)是用 Docker Compose 實(shí)現(xiàn)的，可以在這里找到源代碼：https://github.com/lopespm/autocomplete

開(kāi)發(fā)者手?jǐn)]類(lèi)谷歌搜索關(guān)鍵字智能匹配功能系統(tǒng)

系統(tǒng)要求

最終的系統(tǒng)需要適應(yīng)類(lèi)似 Google 的搜索規(guī)模，即每天約 50 億次搜索，也就是每秒鐘約 5.8 萬(wàn)次查詢(xún)。我們可以預(yù)期這些搜索中有 20% ，也就是每天有 10 億次查詢(xún)。

如果我們選擇為這 10 億條查詢(xún)建立索引的話，平均每個(gè)查詢(xún)有 15 個(gè)字符【2】，每個(gè)字符有 2 個(gè)字節(jié)（我們將只支持英語(yǔ)設(shè)置），這反映在托管這些查詢(xún)所需的存儲(chǔ)空間大約為 30 GB。

功能要求

根據(jù)用戶(hù)輸入（前綴）獲取熱門(mén)的短語(yǔ)建議列表。
通過(guò)加權(quán)按給定短語(yǔ) / 查詢(xún)的頻率和相似度對(duì)建議進(jìn)行排序【3】。

主要的兩個(gè) API 是：

top-phrases(prefix) ：返回給定前綴的熱門(mén)短語(yǔ)列表。
collect-phrase(phrase) ：將搜索到的短語(yǔ)提交給系統(tǒng)。稍后，匯編器將使用這個(gè)短語(yǔ)來(lái)構(gòu)建數(shù)據(jù)結(jié)構(gòu)，這個(gè)數(shù)據(jù)結(jié)構(gòu)將前綴映射到熱門(mén)短語(yǔ)列表。

非功能性需求

高可用；
性能：熱門(mén)短語(yǔ)的響應(yīng)時(shí)間應(yīng)快于用戶(hù)的輸入速度（<200ms）；
可擴(kuò)展性：系統(tǒng)應(yīng)該能夠適應(yīng)大量請(qǐng)求，同時(shí)保持性能；
持久性：即使存在硬件故障或發(fā)生系統(tǒng)崩潰，先前搜索的短語(yǔ)（對(duì)于給定的時(shí)間跨度）也應(yīng)該可用。

設(shè)計(jì)與實(shí)現(xiàn)

高級(jí)設(shè)計(jì)

兩個(gè)主要的子系統(tǒng)是：

分發(fā)服務(wù)器：負(fù)責(zé)處理用戶(hù)對(duì)給定前綴的熱門(mén)短語(yǔ)的請(qǐng)求。
匯編器：負(fù)責(zé)收集用戶(hù)搜索并將它們匯編成數(shù)據(jù)結(jié)構(gòu)，稍后由分發(fā)服務(wù)器使用。

詳細(xì)設(shè)計(jì)

這個(gè)實(shí)現(xiàn)使用了現(xiàn)成的組件，如 Kafka（消息代理）、Hadoop（MapReduce 和分布式文件系統(tǒng)）、redis（分布式緩存）和 Nginx（負(fù)載平衡、網(wǎng)關(guān)、反向代理）等，但是也有用 Python 構(gòu)建的定制服務(wù)，即 Trie 分發(fā)和構(gòu)建服務(wù)，Trie 數(shù)據(jù)結(jié)構(gòu)也是定制的。

這個(gè)實(shí)現(xiàn)中的后端服務(wù)被構(gòu)建為可持續(xù)使用，不需要太多編排。例如，如果一個(gè)活動(dòng)后端主機(jī)停止響應(yīng)，則它對(duì)應(yīng)的臨時(shí)節(jié)點(diǎn) znode 注冊(cè)表最終會(huì)消失，而另一個(gè)備用后端節(jié)點(diǎn)將嘗試通過(guò) zookeeper 上的臨時(shí)節(jié)點(diǎn) znode 聲明該位置來(lái)取代它的位置。

Trie：基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)

分發(fā)服務(wù)器使用并提供給分發(fā)服務(wù)器的數(shù)據(jù)結(jié)構(gòu)是 Trie （譯注：又稱(chēng)前綴樹(shù)、字典樹(shù)，是一種有序樹(shù)，用于保存關(guān)聯(lián)數(shù)據(jù)），其每個(gè)前綴節(jié)點(diǎn)都有一個(gè)熱門(mén)短語(yǔ)列表。熱門(mén)短語(yǔ)是使用享元模式（flyweight pattern）進(jìn)行引用的，這意味著短語(yǔ)的字符串文字僅存儲(chǔ)一次。每個(gè)前綴節(jié)點(diǎn)都有一個(gè)熱門(mén)短語(yǔ)列表，這是對(duì)字符串文本的引用列表。

正如我們之前看到的，我們將需要大約 30 GB 來(lái)索引 10 億個(gè)查詢(xún)，這大約是上述 Trie 存儲(chǔ) 10 億個(gè)查詢(xún)所需的內(nèi)存。由于我們希望將 Trie 保存在內(nèi)存中，以便為給定的查詢(xún)啟用快速查找時(shí)間，因此，我們將 Trie 劃分為多個(gè) Trie，每個(gè) Trie 在不同的機(jī)器上進(jìn)行。這一做法減輕了任何給定機(jī)器上的內(nèi)存負(fù)載。

為了提高可用性，托管這些 Trie 的服務(wù)也將具有多個(gè)副本。為了提高持久性，Trie 的序列化版本將在分布式文件系統(tǒng)（HDFS）中可用，并且可以通過(guò) MapReduce 作業(yè)以一種可預(yù)測(cè)的、確定性的方式重新構(gòu)建。

信息流

匯編器：收集數(shù)據(jù)并匯編 Trie

1、客戶(hù)端通過(guò) http://localhost:80/search?phrase="a user query" 將搜索到的短語(yǔ)提交到網(wǎng)關(guān)：

2、由于搜索服務(wù)器不在此實(shí)現(xiàn)的范圍內(nèi)，網(wǎng)關(guān)通過(guò) http://assembler.collector-load-balancer:6000/collect-phrase?phrase="a user query" 直接將搜索短語(yǔ)發(fā)送到收集器的負(fù)載均衡器：

3、收集器的負(fù)載均衡器通過(guò) http://assembler.collector:7000/collect-phrase?phrase="a user query" 將請(qǐng)求轉(zhuǎn)發(fā)到其中一個(gè)收集器后端：

4、收集器后端向消息代理（Kafka）發(fā)送短語(yǔ)主題的消息。關(guān)鍵和價(jià)值在于短語(yǔ)本身【4】。

5、Kafka Connect HDFS Connector 匯編器。kafka-connect 將短語(yǔ)主題中的消息轉(zhuǎn)儲(chǔ)到 /phrases/1_sink/phrases/{30 minute window timestamp} 【5】文件夾【6】中。

6、觸發(fā) MapReduce 作業(yè)【7】：通過(guò)加權(quán)每個(gè)短語(yǔ)的新近度和頻率，它們將搜索的短語(yǔ)減少到一個(gè)單獨(dú)的 HDFS 文件中【8】。

根據(jù)當(dāng)前時(shí)間生成一個(gè) TARGET_ID ，例如： TARGET_ID=20200807_1517 。
第一個(gè) MapReduce 作業(yè)針對(duì) K【9】最近的 /phrases/1_sink/phrases/{30 minute window timestamp 文件夾執(zhí)行，并為這些文件夾中的每一個(gè)賦予一個(gè)基本權(quán)重（越近，則基本權(quán)重越高）。這個(gè)作業(yè)還將計(jì)算給定文件夾中相同短語(yǔ)的權(quán)重。生成的文件將存儲(chǔ)在 /phrases/2_with_weight/2_with_weight/{TARGET_ID} 文件夾中。
第二個(gè) MapReduce 作業(yè)將把給定短語(yǔ)的所有權(quán)重從 /phrases/2_with_weight/2_with_weight/{TARGET_ID} 匯總到 /phrases/3_with_weight_merged/{TARGET_ID} 。
第三個(gè) MapReduce 作業(yè)將通過(guò)遞減權(quán)重對(duì)條目進(jìn)行排序，并將它們通過(guò)單個(gè) Reducer，以生成單個(gè)文件。此文件放在中 /phrases/4_with_weight_ordered/{TARGET_ID} 。
zookeper znode /phrases/assembler/last_built_target 被設(shè)置為 TARGET_ID 。

7、Trie Builder 服務(wù)正在監(jiān)聽(tīng) / phrases/assembler/last_built_target zonde 中的更改，它基于 /phrases/4_with_weight_ordered/{TARGET_ID} 文件為每個(gè)分區(qū)【10】構(gòu)建 Trie。例如，一個(gè) Trie 可以覆蓋前綴直到 mod，另一個(gè)從 mod 到 racke，還有一個(gè)從 racke 開(kāi)始。

每個(gè) Trie 被序列化并寫(xiě)入 /phrases/5_tries/{TARGET_ID}/{PARTITION} HDFS 文件（例如， /phrases/5_tries/20200807_1517/mod|racke ），而 zookeeper znode /phrases/distributor/{TARGET_ID}/partitions/{PARTITION}/trie_data_hdfs_path 被設(shè)置為前面提到的 HDFS 文件路徑。
該服務(wù)將 zookeper znode /phrases/distributor/next_target 設(shè)置為 TARGET_ID 。

將 Trie 轉(zhuǎn)移到分發(fā)服務(wù)器子系統(tǒng)

1、分發(fā)服務(wù)器后端可以處于活動(dòng)模式（服務(wù)請(qǐng)求）或備用模式。處于備用模式的節(jié)點(diǎn)將獲取最近的 Trie，將它們加載到內(nèi)存中，并將自己標(biāo)記為準(zhǔn)備接管活動(dòng)位置。具體如下：

a. 備用節(jié)點(diǎn)在監(jiān)聽(tīng)對(duì) znode /phrases/distributor/next_target 的更改時(shí)，檢測(cè)其修改并為每個(gè)每個(gè)分區(qū)創(chuàng)建一個(gè) 臨時(shí)的順序節(jié)點(diǎn) znode，一次一個(gè)，位于 /phrases/distributor/{TARGET_ID}/partitions/{PARTITION}/nodes/ znode。如果創(chuàng)建的 znode 是第一個(gè) R znode 之一（R 是每個(gè)分區(qū)的副本節(jié)點(diǎn)數(shù)【11】），繼續(xù)執(zhí)行下一步。否則，從這個(gè)分區(qū)移除 znode 并嘗試加入下一個(gè)分區(qū)。

b. 備用后端節(jié)點(diǎn)從 /phrases/5_tries/{TARGET_ID}/{PARTITION} 獲取序列話的 Trie 文件，并開(kāi)始將 Trie 加載到內(nèi)存中。

c. 當(dāng) Trie 加載到內(nèi)存時(shí)，備用后端節(jié)點(diǎn)通過(guò)將 /phrases/distributor/{TARGET_ID}/partitions/{PARTITION}/nodes/{CREATED_ZNODE} znode 設(shè)置為后端主機(jī)名，將自己標(biāo)記為就緒。

2、Trie 后端應(yīng)用程序服務(wù)輪詢(xún) /phrases/distributor/{TARGET_ID}/ sub-znode （ TARGET_ID 是 /phrases/distributor/next_target 中定義的節(jié)點(diǎn)），并檢查是否所有分區(qū)的所有節(jié)點(diǎn)都標(biāo)記為就緒。

a. 如果它們都為下一個(gè) TARGET_ID 做好了準(zhǔn)備，那么服務(wù)將在單個(gè)事務(wù)中將 /phrases/distributor/next_target znode 的值更改為空，并將 /phrases/distributor/current_target znode 設(shè)置為新的 TARGET_ID 。通過(guò)這一步驟，所有標(biāo)記為就緒的備用后端節(jié)點(diǎn)現(xiàn)在都將處于活動(dòng)狀態(tài)，并將用于以下分發(fā)服務(wù)器請(qǐng)求。

分發(fā)服務(wù)器：處理熱門(mén)短語(yǔ)的請(qǐng)求

當(dāng)分發(fā)服務(wù)器的后端節(jié)點(diǎn)處于活動(dòng)狀態(tài)并加載了它們各自的嘗試后，我們就可以開(kāi)始為給定的前綴提供熱門(mén)短語(yǔ)請(qǐng)求：

1、客戶(hù)端通過(guò) http://localhost:80/top-phrases?prefix="some prefix" 向網(wǎng)關(guān)請(qǐng)求給定前綴的熱門(mén)短語(yǔ)。

2、網(wǎng)關(guān)通過(guò) http://distributor.load-balancer:5000/top-phrases?prefix="some prefix" 將此請(qǐng)求發(fā)送到分發(fā)服務(wù)器的負(fù)載均衡器。

、3 負(fù)載均衡器通過(guò) http://distributor.frontend:8000/top-phrases?prefix="some prefix" 將請(qǐng)求轉(zhuǎn)發(fā)到其中一個(gè)前端。

4、前端服務(wù)器處理請(qǐng)求：

a. 前端服務(wù)檢查分布式緩存（redis）是否有這個(gè)前綴的條目【12】。如果是，則返回這些緩存的熱門(mén)短語(yǔ)，否則，繼續(xù)執(zhí)行下一步。

b. 前端服務(wù)從 zookeeper（ /phrases/distributor/{TARGET_ID}/partitions/ znode）獲取當(dāng)前 TARGET_ID 的分區(qū)，并選擇與提供的前綴匹配的分區(qū)。

c. 前端服務(wù)從 /phrases/distributor/{TARGET_ID}/partitions/{PARTITION}/nodes/ znode 中隨機(jī)選擇一個(gè) znode，并獲取其主機(jī)名。

d. 前端服務(wù)通過(guò) http://{BACKEND_HOSTNAME}:8001/top-phrases="some prefix" 從選定的后端請(qǐng)求熱門(mén)短語(yǔ)。

e. 后端使用其相應(yīng)的加載 Trie 返回給定前綴的熱門(mén)短語(yǔ)列表。

f. 前端服務(wù)將熱門(mén)短語(yǔ)列表插入到分布式緩存（緩存模式）中，并返回?zé)衢T(mén)短語(yǔ)。

熱門(mén)短語(yǔ)“響應(yīng)”向用戶(hù)提供。

Zookeeper Znode 結(jié)構(gòu)

注意：當(dāng)系統(tǒng)運(yùn)行時(shí)，請(qǐng)使用 shell 命令 docker exec -it zookeeper ./bin/zkCli.sh 查看當(dāng)前 Zookeeper 的 znode。

phrasesdistributorassemblerlast_built_target - 設(shè)置為 TARGET_IDdistributorcurrent_target - 設(shè)置為 TARGET_IDnext_target - 設(shè)置為 TARGET_ID{TARGET_ID} - 例如，20200728_2241partitions|{partition 1 end}trie_data_hdfs_path - 保存序列化的 Trie 的 HDFS 路徑nodes000000000000000000010000000002…{partition 2 start}|{partition 2 end} * …{partition 3 start}| * …

HDFS 文件夾結(jié)構(gòu)

注意：當(dāng)系統(tǒng)運(yùn)行時(shí)，在瀏覽器中訪問(wèn) http://localhost:9870/explorer.html 來(lái)瀏覽當(dāng)前的 HDFS 文件和文件夾。

phrases1_sink - 搜索到的短語(yǔ)被轉(zhuǎn)儲(chǔ)到此處，分成 30 分鐘的時(shí)間塊。{e.g 20200728_2230}{e.g 20200728_2300}2_with_weight - 應(yīng)用初始權(quán)重的短語(yǔ)，除以時(shí)間塊。{TARGET_ID}3_with_weight_merged - 所有時(shí)間塊的合并：具有最終權(quán)重的短語(yǔ)。{TARGET_ID}4_with_weight_ordered - 按權(quán)重遞減順序排列的單個(gè)短語(yǔ)文件。{TARGET_ID}5_tries - 序列化 Trie 的存儲(chǔ)。{TARGET_ID}|{partition 1 end}{partition 2 start}|{partition 2 end}{partition 3 start}|

客戶(hù)端交互

你可以通過(guò)在瀏覽器中訪問(wèn) http://localhost 與系統(tǒng)進(jìn)行交互。當(dāng)你輸入一個(gè)查詢(xún)時(shí)，系統(tǒng)會(huì)提供搜索建議，可以通過(guò)提交更多搜索來(lái)輸入更多查詢(xún)或短語(yǔ)到系統(tǒng)中。

源代碼

你可以在 https://github.com/lopespm/autocomplete 上獲得完整的源代碼。

尾注

【1】因?yàn)檫@個(gè)實(shí)現(xiàn)的主要目標(biāo)是以簡(jiǎn)單的方式構(gòu)建和共享系統(tǒng)，所以使用 Docker compose 代替了像 Kubernetes 或 Docker Swarm 這樣的容器編排工具。

【2】搜索查詢(xún)的平均長(zhǎng)度為 2.4 個(gè)詞，英語(yǔ)中的平均詞長(zhǎng)為 4.7 個(gè)字符。

【3】在本文中， 短語(yǔ) 和 查詢(xún) 是可以互換使用。不過(guò)，在系統(tǒng)內(nèi)部中，只使用 短語(yǔ) 這一術(shù)語(yǔ)。

【4】在這個(gè)實(shí)現(xiàn)中，為清楚起見(jiàn)，只使用了代理的一個(gè)實(shí)例。但是，對(duì)于大量的傳入請(qǐng)求，最好將該主題分為多個(gè)實(shí)例（消息將根據(jù) 短語(yǔ) 鍵進(jìn)行分區(qū)），以便分配負(fù)載。

【5】 ** /phrases/1_sink/phrases/{30 minute window timestamp} 文件夾 ：例如，假設(shè)消息 A[time: 19h02m] [time: 19h25m]，C[time: 19h40m]，消息 A 和 B 將放入文件夾 /phrases/1_sink/phrases/20200807_1900，而消息 C 將被放入文件夾 /phrases/1_sink/phrases/20200807_1930。

【6】在將這些消息傳遞給 Hadoop 之前，我們還可以將它們預(yù)先聚合到另一個(gè)主題中（使用 Kafka Streams）。

【7】為清楚起見(jiàn)，在這個(gè)實(shí)現(xiàn)中，MapReduce 作業(yè)是通過(guò) make do_mapreduce_tasks 手動(dòng)觸發(fā)的，但是在生產(chǎn)環(huán)境中，它們可以通過(guò) cron job 每 30 分鐘觸發(fā)一次。

【8】可以添加一個(gè)額外的 MapReduce 來(lái)將 /phrases/1_sink/phrases/ 文件夾聚合為更大的時(shí)間 timespan 聚合（如 1 天，5 周，10 天等）。

【9】可在 assembler/hadoop/mapreduce-tasks/do_tasks.sh 中通過(guò)變量 MAX_NUMBER_OF_INPUT_FOLDERS 進(jìn)行配置。

【10】分區(qū)在 assembler/trie-builder/triebuilder.py 中定義。

【11】每個(gè)分區(qū)的副本節(jié)點(diǎn)數(shù)是通過(guò) docker-compose.yml 中的環(huán)境變量 NUMBER_NODES_PER_PARTITION 配置的。

【12】在這個(gè)實(shí)現(xiàn)中，默認(rèn)情況下分布式緩存是禁用的，因此，對(duì)于首次使用這個(gè)代碼庫(kù)的人來(lái)說(shuō)，可以更清楚地了解每個(gè)更新 / 步驟中發(fā)生了什么。分布式緩存可以通過(guò) docker-compose.yml 中的環(huán)境變量 DISTRIBUTED_CACHE_ENABLED 來(lái)啟用。

原文鏈接：

https://lopespm.github.io/2020/08/03/implementation-autocomplete-system-design.html