『データ指向アプリケーションデザイン ――信頼性、拡張性、保守性の高い分散システム設計の原理』Part 2 分散データ
Part 2 distributed data
目的
- Part 1: 単一のマシンにデータを保存.
- Part 2: 複数マシンにデータを保存.
- 複数マシン保存の目的
- scalability: 負荷分散
- 耐障害性,高可用性
- latency
- !1 高負荷へのscaling
- simple: scale up(vertical)
- 共有memory archtecture
- problem: cost upが性能upに対して比例以上.
- 共有disc archtecture
- problem: 競合.ロックのoverheadでscalabilityに制限
- 共有memory archtecture
- !!1 shared nothing archtecture(a.c.a. horizontal scaling, scaleout)
- 利用広がる
- node ← 独立
- bestな費用対効果のマシンを自由に選択
- 地域分散 → latency down, 高可用
- 小企業でも可能
- 制約やトレードオフの認識必要
- merit多いが,applicationが複雑化
- → data modelの表現力に制約生じる
- !!2 replicationとpartitioning
- replication: 冗長性,performance良化
- partitioning(a.c.a. sharding)
- 図Ⅱ-1: e.g.
- simple: scale up(vertical)
Ch05 replication
目的
- 目的
- 地理的近さ → latency down
- 高可用性
- read queryを処理するmachineをscale out → throughputを高める
- dataへの変更の扱いが重要
- single leader, multi leader, leaderless
- tradeoff
- sync, async
- 障害中のreplicaの扱い
- 結果整合性について
- read-your-write, monotonic reads
5.1 leader, follower
目的
- 図5-1 leader base(a.c.a. active-passive, master-slave) replication
- replication log, or 変更streamの一部としてleaderがfollowerに送信
- e.g.
- PostgreSQL, MySQL, Oracle Data Guard, SQL Server AlwaysOn可用性groupなどのrelational db
- MongoDB, RethinkDB, Espressoなど非relational db
- KafkaやRabbitMQ高可用性queueなどのdistributed message brokerもこのarchtectureを利用
- DRDBなどnetwork filesystemやreplicationを行うblock deviceにも同様のものある
対応
- !1 sync/asyncのreplication
- 図5-2: sync/asyncのfollower各1つ
- 通常は1つのみsync, 他はasync
- semi-synchronous
- 完全asyncも多い
- sync型の変種: chain replication @ Azure Storage
- !2 新しいfollowerのset up
- snapshot
- snapshotのreplication log上の位置: log sequence no.(@PostgreSQL), binlog coordinates(@MySQL)
- → catchup
- snapshot
- !3 nodeのfaultへの対処
- !!1 followerの障害: catchup recovery
- !!2 leaderの障害: fail over
- !4 replication logの実装
- !!1 statement baseのreplica
- problem多い,compact〇
- e.g. MySQL, VoltDB
- !!2 Write-Ahead Log(WAL)の転送
- e.g. PostgreSQL, Oracle
- 欠点: logはとても低レベル → storage engineとの結合強い
- → version mismatchがよくない → upgradeにdowntime必要
- !!3 login(行base) log replication
- logic log ←→(独立) storage engineの(physical) log
- e.g. MySQLのbinlog
- 互換性〇.外部applicationのparse〇 → DWHや,custom indexやcacheの構築に〇
- → 変更データのキャプチャ → Ch11
- !!4 trigger base replication
- !!1 statement baseのreplica
5.2 replication lagにまつわるproblem
目的
- 読み取りscaling archtecture
- async replicationのみ
- 「eventual consistency(結果整合性)」と非一貫性のproblem
対応
- !1 自分が書いた内容のread
- 図5-3: read-after-writeの必要性(a.c.a. read-your-write)
- 多くの方法
- userが変更しうるものはleaderから,他はfollowerから
- 更新時刻の追跡.@user, replica
- logicalなtimestampもreal system clockも使える
- cross-device read-after-write 一貫性
- metadataの集中配置
- routing
- !2 monotonicなread
- 図5-4: より過去の情報の取得
- eventual consistencyよりは強い一貫性を保証
- 各userが各々同じreplicaからread
- !3 一貫性のあるprefix read
- 図5-5: e.g.
- !4 replication logへの対処
- dbがreplicationのproblemに対処 → transactionの意義.→ 強い保証を提供
5.3 multi leader replication
目的
- multi leader(a.c.ca. master-master, active-active replication)
- leader base replicationの自然な拡張
対応
- !1 multi leader replicationのUseCase
- !!1 multi datacenterでの運用
- !!2 offlineで運用されるClient
- 各deviceがleaderとしてactするlocal dbを持つ
- → 全device上でasyncのmulti leader replication processingあり
- 実装が困難
- CouchDBは,このような運用に応じたdesign
- !!3 collaborativeなedit
- !!2のoffline editと多くの点で共通
- !2 writeのconflictのprocessing
- 図5-7: e.g.
- !!1 syncのconflict detectとasyncのconflict detect
- !!2 conflictの回避
- あるrecordへのwriteは同じleader
- 多くのケースで推奨
- !!3 一貫したstateへの収束(convergent)
- 各writeにunique ID → Last Write Wins(LWW)
- → 損失リスク大の手法
- replicaにunique ID →↑
- 値のマージ
- 全ての情報をstoreするdata struct → conflictを記録
- → application codeで解決. ← userに確認要求
- !!4 customのconflict resolution logic
- !!5 Whats's Conflict?
- → Ch07, Ch12
- !3 multi leader replicationのtopology
5.4 leaderless replication
目的
対応
- !1 when a node is down, write to db
- 図5-10
- read requestも複数nodeに送る
- !!1 read repairと反entropy
- read repair: readがoftenなとき〇.ただし耐久性低い.
- Anti-entropy処理.
- background processing.遅延あり・
- !!2 writeのためのQuorum
- w + r > n を満たすwrite, read → Quorum read(or write)
- ingeneral: nはodd, w=r=(n+1)/2
- 図5-11: e.g.
- !2 Quorumの一貫性の限界
- w + r <= n → 低latency, 可用性up
- w + r > nでもoldなvalueが返るケース
- → 絶対的な保証ではない.結果整合性〇
- → transactionや合意が必要
- !!1 delayのmonitoring
- replicaのhealthnessについてのalert要
- leaderlessでは難しいmonitoring
- 結果整合性の「結果」の数値化が重要
- !3 sloppy quorum, hintつきhandoff
- leaderless replication: 高可用性と低latencyがdesire
- sloppy quorum: writeの可用性upに重要
- optionとなる
- !!1 multi datacenterでの運用
- leaderless replicationも〇
- e.g. Cassandra, Voldemort
- leaderless replicationも〇
- !4 並行writeのdetect
- 図5-12: case e.g.
- !!1 LWW
- Cassandra, Riakのoption
- 耐久性のコスト
- data lossが×なら不十分
- keyがimmutableなときのみ安全
- !!2 happens-before relationと並行性
- happens-before(因果関係あり) ←→ 並行
- 2者間不関知 → 並行
- !!3 happens-before relationの補足
- version no.の使用
- !!4 並行で書き込まれた値のマージ
- 並行の値: sibling
- tombstone for delete
- siblingのmergeは複雑
- → 自動でmergeできるdata structureがdeveloped
- e.g. RiakのCRDT
- !!5 version vector
まとめ
- replicationの目的
- 高可用性
- 切断stateでのmanupulation
- latency
- scalability
- 難しい問題多い
- replicationの3つのapproach
- single leader replication
- multi leader replication
- leaderless replication
- replication logへの対応
- read-after-write一貫性
- monotonicなread
- 一貫性あるprefix read
- multi leaderやleaderlessでの並行性のproblem
Ch06 Partitioning
目的
- 非常に大規模なdatasetやqueryのthroughputがとても高い
- 目的: scalability
6.1 Partitioning, replication
目的
- 図6-1: replicationとpartitioningのcombination
6.2 K-V dataのpartitioning
目的
- 目標: dataとqueryの負荷をノード間で均等に分散
- 一部の負荷大: skewなstate, 一部: hotspot
- → hotspotを避ける.
対応
- !1 keyのrangeにもとづくpartitioning
- !2 keyのhashにもとづくpartitioning
- !3 workloadのskewとhotspotの軽減
- applicationがskewを抑える必要
- 負荷が集中する少数のkeyに限定 → n倍のkeyをreadなど,管理のための処理増
- 分割されたkeyの追跡必要
- 将来的には,datasystemが自動でskew workloadを検知 → 対処
6.3 Partitioning, Secondary index
目的
- secondary indexは,SolrやElasticsearchなどの検索serverの存在意義(レーゾンデートル)
- secondary indexとpartitioningの対応づけのproblemに対応
対応
- !1 documentによるsecondary indexでのpartitioning
- 図6-4: e.g.
- documentでpartitioningされたindex: local index
- queryはすべてのPartitionに送る必要: scatter/gather
- 負荷極大のケースアリ
- e.g. MongoDB, Riak, Cassandra, Elasticsearch, Solr Cloud, VoltDB
- !2 語によるsecondary indexでのpartitioning
6.4 Partition のrebalancing
目的
- 負荷をcluster内のあるnodeから別のnodeに移行: rebalancing
- 要求
- 負荷がcluster内node間でfairに分配
- rebalancing中も,dbはread/writeを受け付ける
- node間のdataの移動は最小限.rebalancingは高速でnetworkやdisc I/Oの負荷を最小にする.
- 要求
対応
- !1 rebalancingの戦略
- !!1 取るべきでない方法: hashの剰余
- node数に場所が依存
- !!2 Partition数の固定
- 図6-6: balancingの前後
- Partitionのnodeへのアサインのみ変わる
- e.g. Riak, Elasticsearch, Couchbase, Voldemort
- Partitionの数は固定が多い
- → datasetの合計サイズに大きな変動があると,設定が難しい
- 図6-6: balancingの前後
- !!3 dynamicなPartitioning
- HBaseやRethinkDBなど,keyのrangeによってPartitioningされたDBは,dynamicにPartitionを作成
- BTreeのtop level と似た処理
- 固定 number (Partition)と同じく,各nodeは複数Partitionを扱える
- dynamic Partitioningのメリット
- Partitionの数をdataの総量に適合
- 事前分割も可能
- keyのrangeとhash Partitioningどちらにも〇
- e.g. MongoDB
- !!4 node数に比例するPartitioning
- metadataのoverheadを低く抑える by 新しいhash function
- e.g. Cassandra, Ketama
- nodeあたりのPartition数を固定
- hash baseのPartitioning → Partitionの境界をランダムに選択
- ↑ context hash法の元々の定義に近い
- !!1 取るべきでない方法: hashの剰余
- !2 運用: 児童のrebalancingと手動のrebalancing
- 自動化と児童のフォールト検知の組み合わせ
- → カスケード フォールトのリスクあり
- どこかで人の処理があった方が〇
- 自動化と児童のフォールト検知の組み合わせ
6.5 requestのrouting
目的
- service discoveryのproblem
- 図6-7: 3つの方法
- routingのjudgeを行うcomponentがどのようにしてPartitionのnodeへのアサインの変化を知るか
- 図6-8: ZooKeeperを使った,Partitionからnodeへのアサインの追跡
- e.g.
- LinkedInのEspressoは,Helix(relys on ZooKeeper)を使用.routing層あり.
- HBase, SolrCloud, KafkaもZooKeeper
- MongoDBはoriginalのconfig serverとrouting layer: mongos
- CassandraとRiakは,node間でgossip protocol
- Couchbaseは,moxiというrouting層で構成
- auto rebalancingなしのため単純
- connect先IP addressはDNSで十分なこと多い
対応
- !1 parallel queryの実行
- OLAPで使われるMassively Parallel Processing: MPP(大規模並列処理)
- relational dbは複雑なqueryをサポート.
- ↑→ NoSQL distributed datastore: 単一のkeyのread/write
- especially, datasetの大部分へのscanをするqueryで〇.
- OLAPで使われるMassively Parallel Processing: MPP(大規模並列処理)
まとめ
- 大規模なdatasetを小さな部分集合にPartitioning
- dataに適したPartitionのschemaを選択 + rebalancing
- 2つのPartitioningのapproach
- keyのrangeによるPartitioning
- rebalancingはdynamic
- hash Partitioning
- 固定数のPartitionがgeneral. dynamicなPartitioningも使える〇.
- hybridなapproachも可能
- keyのrangeによるPartitioning
- secondary index のPartitioningの2つの方法
- documentによりPartされたindex(local index)
- scatter/gather必要
- WordによってPartitioningされたindex(global index)
- writeで複数Partitionをupdate, readは単一Partitionで処理〇.
- documentによりPartされたindex(local index)
- routing
- 全てのPartitionはほぼ独立に動くようdesign
Ch07 Transaction
目的
- Transaction: 複数read/writeをlogicalな単位にまとめる
- → systemの様々なフォールトへの対処 → 信頼性
- commit/abort/rollback
- Transactionの目的: dbにaccessするapplicationのためのprogramming modelを単純にする
- → 安全性の保証
- あらゆるapplicationがTransactionを要するわけではない
- Transactionを弱めると,performanceや可用性が上がりうる
- どのような安全性の保障と,それらに伴うcostを見る
- especially, concurrency control
- race condition, read committed, snapshot isolation, serializability
- especially, concurrency control
- 単一ノードのdbにも分散dbにもあてはまるproblemを見る
7.1 Transactionというとらえどころのない概念
目的
- MySQL, PostgreSQL, Oracle, SQL Serverとも,IBMがSystem R(1975)に導入したものに似ている
- 非relational dbは,Transactionをはるかに弱い保証群として再定義
- Transactionにはどちらでもないメリットと制限がある
対応
- !1 ACIDの意味
- Atomicity, Consistency, Isolation, Durability
- 実情は,ただのマーケティングワード
- ACID ←→ BASE(Basically Available, Soft state, Eventual consistency)
- BASE: 「ACIDでない」という意味のみ
- !!1 Atomicity
- concurrencyとは無関係
- commit or abort・rollback
- → abortabilityが本来の意味をよくとらえる語
- !!2 Consistency
- dataについて常に真でなければならない何らかの言明・不変性がある
- e.g. 貸借一致
- → applicationの特性でありdbの特性ではない
- CAP定理では,線形化可能性の意味
- dataについて常に真でなければならない何らかの言明・不変性がある
- !!3 Isolation
- concurrencyのproblem, race condition
- 図7-1: e.g.
- a.c.a. serializability(直列化可能性)
- performanceのproblemのため,実際は使われない
- snapshot分離というserializabilityより弱い保証もある
- !!4 Durability
- written dataはlostしないことを保証(完全はありえない)
- discへのwriteとreplication → 多くの手法を併用すべき
- !2 単一Objectと複数Objectの操作
- multi Object Transaction
- !!1 単一のObjectへのwrite
- storage engineは,単一nodeにおける単一Objectのレベルで,Atomicity(← log), Isolation(← ロック@ Object)を提供
- 一部: increment操作などのさらに複雑なatomic操作
- 広く使用: compare-and-set
- 複数Clientが並行に同じObjectにwriteしたときの更新lossを防ぐ
- 通常,Transactionとは,複数Objectへの複数操作を1つの実行単位としてグループ化する仕組み
- !!2 複数ObjectのTransactionの必要性
- 多くの分散データストアでは放棄
- relational data model, document data model, secondary indexでの必要性
- !!3 errorとabortの処理
- Transactionの重要な機能: error時にabort.安全にretry
- aborted Transactionのretry: simple & effectiveなerror処理の仕組み.ただし完全でない
- 別途重複排除必要
- 過負荷へのexponential backoffが必要
- eternal errorへのretryは×
- 2相コミットが必要なケース ← DB外副作用
- Clientのprocessing downは×
7.2 弱いisolation level
目的
- ある種(not all)concurrency problemへの保護のみのsystemがgeneral
- ↑→ serializableなisolation: performance重い
- → bugもありうる
- → concurrencyのproblemの種類と回避策をし折る
- → 信頼でき正しく動くapplicationを,手の届くtoolsで構築
対応
- !1 read committed
- 2つの保証
- ①dirty readなし
- ②dirty writeなし
- most basical levelのTransaction isolation
- !!1 dirty readなし
- 図7-4: e.g.
- dirty read回避のメリット
- 複数Objectの更新
- rollback
- !!2 dirty writeなし
- いくつかのconcurrency problem回避
- 図7-5: e.g.
- counterのincrementのproblem(図7-1)は回避不可能
- いくつかのconcurrency problem回避
- !!3 read committedの実装
- e.g. Oracle11g, PostgreSQL, SQL Server 2012, MemSQL etc.
- 行levelロックが一般的
- ほとんどのDBでは,図7-4のようなapproach ← 旧新2つを保持
- read committed isolation levelのためのロックは,IBM DB2と,read-committed snapshot=offのSQL Serverのみ
- 2つの保証
- !2 snapshot isolationとrepeatable code
- 図7-6: read-committedで生じるbug
- non repeatable read(a.c.a. read skew)
- skew: timingの異常. ≠ hotspotによるskew
- temporary not consistencyが×なケース
- backup
- Analytic queryとconsistency check
- → snapshot isolationで対処
- 各Transactionがconsistentなsnapshotからread
- 長時間のreadだけのqueryに有益
- e.g. PostgreSQL, Storage engineとしてInno DBを使うMySQL, Oracle, SQL Server etc.
- !!1 snapshot isolationの実装
- readはwriteをnot block, writeもreadをnot block
- MVCC(Multi-Version Concurrency Control)と呼ぶ
- 図7-7: PostgreSQLでのsnapshot isolation by MVCC
- !!2 Consistent snapshotを見るためのvisualize rule
- Objectが見えるcondition
- overheadを小さく抑える.一貫したsnapshotを提供
- !!3 indexとsnapshot isolation
- append-only/copy-on-writeなど,実装の細部
- !!4 repeatable readとnameの混乱
- readのみのTransactionに特に有益
- 別名多い @Oracle → SERIALIZABLE, @MySQL,PostgreSQL → Repeatable Read
- SQL Standardのisolation levelの定義は欠陥
- Repeatable Readの正式な定義を満たす実装はほぼない
- !3 更新のlostの回避
- clobber(ひっぱたく)
- !!1 atomicなwrite
- 最もよい選択肢
排他ロック,カーソル固定(stability)
ORM frameworkでは,unsafeなread-modify-write cycleが起こりうる
- !!2 explicit lock
- applicationによるlock
- 例7-1
- 実装複雑
- !!3 更新のlostの自動検知
- snapshot isolationとの併用が効率的
- Transaction Managerが検知 → abort → retry
- applicationが特別な処理の呼び出し不要 → 素晴らしい.
- !!4 compare-and-set
- snapshotからのreadがあるときは注意
- !!5 conflictのresolutionとreplication
- compare-and-setは×
- siblingを生成〇 → 事後にconflictのresolutionやマージする
- 交換可能な操作 → atomicな操作〇 @ replication
- LWWは×だが,多くのDBでdefaultになっている
- !4 write skewとphantom
- 図7-8: e.g.
- serializationかexplicit lock(→ !!1 what's write skew)
- !!2 write skewのほかの例
- 例7-2: 会議室予約システム
- e.g. multiplayer game.利用するusernameの要求.2重支払いの防止
- !!3 write skewを生じさせるphantom
- phantom: あるTransactionのwriteがほかのTransactionのreadに影響
- !!4 conflictの実体化
- lock集合のtable作成: 最後の手段
- → serializable isolation levelの方がはるかに◎
7.3 serializability
目的
- race conditionに弱いTransactionにかんするproblem
- isolation levelの理解難しい.DBごとに非一貫
- safeかどうか判定が難しい
- race condition detectのためのtoolなし
- serializable isolation: 最も強いisolation level
- → 考えられる全race conditionを回避
- implementとperformanceのproblem
対応
- !1 完全な順次実行
- 単一threadでTransactionを処理 → serializable isolation level
- RAM price down
- OLTP Transactionは短く少ないread/writeしかない
- e.g. VoltDB/H-Store, Redis, Datomic
- lockによる調整のoverheadなく,高性能たりうる
- !!1 SPへのTransactionのencapsulate
- Transactionは1つのhttp request内でcommit
- 単一threadで順処理では,外部とのやり取りを行う複数文を含むTransactionをprohibit
- → 代わりにSPとして登録 → dataがmemoryにあれば極めて高速
- 図7-9
- !!2 SPのmerit, demerit
- !!3 Partitioning
- 複数PartitionにまたがるTransactionでは,SPのthroughputは数桁down
- !!4 順次実行のまとめ
- Transactionの順次実行がserializable isolation level実現のための制約
- 全Transactionが小さくて高速
- activeなdatasystemがメモリに収まるUseCase → or, anti caching
- write throughputが,単一のCPU coreで十分処理できる程度には低い
- or Partitionをまたぐ調整なしにTransactionをPartitioningできる
- PartitionをまたがるTransactionでは,hard limitを設けられる
- Transactionの順次実行がserializable isolation level実現のための制約
- 単一threadでTransactionを処理 → serializable isolation level
- !2 two phase lock(2PL)
- 30年間唯一のserializable isolation levelのための2PL ← 特にSS2L(Strong Strict Two-phase Locking)と呼ぶ
- 2PL ≠ 2PC(Commit)
- writerはほかのwriterに加えてreaderをブロック
- readerもwriterをブロック
- ↑→ snapshot isolation level
- → すべてのrace conditionへのguardを提供
- !!1 2PLの実装
- e.g. MySQL(InnoDB), SQL Serverのserializable isolation level, DB2のrepeatable read isolation level
- shared modeとexclusice mode
- deadlockのproblemと対応
- 自動の対応
- !!2 2PLのperformance
- performanceはbad
- ↑ 多くのlockのoverheadと,concurrencyの低下
- latency不安定 → 高p値の速度低い
- !!3 predicate(述語) lock
- phantomに対しても適用可能
- !!4 index range lock(a.c.a. next-key lock)
- preciseではないが,overheadははるかに低い
- !3 serializableなsnapshot isolation(SSI)
- 完全なserializableかつsnapshot isolationよりperformance〇
- 2008~
- e.g.
- 単一node: PostgreSQL 9.1~
- 分散DB: FoundationDB
- !!1 pessimisticなconcurrency controlとoptimisticなconcurrency control
- pessimistic: 相互排他(multithread programmingでdata structureを保護)に似ている.
- ↑ 順次実行
- optimistic ← SSI
- 十分な要領でtransaction environmentの競合がそれほど高くない → performance〇
- 競合: 交換可能なatomicな操作で減らせる
- snapshot isolationの上に,write間のserializableのconflictの検知アルゴリズム
- pessimistic: 相互排他(multithread programmingでdata structureを保護)に似ている.
- !!2 古くなったpremiseにもとづくjudge
- premise: transactionのstart時は真だったfact
- readとwriteの因果を示す必要
- 要考慮点
- 古いversionのMVCC Objectのreadのdetect(!!3)
- 前のreadに影響sるwriteがあるときのdetect(!!4)
- !!3
- snapshot isolation level ← MVCCで実装
- 図7-10: e.g.
- !!4
- 図7-11: e.g.
- !!5 SSIのperformance
- reader, writer間はブロックなし
- latency予測〇, 変動小さい
- readのみのqueryはロック不要
- 単一CPU coreのthroughputにunlimited
- 複数マシンのPartitioningにも対応
- read/write transactionは極短がneeded
- 2PLや順次実行ほどは,低速なtransactionの影響なし
- reader, writer間はブロックなし
まとめ
- Transaction: abstractionのlayer
- concurrencyやhardware, softwareのproblemを隠す
- → simpleなtransactionのabortにまとめる → retryのみでOK
- concurrency controlのlevel
- read committed
- snapshot isolation(a.c.a. repeatable read)
- serializable
- race conditionとisolation level
- dirty read/write
- non repeatable read(a.c.a. read skew)
- MVCC
- 更新のlost
- write skew
- phantom read
- 全てをresolveはserializable isolation levelのみ
- 〇順次実行
- ×2PL
- 〇SSI
Ch08 distributed systemのproblem
目的
- distributed systemと単一マシンsystemの根本的違い
8.1 faultと部分fault
目的
- 単一マシン: 決定的
- distributed system: 部分fault → 非決定的
- 成功したか分からない
対応
- !1 Cloud computingとsuper computing
- 大規模なcomputing systemの構築方法の哲学のスペクトラム
- HPC(High Performance Computing)
- 演算中心型のscientific calculation task
- cloud computing
- traditionalな企業datacenterは,この間のどこか
- HPC(High Performance Computing)
- → フォールトへのapproach異なる
- softwareにフォールトtoleranceの組込必要
- 信頼性のないcomponentからtrustnessあるsystemを構築
- 様々なフォールトへのテスト必要
- 大規模なcomputing systemの構築方法の哲学のスペクトラム
8.2 低trust network
目的
- shared nothing system by network
- internetとdatacenter内の大部分の内部network(Ethernet)は,async packet network
- 図8-1
- 各problem ^ timeoutでの対応
- internetとdatacenter内の大部分の内部network(Ethernet)は,async packet network
対応
- !1 networkのfaultの実際
- networkの分断: network partition, netsplitと呼ぶ
- 必ずしもtolerantである必要はない
- networkのproblemへの反応の認識が重要
- networkの分断: network partition, netsplitと呼ぶ
- !2 faultのdetect
- requestのsuccessは,applicationからのproperなresponce以外確認不可能
- errorはtimeoutでjudge
- requestのsuccessは,applicationからのproperなresponce以外確認不可能
- !3 timeoutと限度のない遅延(unbounded delay)
- !4 sync networkとasync network
- sync networkでは,bounded delay by 回線,connection
- !!1 network delayの予測
8.3 低trust clock
目的
- 期間と時点
- 時間の複雑さ
- clockのsync
対応
- !1 単調increment clockと時刻のclock
- !!1 時刻のclock
- a.c.a. wall-clock time, real time
- NTPとsync
- 解像度のproblem @ 旧マシン
- !!2 単調incrementのclock
- 期間の計測に〇
- 絶対値はno mean
- 各CPU timerは必ずしも同期でない
- slewing: 進ませる頻度の調整
- distributed systemの期間計測に使える.
- !!1 時刻のclock
- !2 clockの動機とaccuracy
- !3 sync clockへの依存
- softwareがclockのずれをmonirtor要
- !!1 順序relationをもつeventのtimestamp
- 図8-3: e.g.
- LWWのproblem
- → logical clockの使用が〇
- 相対順序の決定.単調increment
- ≠ physical clock: 時刻のclockや経過時間を観測する単調increment のclock
- → logical clockの使用が〇
- !!2 clockの値の信頼区間
- !!3 globalなsnapshotのためのsync clock
- distributed system(machine), 複数datacenterなどでのDBにおけるsnapshot isolation levelのproblem @transaction idの生成
- SpannerはTrueTime APIを使い,clockのtimestampをTransaction IDとして用いる
- distributed transactionでのclockのsyncは重要
- !4 processingの一時停止
- distributed systemにおけるleaderの扱い
- leaderがleaseを取得
- lease: timeoutつきlockのようなもの
- leaseについてのclockのproblem
- leaderがleaseを取得
- !!1 responce timeの保証
- hard real time system. RTOS(Real Time OS)
- 組込systemのreal time ←→ Webのreal time
- physicalなものをcontrolするsystem
- worst proceed timeの保証
- cost 極大.performance 悪い
- safetyが極めてimportantな組込deviceを使う
- ↑→ 多くのServer side data proceed system
- hard real time system. RTOS(Real Time OS)
- !!2 GCによるimpactの制限 → 有益
- distributed systemにおけるleaderの扱い
8.4 知識・真実・虚偽
目的
- system model(仮定)を設定して設計する
- distributed systemでの知識と真実を見る
対応
- !1 真実(truth)は多数決で決まる
- 多くのdistributed algorithmはquorumに依存
- !!1 leader とlock
- 図8-4: bugのe.g.
- !!2 フェンシングtoken
- 図8-5: e.g.
- e.g.: ZooKeeperでのzxid, cversion
- Server sideでのtoken chack: 〇
- !2 ビザンチンフォールト(Byzantine)
- nodeはuntrust, but誠実がpreposition
- Byzantine fault-tolerant: attackerへも耐性
- complicate protocol必要.hardware levelでのsupportに依存
- P2P networkでは考慮必要
- !!1 weakなうそからの保護
- !3 system modelと現実
- 3つのmodel
- sync model
- ほとんどのcaseで現実的でない.上限は現実ではないこと多い
- 部分 sync model
- 多くのsystemで現実的
- async model
- 制約強い
- sync model
- nodeについての3つのmodel
- crash stop fault
- crash recovery fault
- Byzantine fault
- 部分sync modelとcrash record faultのペアが一番beneficial
- !!1 algorithmの正しさ
- 性質(properties)によって正しさを定義
- e.g. unique性,単調increment sequence(→ ここまで安全性), 可用性(→ live性)
- !!2 安全性とlive性
- live性: 「eventual」 ←→ 安全性: いつも起こらない
- !!3 現実世界へのsystem modelのmapping
- 実際の実装では,起こりえないことへの対処のcodeが必要
- 理論的分析と実践的testは等しく重要
- 3つのmodel
まとめ
- distributed systemでの幅広いproblem
- 部分fault
- faultのdetect
- quorumが合意するためのprotocolで耐性付け
- distributed systemの目的: scalability, fault-tolerance, low latency
- ↑→ 単一node
Ch09 一貫性と合意
目的
- fault-tolerantなdistributed systemの構築のためのalgorithmとprotocol
- abstractionでproblemを隠蔽が重要
- 重要なabstraction: 合意
- 可不可の限度の認識が重要
- abstractionでproblemを隠蔽が重要
9.1 一貫性の保証
目的
- eventual consistency(convergence(収束性)の方が良い表現) @replicationをするdb
- とてもweakな保証
- boundの認識が重要
- edge case: systemのfaultや,並列性極高のときに生じる
- → より強い一貫性modelを見る
- 対価: performance, tolerance down
- distributed 一貫性modelと,transactionのisolation levelの階層は,focusがそれぞれ独立.
- transactionは,race conditionの回避
- distributedの一貫性は,delayやfaultに際してのreplicaの調整
- ただし,両社は深くrelationあり
- linearizability(線形化可能性): the strongest
- distributed systemでのeventの順序付けの問題
- especially 因果律と全順序(total ordering)のproblem
- atomicityを保ちつつcommit @ distributed transaction
- → 合意のproblemの解決方法
9.2 linearizability
目的
- linearizability: a.c.a. atomic consistency, strong consistency, immediate consistency, external consistency
- dataのcopyが1つしかないように見せる
- recency guarantee(最新性の保証)
- 図9-1: 反例
- recency guarantee(最新性の保証)
- dataのcopyが1つしかないように見せる
対応
- !1 systemをlinearizableにするcondition?
- 図9-2: xはregister. read, write, concurrのe.g.
- 図9-3: concurrencyでの制約.新旧どちらか不明な登録(regular register)
- 図9-4: complicate case ← compare and set
- linearizabilityとserializability
- linearizability
- 個々のObjectに関すること.registerのread/writeでのrecency保証
- serializability
- transactionのisolation.複数Objectを扱う.transactionの実際の順序とは関係なし.
- 共に提供: strict serializability(a.c.a. strong-1SR, strongest one-copy serializability)
- SSIはnot linearizability
- linearizability
- !2 linearizabilityへの依存
- !!1 lockとleader election
- lockはlinearizability must
- e.g. Apache ZooKeeperやetcd. for distributed lock, leader election
- 合意algorithmを使い,fault tolerantを保って,linearizableな操作を実装
- Apache Curatorのようなlibraryが,ZooKeeper上で高レベルの処方を提供. to 多くの繊細なproblem
- → 協調taskの基盤になる
- distributed lockは,Oracle Real Application Clustors(RAC)のようなdistributed db 中で極小levelで使用
- RAC: lockをdiscのpageごとに使う
- linearizable lockは,transaction実行のcritical path
- → db node間communicationに,専用のcluster inter connection networkを使う
- !!2 制約およびuniqueの保証
- unique制約を保証するためのlinearizability
- lockと類似
- unique制約を保証するためのlinearizability
- !!3 cross channel timing依存relation
- 図9-5: e.g. cross channel
- → linearizability 必要
- !!1 lockとleader election
- !3 linearizable systemの実装
- replication for fault-tolerance
- !!1 linearizabilityとquorum
- 図9-6: quorumでのrace condition
- performanceを代償にすれば,linearizableにできる
- compare-and-setは×
- → 不可能と考えてよい
- !4 linearizableにするコスト
- 図9-7: linearizability or availabilityのselection
- !!1 CAP定理
- linearizabilityとavailabilityのtradeoffの議論の出発点
- CAP 3つから2つではなく,C(Consistency: linearizability)かAvailabilityの一方をselect when network fault
- Availabilityには矛盾した複数の定義アリ → CAPは使えない
- linearizabilityとnetwork分断のみを扱うもの
- → historicalなinterestのみある
- !!2 linearizabilityとnetwork delay
- 実際にlinearizableなsystemはほとんどない
- e.g. multi core CPUのRAMも not linearizable. without memori barrier or fence
- performanceとのtradeoffのため
- 実際にlinearizableなsystemはほとんどない
9.3 Orderの保証
目的
- 順序付け: important basic concept(概念)
- Ch05, 07, 08
- 順序とlinearizability合意の間の深い関係
対応
- !1 Orderと因果関係
- Orderは因果関係
- e.g. request/responce, 事前発生(Ch05), Consistency, skew(Ch07), 図9-1
- 因果律からのorderに従う: 因果律において「causually consistent」
- e.g. snapshot isolation
- !!1 因果律にもとづくorderと全orderの違い
- incomparable: {a,b}, {b,c}
- → partially ordered(単順序) → {a} ⊂ {a,b}など
- linearizable systemは全order
- 因果律: 半orderを定義
- concurrencyはincomparable
- → linearizable systemにはconcurrencyなし
- concurrency: 枝分かれ.別々の分岐はincomparable
- !!2 因果律の一貫性より強いlinearizability
- linearizabilityは因果関係を暗に含む
- しかし,performanceやavailabilityの大小アリ
- linearizability以外でも因果律は実現可能
- → causually consistencyがnetwork delayで速度が落ちないconsistencyの中でstrongest
- network faultがあっても利用〇
- → ごく最近の研究で扱われている. about causually consistency
- → causually consistencyがnetwork delayで速度が落ちないconsistencyの中でstrongest
- linearizabilityは因果関係を暗に含む
- !!3 因果律における依存関係の補足
- 操作の先行を知る必要: 半order
- nodeのacknowledgeを記述する必要
- version vectorの利用 ← 5.4.4と似ている
- dbがread dataのversionを知ることが必要
- nodeのacknowledgeを記述する必要
- 操作の先行を知る必要: 半order
- Orderは因果関係
- !2 sequencial numberのorder
- sequencial number( or timestamp)でのeventのorderづけ
- timestampはlogical clockで〇
- compactで全orderを提供
- especially, sequencial numberは因果律とのconsistencyをもつ全orderを持たせて生成〇
- e.g. single leader replicationのdbは,replication logがwriteの全orderを規定
- !!1 因果的でないsequencial number生成器
- 単一leaderなし → sequencial numberの発行は,不透明
- 個別のsequencial number発行は,因果律のconsistencyなし
- ↑ 複数nodeでの操作のorder補足不可能
- 個別のsequencial number発行は,因果律のconsistencyなし
- 単一leaderなし → sequencial numberの発行は,不透明
- !!2 Lamport timestamp
- !!3 timestampでのorderづけでは不十分
- Lamport timestampは,distributed systemのgeneral な多くの問題の解決には不十分
- ↑ 操作の全orderは,すべての操作がcollectできたあと
- → unique制約には,操作の全orderでは不十分
- → いつまでに確定するかが重要
- sequencial number( or timestamp)でのeventのorderづけ
- !3 全orderのbroadcast
- problem
- 操作のthroughputが単一leaderでproceedできる以上のもののときのsystem scale 方法
- leaderのfail over
- (↑2つ)→ total order broadcast ( or, atomic broadcast)と呼ぶ
- Partitionごとのleaderのときは,total order broadcastよりさらにcomplicate processingが必要
- total order broadcast: node間のmessage交換protocolとして記述
- 2つの安全性の保障
- trusted cast(配信)
- total ordered cast
- 2つの安全性の保障
- !!1 total order broadcastの利用
- ZooKeeperやetcdのような合意serviceは,total order broadcastを実装
- total order broadcast: dbのreplicationに必要なもの
- ↑ state machine replication
- serializable transactionの実装にも使われる
- messageがcastされた時点で順序確定
- → timestampでのorderingよりstrong
- logの生成とみることも〇
- fencing serviceをserveするlock serviceの実装にも使える
- @ZooKeeperのzxid
- !!2 total order broadcastを使ったserializable storageの実装
- serializabilityとtotal order broadcast(合意のproblem)は密な関係
- total order broadcast: async ←→ linearizabilityは最新性
- but, total order broadcast可能 → linearizable storage構築〇
- linearizable compare-and-set操作は,total order broadcastを,追記のみ行われるlogとして使う
- 全てのnodeが,どれが初めか合意
- → writeのcommitとabortの合意
- → log baseのserializable multi object transactionの実装にも使える
- → writeはlinearizable, readはnot linearizable
- → sequencial consistency(a.c.a. timeline consistency) <(わずかに) linearizability
- readもlinearizableにする方法,approach
- → writeのcommitとabortの合意
- !!3 linearizableなstorageを使ったtotal order broadcastの実装
- linearizable sequencial number generatorを使う ← 合意のalgorithm
- linearizable (increment) compare-and-set registerと,total order broadcastはどちらも合意と等価
- → どちらかをresolve → もう一方にも変換〇
- problem
9.4 distributed Transactionと合意
目的
- consent: distributed computingで,most importantでbasicalなproblemの1つ
- replication, transaction, system model, linearizabilityとtotal order broadcastの上に立つproblem
- node群のconsentがimportantなcase
- leader elegant
- atomic commit
- → atomic commit problem
- consent の不可能性
- FLP帰結(consent不可)は,async system modelでの証明
- 通常のdistributed systemはconsent可能
対応
- !1 atomic commit と2PC
- transactionのatomicity
- !!1 単一nodeからdistributed atomic commitへ
- 単一nodeでのtransactionのcommitは,dataが永続性をもってdiscにwriteされるorderに完全に依存
- data のwrite → commit recordのorder
- read commit isolationのため,commitは消せない
- !!2 2PC
- !!3 約束のsystem
- commit point
- 2つのpoint of no return
- !!4 coordinatorのfault
- in doubt, uncertain
- 図9-10
- coordinatorのrecoveryを待つ必要
- in doubt, uncertain
- !!5 3PC
- 2PC: blocking atomic commit protocol
- 3PC: nonblocking
- but, 制限あり.現実にはnot atomic
- non blocking. atomic commitはperfect failure detector必要
- 実際は難しい
- non blocking. atomic commitはperfect failure detector必要
- but, 制限あり.現実にはnot atomic
- !2 distributed transactionの実際
- distributed transactionへの2つの評価
- ほかのwayでは提供できない重要なsafenessの保証を提供
- ↑→運用上のproblemの原因.performanceを損ない提供可能以上の約束をしている.
- → 実際は,多くのcloud serviceで,distributed transactionは実装していない
- 2つのdistributed transaction
- db内部のdistributed transaction → 特定の技術固有のoptimise〇
- heterogeneous(不均一な,hetero: other)なdistributed transaction → 特定の技術固有のoptimise×
- 参加者は2つ以上の異なる技術を使う
- !!1 exactly-onceなmessage proceed
- !!2 XA transaction
- X/Open XA (eXtended Architectureの略): heterogeneous technologyでの2PCのstandard
- transaction coordinatorがXA APIを実装
- !!3 in doubt下のlockの保持
- lockのproblemあり
- !!4 coordinatorのfaultからのrecovery
- orphaned(孤立) in doubt transaction
- heuristic decisions を緊急避難ハッチとする実装
- atomicityを破る決定を回避
- !!5 distributed transactionのboarder
- XA transaction: 複数参加者のdata system間consistencyを保つという,realで重要なproblemを解決
- but 運用上の大きなproblemあり
- → transaction coordinator自体が一種のDB
- replication必要
- application serverのstateのproblem
- SSIとともにはXAは×
- db内部のdistributed transactionは制限小さい
- → SSIのdistributed versionはrealizable
- but, distributed transactionはfaultを増幅
- distributed transactionへの2つの評価
- !3 耐障害性をもつconsent
- consent: 非形式的には,複数nodeが何かについて同意すること.
- 形式的には,1つ以上のnodeがpropose → 合意algorithmがそれらの値から1つを決定
- uniform consent
- 4つの性質
- uniform agreement
- integrity(整合性)
- validity(妥当性) (ここまで3つが合意の核.安全性)
- termination(終了性): 耐障害性.(live性)
- 4つの性質
- いかなるalgorithmも,terminationの保証にはat least 過半数のnodeが正常であることが必要
- 安全性は,ほとんどのnodeが×でも保証できる
- Byzantine faultはないことを前提
- !!1 consent algorithmと total order broadcast
- 耐障害性のconsent algorithm
- e.g. ViewStamped Replication(VSR), Raft, Paxos, 2ab
- 形式的modelでなく,値の並びに決定 → total order broadcast
- → × 1つの値ごと, 〇 各orderでconsent → effective
- 耐障害性のconsent algorithm
- !!2 single leader replicationとconsent
- leader electionのためにleader必要
- !!3 epoch numberとquorum
- epoch: a.c.a. ballot, view, term
- 2 roundのvote(ballot)
- electionと2PCの違い → consent algorithmの正しさと耐障害性のkey
- coordinatorは2PCではnot elect
- 2PCではすべての参加者 ←→ 耐障害algorithmでは過半数
- epoch: a.c.a. ballot, view, term
- !!4 consentのbound
- consent algorithm: distributed systemの大きなbreakthrough
- すべてが不確定なsystemに,強い安全性(3つ)と耐障害性を与える
- total order broadcastを提供.耐障害性を保ちつつlinearizable and atomicな操作を実装
- performanceとcostのproblem → 使われないcaseあり
- 非固定集合では,sync membership extention必要
- timeout依存 → network delay大のcase → performance×
- e.g. Raftなど
- → 低trust networkに対する耐性アリのalgorithmは研究中
- consent algorithm: distributed systemの大きなbreakthrough
- consent: 非形式的には,複数nodeが何かについて同意すること.
- !4 membershipと強調service
- ZooKeeperやetcd: distributed key-value store, 協調および設定service
- 完全にmember内に収まる少量のdataを保持
- 耐障害total order broadcastを使って全nodeにreplication
- ZooKeeper ← GoogleのChubby
- total order broadcast 以外の機能群あり
- linearizable and atomicな操作
- 操作の全順序
- fencing token
- fault detect
- ephemeral node ← sessionがもつ任意ロック
- 変更通知
- 通知をsubscribe
- !!1 nodeへの処理のassign
- ZooKeeper/ Chubbyがeffectiveなcase
- processing/ serviceの複数インスタンスからleader, primaryをelect
- Job Schedulerやほあkのstateful systemでも〇
- partitioningされたresource(db, message system, filestorage, distributed actor system etc.)
- どのnodeにどのpartitionをassignかjudge
- processing/ serviceの複数インスタンスからleader, primaryをelect
- ZooKeeperのatomic操作, ephemeral node, 通知により達成可能
- Apache Curatorのようなlibraryあるが,簡単ではない
- ZooKeeperはnode間協調作業をoutsourcing
- applicationのstateをnode間でreplication → Apache BookKeeper
- ZooKeeper/ Chubbyがeffectiveなcase
- !!2 service discovery
- ZooKeeper, etcd, Consul
- linearizability不要なread requestにresponceできる
- !!3 membership service
- consentとfault detectの組み合わせ
- どういったnode群でmembershipが構成されているか.Systemでconsent生成は有益
- ZooKeeperやetcd: distributed key-value store, 協調および設定service
まとめ
- 一貫性とconsent
- linearizability ← 一貫性model
- 因果律
- 全eventのorder
- 弱い一貫性model
- 分岐と合流のversion history
- → consentのproblem
- 合意のproblemと等価なもの
- linearizable compare-and-set register
- atomicなtransactionのcommit
- total order broadcast
- lockとlease
- membership/ 協調service
- unique制約
- single leaderがin faultのcase
- leaderのrecovery待ち
- XA/JTA transaction coordinator
- 終了性なし → consentを解決しない
- 手動fail over
- 低速
- algorithmで自動に新leader elect
- consent algorithm
- networkの状況に対処必要証明
- leaderのrecovery待ち
- 耐障害性をもつconsentのためのalgorithm system
- ZooKeeper
- consent不要なcase
- multi leader replication system
- 単にlinearizabilityなしに対処.分岐や合流を伴うversion historyをもつdataを扱えばよい.
- multi leader replication system