『データ指向アプリケーションデザイン ――信頼性、拡張性、保守性の高い分散システム設計の原理』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に制限
    • !!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.

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
  • !3 nodeのfaultへの対処
    • !!1 followerの障害: catchup recovery
    • !!2 leaderの障害: fail over
      • ①leaderのfault check
        • timeout
      • ②新leaderの選出
      • ③新leaderを使うためのsystemのreconfigulation
      • fail overのproblem
        • Clientからの永続性の期待
        • ほかのstorage systemとのdbの内容の連携による問題(e.g. GitHub)
        • split brain
        • timeout値の設定難しい
      • nodeのfault, 低信頼のnetwork replicaの一貫性についてのトレードオフ,永続性,可用性,latencyといったproblem
  • !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
      • triggerやStored Procedureの利用.またはOracle GoldenGateのようにlogをread
      • → より柔軟なreplication
      • e.g. OracleのDatabusや,PostgresのBucardo
      • overhead大,bug起きやすい,組込のreplicationより制約大きい

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での運用
      • 各datacenterにleaderを置く
      • 図5-6: archtecture
      • multi datacenterでのdeployのcompare
        • performance: multi datacenterの方が〇
        • 耐障害性: 各datacenterは独立
        • networkのproblemへの耐性: asyncのmulti leader(syncのsimple leader) → 耐性〇
      • e.g. MySQL, Postgres, Oracleの外部tool
      • 大きな欠点
        • Conflict resolution
        • → 可能背あれば避けるべき危険領域
    • !!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
      • onwrite: e.g. BucardoでPerlを使う
      • onread: e.g. CouchDB
      • transaction全体ではなく,行やdocument単位でresolveする
      • 〇auto conflict resolve → 将来性〇
        • problemのe.g. : Amazon
        • 〇Conflict-free replicated datatypes: CRDTs ← 2way merge
        • 〇Mergeable persistent(永続) data structures
          • e.g. Git ← 3way merge
        • 〇Operational transformation
    • !!5 Whats's Conflict?
      • → Ch07, Ch12
  • !3 multi leader replicationのtopology
    • 図5-8: 構成のe.g.
      • most general: all to all → 耐障害性で他より〇
      • 循環topology: e.g. MySQL
      • star topologyも広く使用
    • all to allのproblem
    • 多くのmulti leader replicationのconflict detect手法の実装は貧弱.
    • → dbで徹底的にテスト必要.

5.4 leaderless replication

目的

  • AmazonDynamoで利用してから流行
  • OSSのdata store: Riak, Cassandra, Voldemort
  • Dynamo Style
  • → dbの利用方法に大きな違い

対応

  • !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
  • !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
      • replicaごとのversion no.
        • e.g. Riak 2.0のdotつきversion vectorized
        • Riakでは,version vectorをcausal(因果) contextというstringでencode
      • vector clockとは微妙に異なる.

まとめ

  • 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がとても高い
    • → Partitioning(a.c.a. Sharding)
    • partitionの別名
      • Shard: MongoDB, Elasticsearch, Solr Cloud
      • resion: HBase
      • tablet: Bigtable
      • vnode: Cassandra, Riak
      • vBucket: Couchbase
  • 目的: 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
    • 図6-2: e.g.
    • e.g.: HBase(OSS) (refers to Bigtable), RethinkDB, MongoDB(ver ~2.4)
    • access patternによってはhotspotが生じる決定ん
    • → keyに工夫が必要
  • !2 keyのhashにもとづくpartitioning
    • Cassandra, MongoDBはMD5, VoldemortはFowler-Noll-Vo
    • 同じkeyで同じhash値はmust
    • 図6-3: keyのhashによるpartitioning
    • 境界も疑似時乱数的に選択: Consistent hash法
      • CDNのようなcache systemで使われる.DBではあまり使われない
    • 均等分散は〇.しかし範囲へのクエリの効率悪い
    • Cassandraでは,先頭列以外ならrange search〇
      • 複合PK
      • 連結indexのapproach: 一対多のrelationに対してelegantなdatamodel
  • !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-5: e.g.
    • 「Word」 ← 全文検索indexから
    • range scanに有利になりうる
    • global index
      • readがeffective, writeが低速で複雑
      • ↑ scatter/gatherが不要
      • ↑ 1つのdocumentが複数Partitionに影響しうる
      • globalなsecondary indexの更新はasync
      • e.g. Riakのsearch機能や,local/global indexを選択できる OracleのDWH

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の合計サイズに大きな変動があると,設定が難しい
    • !!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法の元々の定義に近い
  • !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で〇.

まとめ

  • 大規模なdatasetを小さな部分集合にPartitioning
  • dataに適したPartitionのschemaを選択 + rebalancing
  • 2つのPartitioningのapproach
    • keyのrangeによるPartitioning
      • rebalancingはdynamic
    • hash Partitioning
      • 固定数のPartitionがgeneral. dynamicなPartitioningも使える〇.
    • hybridなapproachも可能
  • secondary index のPartitioningの2つの方法
    • documentによりPartされたindex(local index)
      • scatter/gather必要
    • WordによってPartitioningされたindex(global index)
      • writeで複数Partitionをupdate, readは単一Partitionで処理〇.
  • 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
  • 単一ノードの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定理では,線形化可能性の意味
    • !!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
      • 図7-2: e.g. to Isolation
      • 図7-3: e.g. to Atomicity
      • 同じTransactionの判定: ClientからDB ServerへのTCP接続による
        • ↑ 望ましくない.TCP接続によらないuniqueなidを使う方法ある
      • 多くの非relational dbでは,操作のグループ化する方法なし
    • !!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)は回避不可能
    • !!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 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
      • 現代的なSPの実装は,既存の汎用programming languageをつかえる
        • e.g. VoltDB - Java or Groovy, Data - Java or Clofare, Redis - Lua
      • SPとメモリにあるデータを使えれば,単一threadで全Transaction実行が現実的
        • → 良いthroughput
      • VoltDBは,replicationでもSPを使う → SPは決定的がmust
    • !!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を設けられる
  • !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の検知アルゴリズム
    • !!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の影響なし

まとめ

  • 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は,この間のどこか
    • → フォールトへのapproach異なる
      • super computingは単一ノードのcomputingに近い
      • 本書の焦点は,internet上のserviceを実装するsystem
        • online → 低latency必要
          • hardware
          • network
            • 大規模datacenterのnetworkはIPとEthernetがベース
              • → 高2分割帯域幅のために,Clos topology
            • super computingのnetwork: 多次元メッシュやトーラス
          • 何かが常にフォールト
          • rolling upgradeなど
          • 地理分散 → (network) internetに依存
    • softwareにフォールトtoleranceの組込必要
      • 信頼性のないcomponentからtrustnessあるsystemを構築
      • 様々なフォールトへのテスト必要

8.2 低trust network

目的

  • shared nothing system by network
    • internetとdatacenter内の大部分の内部network(Ethernet)は,async packet network
      • 図8-1
      • 各problem ^ timeoutでの対応

対応

  • !1 networkのfaultの実際
    • networkの分断: network partition, netsplitと呼ぶ
      • 必ずしもtolerantである必要はない
      • networkのproblemへの反応の認識が重要
  • !2 faultのdetect
    • requestのsuccessは,applicationからのproperなresponce以外確認不可能
      • errorはtimeoutでjudge
  • !3 timeoutと限度のない遅延(unbounded delay)
    • 保証なし@networkのdeliveryとrequestの処理のtime
    • !!1 networkのcongestionとqueuing
      • 図8-2: queuing
        • TCP, UDP
        • timeoutは経験的に決定 @public cloudやmultitenant datacenter
          • auto timeout 調整も◎
            • e.g. AkkaやCassandraで利用されているPhi Accural failure detector
            • TCPのresendのtimeoutと同様
  • !4 sync networkとasync network
    • sync networkでは,bounded delay by 回線,connection
    • !!1 network delayの予測
      • burst性のあるtrafficにoptimiseされたnetwork: packet 交換方式
      • QoSやadmission control(受付control)を使うと,packet network上で回路交換をemulate. 統計的にdelayのbound課すこと可能
      • latencyとresourceの活用: tradeoff
      • このQoSは,multitenant datacenterやpublishing cloudにはない
      • → networkのcongestion queuing, unbounded 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の期間計測に使える.
  • !2 clockの動機とaccuracy
    • ずれが生じるe.g.
    • 精度の実現
      • GPS受信マシン, Precision Time Protocol(PTP), 注意深いdeployとmonitoring
      • コスト莫大
  • !3 sync clockへの依存
    • softwareがclockのずれをmonirtor要
    • !!1 順序relationをもつeventのtimestamp
      • 図8-3: e.g.
      • LWWのproblem
        • → logical clockの使用が〇
          • 相対順序の決定.単調increment
        • ≠ physical clock: 時刻のclockや経過時間を観測する単調increment のclock
    • !!2 clockの値の信頼区間
      • 精度より小さい桁はno mead
      • ふつうは非公開
    • !!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
        • ずれ
        • 処理時間
          • especially, processing(thread)の一時停止
            • processingが止まる例
              • GC(Garbage Collector)
              • VMのsuspend→ resume e.g. for host間live migration
              • VMがCPUを使うsteal time
              • discへのswapping(paging) → thrashing
              • UNIXでのCtrl-z(: SIGSTOP) (→ SIGCONTでrestart)
            • preemption(一時的中断)に気づけない
            • multithread codeをthread safeにするproblemと同様
    • !!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
    • !!2 GCによるimpactの制限 → 有益
      • GCの一時停止を事前に計画された短時間のnodeの停止として扱う
      • processingのregular restart
        • GCは短命Objectのみ

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
        • 制約強い
    • 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は等しく重要

まとめ

  • 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: 合意
    • 可不可の限度の認識が重要

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: 反例

対応

  • !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
  • !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と類似
    • !!3 cross channel timing依存relation
      • 図9-5: e.g. cross channel
      • → linearizability 必要
  • !3 linearizable systemの実装
    • replication for fault-tolerance
      • single leader replication (潜在的にlinearizable)
      • 合意algorithm ( linearizable)
        • e.g. ZooKeeper, etcd
      • multileader ( not linearizable)
      • leaderless replication(maybe not linearizable)
    • !!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のため

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
    • !!3 因果律における依存関係の補足
      • 操作の先行を知る必要: 半order
        • nodeのacknowledgeを記述する必要
          • version vectorの利用 ← 5.4.4と似ている
          • dbがread dataのversionを知ることが必要
  • !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補足不可能
    • !!2 Lamport timestamp
      • 図9-8: e.g. ← {counter, nodeID}のpair 「max」が重要
      • readed max counterを追跡 by all nodes, Clients
      • version vector: 並行か因果律の依存関係か判断
      • Lamport timestamp: 常に全orderが決まるようにする
      • 上の2つは目的がdifferent
    • !!3 timestampでのorderづけでは不十分
      • Lamport timestampは,distributed systemのgeneral な多くの問題の解決には不十分
      • ↑ 操作の全orderは,すべての操作がcollectできたあと
      • → unique制約には,操作の全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
    • !!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
    • !!3 linearizableなstorageを使ったtotal order broadcastの実装
      • linearizable sequencial number generatorを使う ← 合意のalgorithm
      • linearizable (increment) compare-and-set registerと,total order broadcastはどちらも合意と等価
        • → どちらかをresolve → もう一方にも変換〇

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
      • applicationからはXA Transactionや,SOAP Web servicesのWA-Atomic Transaction経由で利用
      • 図9-9: e.g.
      • 2PC: distributed systemでatomic commit ≠ 2PL: serializable isolationを提供
        • coordinator(a.c.a. transaction manager)
          • e.g. Narayan, JOTM, BTM, MSDTC
        • db node: 参加者
    • !!3 約束のsystem
    • !!4 coordinatorのfault
      • in doubt, uncertain
        • 図9-10
      • coordinatorのrecoveryを待つ必要
    • !!5 3PC
      • 2PC: blocking atomic commit protocol
      • 3PC: nonblocking
        • but, 制限あり.現実にはnot atomic
          • non blocking. atomic commitはperfect failure detector必要
            • 実際は難しい
  • !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
        • 多くのrelational dbやmessage brokerで旧来サポート.
        • XA: transaction coordinatorへのCのAPI
          • Javaでは,Java Transaction API(JTA)で実装
            • JTAは,Java DB Connectivity(JDBC)を使うDBの多くのdriverや,Java Message Service(JMS) APIを使うmessage broker用のAPIでサポート
      • 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を増幅
  • !3 耐障害性をもつconsent
    • consent: 非形式的には,複数nodeが何かについて同意すること.
      • 形式的には,1つ以上のnodeがpropose → 合意algorithmがそれらの値から1つを決定
    • uniform consent
      • 4つの性質
        • uniform agreement
        • integrity(整合性)
        • validity(妥当性) (ここまで3つが合意の核.安全性)
        • termination(終了性): 耐障害性.(live性)
    • いかなる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
    • !!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では過半数
    • !!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は研究中
  • !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
      • ZooKeeperのatomic操作, ephemeral node, 通知により達成可能
        • Apache Curatorのようなlibraryあるが,簡単ではない
      • ZooKeeperはnode間協調作業をoutsourcing
      • applicationのstateをnode間でreplication → Apache BookKeeper
    • !!2 service discovery
      • ZooKeeper, etcd, Consul
      • linearizability不要なread requestにresponceできる
    • !!3 membership service
      • consentとfault detectの組み合わせ
      • どういったnode群でmembershipが構成されているか.Systemでconsent生成は有益

まとめ

  • 一貫性と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の状況に対処必要証明
  • 耐障害性をもつconsentのためのalgorithm system
    • ZooKeeper
  • consent不要なcase
    • multi leader replication system
      • 単にlinearizabilityなしに対処.分岐や合流を伴うversion historyをもつdataを扱えばよい.