狠狠撸

狠狠撸Share a Scribd company logo

クラウドを支える基盘技术の最新动向と今后の方向性

?
?
M
Masayoshi Hagiwara
1 of 47
クラウドを支える基盤技術の 最新動向と今後の方向性 日本マイクロソフト株式会社 萩原 正義 @masayh
目的 ? クラウドの分散システムや大規模データベー ス技術の発展の歴史、現在の動向、将来の方 向性 – CAP 定理の制約をどのように克服しているか – 可用性技術がどのように保証されているか – OLTP が分散システムでどう拡張されたか – 開発手法として考えていくべき課題と対応は何か – Big Data の次の基盤の重要な要素技術は何か (C) 2012 Microsoft Corporation 2
Agenda ? 分散システムとは – CAP 定理 ? 可用性を支える复製 – P-B – ROWA – quorum – RSM、Paxos – A/E 分離 ? スケーラビリティ OLTP プロトコルの発展 – Group safety – 2PC に代わる atomic broadcast – View synchronous ? 设计论 – 次世代アーキテクチャー – CAP 定理の制約を超える – 混沌と秩序 – 最適化の方法 – 抽象データ(型)の応用 (C) 2012 Microsoft Corporation 3
分散システムとは
分散システム再評価の背景 ? Hadoop で分散プログラミングモデルが普及 ? クラウドの普及で可用性確保で fault-tolerance が必要 ? ZooKeeper のような OSS のサービス部品の再利用可能性 ? 1970年代のトランザクションが1980年代のグループコミュニケー ションで進化 – さらに、HTTP/XML から WebSockets で分散が再興。双方向と提案型 – 特許有効期間は20年 ? Big Data で、データ分析基盤のフロントの更新系サービスで分散シ ステムの利用 – 分析対象の収集のためのサービス化を考える – フロントでのソーシャルのタイムラインの一貫性など、可用性と応答時 間のバランスを考えることが重要視される ? serializability による証明可能化、形式化 (C) 2012 Microsoft Corporation 5
分散システムとは何か ? 確実な障害検出ができない – 単なるネットワークの遅延なのか、相手の障害なのか ? その前提で以下の機能が求められる – 複製の一貫性のための合意 – リーダー障害時のリーダーの選出（合意） – 参加メンバーのリストの合意 – 分散排他制御 – それらのリカバリー、再構成を含むアルゴリズム、プロトコル ? 原子的ブロードキャストプロトコル ? ベクタークロック ? 障害検出器 ? 分散プロトコルの証明 – 障害モデルの前提（転送の信頼性、非同期性、Fail-stop/Byzantine、 認証） – Safety、liveness の証明 – 障害検出器とクロック (C) 2012 Microsoft Corporation 6
分散システムの難しさ ? elastic なリソース管理、再構成定義 – 負荷に応じて – 障害に応じて、リカバリー ? 構成変更中も動作を止めない – 複数のラウンドに分割（ビュー/バロット/エポックの同期） ? 複合障害への対応 – SPOF の許容度 – 障害モデルごとの対応 ? 各種要素のバランスでアルゴリズム、プロトコルを選択 – 可用性/信頼性の要求、スループット、応答時間、再構成可能とリカバ リーの完了期間、一貫性の調整、リソースの消費量（ネットワーク帯 域、ディスク帯域、ディスクI/O 回数など）= コスト – 多様なアルゴリズム、プロトコルから選択、システム化 – テストなど、エンジニアリング的な解決が難しい – 形式手法化： correctness criteria (C) 2012 Microsoft Corporation 7
分散システムの適用 ? 複製への適用 – Group safety ? OLTP への適用 – 2PC に代わる atomic broadcast + ローカルト ランザクション – Paxos コミット – Serializability の拡張 ? スケジューリングやリソース管理 – HadoopDB (C) 2012 Microsoft Corporation 8
CAP 定理 Revisited ? Consistency: すべてのクライアントは変更があっても同一の ビューを見る ? Availability: すべてのクライアントは障害が発生しても、データ のいくつかの複製を発見することができる ? Partition-tolerance: （分散）システムはネットワークが切断さ れても、その特性を維持する ? 制約： – Partition-tolerance に着目しているサービス提供者向け – Latency の考慮がない – 障害モードでの補償処理をどう考えるか – 必要に応じて ACID、合意プロトコルにより一貫性を取る考え方へ (C) 2012 Microsoft Corporation 9
CAP の2特性を選択 C A ? Consistency + Availability ? 単一サイト / クラスタデータベース P ? 通常の RDB など ? Consistency + Partition-tolerance C A ? 分散データベース / 分散ロック P ? HBase、Paxos ? Availability + Partition-tolerance C A ? 分散キャッシュ / DNS P ? Cassandra, eventual consistency (C) 2012 Microsoft Corporation 10
可用性 vs. 一貫性 CAP 定理 (C) 2012 Microsoft Corporation 11
可用性を支える复製
データベースの安全性基準 安全性の基準 配送される コミットされ 説明 サーバ数 たサーバ数 無処理 ゼロ ゼロ 0-safety 1 ゼロ トランザクションは1つのサーバに配送され、実行され たがまだコミットはされない。ストレージにトランザク ションの結果が永続化される前にクラッシュすると、ト ランザクションは失われる 1-safety 1 1 トランザクションは1つのサーバに配送され、コミット された。そのトランザクションが他のサーバに送信され る前にクラッシュするとトランザクションは失われる可 能性がある。他のサーバは先のトランザクションの存在 を知らないので、そのトランザクションと衝突する新た な別トランザクションを受け付けられる場合にトランザ クションは失われる Group-safety すべて ゼロ トランザクションはすべてのサーバに配送されるがまだ コミットはしていない。f（0<f<すべて）個以上のサー バがクラッシュすると、トランザクションは失われる Group-safetyか すべて 1 トランザクションはすべてのサーバに配送され、1つの つ1-safety サーバでコミットされた。f個のサーバかつトランザク （group-1- ションをコミットした1つのサーバがクラッシュすると、 safety） トランザクションは失われる可能性がある。データベー スとグループ通信機構を組み合わせたレプリケーション の大部分はここに属する 2-safety すべて すべて トランザクションはすべてのサーバに配送され、コミッ トされた。トランザクションが失われることはない (C) 2012 Microsoft Corporation 13
現状の複製技術 ? Primary-backup ? Update-anywhere ? Master-slave から cohort単位の複製へ Zookeeper Node A Node B Node C Node D Node E key ranges key ranges key ranges key ranges key ranges [0,199] [200,399] [400,599] [600,799] [800,999] [800,999] [0,199] [200,399] [400,599] [600,799] [600,799] [800,999] [0,199] [200,399] [400,599] (C) 2012 Microsoft Corporation 14
Primary-Backup プロトコル Alsberg-Day Protocol (C) 2012 Microsoft Corporation 15
全順序化 ? P-B の順序化の例 – viewstamped replication ? 順序化しないと合意が必要な例 – 楽観的レプリケーション 出典： Optimistic Replication (Shapiro, Saito) (C) 2012 Microsoft Corporation 16
ROWA (Read One Write All) W=N R=1 読み取りに最適化した強い一貫性 W=1 R=N 書き込みに最適化した強い一貫性 W+R<=N eventual consistency 古いデータの読み取りがありえる W+R>N quorum assembly による強い一貫性。読み取りには少なく とも1つの最新データの複製を含む Read quorum Replica Replica Replica Manger Manger Manger Client Front End Replica Replica Replica Manger Manger Manger Front Client End Replica Replica Manger Manger Write quorum (C) 2012 Microsoft Corporation 17
Quorum (定足数) ? Read quorum(RQ) と Write quorum(WQ) の規則 ? |RQ|+|WQ|>N （Read と Write set は重なる） ? |WQ|>N/2 （２つの Write set は重なる） ? Quorum consensus ? CC とは独立、回復プロトコル不要 ? ROWA との比較 ? P-B と ROWA の中間の特徴 ? これからの位置づけ – Byzantine 障害 – 負荷分散 – 契約の一種 (C) 2012 Microsoft Corporation 18
データ配置 ? Rack aware – HDFS, MapR ? Geo replication – DHT ? いろいろな一貫性モデルがありえる – ビジネスにどれが適切か？ 出典： Geo-Replication in Large-Scale Cloud Computing Applications (C) 2012 Microsoft Corporation 19
Replicated State Machine ? 状態マシン – 状態マシンを壊す要因 ? Paxos – Leader と primary の違い – Learner は合意結果を知らない – 複数の leader の実行と競合 – 1 leader による複数要求の同時実行 – Batching と Pipeline (C) 2012 Microsoft Corporation 20
Basic Paxos (1) 複製（状態マシン） Read フェーズ Write フェーズ 提案番号（バロット ID） 複製への反映 過半数 (C) 2012 Microsoft Corporation 21
Basic Paxos (2) 複製は合意結果を知らない 障害が疑われると複数の Leader を立てられる（弱い障害検知） 提案番号を大きくする (C) 2012 Microsoft Corporation 22
Basic Paxos (3) 複数 Leader 間の競合 (C) 2012 Microsoft Corporation 23
Paxos の過半数 ? propose/accept リーダー A リーダー B 間の調整 propose/accept propose/accept ? 提案番号の全順序 Ballot n-1 Ballot n 化 accept propose 時間推移 Ballot n-1 Ballot n ? Ballot 間の合意の accept accept 引き継ぎ 時間推移 (C) 2012 Microsoft Corporation 24
replica の過半数 ? Replica 一貫性モデル Replica への Replica への write read – Spinnaker の例 Client Leader Followers Write Acquire LSN = X Propose X to Followers Write log record to WAL & Commit Queue Write X to WAL & Commit Ack X Queue Send Ack to Master Don’t apply to Memtables yet Time Update Commit Queue Apply X to Membtables Send Ack to Client X is not in the Memtable yet. Client can read the latest value at the Leader Reads at Followers see an older value now Asynchronous Commit Message for LSN = Y (Y>=X) Process everything in the Commit Queue until Y and apply to Memtables. Reads now see every update up to LSN = Y (C) 2012 Microsoft Corporation 25
Paxos と ZooKeeper ? P-B と RSM の違い ? Primary order の問題 – メッセージ単位のトランザクションスコープ メッセージの安定化 出典： Zab: High-performance broadcast for primary-backup systems (C) 2012 Microsoft Corporation 26
A/E 分離 ? Byzantine 障害対応の複製数の削減 ? privacy 出典： ZZ and the Art of Practical BFT Execution (C) 2012 Microsoft Corporation 27
Paxos コミット ? TM が Paxos を使い RM の合意を取る ? 2F+1 個のアクセプター (~2F+1 個の TMs) ? 各 RM は prepare 要求に応答 ? If F+1 個のアクセプターがすべての RMs が prepared 状態 になったと確認するとトランザクションをコミット ? 2F(N+1) + 3N + 1 回のメッセージ ? 5 回のメッセージ遅延 Commit Acceptors （1回余計の遅延） RM0 Leader RM0…N 0…2F 2回の永続化 ? F=0 なら 2PC と同じ (C) 2012 Microsoft Corporation 28
Vertical Paxos Paxos グループ Paxos グループ 構成要素1 構成要素2 耐障害性、可用性、スケーラビリティ 遅延、運用コストなどを基準に選択 分散システム プロセスメンバー (C) 2012 Microsoft Corporation 29
スケーラビリティ OLTP プロトコルの発展
動的プロセスグループ (C) 2012 Microsoft Corporation 31
ビューの同期（１） (C) 2012 Microsoft Corporation 32
ビューの同期（２） (C) 2012 Microsoft Corporation 33
ビューの同期（３） (C) 2012 Microsoft Corporation 34
2PC に代わる atomic broadcast 2PC に代わり分散システムのメッセージング 受信と配送の分離 ACID の一貫性と永続化が同時に実行される トランザクション リソース クライアント マネージャ read/write 毎 (ROWA) トランザクション毎 ローカル トランザクション の serializability トランザクションデータ操作 Read-only トランザクション commit/abort のアボート (C) 2012 Microsoft Corporation 35
障害時の動作 (1) ROWA ? トランザクション送信中のクラッシュ – トランザクション送信中のビュー変更 Si ① トランザクションデータ操作 ③ ② commit ④ V{Si} → V’{^Si} View 変更あり → V’’{Si} ? トランザクション受信中のクラッシュ ①トランザクションデータ操作 Si ② commit ③ V{Si} → V’{^Si} ? 復旧中のクラッシュ → V’’{Si} Si ① ② ③ (C) 2012 Microsoft Corporation 36
障害時の動作 (2) P-B 運用中の構成変更 古いビューの操作 の片づけ 出典： Dynamic Reconfiguration of Primary/Backup Clusters (C) 2012 Microsoft Corporation 37
设计论
次世代アーキテクチャー ? Soft State – Weak Consistency Model – Timeline consistency – Read-your-Writes consistency – Eventual consistency ? NoSQL C, AP (BASE), 非同期 Stateless, Elastic CA (C) 2012 Microsoft Corporation 39
CAP 定理の制約を超える ? レイヤリング – CP (Quorum) を AP (期限付きキャッシュ) に載せる ? トランザクションの時間分割から一貫性モデルの時間 調整 (CA の 2PC の制約) – メッセージ安定化のフェイズ – Weak consistency 多数のプロセスですべてのプロセスが更新結果をみなくてもいい状況 異なるプロセスでまだ同期化が実行され ていないので観測結果が異なってよい 同期化しているので P2は最新の x の b が見えないといけない 許容 許容されない (C) 2012 Microsoft Corporation 40
混沌と秩序 A C A C A C BASE ACID BASE ACID BASE ACID Superstep Sync Superstep Sync Superstep Sync 非同期 同期 非同期 同期 非同期 同期 混沌 秩序 混沌 秩序 混沌 秩序 (C) 2012 Microsoft Corporation 41
最適化の方法 ? スケーラブルアーキテクチャーの原則 ? MapReduce の最適化 – Data Intensive Scalable Computing アーキ テクチャースタイルの一例 (C) 2012 Microsoft Corporation 42
スケーラブルアーキテクチャーの 原則 データ分割による競合防止 メモリ上の効率利用 分類→分割→配置→集約 index データ構造アクセス ホットスポットの回避 遅延永続化 データ偏在の解決 転送効率化 Co-location、転送プロトコル 簡易検査、圧縮などデータ量の削減 負荷分散 非同期による時間差 並列可能箇所の並列実行 時間順序保証の上 (C) 2012 Microsoft Corporation 43
MapReduce の物理最適化 ? ジョブ段数を減らし shuffle 数を削減 ? 前段に寄せることでデータ転送量を減らす – push-down： join－select－projection を select－join－ projection とする ? sum(2,3,1) = sum(sum(2,3),1) ? avg(2,3,1) != avg(avg(2,3),1) ? インクリメンタルな計算に置き換え – semi-join(?) , bloom filter で転送量を減らす – Combiner ? データ偏在の解決、分割法 ? データ構造の最適化（カラム指向 DB など） ? コード/データの共有、キャッシュ ? 動的最適化 (C) 2012 Microsoft Corporation 44
並列の比較 ? 分散並列 MapReduce vs. ローカル並列 カラム指向 – Tuple のキー特性 Row Group 1 c1 c2 c3 c4 c1 c2 c3 c4 11 12 13 14 11 12 13 14 21 22 23 24 21 22 23 24 31 32 33 34 31 32 33 34 41 42 43 44 51 52 53 54 Row Group 2 c1 c2 c3 c4 41 42 43 44 51 52 53 54 (C) 2012 Microsoft Corporation 45
抽象データ(型)の応用 ? ZooKeeper の znode による分散合意 ? Hive によるデータ分析 – RCFile（カラム指向）と SQL 類似のプログラミングモデル ? Apache Spark による各種並列計算（データフロー、BSP な ど） – RDD (Resilient Distributed Dataset) と Scala のプログラミン グモデル ? CRDT (Commutative Replicated Data Type)による共有デー タのスケーラビリティ、分散データの eventual consistency、 グループウェア – CRDT と各種プログラム言語 (C) 2012 Microsoft Corporation 46
まとめ ? Big Data の次の基盤の重要な要素技術は何 か？ – CAP 定理 – 分散システム – トランザクション、DB – プログラミング言語やツール（抽象化、最適化、 設計ガイド） – H/W （SSD、ネットワーク） – 特許、IP – 皆さんの挑戦、知恵と協力 (C) 2012 Microsoft Corporation 47

More Related Content

クラウドを支える基盘技术の最新动向と今后の方向性

  • 2. 目的 ? クラウドの分散システムや大規模データベー ス技術の発展の歴史、現在の動向、将来の方 向性 – CAP 定理の制約をどのように克服しているか – 可用性技術がどのように保証されているか – OLTP が分散システムでどう拡張されたか – 開発手法として考えていくべき課題と対応は何か – Big Data の次の基盤の重要な要素技術は何か (C) 2012 Microsoft Corporation 2
  • 3. Agenda ? 分散システムとは – CAP 定理 ? 可用性を支える复製 – P-B – ROWA – quorum – RSM、Paxos – A/E 分離 ? スケーラビリティ OLTP プロトコルの発展 – Group safety – 2PC に代わる atomic broadcast – View synchronous ? 设计论 – 次世代アーキテクチャー – CAP 定理の制約を超える – 混沌と秩序 – 最適化の方法 – 抽象データ(型)の応用 (C) 2012 Microsoft Corporation 3
  • 5. 分散システム再評価の背景 ? Hadoop で分散プログラミングモデルが普及 ? クラウドの普及で可用性確保で fault-tolerance が必要 ? ZooKeeper のような OSS のサービス部品の再利用可能性 ? 1970年代のトランザクションが1980年代のグループコミュニケー ションで進化 – さらに、HTTP/XML から WebSockets で分散が再興。双方向と提案型 – 特許有効期間は20年 ? Big Data で、データ分析基盤のフロントの更新系サービスで分散シ ステムの利用 – 分析対象の収集のためのサービス化を考える – フロントでのソーシャルのタイムラインの一貫性など、可用性と応答時 間のバランスを考えることが重要視される ? serializability による証明可能化、形式化 (C) 2012 Microsoft Corporation 5
  • 6. 分散システムとは何か ? 確実な障害検出ができない – 単なるネットワークの遅延なのか、相手の障害なのか ? その前提で以下の機能が求められる – 複製の一貫性のための合意 – リーダー障害時のリーダーの選出（合意） – 参加メンバーのリストの合意 – 分散排他制御 – それらのリカバリー、再構成を含むアルゴリズム、プロトコル ? 原子的ブロードキャストプロトコル ? ベクタークロック ? 障害検出器 ? 分散プロトコルの証明 – 障害モデルの前提（転送の信頼性、非同期性、Fail-stop/Byzantine、 認証） – Safety、liveness の証明 – 障害検出器とクロック (C) 2012 Microsoft Corporation 6
  • 7. 分散システムの難しさ ? elastic なリソース管理、再構成定義 – 負荷に応じて – 障害に応じて、リカバリー ? 構成変更中も動作を止めない – 複数のラウンドに分割（ビュー/バロット/エポックの同期） ? 複合障害への対応 – SPOF の許容度 – 障害モデルごとの対応 ? 各種要素のバランスでアルゴリズム、プロトコルを選択 – 可用性/信頼性の要求、スループット、応答時間、再構成可能とリカバ リーの完了期間、一貫性の調整、リソースの消費量（ネットワーク帯 域、ディスク帯域、ディスクI/O 回数など）= コスト – 多様なアルゴリズム、プロトコルから選択、システム化 – テストなど、エンジニアリング的な解決が難しい – 形式手法化： correctness criteria (C) 2012 Microsoft Corporation 7
  • 8. 分散システムの適用 ? 複製への適用 – Group safety ? OLTP への適用 – 2PC に代わる atomic broadcast + ローカルト ランザクション – Paxos コミット – Serializability の拡張 ? スケジューリングやリソース管理 – HadoopDB (C) 2012 Microsoft Corporation 8
  • 9. CAP 定理 Revisited ? Consistency: すべてのクライアントは変更があっても同一の ビューを見る ? Availability: すべてのクライアントは障害が発生しても、データ のいくつかの複製を発見することができる ? Partition-tolerance: （分散）システムはネットワークが切断さ れても、その特性を維持する ? 制約： – Partition-tolerance に着目しているサービス提供者向け – Latency の考慮がない – 障害モードでの補償処理をどう考えるか – 必要に応じて ACID、合意プロトコルにより一貫性を取る考え方へ (C) 2012 Microsoft Corporation 9
  • 10. CAP の2特性を選択 C A ? Consistency + Availability ? 単一サイト / クラスタデータベース P ? 通常の RDB など ? Consistency + Partition-tolerance C A ? 分散データベース / 分散ロック P ? HBase、Paxos ? Availability + Partition-tolerance C A ? 分散キャッシュ / DNS P ? Cassandra, eventual consistency (C) 2012 Microsoft Corporation 10
  • 11. 可用性 vs. 一貫性 CAP 定理 (C) 2012 Microsoft Corporation 11
  • 13. データベースの安全性基準 安全性の基準 配送される コミットされ 説明 サーバ数 たサーバ数 無処理 ゼロ ゼロ 0-safety 1 ゼロ トランザクションは1つのサーバに配送され、実行され たがまだコミットはされない。ストレージにトランザク ションの結果が永続化される前にクラッシュすると、ト ランザクションは失われる 1-safety 1 1 トランザクションは1つのサーバに配送され、コミット された。そのトランザクションが他のサーバに送信され る前にクラッシュするとトランザクションは失われる可 能性がある。他のサーバは先のトランザクションの存在 を知らないので、そのトランザクションと衝突する新た な別トランザクションを受け付けられる場合にトランザ クションは失われる Group-safety すべて ゼロ トランザクションはすべてのサーバに配送されるがまだ コミットはしていない。f（0<f<すべて）個以上のサー バがクラッシュすると、トランザクションは失われる Group-safetyか すべて 1 トランザクションはすべてのサーバに配送され、1つの つ1-safety サーバでコミットされた。f個のサーバかつトランザク （group-1- ションをコミットした1つのサーバがクラッシュすると、 safety） トランザクションは失われる可能性がある。データベー スとグループ通信機構を組み合わせたレプリケーション の大部分はここに属する 2-safety すべて すべて トランザクションはすべてのサーバに配送され、コミッ トされた。トランザクションが失われることはない (C) 2012 Microsoft Corporation 13
  • 14. 現状の複製技術 ? Primary-backup ? Update-anywhere ? Master-slave から cohort単位の複製へ Zookeeper Node A Node B Node C Node D Node E key ranges key ranges key ranges key ranges key ranges [0,199] [200,399] [400,599] [600,799] [800,999] [800,999] [0,199] [200,399] [400,599] [600,799] [600,799] [800,999] [0,199] [200,399] [400,599] (C) 2012 Microsoft Corporation 14
  • 15. Primary-Backup プロトコル Alsberg-Day Protocol (C) 2012 Microsoft Corporation 15
  • 16. 全順序化 ? P-B の順序化の例 – viewstamped replication ? 順序化しないと合意が必要な例 – 楽観的レプリケーション 出典： Optimistic Replication (Shapiro, Saito) (C) 2012 Microsoft Corporation 16
  • 17. ROWA (Read One Write All) W=N R=1 読み取りに最適化した強い一貫性 W=1 R=N 書き込みに最適化した強い一貫性 W+R<=N eventual consistency 古いデータの読み取りがありえる W+R>N quorum assembly による強い一貫性。読み取りには少なく とも1つの最新データの複製を含む Read quorum Replica Replica Replica Manger Manger Manger Client Front End Replica Replica Replica Manger Manger Manger Front Client End Replica Replica Manger Manger Write quorum (C) 2012 Microsoft Corporation 17
  • 18. Quorum (定足数) ? Read quorum(RQ) と Write quorum(WQ) の規則 ? |RQ|+|WQ|>N （Read と Write set は重なる） ? |WQ|>N/2 （２つの Write set は重なる） ? Quorum consensus ? CC とは独立、回復プロトコル不要 ? ROWA との比較 ? P-B と ROWA の中間の特徴 ? これからの位置づけ – Byzantine 障害 – 負荷分散 – 契約の一種 (C) 2012 Microsoft Corporation 18
  • 19. データ配置 ? Rack aware – HDFS, MapR ? Geo replication – DHT ? いろいろな一貫性モデルがありえる – ビジネスにどれが適切か？ 出典： Geo-Replication in Large-Scale Cloud Computing Applications (C) 2012 Microsoft Corporation 19
  • 20. Replicated State Machine ? 状態マシン – 状態マシンを壊す要因 ? Paxos – Leader と primary の違い – Learner は合意結果を知らない – 複数の leader の実行と競合 – 1 leader による複数要求の同時実行 – Batching と Pipeline (C) 2012 Microsoft Corporation 20
  • 21. Basic Paxos (1) 複製（状態マシン） Read フェーズ Write フェーズ 提案番号（バロット ID） 複製への反映 過半数 (C) 2012 Microsoft Corporation 21
  • 22. Basic Paxos (2) 複製は合意結果を知らない 障害が疑われると複数の Leader を立てられる（弱い障害検知） 提案番号を大きくする (C) 2012 Microsoft Corporation 22
  • 23. Basic Paxos (3) 複数 Leader 間の競合 (C) 2012 Microsoft Corporation 23
  • 24. Paxos の過半数 ? propose/accept リーダー A リーダー B 間の調整 propose/accept propose/accept ? 提案番号の全順序 Ballot n-1 Ballot n 化 accept propose 時間推移 Ballot n-1 Ballot n ? Ballot 間の合意の accept accept 引き継ぎ 時間推移 (C) 2012 Microsoft Corporation 24
  • 25. replica の過半数 ? Replica 一貫性モデル Replica への Replica への write read – Spinnaker の例 Client Leader Followers Write Acquire LSN = X Propose X to Followers Write log record to WAL & Commit Queue Write X to WAL & Commit Ack X Queue Send Ack to Master Don’t apply to Memtables yet Time Update Commit Queue Apply X to Membtables Send Ack to Client X is not in the Memtable yet. Client can read the latest value at the Leader Reads at Followers see an older value now Asynchronous Commit Message for LSN = Y (Y>=X) Process everything in the Commit Queue until Y and apply to Memtables. Reads now see every update up to LSN = Y (C) 2012 Microsoft Corporation 25
  • 26. Paxos と ZooKeeper ? P-B と RSM の違い ? Primary order の問題 – メッセージ単位のトランザクションスコープ メッセージの安定化 出典： Zab: High-performance broadcast for primary-backup systems (C) 2012 Microsoft Corporation 26
  • 27. A/E 分離 ? Byzantine 障害対応の複製数の削減 ? privacy 出典： ZZ and the Art of Practical BFT Execution (C) 2012 Microsoft Corporation 27
  • 28. Paxos コミット ? TM が Paxos を使い RM の合意を取る ? 2F+1 個のアクセプター (~2F+1 個の TMs) ? 各 RM は prepare 要求に応答 ? If F+1 個のアクセプターがすべての RMs が prepared 状態 になったと確認するとトランザクションをコミット ? 2F(N+1) + 3N + 1 回のメッセージ ? 5 回のメッセージ遅延 Commit Acceptors （1回余計の遅延） RM0 Leader RM0…N 0…2F 2回の永続化 ? F=0 なら 2PC と同じ (C) 2012 Microsoft Corporation 28
  • 29. Vertical Paxos Paxos グループ Paxos グループ 構成要素1 構成要素2 耐障害性、可用性、スケーラビリティ 遅延、運用コストなどを基準に選択 分散システム プロセスメンバー (C) 2012 Microsoft Corporation 29
  • 31. 動的プロセスグループ (C) 2012 Microsoft Corporation 31
  • 32. ビューの同期（１） (C) 2012 Microsoft Corporation 32
  • 33. ビューの同期（２） (C) 2012 Microsoft Corporation 33
  • 34. ビューの同期（３） (C) 2012 Microsoft Corporation 34
  • 35. 2PC に代わる atomic broadcast 2PC に代わり分散システムのメッセージング 受信と配送の分離 ACID の一貫性と永続化が同時に実行される トランザクション リソース クライアント マネージャ read/write 毎 (ROWA) トランザクション毎 ローカル トランザクション の serializability トランザクションデータ操作 Read-only トランザクション commit/abort のアボート (C) 2012 Microsoft Corporation 35
  • 36. 障害時の動作 (1) ROWA ? トランザクション送信中のクラッシュ – トランザクション送信中のビュー変更 Si ① トランザクションデータ操作 ③ ② commit ④ V{Si} → V’{^Si} View 変更あり → V’’{Si} ? トランザクション受信中のクラッシュ ①トランザクションデータ操作 Si ② commit ③ V{Si} → V’{^Si} ? 復旧中のクラッシュ → V’’{Si} Si ① ② ③ (C) 2012 Microsoft Corporation 36
  • 37. 障害時の動作 (2) P-B 運用中の構成変更 古いビューの操作 の片づけ 出典： Dynamic Reconfiguration of Primary/Backup Clusters (C) 2012 Microsoft Corporation 37
  • 39. 次世代アーキテクチャー ? Soft State – Weak Consistency Model – Timeline consistency – Read-your-Writes consistency – Eventual consistency ? NoSQL C, AP (BASE), 非同期 Stateless, Elastic CA (C) 2012 Microsoft Corporation 39
  • 40. CAP 定理の制約を超える ? レイヤリング – CP (Quorum) を AP (期限付きキャッシュ) に載せる ? トランザクションの時間分割から一貫性モデルの時間 調整 (CA の 2PC の制約) – メッセージ安定化のフェイズ – Weak consistency 多数のプロセスですべてのプロセスが更新結果をみなくてもいい状況 異なるプロセスでまだ同期化が実行され ていないので観測結果が異なってよい 同期化しているので P2は最新の x の b が見えないといけない 許容 許容されない (C) 2012 Microsoft Corporation 40
  • 41. 混沌と秩序 A C A C A C BASE ACID BASE ACID BASE ACID Superstep Sync Superstep Sync Superstep Sync 非同期 同期 非同期 同期 非同期 同期 混沌 秩序 混沌 秩序 混沌 秩序 (C) 2012 Microsoft Corporation 41
  • 42. 最適化の方法 ? スケーラブルアーキテクチャーの原則 ? MapReduce の最適化 – Data Intensive Scalable Computing アーキ テクチャースタイルの一例 (C) 2012 Microsoft Corporation 42
  • 43. スケーラブルアーキテクチャーの 原則 データ分割による競合防止 メモリ上の効率利用 分類→分割→配置→集約 index データ構造アクセス ホットスポットの回避 遅延永続化 データ偏在の解決 転送効率化 Co-location、転送プロトコル 簡易検査、圧縮などデータ量の削減 負荷分散 非同期による時間差 並列可能箇所の並列実行 時間順序保証の上 (C) 2012 Microsoft Corporation 43
  • 44. MapReduce の物理最適化 ? ジョブ段数を減らし shuffle 数を削減 ? 前段に寄せることでデータ転送量を減らす – push-down： join－select－projection を select－join－ projection とする ? sum(2,3,1) = sum(sum(2,3),1) ? avg(2,3,1) != avg(avg(2,3),1) ? インクリメンタルな計算に置き換え – semi-join(?) , bloom filter で転送量を減らす – Combiner ? データ偏在の解決、分割法 ? データ構造の最適化（カラム指向 DB など） ? コード/データの共有、キャッシュ ? 動的最適化 (C) 2012 Microsoft Corporation 44
  • 45. 並列の比較 ? 分散並列 MapReduce vs. ローカル並列 カラム指向 – Tuple のキー特性 Row Group 1 c1 c2 c3 c4 c1 c2 c3 c4 11 12 13 14 11 12 13 14 21 22 23 24 21 22 23 24 31 32 33 34 31 32 33 34 41 42 43 44 51 52 53 54 Row Group 2 c1 c2 c3 c4 41 42 43 44 51 52 53 54 (C) 2012 Microsoft Corporation 45
  • 46. 抽象データ(型)の応用 ? ZooKeeper の znode による分散合意 ? Hive によるデータ分析 – RCFile（カラム指向）と SQL 類似のプログラミングモデル ? Apache Spark による各種並列計算（データフロー、BSP な ど） – RDD (Resilient Distributed Dataset) と Scala のプログラミン グモデル ? CRDT (Commutative Replicated Data Type)による共有デー タのスケーラビリティ、分散データの eventual consistency、 グループウェア – CRDT と各種プログラム言語 (C) 2012 Microsoft Corporation 46
  • 47. まとめ ? Big Data の次の基盤の重要な要素技術は何 か？ – CAP 定理 – 分散システム – トランザクション、DB – プログラミング言語やツール（抽象化、最適化、 設計ガイド） – H/W （SSD、ネットワーク） – 特許、IP – 皆さんの挑戦、知恵と協力 (C) 2012 Microsoft Corporation 47