読者です 読者をやめる 読者になる 読者になる

脳汁portal

アメリカ在住(だった)新米エンジニアがその日学んだIT知識を書き綴るブログ

NOSQLのDBアーキテクチャ

大まかに分けると

マスタ型

  • GoogleBigtableが元祖
  • Bigtable, CouchDB, HBase, Hibari, MongoDB
  • ひとつのマスタノードが配下にある多数のノードを分類する
  • マスタがダウンするとシステム全体が止まる
    • マスタを冗長化したり、他のnodeにマスタの代行をするようにして障害に備える

P2P

  • AmazonのDynamoが元祖
  • Dynamo, Cassandra, Riak, Voldemort, ROMA
  • マスターnodeが存在せず、全てのnodeがお互いに管理しあっている
  • 一つnodeがダウンしても、他のnodeが役割を引き継ぎます
    • SPOF(単一障害点)がない

整合性に関して

強整合性

  • データ更新中はDBをロックして、他の更新を受け付けない(排他制御)
    • RDBはこちら

弱整合性

  • 最初の更新からわずかなラグの後に全ての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復帰したら更新するように」という指示を出しておく
    • マーカル・ツリー:樹形図構造のアルゴリズムによってデータの整合性を確認。差異がある場合は手動で修復

データ振り分け

コンシステントハッシング

シャーディング

  • あらかじめ定めた規則にしたがって各ノードにデータを割り当てていく(頭文字の文字や数字など)
    • データが偏る可能性がある
  • ノードの負荷が均等になるようにデータを再配置、再分割を行うわなければいけない
    • 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もは定期的にアクセスそて死んだままかの確認