私たちが最も嫌っているPostgreSQLの部分（2023年）

 (cs.cmu.edu)
4 ポイント 投稿者 GN⁺ 2024-10-21 | 1件のコメント | WhatsAppで共有
  • PostgreSQLは最近、インターネットのデフォルト選択肢のように見なされているが、Carnegie MellonとOtterTuneの経験では、MVCC実装の運用負荷はMySQL、Oracle、Microsoft SQL Serverより大きい
  • 行を更新するとき、既存の行を上書きせず新しい物理バージョンを作るappend-only保存方式と、古いバージョンから新しいバージョンへたどるO2Nチェーンが中核設計となっている
  • この構造は、タプル全体のコピー、dead tupleの蓄積、すべてのインデックス更新、autovacuum依存につながり、HOTアップデートが可能な場合にのみ一部のコストを回避できる
  • OtterTuneの顧客PostgreSQL分析では、平均して約46%の更新だけがHOT最適化を使っており、デフォルトのautovacuum設定では大きなテーブルの整理が長く遅れることがある
  • PostgreSQLは依然として魅力的なDBMSだが、書き込みの多いワークロードや大規模テーブルでは、ストレージ容量、I/O、メモリ、インデックス保守、vacuum運用を自分で管理しなければならない

PostgreSQL MVCCが問題になる理由

  • データベースの選択肢は、2023年4月時点でDBDBに897個が登録されているほど多いが、時期ごとに事実上のデフォルト選択肢があった
    • 2000年代には、GoogleとFacebookが使っていたMySQLが慣例的な選択肢だった
    • 2010年代には、MongoDBが「webscale」のイメージとともに注目された
    • 直近5年間は、安定性、豊富な機能、拡張性、運用ワークロードへの適合性からPostgreSQLが広く好まれている
  • この記事の焦点は、PostgreSQLの**多版同時実行制御（MVCC）**実装である
    • Carnegie Mellonの研究とAmazon RDS PostgreSQLの最適化経験では、PostgreSQLのMVCC実装はMySQL、Oracle、Microsoft SQL Serverより悪いと評価されている
    • Amazon Aurora PostgreSQLも同じ構造的問題を抱えている

MVCCの目的とPostgreSQLの設計選択

  • MVCCは、複数のクエリが可能な限り互いを妨げずに同時にデータベースを読み書きできるようにする方式である
    • DBMSは既存の行を上書きせず、論理行ごとに複数の物理バージョンを維持する
    • クエリは生成時刻のようなバージョン順序に従って、自分に適したバージョンを読む
    • トランザクション開始時点のデータベーススナップショットを見るスナップショット分離が可能になる
  • 読み取り処理は、同じ項目を更新する書き込み処理による明示的なレコードロックでブロックされる状況を減らせる
  • MVCC DBMSは大きく3つを決める必要がある
    • 既存行の更新をどう保存するか
    • 実行時にクエリに合った行バージョンをどう見つけるか
    • もはや見えない期限切れバージョンをどう削除するか
  • PostgreSQLは1980年代に行った最初の選択のために、残る2領域でも今日まで負担を抱えている

append-onlyバージョン保存

  • PostgreSQLは最初から多版対応を前提に設計されており、更新時には既存行を上書きせずコピーを作ってから新しいバージョンに変更を適用する
  • この方式はappend-onlyバージョン保存と見なせる
    • 既存タプルを更新すると、DBMSはテーブル内で新しい行バージョン用の空きスロットを確保する
    • 現在バージョンの行内容を新しいバージョンにコピーする
    • 新たに割り当てられたバージョンスロットに変更を適用する
  • 例のテーブルは映画情報を保持するmoviesテーブルである
    • idは主キーで、name、year、directorカラムを持つ
    • movies_pkey主インデックスと、idx_name、idx_director補助B+Treeインデックスがある
  • "Shaolin and Wu Tang"の公開年を1985年から1983年に変える更新では、元のタプルをコピーした後、新バージョンに変更後の年を適用する
    • 既存ページに空きがなければ、新バージョンは別のテーブルページに作成されることがある

バージョンチェーンとO2N方式

  • 複数の物理バージョンが同じ論理行を表す場合、DBMSはバージョン間の関係を記録する必要がある
    • MVCC DBMSは単方向連結リストとしてバージョンチェーンを作る
    • チェーンは、保存容量と保守コストを減らすため一方向にだけつながる
  • バージョンチェーンの順序は2種類ある
    • N2O: 最新バージョンが以前のバージョンを指し、チェーンの先頭は常に最新バージョン
    • O2N: 各バージョンが新しいバージョンを指し、チェーンの先頭は最古のバージョン
  • OracleとMySQLを含む大半のDBMSはN2Oを実装している
  • PostgreSQLは、Microsoft SQL ServerのIn-Memory OLTPエンジンを除けば珍しくO2Nを使っている
    • O2Nは、タプルが変更されるたびにインデックスが新バージョンを指すよう更新する必要を減らせる
    • その代わり、最新バージョンを見つけるために長いバージョンチェーンをたどる必要がある場合がある
  • PostgreSQLの行ヘッダーにあるt_tcidフィールドは、次のバージョンのタプルIDを保持するか、最新バージョンであれば自分自身のタプルIDを保持する
    • インデックスが古いバージョンを指している場合、PostgreSQLはチェーンをたどって新しいバージョンを探さなければならない

インデックスでチェーン探索を減らす方法

  • PostgreSQL開発者は初期から2つのコストを認識していた
    • 更新ごとにタプル全体の新しいコピーを作るコストが大きい
    • ほとんどのクエリにとって、必要な最新バージョンを見つけるためにバージョンチェーン全体を探索するのは無駄である
  • PostgreSQLは長いチェーン探索を避けるため、行の各物理バージョンごとにテーブルインデックス項目を追加する
    • 論理行1つに物理バージョンが5つあれば、そのタプルに対してインデックス項目が最大5つ作られることがある
    • idx_nameインデックスが"Shaolin and Wu Tang"の複数バージョンを指していれば、PostgreSQLは最新バージョンに直接アクセスできる
  • 最新バージョンへのアクセスは速くなりうるが、インデックスは大きくなり、保守コストも増える

HOTアップデート最適化

  • PostgreSQLは、関連バージョンが複数ページに散らばり、複数のインデックス項目が生じる状況を減らすため、HOT(heap-only tuple)アップデートを使う
  • HOTアップデートが可能な条件は2つある
    • 更新がテーブルインデックスで参照されるカラムを変更しないこと
    • 新バージョンを以前のバージョンと同じデータページに保存できるだけの空きがあること
  • HOTが適用されると、インデックスは引き続き古いバージョンを指し、クエリはバージョンチェーンをたどって最新バージョンを見つける
  • PostgreSQLは通常動作の中で古いバージョンを削除し、バージョンチェーンを剪定する最適化も行う

dead tupleの除去とvacuum

  • PostgreSQLは更新のたびに行のコピーを作るため、古いバージョンであるdead tupleを除去しなければならない
  • 1980年代の初期PostgreSQLはdead tupleを削除していなかった
    • 古いバージョンを保持すれば、特定時点のデータベース状態を見るtime-travelクエリを実行できるという発想だった
    • しかしdead tupleを除去しないと、削除があってもテーブルサイズは縮まず、頻繁に更新されるタプルのバージョンチェーンが長くなる
  • PostgreSQLはvacuum手順でテーブルからdead tupleを整理する
    • vacuumは前回実行以降に変更されたテーブルページを順次スキャンし、期限切れバージョンを探す
    • あるバージョンがアクティブなトランザクションから見えなければ、expiredと見なされる
    • 現在のトランザクションはそのバージョンにアクセスせず、将来のトランザクションも最新のliveバージョンを使うため、空間再利用は安全である
  • PostgreSQLは設定に応じてautovacuumを定期的に自動実行する
    • グローバル設定で全テーブルのvacuum頻度を調整できる
    • テーブル単位のautovacuum設定も可能である
    • ユーザーはVACUUM SQLコマンドで手動実行できる

問題1: タプル全体のコピー

  • append-only MVCCでは、タプルの1カラムだけが変わっても全カラムを新バージョンへコピーする
  • この方式はデータ重複と必要ストレージ容量を大きく増やす
    • PostgreSQLは他のDBMSより、同じデータベースを保存するのに多くのメモリとディスクを必要とすることがある
    • その結果、クエリが遅くなり、クラウドコストが増える可能性がある
  • MySQLとOracleは新バージョンと現在バージョンの間の圧縮デルタを保存する
    • 1000カラムあるテーブルで1カラムだけ変われば、変更された1カラム分のデルタレコードだけを保存する
    • PostgreSQLは、変わった1カラムと変わっていない999カラムを含む新バージョンを作る
  • PostgreSQLのTOAST属性は別扱いなので、この比較からは除外される
  • EnterpriseDBは2013年、append-only保存エンジンをデルタバージョンベースへ変更しようとするzheapプロジェクトを開始した
    • 最後の公式更新は2021年の状況記事である
    • その後、目立った進展は見られない

問題2: テーブルbloat

  • PostgreSQLの期限切れバージョン、つまりdead tupleは、デルタバージョンより多くの空間を占有する
  • write-heavyワークロードでは、autovacuumが追いつく前にdead tupleがより速く蓄積することがある
    • テーブルが継続的に肥大化する可能性がある
    • dead tupleとlive tupleがページ内に混在しているため、クエリ実行中にdead tupleもメモリへ読み込まなければならない
    • 制御されないbloatは、テーブルスキャンでより多くのIOPSとメモリを消費させ、クエリ性能を下げる
    • dead tupleのせいでオプティマイザ統計が不正確になると、悪いクエリプランにつながることがある
  • 例として、moviesテーブルにlive tupleが1000万件、dead tupleが4000万件あるとすると、80%がobsoleteデータである
    • 平均タプルサイズが1KBなら、live tupleは10GB、dead tupleは約40GBを占める
    • テーブル全体のサイズは50GBである
    • 全表スキャン時、PostgreSQLは大半がobsoleteデータでもディスクから50GBを読み、メモリに載せなければならない
  • PostgreSQLにはシーケンシャルスキャンがバッファプールキャッシュを汚染するのを避ける保護機構があるが、I/Oコストそのものはなくせない

VACUUMとVACUUM FULLの違い

  • autovacuumが定期的に実行され、ワークロードに追いついていても、通常のautovacuumはストレージ容量をOSへ返却できない
  • 通常のVACUUMはdead tupleを除去し、各ページ内でlive tupleを再配置するが、ディスク上の空ページは回収しない
  • PostgreSQLが最後のページを空にできればそのページを切り詰められるが、他のページはディスク上に残る
    • 50GBテーブルから40GBのdead tupleを除去しても、PostgreSQLはOSやRDSの観点では50GBの割り当て容量を維持することがある
  • 未使用領域を実際に返却するには、VACUUM FULLまたはpg_repackでテーブル全体を新しい領域へ書き直す必要がある
    • どちらもリソース消費が大きく、長時間かかる
    • 本番データベースではクエリ性能に大きな影響を与えうる
  • VACUUM FULLは各ページのdead tupleを除去し、残ったlive tupleを新しいページへ圧縮して移し、不必要なページを削除する

問題3: 補助インデックス保守

  • PostgreSQLではタプルを1件更新するたび、そのテーブルのすべてのインデックスを更新しなければならない
  • 主インデックスも補助インデックスも、バージョンの正確な物理位置を保存しているためである
    • 新バージョンが以前のバージョンと同じページに保存されるHOTアップデートでない限り、更新のたびにこの作業が必要になる
  • 例の更新では、PostgreSQLは新バージョンをTable Page #2に作成した後、movies_pkey、idx_director、idx_nameに新バージョンを指す項目を挿入する
  • すべてのインデックスを変更しなければならない構造は、いくつもの性能コストを生む
    • 更新クエリが遅くなる
    • 各インデックスを探索し、新しい項目を挿入する追加I/Oが発生する
    • インデックスやバッファプールページテーブルなどの内部構造でlock/latch競合が起きる
    • 実際のクエリで使わないインデックスにも保守コストを払うことになる
    • Amazon AuroraのようにIOPS課金があるDBMSでは、追加の読み書きが問題になる
  • OtterTune顧客のPostgreSQLデータベース分析では、平均して約46%の更新がHOT最適化を利用していた
    • 残り50%以上の更新はインデックス保守コストを負担している
  • Uberの2016年のPostgresからMySQLへ移行した記事は、この問題を示す代表例である
    • 多数の補助インデックスを持つテーブルで、write-heavyワークロードが大きな性能問題に直面した
  • OracleとMySQLでは、補助インデックスが新バージョンの物理アドレスを保存しないため、同じ問題はない
    • 補助インデックスにはタプルIDや主キーのような論理識別子を保存する
    • DBMSはこの論理識別子を使って現在バージョンの物理アドレスを見つける
    • 補助インデックス読み取りは遅くなる可能性があるが、MVCC実装の別の利点でオーバーヘッドを減らしている

問題4: autovacuum運用の難しさ

  • PostgreSQLの性能は、obsoleteデータを除去して空間を再利用させるautovacuumの効果に大きく依存する
  • RDS、Aurora、Aurora ServerlessはいずれもPostgreSQL派生であるため、同じautovacuum問題を抱えている
  • autovacuumは複雑で、最適な状態で回すのが難しい
    • デフォルト設定はすべてのテーブルに適しているわけではない
    • 特に大きなテーブルで問題が大きくなる
  • autovacuum_vacuum_scale_factorのデフォルト値は20%である
    • 1億タプルのテーブルでは、最低2000万タプルが更新されて初めてautovacuumがトリガーされる
    • このため多くのdead tupleが長時間テーブル内に残り、I/Oとメモリのコストを生むことがある
  • long-running transactionはautovacuumを妨げる可能性がある
    • expired versionの整理が遅れると、dead tupleと古い統計が蓄積する
    • 性能問題がさらにlong-running transactionを生み、そのトランザクションが再びautovacuumを妨げる悪循環に陥ることがある
    • この場合、人手でlong-running transactionを終了させなければならないことがある

OtterTune顧客事例

  • あるPostgreSQL Amazon RDSデータベースでは、dead tuple数が2週間にわたりノコギリ状に変動していた
    • autovacuumが1日に1回ほど大規模な整理を実行していた
    • 2月14日には、DBMSがdead tuple 320万件を整理した
    • グラフ全体ではdead tuple数が増加傾向にあり、autovacuumが追いついていない異常状態だった
  • OtterTune顧客のあるPostgreSQL RDSインスタンスでは、bulk insertion後に古い統計が原因でlong-running queryが発生した
    • このクエリがautovacuumの統計更新を妨げた
    • その結果、さらにlong-running queryが発生した
    • OtterTuneの自動health checkが問題を特定したが、管理者はクエリを手動で終了し、bulk insertion後にANALYZEを実行する必要があった
    • 該当long queryの実行時間は52分から34秒に短縮された

実務的な結論

  • DBMS設計には常に難しい選択があり、その選択によってワークロードごとの性能は変わる
  • Uberの特定のwrite-intensiveワークロードでは、PostgreSQLのMVCCによるインデックス書き込み増幅がMySQL移行の理由だった
  • PostgreSQLのMVCC実装は、新しいMVCC DBMSを作るなら従うべきでない方式だと評価されている
    • append-only保存とautovacuumの組み合わせが中核問題である
    • この設計は1980年代の遺産であり、1990年代以降にlog-structuredシステムのパターンが広く普及する前の方式である
  • PostgreSQLは依然として好まれるDBMSだが、MVCCの弱点を受け入れたうえで運用する必要がある
  • 回避策は、自分で多くの時間と労力を投じてチューニングすることである

関連記事

1件のコメント

 
GN⁺ 2024-10-21
Hacker News の意見

  • Postgres の内部をかなり知っていると思っていたが、この記事は素晴らしく、多くを学べた。
    根本的な弱点の一つは、Postgres が行バージョン追跡に N2O ではなく O2N 方式を採用した点にあるように見える。N2O に変えればすべての問題が解決するわけではないだろうし、たとえば行全体のコピーを保存する問題は残るだろうが、80/20 の観点では現在の実装の欠点の大半を減らせそうだ。
    ほとんどのトランザクションは最新の行バージョンを求めるはずなので、N2O 順を使えば古いバージョンが必要なときだけ連結リストをたどればよく、各行バージョンをインデックスに保存しなくても済む可能性が高い。

    • Andy の YouTube 講義 History of Databases（CMU Databases / Spring 2020）を見るとよい。
      初回の授業全体を、ホテルに入れなかったためアムステルダムの通りで行っているのだが、キャラクターとしても興味深く、内部動作を説明する能力がものすごい。

  • 大きな利点は、ワークロードが主に INSERT とその後のテーブル削除で構成される場合、追加の領域が不要であること。
    一般に、挿入トランザクションを分割する必要もない。生成されるデータサイズや変更された総行数に実質的な制限がないためだ。トランザクション内の文数制限はあるが、テーブルをあまり頻繁に変更しないなら COPY FROM で回避できる。
    DBA の観点では、ロールバック/UNDO 領域をテーブルストレージとは別に管理する必要がない。アプリケーションによって違うが、PostgreSQL の設計があらゆる面で負けているわけではない。バブルソートのようなものではない、ということだ。

    • 2000年代初頭にゲーム開発をしていて、バブルソートもあらゆる面で負けているわけではないと学んだ。
      リストがほぼソート済みの状態では性能がよく、3D レンダリングでカメラからの距離を基準にオブジェクトをソートする場合がまさにそれだ。カメラを少し動かしたり回転させたりすると、前フレームの順序をもとに再ソートする際にバブルソートが非常によく機能する。
      最悪の場合を避けるには、直近のパスで失敗した比較回数と、これまで実行したパス数を数えておき、しきい値を超えたら別のソートアルゴリズムに切り替えればよい。
    • バブルソートはハードウェアや、ほぼソート済みの集合では優れている。
    • 記事では文字どおり、pg の MVCC 設計は90年代式で、今では誰もそうしていないと言っている。
      30年以上も古い技術なのだから、あらゆる面で負けているわけではないとしても、最も重要な側面では負けていると見る。

  • この記事は特に次の部分が間違っていると思う。
    「2000年代には、Google や Facebook のような台頭するテック企業が MySQL を使っているという理由で、通説は MySQL を選んだ。2010年代には、非永続的な書き込みのおかげで『ウェブスケール』になった MongoDB だった。ここ5年で PostgreSQL はインターネットに愛される DBMS になった。それには理由がある！ 信頼性があり、機能が豊富で、拡張可能で、ほとんどの運用ワークロードによく合う。」
    賢いエンジニアたちが Postgres を選んだのは、人気に訴える誤謬のためではなく、データ安全性、ACID、Oracle との類似性、MVCC、SQL 標準への準拠、Postgres チーム、優秀で助けになるコミュニティ、データ型、高い性能、BSD の柔軟性のためだった。
    2000年代初頭に ATT で Postgres を選んだ理由もこれらであり、Oracle DBA も移行を非常に容易に受け入れた。MySQL が荒い移行を経験する間、PG はずっと強くなり、改善され続けてきた。Bruce Momjian はこの成功に大きな役割を果たしたと思うし、本当に素晴らしいコミュニティがある。

    • 同じように、2005年に MySQL から PostgreSQL へ好みが変わった。
      古い AS400 データベーススキーマと現代的な Rails アプリの間に「ライブ」な互換レイヤーを作るため、データベースビューを使いたかったからだ。
      その後、データ安全性やトランザクション内の DDL などのおかげで、好みはさらに強まっていった。

  • 「MySQL と Oracle は、新バージョンと現在バージョンの間の圧縮されたデルタを保存する（git diff のようなものだと考えればよい）。」
    Git は有名な話として diff を保存しておらず、ここで Postgres が使っている方式のように、新しいオブジェクトと以前のオブジェクト全体を保存しているのでは？

    • 引用した文は、Git が diff を保存すると言っているのではなく、MySQL と Oracle が保存するものが git diff に似ていると言っているのだ。
    • その通り。ファイルの各バージョンは別々の blob だ。
      クローンを速くするためにパッキングで圧縮はするが、Git が扱う生の形はこうした blob だ。
    • 比較対象は Git の保存方式ではなく、MySQL と Oracle の保存方式が git diff 形式に似ているという比喩だった。
      Git リポジトリも圧縮を行い、その圧縮は一種の diff ベースだが、素朴に予想するようなコミット履歴ベースではない。
    • 他の人たちが「git diffs」と言っていた点を指摘したが、Git は実際に pack file で低レベル最適化として デルタを使っており、MySQL との比較に似ている。
      SQL クエリでも diff がそのまま返されるわけではない。
    • Git diff はその場で生成されるが、diff はそれでも diff だ。

  • 「PostgreSQL が各 update のたびにテーブルのすべてのインデックスを修正しなければならない必要性は、複数の性能上の影響をもたらす。当然、システムはより多くの仕事をしなければならないため、update クエリは遅くなる。」
    この 書き込み増幅について気になっていた。MySQL はそのようにインデックスを更新する必要がないのは確かだが、MySQL のレプリケーションは binlog に依存しており、すべての変更はデータベース自体（InnoDB redo log など）に加えて追加で記録されなければならない。
    そのため、クラスタで使う MySQL には別種の書き込み増幅があるように見える。PostgreSQL はレプリケーションに WAL を再利用するので、その増幅はない。
    さらに受信側では、MySQL は入ってくる binlog をまず relay log に書き込み、relay log を applier スレッドが消費しながら追加の InnoDB 書き込みと、デフォルト設定では追加の binlog を生成する。

  • このテーマはディスク抜きには語れない
    SSDは一度に4KBページを書き込む。つまり1ビットだけ更新しても、ディスクは4KBを読み、ビットを変更したうえで新しいスロットに4KBページを書き直す。したがってコピーのペナルティはディスクの種類によって変わる

    • 興味深い。これがAWSの課金にはどう反映されるのか気になる
      AWSはIOのMBpsに対して定額で課金するが、最も近い4KBに切り上げるルールがあるのか、それともリクエスト量ではなくドライブ自体の書き込み量を追跡して、ストレージ実装で実際のIO量を課金するのかは分からない
    • Postgresのページは8KBなので、その指摘はあまり意味がない

  • 「OracleとMySQLはMVCC実装でこの問題を抱えていない。セカンダリインデックスが新しいバージョンの物理アドレスを保存しないためだ。代わりに論理識別子（例：タプルID、主キー）を保存し、DBMSがそれを使って現在バージョンの物理アドレスを見つける。そのためセカンダリインデックスの読み取りが遅くなる可能性はあるが、これらのDBMSにはオーバーヘッドを減らすMVCC実装上の別の利点がある」
    MySQLで観察した興味深い挙動がある。約500GBのデータベースで、スキーマはリレーショナルというよりドキュメント指向に近かったが、SELECT id WHERE something; UPDATE what WHERE id=idがUPDATE what WHERE somethingより何桁も速い
    この挙動の理由はおそらくここにあるのではないかと思う。ただし通常のワークロードではこうはせず、不整合を直すための一時的なDMLでだけ遅くなる

    • SELECTは読み取り専用の処理なので並列実行が可能
      一方、UPDATEは実際に書き込みを行い、テーブルをロックする場合もある。UPDATE id=idは行レベルロックを可能にする。ただしSELECTとUPDATEの間に新しく挿入されたレコードを取りこぼすリスクもある
    • 読み取り中心の2TB超のPostgresインスタンスをいくつか運用していて、これらもドキュメント指向に近い
      大量更新が非常に遅くなり得るという点には同意する。結局、更新をバッチ単位で段階的に処理したり、場合によってはCOPYを使ったりすることが多い

  • 「2010年代はMongoDBだった。非永続書き込みのおかげで『Webスケール』になったからだ」
    話題からはそれるが、最初から最後までマーケティングだった: https://news.ycombinator.com/item?id=15124306

    • MongoDBは元DoubleClickのエンジニアたちが、別サービスに必要な要件を満たすDBがなかったため、おまけで作ったDIY DBとして設計された
      バージョン4.2.8（2020年）ではかなり堅牢になっており、ダーティライトはないとされている: https://en.wikipedia.org/wiki/MongoDB#Technical_criticisms

  • 2024年になっても、いまだに前段にコネクションプーラ（例：pgbouncer）を置かないと実用的でない点がいちばん嫌い

  • OrioleDBが新しいストレージエンジンでこの問題を解決しようとしていた: https://github.com/orioledb/orioledb

    • Supabaseチームにいる
      Orioleは今ではSupabaseに合流しており、Alexanderと彼のチームがフルタイムで取り組んでいる。パッチセットはこちら: https://www.orioledb.com/docs#patch-set
      今年末にはSupabaseプラットフォームでも試せるようになる予定