Hadoopモデリング座談会#3

第2回のレポートはこちら

概要

イベント名	Hadoopを中心とした分散環境での開発方法論・モデリング・設計手法等についての座談会(第3回)
URL	http://atnd.org/events/9098
日時	2010/11/19 18:30 - 21:00
場所	スター研修センター神田3F

佐藤一郎先生(NII) @ichiro_satoh 分散環境の過去・現在・未来

モバイルエージェント、まずはデモから

デモテキストエディタ
- 2つのPCを用意、片方でエディタ起動
- 文字を適当に書きこんでから「Go」ボタンを押すと、もう片方に「移動」する
- テキストデータだけを通信しているのではなく、プログラムごと移動している
デモライフゲーム
- エディタと同様に移動のデモ

モバイルエージェント(MA)の仕組み

JavaVMとランタイムの上で動くエージェントがノード間を移動する
データを移動しないのでネットワーク負荷を大幅に低減することができる
デモ grep
- grep は「1行づつ」とってきてはマッチ処理を行う
- 相手先に grep 投げて処理してもらえば速い、という発想
デモ mapreduce(ワードカウント)
- いつも通りのワードカウント
- 相手先にワードカウントプログラムを投げ、その結果を受け取る

我々はプロトコルに縛られている

我々が本当にやりたいのはプログラム間の通信でしょ？
- なのに現代の通信は TCP/IP に縛られている
- RMI とか RPC は呼び出し側は待ってるので無駄
相手がプロトコルしゃべれないなら渡してしまえばいい
- さきほどのエージェントがプロトコルをしゃべれればいいということ
デモチャット
- 相手先にチャットエージェント渡してチャットする
- 相手側はプロトコルを最初から知っている必要はない

並行、並列、分散

並行
- 論理的に複数同時実行
- con-currency ラテン語で「現在がたくさんある」
並列
- parallel
- 物理的に複数同時実行
- マルチコアCPUとか
分散
- 論理的に複数のものが同時的に動作する
- コンピュータが複数ある感じ

オブジェクト指向の歴史

Simula
- Algolにシミュレーションの記述性を追加
- 1962-1967ほど
- オブジェクト、クラス、インヘリタンスなどOOに必要な概念は全てここから始まった
  - その中で今回重要なのはコルーチンと並行性
Smalltalk
- 並行性の概念が抜かれた
- アラン・ケイの貢献なんてメッセージパッシングの概念ぐらいじゃない？
C++
- これも並行性の概念がないOO
Java
- Smalltalk,C++の流れをくんで並行性がなかったが、後からマルチスレッドとか追加したからえらいことに
並行オブジェクト
- 並行性の流れを継承、SmalltalkやC++とは別の流れ
- Actorとか
Scala,Erlang
- Actorの概念を取り入れている
- 2つに分かれた流れが一つになった感じ

並行オブジェクト

オブジェクト
- コード + データ
- 自分の中で自分を記述できる
並行オブジェクト
- コード + データ + プロセッサ
- 自律性 automony
- 自分の中に仮想的なプロセッサ
- すなわち、仮想的なコンピュータ
- これが組み合わさると分散処理になる

Sync method call

オブジェクトAがオブジェクトBを呼び出す
Bが処理を終えるまでAはサスペンド
Bは処理が完了したら結果をAに返して終了する
Aは結果を受け取ったら処理を続行する

このスキームから脱却するのが今回の目的。

One Message Passing

オブジェクトAがオブジェクトBを呼び出す
AもBもそのまま処理を継続

Javaとか。明示的にスレッド起動
プログラムが見えにくくなる

Async return

オブジェクトAがオブジェクトBを呼び出す
Bが処理を終えるまでAはサスペンド
Bは処理が完了したら結果をAに返し、そのまま処理を続行する
Aは結果を受け取ったら処理を続行する

あるメソッド内で return 文を書いたあとに処理を記述するとかできる

Future オブジェクト

呼び出し側(Callee)と呼び出される側(Called)のどちらかが結果の授受専用オブジェクトを作成
Callee が作成する場合は以下の通り

1. Callee が Future を作成
2. Future は Callee に自身の id を返す
3. Callee は Future の id を投げて Called に処理を要求する
4. Called は処理を実行し、結果を Future に渡す

Called が作成する場合は以下の通り

1. Callee が Called に処理を要求する
2. Called が Future を作成
3. Future は Called に自身の id を返す
4. Called は Callee に Future の id を渡す
5. Called は処理を実行し、結果を Future に渡す
6. Callee は Future から結果を取り出す

Actor モデル

1970年代のモデル
コード、データ、メッセージキューからなる
全てのメッセージを受け取る
- ガードなし通信
各オブジェクトはたかだか1つのメッセージしか処理できない
非同期1方向メッセージ

CSP モデル

プロセスは特定のメッセージだけ受け取る
- ガードつき通信
同期1方向メッセージ

ガードつき通信とガードなし通信

ガードなし通信は全てのメッセージを受け取り、ガードつき通信は一部のメッセージを受けとる
メールで例えるとガードつき通信はスパムフィルタがある状態
ガードつきの方がプログラム的には楽
並行処理においては Actor モデルのが楽

なぜ Actor モデルのが並行処理を書きやすいのか？

1オブジェクト1スレッドはマルチスレッドに比べて処理効率が悪い
- だから以前はマルチスレッドが採用された
しかし1オブジェクト1スレッドは逐次処理だからきやすい
- Scala, Erlang

まとめ

並行オブジェクトの考えはそのまま分散システムに考えを持っていける

質疑応答

Q. どのリソースを移動できればMAと言えるのか？
- 研究の世界では色々行われてるが、実用的にはヒープのみ移動できればよくスタックは必要ない
- mobility transparency
Q. ライブマイグレーション(LM)との違いは？
- LMは移動先でも同じものしか見えない。MAは移動先でも別のものを見せたり使うことができる
Q. ソフトウェアトランザクションメモリはどうよ？
- 「本当に実現できれば」いいんじゃない？
Q. 10年前、なぜエージェントは流行らなかったか？
- モデリングとして適切ではなかったのでは？　プログラミングの実装と離れてたり。

萩原さん @masayh クラウドのデータ処理の原則

イントロ

ヨーロッパ環境データマップ Eye on Earth
- SQL Azure がバックエンド

データの分類と扱い方

データ
- RDBかファイルか追記型ファイルか
KVS
- 非正規化
- データ量が少なければいいが、大きいと従量課金のクラウドで死ぬ

JOINの話

分散データベースのJOIN
- Nested Loop
- Sort Merge
- Semi Join
- Hash Semi Join
2つのテーブルL,RのうちRが小さいとき、Rの側はメモリに置いて処理
JOIN の最適化
- Semi Join
- Bool Filter

データの偏り

プロセッサやノードの数が増えるに連れ、性能に関する支配的な問題は変わっていく
- 少ないときは初期化のオーバヘッド
- 増えてくると、相互作用のオーバヘッドが支配的に
- 最終的にはデータの偏りのオーバヘッドになる
データの分割方法
- ハッシュ→パーティション→バケット→チューニング済みバケット(動的に変更したりとか)
ヒストグラム使ってデータの偏りを最適化したりする
Virtual Processor Partitioning
- プロセッサの数以上にバケットを分ける

RDBMS と MapReduce

RDBMS の構文解析
- タプルを入力とし、Scan→Join→Insert の流れ
- この流れを取り出したのが MapReduce

Dryad

数値計算のフローなどもコンパイラが最適化してくれる
(ここで Dryad LING コーディング例)

座談会

データの並列処理は実績が既にたくさんあるので参考にすべし
デザインパターンは発展途上
- インフラが不安定だとパターンも変わる。が、必要なので作るしかない
性能向上の変遷
- 中の処理の効率化から、データや問題の分割をいかにうまくやるかというものに
- これはフレーム問題。自動処理は難しい
- ただのチューニングをしていたのではいつか取り残される
Q. モバイルエージェントにおける共有領域はどうすればいい？
- 答えはない。が、人間のオペレーションがヒントになる
業務分析などはシーケンシャルにやっていて、我々の持っている道具は最上位のものですらパラレルではない。この状態をどうすればいいか？

感想

モバイルエージェントと電子の妖精

佐藤先生は冒頭で「今回 Hadoop の話はあまりしませんが」と言いましたが、今回の話を聞いて Hadoop と関係がないなんて誰も思わなかったことでしょう。MAの話を聞いて MapReduce のジョブ投入だと多くの人が気づいたはずです。しかし、浅はかなことに私はそこで満足してしまっていました。

座談会の後佐藤先生は日記でこう書いていました。
個別記事へのリンクがないので、2010/11/19 の記事より引用します。

なぜモバイルエージェントでMapReduceを実装したのかという、MapReduceもHadoopも閉じたシステムだから。Googleは膨大なデータを集め、膨大なサーバでMapReduceを振り回しています。それ以外が対抗しようとしたら、データとサーバをシェアするしかないのです。しかし、MapReduceもHadoopも、クラスタ内で閉じたシステムとして構成することを前提にしており、他のクラスタのデータやサーバを共有する仕組みがない。GoogleのMapReduceについてはGoogle自身を閉じたシステムなので、それでもいいわけですが、HadoopについてはHadoop クラスタ同士で、データやサーバを共有する仕掛けを提供しない限り、MapReduceもどきからは抜け出せないし、少なくてもHadoopを使う側もGoogleに勝てない。それでは複数Hadoop クラスタ間でデータやサーバをシェアするにどうすればいいのかを考えると、モバイルエージェントそのものではなくても、近いアプローチになるはず。それが今日のメインメッセージのひとつでした。モバイルエージェントとMapReduceの組み合わせが一見、不自然なので、絶対に質問されると思っていたのですがね。

オープンソースコミュニティ、バザール開発、ウィキノミクスモデルの力を知っていながらこの観点を見落としていたことはただただ恥じるばかりです。
実現可能性とか、実際の実現方法とかこの場ではどうでもいい話で、これがもし実現できるのなら、人類は単なるデータの塊であるwebの世界全体を巨大な計算クラスタにできるわけです。とても恐ろしくて、とても面白そうだと思いませんか？
私は講演中、「モバイルエージェントって、SFとかに出てきた、コンピュータネットワーク上だけで生きている妖精とかみたいだな」なんて思っていたのですが、実際に世界中のコンピュータを駆け巡り仕事をこなし、人類に恩恵を与えてくれる存在ができるのだとしたらそれこそまさに電子の妖精なのかもしれません。

あと余談ですが、S4で学んだばかりの Actor モデルが出てきたのはちょっとうれしかったです。

木の精霊は蜂や豚と戯れる

萩原さんの話は、その多くが Hive で既に実装されている話でした。
例えばデータの偏りなどは、Hive では GROUP BY などでそれを解決するオプションがあります*1。
パーティションやバケットなども Hive における基本コンセプトの一つです。
Pig と似てるよねなんて言っている人もいたので、Pig も大体同等機能を備えてるのでしょう。
そして Hive/Pig も、少し動かせば分かりますが、多段の MapReduce を組み立ててくれます。
つまり DAG を自動で組んでくれるわけです。
性能の差こそあれ、Dryad も Hive も Pig も同じような方向性なのでしょうね。

非シーケンシャルの業務分析

真っ先に思いついたのが、チケット駆動開発でした。
タスクは全てチケットに落とし、プロジェクトメンバはアサインされたチケットをこなしていく。チケットにない作業はやらない。
メンバをジョブ処理のエージェントと見立てて、チケットを「取りに行く」のではなくチケットのある場所に「作業しに行く」と見立てれば何か見えてきそうな気がしたのですが自分の頭ではそこ止まりでした。
とはいえ、アジャイル開発だのスクラムだの、新しいプロジェクト管理の手法というのはシーケンシャルなフローからは一歩先に行っているとは思いますし、そういった部分の知見を分散処理の技法に生かせないものでしょうかと考えました。

私はどちらもど素人なので、見当違いも甚だしい妄言なのかもしれませんが。