自作分散KVS
動機
Elixirを使ってなんか書きたかった
分散したかった
雑な要件
分散
書き込みを高速にしたい
インターフェースはHTTP
耐障害性がある
クラスタのうち、1台がダウンしても平気を目指す
とりあえず調べてみる
辞書データ構造の抽象化がKVS
NoSQLの類
CRUD操作を持つ
単純に考えるなら最初はメモリに入れる、が、データが大きくなると容量が足りなくなる
冗長性も足りない
分散させる
どのように複数ノードへデータを配分するかが問題となる
シャーディング
アルファベット26文字で分配する
欠点は負荷の分散が均等ではないこと
ハッシュを使うほうがいい
スケーリング/可用性/一貫性
可用性を高める一つの手段がレプリカ
レプリカが冗長性を高めるため
シャーディングが負荷分散(ストレージとCPU)のため
レプリカのトレードオフが一貫性
一貫性を保持するために
コーディネータにレプリカへのコピーをする責任を持つ
各ノードがコミットログを持つ
コミットを保存、別プロセスが処理、を各ノードで行う
処理が失敗してもコミットログがあればリトライできる
読み込み時はコーディネータがレプリカの値を取得
違っているものがあれば修正する
NoSQLが普及したのはなぜか？
速度
単一障害点を回避できる
構造化されてないデータのより良いサポート
トータル運用コストの低さ
スケールアウトのしやすさ
Inside Cassandra
分散ハッシュテーブルリング
https://s3.amazonaws.com/fourthbit-blog/2015-04-12-building-a-distributed-fault-tolerant-key-value-store/cassandra.png
このリングがKey -> ServerNodeのマッピング構造を成す
クラスタに1個のコーディネータが居る
DCというよりクラスタに1個な気がする
選出にはPaxosのような合意プロトコルが使用される
書き込み動作
クライアントが書き込み要求を送信する
コーディネータが受信、全てのレプリカの場所を解決、それらにクエリを送信
一定数の返答があればコーディネータはackをクライアントに返す
quorum-numberという
lock-freeな書き込みで高速
データベースは常に書き込み可能
Hinted-Handoffメカニズムのおかげ
レプリカがダウンしても復旧するまでローカルにコピーを保持する
ディスクなどの永続メモリに書き込む
次に、インメモリテーブルに書き込む
いっぱいになったらディスクにflushする
読み込み動作
クライアントが読み込み要求を送信する
コーディネータが受け取る、レプリカに問い合わせる、タイムスタンプが最も新しい値を返却する
書き込みよりも読み込みのほうが遅い
rowがSSTables間で分割されるため
minimal分散フォルトトレラントKVSのアーキテクチャ
上述のCassandraをベースにする
レイヤーは上から3つ
アプリケーション
KSV
ネットワーク
ノードレイヤ
https://s3.amazonaws.com/fourthbit-blog/2015-04-12-building-a-distributed-fault-tolerant-key-value-store/architecture_store.png
全てのノードは同じ機能を持つ
全てのノードはリクエストコーディネータ/データセンターコーディネータになることができる
どのノードにリクエストを送ってもいいという意味？
メンバーシッププロトコル
全てのノードはリング内の他のノードに情報を通知する必要がある
一般に2つのコンポーネントに分けられる
流布
失敗検知
単純な方法はAll-to-all multicast
よくある手法はGossip-like membership protocolとして知られている
仮想リングトポロジー
ハッシュリング
hash(Key) % ringSize
CRUD操作
クラスタ内のそれぞれのノードはクライアントCRUD/サーバCRUDの両方をサポートする
Storageコンポーネント
書き込み処理をする
stabilizationプロトコルがノードダウン時の回復を行う
Replication/Consistency
Eventual consistency
どのくらいの一貫性を保持するかで性能のトレードオフがある
書き込み
書き込みはper-keyコーディネータによって管理される
実行順に書き込まれることが保証される
コーディネータが全てのそのキーに対応するレプリカノード全てに書き込みクエリを送信する
自分自身がレプリカになるときもある
quorumの数だけレスポンスがあればackをクライアントに返す
実装例
レプリカは3つ
elseの中が自分自身がレプリカだった場合のそれぞれの処理
読み込み
書き込みと殆ど同じ
レプリカから異なる値が帰ってきたら古い方を新しい値で上書きする
サーバ
ハッシュテーブルを持ち、一定感覚でディスクへダンプ
Stabilization
ノードダウンに対処するために必要
それぞれのノードのキーを全探査して、こわれたKey -> Nodeマッピングを探す
キーが別のノードに属していたとき
ローカルのデータベースから削除して、他の3つのノードに送信する
ノードの選出は？
キーが自分のノードに属していたとき
他の2ノードに送り、自分は保持
特徴まとめ
↑の特徴まとめよりは踏み込んでいる
整合性、冗長性、データ構造について言及している
ちょっと動かしてみるパートがある
mnesia
分散DBMS
ETSはシングルノード、これを拡張して分散するようにしたのがmnesia
トランザクションを持つ
dirty operationsでトランザクションを使わないこともできる
CAP定理でいうとCP
Mnesiaは少量のデータで、限られたノード数で処理するために作られたもの
10ノードくらいが実用限界
RAMかディスクか選べる
レプリケーション
クラスタ内のmnesiaが起動する全てのノードでレプリケーションされる？
レプリケーションノードはマニュアル指定
レプリカを自動管理はしない
ノード指定は使用者の責務
システム動作中にレプリカの設定を変更できる
majorityオプション
Cassandraのquorum数ぽい
大体ここを読めばわかりそうだが量が多い
自作例
書き込みの性能がスケールアウトする
要件
できれば読み込みよりも書き込みを高速にしたい
インターフェースはHTTPでCRUD
ユーザはHTTPが話せればよいとしたい
クライアントライブラリを作らない、ということ
耐障害性がある
クラスタのうち、1台がダウンしても平気を目指す
全てのノードは同じ機能を持つ
どのノードからでも読み書き可能
実行時のノードの追加は考えない
結果整合性でよい
ここはもう少し詰める
オンメモリにする
Cassandraのブログを参考にする
実装メモ
設定をクラスタでどのように共有するか
プロセス
コーディネータ
レプリカノードの選択
Node.list/0からノードを取得し、ハッシュの余りから連番ではノードが落ちたときに崩壊する
なので、本来あるべきノードリストは自前で持ったほうがいい
他のノードとの協調
ストレージへの指示
ノードダウン時
モニタで検出
持っているキーを全探査
死んだノードを含めずに再計算、分散して格納しなおす
ストレージ
ローカルに値を保存する
バックエンドは切り替えられるように
メモリ (ElixirのMap)
pros: 高速、実装が簡単
cons: 揮発性、書き込みが直列、小容量
ETS
pros: 高速、読み込みが並列にできる
cons: 揮発性、書き込みが直列、小容量
ディスク
pros: 永続性、大容量
cons: 実装が面倒
ストレージの本質的な違いは揮発性と速度だけでは？
読み書きの直列/並列は実装都合？
HTTPサーバ
ただのインターフェス変換
Elixir関数 ←→ REST API
起動時
どうやってノードを認識する？
理想的にはクラスタ内のノード全て、としたいが、これは自動でスケールする機能が必要
なので、今は環境変数にノードを適当に突っ込んでおく、空ならば自分のみ
コンシステントハッシュ
redis
小さいクラスタが集まってる
シャーディング
feature work
HTTP APIを実装する
整合性について
処理が失敗したレプリケーションノードへの復旧処理
Storageへの処理の部分で直列化されてしまう
更にシャーディングなどすれば並行に読み書きできる？
make runの改善
デバッグ用はいいとして、ちゃんとしたアプリケーションコンテナぐらいは作ってみたい
ExUnitをもう少し使う
テストを書こうね
うまいことやれば最後の1台になってもKVSとしては動かせる？