Coursera で "Cloud Computing Concepts, Part 1" Week 4 を受講した

Coursera

Coursera でイリノイ大学の講義 "Cloud Computing Concepts, Part 1" を受講してる！

Week 4 に関して個人的な勉強メモをまとめた．

• https://www.coursera.org/learn/cloud-computing

Week 4 : 期間

• 2016/09/19 - 2016/09/25

Week 4 : アジェンダ

• Week 4: Key-Value Stores, Time, and Ordering
  • Overview
  • Lesson 1: Key-value stores
    • Why Key-Value/NOSQL?
    • Cassandra
    • The Mystery of X-The Cap Theorem
    • The Consistency Spectrum
    • HBase
  • Lesson 2: Time and Ordering
    • Introduction and Basics
    • Cristian's Algorithm
    • NTP
    • Lamport Timestamps
    • Vector Clocks
  • Interview
  • Homework

Lesson 1: Key-value stores

Why Key-Value/NOSQL?

• Key-Value は辞書データのような構造
• RDB との比較（RDBは読み取りにオプティマイズされている）
• データが巨大・そして非構造化
• ライトヘビー（ユースケース的に読み取りよりライトが詰まることもある）
• 大量のランダムリードとランダムライト
• 外部キーやジョインは不要なことが多い
• 最近のワークロードに対して「スピード・SPOF・TCO・少ないシステム管理者・繰り返すスケーラビリティ（スケールアウト）」が KVS を必要としている理由

Cassandra

• IBM / Adobe / HP / eBay / Twitter / Spotify も Cassandra を使っている
• Netflix は position in the videos の追跡管理に使っている
• どのサーバに kv がマッピングされるか？
• 分散ハッシュに類似した形でストアしている
• Cassandra ring 型の DTH
• キーからサーバを特定するマッピング方法を「パーティショナー」と呼ぶ
• レプリケーションストラテジー
  • SimpleStrategy
  • randompartitioner : Chord ライクなハッシュ分割
  • byteorderdpartitioner : 実際にキー名の順番で並べる
  • NetworkTopologyStrategy
• Snitches
  • IP アドレスからラックとデータセンターを特定する
  • RackInferringSnitch
    • w.x.y.z
      • x ... datacenter
      • y ... rack
      • z ... node
  • Ec2Snitch
  • Ec2MultiRegionSnitch
• Memtable
• SSTable
• Bloom Filter
  • 高速にキーの存在確認ができる
  • false positive（キーがない場合にあると応答してしまうこと）はあるけど，false negative（キーがある場合にないと応答してしまうこと）はない
  • Bloom Filter は bit 空間（例えば m = 3 なら，0-127 の 128 bit 空間）
  • 計算ロジック
    • 最初 bit 空間を全て 0 で埋める
    • 登録するデータごとにハッシュ値を取得して，bit 空間にフラグを立てる
    • ただし，2個目のデータ以降は，直接 bit 空間を上書きするため，過去の履歴などは判別できなくなる
    • 講義の例だと，3種類のハッシュを使って 3bit を立てていた
  • チェックロジック
    • チェック値を同じくハッシュ値を取得して，bit 空間と照らし合わせる
    • Bloom Filter 側で 0 なのにチェック値が 1 の bit 空間がある場合，未登録と言える
    • ただし，別の値で立ったフラグと一致してしまう場合，存在していると返してしまう可能性がある

The Mystery of X-The Cap Theorem

• Consistency
  • 複数のクライアントが同時にアクセスしたときに完全に同じデータが返ること（直近で更新された値があれば，それが返ること）
• Availability
  • リードライトがいつでもできて，早くできること
• Partition-tolerance
• CAP
  • この3個のうち2個しか満たすことはできない
• Availability がなぜ重要なのか？
  • レイテンシは売上に起因する
  • 500ms を超えてしまうと，Amazonもgoogleも20％のレベニューを落とした
  • だからこそレイテンシを低く保つ
• Consistency 銀行口座のことを考えればわかる
• Cassandra は AとPを採用している
  • Cは諦める
• Cassandra で提供される Eventual Consistency とは何か？
• RDBMS vs KVS
  • RDBMS は ACID を提供する
    • Atomicity ... 不可分性
    • Consistency ... 一貫性
    • Isolation ... 独立性
    • Durability ... 永続性
  • 逆に Cassandra などの KVS は BASE を提供する（一貫性より常に使えることを重視）
    • Basically
    • Available
    • Soft-State
    • Eventual Consistency
• Cassandra は consistency level を選べる
  • ANY
  • ALL
  • ONE
  • QUORUM
  • LOCAL_QUORUM
  • EACH_QUORUM
    • QUORUM とはマジョリティのこと（ようするに50%以上のノード）

The Consistency Spectrum

• コンシステンシースペクトラム
  • スペクトラムは分布範囲の意味・ようするに特性ごとの関係性
• 当然コンシステンシーを求めるならリードライトは遅くなる
• Eventual consistency : 結果整合性
• Cassandra は Eventual consistency を提供している
• キーのレプリカが反映されるのは converge eventually
• Cassandra も Voldemort も Dynamo の思想に影響されている
• Per-key sequential
• CRDTs
• 結果整合性のモデル
• Linearizability
  • 変更を全クライアントに即座に反映する
  • 分散システムだと採用は難しい
• Sequential Consistency

HBase

• HBase は GoogleのBigTable をYahoo! が OSS にした
• Facebook も内部で使っている
• Cassandra と違って分散上で整合性を取る
• HBase Table はリージョンごとにわかれている
• インスタンスはテーブルのレコードとして表される
• Memstore : CassandraのMemtableに似ている
• Memstore からディスクにフラッシュされる
• HBase はどうやって整合性を取っているのか？
  • それは HLog の役割
  • Hlog は resion server ごとにメンテナンスされる
  • Memstoreに書く前にhlog に書いてしまう

Lesson 2: Time and Ordering

Introduction and Basics

• なぜ Synchronization が必要なのか？
  • あなたは 6:05 pm にバスに乗る予定
  • なのにあなたの時計は15分ズレている
  • 早かったら乗り遅れるし，遅かったら15分追加で待つことになる
  • 時計は同期されていない
• Clock Skew
• Clock Drift

Cristian's Algorithm

• クリスチャンアルゴリズム
• 中央サーバに問い合わせて返ってきた値を設定する
• RTT Round-Trip-Time : 問い合わせてから応答が返ってくるまでの時間

NTP

• 木構造
• 常に自分の親から同期する
• Offset o = (tr1 - tr2 + ts2 - ts1) / 2
• ノード間のネットワークレイテンシは把握できない

Lamport Timestamps

• 1970年に Lamport 氏によって提案された
• 各プロセスは整数のカウンタを持つ（初期値は 0）
• 各プロセスはメッセージを送信する or 命令を処理するタイミングでカウンタをインクリメントする
• メッセージを受信したプロセスは以下の式に沿ってカウンタをインクリメントする
  • MAX(local clock, message timestamp) + 1
• 時刻をデクリメント（後戻り）させることはなく，必ずインクリメントしていく
• 時刻が A < B である場合に causality（訳としては前後関係？）を満たす
• 実際にメッセージが送信されない関係の場合 not causality となる
  • 並行 (concurrent) な関係と言える

Vector Clocks

• イベントにタイムスタンプを付与する方法
• Riak で使われている
• N プロセスあったときに
  • プロセス i は ベクトル Vi[1...N]をメンテナンスする（ようするに全方向に）
  • プロセスiで j を処理されたとき，jのタイムスタンプが更新される
• Lamport timestamp に似てる
• プロセスiは送るときに自身のタイムスタンプを更新する
  • 次に受け取ったjは
  • メッセージのベクトル全体で比較して1番大きい方で更新する
  • ローカルと同じだったらインクリメントする
• イベントに整数のクロックをアサインする
• obeys causality（因果関係に従う）
• コンカレントイベントを識別できない（ことがマイナスポイント）
• ベクターを使うことで，コンカレントイベントを識別できるように拡張したことがポイント