クラウド ネーティブな データ アーキテクチャーの 選択のポイント 萩原正義 @masayh 日本マイクロソフト株式会社 このセッションの目的 1. 過去と現在の技術の誤謬を明らかにする 2. Big Data の “次” の課題を明らかにする 3. クラウドネーティブなアーキテクチャー の方向性を与える * 筆者（≠ Microsoft 社の見解）の解釈を含みます ラムダアーキテクチャ 2 Speed レイヤー 5 1 StreamInsight Serving レイヤー Batch レイヤー 4 3 hadoop HDFS NoSQL/RDB Visualization “Big Data” トレンド • Hadoop、NoSQL、ストリームデータ、データウェアハウスの 最適な選択 • ラムダアーキテクチャー • In-memory データモデル • ワークロード毎のマルチテナント化をする分散システム基盤 • In-memory データベース • ログ（リカバリー）、複製、同時性制御、インデックス • SSD、不揮発メモリー、高速ネットワークなどのハードウェア の進化 いくつかの先進事例 • アーキテクチャーの革新 • N-tier モデルから、Shared nothing、P2P、多重の垂直クラ スター構成、クラスターのマルチ テナント化、geo-replication な ど • プログラミングモデルの革新 • Actor モデル、dataflow、 reactive、agent 指向など • 分散、データモデル統合 • YARN、Mesos • new SQL（VoltDB、NuoDB、Hadapt など） • Anti-caching（H-Store) • Hyder • ハードウェア技術 • Amdahl の法則 • 2.75億 iOPS の SSD (200 iOPS の HDD の 137 万台相当) http://www.hpcwire.com/hpcwire/2013-1018/small_tacc_cluster_set_to_shatter_iops_ceiling.html?featured=top トランザクションの復権 • あらゆる複合的な例外、障害時を想定した “正しい” データ 操作の実行を一般プログラマが保証できるか？ “No ACID Equals No Interest” (Michael Stonebraker 博士) Horizontal partitioning (sharding) Log • DC 間のまたがる規模までの分散トランザクション • 耐障害性、可用性、レイテンシー、スケーラビリティを実現 • CAP 定理の克服 • 実行一貫性、セッション内順序、投入順序の保証 など • まだ、OSS では実現できていない 1-7 714 Shards/Partitions ... ... ... アジェンダ • 障害を想定して、一貫性を取り、しかも低レイテンシーを実現 • 耐障害性の保証 • 複製の一貫性（strong consistency） • ネットワーク遅延（ネットワークの非同期性）が前提 • 分散トランザクションのデータ項目間の一貫性（2PC などによる）と、各データ項目の 複製との同一性を組み合わせる • 高可用性の維持、スケーラブルで高スループットを条件にした一貫性 （serializability）の保証 • 低レイテンシーの保証 • 新しいトランザクション概念による再構築 • 一貫性を弱くする方向から強くする方向へ Paxos 分散システムの耐障害性を保証する基本アルゴリズム 複製による耐障害性の原則 • 複製を常に一貫性を保つ • 複製の非一貫性を許容 ネットワーク非同期 性（遅延予見不可） からこちらが現実的 1つでも遠い DC に 複製が存在する場合 は？ 例、火星 障害、応答なし 正常動作 f = 許容される 障害の個数 遠い DC にある複 製はほとんど合意応 答が採用させず、 DR 上問題では？ f+1 2f+1 ノード、ネットワーク障害がある合意 全体 N 個のうち、 W 個だけ一貫性が 取れていれば他は 非一貫でいい R R W N=5, W=3, R=3, f=2 (1) W+R > N (2) W > N/2 リーダー（正常） 障害、応答なし 正常動作 W W’ ネットワーク遅延がある合意 ノードに到着順に ACK を返すことで、書き込み クォーラムを達成 m2 ACK NG p NG NG これを prepare の 読み取り（R）と accept の書き込み （W）の２回行うの が、Basic Paxos の ２相プロトコル q r s t ACK m1 ACK m2 は m1 より先に到着し ているが、各ノードへの到 着時間のばらつきで、m1 が先に合意を得る 可用性と一貫性のトレードオフ ネットワーク障害を例に 過半数のサブネット でのみ、新しいリー ダーを選出可能 CAP 定理の CP 古いリーダーが半数 以下のサブネットに あった場合は、合意 を進められない ノード障害時の引き継ぎ • ノードやネットワーク障害を検知したノードが過半数ノードからリーダーの合意 を得て、新リーダーになる • 新リーダーは、過半数ノードが属するサブネットに所属し、スプリットブレインを回避 • 現リーダーが過半数ノードが属するサブネットになければ、新しい合意は得られない = 過半数に満 たないサブネットでは可用性がない • 同時に複数ノードがリーダーになることもありえる • 障害回復後にもデータ更新が有効（更新の衝突問題がない） • 新リーダーは古いリーダーが合意済み、処理中の合意を引き継げる リーダー（正常） 障害、応答なし 正常動作 W R 最新の書き込み が読めるノード (正常） 全順序化 • 分散システム全体で1個以上の最新の書き込みを保持 • 分散システム全体で共有するグローバル変数（外部からは見えない） • 分散プロトコル上、どこかのタイミングでグローバル化が必要 • 衝突するデータ操作順の保持が必要（例、書き込み順） • グローバル化に伴い順序化（全順序化） 同一スロット番号への 書き込み W’ はブロック なしに排他されて、再試行 W’ PREPARE （読み取りフェーズ） 最新の書き込みを 読み取り、その要 求番号+1を新しい 要求として要求 リーダー（正常） 障害、応答なし 正常動作 W ACCEPT （書き込みフェーズ） R 最新の書き込み が読めるノード (正常） Serializability 同時実行トランザクションのスケジュールの正しさを保証する基準ルール Strong consistency と serializability • 耐障害性、可用性を持つ strong consistency • ノード障害、ネットワーク障害、ネットワーク遅延で合意可能 • リーダーの failover、failover 中の障害でも合意結果が引き継げる • 要求の合意の全順序化 • ノード障害によってデッドロックしない • 合意結果には、半数以下のノードサブネットからの要求は影響しない（スプ リットブレインを起こさない） • Strong consistency はコミット済みトランザクション、トランザク ションの複製によるリカバリーを、serializability は同時実行トラン ザクションのスケジュールを管理 • 複製によるバックアップされるログに基づき、トランザクションは serializability により正しく実行される Scheduler/Lock manager の構造 分散トランザクション実行 複製制御プロトコル 分散同時性制御 プロトコル ローカルリカバリー プロトコル Data Item List of Locks Wait List x [T1,r] [T2,r] [T3,w] y [T4,w] [T5,w] [T6, r] Snapshot isolation • 読み取りと書き込みは互いにブロックしない First Committer Wins ルール Time Operations in tx1 • トランザクション開始時点にコミット済みト ランザクションのスナップショットを取る 100 BEGIN TRAN • データ設計上の考慮 102 … Time 100 101 102 Contents of Operations in Tab tx1 r1 BEGIN TRAN r1 … SELECT FROM r1 Tab 103 104 r1, r2 r1, r2 105 r1, r2 106 r1, r2 Operations in tx2 BEGIN TRAN INSERT Tab VALUES (r2) * returns (r1) … COMMIT … SELECT FROM Tab * returns (r1) COMMIT 101 … Operations in tx2 BEGIN TRAN UPDATE r1 – success UPDATE r1 – error … – tx1 is aborted 104 COMMIT – success 103 読み取りトランザクションの介在による異常 T1 （Y を更新） T2 （X を更新） 更新後の Y のスナップショット T3 （X,Y 読み取り） http://blogs.technet.com/b/dataplatforminsider/archive/2013/10/01/in-memory-oltp-programmability-concurrency-and-transaction-isolation-for-memory-optimized-tables.aspx Snapshot のライフタイム 時間 同時実行トラ ンザクション 同時実行トランザクション 同時実行トランザクション 論理的な読み取り 複製全体で単一コミット順序を強制 コミット済みト ランザクション Snapshot の 済み取りセット/ 書き込みセット の更新のコミット時点 論理的な書き込み （コミット順の協調解決） Snapshot isolation を実行する現トランザクション トランザクション 最初の読み取り 複製にすべての読み取り 書き込み 開始時点 の実行時点 セットのコミット更新が の実行時点 伝搬した時点 コミット済みを待機しないので 低レイテンシー、高スループット 弱い一貫性（投機的実行） 読み取り後の更新の確率が 低くアボート率が下がる すべての分散 トランザクション 参加者への書き込み が終了し、consistent な snapshot が完成 複製の snapshot Replicated (Serializable) Snapshot Isolation • 論理的な書き込みでブロード キャストで複製に伝搬 • ローカルと他のリモートでの同 時実行トランザクションとのス ケジュールを検証 • 事例： • T1=w1(x), T2=w2(y), T3=w3(x), T4=r4(x), r4(y), T5=r5(x), r5(y) • T1,T4 は RA ローカル、T2, T3, T5 は RB ローカル 出典： Snapshot Isolation and Integrity Constraints in Replicated Databases 一貫性を調整する • Snapshot には3段階の正しい一貫性がある • 段階の強さに応じて実行性能 vs. 正しさのトレードオフがある • 弱い方から（非 serializable であってもすべて可能） • コミット済みトランザクション（avoiding cascading aborts） • コミット順序で更新が順序化（monotonicity） • 読み取りセットの複数データ項目間のコミット済みトランザクション からの読み取り一貫性（consistent） • Serializable と Snapshot Isolation を組み合わせる • Isolation level をワークロードに割り当てる • Read-only トランザクションへの考慮 最新動向 地球規模クラウドへの適用例 耐障害性、高可用性、低レイテンシーを維持しつつ Geo-replication とは • 次世代の大規模 Web サービス の方向性 • ハイブリッドクラウドの進展 • Geo-replication の課題とは？ • 可用性のための複製とその一貫性 の両立 • ネットワークの障害、遅延 • いわゆる CAP 定理の克服 Parallel snapshot isolation “Walter” 同期複製 出典： Transactional storage for geo-replicated systems 同期複製 Causal Consistency • 特定ユーザが A を実行し次に B を実行、あるユーザの A の実行 を見た別のユーザが B を実行したときの A と B の前後関係が causal （因果）関係で、その関係を保持するのが、causal consistency • トランザクションではなく、（セッションの）R や W 操作の一貫性 A さん w1 r2 論 理 時 間 w3 (W,R)=Read Your Writes • (R,R)=Monotonic Reads • (R,W)=Writes Follow Reads • (W,W)=Monotonic Writes • Causal consistencyでは以下の一貫性を保証できない • トランザクショナルな操作： 銀行送金、注文と決済など • 参照整合性、ユニーク性などの integrity constraints C さん Web クライアントが Write トランザクションに causal 依存関係を含ませる スレッドやリプライ数は高々 100 程度 r4 w5 w6 • （前操作、後操作）の組み合わせに対して、 • B さん r7 操 作 依存関係 w8 w1 w3 w1 w5 - w6 w3 w1 w8 w6 w5 w3 w1 出典： Stronger Semantics for Low-Latency Geo-Replicated Storage Don’t Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS （causal+ consistency) の改良版 Transaction Chains トランザクションの意味的分割 • 分散トランザクション を意味的にマルチホッ プに分割 • 第一ホップ終了で応答す ることで serilaizable と、 低レイテンシーを実現 • オークションの事例 出典： Transaction Chains: Achieving Serializability with Low Latency in Geo-Distributed Storage Systems SOSP 2013 Spanner での snapshot の選択 • 耐障害性、可用性 • Paxos により 複製の snapshot の strong consistency を保証 • 一貫性 • coordinator は Paxos プロトコル上で 2PC を実行＝コミットの分散合意 • prepare で各トランザクション参加者は書き込みの timestamp を coordinator に返し、最大の timestamp をそのトランザクションの timestamp とする • Timestamp によりトランザクション順序、トランザクション間の readsfrom 関係を管理 • 時間管理 • 時間の読み取り誤差の範囲を限定 • 時間ずれの範囲が大きいと、coordinator はトランザクションコミットを待機 させてずれの修正 2PC と Paxos の関係 • Replicated log (Spanner） • NoSQL ベース NoSQL • Replicated commit • トランザクション ベース 2PC Paxos Paxos 2PC NoSQL NoSQL • DC 間の各 shard で Paxos で合意、 shard 間で 2PC で 更新 • Google、OSS ？ RDB RDB RDB • DC 内で 2PC で prepare、 DC 間で shard 毎に Paxos で合意が取れる場合、 各 DC で commit • Microsoft、Oracle ？ 出典： Low-Latency Multi-datacenter database using Replicated Commits, VLDB 2013 最新動向 トランザクション技術の再考 耐障害性、可用性と一貫性を両立するためのトランザクション技術の制約 条件を洗い出し、その制約を持たない実装技術を提案 HAT (Highly Available Transactions) 方向性（筆者注） トランザクション 概念の根底を見直す 出典： Highly Available Transactions: Virtues and Limitations まとめ • 一貫性は極めて重要 • NoSQL、Hadoop はこの観点で見ていく • Serializable から弱い一貫性へ、そこからまた、強い一貫性へ • 地球規模でのトランザクション実行は現実化しつつある • ネットワーク障害、ノード障害、レイテンシーも考慮される • 耐障害性、可用性を最初から考慮しないアーキテクチャーはクラウドネーティブ とは言えない • スケールする複合的なサービスは複数クラスターを組み合わせ、異なるワークロードを 集約したクラスターで実行される • 基本アルゴリズム Paxos の実装は難しく、現実的にはライブラリーの使用 ZooKeeper/Curator、Raft など • ビザンチン障害の考慮、Fail Safe、Anti-fragile … • データベースと分散システムは高度に融合 • Big Dataというくくりではなく、クラウド、サービスのための次世代技術 Microsoft 社の寄与 • Paxos の基本アルゴリズム、関連特許 • Leslie Lamport 博士 http://www.lamport.org/ • Jim Gray 博士 “Paxos Commit” • トランザクション、MVCC の同時性制御の基礎、Hyder などの先進的研究 • Philip Bernstein 博士 "Concurrency Control and Recovery in Database Systems“ • Isolation Level を定義化 • Serializable snapshot isolation • Alan Fekete 博士との共同研究 "One-Copy Serializability with Snapshot Isolation under the Hood" • SQL Server 2014 “Hekaton” による製品化 • Parallel snapshot isolation “Walter” • Transaction Chains © 2013 Microsoft Corporation. All rights reserved. This presentation is for informational purposes only. Microsoft makes no warranties, express or implied, in this summary. このプレゼンテーションは、情報提供のみを目的としています。 Microsoft は、この概要について、明示または暗示を問わず、いかなる保証も行いません。
© Copyright 2024 ExpyDoc
