データ指向アプリケーションデザイン | 第10章 バッチ処理

Tags:

• Database
• NoSQL
• Data
• RDB

発表者: キム・ジョンス、パク・スミン

発表資料

バッチ処理の代替

MapReduce

• 長所: 分散ファイルシステム上で、かなり単純で明快に抽象化されたモデルである。
• 短所: 複雑な演算は非常に難しい。

MapReduceの中間状態の具現化

バッチ処理ワークフローで、各タスクのoutput（中間状態）を分散ファイルシステムにファイルとして保存（具現化）しておく方法である。

（複雑な演算を複数のMapReduceに分割して処理する。）

• 分散ファイルシステム: タスクのoutputをファイルとして保存する仕組み。
  • このファイルは他のタスクのinputとして使われる。主にタスク間でデータを渡す用途である。
• 中間状態: このようなファイルとして保存されている状態。
  • 複雑なワークフローでは非常に多くの中間状態が存在する。
• 具現化: 中間状態をファイルとして保存する過程。
  • 要求が来たときに結果を生成するのではなく、あらかじめ特定の演算結果を生成しておくこと。

Unixパイプと比べた短所:

• 先行作業が完了しなければ後続作業を開始できない。
  • Unixパイプでは同時に作業が進む。
    • データの生成と同時に消費が行われる。
  • ワークフロー全体の実行時間が遅くなる。
• マッパーの重複
  • マッパーはリデューサーが生成したファイルを読み、パーティショニングとソートを行う。
    • 不要なI/Oが発生する。
    • リデューサーにマッパーの機能も持たせることで解決できる。
• 分散ファイルシステムのすべてのマシンに中間状態ファイルの複製が発生する。
  • 中間状態ファイルは一時データであるにもかかわらず、分散ファイルシステムを使うことで複製という過度なコストが発生する。

データフローエンジン（Dataflow Engine）

MapReduceの問題を解決するために、分散バッチ処理演算を実行するエンジンが登場した。

データの流れを明示的にモデル化する。

• Spark: フレームワーク
• Tez: 軽量ライブラリ
• Flink: フレームワーク

フレームワーク: 独自のネットワーク通信層、スケジューラ、APIなどを備える。

https://trends.google.com/trends/explore?cat=32&q=Spark,Tez,Flink

特徴:

• ワークフローを独立した下位作業に分けず、1つの作業として扱う。
• MapReduceのように、単一スレッドでユーザー定義関数を呼び出し、レコードを1つずつ処理する。
• 入力データをパーティショニングして並列処理する。
• ネットワークコピーによって、ある関数のoutputが別の関数のinputとして渡される。

演算子:

• データ処理に使われる各種関数。

MapReduceモデルと比べた長所:

• ソートなどの高コストな作業は、必要な場合にだけ実行できる。
  • MapReduceでは、基本的にmapとreduceの間で常にソートが発生する。
• 局所性の最適化が可能である。
  • ワークフローが明示的なので、どのデータがどの時点で必要かを把握できる。
  • 関数間のデータ受け渡しをネットワークコピーではなくメモリ共有で行える。これによりネットワークI/Oを減らせる。
• 中間状態はローカルディスクに保存する。I/O消費を減らせる。
  • HDFS（Hadoop Distributed File System）に保存する場合、複数サーバーへの複製が必要になる。
• 演算子はinputが発生するとすぐに実行される。
  • 先行関数全体の終了を待つ必要がない。
• 演算子を実行するたびにJVMを起動しなくてもよい。
  • MapReduceでは各タスクごとに新しいJVMを起動する。

データフローエンジンはMapReduceのワークフローと同じ演算を実装でき、複数の最適化によって一般に実行速度がはるかに速い。
演算子はmapとreduceを一般化したものなので、MapReduceのワークフローは大きな変更なしにデータフローへ簡単に移行できる。移行前に互換性を確認すること。

耐障害性

MapReduceはすべての中間状態を具現化するため、耐障害性（耐久性）を容易に確保できる。
データフローエンジンはHDFSに中間状態を具現化しないため、別の方法を使う。HDFSを使わないという意味ではない。元データはHDFSにある。

• ローカルにinputデータが残っていれば再計算する。なければHDFSから元データを取得して計算する。

再計算のために演算を追跡する。

• どの入力パーティションを使ったか、どの演算子を使ったかを追跡しなければならない。
• SparkはRDD（Resilient Distributed Dataset）抽象化を使う。
  • RDD: 複数のデータ要素を集めたimmutableな分散コレクション。
• Flinkは演算子の状態をチェックポイントとして残す。

再計算時には冪等性が保証されなければならない。

冪等性を保証するために注意すべき事項:

• データ検索などでハッシュテーブルを使う場合、ハッシュテーブルは特定の順序を保証しない。
• 演算ロジックが乱数に依存する場合、乱数が必要なら固定シードを使うなどして乱数を制御する。
• システム時刻や外部データを使う場合、冪等性を保証できなくする原因を取り除く。

ただし、中間データのサイズが小さい場合や演算がCPUリソースを多く使う場合は、再計算よりも中間データを生成するほうが効果的なことがある。

具現化に関する議論

内容の要約:

• 先行作業の完了を待つ必要がない。パイプライン方式で実行できる。
• すべての中間状態をHDFSに保存しなくてもよい。

グラフと反復処理

グラフデータモデルに対するバッチ処理の必要性が高まっている。

• PageRank: Webページの人気度を測定するアルゴリズム。

データフローエンジンでは、データ自体は典型的なリレーショナルタプルで構成される。ある演算子から別の演算子へ向かうデータフローはグラフとして構成される。

• 一般には演算子を有向非巡回グラフとして配置する。
• 「データフロー」という名前のため、グラフではないかのような誤解を招くことがある。

データはリレーショナルタプル（辺と頂点）として構成できるため、アルゴリズムを反復的な形で実装できる。

• MapReduceでも実装できるが非効率である。
• MapReduceはアルゴリズムの反復的な性質を考慮しない。
  • データを一回限りで処理する。
  • 例: 「ある条件を満たすまでそのタスクを繰り返す」といった形式を自然に実装できない。

Pregel処理モデル

バッチグラフ処理を最適化する方法として、BSP（Bulk Synchronous Parallel）演算モデルが広く使われる。

BSPの実装:

• Apache Giraph
• Spark GraphX
• Flink Gelly API

BSPはPregelモデルとも呼ばれる。GoogleのPregel論文でグラフ処理方法論として紹介され、広く普及した。

Pregel = グラフ並列/分散処理フレームワーク。

• 大規模なグラフを扱うことは非常に難しい。最適なアルゴリズムを選んでも、processing costが指数的に増加するのが一般的である。
• グラフの分散処理のために使われる。
• Pregel自体だけでも内容が非常に広範なため、Pregelの詳細説明と本の該当内容は省略する。

高水準APIと言語

分散バッチ処理エンジンの発展:

• 数万台のマシンで構成されたクラスタで、PB（ペタバイト、1PB = 1,000TB）のデータを保存し処理するのに十分で堅牢になった。
• 技術が成熟し、技術で解決できる問題の範囲を広げることに注力するようになった。

SparkとFlinkも独自の高水準データフローAPIを持っている。

• 高水準APIにより、実装する演算のコード量を減らせる。
• 対話的な利用もサポートし、コードの動作をすぐ確認できる。

結論: 高水準APIを使うことでシステムの生産性を高め、作業をより効率的に実行できる。

宣言型クエリ言語への移行

結合が必要な演算では、結合を実行するコードを書くよりも、リレーショナル演算子として結合を表現するほうが、フレームワークが結合に使う適切なアルゴリズムを自動的に決定できるという利点がある。RDBのjoinに似ている。

Hive、Spark、Flinkはこのようなクエリオプティマイザを内蔵している。

• ユーザーはさまざまな結合アルゴリズムをすべて知る必要も、どのアルゴリズムを使うか悩む必要もない。
• 宣言的な方法により、optimizerが最適な実行方法を決定する。
• MapReduceの場合、ユーザーが直接コードを書けるという利点がある。ただし、CPUリソースのオーバーヘッドなどの短所もある。MapReduceとデータフローエンジンそれぞれの特徴として理解しよう。

多様な分野を支援するための特殊化

標準化された処理パターンが繰り返し現れる共通ケースは多い。そのため、再利用可能な共通ビルディングブロックを実装することは重要である。

統計学や数値アルゴリズムの分野でも、バッチ処理の重要性が高まっている。

• 統計学や数値アルゴリズムの分野は、分類や推薦システムのような機械学習アプリケーションを構築するために必要である。

上記の分野で再利用可能な実装を提供する技術:

• Mahout: MapReduce、Spark、Flinkで実行されるさまざまな機械学習用アルゴリズム実装を持つ。
• MADlib: リレーショナルMPP（Massively Parallel Processing）データベースに機械学習機能を追加できるオープンソースライブラリ。
• k近傍法（k-nearest neighbor）アルゴリズム: 多次元空間で、与えられたアイテムに近いアイテムを探す一種の類似度検索アルゴリズム。
  • 遺伝子解析アルゴリズムで重要に使われる。

バッチ処理システムは、組み込み機能と高水準の宣言的演算子の両方を持つため、広範な領域で必要とされるアルゴリズムを分散実行するために使われる。