PostgreSQLのMVCC実装は効率が悪いという話

これは、なにをしたくて書いたもの？

気になる記事を見かけたので、メモということで。

昨今では人気のRDBMSであるPostgreSQLですが、合わせて出てくる話でVacuumがあります。

MVCCに端を発するものであることは知っていましたが、そういえばVacuumというのはPostgreSQL固有の話で、MVCCを
採用しているRDBMSはMySQLをはじめとして他にあるにも関わらず、似たような話を聞いたことがありません。

どうしてでしょう？とたまに思うことはあったものの、あまり深く追わずにきたのですが、その答えのような記事が
あったのでメモしておきます。

端的に言うと、PostgreSQLと他のRDBMSではMVCCの実装方針が異なり、PostgreSQLでは効率が悪い実装になっているから
ということのようです。

The Part of PostgreSQL We Hate the Most // Blog // Andy Pavlo - Carnegie Mellon University

以降、端的に書いていきます。

MVCCとはなにか？

MVCC（Multi Version Concurrency Control）とは、データベースに対して複数のクエリーが互いに干渉することなく同時に
読み書きできるようにする仕組みです。

基本的な考え方は、データベースが既存のレコードを上書きしないことになります。

アプリケーションがクエリーを発行した時に、データベースは要求を満たすバージョンのレコードを探します。

MVCCを実装する際には、以下の方針を決めることになるようです。

既存のレコードを更新し、保存する方法
実行時にクエリーに対する正しいレコードを見つける方法
有効期限切れになったレコードを削除する方法

PostgreSQLではこの方針を1980年代に決めたようなのですが、これが理由でストレージとVacuumという2つの問題を
引き起こしたと書かれています。

PostgreSQLのMVCC

Multi Versioned Storage

PostgreSQLでは、レコードを更新する場合は新しいレコード用に領域を確保します。そして、既存のレコードをコピーして
変更内容を適用します。

この結果、同じレコードに対して複数のバージョンが存在することになりますが、データベースはバージョンの更新履歴を
記録して、これらを使い分ける必要があります。これをデータベースは片方向のリンクリストを作成することで実現します。

このリンクリストの作り方は次の2つがあります。

N2O（newest-to-oldest） … 最新のバージョンから古いバージョンに向かってリンクリストを作成する
O2N （oldest-to-newest）… 最古のバージョンから新しいバージョンに向かってリンクリストを作成する

N2Oではリンクリストの先頭は常に最新のバージョンになります。O2Nでは先頭はもっとも古いバージョンになり、
バージョンが更新される度にデータベースがインデックスを更新して新しいバージョンを指す必要がなくなります。その代わりにクエリーを処理する際に新しいバージョンを探すのに時間がかかるという問題があります。

OracleやMySQLなど、ほとんどのデータベースはN2Oを実装しています。O2Nを実装しているのはPostgreSQLだけです。

PostgreSQLの開発者は、MVCC実装に次の2つの問題を抱えていることを認識していたようです。

バージョンが更新される度にレコードのコピーを作成する必要がある
最新バージョンを見つけるためにリンクリストの全バージョンをたどる必要がある

この対処のひとつとして出てきたのがHeap Only Tuple（HOT）のようです。

Version Vacuum

アプリケーションがレコードを更新する度に、レコードのコピーが作られるという話でした。

1980年代のオリジナルのPostgreSQLでは、古いバージョンすべてを保持することでアプリケーションに任意の時点の
データを参照させることができるという考え方があったようです。

ですが古いバージョンが残り続けるとテーブルのサイズは小さくなりませんし、バージョンを管理するリンクリストが
長くなりクエリーの速度が低下します。

このためPostgreSQLはインデックスを追加することで、リンクリストをたどる代わりに新しいバージョンに素早くジャンプ
できるようにしています。

これらの問題を解消するためのものがVacuumです。

PostgreSQLのMVCCの問題点

この記事では、PostgreSQLのMVCCには以下の4つの問題点があるとされています。

バージョンのコピー
- レコードが更新されると、その度にコピーが作成される
- 大量のデータが重複しストレージの使用量は増え、他のデータベースに比べてメモリーとストレージを必要とし、クエリーの速度が低下する
テーブルの肥大化
- 期限切れのバージョンが蓄積される
- 書き込み負荷の高いワークロードでは、Vacuumが追いつかないほどバージョン履歴が蓄積され、データベースが肥大化する可能性がある
- Auto Vacuumが実行されてもストレージ領域を回収できない
セカンダリーインデックスのメンテナンス
- レコードを1回更新するだけで、PostgreSQLはそのテーブルのすべてのインデックスを更新する必要がある
- プライマリーインデックスとセカンダリーインデックスの両方でレコードのバージョンの正確な物理的な位置を記録しているため
- 更新クエリーのパフォーマンス低下の原因となり、ロックが発生する
- クエリーでインデックスが使用されなくても、このメンテナンス作業は発生する
Vacuumの管理
- データベースの性能を維持するためにAuto Vacuumを管理する必要がある
- Auto Vacuumを最適化することは困難であり、特にデフォルト設定は大規模テーブル向けではない
- ロングトランザクションがあるとAuto Vacuumがブロックされてしまい、古いバージョンや統計情報が削除されないままになる
  - これが悪循環することもある