Zenn
😺

【10章】データベースリライアビリティエンジニアリングの読書メモ

2021/09/09に公開
O'Reilly
DBRE
tech

DBRE 輪読会 vol.10

2021/09/09

~ストレージ、インデックス、レプリケーション~

おさらい

1 章:学習を続け、チームを超えて改善を進める
2 章:SLO が全ての基礎
3 章:SLO のためにリスクを認識し低減する
4 章:SLO への影響を知るための⾒える化
5 章:インフラ構築の実践
6 章:インフラ構築の管理
7 章:リスクに応じたバックアップ・リカバリの実践
8 章:DB の安全なリリースのための施策
9 章:データを守る

この章で学ぶこと

ここまではデータベースの運用方法について。
ここからは、データベースの重要な機能である「データの格納」について詳しく見ていく。

おすすめ図書:
データ指向アプリケーションデザイン

目次

10.1 データ構造のストレージ

伝統的なデータベースは、テーブルとインデックスの組み合わせでデータを保存する。

  • テーブル
    • 主な記憶メカニズム
  • インデックス
    • アクセス時間を改善するために順序付けられたサブセット




10.1.1 データベースの行ストレージ

データはブロック（or ページ）呼ばれるものに格納される。

  • ブロック
    • ディスク上の特定のバイト列に対応している。
    • データを格納する最小単位
    • データのほかにメタデータを保持
      • ディスク上のアドレス情報、ブロックに対するアクティビティ情報等
    • エクステントと呼ばれる、より大きな入れものの単位で管理されることがある
  • エクステント

cncpt027

引用: Data Blocks, Extents, and Segments








バイナリツリー構造

多くのデータベースでは、データをバイナリツリー（B-tree）のフォーマットで構造化している。

  • バイナリツリー構造
    • データが増え続ける場合でも自分でバランシング（二分探索）する
    • データブロックの読み書き、そしてファイルシステムやデータベース向けの構造
    • B+treeやB*-treeといった改良版も存在する

※注: 本著ではバイナリツリー=B-treeとなるが、バイナリツリー=binary tree=二分木とB-tree=self-balancing binary search tree=平衡二分探索木は別物のようです。本著では、B-treeの意味として使われているように感じます。
参考: B 木 - Wikipedia

  • バイナリツリーが持つ特性と利点
    • 範囲ベースのクエリに対して高パフォーマンス
    • 単一行ベースの検索に対しては、もっとも理想的なモデルというわけではない(後述)
    • ソートされたキーに対しては、検索と範囲スキャンは効率的に実施できる
    • 大規模データセットにおいてページの読み込みを最小に抑えられる
    • ページごとにキーを格納する必要がないので、削除と挿入が効率的に実施できる
    • バイナリツリーがメモリにすべて載る場合は、極めてよいパフォーマンスを発揮する

10.1.2 ストアドストリングテーブルとログ構造のマージツリー

※注: おそらく訳ミスで、ストアドストリングテーブル:Stored String TableではなくSorted String Table（SSTable）

  • SSTable
    • 以下のようなデータベースのプライマリストレージとして機能するストレージエンジン
      • Apache Cassandra
      • Google Bigtable
      • HBase
      • LevelDB
      • Lucene
      • Riak
      • RocksDB
      • WiredTiger
    • ペアとなるキーと値がソートされた多数のファイルを保持している
    • ブロックストレージとは異なり、オーバーヘッドとなるメタデータは存在しない

ストアドストリングテーブルエンジンは、

  • データをすべてメモリ上に保持するインメモリテーブル
  • データをひとまとめ（バッチ）にしたディスク同期（フラッシュ）
  • 定期的に実行されるコンパクション

といったアルゴリズムを組み合わせて動作する。
このアルゴリズムは、ログ構造マージ（LSM）ツリーアーキテクチャとも呼ばれる。

10_01

引用: データベースリライアビリティエンジニアリング P204

10.1.3 インデックスの生成

ハッシュインデックス

検索キーをハッシュ関数でハッシュ化し、その値とレコードを紐付けて格納する（=ハッシュマップ）。
検索時は、検索キーのハッシュ値に基づいてレコードを取得する。

image-126.png

参考: Hash Index: Everything you Need to Know about Hashing

  • デメリット
    • ハッシュマップ自体がメモリに載せられるサイズである必要がある
    • 単一キーでの検索となるため、範囲検索には向かない

ビットマップインデックス

データをビットマップの配列として保持する。
バイナリツリーインデックスと異なり、カーディナリティ（データ濃度）が低い（=取りうる値の種類が少ない）場合に有効。

バイナリツリーにおける並び替え

バイナリツリーインデックスの並び替え（ソート）手法には様々なものがあるが、用途によって使い分ける必要がある。

  • 関数ベースの並び替え
    • 任意の関数で並び替えを行ったインデックス
  • 逆インデックス
    • ソート順を逆向きにしたインデックス
  • クラスタリングされたインデックス
    • I/O 最適化のためにテーブルを物理的に保存しているインデックス
    • バイナリツリーの葉ノードは、クラスタリングされたそれぞれにデータページを保持する
  • 空間インデックス
  • サーチインデックス
    • カラム内のサブセットとしての情報を検索するのに適したインデックス
    • インデックス化された値に対して検索できる
    • 例: ElasticSearch

10.2 データのレプリケーション

  • 単一リーダー（Single Leader）
    • リーダーが 1 つのノードのケース
    • データは常に特定のリーダーに送られる
  • 複数リーダー（Multiple Leader）
    • リーダーのロール（役割）を持った複数のノードが存在するケース
    • それぞれのリーダーがクラスタを通じてデータを保持する
  • リーダー不在（No Leader）
    • すべてのノードが書き込み可能

10.2.1 単一リーダーによるレプリケーション

  • 単一ノードに書き込みが行われるため、
    • コンフリクトが発生しない
    • データの一貫性が保たれる
  • すべてのオペレーションは確定して行われるため
    • それぞれのノードで実施された同じオペレーションに対して同じ結果が保証される

レプリケーション構成

単一リーダーの場合、次の 3 つの構成が使用可能

  • 非同期
    • 耐障害性よりもレイテンシを重視した構成（レイテンシ＞耐障害性）
  • 同期
    • レイテンシよりも耐障害性を重視した構成（耐障害性＞レイテンシ）
  • 準同期(=結果整合性)
    • レイテンシと耐障害性を両立させて妥協したもの

10.2.2 複数リーダーのレプリケーション

単一リーダーのレプリケーションの枠組みから抜け出す 2 つの方法

  1. 多次元レプリケーション
    • 各々のリーダーの役割を持ったノードが書き込みを行い、レプリカにそれを伝える
    • 典型的なパターンは、2 台のリーダーがそれぞれ違うデータセンタに配置されているパターン
  2. どこからでも書き込み可能なアプローチ
    • データベースクラスタ内の、どのノードも、いつでも読み込みと書き込みが行える
    • いったん書き込みを行った後は、ほかのノードにそれを伝える

どちらの方法を取るにせよ、複数リーダーのレプリケーションがもたらす複雑性については、覚悟しておかなければならない。

単一リーダーの場合は、書き込みを行うノードが 1 つであることからコンフリクトが発生しないが、複数リーダーの場合は、書き込み時に発生するコンフリクトを解消する必要がある。

複数リーダーを使用するメリット

  • 可用性
    • 単一リーダーのレプリケーションの場合、リーダーのフェイルオーバー時に少なからずダウンタイムが発生しますが、複数リーダーの場合はダウンタイムが発生しない
  • ローカリティ
    • 世界各国でサービスを提供する場合
    • 複数リーダーのレプリケーションを採用して、拠点ごとにリーダーを設置することで、レイテンシを低く抑える
  • ディザスタリカバリ（DR）
    • 複数リーダーを採用することで、ディザスタリカバリ用のデータセンターも、アクティブに活用することができる

10.3 まとめ

ストレージ、インデックス、レプリケーションはデータベースアーキテクチャの基本概念でもあるので、しっかりと知識を蓄え、難解であっても理解しておくことが大事。
次章は、データベースの各モデルについて見ていく。

GitHubで編集を提案

Discussion