トップ10の最も頻繁には、データがネットワーク

Question

全体に保存されている

ソース、URLを訪問した検索：がトップ10最も訪問されたURLを見つけ、Googleの面接の質問

コンピュータの大規模なネットワークを考えると、訪問したURLの各保持ログファイルを。

多くの大きい<string (url) -> int (visits)> mapsがあります。

< string (url) -> int (sum of visits among all distributed maps)を計算し、組み合わせマップのトップ10を取得します。

主な制約：マップがネットワーク経由で送信するには大きすぎます。 MapReduceを直接使用することはできません。

私は今、大規模な分散システム上でprocessiongを実行する必要があるこのタイプの質問に出くわしました。私は思う、または適切な答えを見つけることができません。

私が考えることができるのは、何らかの形でまたは他の方法で、与えられた制約に違反するブルートフォースです。

Answer 1

それは我々だけで、地図減らすの行動を模倣するので、あなたは質問の作者は、マップが作品を減らす方法を考えるたいヒントです直接を地図減らす使用することはできませんと言います。

1. 前処理：各（stringには、Rは、クラスタ内のサーバの数とする0,1,2からそれぞれ サーバ固有のIDを与え、...、R-1
2. （マップ） 、id） - タプルをID：hash(string) % Rのサーバに送信します。
3. （reduce）ステップ2が完了したら（単純な制御通信）、サーバごとに上位10個の文字列のうち(string,count)を生成します。これらのタプルはステップ2でこの特定のサーバーに送信されます。
4. （map）各サーバーは、上位10対1のすべてのサーバーを送信します（サーバー0にする）。それはうまくいくはずです、それらのレコードの10 * Rしかありません。
5. （削減）サーバー0は、ネットワーク上で上位10を生成します。

注：アルゴリズムと

• 問題、失敗のサーバーを処理しているフレームワークを使用していない 最もビッグデータアルゴリズムのように。 MapReduceは あなたの世話をします。
• 上記のアルゴリズムは、2段階のマップリダクションアルゴリズムに変換することができます。

Answer 2

アルゴリズムは周波数テーブル全体を送信する必要はありませんが、失敗する可能性があります。グローバルなトップ10がすべての個々のマシンリストの一番下にあるという単純なケースを作り出すことができます。

URIの頻度がZipfの法則に従っていると仮定すると、効果的な解決策を思いつくことができます。そのような解決策の1つが後に続く

各マシンはトップK要素を送信します。 Kは利用可能な帯域幅にのみ依存します。 1つのマスターマシンが周波数を集約し、10番目の最大周波数値 "V10"を見つけます（これは下限であることに注意してください。グローバルトップ10はすべてのマシンのトップKにないため、合計は不完全です）。

次のステップでは、すべてのマシンが、頻度がV10/M（Mはマシンの数）のURIのリストを送信します。そのようなすべての組合はすべての機械に返送されます。各マシンは、この特定のリストのために周波数を送信します。マスターはこのリストを上位10リストに集約します。