分散処理
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
開始行:
「[[.NET 開発基盤部会 Wiki>http://dotnetdevelopmentinfras...
-[[戻る>ビッグデータ]]
*目次 [#oc1d257e]
#contents
*概要 [#u1bd4882]
**コンピューティング（計算） [#vef87ecc]
分散処理とは、
-複雑な計算などをネットワークを介して複数のコンピュータを...
-スループットを上げようとする取り組み、またはそれを実現す...
**ソリューション（解決） [#b132e7ee]
また、分散処理は、
-RDBでは大き過ぎるか、複雑すぎるデータを処理するように設...
-以下ケースに分散処理の分散処理（アーキテクチャ）が適合す...
--大量のデータを格納して処理する
--非構造化データを変換する
--ストリーミング データを処理する
*詳細 [#w06ca93f]
-基本的には1990年代までの並列データベースの技術に基づいた...
-ハードウェアの高性能化や新たな需要を踏まえ，その中核をな...
-以下のコンテンツをサマリすると、
--RDBの並列処理の様なモノ（基礎は同じ）を、
--異なる目的（セグメント＆ターゲット）で実装している感じ。
**基礎 [#q4fb50c2]
ざっくり、
-分散処理の起点は、[[並列化>#j0673aa7]]。
-[[並列化>#j0673aa7]]処理は
--手続型言語ではなく宣言型言語で記述される。
--宣言型言語では実行プランという形で最適化された処理が計...
みたいな話。
***アーキテクチャ [#gc694646]
無共有型のアーキテクチャが主流である。
-型
--共有メモリ型（シェアード・メモリ）
--共有ディスク型（シェアード・ディスク）
--無共有型（シェアード・ナッシング）
-理由
--単一ハードウェアコンポーネントにおけるレイテンシ低減の...
複数のハードウェアコンポーネントを効率的に活用する方向に...
--複数のコモディティサーバを高速なネットワークで接続した...
昨今のビッグデータ解析においては，価格性能比の点から，後...
***並列処理 [#j0673aa7]
-問い合わせ間の並列性（Inter-query Parallelism）~
複数の異なる問い合わせを並列に実行するときの並列性
-&color(red){問い合わせ内の並列性（Intra-query Parallelis...
1つの問い合わせを並列に実行可能な複数の~
サブタスクに分解して実行するときの並列性
--オペレータ間の並列性（Inter-operator Parallelism）~
問い合わせにおける複数の異なるオペレータを並列に実行する...
---&color(red){パイプライン並列性（Pipelined Parallelism...
あるオペレータが出力するデータを~
別のあるオペレータが入力する場合において，~
これらのオペレータを並列に実行するときの並列性
---独立並列性（Independent Parallelism）~
データの依存関係がない複数の独立したオペレータを並列に実...
--オペレータ内の並列性（Intra-operator Parallelism）~
1つのオペレータを並列実行可能な複数のサブタスクに分解して...
---&color(red){パーティション並列性（Partitioned Parallel...
データを複数にパーティショニングし，~
オペレータの複数のインスタンスが当該パーティションを~
並列に読み出すことにより，オペレータ内の並列性を活用する。~
※ [[SQL Serverの並列クエリはファイル・グループによるパー...
***データ分割 [#ye7e9cb6]
パーティション並列性のデータの分割方法には、主に次の3つの...
-ラウンドロビン分割（Round-Robin Partitioning）~
均等に分散される。
-ハッシュ分割（Hash Partitioning）~
均等に分散される。
-範囲分割（Range Partitioning）~
不均等だが、データが値でクラスタ化されており、~
処理系が処理の効率化を図ることができる場合がある。
***性能指標 [#xc519c0c]
並列処理の性能指標
-スケーラビリティ（Scalability）~
以下の指標があるが、ビッグデータ系では、~
スケールアップ（Scale-up）がより重要になる。
--スピードアップ（Speed-up）~
ジョブを処理する計算資源をN倍に増やしたときに，~
ジョブの処理時間がどの程度低下するか？
--スケールアップ（Scale-up）~
ジョブを処理する計算資源をN倍に増やしたときに，~
ジョブの仕事量（データ量）もN倍に増やしたときに，~
ジョブの処理するための時間が同程度か？
-線形なスケーラビリティ~
理想的には線形なスケーラビリティを有することが望ましい。~
--スピードアップ（Speed-up）では、~
計算資源N倍で1/N時間になる場合。~
--スケールアップ（Scale-up）では、（同じ処理時間で）~
計算資源N倍で仕事量（データ量）もN倍になる場合。
***アルゴリズム [#f1f6bb35]
並列処理のオペレータとアルゴリズム
-選択オペレータ
--スキャン（・アルゴリズム~
--索引スキャン（・アルゴリズム~
-結合オペレータ~
--ソートマージ結合（アルゴリズム~
---並列化が可能（並列ソートマージ結合）
---双方のソート済み結合キーで再パーティションして、結合。
---ソートマージ結合はハッシュ結合よりも低速
--ハッシュ結合（アルゴリズム~
---並列化が可能（並列ハッシュ結合）
---片方の結合キーをハッシュに読み込み（再パーティションし...
---ハッシュ結合はソートマージ結合よりも高速
--ネステッド・ループ結合（アルゴリズム
***実行プランの選択 [#rd0ce58b]
実行プランの列挙・見積・選択は、~
「（問い合わせ）最適化」と呼ばれる。
-実行プランの列挙
-処理のコスト見積
--どのようなアルゴリズムを用いるか？
---選択（Selection）のアルゴリズム
---結合（Join）のアルゴリズム
---集約（Aggregation）のアルゴリズム
--結合方法、結合順序をどうするか？
--並列データ処理の戦略をどうするか？
--統計情報を用いた性能比較。
-最適な実行プランの選択
***永続性と一貫性 [#ie9bbdb3]
レプリケーションとロギングがある（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を保証する。
***コーディネーション [#p0aafb89]
複数のプロセス間において，協調して動作をする，または，同...
-分類
--分散排他制御（Distributed Mutual Exclusion）~
分散環境で
---排他制御を行う（ロックを取る）。
---クリティカルセクションに入るプロセスを選択する。
--リーダ選挙（Election / Leader Election）
---ある特定の作業を行うためのリーダプロセスを選択する。
---分散排他制御は，ロックを取るリーダプロセスの選挙の特殊...
--グループ通信（Group Communication / Multicast）
---あるプロセスがほかの全プロセスにメッセージを送信するこ...
---いわゆる，マルチキャスト。
--コンセンサス（Consensus）
---あるプロセスが提案者となり，他のプロセスが同意をして，...
---グループ通信とコンセンサスはほぼ同等のもの。
-アルゴリズム
--2相コミット（Two-Phase Commit）
---複数のプロセスをまたいだ分散トランザクションにおいて~
原子性（Atomicity）を実現するための方法として広く用いられ...
---2つのフェーズから構成される。~
・フェーズ1：コーディネータがリソース・マネジャに対してPr...
・フェーズ2：コーディネータがすべてのリソース・マネジャか...
全リソース・マネジャに当該分散トランザクションのCommit or...
--ZAB
---Zookeeperにおいて用いられているコンセンサスアルゴリズム
---Proposerが常に1つのみ存在し、提案のFIFO / Causal / Tot...
---ProposerはFollowerに対して、2PCと類似の方法で任意の値...
---定足数が同意があればProposerは当該提案をコミットする。
--PAXOS
---ZABと類似の現在，最も広く使われているものの1つ。
---Proposerは複数の場合であっても動作する。~
・汎用性が高い~
・ZABと比較する複雑な仕組~
・提案のFIFO / Causal orderingを保証しない。
-前提知識
--コーディネーションの前提
---任意のプロセスがクラッシュし得る。~
・ビザンチン故障（プロセスの動作において仮定をおかない故...
・≒任意の動作を実行しない（要求に対して不正または一貫しな...
---メッセージの送信にかかる時間は有限だが上限がない。~
すなわち，分散システムモデルにおける非同期システムを想定...
---複数のプロセス間においては、~
固定的なマスタ / スレーブの関係は存在しない。
--分散システムにおける順序
---FIFO ordering~
・メッセージ送信順序でメッセージを受信する。~
・プロセス毎の因果関係のみを保証する性質。
---Causal ordering~
・因果関係が保たれる順序でメッセージを受信する。~
・FIFO ordering前提＋αのプロセス間の因果関係も保証する性質
---Total ordering~
すべてのプロセスにおいてメッセージの到達順序が同一である...
***分散処理 [#df139e29]
本項での処理系は
>「分散システム技術を活用した、~
データ処理専用の並列システム」
と言うことができる。
-永続性と一貫性
--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()においては，並列スキャンを行う。
---結合にハッシュ結合を使用しパイプライン並列性を活用
**ストア [#r77f778c]
データ・ストア、ディスクか？メモリか？
***ディスク [#g08a6d25]
-[[Hadoop]] の [[Hadoop Distributed File System (HDFS)>Ha...
-[[HDFS>Hadoop#l2a0cd99]]ベース
--[[Apache HBase]]
--, etc.
***メモリ [#v4fec751]
-[[Apache Spark]] の [[Resilient Distributed Dataset (RDD...
-[[RDD>Apache Spark#f411c5af]]ベース
--...
***その他 [#e2bd9443]
-[[ストレージ]]
-[[NoSQL]]~
[[Apache Spark]]と[[Cassandra]]なんて組み合わせもある模様。
**処理 [#q6bc0cf1]
どのような処理を実行できるか？
***[[分散（バッチ）系>分散処理：分散（バッチ）系#i6d81dee...
***[[ストリーム系>分散処理：ストリーム系#u7b64dd2]] [#m55...
***[[データ収集・格納系>分散処理：データ収集・格納系#f13e...
**目的 [#d5e53305]
ビジネス上の目的の例。
***意味付け [#r5007b57]
前もって意味付けせずに生のまま蓄積できる。
-データ分析時にいろいろな意味付けを試してみる探索的なデー...
-最新の統計理論をベースにゼロからプログラミングできる自由...
データアナリストというよりデータサイエンティストに向いた...
***可視化 [#b92c7f0a]
-可視化が目的の場合、以下のような流れで処理を行う。
>
+[[ストリーム>#m55c61c3]]
++データ収集
++エンリッチメント
+[[分散（バッチ）>#o97a1890]]
++蓄積
++可視化
-以下のようなプロダクトがある。
--[[Elasticsearch>#a87e408a]] ( + Kibana)
--[[BIツール>ビジネス インテリジェンス（BI）#j255e469]]
※ [[ディスク>#g08a6d25]]のデータを[[DWH>ビジネス インテリ...
***[[データ解析]] [#g5da28df]
***[[機械学習>機械学習（machine learning）]] [#jaf2c402]
*リンク [#c29bf3e1]
**目的別 [#w454319b]
***[[分散（バッチ）系>分散処理：分散（バッチ）系#jb20d368...
***[[ストリーム系>分散処理：ストリーム系#ef4cce53]] [#ta7...
***[[データ収集・格納>分散処理：データ収集・格納系#p2196c...
**プロダクト [#yc726057]
***[[分散（バッチ）系>分散処理：分散（バッチ）系#nb6b6319...
***[[ストリーム系>分散処理：ストリーム系#y82f9daa]] [#wba...
***[[データ収集・格納>分散処理：データ収集・格納系#d0265f...
***[[Elastic Stack>Elasticsearch#r521f91b]] [#a87e408a]
[[Elasticsearch]]の推奨構成
-[[ビッグデータ]]の可視化のプロダクト群
-データはドキュメントで、全文検索処理を行う。
-ストレージに[[Hadoop]]を使えるので分散処理系に分類
**[[データ・パイプライン]] [#d336dcf5]
[[データ収集・格納系>分散処理：データ収集・格納系]]~
→ [[ストリーム系>分散処理：ストリーム系]]~
→ [[分散（バッチ）系>分散処理：分散（バッチ）系]]
みたいな組み合わせ。
*参考 [#d32f224d]
-[[分散コンピューティング - Wikipedia>https://ja.wikipedi...
-分散処理に入門してみた（Hadoop + Spark） | キャスレーコ...
https://www.casleyconsulting.co.jp/blog/engineer/150/
**＠IT [#t952a25a]
-Database Watch（2016年3月版） Sparkは“誰”に例えられる？~
多様化と進化を続ける「Hadoop」、人気急上昇「Spark」~
https://www.atmarkit.co.jp/ait/articles/1603/07/news002.h...
-Amazon EMRで構築するApache Spark超入門
--（1）Apache Sparkとは何か――使い方や基礎知識を徹底解説~
https://www.atmarkit.co.jp/ait/articles/1608/24/news014.h...
--（2）Spark 2.0の回帰分析アプリをScalaのSBTで実装し、EMR...
https://www.atmarkit.co.jp/ait/articles/1609/27/news018.h...
**Think IT [#sa9f6bfa]
-伊藤 雅博~
https://thinkit.co.jp/author/10002
**NTTデータ [#r1f81a19]
***システム技術本部 [#s73a50e9]
-Hadoopエコシステムの最新動向とNTTデータの取り組み （OSC ...
https://www.slideshare.net/hadoopxnttdata/hadoop-osc2015s...
-並列分散処理基盤のいま 45分で学ぶHadoop／Spark／Kafka／...
https://www2.slideshare.net/nttdata-tech/distributed-data...
--動画 : https://www.youtube.com/watch?v=9NtYlRF5j6A
--動画２ : https://www.youtube.com/watch?v=-HGGmMOkEuc（...
***先端技術株式会社 [#wc71adf3]
-ビッグデータコラム Column on Big Data Analytics and Plat...
http://www.intellilink.co.jp/article/column/bigdata/index...
--ビッグデータ分析の意義と、分析のためのシステム基盤~
http://www.intellilink.co.jp/plan/corporate/column1.html
--ビッグデータ活用から価値を生む仕組みについて~
http://www.intellilink.co.jp/article/column/bigdata-ok01....
**[[Hadoopの歴史>Hadoop#reddea41]] [#ida03893]
**gihyo.jp … 技術評論社 [#r8aff958]
Hadoopはどのように動くのか
-並列・分散システム技術から読み解くHadoop処理系の設計と実...
https://gihyo.jp/admin/serial/01/how_hadoop_works
--第1回 なぜ，Hadoopはどのように動くのか，を学ぶのか~
https://gihyo.jp/admin/serial/01/how_hadoop_works/0001
--第2回 並列データ処理系の歴史と重要性~
https://gihyo.jp/admin/serial/01/how_hadoop_works/0002
--第3回 並列システムと分散システム~
https://gihyo.jp/admin/serial/01/how_hadoop_works/0003
--第4回 データ処理の方法~
https://gihyo.jp/admin/serial/01/how_hadoop_works/0004
--第5回 データ処理の並列化
---https://gihyo.jp/admin/serial/01/how_hadoop_works/0005
---https://gihyo.jp/admin/serial/01/how_hadoop_works/0005...
--データ処理における並列アルゴリズム
---第6回［1］~
https://gihyo.jp/admin/serial/01/how_hadoop_works/0006
---第7回［2］~
https://gihyo.jp/admin/serial/01/how_hadoop_works/0007
---第8回［3］~
https://gihyo.jp/admin/serial/01/how_hadoop_works/0008
--第9回 データ処理における性能の見積り~
https://gihyo.jp/admin/serial/01/how_hadoop_works/0009
--第10回 データ処理の最適化~
https://gihyo.jp/admin/serial/01/how_hadoop_works/0010
--第11回 耐障害性のための仕組み─レプリケーションとロギン...
https://gihyo.jp/admin/serial/01/how_hadoop_works/0011
--第12回 複数のプロセスにおける協調動作のための仕組み─コ...
https://gihyo.jp/admin/serial/01/how_hadoop_works/0012
--第13 - 15回
---[[Hadoop MapReduce>Hadoop#gd508729]]
---[[Hadoop YARN>Hadoop#h693517e]]
--第16回~
[[並列データ処理系 Apache Tez>Apache Tez#e2369c9c]]
--第17 - 19回~
[[Impalaの設計と実装>Apache Impala#ib9c9b50]]
--第20 - 21回~
[[Sparkの設計と実装>Apache Spark#r1d8a217]]
--第22回［最終回］まとめと本連載で解説できなかったこと~
https://gihyo.jp/admin/serial/01/how_hadoop_works/0022
終了行:
「[[.NET 開発基盤部会 Wiki>http://dotnetdevelopmentinfras...
-[[戻る>ビッグデータ]]
*目次 [#oc1d257e]
#contents
*概要 [#u1bd4882]
**コンピューティング（計算） [#vef87ecc]
分散処理とは、
-複雑な計算などをネットワークを介して複数のコンピュータを...
-スループットを上げようとする取り組み、またはそれを実現す...
**ソリューション（解決） [#b132e7ee]
また、分散処理は、
-RDBでは大き過ぎるか、複雑すぎるデータを処理するように設...
-以下ケースに分散処理の分散処理（アーキテクチャ）が適合す...
--大量のデータを格納して処理する
--非構造化データを変換する
--ストリーミング データを処理する
*詳細 [#w06ca93f]
-基本的には1990年代までの並列データベースの技術に基づいた...
-ハードウェアの高性能化や新たな需要を踏まえ，その中核をな...
-以下のコンテンツをサマリすると、
--RDBの並列処理の様なモノ（基礎は同じ）を、
--異なる目的（セグメント＆ターゲット）で実装している感じ。
**基礎 [#q4fb50c2]
ざっくり、
-分散処理の起点は、[[並列化>#j0673aa7]]。
-[[並列化>#j0673aa7]]処理は
--手続型言語ではなく宣言型言語で記述される。
--宣言型言語では実行プランという形で最適化された処理が計...
みたいな話。
***アーキテクチャ [#gc694646]
無共有型のアーキテクチャが主流である。
-型
--共有メモリ型（シェアード・メモリ）
--共有ディスク型（シェアード・ディスク）
--無共有型（シェアード・ナッシング）
-理由
--単一ハードウェアコンポーネントにおけるレイテンシ低減の...
複数のハードウェアコンポーネントを効率的に活用する方向に...
--複数のコモディティサーバを高速なネットワークで接続した...
昨今のビッグデータ解析においては，価格性能比の点から，後...
***並列処理 [#j0673aa7]
-問い合わせ間の並列性（Inter-query Parallelism）~
複数の異なる問い合わせを並列に実行するときの並列性
-&color(red){問い合わせ内の並列性（Intra-query Parallelis...
1つの問い合わせを並列に実行可能な複数の~
サブタスクに分解して実行するときの並列性
--オペレータ間の並列性（Inter-operator Parallelism）~
問い合わせにおける複数の異なるオペレータを並列に実行する...
---&color(red){パイプライン並列性（Pipelined Parallelism...
あるオペレータが出力するデータを~
別のあるオペレータが入力する場合において，~
これらのオペレータを並列に実行するときの並列性
---独立並列性（Independent Parallelism）~
データの依存関係がない複数の独立したオペレータを並列に実...
--オペレータ内の並列性（Intra-operator Parallelism）~
1つのオペレータを並列実行可能な複数のサブタスクに分解して...
---&color(red){パーティション並列性（Partitioned Parallel...
データを複数にパーティショニングし，~
オペレータの複数のインスタンスが当該パーティションを~
並列に読み出すことにより，オペレータ内の並列性を活用する。~
※ [[SQL Serverの並列クエリはファイル・グループによるパー...
***データ分割 [#ye7e9cb6]
パーティション並列性のデータの分割方法には、主に次の3つの...
-ラウンドロビン分割（Round-Robin Partitioning）~
均等に分散される。
-ハッシュ分割（Hash Partitioning）~
均等に分散される。
-範囲分割（Range Partitioning）~
不均等だが、データが値でクラスタ化されており、~
処理系が処理の効率化を図ることができる場合がある。
***性能指標 [#xc519c0c]
並列処理の性能指標
-スケーラビリティ（Scalability）~
以下の指標があるが、ビッグデータ系では、~
スケールアップ（Scale-up）がより重要になる。
--スピードアップ（Speed-up）~
ジョブを処理する計算資源をN倍に増やしたときに，~
ジョブの処理時間がどの程度低下するか？
--スケールアップ（Scale-up）~
ジョブを処理する計算資源をN倍に増やしたときに，~
ジョブの仕事量（データ量）もN倍に増やしたときに，~
ジョブの処理するための時間が同程度か？
-線形なスケーラビリティ~
理想的には線形なスケーラビリティを有することが望ましい。~
--スピードアップ（Speed-up）では、~
計算資源N倍で1/N時間になる場合。~
--スケールアップ（Scale-up）では、（同じ処理時間で）~
計算資源N倍で仕事量（データ量）もN倍になる場合。
***アルゴリズム [#f1f6bb35]
並列処理のオペレータとアルゴリズム
-選択オペレータ
--スキャン（・アルゴリズム~
--索引スキャン（・アルゴリズム~
-結合オペレータ~
--ソートマージ結合（アルゴリズム~
---並列化が可能（並列ソートマージ結合）
---双方のソート済み結合キーで再パーティションして、結合。
---ソートマージ結合はハッシュ結合よりも低速
--ハッシュ結合（アルゴリズム~
---並列化が可能（並列ハッシュ結合）
---片方の結合キーをハッシュに読み込み（再パーティションし...
---ハッシュ結合はソートマージ結合よりも高速
--ネステッド・ループ結合（アルゴリズム
***実行プランの選択 [#rd0ce58b]
実行プランの列挙・見積・選択は、~
「（問い合わせ）最適化」と呼ばれる。
-実行プランの列挙
-処理のコスト見積
--どのようなアルゴリズムを用いるか？
---選択（Selection）のアルゴリズム
---結合（Join）のアルゴリズム
---集約（Aggregation）のアルゴリズム
--結合方法、結合順序をどうするか？
--並列データ処理の戦略をどうするか？
--統計情報を用いた性能比較。
-最適な実行プランの選択
***永続性と一貫性 [#ie9bbdb3]
レプリケーションとロギングがある（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を保証する。
***コーディネーション [#p0aafb89]
複数のプロセス間において，協調して動作をする，または，同...
-分類
--分散排他制御（Distributed Mutual Exclusion）~
分散環境で
---排他制御を行う（ロックを取る）。
---クリティカルセクションに入るプロセスを選択する。
--リーダ選挙（Election / Leader Election）
---ある特定の作業を行うためのリーダプロセスを選択する。
---分散排他制御は，ロックを取るリーダプロセスの選挙の特殊...
--グループ通信（Group Communication / Multicast）
---あるプロセスがほかの全プロセスにメッセージを送信するこ...
---いわゆる，マルチキャスト。
--コンセンサス（Consensus）
---あるプロセスが提案者となり，他のプロセスが同意をして，...
---グループ通信とコンセンサスはほぼ同等のもの。
-アルゴリズム
--2相コミット（Two-Phase Commit）
---複数のプロセスをまたいだ分散トランザクションにおいて~
原子性（Atomicity）を実現するための方法として広く用いられ...
---2つのフェーズから構成される。~
・フェーズ1：コーディネータがリソース・マネジャに対してPr...
・フェーズ2：コーディネータがすべてのリソース・マネジャか...
全リソース・マネジャに当該分散トランザクションのCommit or...
--ZAB
---Zookeeperにおいて用いられているコンセンサスアルゴリズム
---Proposerが常に1つのみ存在し、提案のFIFO / Causal / Tot...
---ProposerはFollowerに対して、2PCと類似の方法で任意の値...
---定足数が同意があればProposerは当該提案をコミットする。
--PAXOS
---ZABと類似の現在，最も広く使われているものの1つ。
---Proposerは複数の場合であっても動作する。~
・汎用性が高い~
・ZABと比較する複雑な仕組~
・提案のFIFO / Causal orderingを保証しない。
-前提知識
--コーディネーションの前提
---任意のプロセスがクラッシュし得る。~
・ビザンチン故障（プロセスの動作において仮定をおかない故...
・≒任意の動作を実行しない（要求に対して不正または一貫しな...
---メッセージの送信にかかる時間は有限だが上限がない。~
すなわち，分散システムモデルにおける非同期システムを想定...
---複数のプロセス間においては、~
固定的なマスタ / スレーブの関係は存在しない。
--分散システムにおける順序
---FIFO ordering~
・メッセージ送信順序でメッセージを受信する。~
・プロセス毎の因果関係のみを保証する性質。
---Causal ordering~
・因果関係が保たれる順序でメッセージを受信する。~
・FIFO ordering前提＋αのプロセス間の因果関係も保証する性質
---Total ordering~
すべてのプロセスにおいてメッセージの到達順序が同一である...
***分散処理 [#df139e29]
本項での処理系は
>「分散システム技術を活用した、~
データ処理専用の並列システム」
と言うことができる。
-永続性と一貫性
--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()においては，並列スキャンを行う。
---結合にハッシュ結合を使用しパイプライン並列性を活用
**ストア [#r77f778c]
データ・ストア、ディスクか？メモリか？
***ディスク [#g08a6d25]
-[[Hadoop]] の [[Hadoop Distributed File System (HDFS)>Ha...
-[[HDFS>Hadoop#l2a0cd99]]ベース
--[[Apache HBase]]
--, etc.
***メモリ [#v4fec751]
-[[Apache Spark]] の [[Resilient Distributed Dataset (RDD...
-[[RDD>Apache Spark#f411c5af]]ベース
--...
***その他 [#e2bd9443]
-[[ストレージ]]
-[[NoSQL]]~
[[Apache Spark]]と[[Cassandra]]なんて組み合わせもある模様。
**処理 [#q6bc0cf1]
どのような処理を実行できるか？
***[[分散（バッチ）系>分散処理：分散（バッチ）系#i6d81dee...
***[[ストリーム系>分散処理：ストリーム系#u7b64dd2]] [#m55...
***[[データ収集・格納系>分散処理：データ収集・格納系#f13e...
**目的 [#d5e53305]
ビジネス上の目的の例。
***意味付け [#r5007b57]
前もって意味付けせずに生のまま蓄積できる。
-データ分析時にいろいろな意味付けを試してみる探索的なデー...
-最新の統計理論をベースにゼロからプログラミングできる自由...
データアナリストというよりデータサイエンティストに向いた...
***可視化 [#b92c7f0a]
-可視化が目的の場合、以下のような流れで処理を行う。
>
+[[ストリーム>#m55c61c3]]
++データ収集
++エンリッチメント
+[[分散（バッチ）>#o97a1890]]
++蓄積
++可視化
-以下のようなプロダクトがある。
--[[Elasticsearch>#a87e408a]] ( + Kibana)
--[[BIツール>ビジネス インテリジェンス（BI）#j255e469]]
※ [[ディスク>#g08a6d25]]のデータを[[DWH>ビジネス インテリ...
***[[データ解析]] [#g5da28df]
***[[機械学習>機械学習（machine learning）]] [#jaf2c402]
*リンク [#c29bf3e1]
**目的別 [#w454319b]
***[[分散（バッチ）系>分散処理：分散（バッチ）系#jb20d368...
***[[ストリーム系>分散処理：ストリーム系#ef4cce53]] [#ta7...
***[[データ収集・格納>分散処理：データ収集・格納系#p2196c...
**プロダクト [#yc726057]
***[[分散（バッチ）系>分散処理：分散（バッチ）系#nb6b6319...
***[[ストリーム系>分散処理：ストリーム系#y82f9daa]] [#wba...
***[[データ収集・格納>分散処理：データ収集・格納系#d0265f...
***[[Elastic Stack>Elasticsearch#r521f91b]] [#a87e408a]
[[Elasticsearch]]の推奨構成
-[[ビッグデータ]]の可視化のプロダクト群
-データはドキュメントで、全文検索処理を行う。
-ストレージに[[Hadoop]]を使えるので分散処理系に分類
**[[データ・パイプライン]] [#d336dcf5]
[[データ収集・格納系>分散処理：データ収集・格納系]]~
→ [[ストリーム系>分散処理：ストリーム系]]~
→ [[分散（バッチ）系>分散処理：分散（バッチ）系]]
みたいな組み合わせ。
*参考 [#d32f224d]
-[[分散コンピューティング - Wikipedia>https://ja.wikipedi...
-分散処理に入門してみた（Hadoop + Spark） | キャスレーコ...
https://www.casleyconsulting.co.jp/blog/engineer/150/
**＠IT [#t952a25a]
-Database Watch（2016年3月版） Sparkは“誰”に例えられる？~
多様化と進化を続ける「Hadoop」、人気急上昇「Spark」~
https://www.atmarkit.co.jp/ait/articles/1603/07/news002.h...
-Amazon EMRで構築するApache Spark超入門
--（1）Apache Sparkとは何か――使い方や基礎知識を徹底解説~
https://www.atmarkit.co.jp/ait/articles/1608/24/news014.h...
--（2）Spark 2.0の回帰分析アプリをScalaのSBTで実装し、EMR...
https://www.atmarkit.co.jp/ait/articles/1609/27/news018.h...
**Think IT [#sa9f6bfa]
-伊藤 雅博~
https://thinkit.co.jp/author/10002
**NTTデータ [#r1f81a19]
***システム技術本部 [#s73a50e9]
-Hadoopエコシステムの最新動向とNTTデータの取り組み （OSC ...
https://www.slideshare.net/hadoopxnttdata/hadoop-osc2015s...
-並列分散処理基盤のいま 45分で学ぶHadoop／Spark／Kafka／...
https://www2.slideshare.net/nttdata-tech/distributed-data...
--動画 : https://www.youtube.com/watch?v=9NtYlRF5j6A
--動画２ : https://www.youtube.com/watch?v=-HGGmMOkEuc（...
***先端技術株式会社 [#wc71adf3]
-ビッグデータコラム Column on Big Data Analytics and Plat...
http://www.intellilink.co.jp/article/column/bigdata/index...
--ビッグデータ分析の意義と、分析のためのシステム基盤~
http://www.intellilink.co.jp/plan/corporate/column1.html
--ビッグデータ活用から価値を生む仕組みについて~
http://www.intellilink.co.jp/article/column/bigdata-ok01....
**[[Hadoopの歴史>Hadoop#reddea41]] [#ida03893]
**gihyo.jp … 技術評論社 [#r8aff958]
Hadoopはどのように動くのか
-並列・分散システム技術から読み解くHadoop処理系の設計と実...
https://gihyo.jp/admin/serial/01/how_hadoop_works
--第1回 なぜ，Hadoopはどのように動くのか，を学ぶのか~
https://gihyo.jp/admin/serial/01/how_hadoop_works/0001
--第2回 並列データ処理系の歴史と重要性~
https://gihyo.jp/admin/serial/01/how_hadoop_works/0002
--第3回 並列システムと分散システム~
https://gihyo.jp/admin/serial/01/how_hadoop_works/0003
--第4回 データ処理の方法~
https://gihyo.jp/admin/serial/01/how_hadoop_works/0004
--第5回 データ処理の並列化
---https://gihyo.jp/admin/serial/01/how_hadoop_works/0005
---https://gihyo.jp/admin/serial/01/how_hadoop_works/0005...
--データ処理における並列アルゴリズム
---第6回［1］~
https://gihyo.jp/admin/serial/01/how_hadoop_works/0006
---第7回［2］~
https://gihyo.jp/admin/serial/01/how_hadoop_works/0007
---第8回［3］~
https://gihyo.jp/admin/serial/01/how_hadoop_works/0008
--第9回 データ処理における性能の見積り~
https://gihyo.jp/admin/serial/01/how_hadoop_works/0009
--第10回 データ処理の最適化~
https://gihyo.jp/admin/serial/01/how_hadoop_works/0010
--第11回 耐障害性のための仕組み─レプリケーションとロギン...
https://gihyo.jp/admin/serial/01/how_hadoop_works/0011
--第12回 複数のプロセスにおける協調動作のための仕組み─コ...
https://gihyo.jp/admin/serial/01/how_hadoop_works/0012
--第13 - 15回
---[[Hadoop MapReduce>Hadoop#gd508729]]
---[[Hadoop YARN>Hadoop#h693517e]]
--第16回~
[[並列データ処理系 Apache Tez>Apache Tez#e2369c9c]]
--第17 - 19回~
[[Impalaの設計と実装>Apache Impala#ib9c9b50]]
--第20 - 21回~
[[Sparkの設計と実装>Apache Spark#r1d8a217]]
--第22回［最終回］まとめと本連載で解説できなかったこと~
https://gihyo.jp/admin/serial/01/how_hadoop_works/0022
ページ名:
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
