# バージョン履歴 ## 定義 バージョン履歴(version history)とは、named variable ごとに単一のセル(上書きする通常の記憶=セル記憶)を割り当てる代わりに、その変数の値の列(版の履歴)を非揮発性記憶に保持する記憶モデルである。この方式は**ジャーナル記憶(journal storage)**と呼ばれる層としてセル記憶の上に実装され、セル記憶に対する上書き(store)を、新しい暫定的な版の追記(append)へ置き換える。目的は**原子性の黄金律(golden rule of atomicity)**——唯一のコピーを決して書き換えるな——を機械的に満たすことにある。各版には作成者となる原子アクションの識別子(結果レコードへの参照)が付与され、`READ_CURRENT_VALUE` は結果レコードが COMMITTED になっている最新の版だけを返すことで、未確定・アボート済みの版を後続の読み取りから隠す。(Source: [[@2009__MITOCW__Principles of Computer System Design - Chapter 9 Atomicity - All-or-Nothing and Before-or-After]] §9.2.3) バージョン履歴は全か無かの原子性を体系的に与えるだけでなく、前か後かの原子性の基盤にもなる。単純直列化・マークポイント規律・read-captureの3方式はいずれも、結果レコードに連番の識別子を割り当て、その識別子順を「直列化順序」とみなすことで正しさを論証する。マークポイント規律は各トランザクションに、自分が変更する変数へ先に暫定版を作らせてから読み書きを許すことで、単純直列化より高い並行性を得る。read-captureはこの事前マーキングを不要にする楽観的な変種で、各読み取りが対象変数に「ハイウォーターマーク」を刻み、後から遅れて到着した書き込みがそのマークより古い直列位置しか持たなければアボートさせる。(Source: [[@2009__MITOCW__Principles of Computer System Design - Chapter 9 Atomicity - All-or-Nothing and Before-or-After]] §9.4.1–§9.4.3) ## バージョン履歴の実際の用例 書籍は、フルスケールのバージョン履歴実装は性能上の理由(間接参照、複数回のディスク書き込み)から低性能アプリケーション(改訂管理システムの check-out/check-in、対話型アプリケーションの「深い undo」、ファイルシステムの自動バージョニング)に限られ、高性能データベースはより特殊化されたログ方式を使うと明言する。一方で、バージョン履歴の考え方自体は形を変えて広く使われている。 - **レジスタリネーミング(register renaming)**: マルチイシュープロセッサのリオーダバッファは `NEW_VERSION`/`WRITE_VALUE` の直接的なハードウェア実装であり、アーキテクチャレジスタに対する複数の物理レジスタ版を同時に保持することで、レジスタ不足だけが原因で発生する命令間の見かけの依存を解消する。 - **Oracle のスナップショット分離**: トランザクション開始時にコミット済み値の概念的なスナップショットを取り、同一変数への並行更新は先にコミットした方が勝ちとするバージョン履歴の限定変種。書籍は「serializable」というラベルは誤解を招きうると注記する。 - **トランザクショナルメモリ**: STORE 命令を隠しコピーへ向け、コミット時に他のコミット済みトランザクションとの干渉を検査する、read-captureよりさらに楽観的な変種。 (Source: [[@2009__MITOCW__Principles of Computer System Design - Chapter 9 Atomicity - All-or-Nothing and Before-or-After]] §9.2.4, §9.4.4) ## 横断的知見 - **本書のバージョン履歴は、[[スナップショット分離とMVCC]]が扱う MVCC の一般化された祖先にあたる**: MVCC(Multi-Version Concurrency Control)は「読み取りが書き込みをブロックしない」という性能特性を得るために複数版を保持する実装技法として説明されることが多いが、本書のバージョン履歴はむしろ「正しさをどう論証するか」という視点から出発し、結果レコードの連番を直列化順序とみなす議論(単純直列化→マークポイント→read-capture)を積み上げる。Oracle のスナップショット分離を本書が「serializable というラベルは誤解を招く」と評する点(§9.4.4)は、[[直列化可能性]]ページが DDIA から引く「スナップショット分離は直列化可能性より弱い」という整理と独立に一致しており、教科書横断で同じ結論に達している。(Source: [[@2009__MITOCW__Principles of Computer System Design - Chapter 9 Atomicity - All-or-Nothing and Before-or-After]] §9.4.4, [[直列化可能性]]) - **read-captureの「ハイウォーターマーク」は、[[ロストアップデートと書き込みスキュー]]が扱う条件付き書き込み(CAS)や自動検出と同じ役割を、バージョン履歴という異なる基盤の上で果たす**: DDIA 側の「更新のロストの自動検出」は、書き込み前に読み取り時点の値と現在値を比較する CAS 的発想だが、本書の read-captureはこれを「読み取りがマークを残し、遅れて来た書き込みがそのマークを見て自らアボートする」という逆向きの責任分担で実現する。検出の主体が書き込み側(CAS)か読み取り側(ハイウォーターマーク)かという違いは、同じ「陳腐化した前提に基づく書き込みを防ぐ」問題への2つの異なる設計解として対比できる。(Source: [[@2009__MITOCW__Principles of Computer System Design - Chapter 9 Atomicity - All-or-Nothing and Before-or-After]] §9.4.3, [[ロストアップデートと書き込みスキュー]]) ## 未解決の問い - 本書はバージョン履歴を「低性能アプリケーション向け」と位置づけるが、[[スナップショット分離とMVCC]]が扱う現代の MVCC 実装(PostgreSQL 等)は高性能 OLTP で広く使われている。この評価の違いは、2009年時点の書籍が想定した「フルスケールで版を保持し続ける」実装と、現代のガベージコレクション付き MVCC(不要になった旧版を積極的に破棄する)の実装差にどこまで帰着できるか。 - read-captureのハイウォーターマーク方式と、[[直列化可能性]]ページが扱う直列化可能スナップショット分離(SSI)の「陳腐化した MVCC 読み取りの検出」は、同じ楽観的検出の系統に見える。両者の検出タイミング(read-captureはNEW_VERSION呼び出し時、SSIはコミット時)の違いは性能特性にどう影響するか、定量比較は存在するか。 - 本書はレジスタリネーミングを version history の直接実装と位置づけるが、この対応関係(BEGIN_TRANSACTION≒命令発行、COMMIT≒命令の退役)を、現代のアウトオブオーダー実行の投機的実行・分岐予測ミス時のロールバックにまで拡張して論じた文献は本 wiki にまだない。 ## 関連 - ソース: [[@2009__MITOCW__Principles of Computer System Design - Chapter 9 Atomicity - All-or-Nothing and Before-or-After]] - 概念: [[直列化可能性]] / [[分散トランザクション]] / [[クラッシュリカバリ]] / [[Write-Ahead Logging (WAL)]] / [[スナップショット分離とMVCC]] / [[ロストアップデートと書き込みスキュー]] - 書籍: [[Principles of Computer System Design]] ## 出典 - Jerome H. Saltzer and M. Frans Kaashoek, *Principles of Computer System Design: An Introduction*, Version 5.0, 2009, Chapter 9 §9.2.3–9.2.4, §9.4.1–9.4.4. MIT OpenCourseWare, CC BY-NC-SA 3.0 US.