Think Distributed

Database and Distributed Systems

DB Weekly #281

dbweekly.com

率直に言って、今回の DB Weekly はおもしろくないです。

ksqlDB: The event streaming database purpose-built for stream processing applications.

ksqlDB is primarily useful for three broad categories of applications:

Building and serving materialized views that power apps

Creating real-time streaming apps that react to event streams and trigger side effects

Creating real-time streaming pipelines that continuously transform event streams

という用途に使えるものらしい。

12 Common Mistakes and Missed Optimization Opportunities in SQL | Haki Benita

よくあるなと思ったのは「Know the Difference Between UNION and UNION ALL」「Be Careful When Counting Nullable Columns」「Fetch Only What You Need!」ぐらいかなぁ。PostgreSQL って、GROUP BY と ORDER BY でカラム名の代わりに index 番号が使えるの知らなかった。

RedisInsight—The Redis GUI You’ve Been Looking For | Redis Labs

GUI 上で統計情報などが見られるツールらしい。こういうの管理ツールとして作ってた人結構いるだろうし、それなりに需要はありそう。

An interview on what makes Postgres unique (extensions) - Craig Kerstiens

ここ10年の PostgreSQL では extension API が一番重要な機能だったと。ていうか、HyperLogLog 使ってるのかという驚き。

Releasing BadgerDB v2.0 - Dgraph Blog

BadgerDB 知らなかったけどグラフ DB なのか。近頃、internal なストレージフォーマット変更時に DB のマイグレーション方法が気になっていて、BadgerDB は badger restore でおそらく古い方のデータを全部復元処理として扱って新しいフォーマットに取り込むのかな。

Erasure Coding による CPU, IO 負荷を下げる案

しばらく前から仕事で Erasure Coding を使って保存されたデータを復元する処理の負荷を下げる方法について考えている。なぜこんなことをしているかというと自社製のストレージのデータが EC を使うようになっているから。

すでに実装された機能として、

  1. I/O が暇な時だけデータを復元する
  2. 同時に走る復元処理の並行数を制限する

というものがある。EC の復元処理の CPU, IO 負荷を下げるのとリペアをなるべく早く完了させたいため、これだけでは十分ではなく、色々処理を効率化する方法を考えている。

例えば、他にやれることとして、

  1. リペア処理をクラスタに分散させて CPU 負荷を減らす
    1. Facebook の f4 というストレージで採用されている方法
    2. f4: Facebook's Warm BLOB Storage System | USENIX
  2. read repair(データを読んだ時に欠けてるフラグメントがあったらリペアしてしまう) する
    1. Cassandra で採用されている方法、Dynamo も(?)
    2. lakshman-ladis2009.pdf
    3. 1 回分データをディスクから読んでデコードする処理が省ける
  3. いくつかのデータをまとめて(仮にブロックと呼ぶ)ディスクに保存して、ブロック単位でリペアすることでシーケンシャルライトに持ち込む
    1. Hadoop の EC がこのような構造になっている
  4. Erasure Coding の実装を Local Reconstruction Codes に置き換える
    1. Erasure Coding in Windows azure storage - Microsoft Research
    2. Microsoft Azure で採用されている方法

というのがある。さてどうしたものか。

Reading: GEMS: Gossip-Enabled Monitoring Service for Scalable Heterogeneous Distributed Systems

論文

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.160.2604

highscalability.com

でおすすめされていた論文。

flat gossiping

  • 主要なデータ構造は gossip list, suspect vector, suspect matrix, live list の4つ。
  • gossip list に他ノードから最後に gossip を受け取ってからの経過時間を持つ。
  • suspect vector に他のノード(自分も含んでもよいが)の故障疑い状態を持つ。
  • suspect matrix に全ノードの suspect vector を持つ(gossip で入手する)。
  • live list に各ノードの死活状態を持つ。
    • コンセンサスの結果により、自身の suspect vector と結果が異なる可能性がある。
  • T(gossip)時間経過毎に別のノードにハートビートを UDP で送る。
  • T(cleanup)時間以内にgossipされなければ故障扱いになる。
  • 故障検知には、過半数のコンセンサスとタイムアウトを組み合わせる。
  • 論文によると、random gossip が round-robin よりもスケーラブルとのこと。

誤検知への対応

過半数が故障を検知しているか、コンセンスを使って判断する。suspect matrix を参照すれば過半数が故障検知しているかが分かる。

ネットワーク分断への対応

コンセンサスが得られない場合、故障しているかもしれないノード j がタイムアウト時間以内に suspect matrix 上で状態が更新されないかを待つことで分断中でも故障検知が可能になる。

Reading: A Gossip-Style Failure Detection Service

https://www.cs.cornell.edu/home/rvr/papers/GossipFD.pdf

  1. 故障の誤検知の確率がクラスタ内のプロセス数に依存しない
  2. 小数の故障ノードやメッセージロスがある状態でも誤検知を起こしづらい
  3. ノードのローカルクロックがズレてもその影響を無視できる
  4. 検知時間がスケールする
  5. ネットワーク負荷面でスケールする

特性を持ったアルゴリズムについての論文。

基本的なアイディアは、

  1. 各ノードが一定時間毎にメンバーリストとハートビートカウンターを交換する。受けとったらマージ。
  2. たまにリストをブロードキャストする。
  3. T(fail) 時間以内にカウンターが更新されなければ故障を検知する。T(fail)は誤検知の確率を考慮して決める。
  4. T(cleanup)時間経過したら故障ノードをメンバーリストから削除する

ゴシップスタイルのアルゴリズムで気を付けるべき点として、ネットワーク分断など大規模なノード障害が発生すると障害検知が機能しなくなる点。

Reading: Frangipani: A Scalable Distributed File System

Frangipani: A Scalable Distributed File System

システム構成

  • Petal
  • Frangipani
    • カーネルモジュールを提供する。
    • OS の File System API 経由で使われる。
    • 各 Frangipani サービスは共有の Petal ストレージを使う。
    • Frangipani は Petal と分散ロックサービス以外とは通信しない(Frangipani 同士は通信しない)。
  • 分散ロックサービス
    • ロック機能を提供する。
    • 内部では Paxos を使う。

ファイルシステムとして Frangipani は複数マウント可能だが、Frangipani は(Petal上の)単一の共有仮想ディスクを使う。

ディスクレイアウト

f:id:syamaoka:20191117074706p:plain
Frangipani の論文より

リカバリ

WAL を使う。Petal のログ領域を更新してから、自サーバー上の metadata 領域を更新する。

ロックサービス

  • ロックには lease を使う。
  • 障害検知には heartbeat を使う。
  • ネットワーク分断には majority consensus を使う。(ここは Paxos のことだと思われる)
  • multiple reader/single writer ロックを提供する。
  • 効率のために、ロックはロックグループという単位でまとめられ(トータル100グループ)、ロックグループが各サーバーに割り当てられる。ロックを個別にサーバーに割り当てることはしない。
  • サーバー故障時に残ってしまったロックは、リカバリー処理時に解除される。
  • false sharing を避けるために、共有ストレージ領域上の各セクションは1つだけ共有可能なデータ構造を提供する。
  • atomicity が必要で複数のロックを取らないといけない場合は、以下のステップを踏むことでデッドロックを避ける:
    1. ロックすべきロック群を決める
    2. inode 番号でロック対象を sort する

サーバーの追加/削除

追加時はロックサービスからロックを取って、自分の使う仮想ディスク上のログ領域を決定する。

バックアップ

基本機能は Petal 付属のものを使う。つまり、バックアップ時は Petal で Snapshot を取ってそれをテープに書くという手順を踏む。

単一のロックに対して Frangipani は shared lock を、バックアッププログラムが exclusive lock を取ることで、バックアッププログラムがバックアップ中に Frangipani によって変更が行われないようにするテクニックが使われる。

Reading: Petal: Distributed Virtual Disks

http://www.scs.stanford.edu/nyu/02fa/sched/petal.pdf

モジュール構成

  • Global State Module
    • 分散システムの機能を担う。
  • Liveness Module
    • 分散システムの機能を担う。
  • Recovery Module
    • クラッシュした時のためのリカバリ処理を担う。
  • Virtual to Physical Translator
    • 仮想ディスクのオフセットを物理ディスクのアドレスへと変換する。
  • Data Access Module
    • 物理ディスクに保存されたデータへのアクセス。

設計

  • データは chained-declustering によって分散保存される。
  • グローバルなサーバー設定において、分散合意アルゴリズムには Paxos を使う。
  • 物理的なディスクは仮想的なディスクとして束ねられ、クライアントには仮想ディスクとして見える。
  • RPC で操作できる。
  • 仮想ディスクを作成する時に冗長化方式を選択する。
  • サポートしている冗長化方式は striping(冗長化なし)、レプリケーション(chained-declustering)の2つ。

物理と仮想のディスクアドレスの変換

  • VDir(Virtual disk directory)
    • クライアントが指定した仮想ディスクIDを GMap の ID に変換する。
  • GMap(Global Map)
    • 指定されたオフセットに応答可能なサーバーを決める。
    • 変更不可。
    • 仮想ディスクと 1 対 1 の関係。
  • PMap(Physical Map)
    • GMap の ID とオフセットを物理ディスクとそのディスクのオフセットへと変換する。

サーバー設定変更とデータ再配置

サーバーの設定が変更された時に、古い仮想ディスクの設定から新しい仮想ディスクの設定への切り替えで、古い設定で保存されたデータもアクセス可能なままにしておきたい。また、ディスクへの負荷も抑えたい。

まず、データの再配置の基本アルゴリズムは、

  1. 新しい設定で新しい GMap を作る。
  2. すべての仮想ディスク上のディレクトリエントリが新しい GMap を参照するよう変更する。
  3. 新しい GMap に応じてデータを再配置する。

次に、より洗練されたアルゴリズムについて。仮想ディスクの領域を old, new, fenced の3つに分ける。fenced な領域に来たリクエストに対しては基本アルゴリズムを適用する。fenced な領域のデータがすべて再配置されたら、別の領域を fenced な領域に変更し、以下同じことを繰り返す。fenced なリージョンは連続した領域ではなく、仮想ディスク上で分散した非連続な小領域で構成する。

Chained declustering

データを冗長化するための技法で(http://pages.cs.wisc.edu/~dewitt/includes/paralleldb/dbengin90.pdf を参照)、データは必ず(隣接する異なるサーバー上の)2つの物理ディスクに書かれる。chained declustering は冗長化先をデータ毎にずらして特定のサーバーに負荷が偏らないようにする効果がある。冗長化対象のディスクには primary と secondary の区別があって、書き込み時は primary から始めて secondary までデータを書き、読み込み時は primary と secondary のどちらかからデータが取れるまで primary と secondary にクライアントがリトライすることで冗長化を実現している。

Reading: Ω Meets Paxos: Leader Election and Stability without Eventual Timely Links

www.microsoft.com

今からやるなら Paxos より Raft の方をおすすめしたいわけですが、それはさておきこの論文の Abstract, Related work は survey として秀逸と感じました。ピュア(定義の列挙は読者にとっては自明として省略)な非同期システム(通称 FLP impossibility を参照)上でコンセンサスを実現するには、何らかの条件の緩和が必要なわけですが、コンセンサスを実現する際の同期条件に着目して関連研究が挙げられているためです。似たような内容は、「Communication and Agreement Abstractions for Fault-Tolerant Asynchronous Distributed Systems」にも記載されていますので、詳しく知りたい方は書籍を参照してください。