NOSQLのDBアーキテクチャ
大まかに分けると
マスタ型
整合性に関して
弱整合性
- 最初の更新からわずかなラグの後に全てのnodeのデータが更新される
- その瞬間だけを見れば、データの不整合がある
- 結果的に整合性が保たれればよい(結果整合性)という考えに基づいている
CAP定理
- 整合性(C)
- 可用性(A)
- 分断耐性(P)
- ネットワークが分断されても間違った結果(でーたの不整合)を引き起こさない
- システムが継続して使用できる(≠可用性)
- この特性を満たすためにあえて一部(または全体)の機能を停止するものもある
- 分散システムはこの3つのうち最大2つしか満たすことが出来ない
詳しくは過去のポスト参照
portaltan.hatenablog.com
ACID/BASE
- 整合性よりも可溶性と分断耐性が求められるのであれば、その特性はBASEであるべき(Dynamo)
- CとPを満たすことが場合はACID特性であるべき(Bigtable)
Quorum
- R(読み出し) + W(書き込み) > N(冗長度)
整合性の修復
- 結果整合性の場合、不整合が起きたときの修復方法
- リードリペア:複製データの読み出しをすべてのnodeに送り、差異がある場合はバックグラウンド処理で修復
- ヒンテッドハンドオフ:A⇒Bの複製の際に、Bが故障している場合、Cに対して「B復帰したら更新するように」という指示を出しておく
- マーカル・ツリー:樹形図構造のアルゴリズムによってデータの整合性を確認。差異がある場合は手動で修復
データ振り分け
コンシステントハッシング
- keyの値をハッシュ関数によって求める
- Cassandra, Riak, Voldemort
シャーディング
- あらかじめ定めた規則にしたがって各ノードにデータを割り当てていく(頭文字の文字や数字など)
- データが偏る可能性がある
- ノードの負荷が均等になるようにデータを再配置、再分割を行うわなければいけない
- BigtableやHBaseは自動で再分割、再配置を行う
- または、割り当て先を小さくして細かく分割しておく
ハイブリッド型
- 両者を採用したハイブリッド型なども存在する
- ハッシュを出した後でそのハッシュ値によって分散してシャーディングするなど
実際のストレージ
LSM-Tree(Log Structured Merge Tree)
- Bigtableから派生したものは使用していることが多い
- 3つのテーブルからなる
- Mem-table:メモリ領域
- SS table:物理ストレージ領域
- Commit Log:ログ
- 書き込み処理⇒Commit log記入⇒Memテーブルに保存⇒(一定上達したら)⇒SSテーブルへ書き込み(フラッシュ)⇒Memテーブルは空になる
- SSテーブルは一度作成されるとその内容が更新されることはない
- 更新やデータの削除された時はmemテーブルに一次保持された後、新しい世代のSSテーブルに書き込まれる
- ディスクからこのデータを探し出して更新という手順を踏まないため、書き込み性能が速い。とにかく速い
- 読み込みの際はまず求めるデータmemテーブルに残っているか、SSテーブルにフラッシュ済みかを返す
- その後実際の読み込みではmemにあると速い
- memやSSに対象のKeyが入っているかを高速に判断するためにブルームフィルタというデータ構造も同時に格納される
- 毎世代分SSテーブルを残しておくとデータ容量がかさむため、コンパクションを行い、全てのSSテーブルを一つにまとめる
- Commit logとSS tableへの書き込みは、シーケンシャル(追記)なので速い)
- ランダムアクセスで毎回データを書き換えすると遅い
- 読み込み性能は低下している
- ランダムアクセスだし、どの世代のSSテーブルにあるかわからないから
- 対策として定期的にコンパクションや、そもそもメモリに可能な限り積むようにしている
障害検知
ゴシッププロトコル
- 各nodeは毎秒ランダムな相手nodeにコンタクトをして、データ割り当て状況と配置に関するデータを交換する
- このデータは各nodeに保存され、どのnodeにデータを複製するかの判断材料となる
- 各nodeがそれぞれ他のnodeの生存リストを持っている
- 利用できないnodeもは定期的にアクセスそて死んだままかの確認