介紹

如今，我們幾乎在每個網站上都看到一個搜索欄。搜索欄使我們能夠快速找到我們需要的內容。

讓我們舉個例子。想象一下，如果 YouTube 沒有提供搜索欄，我們如何在數百萬個視頻中找到特定的視頻，這些視頻多年來都已上傳到 YouTube？用戶僅通過滾動瀏覽很難找到他們想要的內容。

在每個搜索欄背後，都有一個搜索系統。

需求

• 可用性：系統應對用戶高度可用。• 可擴展性：系統應能夠隨着數據量的增加而擴展。換句話說，它應能夠索引大量數據。• 快速搜索大數據：無論用戶搜索多少內容，他們都應該能夠快速獲取結果。

核心概念

倒排索引

索引 — 是組織和操作數據的過程，旨在促進快速和準確的信息檢索。

倒排索引 — 是一種類似於哈希映射的數據結構，它使用文檔 - 詞術矩陣。它不是將完整文檔存儲，而是將文檔拆分爲單個詞語。然後，文檔 - 詞術矩陣識別唯一的詞語，並丟棄頻繁出現的詞語，如 “to”、“they”、“the”、“is” 等等。

圖 1.0：倒排索引

“映射” 列中的每個條目都包括三個列表：

• 詞語出現的文檔列表。• 統計詞語在每個文檔中出現的頻率的列表。• 指出詞語在每個文檔中的位置的二維列表。一個詞語可以在同一文檔中出現多次，因此使用二維列表。

對於提取的每個詞語，我們要麼在倒排索引中添加新行，要麼在該詞語已經在倒排索引中有條目的情況下更新現有條目。同樣，在刪除文檔時，我們需要處理，找到已刪除文檔詞彙在倒排索引中的條目，然後相應地更新倒排索引。

設計

在添加文檔或運行搜索查詢時，需要將倒排索引加載到主內存中。爲了效率，必須將倒排索引的大部分內容適應於機器的 RAM 中。

這意味着我們必須將大量數據加載到 RAM 中。不是增加單臺機器的資源來索引十億頁，而是要轉向分佈式系統，利用並行化的力量。

圖 2.0：分佈式搜索系統的高級設計

• 索引器從分佈式存儲中獲取文檔，並使用 MapReduce 進行索引，MapReduce 運行在分佈式的普通機器集羣上。索引器使用分佈式數據處理系統（例如 MapReduce）進行並行和分佈式索引構建。構建的索引表存儲在分佈式存儲中。• 使用分佈式存儲來存儲文檔和索引。• 用戶在搜索欄中輸入包含多個詞語的搜索字符串。• 搜索器解析搜索字符串，從存儲在分佈式存儲中的索引中搜索映射，並將最匹配的結果返回給用戶。

數據分區

爲了實現成本效益，我們在索引中使用了衆多小節點。這個過程要求我們對輸入數據（文檔）進行分區或拆分。

圖 3.0：在多個普通機器集羣中以並行方式進行分佈式索引和搜索

索引

• 集羣管理器將輸入文檔集分成 N 個分區，其中 N 等於上圖中的 2。每個分區的大小由集羣管理器決定，考慮到數據的大小、計算、內存限制和集羣中的節點數量。由於各種原因，可能不是所有節點都可用。集羣管理器通過定期心跳監視每個節點的健康狀況。要將文檔分配給 N 個分區之一，可以使用哈希函數。• 分區後，集羣管理器在集羣中的 N 個節點上同時運行所有 N 個分區的索引算法。每個索引過程都會生成一個小型的倒排索引，存儲在節點的本地存儲中。這樣，我們生成了 N 個小型倒排索引，而不是一個大的倒排索引。

搜索

• 在搜索階段，當用戶查詢進來時，我們在存儲在節點本地存儲中的每個小型倒排索引上運行並行搜索，生成 N 個查詢。• 每個小型倒排索引的搜索結果都是與查詢詞語匹配的映射列表（我們假設用戶查詢是單個詞語 / 術語）。合併器聚合這些映射列表。• 在

聚合映射列表後，合併器根據每個文檔中詞語的頻率對文檔列表進行排序。

• 排序後的文檔列表以升序順序返回給用戶。

複製

我們爲生成分配分區的索引節點創建副本。

通常，三個副本足夠。三個副本意味着三個節點託管相同的分區並生成索引。三個節點中的一個成爲主節點，而其他兩個是副本。同一分區將轉發到所有三個副本。我們假設每個副本都會獨立計算索引，這會導致資源的低效使用。與在副本上重新計算索引不同，我們只在主節點上計算倒排索引。接下來，我們將倒排索引（二進制文件）傳輸到副本。這種方法的主要好處是避免了在副本上使用重複的 CPU 和內存來進行索引。

圖 4.0：由索引節點生成的索引存儲在分佈式存儲中，參與搜索的節點從分佈式存儲中讀取索引以爲用戶的查詢生成結果

索引和搜索之間有很強的分離，而沒有索引延遲的負面影響。由於這種分離，索引不會影響搜索可擴展性，反之亦然。此外，與在副本上重新計算索引不同，我們只需複製索引文件。

在硬件故障的情況下，會添加新的搜索器或索引器機器，並從分佈式存儲中檢索數據的副本。

評估

可用性

數據在分佈式存儲中跨多個區域進行復制，使索引和搜索的跨區域部署更加容易。因此，如果一個地方發生故障，我們可以在另一個集羣中處理請求。

索引是離線執行的，不在用戶的關鍵路徑上。我們不需要同步複製索引操作。無需在將新索引複製到響應搜索查詢之前等待。這使得搜索對用戶可用。

可擴展性

分區是搜索系統擴展的重要組成部分。當增加分區的數量並向索引和搜索集羣添加更多節點時，可以在數據索引和查詢方面實現擴展。

索引和搜索過程之間的強分離有助於索引和搜索獨立和動態地擴展。

大數據快速搜索

我們利用了多個節點，每個節點在較小的倒排索引上並行執行搜索查詢。然後，將每個搜索節點的結果合併並返回給用戶。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/ldKMzTxwzIEVGsHPk1DnVw