データは分散されており、コンピューティングもそれに追いつく必要があります。

[[221573]]

1. 背景

懸命な努力の末、Zhang Dapang と Bill は分散ファイルシステムである HDFS を実装することに成功しました。

(「HDFS の誕生」を参照)。

このシステムでは、大きなファイルをフラグメントに分割して異なるサーバーに保存し、各フラグメントに 2 つ以上の追加バックアップを作成できます。

ファイルは複数の部分に分割されますが、クライアント ソフトウェアの観点からは、クライアント ソフトウェアは依然として 1 つのファイルに対して操作を行い、HDFS がバックグラウンドで行っている「トリック」を認識しません。

そこで、Zhang Dapang は大量の Web ログ ファイルを HDFS に保存しました。

2. 並列コンピューティング

Zhang Dapang 氏は、まず HDFS を使用して、各 URL が何回訪問されたかをカウントするという小さな目標を達成することにしました。

当初、私たちはデータの量が多すぎるという厄介な問題に直面しました。 1 台のマシンですべてのファイルを読み取り、同じマシン上で処理する場合でも、処理速度は非常に遅くなります。

ビル師匠はこう語った。「プログラミングには『分割統治』という非常に重要な概念があり、それをここで使うことができるようになりました。」

「分割統治？」張大鵬は「すでにファイルを分割して別のマシンに置いているのではないですか？」と尋ねました。

「これは単なるデータです。今度はコンピューティング プログラムも分散化します。そして、コンピューティングをできるだけデータに近づけて、ネットワーク トラフィックのオーバーヘッドを削減します。たとえば、URL のアクセス数をカウントするという小さな目標の場合、このコンピューティング プログラムを各シャードが配置されているマシンに送信し、次のように各マシンで並列に計算を実行します。」

「並列計算なのに、結果がまとまりません。一体何の意味があるのでしょうか？」

「URL ごとにグループ化したらどうなるでしょうか?」ビルは言った。

(注: 正式な用語は group by ではなく shuffle です。)

「なるほど。こうすると、データが独立して並列計算できるようになりますね！」

張大鵬はビルから絵を描き続けた。

「はい、このようにしてコンピューティングは分散され、各プログラムは比較的シンプルになります。プログラム 1 の役割は、シャード内の URL を抽出して数値を記録することです。プログラム 2 の役割は、各 URL へのアクセス回数を累積することです。」ビルは言った。

3. 詳細な議論

「面白いですね。プログラムの並列実行を維持することが鍵のようです。プログラム 1 もプログラム 2 も内部状態を維持していないという現象に気づきました。入力に基づいて計算し、結果を出力する関数のようなものです。それだけです。」

「この方法によってのみ、絶対的な柔軟性が得られます。プログラム 1 のコピーは相互に依存しておらず、プログラム 2 も同様であるため、プログラム 1 とプログラム 2 を任意のマシンに展開して実行できます。」ビルは言った。

「また、プログラム 1 の出力では、各 URL へのアクセス回数が 1 として記録されるのはなぜですか? 最初にそのノードで同じ URL へのアクセス回数を合計できないのはなぜですか?」

「この単純なケースでは、まず合計を計算し、それを 2 番目のプログラムに送信して統計処理を続行できます。これで問題はありません。しかし、平均を計算する場合など、他のケースでは、最初に平均を計算することはできません。2 番目のプログラムに任せる必要があります。そうしないと、間違った結果になります。」

張大鵬は心の中で計算した。 3 つの数値 a=20、b=10、c = 30 があり、その平均が 20 であるとします。ただし、最初に a+b の平均を計算し、次に c の平均を計算すると、つまり ((a+b)/2 + c)/2 になると、結果は 22.5 となり、前の結果とは異なります。

「配布が面倒だとおっしゃいましたが、疑問があります。プログラムが実行を完了する前に終了したり、プログラムを実行しているマシンがダウンしたりした場合はどうなるのでしょうか。どうすればよいでしょうか。」

「悪魔は細部に潜んでいます。異常な分岐に遭遇すると、プログラムは非常に複雑になります。当然、各プログラムの状態を追跡する必要があります。使用できないことが判明した場合は、別のマシンで再実行する必要があります。意図的に複数のプログラムを開いて、それらを競争させることもできます。最も速く実行したプログラムの結果が最終結果になります。」

「ああ、やるべきことがたくさんあるので、それらに対処するための枠組みを考え出す必要があるようです！」太っちょ張はため息をついた。

「それは当然ですね。フレームワークとは何でしょうか。フレームワークは当然、優れたインフラストラクチャを提供し、反復作業をすべて実行して、ユーザーが作成したプログラムを可能な限りシンプルにします。私たちのフレームワークは、プログラム 1 とプログラム 2 をさまざまなマシンに分散して並列実行し、状態を監視します。いわゆるグループ化操作も処理する必要があるため、これはフレームワークである必要があります。MapReduce と呼んでもよいと思います。」

4. マップリデュース

「MapReduce？前回それについて教えてくれたよね？」

「そうですね、プログラム 1 を Mapper、プログラム 2 を Reducer と呼べば、全体が MapReduce になります」とビルは笑顔で言いました。

「なぜそんな変な名前なの？」太っちょ張は口を尖らせた。

「Map と Reduce はもともと関数型プログラミングの概念でした。いわゆるマップは次のようになります。」

張大鵬氏はこう語った。「これは単にデータセットに関数を適用し、それを別のデータセットに変換するだけではないでしょうか？」

「はい、広い意味では、マップはデータの変換であり、あるデータを別のデータに変換します。例に戻ると、プログラム 1 が受け取る入力は、実際にはログ レコードの行です。ログの各行について、プログラム 1 はそこから URL を抽出し、それを別の構造 (URL, 1) に変換して、後続の処理のために出力します。したがって、これもマップ操作です。」

「減らすとしたらどうですか？」

「Reduce は、関数と初期値を与え、リスト内の要素に対してその関数を毎回呼び出し、リストを常に「折りたたんで」最終的に値に変換します。最も単純な合計を例にとると、初期値が 0 でリストが [1,2,3,4] の場合、計算プロセスは次のようになります。

「なるほど。アイデアはシンプルですが、HDFS に適用してプログラムを並列実行できるようにすると非常に強力になります。」

【この記事は51CTOコラムニスト「Liu Xin」によるオリジナル記事です。転載する場合は著者のWeChat公開アカウントcoderisingを通じて許可を得てください]

この著者の他の記事を読むにはここをクリックしてください