db-memo.md

DB・データ構造 メモ

ACID

• ACID

  • Atomicity
  • Consistency
  • Isolation
  • Durability

• Transaction Isolation Level は速度のためにACIDのIを緩和する設定。

  • Wikipedia トランザクション分離レベル

ANSI/ISO SQL Standard

• SERIALIZABLE ⸺ 安全だが遅い。とはいえトランザクション同士の順序までは保証されない。

• REPEATABLE READ ⸺ Phantom Readのリスクがある。

• READ COMMITTED ⸺ Phantom Read, Non-Repeatable Readのリスクがある。

• READ UNCOMMITTED ⸺ Dirty Read, Phantom Read, Non-Repeatable Readのリスクがある。 感想: いつ使える?

• Dirty Read ⸺ 不完全/計算途中のデータが読めてしまうリスク

• Phantom Read ⸺ 削除済みやこれから追加されるはずのデータが読めてしまうリスク

• Non-Repeatable Read ⸺ 同じトランザクション中なのに、読むたびに異なり矛盾するリスク

NoSQL

• BASE

  • Basically Available
  • Soft-State
  • Eventual Consistency
  • ACID ⇄ BASE は対義語になっている。化学の酸⇄塩基にかけたシャレ。

• Linearizability ⸺ Serializability(直列化したときと同じ結果になる)とは別!!! 実時間。

• External Consistency

• Quiescent Consistency

• Sequential Consistency

• Release Consistency

• Causal Consistency

  • →Vector Clock

• PRAM consistency

• Read Your Write Consistency

• Eventual Consistency

• https://qiita.com/kumagi/items/3867862c6be65328f89c

• 論理クロック

  • Lamport Clock ⸺ クロックの値はスカラ。全順序を与える。cons: 本来は比較不能なイベントも比較できて順序がついてしまう。
  • Vector Clock ⸺ クロックの値はプロセス数/ノード数の次元のベクタ。半順序を与える。比較不能 ⇔ 並行 ⇔ t_A||t_B である場合もある。論理的に正確そう(感想)。処理が重そう（感想)。
  • Mitsuhisa Sato 2012分散システム講義資料 同期(1) 論理クロック
  • Kei Takahashi 並列分散処理 ベクタークロック

その他

• CAP theorem
• MVCC
• Split brain
• two phase commit
• voting
• starvation
• concurrent / parallel
• critical section
• ポリグロット・パーシステンス / マルチモデルデータベース

よさげな資料

• https://www.hpcs.cs.tsukuba.ac.jp/~msato/lecture-note/
• https://www-higashi.ist.osaka-u.ac.jp/~nakata/mobile-cp/
• http://funini.com/kei/logos/
• https://christina04.hatenablog.com/entry/causal-consistency

このノートについて

• 昔のメモやカードを整理したり、勉強中のものを書き込んだりするノート
• DBだけでなく並行・並列プログラミング・分散コンピューティングの情報が混じってしまっているが、現代におけるDBの問題って大体並行並列が関わるからまぁこれでいい気もする。