每當您開始在Google上輸入搜索內容時，您都會獲得推薦列表，並且鍵入的字母越多，推薦的準確性就越高。如果您像我一樣，您總是想知道這是如何工作的-是存儲倒排索引還是其他內容？

這裏適合的數據結構是Trie。

系統要求

考慮到Google的規模，我們需要牢記的因素是延遲，一致性和可用性。一個理想的延遲應該是非常低的，給人/每個信你可以鍵入改變的建議。接下來，系統需要一直可用。但是，這裏可以包含一致性。每次鍵入內容時，它都會更改以前存儲的查詢的頻率，這會影響建議。此處稍有延遲是可以的，最終的一致性也將起作用。

方法1

特里表示一個單詞爲樹，每個字母爲節點，下一個字母爲子節點，依此類推。Google還會以Trie的形式存儲每個單詞/句子。在這裏考慮，父節點是“ h”，其子節點是“ a”，然後是“ r”，依此類推。每個節點可以有26個子節點。現在，每個節點還可以存儲搜索到的每個字母的頻率。

例如，節點“ h”存儲搜索頻率“ h”，其子節點“ a”存儲搜索頻率“ ha”，依此類推，現在，如果我們要顯示前N條建議，請說鍵入“ h”，建議應該顯示“ harry potter”或“ harry styles”。然後，我們需要將父節點中的所有建議排序到頻率的每個級別並進行顯示，這意味着掃描數TB的數據，並且因爲延遲是我們的目標，所以這種掃描方法將行不通。

方法＃2

爲了使這種方法更有效，我們可以在每個節點上存儲更多數據以及搜索頻率。讓我們在它下面的子樹中的每個節點上存儲前N個查詢。這意味着節點“ h”將存儲“哈里·波特”，“哈雷·戴維森”等查詢。如果將樹遍歷到“ harl”（即鍵入“ harl”），則節點“ l”將具有諸如“ harley davidson”，“ harley quinn”之類的查詢。

與前一種方法相比，這種方法更好，因爲讀取效率很高。每當節點的頻率更新時，我們都會從該節點回溯到其父節點，直到到達根節點爲止。對於每個父級，我們檢查當前查詢是否是前N個查詢的一部分。如果是，則將相應的頻率替換爲更新的頻率。如果不是，則檢查當前查詢的頻率是否足夠高以成爲前N個查詢的一部分。

如果是這樣，我們用頻率更新前N個。儘管這種方法有效，但確實會影響我們的讀取效率-每次執行寫入/更新操作時，我們都需要在節點上加一個鎖，這樣用戶就不會得到過時的值，但是如果我們考慮最終的一致性，則可能沒什麼大問題。用戶可能會暫時獲取過時的值，但是最終它將保持一致。儘管如此，我們將研究這種方法的擴展。

方法3

作爲先前方法的擴展，我們可以離線存儲數據。我們可以將查詢的哈希圖存儲到其頻率，一旦頻率達到設置的閾值，便可以將其映射到服務器。

縮放比例

現在，將不會只有一臺大型服務器來存儲所有PB級數據。我們會垂直擴展生活–有更好的方法。我們可以通過前綴在各種服務器上分發數據（分片）。例如，前綴“ a”，“ aa”，“ aab”等將在服務器＃1上等等。我們可以使用負載均衡器來保留帶有服務器編號的前綴映射。

但是考慮到這一點，與字母“ a”相比，某些具有“ x”，“ xa”，“ yy”等數據的服務器將具有較少的流量，因此，可以對每個服務器進行閾值檢查；如果負載如果流量超過該流量，則可以在其他分片之間分發數據。

如果您擔心單點故障，則可能有許多服務器充當負載平衡器，因此，如果任何負載平衡器發生故障，則將其替換爲另一個。您可以使用ZooKeepers持續運行狀況檢查負載平衡器並採取相應的措施。

相關文章