「.NET 開発基盤部会 Wiki」は、「Open棟梁Project」,「OSSコンソーシアム .NET開発基盤部会」によって運営されています。
目次 †
概要 †
分散処理（分散コンピューティング）とは、
- 複雑な計算などをネットワークを介して複数のコンピュータを利用して行うことで、
- スループットを上げようとする取り組み、またはそれを実現する為の仕組み。
詳細 †
- 基本的には1990年代までの並列データベースの技術に基づいた並列データ処理系
- ハードウェアの高性能化や新たな需要を踏まえ，その中核をなす技術は少しずつ進展を遂げつつある。
基礎 †
ざっくり、
- 並列化処理は
- 手続型言語ではなく宣言型言語で記述される。
- 宣言型言語では実行プランという形で最適化された処理が計算される。
みたいな話。
アーキテクチャ †
無共有型のアーキテクチャが主流である。
- 型
- 共有メモリ型（シェアード・メモリ）
- 共有ディスク型（シェアード・ディスク）
- 無共有型（シェアード・ナッシング）
- 単一ハードウェアコンポーネントにおけるレイテンシ低減の停滞のため、
複数のハードウェアコンポーネントを効率的に活用する方向にシフトしている。
- 複数のコモディティサーバを高速なネットワークで接続した無共有型のクラスタシステムが
昨今のビッグデータ解析においては，価格性能比の点から，後者が広く利用されつつある。
並列処理 †
- 問い合わせ間の並列性（Inter-query Parallelism）
複数の異なる問い合わせを並列に実行するときの並列性
- 問い合わせ内の並列性（Intra-query Parallelism）
1つの問い合わせを並列に実行可能な複数の
サブタスクに分解して実行するときの並列性
- オペレータ間の並列性（Inter-operator Parallelism）
問い合わせにおける複数の異なるオペレータを並列に実行するときの並列性
- パイプライン並列性（Pipelined Parallelism）
あるオペレータが出力するデータを
別のあるオペレータが入力する場合において，
これらのオペレータを並列に実行するときの並列性
- 独立並列性（Independent Parallelism）
データの依存関係がない複数の独立したオペレータを並列に実行するときの並列性
- オペレータ内の並列性（Intra-operator Parallelism）
1つのオペレータを並列実行可能な複数のサブタスクに分解して実行するときの並列性
- パーティション並列性（Partitioned Parallelism）
データを複数にパーティショニングし，
オペレータの複数のインスタンスが当該パーティションを
並列に読み出すことにより，オペレータ内の並列性を活用する。
※ SQL Serverの並列クエリはファイル・グループによるパーティション並列性になる。
データ分割 †
パーティション並列性のデータの分割方法には、主に次の3つの方法がある。
- ラウンドロビン分割（Round-Robin Partitioning）
均等に分散される。
- ハッシュ分割（Hash Partitioning）
均等に分散される。
- 範囲分割（Range Partitioning）
不均等だが、データが値でクラスタ化されており、
処理系が処理の効率化を図ることができる場合がある。
性能指標 †
並列処理の性能指標
- スケーラビリティ（Scalability）
以下の指標があるが、ビッグデータ系では、
スケールアップ（Scale-up）がより重要になる。
- スピードアップ（Speed-up）
ジョブを処理する計算資源をN倍に増やしたときに，
ジョブの処理時間がどの程度低下するか？
- スケールアップ（Scale-up）
ジョブを処理する計算資源をN倍に増やしたときに，
ジョブの仕事量（データ量）もN倍に増やしたときに，
ジョブの処理するための時間が同程度か？
- 線形なスケーラビリティ
理想的には線形なスケーラビリティを有することが望ましい。
- スピードアップ（Speed-up）では、
計算資源N倍で1/N時間になる場合。
- スケールアップ（Scale-up）では、（同じ処理時間で）
計算資源N倍で仕事量（データ量）もN倍になる場合。
アルゴリズム †
並列処理のオペレータとアルゴリズム
- 選択オペレータ
- スキャン（・アルゴリズム
- 索引スキャン（・アルゴリズム
- ソートマージ結合（アルゴリズム
- 並列化が可能（並列ソートマージ結合）
- 双方のソート済み結合キーで再パーティションして、結合。
- ソートマージ結合はハッシュ結合よりも低速
- ハッシュ結合（アルゴリズム
- 並列化が可能（並列ハッシュ結合）
- 片方の結合キーをハッシュに読み込み（再パーティションして）、結合。
- ハッシュ結合はソートマージ結合よりも高速
実行プランの選択 †
実行プランの列挙・見積・選択は、
「（問い合わせ）最適化」と呼ばれる。
- どのようなアルゴリズムを用いるか？
- 選択（Selection）のアルゴリズム
- 結合（Join）のアルゴリズム
- 集約（Aggregation）のアルゴリズム
永続性と一貫性 †
レプリケーションとロギングがある（RDBMSにもある）。
- 論理ロギング（Logical Logging）
- データを生成するオペレーション（命令）のみを二時記憶に保持
- RDBMSのトランザクション・ログ的なもの。
- 物理ロギング（Physical Logging）
- データイメージを（別の形式で）二時記憶に保持
- リラン可能バッチの中間状態のような状態と言える。
- RDBでは共有ディスクを使用しないクラスタで利用される。
- トレードオフ関係があるが、可用性の向上が耐障害性に繋がる。
- Eager or Lazy
データの追加や更新がいつレプリカに伝播するか？
・Eager：当該処理の確定後に伝播するか？
・Lazy：当該処理の確定前にも伝播してしまうか？
- Centralized or Distributed
データの追加や更新がどこを起点に発生するか？
・Centralized：中央のサーバ（マスタ）で行われる。
・Distributed：いずれのサーバかで行われる（ADのマルチマスタ的な）。
- Eager * Centralized
・[Eager] or Lazy
・Strong Consistencyの一貫性が得られる。
・追加や更新にかかる時間（レイテンシ）が長くなる。
・[Centralized] or Distributed
・メタデータの管理が簡潔になる。
・システム全体のスループットや耐障害性が低くなる。
- Lazy * Centralized
・Eager or [Lazy]
・Eventual Consistencyの一貫性
・追加や更新にかかる時間（レイテンシ）が短くなる。
・[Centralized] or Distributed
・メタデータの管理が簡潔になる。
・システム全体のスループットや耐障害性が低くなる。
- Eager * Distributed
・[Eager] or Lazy
・Strong Consistencyの一貫性が得られる。
・追加や更新にかかる時間（レイテンシ）が長くなる。
・Centralized or [Distributed]
・メタデータの管理が複雑になる。
・システム全体のスループットや耐障害性が高くなる。
- Lazy * Distributed
・Eager or [Lazy]
・Eventual Consistencyの一貫性
・追加や更新にかかる時間（レイテンシ）が短くなる。
・Centralized or [Distributed]
・メタデータの管理が複雑になる。
・システム全体のスループットや耐障害性が高くなる。
- Mutual Consistency
分散システムのCAP定理におけるCに相当するレプリカ間の値の一貫性
- Transaction Consistency
データベースにおけるACIDのIに相当するもの（分離レベル）
- Database Consistency
データベースにおけるACIDのCに相当するもの（整合性）
- Strong Consistency（Linearlizability）
当該データの書き込み後の当該データの読み出では、
書き込まれた当該データの値が必ず得られる。
Eagerは、Strong Consistencyを保証する。
- Eventual Consistency
当該データの書き込み後の当該データの読み出では、
書き込まれた当該データの値が「いつかは」必ず得られる。
Lazyは、Strong Consistencyを保証する。
コーディネーション †
複数のプロセス間において，協調して動作をする，または，同意を取るための技術
- 分散排他制御（Distributed Mutual Exclusion）
分散環境で
- 排他制御を行う（ロックを取る）。
- クリティカルセクションに入るプロセスを選択する。
- リーダ選挙（Election／Leader Election）
- ある特定の作業を行うためのリーダプロセスを選択する
- 分散排他制御は，ロックを取るリーダプロセスの選挙の特殊系とも見れる。
- グループ通信（Group Communication／Multicast）
- あるプロセスがほかの全プロセスにメッセージを送信すること。
- いわゆる，マルチキャスト。
- コンセンサス（Consensus）
- あるプロセスが提案者となり，他のプロセスが同意をして，全体で決定する。
- グループ通信とコンセンサスはほぼ同等のもの。
- アルゴリズム
- 2相コミット（Two-Phase Commit）
- 複数のプロセスをまたいだ分散トランザクションにおいて
原子性（Atomicity）を実現するための方法として広く用いられる。
- 2つのフェーズから構成される。
・フェーズ1：コーディネータがリソース・マネジャに対してPrepareメッセージを送る。
・フェーズ2：コーディネータがすべてのリソース・マネジャから応答を受け取ると，
全リソース・マネジャに当該分散トランザクションのCommit or Abortメッセージを送る。
- ZAB
- Zookeeperにおいて用いられているコンセンサスアルゴリズム
- 任意のプロセスがクラッシュし得る。
・ビザンチン故障（プロセスの動作において仮定をおかない故障）は想定しない。
・≒任意の動作を実行しない（要求に対して不正または一貫しない応答を返すさない）。
- メッセージの送信にかかる時間は有限だが上限がない。
すなわち，分散システムモデルにおける非同期システムを想定する。
- 複数のプロセス間においては、
固定的なマスタ／スレーブの関係は存在しない。
- FIFO ordering
・メッセージ送信順序でメッセージを受信する。
・プロセス毎の因果関係のみを保証する性質。
- Causal ordering
・因果関係が保たれる順序でメッセージを受信する。
・FIFO ordering前提＋αのプロセス間の因果関係も保証する性質
- Total ordering
すべてのプロセスにおいてメッセージの到達順序が同一であることを保証する性質。
分散処理 †
本項での処理系は
「分散システム技術を活用した、
データ処理専用の並列システム」
と言うことができる。
- HDFSの性質そのもの。
レプリケーション方式
- Centralizedのアプローチを採用。
- ファイルエントリはEager。
- データはLazy（追加はあるが更新はない）。
- Hadoop MapReduce?
ロギング方式
- 外部ソートの結果を用いて物理ロギングと見ることができる。
- MapReduce?処理の間の整列フェーズにおける結果データを二次記憶に書き、
Reduceフェーズが何らかの理由で失敗した場合は，再度Reduce処理をやり直せる。
- Spark
ロギング方式
- RDDと称されるデータの塊を生成する論理ロギングと見ることができる。
- データが失われた場合、前のデータに対して当該オペレーションを適用してデータを復旧する。
- HDFSの性質そのもの。
ラウンドロビン分割(HDFS)のパーティション並列性を活用
- Hadoop MapReduce?
- Map処理においては，並列スキャンを行う。
- 一種の並列ソートマージ結合処理フレームワーク的。
・通常はReduce側で並列ソートマージ結合を行う。
・Map側で並列ハッシュ結合を行うことも可能。
- Cloudera Impala / Presto
- Map処理においては，並列スキャンを行う。
- 結合にハッシュ結合を使用しパイプライン並列性を活用
- Spark
Hadoopに類したデータ処理系
- map()，filter()においては，並列スキャンを行う。
- 結合にハッシュ結合を使用しパイプライン並列性を活用
ストア †
データ・ストア、ディスクか？メモリか？
ディスク †
メモリ †
Apache Spark の Resilient Distributed Dataset (RDD)
その他 †
- NoSQL
SparkとCassandraなんて組み合わせもある模様。
処理 †
どのような処理を実行できるか？
分散（バッチ） †
得意とするストレージによってフレームワークが異なる感じ。
※ Hadoop MapReduceは他の分散エンジンの隆盛によってフェードアウト気味らしいが、
Hadoop や Hadoop Distributed File System (HDFS) は進化しつつあるらしい。
ストリーム †
- CEP（complex event processing）とも言う。
分散（バッチ） + ストリームみたいな組み合わせ。
目的 †
ビジネス上の目的の例。
意味付け †
前もって意味付けせずに生のまま蓄積できる。
- データ分析時にいろいろな意味付けを試してみる探索的なデータマイニングできる。
- 最新の統計理論をベースにゼロからプログラミングできる自由度をもっている。
データアナリストというよりデータサイエンティストに向いたアーキテクチャ
可視化 †
- 可視化が目的の場合、以下のような流れで処理を行う。
- ストリーム
- データ収集
- エンリッチメント
- 分散（バッチ）
- 蓄積
- 可視化
※ ディスクのデータをDWHにロードし、従来タイプのBIツール群を使うこともできる。
プロダクト †
分散（バッチ）系 †
HDFSを使ったビッグデータの分散（バッチ）処理のプロダクト。
ビッグデータの分散（バッチ）処理のプロダクト。
ストリーム系 †
ビッグデータのストリーム処理のプロダクト
ビッグデータのストリーム処理のプロダクト
※ Apache Stormとの違いはリンク先参照を。
データ収集・格納 †
- データ生成元 → HadoopのHDFS部の課題
- スクラッチ開発が必要なので、OSSのプロダクトが存在する。
非構造化データ
非構造化データ
時系列データ
業務データベースからのデータ
EAI/ETL系のデータフロー・オーケストレーション・ツールだが、
ビッグデータのコンテキストでデータ収集＋エンリッチメント役割を担う。
処理性能を重視したメッセージキュー
- データをロストし難い仕組みを備える。
- 複数台のマシンでクラスタを構成
- 分散処理により高いスループットを発揮
目的別 †
分散（バッチ）系 †
- 繰返しの多い処理や、複雑な処理が苦手
- 複雑な処理は、MapReduce?ジョブの組み合わせで実現
- MapReduce?ジョブの都度、ディスクの読み書きが発生
- 複数台のサーバのメモリ/CPU/ディスクを効率よく利用
- 複雑な処理を実行できる。
- SQL（汎用化）
- 機械学習
- ストリーム
- ライブラリ、API
ストリーム系 †
... †
Elasticsearchの推奨構成
- ビッグデータの可視化のプロダクト群
- データはドキュメントで、全文検索処理を行う。
- ストレージにHadoopを使えるので分散処理系に分類
Kibana †
Logsatsh †
Beats †
参考 †
＠IT †
- Amazon EMRで構築するApache Spark超入門
Think IT †
Qiita †
NTTデータ †
システム技術本部 †
先端技術株式会社 †
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
