分散処理のバックアップ(No.26)

「.NET 開発基盤部会 Wiki」は、「Open棟梁Project」,「OSSコンソーシアム .NET開発基盤部会」によって運営されています。

戻る

目次 †

↑

概要 †

分散処理（分散コンピューティング）とは、
- 複雑な計算などをネットワークを介して複数のコンピュータを利用して行うことで、
- スループットを上げようとする取り組み、またはそれを実現する為の仕組み。

また、分散処理（ソリューション）は、
- RDBでは大き過ぎるか、複雑すぎるデータを処理するように設計されている。
- 以下ケースに分散処理の分散処理（アーキテクチャ）が適合する。
  - 大量のデータを格納して処理する
  - 非構造化データを変換する
  - ストリーミングデータを処理する

↑

詳細 †

基本的には1990年代までの並列データベースの技術に基づいた並列データ処理系
ハードウェアの高性能化や新たな需要を踏まえ，その中核をなす技術は少しずつ進展を遂げつつある。
以下のコンテンツをサマリすると、
- RDBの並列処理の様なモノ（基礎は同じ）を、
- 異なる目的（セグメント＆ターゲット）で実装している感じ。

↑

基礎 †

ざっくり、

分散処理の起点は、並列化。

並列化処理は
- 手続型言語ではなく宣言型言語で記述される。
- 宣言型言語では実行プランという形で最適化された処理が計算される。

みたいな話。

↑

アーキテクチャ †

無共有型のアーキテクチャが主流である。

型
- 共有メモリ型（シェアード・メモリ）
- 共有ディスク型（シェアード・ディスク）
- 無共有型（シェアード・ナッシング）

理由

単一ハードウェアコンポーネントにおけるレイテンシ低減の停滞のため、
複数のハードウェアコンポーネントを効率的に活用する方向にシフトしている。

複数のコモディティサーバを高速なネットワークで接続した無共有型のクラスタシステムが
昨今のビッグデータ解析においては，価格性能比の点から，後者が広く利用されつつある。

↑

並列処理 †

問い合わせ間の並列性（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では共有ディスクを使用しないクラスタで利用される。

トレードオフ関係があるが、可用性の向上が耐障害性に繋がる。

次の2軸で整理できる。

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]
　・メタデータの管理が複雑になる。
　・システム全体のスループットや耐障害性が高くなる。

前提知識

一貫性(Consistency)の種類。

Mutual Consistency
分散システムのCAP定理におけるCに相当するレプリカ間の値の一貫性

Transaction Consistency
データベースにおけるACIDのIに相当するもの（分離レベル）

Database Consistency
データベースにおけるACIDのCに相当するもの（整合性）

さまざまなレプリカ間の一貫性

Strict Consistency

Strong Consistency（Linearlizability）
当該データの書き込み⁠後の当該データの読み出では、
書き込まれた当該データの値が必ず得られる。
Eagerは、Strong Consistencyを保証する。

Sequential Consistency

Causal 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において用いられているコンセンサスアルゴリズム
- Proposerが常に1つのみ存在し、提案のFIFO / Causal / Total orderingを保証。
- ProposerはFollowerに対して、2PCと類似の方法で任意の値を提案（送信）。
- 定足数が同意があればProposerは当該提案をコミットする。

PAXOS
- ZABと類似の現在，最も広く使われているものの1つ。
- Proposerは複数の場合であっても動作する。
  ・汎用性が高い
  ・ZABと比較する複雑な仕組
  ・提案のFIFO / Causal orderingを保証しない。

前提知識

コーディネーションの前提

任意のプロセスがクラッシュし得る。
・ビザンチン故障（プロセスの動作において仮定をおかない故障）は想定しない。
・≒任意の動作を実行しない（要求に対して不正または一貫しない応答を返すさない）。

メッセージの送信にかかる時間は有限だが上限がない。
すなわち，分散システムモデルにおける非同期システムを想定する。

複数のプロセス間においては、
固定的なマスタ / スレーブの関係は存在しない。

分散システムにおける順序

FIFO ordering
・メッセージ送信順序でメッセージを受信する。
・プロセス毎の因果関係のみを保証する性質。

Causal ordering
・因果関係が保たれる順序でメッセージを受信する。
・FIFO ordering前提＋αのプロセス間の因果関係も保証する性質

Total ordering
すべてのプロセスにおいてメッセージの到達順序が同一であることを保証する性質。

↑

分散処理 †

本項での処理系は

「⁠分散システム技術を活用した、
データ処理専用の並列システム」

と言うことができる。

永続性と一貫性

HDFS
レプリケーション方式
- Centralizedのアプローチを採用。
- ファイルエントリはEager。
- データはLazy（追加はあるが更新はない）。

RDD
レプリケーション方式
- ...

Hadoop MapReduce?
ロギング方式
- 外部ソートの結果を用いて物理ロギングと見ることができる。
- MapReduce?処理の間の整列フェーズにおける結果データを二次記憶に書き、
  Reduceフェーズが何らかの理由で失敗した場合は，再度Reduce処理をやり直せる。

Spark
ロギング方式
- RDDと称されるデータの塊を生成する論理ロギングと見ることができる。
- データが失われた場合、前のデータに対して当該オペレーションを適用してデータを復旧する。

並列性

HDFS
ラウンドロビン分割(HDFS)のパーティション並列性を活用

RDD
...。

Hadoop MapReduce?
- Map処理においては，並列スキャンを行う。
- 一種の並列ソートマージ結合処理フレームワーク的。
  ・通常はReduce側で並列ソートマージ結合を行う。
  ・Map側で並列ハッシュ結合を行うことも可能。

Cloudera Impala / Presto
- Map処理においては，並列スキャンを行う。
- 結合にハッシュ結合を使用しパイプライン並列性を活用

Spark
Hadoopに類したデータ処理系
- map()，filter()においては，並列スキャンを行う。
- 結合にハッシュ結合を使用しパイプライン並列性を活用

↑

ストア †

データ・ストア、ディスクか？メモリか？

↑

ディスク †

Hadoop の Hadoop Distributed File System (HDFS)

HDFSベース
- Apache HBase
- , etc.

↑

メモリ †

Apache Spark の Resilient Distributed Dataset (RDD)

RDDベース
- ...

↑

その他 †

ストレージ

NoSQL
SparkとCassandraなんて組み合わせもある模様。

↑

処理 †

どのような処理を実行できるか？

↑

目的 †

ビジネス上の目的の例。

↑

意味付け †

前もって意味付けせずに生のまま蓄積できる。

データ分析時にいろいろな意味付けを試してみる探索的なデータマイニングできる。
最新の統計理論をベースにゼロからプログラミングできる自由度をもっている。

データアナリストというよりデータサイエンティストに向いたアーキテクチャ

↑

可視化 †

可視化が目的の場合、以下のような流れで処理を行う。
1. ストリーム
  1. データ収集
  2. エンリッチメント
2. 分散（バッチ）
  1. 蓄積
  2. 可視化

以下のようなプロダクトがある。
- Elasticsearch ( + Kibana)
- BIツール

※ ディスクのデータをDWHにロードし、従来タイプのBIツール群を使うこともできる。

↑

データ解析 †

↑

機械学習 †

↑

目的別 †

↑

分散（バッチ）系 †

↑

ストリーム系 †

↑

データ収集・格納 †

↑

プロダクト †

↑

分散（バッチ）系 †

↑

ストリーム系 †

↑

データ収集・格納 †

↑

Elastic Stack †

Elasticsearchの推奨構成

ビッグデータの可視化のプロダクト群
データはドキュメントで、全文検索処理を行う。
ストレージにHadoopを使えるので分散処理系に分類

↑

参考 †

分散コンピューティング - Wikipedia

分散処理に入門してみた（Hadoop + Spark） | キャスレーコンサルティング株式会社
https://www.casleyconsulting.co.jp/blog/engineer/150/

↑

＠IT †

Database Watch（2016年3月版） Sparkは“誰”に例えられる？
多様化と進化を続ける「Hadoop」、人気急上昇「Spark」
https://www.atmarkit.co.jp/ait/articles/1603/07/news002.html

Amazon EMRで構築するApache Spark超入門
- （1）Apache Sparkとは何か――使い方や基礎知識を徹底解説
  https://www.atmarkit.co.jp/ait/articles/1608/24/news014.html
- （2）Spark 2.0の回帰分析アプリをScalaのSBTで実装し、EMRで実行
  https://www.atmarkit.co.jp/ait/articles/1609/27/news018.html

↑