PostgreSQLの共有バッファ(shared_buffer)とMySQLのバッファプール(buffer_pool)のメカニズム比較

MySQL PostgreSQL

PostgreSQLとMySQLのバッファについて。

PostgreSQLのバッファマネージャ

詳細はこちらをみて頂くとして、PostgreSQLのバッファマネージャは、２００５年リリースのバージョン8.1で大幅に変わった。

以下の表をみて頂くとわかるようにページ置換アルゴリズムは、8.0まではリストで実装したLRUとそのバリエーションであったが、8.1から配列で実装したClockSweep方式になった。



ページ置換アルゴリズムとロックの変遷
バージョン ページ置換アルゴリズム バッファマネージャのロック
方式 説明 PostgreSQL
での呼称		 説明
7.4まで
[〜2004]		 LRU "Least Recently Used"の略称。最もオーソドックスなアルゴリズム。 BufMgrLock 排他ロックのみ。ページの入れ替えだけでなく、読み取りでも排他ロックをかける*1。
8.0.0〜8.0.1
[2005.1]		 ARC "Adaptive Replacement Cache"の略称。LRUのバリエーション。IBMが特許申請したため、8.0.2で不採用となった。
8.0.2〜8.0.36
[2005.2]		 2Q ARC特許問題回避のために行われた一時的実装。
8.1
[2005.11]		 Clocksweep 実際はClocksweepのバリエーションで、様々な改良を加えている。 BufMappingLock 読み取りでは共有ロック、ページの入れ替え時だけ排他ロックをかける。
8.2以降
[2006.12]		 ロックを(デフォルトで)16分割して、より並列実行性を高めた。


PostgreSQLのバッファマネージャの構造を以下に示す。３層に分れている：

[<バッファマネージャの構造>]

  • バッファテーブル

　(テーブル名＋ブロック＝ページ番号)をキーとして、バッファディスクリプタの位置を求めるハッシュテーブル

  • バッファマネージャ

　ページ置換アルゴリズムを実装した層

  • バッファプール

　実際のページを保存している領域



バッファマネージャは配列で実装されている。配列をリングと見なして使う。


[<バッファディスクリプタ層とバッファディスクリプタ>]

配列の要素は、大きく３つに分類される。もちろん、動的に役割は変化する。

  1. 未使用
  2. 使用済み
  3. 使用中

バッファディスクリプタの論理構造

例えば、読み込み済み(使用済み)のデータにアクセスする場合の手順は以下：
[<読み込み済のページにアクセスする場合>]

(1)BufMappingLockで共有ロックをかけ、該当するバッファディスクリプタを見つける。
(2)みつけたバッファディスクリプタにPinを立て(refcountに+1する)、usage_countにも+1する。
(3)BufMappingLockを解除する。


次にHDDからデータを読み込む場合をしめす。

これには２つのパターンがある。一つ目は、Freelist(未使用)から一つ取り出してHDDからデータを読み込むパターン。

[]

(1)BufFreelistLockで排他ロックをかけて、Freelistからvictimを選ぶ。 victimディスクリプタにPinを立てて(refcount++)、usage_countに+1する。 BufFreelistLockはすぐに解除する。
(2)BufMappingLockで排他ロックをかけ、BufferTableを更新する。 更新後すぐにBufMappingLockを解除する。
(3)io_in_progress_lockで排他ロックをかけ、HDDからデータを読み込む。


２つ目は使用済みからvictimを選んで使うパターン。サーバがしばらく稼働するとFreelistは尽きるので、 使用済みのバッファディスクリプタからvictimを選ばなければならない。 バージョン8.1からはClocksweepで選ぶ。
ちょっと説明が面倒なので、詳細は詳細はこちらか拙書を参照。
ざっくりいうと、バッファディスクリプタのリング内に針をおく。その針がくるくる回ってvictimを選ぶ。それが時計の針のように見えるからClockSweep。しかし単純な実装では、本来なら残すべきデータが針に指されてvictimになる可能性がある。なので、データがアクセスされた回数も考慮してvictimを選ぶ(針に指されるとusage_count--、usage_count==0が見つかるまでくるくる針を廻す)。

同時実行性能を向上させるために

バージョン8.2以降、BufMappingLockはデフォルトで１６分割している。
ロックの粒度は細かいほうがよい。(非公式情報ながら)分割は256分割でも512分割でも問題ない。メカニズムを考えても、分割によるオーバーヘッドなどないので、なるべく細かく分けた方がよいのだろう。



というわけで厳密なLRUを棄て、ページ置換アルゴリズムも実装そのものも簡単になり、性能が向上した。また、BufMappingLockの範囲を細かく分割できるおかげで並列実行性も著しく向上した。


これらは８年から５年くらい前にホットだった話題である。


現在はというと、"こんな議論"がなされている。昔にくらべてメモリが安価になり、巨大なshared_buffer領域を確保できるようになったので、clock sweepでvictim pageを探す部分がボトルネックになってんじゃね？という、贅沢なお話。

MySQL InnoDBストレージエンジンのバッファマネージャ

MySQLのInnoDBストレージエンジンについて。こちらのバッファはバッファプール(buffer_pool)と呼ばれている。

バッファプールはリストで実装。LRUということになっているが、ちょっと工夫されている。

HDDなどから読み込んだページをバッファプールに書き込む際innodb_old_blocks_pctで示した位置に書き込む。先頭ではなく、デフォルトで後方から37%くらいのところ。

アクセスされないまま後ろに移動したデータはいずれはみ出して棄てられるが、はみ出す前に再度アクセスされたデータは先頭に移動する。

(lockfree-listやLazy Listなんてのもあるにはあるが、普通は)リスト操作ではジャイアントロックをかけることが多いので、性能向上させるには地道な努力が必要。実際、バージョン5.1から5.6にかけ、非常に苦労してコツコツ性能向上させてきたのはご存知のとおり*2。

同時実行性能を向上させるために

バージョン5.5でやっと複数のバッファプールを持って処理を並列化できるようになった。ただし、一つのバッファプールは1Gバイト以上確保しないとダメである。
何故なら、一つのバッファプールが一つのリストになっているので、あまり小さくしすぎると、すぐにデータがあふれてキャッシュ効果が得られなくなるからである。
よって、同時に実行するスレッドの数との兼ね合いで分割数を決めることになる。


巨大テーブルスキャン対策

バッファマネージャの天敵は、フルテーブルスキャンによるデータの追い出しである。

たった一度読み込むだけなのに、それまでメモリ上に留まり続けた使用頻度の高いデータが皆追い出されてしまう。

PostgreSQLのリングバッファ

PostgreSQLはバージョン8.3でリングバッファという256kバイトの小さい一時的なバッファ*3を使うことで解決した。
バッファサイズの1/4を超えるテーブルのデータをフルテーブルスキャンで読み込む場合は、リングバッファに読み込む。このデータに関してはキャッシュ効果はでないが*4、バッファ上のデータは追いだされず、サーバのキャッシュ効果は持続する。

MySQLのinnodb_old_blocks_pct,innodb_old_blocks_time

MySQLは（上図にも書いたが）読み込んだデータをinnodb_old_blocks_pctの位置に書き込むのだから、巨大テーブルをフルスキャンしても、順次old_sublistのほうに押し出されていく。もともと対策済みといえる。

さらにMySQLはinnodb_old_blocks_timeというパラメータで、再アクセスしても先頭に移動するまでの時間を遅らせることができる。
それほど頻繁にアクセスしないテーブルのスキャンなら、先頭への移動はタイムアウトしてしまい、いずれバッファプールから消えていく。young-sublistの使用頻度の比較的高いデータは押し出されないので、めでたしめでたし。

これらのパラメータが導入されたのはバージョン5.1。



バッファのお掃除

バッファのゴミ(dirtyページ)は、通常はcheckpoint時にまとめてHDDに書き込む。しかし、更新が多い＝dirtyページが多い場合はcheckpoint毎に書き込みが集中してサーバの性能が極端に劣化する。
このような状況を避けるには、checkpointとは別のゴミ掃除機構が必要になる。


PostgreSQLは8.0からbackground-writerでバッファのゴミをHDDに書き込むようになっていた。
MySQLはPostgreSQLに遅れること約７年、バージョン5.6でやっと、page_cleanerというお掃除スレッドがはいった。

その他

MySQLバージョン5.6は、shutdownする時にバッファプールの内容を保存できる*5。そして再起動時は、保存されたバッファプールの内容を読み込んで、いきなり停止前のキャッシュ効果を発揮する。
相変わらず、飛び道具が得意。

が、今やPostgreSQLもpg_prewarmというextensionが用意されている。

*1:postgresプロセスが同時にアクセスしようとしても、BufMgrLockが排他ロックなので同時に読み込みできるのは一つのプロセスだけ。これは並列処理の大きなボトルネックとなっていた。

*2:ページの先読みとか、読み書き専用のスレッドをいくつも独立で走らせるとか、CPU依存のatomic命令できわどい排他制御をやるとか、ロック周りの改良とか。。。。

*3:256kの理由は、ソースコードのsrc/backend/storage/buffer/READMEに書いてある。いかにもPostgreSQLらしい理由である。

*4:実は、複数のトランザクションが同時に同じテーブルをスキャンする場合、リングバッファを共用してスキャンする。当然、キャッシュ効果がある。これを”同期シーケンシャルスキャン”と呼んでいる。

*5:データをバイナリダンブするわけではない。テーブルデータのどのページがバッファプールにあったか、可読なファイルで保存されている