GCP
概要 †
- データベースは大量にあるがそれぞれに特徴と注意点がある。
分散トランザクション †
Paxos †
- 要するに Level 0: n 個のマシンが m 個のメモリに思い思いのデータを書き込もうとして、完了して m 個のメモリの中身をみてみると、特定の値が過半数のメモリに書き込まれていることを保証するアルゴリズム。
- 要するに Level 1: n 台プロポーザがあって、プロポーザ i (0 <= i < n) が m 個あるアクセプタ (1 変数を格納するメモリ＋リクエスト返信ができるマシン) の部分集合に値 v_i を書き込もうとして、終了時に [m/2]+1 個のアクセプタが同一の値を有することを保証するアルゴリズム
- （プロポーザのリクエスト送信順序反転・アクセプタの受信順序反転・アクセプタの処理速度に問わず、[m/2] 個以下のアクセプタ障害を許容して）
- 誤った合意をしないことは保証できるが、停止する保証はない
必要性 †
- 同意の必要性
- 大陸に分かれてデータセンターがある。複数のデータセンタで単一のデータベースを管理したい。データベースは、クエリの手順が時系列まで含めて全世界で同一であれば、あらゆる時点でデータを復元することが可能。
- しかし、ほぼ同時に 2 つの異なるデータセンターからあるデータセンターにクエリが投げられた場合、どちらのクエリを最新として受け取るべきかがわからないので、時系列まで含めたクエリ列を全世界で共有して持つことは困難。
- Proposer (P), Acceptor (A), Learner (L)
- 各大陸各データセンターにはPがある。
- ユーザがクエリを投げて、とあるデータセンターにヒットする。
- データセンターのPは、「全世界のデータセンターさん！今僕が受け取ったクエリを最新のクエリとして受理して〜！全世界で共通して同じだと信じているクエリ列に追加して〜！」と**提案**全世界のデータセンターに送る（自分も含む）。
- 各大陸各データセンターにはAがある。
- 全世界のデータセンターに送られた提案は、Aにヒットする。
- もし複数のクエリが複数のデータセンターにヒットしていたら、あるAに異なる提案が異なる時間にヒットする可能性もあることに注意！これが分散合意システムが解決したい問題。どの提案を全世界のデータセンターが合意して、クエリ列の最新に追記するべきか？
- 合意されたクエリ列を時系列として扱うための効率的なアルゴリズムは Multi-Paxos が扱っている。Paxos は一回のクエリだけを扱う。
ロック †
- CAS 楽観ロック (特殊な CPU 命令があって面白い)
- 0. int val は複数スレッドから変更されうる
- 1. GET: int val の 値をとる -> oldval
- 2. CAS: int val に newval を書き込もうとする時に、int val に oldval がまだ格納されていたら newval を入れる。そうでなければ失敗を返す
- 通常 int val だけではよくわからないし重くなる可能性があるので、(変更バージョン, val) を保持して、GET での変更バージョンと CAS 時の変更バージョンを比較するように作られがち。
- CAS は CAS 命令という特殊な命令として実装されており、アトミックであることがハードウェア的に保障されている。
int compare_and_swap(int* reg, int oldval, int newval)
{
ATOMIC();
int old_reg_val = *reg;
if (old_reg_val == oldval)
*reg = newval;
END_ATOMIC();
return old_reg_val;
}
データベースの分類 †
有名な問題 †
- N+1問題
- id=1から100までを取得しようとしたときに、where id = 1みたいにしてO(n)個のSQL文を生成する問題
排他処理 †
悲観排他 ・ロックして他Txを待機させることで、複数同時更新による処理の不整合を防ぐ。
・設計次第では、デッドロックの恐れがある。
楽観排他 ・Tx開始からコミットまでの間に、他のTxによって更新されたリソースがないかを確認することで、処理の不整合を防ぐ。
・競合検出された時に、リトライ処理が必要。
MySQLではトランザクション時にreadもできないが、datastoreの場合はreadもwi4rteもできるが検知はできるという感じ。なので、競合検知したらリトライ処理をしないといけない
データベース各論 †
SQL †
- 平衡二分木なので、SQL OFFSETのようなものが計算量的に高速化する（index張れば）
JanusGraph?
グラフ式のデータベース。これを使うと数億レベルのグラフに対してクエリが投げられる。
データベース抽象化 †
DAO †
Javaなので本番のDBとテスト環境のDBを分ける方法
ODBC (Open DataBase? Connectivity) †
利用するデータベースの以外を吸収する手法
マイクロソフトが作ったデータベースとや霊取りするための通や腕、データベースとプログラムの間に入って媒する部品
DBC接続を行う際には
１．どの種類の
２．どのデータベースに
接続するかの情報が必要です。
例えば
SQLServerの「test_db」という名前のデータベースに接続する
のような情報ですね。
それに対応するODBCドライバがあれば、他の一般的なデータベースへのアクセスするのと同様な方法で利用することが可能になる！だから新たなデータベースが現れたらその都度Driverを売る会社が現れるということ。例: BQ
建前上は、ODBCを利用することにより、データベースの各ベンダ固有のインターフェースを抽象化し統一的にアクセスできるようになるはずだが、単純なケースはともかく、実際にはSQLの文法が各ベンダによって方言があるように、接続以外の問題でデータベースごとの仕様（例えばロック）や特性を理解する必要がなくなるわけではない。
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
