データベース基礎

 (tontinton.com)
5 ポイント 投稿者 GN⁺ 2023-12-16 | 1件のコメント | WhatsAppで共有

bashdbの基本

  • 最もシンプルなデータベースプログラムであるbashdbは、2つの bash 関数で構成される。
  • db_set関数はデータをファイルに追記し、db_get関数はデータを検索する。
  • bashdbの問題点として、耐久性、原子性、分離性、性能などがある。

bashdbを ACID に改善する

  • ACID は、原子性、一貫性、分離性、耐久性を意味するデータベーストランザクションの特性である。
  • bashdbの耐久性を改善するために、db_setにsyncコマンドを追加する。
  • 分離性のために、flockプログラムを使ってファイルロックを追加する。

耐久性

  • fsyncとfdatasyncは、書き込みバッファをディスクにフラッシュするシステムコールである。
  • syncコマンドはすべての「ダーティ」ページをディスクにフラッシュし、-dフラグはfdatasyncを呼び出す。

分離性

  • flockを使ってbashdbにマルチプロセス分離性を提供する。
  • flockはファイルロックのための Linux プログラムで、-sフラグを使って同時読み取りを許可する。

悪い知らせ

  • bashdbで原子性を保証する簡単な方法は見つからない。
  • 性能向上のためには、O(n)アルゴリズムを改善する必要がある。

ストレージエンジン

  • ストレージエンジンの目的は、永続ストレージにデータを読み書きするための抽象化を提供することである。
  • ストレージエンジンの設計は、ディスク I/O とディスクシークを最小化することを目標とする。

可変 B-Tree

  • B-Tree は、BST の空間局所性を持つ変種であり、ディスク I/O とシークを最小化する。
  • B-Tree は、ノードがより多くの子を持てるように一般化された BST である。

不変 LSM ツリー

  • LSM ツリーは、書き込み中心のワークロードに有利な、順次書き込みされる不変データ構造である。
  • LSM ツリーはメモリにデータをバッファし、一定容量に達するとソート済み SSTable としてフラッシュする。

ブルームフィルタ

  • ブルームフィルタは、集合内に項目が存在しないことを効率的に確認できる確率的データ構造である。
  • ブルームフィルタはハッシュ関数を使って動作し、空間計算量はO(log n)である。

Write Ahead Log

  • WAL は、すべてのトランザクション操作を記録する特別なファイルであり、データベースプロセスの起動時に状態を再構築する。

分離性

  • 分離性を達成するために、悲観的ロック、楽観的ロック、または MVCC を使用できる。
  • ANSI/ISO 標準 SQL 92 は、さまざまな読み取り分離レベルを定義している。

分散システム

  • 分散システムは複雑性を増すが、可用性と水平スケーリングのためにデータを複数のマシンに分散できる。
  • CAP 定理によれば、システムは一貫性、可用性、分断耐性のうち 2 つだけを保証できる。

コンシステントハッシング

  • コンシステントハッシングは、ノードの追加または削除時に移行される項目量を減らすデータ分割手法である。

GN⁺の意見:

  • データベースの基本的な問題と ACID 特性への理解は、データベースエンジニアリングの中核である。
  • bashdbの例は、実際のデータベースシステムで発生する問題を理解する助けになる。
  • ストレージエンジンと分散システムの設計は、データベースの性能と信頼性を決定する重要な要素である。

関連記事

1件のコメント

 
GN⁺ 2023-12-16
Hacker Newsのコメント

  • 1つ目のコメント要約:

    • LSMベースのデータベースの特性の1つは、削除されたレコードやトゥームストーン（tombstone）が長期間残ること。
    • トゥームストーンは最終レベルでのみスキップすべきであり、すべてのレベルでスキップしてはいけない。
    • そうしないと、上位レベルのトゥームストーンが除去され、下位レベルの項目が再び現れる可能性がある。
    • RocksDBのようなデータベースは、この問題を最適化によって解決しようとしている。

  • 2つ目のコメント要約:

    • 分散システムを学ぶのを避けるのは危険になり得る。
    • 実際、重要でないものではない本番システムはすべて分散システムである。
    • データベースがレプリカセットであるなら、それは分散システムである。
    • 分散システムについて学びたいなら、jepsen.io と raft.github.io を確認するとよい。

  • 3つ目のコメント要約:

    • 整合性には、データベースの整合性とアプリケーションの整合性がある。
    • 1つのテーブルでは ACID（原子性、一貫性、独立性、永続性）を達成できても、複数テーブルにまたがる書き込みでは失敗することがある。
    • 複数テーブルを同時に更新するトランザクションを扱うときは、すべてのテーブルが同時に更新されるか、まったく更新されないかでなければならない。

  • 4つ目のコメント要約:

    • データベース構築に関わるさまざまな概念について、優れた概要を提供する記事である。
    • SIMD を使って単一マシンで性能を引き出す話から、合意アルゴリズムまで扱っている。
    • データベースの信頼性や分散システムに適用される形式手法への言及もある。
    • Amazon S3 チームが TLA+ を使ってモデリングする方法についての興味深い論文がある。

  • 5つ目のコメント要約:

    • 多くの人は SQL を学んでデータベースを学ぶが、B木を理解することで RDBMS の強みと弱みをよりよく理解できる。
    • インデックスを追加してデータベースを高速化しようとするが、実際には問題を覆い隠しているにすぎない。
    • B木に適した問題もあるが、多くの問題はそうではない。
    • SQL はリモート B木システムに対するクエリインターフェースにすぎない。

  • 6つ目のコメント要約:

    • 多くの開発者は、ある時点で自分だけの小さなデータベースを作ってみる段階を経験する。
    • この過程を通じて、何がうまくいかないのかについて多くを学べる。
    • 自分でデータベースを作ることは、既存のソリューションへの敬意を深める助けになる。
    • ディスクからデータを高速かつ信頼性高く転送するのは難しい作業である。

  • 7つ目のコメント要約:

    • Bash バージョンでは、原子性はファイルを一時ファイルにコピーしてから修正し、sync; mv; sync を使うことで達成できる。

  • 8つ目のコメント要約:

    • ドキュメント API は MongoDB に似ており、リーダーレスレプリケーションは Cassandra に似ていて、1スレッドあたり1コアのアーキテクチャは ScyllaDB に似ている、とても魅力的な設計である。
    • そのすべてが Rust で実装されている。

  • 9つ目のコメント要約:

    • 『Database Internals』という本は驚くほど優れており、内部実装について深く掘り下げている。
    • これに似たほかの本があるか尋ねている。

  • 10個目のコメント要約:

    • 『Database Design and Implementation』という本も、Java で書かれた多くの例とともに非常に優れた読書である。
    • 実際の研究については、Andy（Pavlo）、Viktor Leis、Thorsten Grust、Thomas Neumann らの仕事を勧めている。