Upgrade to Pro — share decks privately, control downloads, hide ads and more …

サーバーゆる勉強会 DBMS の仕組み編

Avatar for Ibuki Kaji Ibuki Kaji
January 13, 2025

サーバーゆる勉強会 DBMS の仕組み編

Avatar for Ibuki Kaji

Ibuki Kaji

January 13, 2025
Tweet

More Decks by Ibuki Kaji

Other Decks in Programming

Transcript

  1. 鍛冶 維吹 - kaji, ibuki 9 2022年 株式会社サイバーエージェント新卒入B 9 株式会社

    WinTicket 所 9 サーバーチームマネージャー 自己紹介 @kj4555 @kj455
  2. 参考資料 Å Å Å Å Å Database Design and Implementatio

    詳説データベー3 データ指向アプリケーションデザイF 各種Spannerドキュメン0 ネットの海に落ちているQiita/Zenn これをベースに話します [Database Design and Implementation : Sciore, Edward] (https://www.amazon.co.jp/-/en/Edward-Sciore-ebook/dp/B085DZM79S) *本書固有の命名については 色で記載 オレンジ
  3. 01 Disk/File 02 Memory 03 Transaction 04 Record 05 Metadata

    06 Query/Parse/Plan 目次 低レイヤー 高レイヤー
  4. モチベーション 「ACID特性」を満たした„  Atomicity(原子性): 全ての操作が全体として成功するか、全て失敗することを保m  Consistency(一貫性): データベースの状態が常に整合性を保B  Isolation(独立性):

    他のトランザクションは、現在進行中のトランザクションに影 響を与えな„  Durability(永続性): トランザクションが確定(コミット)された後は、その変更が 永続的に保持される
  5. モチベーション 「ACID特性」を満たしたR I Atomicity(原子性): 全ての操作が全体として成功するか、全て失敗することを保y I I I Durability(永続性): トランザクションが確定(コミット)された後は、その変更が

    永続的に保持される Consistency(一貫性): データベースの状態が常に整合性を保f Isolation(独立性): 他のトランザクションは、現在進行中のトランザクションに影 響を与えなR
  6. モチベーション 「ACID特性」を満たしたR I Atomicity(原子性): 全ての操作が全体として成功するか、全て失敗することを保y I I I Durability(永続性): トランザクションが確定(コミット)された後は、その変更が

    永続的に保持される Consistency(一貫性): データベースの状態が常に整合性を保f Isolation(独立性): 他のトランザクションは、現在進行中のトランザクションに影 響を与えなR →「リカバリー」が実現できれば良い
  7. リカバリー( ) RecoveryMgr そもそも..S Y トランザクション実行時にはログを記録してお1 Y Star@ Y SetXX#

    Y Commit / RollbacV Y Checkpoint ログの例 Database Design and Implementation p.11より引用
  8. WAL(Write Ahead Log) g Spanner の内部サーバーも WAL を使っていC g PostgreSQL

    には WAL を無効にすることでパフォーマンスを上げるオプションがあっ たりすC g [spanner-osdi2012.pdf](https://static.googleusercontent.com/media/research.google.com/ja//archive/spanner-osdi2012.pdf‡ g [WALの設定](https://www.postgresql.jp/docs/9.4/wal-configuration.html‡ g なお、耐障害性
  9. ロック - ConcurrencyMgr ①どの領域に対して、②どのロックが取られているかを管理する ②ロッW gV ReaderShared ロッW eV WriterShared

    ロッW `V Exclusive ロッW XV WriterSharedTimestamp ロック Cloud Spanner におけるロックのタイプ https://cloud.google.com/blog/ja/products/databases/transaction-locking-in-cloud-spanner ①領‹ † 粒度が細かい方がロックの競合が発生しづら † Spannerは行x列の交点(セル)単位
  10. ロック - ConcurrencyMgr 複数のトランザクションがお互いのロックの解放を待ち合う 「デッドロック」を検知・解消する必要がある デッドロック解消アルゴリズムC 0 Wait-Di" 0 タイムリミッƒ

    0 Wound-Wait(SpannerはこれU 0 ... Cloud Spanner におけるロックのタイプ https://cloud.google.com/blog/ja/products/databases/transaction-locking-in-cloud-spanner
  11. マルチバージョン同時実行制御(MVCC) d 最新のデータを読もうとするからロックが発生す€ d 古いデータの読み取りではロックが発生しなa d Spanner における Staleness Rea9

    d 内部的には複数のバージョンのデータを保持することで実現 データのバージョン, トランザクションの前後関係の判定には タイムスタンプで使われることが多い
  12. 分散システムにおけるタイムスタンプの信頼性 q トランザクションの前後関係はタイムスタンプで決めることが多f q Spanner など、分散システムになると、マシンの時刻は信用できなf q 実行マシンによって若干時刻がズレていた場合、前後関係を保証できない 分散 DB

    ごとに対策は色々H q Google Spanner: True Time APIg q CochroachDB: Hybrid Logical Clock (HLC) q [Spanner: TrueTime と外部整合性](https://cloud.google.com/spanner/docs/true-time-external-consistency?hl=ja{ q [Hybrid Logical Clock (HLC) Timestamps](https://www.cockroachlabs.com/glossary/distributed-db/hybrid-logical-clock-hlc-timestamps/)
  13. トランザクションにまつわる”アノマリー” DBによってはトランザクション中に変なデータが見えたり、見えなかったりする このような一貫性のない挙動のことをアノマリーと呼ぶ “Spanner はすごい”ので、Anomaly は発生しない (Dirty Read, Lost Update,

    Non-repeatable Read, Phantom Read, Read Skew, Write Skew) È [Cloud Spanner を使って様々な Anomaly に立ち向かう | by Yuki Furuyama | google-cloud-jp | Medium](https://medium.com/google- cloud-jp/cloud-spanner-%E3%82%92%E4%BD%BF%E3%81%A3%E3%81%A6%E6%A7%98%E3%80%85%E3%81%AA-anomaly- %E3%81%AB%E7%AB%8B%E3%81%A1%E5%90%91%E3%81%8B%E3%81%86-5132f691ccf4… È [Cloud Spanner におけるトランザクションの排他制御 | TECH | NRI Digital](https://www.nri-digital.jp/tech/20230926-14591/)
  14. レコード管理 テーブルのスキーマ( )が決まると..D % 各フィールドのオフセットが決まる( 6 % 1レコードの大きさが決ま2 % N番目のレコードのオフセットが決まる

    →テーブルのすべてのレコードを走査できる( , ) Schema Layout RecordPage TableScan *実際にはB-Treeなどの場合が多い Database Design and Implementation p.166,167より引用
  15. メタデータ - テーブル 例えば..' 4 テーブ& 4 テーブル$ 4 レコードの大き

    4 フィール 4 名 4  4 大き 4 オフセット テーブル名 テーブル名 Database Design and Implementation p.192より引用
  16. メタデータ - 統計データ 例えば..6 H テーブルのブロック数(B& H テーブルのレコード数(R& H フィールドごとのユニークなデータ種(V)

    →クエリのコスト算出等に利用 統計データの例 Database Design and Implementation p.197より引用
  17. Parse クエリ文字列を解析(パース)し、扱いやすいデータに変換する Select SName From STUDENT Where GradYear = 2020

    and MajorId = 10 QueryData { fields: []{“SName”}, tables: []{“STUDENT”}, pred: Predicate{ terms: []Term{“GradYear = 2020”, “MajorId = “”10”} } } ただの文字列 QueryData構造体 Parse→Plan→Scan
  18. Scan 各種演算子ごとに Scan が実装される 例えば..@ (行から列の絞り込み (行の絞り込み (2テーブルの直積結果を返す) これらを組み合わせてクエリを処理する s

    ProjectScan s SelectScan s ProductScan Select SName From STUDENT Where GradYear = 2020 and MajorId = 10 Parse→Plan→Scan スキャンツリー Database Design and Implementation p.227より引用
  19. Scan Parse→Plan→Scan “foo”, 2020, 10 “foo”, 2019, 10 “foo”, 2019,

    10 “foo”, 2020, 10 “foo”, 2020, 10 “foo” “foo”, 2020, 9 “bar”, 2020, 10 “bar”, 2020, 10 “bar” “bar”, 2020, 10 各スキャンを通じてパイプライン的にデータを取得する様子:
  20. 参考資料 d [Database Design and Implementation: Second Edition](https://www.amazon.co.jp/-/en/Edward-Sciore/dp/3030338355 d [詳説

    データベース - O'Reilly Japan](https://www.oreilly.co.jp/books/9784873119540/ d [データ指向アプリケーションデザイン - O'Reilly Japan](https://www.oreilly.co.jp/books/9784873118703/ d [Spanner: Google's Globally-Distributed Database](https://static.googleusercontent.com/media/research.google.com/ja//archive/spanner-osdi2012.pdf d [Cloud Spanner におけるトランザクションのロックについて | Google Cloud 公式ブログ](https://cloud.google.com/blog/ja/products/databases/transaction- locking-in-cloud-spanner d [Spanner: TrueTime と外部整合性 | Google Cloud](https://cloud.google.com/spanner/docs/true-time-external-consistency?hl=ja d [Cloud Spanner を使って様々な Anomaly に立ち向かう | by Yuki Furuyama | google-cloud-jp | Medium](https://medium.com/google-cloud-jp/cloud-spanner- %E3%82%92%E4%BD%BF%E3%81%A3%E3%81%A6%E6%A7%98%E3%80%85%E3%81%AA-anomaly- %E3%81%AB%E7%AB%8B%E3%81%A1%E5%90%91%E3%81%8B%E3%81%86-5132f691ccf4 d [データベース(RDB)を理解できるようになる動画 / UUIDを主キーにすると遅い?](https://www.youtube.com/watch?v=ifnszOLLgjs&t=627s)