このエントリはPostgreSQL Advent Calender 2021の22日目の記事です。

shallow1729さんのMVCCとInnoDBでの実装についてという記事を読んで、これのPostgreSQL版を書きたいなと思い書いてみました。

同時実行制御とトランザクションID

PostgreSQLは複数のクライアントがトランザクションを同時に実行することが可能で、各トランザクションは他のトランザクションの影響を受けずに処理します。これはトランザクションのACID特性の隔離性（Isolation）の特性です。

以下に簡単な例を挙げます。

-- トランザクションA 開始
BEGIN;
SELECT * FROM test;
 val
-----
   1
(1 row)

UPDATE test SET val = val + 1;
                                     -- トランザクションB 開始
                                     BEGIN;
                                     SELECT * FROM test;
                                      val
                                     -----
                                        1
                                     (1 row)
-- トランザクションA コミット
COMMIT;

                                     SELECT * FROM test;
                                      val
                                     -----
                                        2
                                     (1 row)

                                     COMMIT;

トランザクションBは、トランザクションAがCOMMITする前にtestテーブルを見ると「1」が見えますが、トランザクションAがCOMMITした後にもう一度見ると更新した後の値「2」を見ます。

これは、PostgreSQLのデフォルトのトランザクション分離レベルであるREAD COMMITTEDでの動作で、トランザクションは、他のトランザクションがコミットした変更を見ることになります。

PostgreSQLでは、このような同時実行制御をトランザクションIDを利用して実装しています。

トランザクションID（以下、XID）は、各トランザクションに付与される単調増加する非負整数値です。PostgreSQLのテーブルの各タプルのヘッダには、xmin、xmaxと呼ばれる2つのXIDが格納されています。xminにはそのタプルを追加した（INSERTまたはUPDATEでの更新後のタプル）トランザクションのXIDが格納され、xmaxにはそのタプルを削除した（DELETEまたはUPDATEでの更新前のタプル）トランザクションのXIDが格納されます。UPDATEやDELETEでもタプルは即座に削除されず、xmaxだけ更新される所が特徴的ですね。タプルのxmin、xmaxは明示的に指定すればSELECTでも見ることが可能です。

例えば、XID=100のトランザクションがタプルをINSERTし、そのタプルをXID=200のトランザクションがUPDATEした場合、xmax, xminは以下のようになります。

SELECT xmin, xmax, * FROM test;
  xmin  | xmax | val
--------+------+-----
   100  |  200 |   1
   200  |      |   2
(1 row)

このように、PostgreSQLではUPDATE時にタプルを書き換えるのではなく、古いタプルに自分のxmaxの値を入れて、自分のXIDのをxminに入れた新しいタプルを挿入します。そして、データを読む際はxminやxmaxの値を見ながら適切なデータのみを読みます。

複数のトランザクションが同時に同じデータを読み書きする可能性があるので、データを読む時、書くときにはロックが必要です。しかし、このように、1つのデータに対して複数のバージョンを持ち、読む側が適切なバージョンを選択することで、読み込みロックと書き込みロックが競合しないという特徴があります。このような手法をMultiversion Concurrency Control（MVCC）と呼びます。

MVCCはデータベースによって実装方法が異なります。例えば、MySQLのinnoDBでは、UNDOログと呼ばれる別の領域に古いタプルを退避させて、テーブル上のタプルを新しいタプルで書き換えます。変更されたタプルは新→旧の順番でリンクされているので、古いデータを見たい時はUNDOログ領域を見に行きます。

一方PostgreSQLでは、前述の通り、古いタプルも新しいタプルも同じテーブルの領域に格納します。テーブルの中には古いタプルも新しいタプルも混ざって格納されてあり、テーブルを参照する時はその中から適切なタプル（そのトランザクションが見えるべきタプル）だけを見るようにします。

コミットログ

ここまではトランザクションがコミットされるケースのみを扱ってきましたが、トランザクションはコミットもしくはロールバック（アボート）する可能性ありますので、各トランザクションの結果がどうなったかを記録している必要があります。PostgreSQLはコミットログ（トランザクションログではありません）と呼ばれるログを持っており、各トランザクション毎に2 bitsでトランザクションの状態（実行中、コミット済、ロールバック済など）を記録します。

PostgreSQLでは、INSERTしたけどその後ロールバックした、という状況でもINSERTしたタプルはテーブル内に残ります。そのようなタプルは誰からも見えてはいけません。トランザクションはコミットログを使うことで「このタプルをINSERTしたトランザクションはロールバックした（なので見てはいけない））」という事がわかります。

スナップショット

各トランザクションはテーブルのデータを見る際に、スナップショットと呼ばれるオブジェクトを取得し、スナップショットを使ってデータを見ます。PostgreSQL内部で使われているオブジェクトとしてのスナップショットは、「古いデータ新しいデータが混ざったテーブルから、ある時点（時刻と考えても良い）において見えるデータだけを見るためのフィルター」のようなもので、同じスナップショットを使っていれば常に同じ値を読むことができます。

スナップショットの中には以下のようなデータが入っています（タプルヘッダにあるxminやxmaxとは意味が異なるので注意）。

  • xmin: 現在実行中で最も小さいXID。これより小さいトランザクションはすでに完了しているので、コミットされたかロールバックされたかの2択（コミットログを見ればわかる）。
  • xmax: 直近で完了した最も大きいXID。これより大きいトランザクションはまだ開始していないか進行中。
  • xip: 現在実行中のXIDのリスト。リスト内のXIDは必ずxmin <= xip[i] < xmaxになる。

このスナップショットのデータを使い、タプルに格納されているxminとxmaxのデータ（＋コミットログ）を見ることで、そのタプルを見る・見ないの判断（可視性判断）します。

可視性判断のロジックはそこまで複雑ではありません。「タプルを追加したトランザクション」と「タプルを削除したトランザクション」の2つが、自分自身なのか過去なのか未来なのか、さらにそれらはコミットされたのかアボートされたのか、を確認しながら見ていきます。例えば、あるタプルを追加したトランザクションが「過去のトランザクション」かつそれがコミットされていれば、そのタプルを削除したトランザクションが「未来のトランザクション」だったり、（過去だったとしても）アボートされていれば、可視です。

ガベージコレクション（VACUUM）

これまで解説してきたとおり、PostgreSQLではUPDATEやDELETE時には、自分のXIDを古いタプルのxmaxに記載することで実装されています。xmaxにXIDを入れるだけでは、テーブルは大きくなり続けてしまうので、誰からも参照されなくなった（誰からも可視にならない）タプルは物理的に削除し、その領域を再利用できるようにするべきです。これはいわゆるガーベージコレクションと呼ばれる機能で、PostgreSQLでは、Vacuumがこの役割を担います。

Vacuumは誰からも可視にならないことが保証できる場合にのみ、そのタプルの物理削除を行います。なので、たとえどのトランザクションも参照しないことがわかっているテーブル内のタプルでも、PostgreSQLはそれがわからないため、物理削除をすることはできません。「誰からも可視にならないタプル」というのは「その時点で存在するどのスナップショットを使っても見えないタプル」ということなので、トランザクションが持つ各スナップショットが重要になってきます。

PostgreSQLでは、各スナップショットのxminの値と各トランザクションのXIDを共有メモリ上に持っており、それらの最小1のXID（Oldest Xmin）よりも小さいXIDによって削除されたデータのみVacuumできます。

ちなみに、スナップショットとXIDはそれぞれ存在期間が異なります。スナップショットはある時点でのデータベースデータを見るために使われるので、トランザクション分離レベルによってはSQL毎に生成されたり（例えばREAD COMMITTEDの場合）、トランザクション全体で同じスナップショットを使ったり（例えばREPEATABLE READの場合）します。一方、XIDはトランザクション内で初めてデータを更新した時（UPDATE、DELETEやCREATE TABLEも含む）に発行され、トランザクションが完了するまでXIDを持ち続けます。

※RC: READ COMMITED, RR: REPEATABLE READ

Vacuumにおいては、Oldest Xminの値が、Vacuumがどれくらいのタプルを物理削除できるかに影響するのでOldest Xminを進めることがとても重要です。

例えば、長時間実行中のSQLは同じスナップショットを持ち続けているので、Oldest Xminが進まない原因となります。また、XIDが発行された後、COMMITを忘れて途中で止まっているトランザクションも、XIDをずっと保持し続けていることになるので、Oldest Xminが進まない原因となります。「ロングトランザクションがVacuumのゴミ回収を阻害する」とよく言われるのはこの仕組のためです。

ロングトランザクション”扱い”となるもの

Oldest Xminを算出するときにはスナップショットのxminやXIDを含め、以下のものが考慮されます（カッコ内はその値が見れるビューと列名）。

  • トランザクションのXID（pg_stat_activity.backend_xid）
  • スナップショットのxmin（pg_stat_activity.backend_xmin）
  • 完了していない2相コミット用のトランザクション（pg_prepared_xacts.transaction）
  • ロジカル・デコーディング/レプリケーション（pg_replication_slots.xminとcatalog_xmin）
  • ホットスタンバイを有効にしているスタンバイサーバ（pg_stat_replication.backend_xmin）

細かい最適化はありますが、基本的にはこれらのXIDの最小値がOldest Xminとなります。

テーブルのVacuum

Vacuumの良いところは、INSERT、DELETEやUPDATEと同時に実行可能なところです。Oldest Xminを算出した後、テーブルの先頭からスキャンし、ゴミタプルを見つけていきます。ゴミタプルとして回収した領域は空き領域マップ（Free Space Map）と呼ばれる場所に格納し、後で、INSERT等でタプルを追加するときに利用します。

自動Vacuumにより、テーブル毎の統計情報（ゴミタプルの数など）をもとに自動にVacuumされます。手動でVacuumを実行することもでき、手動の場合はパラレルVacuumやVacuum Fullが利用可能です。

インデックスのVacuum

ここまではテーブルについての話でしたが、テーブルを更新した場合、テーブルだけでなくインデックスにもゴミが溜まるので、インデックスでのVacuumが必要です。PostgreSQLはすべてのインデックスがテーブルを直接参照し、InnoDBのようなセカンダリインデックスの仕組みはありません。

PostgreSQLでは、テーブルにタプルを挿入する際はテーブル、インデックスの両方に挿入しますが、削除する際はテーブルのタプルだけ削除します。なので、削除したタプルを参照するインデックスは残ります。次にインデックスを経由してテーブルを取得した時に、「このインデックスが参照しているテーブルのタプルは削除済み」ということがわかるので、インデックスのタプルに削除マークを入れます(インデックスタプルにはxmaxを入れるところはなく、ここでは本当に削除を示すフラグを立てるだけ)。インデックスVacuum時に、削除マークのついたインデックスを回収します。

最後に

PostgreSQLでのMVCCの実装やガベージコレクション（Vacuum）の仕組みが伝われば幸いです。トランザクション周りの他の機能（SAVEPOINTや2相コミット）、Vacuumでのいろいろな最適化などは別の機会に記事にできればと考えています。また、shallow1729さんの記事も読んでいただき、MySQL（innoDB）との実装の違いなどを感じるのも面白いかもしれません。

最後まで読んでいただきありがとうございました。

  1. XIDは周回するので正確には「最古のXID」 ↩