データベース入門（アーキテクチャ・分散のさわり）

0. データモデル

0-1. データモデルとは

• データモデルには、多くの種類があり、多くのアプリケーションは、幾つものデータモデルのレイヤーを積み重ねていくことによって表現される。

1. アプリケーションのレイヤーにおける、現実世界（人、組織、物、行動、金銭の流れなど）のモデル。
2. 1.のデータ構造を保存するための、JSONやXMLドキュメント、リレーショナルデータベースのテーブル、あるいはグラフモデル。汎用的データモデルという。
3. 2.のデータを、メモリ、ディスク、ネットワーク上でバイト列として表現するモデル。これにより様々な方法でキューイング、検索、操作、処理できるようになる。
4. 3.のバイト列を電流や光のバルス、電磁気などで表現するモデル。

0-2. データの保存とクエリのための汎用的データモデル

0-2-1. リレーショナルデータモデル

• データをリレーション（SQLにおけるテーブル）で構成し、それぞれのリレーションは、順序なしのタプル（SQLにおける行）の集合。
• リレーショナルデータベースは、ビジネスデータの処理(トランザクション処理やバッチ処理)を起源とし、クリーンなインターフェースによって背後の実装の詳細を隠蔽することを目標とした。
• アプリケーション上のオブジェクトとテーブル上のデータモデルの間に、インピーダンスミスマッチ が生じる。
• スキーマオンライト（スキーマは明示され、データベースは書き込まれるすべてのデータがそのスキーマに従っていることを保証する）。

0-2-2. ドキュメントモデル

• NoSQL（Not Only SQL）データベースが広まる。
• リレーショナルデータモデルと比較して、以下のような特徴を持つ。
  • 巨大なデータセットや書き込みのスループットを含む、スケーラビリティ。
  • スキーマの制約がなく、動的で表現力に富む。
• スキーマオンリード（データの構造は暗黙のものであり、データの読み取り時にのみ解釈される。※ スキーマレスというわけではない）。

0-2-3. JSON

• ほぼそれ自体で完結するドキュメントである履歴書のようなデータ構造には、JSONが適している。
  • MongoDB、RethinkDBなどのドキュメント指向データベースはこれをサポートしている。
  • MySQL、PostgreSQLなどでも、JSON型もサポートされるようになった。

メリット

• スキーマが柔軟である。
• ローカリティに優れる。
  • リレーショナルデータベースでは複数のクエリの実行か、複数の結合をした上でのクエリが必要な場合でも、JSONであれば（すべての情報が1箇所に集まっているため、）1度のクエリだけで十分になる。
  • 一度にドキュメントの大部分が必要になる場合にメリットになる。

デメリット

• JSONでは1対多のツリー構造には結合が必要ないことから、多くのドキュメントデータベースでは結合のサポートが弱い。
• アプリケーションに機能が追加されていくにつれて結合が必要になることが多いため、結合の処理がアプリケーション側で必要になり、多対多のリレーションが多く発生する場合にはアプリケーションのコードが複雑になる。
  • 非正規化（データを複製）するか、あるレコードから他のレコードへの参照を自分で辿る必要がある。

1. 単一のデータベースについて考える

1-1. DBMSのアーキテクチャの全体像

出典：『Database Management Systems 3rd ed.』（⁠Raghu Ramakrishnan、Johannes Gehrke 著、McGraw Hill Higher Education、2002年、p.405）
第1回 記憶装置のトレードオフとバッファの考え方―すべてをとることができないとき　（1） - gihyo.jp

1-2. クエリプロセッサ（クエリ評価エンジン）

出典：『Database Management Systems 3rd ed.』（⁠Raghu Ramakrishnan、Johannes Gehrke 著、McGraw Hill Higher Education、2002年、p.405）
第4回 クエリ評価エンジンと実行計画―“シェフおまかせ”はいつも美味しいのか（1） - gihyo.jp

クライアント(アプリケーションプログラムやSQLインタフェースなど)がSQLを記述して実行し、DBMSがSQLを受け取るところから始まる。

パーサ

まずは受け取ったSQLのクエリを、パーサによって文法的に正しいかチェックする。

オプティマイザ

次に、オプティマイザが カタログマネージャが管理するテーブルやインデックスの統計情報を見て、プラン生成とコスト評価を行なったのち、最も低コストな実行計画を1つ決定する。

EXPLAIN文を実行すると、実行計画を確認することができる。

プラン評価

プラン評価で、実行計画を受け取って、DBMSが実行可能なコードへ変換し、実行する。

1-3. ストレージエンジン（データベースエンジン）

• データベースにおいて、データへのアクセス処理（書き込みと読み出し）を行うプログラム。
  • データの取得方法、保存方法、処理方法がストレージエンジンによって異なる。
  • 同時実行制御という、トランザクションマネージャやロックマネージャの機能を含む。
• MySQLのストレージエンジンには、MyISAM（5.5未満でデフォルト）、InnoDB（5.5以降でデフォルト）などがある。
  ※ MyISAMはトランザクション非対応であったり、テーブル単位でロックを行うため更新に不向きなどの問題があった一方で、InnoDBではトランザクション対応と行ロックが備わっている。

第13章 クエリプロセッサ クエリプロセッサとは - SQL Server 7.0 リソースキット
第１回：MySQLストレージエンジンの概要 - ThinkIT
MySQLのストレージエンジンについて - Qiita

1-4. 利用用途の観点から見たデータベース（ストレージエンジン）の種類

OLTP（Online Transaction Processing/オンライントランザクション処理システム）

• トランザクションのワークロードに対して最適化されたストレージエンジン。
• 一般的にイメージするデータベース。レコードの挿入や更新が、ユーザーの入力に基づいて行われる。
• インデックスを利用してデータの読み取りを行う。
  • B-Tree, Hash index, SSTable（Sorted String Table）
• ランダムアクセスと低レイテンシの書き込みが求められる。

OLAP（Online Analytic Processing/オンライン分析処理システム）

• 分析のワークロードに対して最適化されたストレージエンジン。
• 分析目的で使われ、結果がビジネスインテリジェンス（BI）のために利用されるデータベース。データウェアハウス。
• 負荷が高く、データセットの大部分をスキャンするような、アドホックな（特定の）分析クエリがリードオンリーで実行される。
• OLTPのすべてのデータのコピーが、定期的なデータダンプや連続的な更新のストリームによって書き込まれる。

1-5. インデックス

• データベースから特定のキーの値を効率的に見つけるためのデータ構造のこと。
• うまく選択すれば、読み出しのクエリを高速にしてくれるが、あらゆるインデックスは書き込みを低速にする。
  • そのためデフォルトで全てにインデックスをつけるようなことはしない。
• OLTPは、選択するインデックス構造に関して2つの考え方のストレージエンジンに分かれる。
  • log-structuredとページ指向（Bツリー）

log-structured

• 比較的最近開発されたインデックス構造。
• ファイルへの追記と古くなったファイルの削除だけを行うことができる。一度書かれたファイルは決して更新されない（レコードの追加とコンパクション操作の分離）。
• 更新時のランダムアクセスを減らせる一方で、書き込みの増幅が生じるなどの特徴がある。
• 例：SSSTable（Sorted String Table）、LSM（Log-Structured Merge）ツリー、Cassandra、Lucene等

Bツリー

• 最も広く使われるインデックス構造。
• RDBMSでは、基本CREATE INDEX命令を実行するとB-Treeが1個作られる。
• キーと値のペアをキーでソートされた状態で保持する。
  • キーと値のルックアップや範囲に対するクエリを効率よく処理できる。
• データベースを（メモリ上ではなく）ディスク上でページに分割する。
  • １つのページは一度に読み書きされ、各ページはアドレスあるいは場所によって識別できるので、あるページから他のページを参照できる（ポインタに似ている）。
• このアルゴリズムは、ツリーのバランスが保たれることを保証するので、nこのキーを持つBツリーの深さは常にO（log n）になる。
• ページ数が増えても木の高さがあまり増えない（深くならない）ので、ディスクへのランダムアクセスの回数を減らすのに役立つ。
• 例：MySQL、PostgreSQLなどのRDB等

1-6. トランザクション

• データベースの花形技術であり、アプリケーションが複数の読み書きを一つの論理的な単位としてまとめる方法。
• トランザクションは、成功（コミット/commit）もしくは失敗（中断/abort、ロールバック/rollback）する。
• トランザクションが満たすべき性質、安全性の保証を示す語として、ACID がある。
• データベースは、複数のトランザクションが並行して実行される時、どのようなレベルでそれぞれのトランザクションを分離するのか（トランザクション分離レベル）を選択できる。
  • それぞれの分離レベルで。どのような異常状態（Anomaly、あるいは競合状態/race-condition） が発生するか、いくつかのパターンが存在する。

ACID

• トランザクションが満たすべき性質、安全性の保証を示す語。

※ ACIDの実装はデータベースごとに異なるため、実際にどういった保証を期待できるかははっきりしない。

• Atomicity（原子性）
  • 中途半端な結果にならないこと。
    • エラーの際にトランザクションを中断し、そのトランザクションのすべての書き込みを破棄できる。
• Consistency（一貫性）
  • 少なくとも4つの異なる意味で使われている。
    1. レプリカの一貫性と、非同期にレプリケーションを行うシステムで生じる結果整合性。
    2. コンシステントハッシュ法
    3. CAP定理における線形化可能性。※ アプリケーションの表示の（古いキャッシュやレプリカの影響を受けない）最新性の保証のこと。
    4. データベースが「良い状態」にあることを示すアプリケーション固有の概念。
• Isolation（分離性）
  • 並行して実行されたトランザクションがお互いから分離されており、異常（Anomaly、race condition）が発生しないこと。
  • 古典的なデータベースの教科書では、分離性はSerializability（直列化可能性）を指すが、実際には直列化可能な分離性が用いられることはほとんどない。
• Durability（永続性）
  • トランザクションのコミットが成功したら、仮にハードウェアの障害やデータベースのクラッシュがあったとしても、そのトランザクションで書き込まれたすべてのデータは失われないことを約束するもの。

1-7. トランザクション分離レベル

• 米国国家規格協会（ANSI）によって定められた、データベースが保証するIsolation（分離性）の4つのレベルのこと。
  • READ UNCOMMITTED
  • READ COMMITTED
  • REPEATABLE READ
  • SERIALIZABLE
• 以下のようなアノマリーが存在する。
  • Dirty Read
  • Read Skew
  • Lost Update
  • Non-Repeatable Read
  • Write Skew
  • Phantom Read

https://zenn.dev/mpyw/articles/rdb-transaction-isolations
https://qiita.com/kumagi/items/1dc1a91ec007365ac694
https://qiita.com/kumagi/items/5ef5e404546736ebac49
https://qiita.com/PruneMazui/items/4135fcf7621869726b4b

SERIALIZABLE

• かつては基本の分離レベルだった。トランザクション分離レベルの中で最も強い分離レベルとされている。
• 並行して実行される複数のトランザクションが、直列で（順番に）実行された場合と同じになることを保証する。= Anomalyがすべて発生しない。
  • 2PL（ツーフェーズロック） というアルゴリズムによって実現される。

2PL（ツーフェーズロック）

• 2つのフェーズが存在するロック。
  • 最初のフェーズ（トランザクションの実行中）でロックを取得し、2番目のフェーズ（トランザクションの終了時点）がすべてのロックをリリースする。
• 共有モードと排他モードの2つの種類のロックを取ることができる。
• デッドロックが容易に生じ、またロックの取得と解放のオーバーヘッドがあるためパフォーマンスが悪い。

共有モード

• オブジェクトからの読み取りを行う場合、トランザクションはまず共有モードのロックを取得しなければならない。
• 共有モードのロックは複数のトランザクションが同時に取得できるが、他のトランザクションがそのオブジェクトの排他ロックを取得していたら、共有ロックを取得しようとするトランザクションはその排他ロックの解放を待たなければならない。

排他モード

• オブジェクトへの書き込みを行う場合、トランザクションはまず排他モードのロックを取得しなければならない。
• 他のトランザクションが同時に同じロックを（共有モードか排他モードかに関わらず）保持することは許されず、そのオブジェクトのロックがすでに保持されているなら、トランザクションはその解放を待たなければならない。

デッドロック

• 他のトランザクションがあるトランザクションのロック解放を待ち続け、逆にあるトランザクションは他のトランザクションのロック解放を待ち続けてしまうこと。
• データベースはトランザクション間のデッドロックを自動的に検出し、いずれかのトランザクションを中断させて他のトランザクションが処理を進められるようにする。

READ UNCOMMITTED

• Dirty Writeが発生しない。
  • 書き込み不整合であり、他のトランザクションでコミットされていない変更を参照してしまうアノマリー。
• Dirty Readが発生する。
  • 読み取り不整合であり、他のトランザクションでコミットされていない変更を参照してしまうアノマリー。
• 基本的に使用されることはない 。

Dirty Write

• あるトランザクションがデータベースにデータを書き込み、まだコミットはされていない状態の時、他のトランザクションからの書き込みで、コミットされていないデータを上書きしてしまうこと。

※ 実際にはどの分離レベルでも発生しない。

Dirty Read

• あるトランザクションがデータベースにデータを書き込み、まだコミットはされていない状態の時、他のトランザクションからの読み取りで、コミットされていないデータを見れてしまうこと。

READ COMMITTED

• Dirty Read 、Dirty Write が発生しない。
  • 行レベルロックを使用する。
• Non-Repeatable Read 、 Read Skew（読み取りスキュー）が発生する。
  • 読み取り不整合であり、他のトランザクションでコミットされた変更を参照してしまうアノマリー。
• Lost Updateが発生する。
  • 更新競合であり、他のトランザクションでコミットされた変更を上書きしてしまうアノマリー。
• Oracle 11g、PostgreSQL、SQL Server 2012、MemSQL等でデフォルトの設定。

行レベルロック

行レベルロックは、行が更新されたとき（または削除、更新のために印が付けられたとき）に獲得されます。行レベルロックはデータの問い合わせに影響を与えません。 同じ行への書き込みのみを阻止します。

1. あるトランザクションがあるレコードを更新する時、あるトランザクションはそのレコードのロックを取得する。そのレコードのロックは、あるトランザクションがコミットされるまで保持される。
2. 他のトランザクションがそのレコードを更新する時、あるトランザクションがコミットされるのを待つ。
3. あるトランザクションがコミットされたら、他のトランザクションはそのレコードのロックを取得して処理を続ける。

Non-Repeatable Read 、 Read Skew（読み取りスキュー）

• あるトランザクションがトランザクションを開始し、他のトランザクションがデータを更新・コミットした時、あるトランザクションからの読み取りで、コミットされているデータを見れてしまうこと。
  ※ もう一度あるトランザクションを実行した場合は、あるトランザクションの開始時と読み取り時で不整合は発生しない。

Lost Update（更新競合）

• アプリケーションが何らかの値をデータベースから読み取り、その値を変更して書き戻す（read-modify-writeサイクル）場合に生じる。
  • 2つのトランザクションが並行してこの処理を行うと、2つ目の書き込みは1つ目の変更を踏まえてはいないので、変更の1つは失われることになる。
• 明示的なロックや、cursor stability（カーソル固定）によって対策される。

cursor stability（カーソル固定）

• 値の読み取りの際に排他ロックを取り、更新の適用が終わるまで他のトランザクションがその値を読めないようにすることで実装される、アトミックな操作のこと。

明示的なロック（SELECT ~ FOR UPDATE;）

• FOR UPDATE説は、クエリが返すすべての行に対するロックをデータベースが取得しなければならないことを示す。

REPEATABLE READ / Snapshot Isolation（スナップショット分離）

• Non-Repeatable Read 、 Read Skew（読み取りスキュー）が発生しない。
  • MVCCを使用する。
• Write Skew（書き込みスキュー）が発生する。
  • 直列化異常であり、あるトランザクションが読み取ったxを使ってyの変更をする時、他のトランザクションが読み取ったyの値を使ってxを変更してしまい、すれ違いざまに相手の変更前の値（y）に依存した更新を行なってしまうアノマリー。
• Phantom Readが発生する。
  • 読み取り不整合であり、他のトランザクションでコミットされた変更を参照してしまうアノマリー。

MVCC（マルチバージョン並行性制御）

• 進行中の複数のトランザクション（あるトランザクションと他のトランザクション）からそれぞれ異なる時点のデータベースの状態が見れるように、データベースが複数のコミット済みのバージョンを並べて管理、保持すること。
  • 例：
    • スナップショット分離が不要（read committed）な場合: 1つの値につき、コミットされたバージョンと、上書きされたもののまだコミットされていないバージョンの2つのバージョンだけを保持できればよい。
    • スナップショット分離が必要な場合: read committedではクエリごとに個別のスナップショットを使い、スナップショット分離ではトランザクション全体にわたって同じスナップショットを使う。
  • 仕様:
    • トランザクションが開始されると、そのトランザクションにはユニークなトランザクションIDが割り当てられる。
    • トランザクションがデータベースに書き込みを行うと、書き込まれたテーブルの行のcreated_byというフィールドに、トランザクションIDが設定される。
    • トランザクションがデータベースから読み取りを行う場合、そのトランザクションから見えるデータと見えないデータを決定するためにそのトランザクションのIDが使われる。

Write Skew（書き込みスキュー）

• 2つのトランザクションが同じ複数の値からの読み取りを行い、それらのうち、トランザクションごとにいくつかの（同じあるいは異なる）値を更新する場合に生じる。
  • 更新ロストの問題を一般化したもの。
  • ダーティライトや更新ロストは、別々のトランザクションが同じ値を更新するという特殊なケースで生じる。

Phantom Read

• あるトランザクションでの書き込みが他のトランザクションの中の検索クエリの結果を変化させてしまう効果のこと。
• スナップショット分離レベルでは、読み取りのみを行うクエリでのPhantom Readは防いでくれるが、読み書きを行うトランザクションでは、Phantom Readによって複雑なWrite Skewが生じることがある。

2. 複数のデータベースへの分散を考える

なぜ複数のマシンに渡ってデータベースを分散するか？

• スケーラビリティ
  • データの量、読み取りの負荷、書き込みの負荷が単一のマシンの手には余るほどになってきたら、複数のマシンに負荷を分散させるという方法がある。
• 耐障害性/高可用性
  • 1台のマシン（あるいは複数のマシンやネットワーク、あるいはデータセンター全体）がダウンしてもアプリケーションが動作し続けなければならないのであれば、複数のマシンを使って冗長性を持たせることができる。1台に障害が起きても、他のマシンが代理を務めてくれます。
• レイテンシ
  • ユーザーが世界中にいるなら、世界中の様々な場所にサーバーを配置して、それぞれのユーザーが地理的に近いデータセンターからレスポンスを受けられるようにできる。こうすることで、ユーザーが地球を半周してくる。ネットワークパケットを待たずにすむようになる。

2.1. レプリケーション

• 複数のマシンに同じデータのコピーを保持する方法。

レプリケーションの目的

• 読み取りのクエリを処理するマシン数をスケールアウトし、負荷分散させる（スループットの向上）
• 1つのマシンに障害があってもシステムが動作し続けられるようにする（可用性の向上）
• データを地理的にユーザーの近くで保持しておく（レイテンシを下げる）

レプリケーションの種類

• シングルリーダー（Leader）、マルチリーダー、リーダーレス

リーダーベースレプリケーション（アクティブ/パッシブ、マスター・スレーブレプリケーション）

• データベースへの書き込みを、すべてのレプリカで処理するための方法のこと。
  • リーダーに書き込みがあると、フォロワーが同じ順序で書き込む。
• データベースのコピーを保存している各ノードを、レプリカと呼ぶ。
• レプリカの1つの リーダー（マスター、プライマリ） と呼ぶ。
• 他のレプリカをフォロワー（スレーブ、セカンダリ、ホットスタンバイ、リードレプリカ） と呼ぶ。

レプリケーションにおけるトレードオフ

• 同期か非同期か
• 障害が起こしたレプリカの扱いをどうするか

もしPrimaryのデータベースが落ちてしまったら、Read ReplicaのデータベースがPrimaryに昇格するとかしないとか、扱いをどうするかを決める必要がある。

Amazon RDSにおけるレプリケーションのイメージ

• シングルリーダーレプリケーションの例になっている。
• メインとなるデータベース（Primary）があって、そこにRead/Writeをする。
• 非同期でRead専用のデータベース（Read Replica）にデータをレプリケーション（複製）する。
• Read ReplicaにはReadonlyのクエリだけを投げる。

2.2. パーティショニング（シャーディング）

• データベースを分割してデータを保存する方法。
  • レプリケーションでは、全く同じデータのコピーを複数のマシンに持つ手法だったが、パーティショニングでは複数のマシンにデータを分割する。
  • データを時間範囲(1時間、1日など)、あるいはキー範囲などで分割する。
    • 例：24時間ごとにログファイルを分割することで、該当日時のデータを見やすくするなど。
• 均等に負荷分散できているのであれば、良いパーティショニングと言える。
• 実際パーティショニングする時にはハッシュを使ったりとか、いろいろな手法がある。

パーティショニングの目的

• スケーラビリティ向上
  • クエリの負荷分散
• "良い"パーティショニングはデータとクエリの負荷をノード間で均等に分散させる
  • 偏りがある状態：skewという。
  • 負荷集中しているパーティション：ホットスポットという。

A-Zのアルファベットでパーティショニングする例

• 以下により負荷分散させている。
  • KeyがA-Gの場合はA-Gシャードにデータを入れる。
  • KeyがH-Zの場合はH-Zシャードにデータを入れる。
• 例えば、Keyが全体でA-Gであるデータしか存在せず、A-Gシャードにしかデータが存在しない場合、A-Gシャードは負荷が集中しているシャード（パーティション）であり、ホットスポットである。

製品在庫データが製品のKeyに基づいてシャーディング（分割）されます。
各シャードは、アルファベット順に編成された、連続する範囲のシャードKey (A-G および H-Z) のデータを保持します。シャーディングは負荷をより多くのコンピューターに分散するため、競合が減り、パフォーマンスが向上します。

参考

• データ指向アプリケーションデザイン
• 分散データシステム入門の決定版『データ指向アプリケーションデザイン』をたった30分で学んでみた#DataEngineeringStudy
• データベース研修（データベース基礎編）【ミクシィ22新卒技術研修】
• MySQL/Postgres におけるトランザクション分離レベルと発生するアノマリーを整理する - Zenn
• データベースとストレージのレプリケーション入門 / Intro-of-database-and-storage-replication - SpeakerDeck
• Rails Developers Meetup 2018 で「MySQL/InnoDB の裏側」を発表しました - あらびき日記