データベースの基礎

 (tontinton.com)
5 ポイント 投稿者 GN⁺ 2023-12-16 | 1件のコメント | WhatsAppで共有
  • 単純な Bash のキー・バリューストアから出発し、実際のデータベースがなぜ 耐久性、原子性、分離性、性能を別個の設計課題として扱わなければならないのかを段階的に示す
  • fsync/fdatasync、flock、WAL は障害や同時実行の状況でデータを守るための基本的な道具だが、保証水準を高めるほど 性能コスト は大きくなる
  • ストレージエンジンはディスク I/O とシークコストを減らすために B-tree や LSM tree のような構造を使い、それぞれ vacuum・compaction のようなメンテナンスを伴う
  • 分散データベースは可用性と水平スケーリングを得る代わりに、CAP 定理、ネットワーク分断、一貫性の調整、競合解決といった 分散システムの複雑性 を受け入れる
  • データベースを選ぶ、または実装する際には、ACID 保証、分離レベル、保存構造、レプリケーション方式、一貫性要件を ワークロードに合わせて調整 する必要がある

bashdbで明らかになるデータベースの基本問題

  • bashdb は 2 つの Bash 関数で作られた単純なキー・バリューストアである
    • db_set は key,value 形式でファイルに append する
    • db_get は grep、sed、tail を組み合わせて最後の値を読む
  • 学習用としては単純だが、この実装だけでもプロダクションデータベースが解決すべき問題が見えてくる
    • Durability: db_set 成功後にマシンがクラッシュすると、ディスクにフラッシュされていないデータが失われる可能性がある
    • Atomicity: 書き込み途中でクラッシュすると、データが一部だけ記録されて破損する可能性がある
    • Isolation: 同時に読み書きが同じ項目へアクセスすると、読む側が一部のデータしか見えないことがある
    • Performance: db_get はファイル全体を行単位で検索するため O(n) である

ACID と bashdb の改善の試み

  • ACID は、多くのデータベースが保証しようとする性質をまとめた略語である
    • Atomicity: 書き込み中に障害が起きた場合、トランザクション全体を取り消すかロールバックし、部分的な書き込み状態を残さない
    • Consistency: 不正なトランザクションがデータベースを破壊してはならない
    • Isolation: 同じデータへの同時アクセスで race condition が発生してはならない
    • Durability: 成功した書き込みは、電源障害のような状況の後でも保持されなければならない
  • すべてのデータベーストランザクションが必ず ACID を保証しなければならないわけではなく、一部のユースケースでは性能のために保証を弱めることもある

  • 耐久性と fsync

    • write システムコールはバッファをファイルへ書き込むが、それが直ちに不揮発性ストレージへ記録されることを意味するわけではない
    • カーネルはバッファを page cache に dirty page として保存し、後でディスクへフラッシュすることがある
    • ディスク装置や RAID システムも別個の write cache を持つ場合がある
    • fsync と fdatasync は dirty page を永続ストレージへフラッシュするためのシステムコールである
    • fdatasync は write で渡した raw buffer をフラッシュする
    • fsync はデータだけでなく、mtime のようなファイルメタデータもフラッシュする
    • sync -d database を db_set の後に付ければ、fdatasync に近い動作で耐久性を高められるが、通常 sync は write 自体より遅いため性能は悪化する
    • fsync() の成功は「最後の fsync 以降のすべての write がディスクに到達した」ことを意味し、「最後に成功した fsync 以降の write」だけを意味するわけではない
    • PostgreSQL は 2018 年にこの問題を経験し、fsync 失敗時には再試行ではなく panic する方式へ動作を変更した
    • この出来事は fsyncgate として知られており、関連資料として fsync failures 論文 がリンクされている
    • MongoDB はデフォルトで書き込みが 100ms ごとに sync されるため、100% 耐久的ではない

  • 分離性と flock

    • bashdb で最も単純なマルチプロセス分離方法は、保存ファイルを読んだり書いたりする前に lock をかけることである
    • Linux の flock はファイルをロックし、-s フラグを使うと共有 lock となり、複数の reader が同時に読める
    • 改良版 bashdb は、書き込みには exclusive lock、読み込みには shared lock を使う
    • 欠点は、書き込みのたびに データベース全体 をロックする点である
    • Bash だけで原子性を簡単に保証するのは難しく、mv -T や rename を使う可能性はあるが完成していない
    • bashdb は依然として O(n) の検索問題を解決できていない

ストレージエンジンの役割とボトルネック

  • ストレージエンジンは永続ストレージへのデータの読み書きを抽象化して提供し、主な目標は高スループットと低レイテンシである
  • 最大の制約はディスク自体の速度差から生じる
    • 例示されたレイテンシ表では、L1 cache 参照は約 0.5ns、SSD での 4KB random read は 150,000ns、disk seek は 10,000,000ns とされる
    • L1 cache 参照を心拍約 0.5 秒とみなすと、SSD での 1MB 順次読み取りは約 12 日、ディスクでの 1MB 順次読み取りは約 8 か月に相当する
  • そのためストレージエンジン設計は、ディスク I/O と disk seek をできるだけ減らす方向へ発展してきた
  • 一般的なストレージエンジンの設計要素は次のとおりである
    • ディスク上に項目を保存する基本 データ構造
    • ACID トランザクション
    • ディスク読み取りを減らすための cache
    • SQL、document、graph のような API 層
  • ストレージエンジンのデータ構造は、大きく変更可能な構造と不変構造に分けられる
    • 変更可能構造は、ファイルに書いたデータを後で上書きできる
    • 不変構造は、ファイルに書いたデータを再度読むだけである

変更可能な B-tree

  • データが増えても良好な性能を維持するには、bashdb のような線形検索ではなく、最大でも対数時間で項目を見つけられなければならない
  • BST は O(log n) の検索が可能だが、ノードがディスク上で互いに離れていると、探索中の disk seek が多くなる可能性がある
  • B-tree は、1 つのノードが 2 つより多くの子を持てる BST の一般化であり、spatial locality を活用する
    • ディスクでは通常 4KB または 8KB の page を読み込んだ後、その中の複数ノードをメモリと CPU cache 上で順次比較する
    • メモリと CPU cache へのアクセスはディスクより何桁も速いため、ディスクから読み込んだバイトをできるだけ多く活用することが重要である
  • 順次メモリアクセスは、SIMD、instruction pipelining、prefetching のおかげで非常に強力になりうる
  • B+ tree は leaf node にのみ値を保存し、それ以外のノードには key だけを保存するため、1 つのディスク page でより多くの key を比較できる

  • 空間回収と vacuum

    • B-tree は空間最適化のため、データ断片化で生じた空き領域を回収する必要がある
    • 大きな値へ更新すると次のノードデータを上書きしかねないため、項目を別の場所へ移し、元の page に穴が生じる
    • 小さな値へ更新すると末尾に穴が残る
    • 削除は、削除された値があった場所に穴を作る
    • このような空間回収と page 再書き込みの過程は、vacuum、compaction、page defragmentation、maintenance などと呼ばれることがある
    • 通常はユーザー要求のレイテンシスパイクを避けるため、バックグラウンドで実行される
    • PostgreSQL では auto vacuum daemon を設定できる
    • B-tree は PostgreSQL のデフォルト index のように index の基盤データ構造としてよく使われ、DynamoDB は冗談交じりに「distributed B-tree」と呼ばれた例がある

不変LSM tree

  • LSM treeは、disk seekが高コストであることを前提にした append-only データ構造である
  • データをファイル末尾にのみ追加すれば、ディスクヘッドが次の書き込み位置まで大きく移動する必要が少なくなり、書き込みの多いワークロードに有利である
  • Log Structured Merge tree、略して LSM tree は、RocksDB、Cassandra、ScyllaDB のような現代的なデータベースストレージエンジンで使われている
  • 基本動作は以下のとおりである
    • 書き込みをメモリ上のソート可能なデータ構造にバッファする
    • 例として AVL tree、Red Black tree、Skip List がある
    • 一定容量に達すると、ソート済みファイルである Sorted String Table、すなわち SSTable にフラッシュする
  • SSTable はソート済みデータを保存するため、binary search と sparse index によってディスク I/O を減らせる
  • 耐久性のため、メモリに書いた操作は Write-Ahead Log、すなわち WAL に記録される
    • プログラム起動時に WAL を読み、終了前またはクラッシュ前の状態に復元する
  • 削除も通常の書き込みと同様に append され、値の代わりに tombstone を保存する
    • tombstone は compaction の過程で削除される

  • LSM tree の読み取りと compaction

    • LSM tree の読み取りでは、まずメモリ上のデータ構造を検索し、なければディスク上の SSTable を新しいファイルから古いファイルの順に探索する
    • 書き込みが増えるほど、確認すべき SSTable の数も増える
    • 各ファイルがソートされていても、小さなファイルを多数なめるのは、1つの大きなファイルを見るより遅い場合がある
    • 比較式は log(num_files * table_size) < num_files * log(table_size) である
    • compaction は、複数の小さな SSTable を1つの大きな SSTable にまとめ、tombstone を削除するバックグラウンド処理である
    • RocksDB は Leveled Compaction を実装している
    • 新たにフラッシュされた SSTable は level 0 に配置される
    • 設定された数のファイルがある level にたまると、compaction 後に新しいファイルを次の level に昇格させる
    • tombstone の削除は慎重に行う必要がある
    • 削除された項目が、より古いファイルとの compaction によって復活してしまう data resurrection 問題が起こりうる
    • RocksDB は最後の level に昇格される compaction の前まで tombstone を保持する
    • Rust による実例として dbeel の LSM tree コード がある

  • Bloom filter

    • Bloom filter は、ある項目が集合に存在しないことを効率よく確認するための確率的集合データ構造である
    • 問い合わせ結果は2つである
      • false: 項目が集合に確実に存在しない
      • true: 項目が集合に存在する可能性がある
    • Bloom filter は、複数の hash function の結果を bitmap の bit 位置に対応付けて 1 に設定する
    • 空間計算量は、一般的な set の O(n) とは異なり O(log n) とされる
    • bitmap のメモリをさらに割り当て、hash function の数を増やすことで、「存在しないと確信できる確率」を調整でき、計算機 もある
    • LSM tree は各 SSTable ごとに Bloom filter を保存し、特定の key が存在しないと確認できた SSTable の検索をスキップできる

WAL とトランザクション保証

  • WAL は、突発的なクラッシュを乗り切るために、すべてのトランザクション操作を特別なファイルに記録する方式である
  • データベースプロセスが起動すると WAL ファイルを読み、データ状態を再構成する
    • commit log がないトランザクションはスキップされるため、原子性が得られる
  • ユーザーに応答する前に、書き込み要求データが WAL に記録されてフラッシュされていれば、起動時に必ず読み取れるため耐久性が得られる
  • WAL は、トランザクションイベントに対する event sourcing の一形態と見なせる

分離レベルと並行性制御

  • 分離を達成する方法は大きく3つに分かれる
    • 悲観的 lock: 現在書き込み中のデータへのアクセスを防ぐ
    • 楽観的 lock: データのコピーを変更した後、トランザクション中に元データが変わっていなかった場合にのみ commit し、そうでなければ retry する
    • MVCC: データを上書きせず新しい version を作り、各ユーザーが特定時点の snapshot を見るようにする
  • すべてのアプリケーションが完全な分離、すなわち serializable isolation を必要とするわけではない
  • ANSI/ISO SQL 92 は、トランザクション中に他のトランザクションが同じデータを変更したときに起こりうる結果を3つに分類している
    • Dirty read: まだ commit されていない他のトランザクションの更新を読む
    • Non-repeatable read: 同じ row を2回読む間に他のトランザクションが commit し、値が変わる
    • Phantom read: 同じ条件の row 集合を2回読む間に row が追加または削除される
  • ANSI/SQL 92 の分離レベルは、高い順に以下のとおりである
    • Serializable: commit 済みデータのみを読み、範囲ベースの複数 row 書き込みまで含めて phantom read を防ぐ
    • Repeatable reads: phantom read は許容される
    • Read committed: non-repeatable read は許容される
    • Read uncommitted: dirty read が許容される
  • 高い分離レベルは通常、性能の犠牲を伴う
  • ANSI/SQL 92 の分離レベルは不完全だという批判を受けている
    • 多くの MVCC 実装は serializable isolation ではなく snapshot isolation を提供する
    • 高速な serializable MVCC アルゴリズムとして HyPer が推奨される

分散システムが必要な理由と CAP

  • 分散システムは多くの複雑さを追加するため、非分散の解法で十分なときは避けるべきである
  • データを複数マシンに分散する一般的な理由は2つある
    • 可用性(Availability): データベースマシンがクラッシュしたりユーザーとの接続が切れたりしても、別のマシンにリクエストを送れる
    • 水平スケーリング(Horizontal Scaling): より大きな単一マシンへ拡張する vertical scaling の代わりに、ネットワークで接続された複数マシンを1つのように動作させる
  • 分散システムは、運用の複雑さとネットワークパーティションの問題を持ち込む
  • CAP 定理は、システムが次の3つのうち2つしか保証できないと述べる
    • Consistency: 読み取りが最新の書き込みを受け取る
    • Availability: 障害に関係なくすべてのリクエストが成功する
    • Partition Tolerance: ノード間でメッセージ損失や遅延があってもシステムが動作し続ける
  • 単一マシンのデータベースにはネットワークパーティションがなく一貫性もあるが、マシン障害時には新しいリクエストが失敗するため availability に違反する
  • 2台のマシンが独立した CPU、メモリ、ディスクを持ち、ケーブルで接続されている場合、障害時には選択が分かれる
    • リクエストを取り消せば availability を犠牲にして consistency を守る
    • 動作中のマシンだけでリクエスト処理を続ければ consistency を犠牲にして availability を守る
  • consistency を犠牲にして後で合わせるシステムは eventually consistent と呼ばれる
  • ネットワークパーティションは、クラスター内に散在するデータを集める必要があるため、効率的な JOIN も難しくし、NoSQL 陣営はこれを緩和するために denormalization を推奨している

レプリケーションとAmazon Dynamoの事例

  • Amazonの元の Dynamo paper は、amazon.comのショッピングカートでは consistency より availability のほうが重要だとみなした事例として紹介される
    • ユーザーがカート内で同じ商品を2つ見た場合は、片方を削除すればよい
    • 購入そのものができない状況よりはましだという判断である
  • availability を得るには、複数ノードがデータを分散保持するだけでは不十分で、各項目のコピーが少なくとも1つ以上必要である
  • 項目のコピーを保存するノードは replica、コピーの過程は replication と呼ばれる
  • replica 数を増やすと availability は高まるが、コピー保存のためのリソースがより必要になる
  • データのコピーは丸ごと保存するのではなく、erasure coding で分割して複数ノードに散らすこともでき、関連するレイテンシ特性は erasure coding の記事 で説明されている

Consistent Hashing とデータ配置

  • 複数ノードがある場合、保存リクエストをどのノードが処理するかを決めるロードバランシングまたはデータパーティショニング方式が必要になる
  • 単純な方法は、primary key を hash した後でノード数で modulo を取ることである
    • ノードが追加または削除されると len(nodes) が変わり、同じ key が別のノードを指すことになる
    • この場合、ほぼすべての項目をマイグレーションしなければならず、コストが大きい
  • Consistent Hashing はノードを配列ではなく ring 上に配置し、ノード追加・削除時に移動しなければならない項目数を減らす
    • Dynamo や Cassandra のようなデータベースで使われる
  • Consistent hashing ではノード名の hash を ring に配置し、リクエスト key の hash の後に最初に出会うノードがオーナーになる
  • replica の選択は、ring を反時計回りにたどって次のノードにコピーを保存する方式で行える
    • オーナーノードが停止すると、replica ノードがリクエストを処理して availability を維持する
    • この方式は Leaderless Replication と呼ばれ、Cassandra のような Dynamo スタイルのデータベースで使われる
  • ノード追加時に移動が必要な key 数は平均して num_keys / num_nodes である
  • virtual node は、1つの物理ノードを ring 上に複数回配置して、一部ノードがより多くの項目を所有してしまう可能性を下げる
    • 例としては、"half-0"、"half-1" のようにノード名に index を suffix として付ける方式がある
  • leader node と replica node を選ぶ別の方法として leader election もあるが、ここでは扱わない

Leaderless Replication と整合性の調整

  • leaderless 構成は高い availability を得る代わりに consistency を犠牲にする
  • オーナーノードが write リクエスト時に down 状態であれば replica に書き込まれ、オーナーノードが再び復帰した後の read リクエストで古いデータが読まれることがある
  • 特定のリクエストで consistency が必要な場合は、read リクエストを複数の replica とオーナーノードに並列送信し、クライアントが最も新しいデータを選ぶ
  • write リクエストは通常すべての replica に並列送信しつつ、一部ノードからの acknowledgement だけを待つ
  • リクエストレベルで consistency を調整するには R + W > N/2 + 1 を検証する
    • N: データのコピーを持つノード数
    • W: write 成功のために acknowledgement する必要があるノード数
    • R: read 成功のために応答する必要があるノード数
  • W または R が N/2 + 1 となる多数ノードへの要求は quorum と呼ばれる

  • 競合の解決

    • 最も新しい write を選ぶ過程は Conflict Resolution である
    • 単純に timestamp を比較する方法は、分散システムでは信頼しにくい
    • 各マシンは独自の hardware clock を持ち、clock は完全に正確ではないため drift が発生する
    • NTP はより正確な時刻源から時刻を受け取るが、リクエスト自体がネットワークを通るため、応答までにかかった時間を正確に知ることはできない
    • Cassandra は timestamp を使用しており、関連ドキュメントは Cassandra data versioning である
    • Google Spanner は特殊な高精度時刻ハードウェアと、timestamp の不確実性範囲を公開する API により、clock ベースの consistency 保証を達成しており、関連論文は Spanner paper である
    • Dynamo のようなシステムは Version Vectors によって一部の競合を減らす
    • 各項目 version には (node, counter) の組を付けて、version 間の因果関係を見つける
    • 確実により新しい version を見つけて、一部の古い値を取り除くことができる
    • 詳しい資料として Dotted Version Vectors がある
    • Riak KV のように、競合した値をすべてアプリケーションに返し、アプリケーションがデータに関する知識に基づいて解決することもできる
    • eventually consistent なシステムで競合を減らすさまざまな技法は、通常 Anti Entropy という用語の下にまとめられる

Anti Entropy の技法

  • Read Repair

    • クライアントが複数ノードの read 結果から最新値を選んだ後、その値をまだ保存していないノードへ再送して repair する

  • Hinted Handoff

    • write リクエストが対象ノードに到達できなければ、別のノードに hint として保存する
    • 対象ノードが再び available になったら、保存された hint を渡す
    • quorum write では、この方式は Sloppy Quorum とも呼ばれ、quorum リクエストの availability をさらに高める

  • Merkle Trees

    • read repair は参照されたデータだけを修正するため、多くのデータが長く不整合のまま残ることがある
    • ノード同士で同期しながら全体の差分を探すのは、データ量が多いと O(n) で高コストである
    • Merkle tree は、データ範囲の hash を leaf に保存し、親が子の hash を結合した hash を保存する階層構造である
    • ルート hash が同じなら2つのノードのデータは同一であり、異なる場合は下位 hash を再帰的に比較して不一致データを見つけるため、同期を O(log n) で高速化できる

  • Gossip Dissemination

    • イベントをクラスター全体にシンプルかつ信頼性高く伝播する方式である
    • ノードは設定された数のランダムノード、つまり fanout にメッセージを送り、受信したノードは再びランダムな N 個のノードに送る
    • 同じ gossip メッセージを設定回数だけ見たら、それ以上は broadcast しない
    • データ収束を体感できる simulator がある
    • gossip メッセージは通常 UDP で送信される

さらに深く扱える領域

  • データベースには、ここで扱った内容以外にも多くのトピックがある
    • Linux の O_DIRECT の使用と独自 page cache の実装
    • 分散システムの failure detection
    • Raft のような consensus アルゴリズム
    • distributed transaction
    • leader election
  • データベースを選定または実装する際には、ストレージエンジン、ACID、分離レベル、分散レプリケーション、競合解決方式が実際の要件にどう適合するかも合わせて見る必要がある

関連記事

1件のコメント

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

  • compactメソッドにバグがある: トゥームストーンは最後、つまり最大レベルを圧縮するときだけスキップすべきで、すべてのレベル間で削除してはいけない
    そうしないと、上位レベルのトゥームストーンが圧縮過程で消えてしまい、下位レベルにあったエントリが再び表に出てくる
    LSMベースのデータベースでは、削除/トゥームストーンレコードが長く残ることが特徴の一つであり、RocksDBのような一部のデータベースはこれを避けるための最適化を入れている

    • その通り。記事では簡潔さのために意図的に省いており、dbeelでは処理している
    • RocksDBがどんな最適化をしているのか気になる
      範囲削除まわりの機能は知っているが、単一キー削除についてはあまり読んだ記憶がない

  • 多くの人はSQLを学びながらデータベースを習得するが、こうした授業を受けてBツリーを理解する形で学ぶことを勧めたい
    RDBMSの長所と短所の大半は、Bツリーと、それがキーの挿入・検索・ソートに与える影響を知れば理解できる
    多くの人はインデックスを追加してデータベースを速くしようとするが、結局はツリーの上にさらに別のツリーを載せているだけで、根本問題を覆い隠しているにすぎない
    Bツリーにうまく合う問題もあるが、多くの問題はそうではない
    SQLはリモートのBツリーシステムに対するクエリインターフェースにすぎない

    • それは還元しすぎだ
      Bツリーだけがインデックス戦略ではないし、インデックスは読み取り性能を高める代わりに書き込み性能を犠牲にする仕組みだという点もよく知られている
      一般にデータベースは書き込みよりも読み取りをはるかに多く処理するからだ
      「ツリーの上にさらに別のツリーを載せる」ことで覆い隠される問題とは正確に何で、インデックスに手を入れずにどう解決するつもりなのか気になる
      そこそこのサイズのテーブルでは、インデックスは事実上必須だ
    • これには同意する
      Bツリーとハッシュインデックス、入出力レイヤー、プロセスモデルのようなものを学ぶべきだ
      最近では、列指向データベースの一般的な戦略も学ぶ価値がある: 遅延タプル実体化、遅延実行、線形スキャンと二分探索、命令パイプライニングなどだ
      こうしたものに慣れると、現場ではDBMSではなく単純なフラットファイルやRocksDBのような組み込みデータベースで十分な場合もあると分かる
    • Bツリーかもしれないし、LSMツリー、トライ、あるいは状況に合った別のインデックス構造かもしれない
      もちろんカバリングインデックスもあり得る
    • 「ツリーの上にさらに別のツリーを載せているため問題を覆い隠す」という部分を、具体例で説明してもらえるとよい

  • 「分散でない解決策で十分なら分散システムは避けよ」という助言には、逆のことを言いたい
    取るに足りないものではない運用システムはすべて分散システムだ
    少なくともデータベースがレプリカセットなら、すでに分散システムなので、分散システムを学ばないのはリスクを取ることになる
    https://jepsen.io/とhttps://raft.github.io/は見る価値がある

    • システムの一部ではネットワーク呼び出しや分散的な側面を避けられないことがある
      だからといって、それをあらゆる場所に導入してよいという意味ではなく、そうすると必要以上に複雑さが大きく増す
    • まず「取るに足りないものではない運用システム」を定義する必要がある
      その言い方だけでは、不要な複雑さを避けよという助言への反論にはならない。要点は技術的に分散かどうかではなく、本当に必要かどうかだ
      分散システムを学ぶことと使うことは別だ
      学んだ後でも、適した場所にだけ適用する節度を持てるかが重要だ
      最近は、単純でうまく動いているシステムをより強い分散モデルへ移すために大きな労力をかけるケースが多く、まるでコストがほとんどないかのように扱われている
      しかし、解決しようとしている問題と規模を見ると、単一のPostgresインスタンスとモノリスで十分だったことが明白な場合がある
      原文の助言はそういう意味に見える
    • HNのバブルの中では正しいかもしれないが、平均的なビジネスの観点ではまったくそうではない
      少なくとも、必ずそうでなければならないわけではない
    • 分散/冗長システムはバックアップではない
      それでも単純な解決策を選べという助言をしたい
      システムは「取るに足りない単純なストレージ」ですら、永続状態を適切に保存・バックアップ・復元できないことが多い
      災害復旧の状況で分散ストレージの状態を復元しようとするのはさらに難しい
      動作するバックアップ解決策を先に用意してから、分散型の解決策を採用してもよい
    • レプリカのフェイルオーバーを分散システムと呼ぶのは難しい
      読み取り専用レプリカを持つマスター構成も、一般に人々が言う「分散」とは違う。書き込みが分散されていないからだ
      実務で分散とはたいていデータがシャーディングされることを意味し、本当に必要でないなら必ず避けたい部分だ

  • データベースを作るときに関わるさまざまな概念をうまく概観していて、興味深く読んだ
    単一マシンで性能を絞り出すためのSIMDから合意アルゴリズムまで扱っている
    データベース、信頼性、分散システムの話をするついでに、こうした状況やデータベース内部実装に適用できる形式手法もあわせて読んでみる価値がある
    S3チームがTLA+でモデル化した興味深い論文がある
    [0] Use of Formal Methods at Amazon Web Services
    https://lamport.azurewebsites.net/tla/formal-methods-amazon....
    [1] How Amazon Web Services uses formal methods
    https://www.amazon.science/publications/how-amazon-web-servi...

  • 一貫性にはデータベースの一貫性とアプリケーションの一貫性がある
    たとえば1つのテーブル単位では原子性、分離性、永続性を達成できても、複数テーブルにまたがる書き込みでは失敗することがある
    複数のテーブルを同時に更新するトランザクションを扱い始めると、一貫性が重要になる
    すべてのテーブルが同時に更新されるか、何も更新されないかでなければならない

    • よい例なので記事に反映する

  • 「MongoDBのようなドキュメントAPI、Cassandraのようなリーダーレスレプリケーション、ScyllaDBのようなコアごとのスレッドアーキテクチャを備えた」という設計がとても格好いい
    しかも全部Rustで書かれている

  • 「本に好奇心を刺激されて、小さなデータベースを自分で作ってみた」という段階は、多くの開発者が一度は通るものだと思う
    あえて止めようとは思わない。実際にやってみると、何がうまく動かないのかを本当にたくさん学べる
    時間を取れるなら、非常に価値のある教訓になる
    自分でデータベースを作ってみた経験は、既存の解法への敬意を最も大きく育ててくれた
    バイト列をディスクに高速に書き込み、読み出すことが難しい部分なのではない
    本当に難しいのは、想像もしなかったユースケースをサポートしながら、何年にもわたって安定して動作させることだ

    • 現代のDBMSの複雑さのうち、どれほど多くが特定のビジネスドメインのユースケースによって生じた制約に由来するのか、よく気になる
      ドメイン外のユースケースは禁止して無視してよい、という前提でドメイン特化DBMSを設計したら、どんな効率が得られるだろうか？
      たとえば今は、本質的に追記専用であるデータセットにも汎用データベースを使っている
      既存行の更新や削除という概念がまったくなく、挿入とテーブル／データセット全体の削除程度しかないデータベースならどうだろう？
      そのようなデータベースではMVCCトランザクションを実装しなくて済むのだろうか？ 各テーブル自体が先行書き込みログになるので、別個の先行書き込みログを避けられるのだろうか？ より効率的に保存できるのだろうか？ インデックス作成をテーブル全体単位の原子性ではなくチャンク単位の原子性にして、ロックを減らせるのだろうか？

  • Bash版の原子性は、ファイルを一時ファイルにコピーして修正した後に sync; mv; sync を使えば「簡単に」達成できるのでは？

    • コピー中に逆方向の grep フィルタで重複を避けることもできる
      コピーするついでにソートも保証できるだろうが、「bash」と基本ユーティリティだけでそうするのは、あまり筋がよくないと思う
      そういう用途にはDJBのCDB、つまりcdbget、cdbmakeなどがある:
      https://cr.yp.to/cdb.html
    • その通り、後で追加する

  • すばらしい記事
    Database Internals という本は良さそうだが、内部実装を深く掘り下げる似たような本はほかにあるだろうか？

    • 本ではないが、CMUの@apavloグループが公開しているデータベース講義をおすすめする
      https://www.youtube.com/c/cmudatabasegroup
      入門と上級の授業がどちらもオンラインにあり、業界製品に関する発表や講義もある
      非常に有用
      より高いレベルの理論計算機科学の観点で、物理実装にはあまり焦点を当てていない資料としては、「Alice」本、つまり “Foundations of Databases” がすばらしい
      非常に密度が高く数学的だが、関係代数とDatalog、そしてDatalogを関係代数へ変換する内容を扱っている
      紙の本は今では入手が難しく、中古で買った本は製本が壊れてページが外れた状態で届いたが、全体がオンラインにある: http://webdam.inria.fr/Alice/
    • Postgresに焦点を当てた有名な資料もある: https://www.interdb.jp/pg/
    • 同じような概説としては、この論文がよい:
      https://dsf.berkeley.edu/papers/fntdb07-architecture.pdf
    • Raghu RamakrishnanのDatabase Management Systemsという本も非常に役に立った
      ただしDatabase Internalsのほうがより現代的

  • 記事が「データベース」を神秘化せず、Bashのワンライナーで些細な実装を見せるところから始めているのがよい
    すばらしい導入部