如何在分佈式計算機上分割非常大的單詞列表以便快速回答

Question

這更多的是一個架構問題，您將如何在規模上解決此問題。

假設您有一個數以百萬計的單詞列表，並且您需要搜索這些數以百萬計的單詞是否存在於數萬億字的語料庫中。

例如：

Word_List = 
["This", "a", "test", "of", "two", "words","what","words"] 

The_corpus = 
["This", "a", "test", "of", "two", "words","what","words","blah","blah2"] 

在上面的例子中，在the_corpus發現WORD_LIST所有的話，那麼我們的函數將返回true。請注意，「單詞」必須出現兩次。

我不知道我們可以通過Hadoop或Spark解決這個問題，通過在集羣上分發_corpus並編寫Mapper和Reducer來檢查這個單詞是否存在於語料庫中，但我無法弄清楚word_list是如何分佈的。我無法在主節點上保留word_list，因爲它太大。

Answer 1

您的任務的目標類似於常見的連接操作。有在實施它，你可以考慮某些東西：

1. 您可以使用基於WORD_LISTBloom過濾器，以減少潛在值的範圍在The_corpus收集
2. 對於小的收集通常分佈緩存用於使資源在所有任務節點上可用。在你的情況下，這應該是一個很好的空間命中，因爲它將被複制到實際任務將被執行的每個節點。爲了改善這一點，您可以將文件直接放入文件系統，並使用更大的複製因子（例如10（取決於羣集中節點的數量）），以提高其可用性。然後在您的任務中，您將能夠直接下載它，與分佈式緩存方法相比，這將顯着節省您的空間，但成本將是非本地讀取的帶寬。你可以玩這個來找到最佳的複製次數。

Answer 2

您可以在hadoop中的hdfs上添加word_list和corpus，它們將在所有節點上分發這兩個文件。現在你可以從hdfs中讀取這兩個文件。在您的映射器代碼中，您可以使用文件系統類從映射器代碼中的hdfs訪問word_list文件。您可以在Hadoop jar命令中將您的語料庫文件作爲輸入文件路徑提及。

Answer 3

word_list可以通過Hadoop's DistributedCache機制在節點間分佈。本質上，在初始作業配置階段指定了一個文件（-s），然後將其物理複製到將運行地圖任務的所有節點。然後每個地圖任務都可以訪問和使用這個文件的內容。

所以，你的榜樣任務是解決在Hadoop中以下列方式：WORD_LIST和語料庫放入HDFS;在作業中，word_list設置爲使用DistributedCache跨所有節點傳播;在映射階段WORD_LIST抵抗語料庫的特定分裂檢查（即，每個地圖任務具有WORD_LIST全額和64/128/... MB分割語料庫，其中64/128/...的通過用於語料庫文件）設置HDFS塊大小所定義;在減少階段需要發生聚集，例如，如果只是真/假應退還然後異徑輸入可能在WORD_LIST出現所有的字數：如果所有的話至少有一個occurence那麼真，否則爲False。

一般來說，這種任務被稱爲地圖端加入。查看一些示例代碼（使用DistributedCache），例如here。

Answer 4

猜你的問題是如何使用胼集羣節點間的一些方式分割集羣，以加快搜索。在這裏我概述了我會做什麼。

1. 排序語料庫和刪除重複，但添加了一些重複的每個單詞，諸如1，嗒嗒1，blah2 1，1，試驗1，這個1中，兩個1，什麼1，單詞2等，可能每行有一個詞可以簡化搜索過程或以某種打包形式加速IO。

2. 將語料庫劃分爲N個部分，並記錄每個部分中單詞的字母範圍，例如，部分1包含從a到aff的單詞，從afg到amp的part2等，將所有部分放在共享存儲上到每個節點。

3. 對word_list進行排序（並刪除重複項但添加每個單詞的計數）並將這些單詞劃分爲M個節點的M個組​​，並將每個組分配給一個節點進行搜索。

4. 對每個節點上的每個單詞執行二分搜索（搜索工具知道基於字母範圍搜索哪個語料庫部分）並報告爲真（如果所有單詞都在右側找到計數）或錯誤（只要一個單詞失敗就可以返回）。當然，這取決於你決定什麼纔算命中。可以爲搜索進行優化。例如，如果一個節點被分配到的組與三個單詞測試，這兩個和字測試部分X中，搜索字，這將只需要在一部分的右半部分進行的中間被發現X。