Skip to content

DNET_DistributedProcessing

Jump to bottom
nishi_74322014 edited this page Sep 11, 2026 · 1 revision

分散処理

概要

コンピューティング（計算）

分散処理とは、

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

ソリューション（解決）

また、分散処理は、

  • 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の並列クエリはファイル・グループによるパーティション並列性になる
（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（Linearizability）
        当該データの書き込み後の当該データの読み出しでは、
        書き込まれた当該データの値が必ず得られる。
        Eagerは、Strong Consistencyを保証する。

      • Sequential Consistency

      • Causal Consistency

      • Eventual Consistency
        当該データの書き込み後の当該データの読み出しでは、
        書き込まれた当該データの値が「いつかは」必ず得られる。
        Lazyは、Eventual Consistencyを保証する。

移行メモ（正誤）: 元ページの Eventual Consistency の説明が
「Lazyは、Strong Consistencyを保証する。」となっていたが、
直前の Strong Consistency の説明と矛盾するため「Eventual Consistency」とした。
また「Linearlizability」は「Linearizability」の綴り誤りと判断し修正した。

コーディネーション

複数のプロセス間において、協調して動作をする、または、同意を取るための技術

  • 分類

    • 分散排他制御（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処理の間の整列フェーズにおける結果データを二次記憶に書き、
        Reduceフェーズが何らかの理由で失敗した場合は、再度Reduce処理をやり直せる。

    • Spark（Apache Spark）
      ロギング方式

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

  • 並列性

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

    • RDD
      ...。

    • Hadoop

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

    • Cloudera Impala / Presto

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

    • Spark（Apache Spark）
      Hadoop に類したデータ処理系

      • map()、filter()においては、並列スキャンを行う。
      • 結合にハッシュ結合を使用しパイプライン並列性を活用

ストア

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

ディスク

  • Hadoop の Hadoop Distributed File System (HDFS)
    （Hadoopの該当節を参照）

  • HDFSベース

メモリ

  • Apache Spark の Resilient Distributed Dataset (RDD)
    （Apache Sparkの該当節を参照）

  • RDDベース

    • ...

その他のストア

処理

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

分散（バッチ）系

分散処理：分散（バッチ）系の該当節を参照。

ストリーム系

分散処理：ストリーム系の該当節を参照。

データ収集・格納系

分散処理：データ収集・格納系の該当節を参照。

目的

ビジネス上の目的の例。

意味付け

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

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

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

可視化

※ ディスクのデータをDWH
（ビジネス インテリジェンス（BI）の該当節を参照）にロードし、
従来タイプのBIツール群を使うこともできる。

データ解析

機械学習

リンク

目的別

分散（バッチ）系（目的別）

分散処理：分散（バッチ）系の該当節を参照。

ストリーム系（目的別）

分散処理：ストリーム系の該当節を参照。

データ収集・格納（目的別）

分散処理：データ収集・格納系の該当節を参照。

プロダクト

分散（バッチ）系（プロダクト）

分散処理：分散（バッチ）系の該当節を参照。

ストリーム系（プロダクト）

分散処理：ストリーム系の該当節を参照。

データ収集・格納（プロダクト）

分散処理：データ収集・格納系の該当節を参照。

Elastic Stack

Elasticsearchの推奨構成

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

データ・パイプライン

データ収集・格納系
→ ストリーム系
→ 分散（バッチ）系

みたいな組み合わせ。

参考

＠IT

Think IT

NTTデータ

システム技術本部

先端技術株式会社

Tags: 移行, 分散処理, ビッグデータ, Hadoop, Spark, 開発基盤

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

NetDevInfraWiki

マイクロソフト系技術情報 Wiki
Open 棟梁 Wiki

（未着手）

開発基盤部会 Wiki

移行管理: DONE ／ TODO

Clone this wiki locally