#dbts2015 #E14 結果整合性だけじゃない！ #Riak の強整合性オプションのメモ

db tech showcase 2015 、午後 2 つめに参戦したセッションは @kuenishiさんのセッション。

一コマ前の Riak のセッションから聞くとなおよかったようには思いましたが、 MySQL 5.7 の話を聞きたかったので致し方なかったな、と。

とは言え、丁寧な言説でとてもよいセッションでした。日本の分散 DB 界隈の有名人の話を直接、聞ける貴重なセッションだったな、と。

では、以降わたしがとってきたメモです。

概要：

NoSQLで分散KVSというと、複雑な機能を切り捨てて、非常にプリミティブな機能と整合性とパフォーマンスに特化したものと思われがちです。しかし、近年は目的に応じてさまざまな用途や機能を提供するものが増えてきました。従来のRiakでは結果整合性、因果整合性が保証されていましたが、2.0から強整合性のある書き込みもサポートされるようになりました。分散システムでなぜ強整合性が難しいのか、Riakではそれをどのように解決したかを解説します。
Bashoジャパン株式会社上西康太氏

分散システムのスレーブのデータ整合性って適当なんだろ？という誤解を解きたい、そんなセッション。
- 最近はガチガチのトランザクションに興味があるとのこと
レプリケーションは難しい
- 運用が
- 切り替えの後、切り戻しをしないといけない
- 夜中にアラートが起きる
- 自動化は難しい (Split Brain しない)
- 一度レプリカが壊れたら 1 からリカバリ
- 瞬断も大変
  - 非同期→おいつき、ズレ
  - 同期レプリケーション→ Downtime
- CAP 定理
  - 複数のノードが保持している、最初は同じオブジェクトに変更の列を送り続ける
  - メッセージが到達しないときに、全てのノードが同じ変更の列を保持することができない
- 難しさの根源は故障単位を分けたこと
  - 美しくやろうとすると大変ということ
- 別のものが同一であるということを保証してしまっている
凡例
- 解法その 0 : Master-Slave
  - 更新の命令列が唯一であることを保証する
  - マスター不在ではなにもできない
  - 背景
    - 1990 年代 RDBMS 普及期
    - 2000 年代 Web 時代
      - MySQL binlog, GFS(BigTable), HDFS(HBase)
  - Master-Slave は難しい : 課題の限定が難しい
    - Master 切り替えのタイムラグ
    - Split Brain 耐性
      - redo log の順番がいれかわってしまう、とか
- 解法その 1 : コンセンサス
  - 異なる実体が同じ状態をもつことがゴール
  - レプリケーションはいわゆる分散合意問題
  - これを解く通信方式を、コンセンサスプロトコルという
  - 背景
    - 2000 年代 Web 時代
      - Web システムの複雑化、巨大化
      - NW 分断が起きても自動的に解決できる方式が必要だった
      - Dynamo, Chubby, ZK, SQL Server
        
        基本的には多数決
  - コンセンサス型レプリケーションの分類
    - CP 型
      - Paxos, Raft
      - 複製間の同一性を保障するタイプ
    - AP 型
      - Vector Clock や CRDT により因果整合性を保障
      - ネットワーク分断しても、すべてのノードで利用可能
レプリケーションからみたデータベースの分類
- Master-Slave 型
  - 実装シンプル、高速
  - MySQL, PostgreSQL
- コンセンサスと Master-slave のハイブリッド
  - MongoDB, HBase, Redis
- コンセンサス型
  - マスター故障によるダウンタイムなし
  - Riak
Riak
- Riak のレプリケーション
  - Sloppy Quorum を使ったルーズなやつ
  - 生のやつ: 整合性は Eventual
  - CRDT: Causal Consisitency -> Siblings を自動的にマージ
- Quorum: コンセンサスは難しい
  - 上書きを許容するナイーブなプロトコル設計では簡単にデータが破壊されてしまう
  - いつでもだれでも故障するし、黙るし、復活するという、現実世界では実用的ではない
- Sloppy Quorum: データの上書きをさせない
  - とりあえず別のノードに書いておく
  - ノードが復帰したら、別のノードが持っていたデータを返す
  - これでカバーできるユースケース
    - Monotonic なもの
    - Sets, LWW-Registers, カウンター、キーをシステム側で生成して良いもの
    - ショッピングカート、チャット、プレゼンス表示、 +-1, UUID-based records, etc...
- Monotonic とは
  - 経路非依存でデータの発展が単調なデータ
  - マージを実装できる
  - カバーできないユースケース
    - Monotonic でないもの、 Unique なもの
    - CAS をつかうもの
    - キーをアプリ側で決定するもの
    - Item inventory, Bank Account
Strong Consistency in Riak using Paxos
- 分散システムで CAS は難しい
  - Exactly Once Semantics
  - 個々のノードで CAS をしてもインターリーブすると死
  - インターリーブさせない仕組みが必要
- それを解決するのが Paxos
  - 2 フェーズの合意プロトコル
    - Proposer (値を提案する人)を多数決で決定 (早い者勝ち)
    - Proposed Value (提案された値)を多数決で決定
  - MultiPaxos in Riak
    - Proposer だけが Lease の間書き込める
  - MultiPaxos in a nutshell
    - 図解 (資料見たい)
    - Accceptor は Proposer の write を受け付ける
    - 過半数から Ack をもらえない場合は失敗
  - Why Paxos is important?
    - DC 間レプリケーション
    - Paxos は... 2F + 1 のノードがいるとき、 F 個のノード故障に耐えられるコミットプロトコル
    - 分散トランザクションのコミットメッセージに使えるかも
      - 2PC (Phase Commit) は F=0 のときの特殊ケース
        
        基本的には 2PC は耐障害性がない
        
        Paxos ⊂ 2PC
        
        耐障害性を持たせたいなら実質 Paxos しか選択肢がない
- Strong Consistency in Riak
  - Vector Clock をつかった CAS のような API
  - 既存アプリを書き換える必要がない
レプリケーションは難しい (実装が)
- 非同期の状態遷移機械の組み合わせ
- 故障の組み合わせ
- タイミングを再現しにくい
- コーナーケースがいくらでもある
- 難しい
レプリケーションのテスト
- ひたすら長時間叩く
- プロトコルの正しさを証明する
  - 数式の世界、 TLA + (時相論理)
- Fault Injection + linearizability test
  - Jepsen
    - iptables
    - これを使って Kafka のバグをみつけたのが有名な話