[pgsql-jp: 40838] Re: backend/storage/buffer/README翻訳

Tatsuo Ishii ishii ＠ sraoss.co.jp
2011年 6月 30日 (木) 14:34:39 JST 

石井です。

片岡さん、那賀さんのご指摘を受け、更にその他の細かい修正を加えたバージョンです。

原文: postgresql-9.0.4/src/backend/storage/buffer/README

共有バッファのアクセスルールに関するメモ
======================================

共有ディスクバッファのアクセス管理の仕組みは2種類あります。リファレンス
カウント(つまりピンカウント)と、バッファ内容ロック(buffer content
lock)です。

(実際には第3のレベルのアクセス管理があります。リレーションのページを正
当な方法でアクセスするためには、適切なリレーションロックを獲得する必要
があります。リレーションレベルのロックについては、ここでは議論しません)。

ピン:バッファで何かする前に必ずバッファに対して「ピンを保持する」(参照
カウンタをカウントアップする)という操作が必要です。ピンが保持されていな
いバッファは、他のページのために必要に応じていつでも回収、再利用される
ので、そういったバッファに触るのは安全ではありません。

通常、ピンは ReadBuffer で獲得し、 ReleaseBuffer で解放します。バックエ
ンドが同時に同じページにピンを保持するのは普通にあることですし、問題あ
りません。バッファマネージャが効率よくこうした事態をさばきます。ピンを
長い期間保持するのも問題ありません。たとえば、ジョインのアウター側をス
キャンする際には、ページ上のすべてのタプルに対する順スキャンが行われ、
かなり長い時間がかかります。同様に、btreeインデックススキャンでは、現在
のインデックスページのピンを保持します。通常の処理では、ピンのカウンタ
が0になるまで待つことはないので、これは通常問題になりません(そのような
操作が必要な場合は、リレーションレベルのロックを代わりに取得します。最
初にピンを保持した方が良いのはこうした理由によります)。ただし、トランザ
クションをまたがってピンを保持することはできません。

バッファの内容に対するロック:共有と排他の2種類のバッファロックがありま
す。その働きは想像の通りです。複数のバックエンドは同じバッファに共有ロッ
クを保持することができますが、あるバックエンドが排他ロックを保持してい
る場合は、他のバックエンドが共有ロックまたは排他ロックを取得することは
できません(これらは、READロックとWRITEロックと呼ばれることがあります)。
これらのロックは短期間保持されることを想定しています。長期間保持しては
いけません。バッファロックは LockBuffer() を使って獲得と解放を行います。
ある単一のバックエンドの中で同じバッファに対して複数回のロックを取るこ
とはできません。ロックを取る前に、そのバッファにピンしてください。

バッファのアクセスルール:

1. タプルを取得するためにページをスキャンする際には、ピンを保持してから
共有または排他ロックを獲得します。共有バッファ上のタプルのコミットステー
タス(XIDおよびステータスビット)を調べる際にも、ピンと共有または排他ロッ
クの獲得が必要です。

2. あるタプルが意味のあるもの(現在のトランザクションから見て可視的
(visible))であることがわかったら、内容ロックを解放しても構いません。バッ
ファピンを保持している間はタプルのデータにアクセスできます。ヒープスキャ
ンではこのような使い方が典型的です。なぜなら、heap_fecth が共有バッファ
上のタプルデータへのポインタを持っているからです。というわけで、ピンが
保持されている限りタプルを消すことはできません(ルール #5を参照)。タプル
の状態は変わるかもしれませんが、最初にタプルの可視性を確定した後ではそ
れはどうでも良いことです。

3. タプルを追加したり、注目しているタプルの xmin/xmax フィールドを変更
するには、該当バッファにピンと排他ロックを獲得しなければなりません。こ
れにより、可視性のチェックを行う際に更新中の中途半端な状態を見ることが
ないことが保証されます。

4. 共有ロックとピンさえ保持すれば、タプルのコミットステータスビットを更
新(すなわち、HEAP_XMIN_COMMITTED, HEAP_XMIN_INVALID,
HEAP_XMAX_COMMITTED, HEAP_XMAX_INVALID を OR して t_infomask に書き込
む)するのは問題ないと考えれます。なぜなら、ほぼ同じ時刻にそのタプルを
参照している他のバックエンドが同じビットを OR してそのフィールドに書き
込むのは、リスクがないか、あってもわずかであると考えられるからです。仮
にコンフリクトがあったとしても、それは単に 1ビットの更新が失われただけ
であり、後に復旧できます。これらの4ビットはヒントに過ぎず(これらのビッ
トは pg_clog を参照した結果をキャッシュしています)、衝突した更新によっ
てビットが0になったとしても、大した問題にはなりません。

5. タプルを物理的に削除する、もしくはページのフリースペースを圧縮するに
は、ピンと排他ロックを獲得しなければなりません。加えて、排他ロックを保
持している間、バッファの共有カウントが1であることを確認しなければなりま
せん(つまり、他にピンを保持しているバックエンドがない、ということです)。
これらの条件が満たされていれば、排他制御が解放されるまでは他のバックエ
ンドがページをスキャンすることはできませんし、他のバックエンドが再検査
されるかもしれない既存のタプルへの参照を保持していることもないと言えま
す。なお、あるバックエンドがクリーンナップ処理をしている間に他のバック
エンドがバッファピンを保持する(よって参照カウンタが増える)ことはあり得
ます。しかし、共有または排他ロックを獲得するまでは、実際にはそのページ
を見ることはできません。

ルール #5は VACUUM 操作にのみ影響します。必要なロックはバッファマネージャ
の LockBufferForCleanup()によって獲得されます。はじめて排他ロックを獲得
すると、共有ピンカウンタが現在1であることを確認します。もしそうでなけれ
ば、排他ロックを解放し(ただしピンは保持したまま)他のバックエンドからの
シグナルを受けとるまで待ちます。シグナルを受けとったら、再度同じ処理を
繰り返します。シグナルは、 UnpinBuffer が共有ピンのカウントを1に減少さ
せたときに発生します。上述のように、この操作はロックを獲得するまでしば
らくかかることがあります。しかし、コンカレント VACUUM にとってはそれは
大した問題にはならないでしょう。現在の実装では、ある共有バッファのピン
カウントが1になる状態を待つのは一人に限定されます。今のところあるリレー
ションに対して複数の VACUUM を同時に行うことは許されていないので、
VACUUM 操作にはこれで充分です。

バッファマネージャの内部ロック操作

PostgreSQL 8.1より前は、共有バッファに対するすべての操作は単一のシステ
ム全体のロックである BufMgrLock で保護されていました。もちろんこれは競
合の原因となっていました。新しいロック方法では、ほとんどの場合にシステ
ム全体のロックを獲得することは避けるようになっています。

以下のように処理が行われます。

* システム全体の LWLock である BufMappingLock が存在します。これは、バッ
  ファに対するバッファタグ(ページ識別子)のマッピングを保護する意味があ
  ります。(実装上では、 buf_table.c で定義されるハッシュテーブルを保護
  するものと考えられます)タグに対応するバッファを見つけるには、
  BufMappingLock に対して共有ロックを獲得するだけで充分です。なお、
  BufMappingLock を解放する前に、見つかったバッファにピンを保持しなけれ
  ばなりません。バッファに対応するページを変更する際には、
  BufMappingLock に対して排他ロックを獲得しなければなりません。バッファ
  ヘッダや buf_table ハッシュテーブルを変更している間は、そのロックは保
  持しておかなければなりません。排他ロックを必要とする典型的な操作は、
  共有バッファ上にないページを読み込む場合だけです。これはカーネルコー
  ルを必要としますし、通常I/O待ちが発生するので、どちらにしても遅い操作
  です。

* PostgreSQL 8.2では、 BufMappingLock は NUM_BUFFER_PARTITIONS 個の別々
  のロックに分かれています。これによって通常の実行パスでの競合が少なく
  なっています。タグのハッシュ値の低位ビットから、あるバッファがどのパー
  ティションに所属するかが決まります。この処理は、それぞれのパーティショ
  ンに対して独立して行われます。もし複数のパーティションを同時にロック
  する必要がある場合は、デッドロックを避けるために、パーティション番号
  順にロックをかけなければなりません。

* バッファフリーリストへのアクセスまたは置換対象のバッファの選択操作を
  相互排他的に行えるようにするために、別のシステム全体の LWLock である
  BufFreelistLock が提供されています。これらのデータ構造の操作では読み
  出しのみということはあり得ないので、排他ロックが常に使われます。バッ
  ファマネージメントポリシーは、I/Oが必要でどちらにしても遅い実行パス以
  外では BufFreelistLock を取得する必要がないように設計されています(詳
  細は後述)。 BufMappingLock と BufFreelistLock を同時に取得する必要は
  ありません。

* 各々のバッファヘッダにはスピンロックがあり、バッファヘッダのフィール
  ドを見たり、変更する必要があるときは必ず獲得しなければなりません。こ
  れによって、 ReleaseBuffer のように、ローカルな状態を変更する際にシス
  テム全体のロックを取らなくても済むようになっています。これらの操作は、
  数回のマシンコード実行しか必要ないので、 LWLock ではなくてスピンロッ
  クが使われます。

  バッファヘッダのスピンロックは、バッファ内のデータを管理するものでは
  ないことに留意してください。各々のバッファヘッダには LWLock 「バッファ
  内容ロック」があり、バッファ内のデータへのアクセス権を表します。この
  ロックは、上述のルールに従います。

  これ以外に、バッファ単位の一連の LWLock があります。 io_in_progress
  ロックはバッファのI/Oの完了待ちに使われます。読み書きを行うプロセスは
  その間排他ロックを獲得します。そのロックを待つプロセスは共有ロックを
  獲得します(共有ロックは獲得出来次第すぐに解放されます)。XXX LWLock が
  少なからず資源を消費するようなシステムでは、たくさんのロックを獲得し
  なければならないことが問題になります。たぶん、代わりにバックエンド単
  位の LWLock を使うことができるでしょう(その場合は、バッファヘッダにど
  のバックエンドがI/Oをしているのかを示すフィールドが追加されます)。

通常のバッファ置換戦略

優先的な置き換え対象を表す「フリーリスト」があります。特に、
完全に自由なバッファ(意味のあるデータを含まないページ)は常にこのリスト
に含まれます。近々に必要なさそうなページもこのリストに登録できるでしょ
う。しかしながら、現在のアルゴリズムでは、決してこれは行いません。この
リストは、バッファヘッダのフィールドを使った単一リンクです。広域変数に
リストの先頭と最後が保持されます(このリストはバッファヘッダにありますが、
バッファヘッダスピンロックではなくて BufFreelistLock によって保護されま
す)。空いているバッファがなくて再利用する対象のバッファを選ぶ際には、単
純なクロックスィープアルゴリズムが使われます。このアルゴリズムでは、通
常の操作において、システム全体にわたるロックの獲得を避けることができます。
こんな風に動きます。

各々のバッファヘッダには利用カウンタがあります。バッファがアンピンされ
たら必ずカウントアップされます(上限値は小さな値です)。(この操作はバッファ
ヘッダスピンロックだけが必要で、それはバッファリファレンスカウントをカ
ウントダウンする際に獲得されるので、ほとんどコスト0です)

「時計の針」はバッファのインデックスである NextVictimBuffer で、すべて
のバッファ上を循環して動きます。 NextVictimBuffer は、 BufFreelistLock
によって保護されます。

犠牲となるバッファを得るためのアルゴリズムは以下のようになります。

1. BufFreelistLock を獲得します。

2. フリーバッファリストが空でなければ、先頭のバッファを削除します。バッ
ファがピンされているか、あるいは利用カウンタが0でない場合は利用できませ
ん。それを無視してステップ2の先頭に戻ります。そうでなければ、バッファを
ピンして、 BufFreelistLock を解放します。バッファを返却します。

3. そうでなければ、 NextVictimBuffer が指しているバッファを選びます。そ
して循環的に NextVictimBuffer を進めます。

4. バッファがピンされているか、あるいは利用カウンタが0でない場合は利用
できません。(カウンタが0でなければ)利用カウンタをカウントダウンし、3に
戻って次のバッファを調べます。

5. 選択したバッファをピンして、 BufFreelistLock を解放し、バッファを返
却します。

(選択したバッファがダーティなら、再利用する前に書き出しを行います。他の
人がバッファをピンしていたら、そのバッファはあきらめて他のバッファを探
さなければなりません。しかし、これは犠牲バッファを選ぶアルゴリズムの基
本的な問題ではありません)。

バッファ・リング置き換え戦略

VACUUM や大量の順スキャンのように、一度だけ大量のページをアクセスする場
合には、別の戦略が使われます。そのようなスキャンが使用したページはすぐ
には利用されない可能性が高く、通常のクロックスィープアルゴリズムがバッ
ファキャッシュ全体を使い尽くすのでのではなくて、同じクロックスィープア
ルゴリズムを使う小さなリングバッファが用意され、スキャン全体でバッファ
の再利用のために使われます。これによって、そうしたSQLによって生じた書き
込みトラフィックの大部分が、そのバックエンド自身によって行われ、他のバッ
クエンドが行うことはありません。

順スキャンのために 256KB のリングバッファが使われます。これは L2キャッ
シュに充分収まる大きさで、OSのキャッシュから共有バッファへの転送が効率
的に行われます。もっと小さなバッファでも良いのですが、同時にピンされて
いるバッファをすべて収容できる大きさでなければなりません。256KBというの
は、同期順スキャン(synchronized sequential scan)に他のバックエンドが参
加できるほどの小さなキャッシュの軌跡を残すのに充分です。リングバッファ
がダーティになり、LSNが更新されたら、通常はバッファを再利用する前にWAL
を書きだし、フラッシュしなければなりません。この場合、代わりにバッファ
をリングから破棄して、(後で)通常のクロックスィープアルゴリズムを使って
置き換え対象を選びます。ですから、この戦略は読み込み専用のスキャンの場
合にもっともうまく動きます(あるいは、最悪でもヒントビットを更新するよう
な)。大量のUPDATEやDELETEのように、スキャン中にすべてのページを更新する
ようなスキャンでは、リング中のバッファは常にダーティになり、リング戦略
は実質的に通常の戦略にまで落ちてしまいます。

VACUUMは順スキャンのように256KBのリングを使います。ただし、ダーティペー
ジはリングからは取り除かれません。代わりに、バッファの再利用が必要な際
にWALがフラッシュされます。リングバッファ戦略が8.3で導入されるまでは、
VACUUMのバッファはフリーリストに送らていて、それは実質的には1バッファの
リングバッファだったので、大量のWALフラッシュが発生していました。WALフ
ラッシュの間隔で、VACUUMが256KBの更新を行う方が効率的です。

大量の書き込みはVACUUMと同様です。今のところ、これはCOPY INとCREATE
TABLE ASにだけ適用されます。(順スキャンUPDATEやDELETEが大量書き込み戦略
を採用するのも面白いかもしれません?)大量書き込みでは、16MBのリングを使
います(ただし、shared_buffers の1/8を超えない範囲で)これより小さいと、
WALのフラッシュのために、COPYのブロックが頻繁に起こることが分かっていま
す。バックグラウンド VACUUM が自身のWALフラッシュによって遅くなるのは構
いませんが、COPYではそれは起こって欲しくないので、バッファを多目に取っ
ています。

バックグラウンドライターの処理

バックグラウンドライターは近々に再利用されそうなページを書き出すように
設計されています。それによって、バックエンドの書込処理を軽減させます。
このために、 NextVictimBuffer(その位置は変更しません!) から、ダーティで
ピンされてなく、かつ正の利用カウンタを持たないバッファを探して前方に向
かって、循環的にスキャンします。そのようなバッファが見つかったら、ピン
を獲得、書きだし、バッファを解放します。

NextVictimBuffer の読み出しが原子的操作であると仮定できるのであれば、ラ
イターは書き出すバッファを探すために BufFreeListLock を取得する必要さえ
ありません。バッファヘッダのダーティビットをチェックする間だけスピンロッ
クが必要になるだけです。このような仮定が成り立たない場合でさえ、ライター
に必要なのは、バッファをスキャンする間ではなく、その変数の値を読み出す
間だけロックを取ることだけです(8.0と比較すると、このことが競合コストを
低減するのに多いに役だっています)。

チェックポイントの間、バックグラウンドライターの戦略は、すべてのダーティ
ページを(ピンされていようといまいと!)書き出すというものでなければなりま
せん。最初に書き出すページがバックエンドが自分でいずれ書き出さなければ
ならないページになるようにするために、同じように NextVictimBuffer から
スキャンを始めます。

バックグラウンドライターがバッファを書き出す間、バッファの内容に対して
共有ロックを取ります(ディスクにバッファを書き出す際には必ずそうします)。
これにより、ページイメージが一貫性を持ってディスクに転送されることを保
証します。1ビットか2ビットのヒントビットの更新が失われるかもしれません
が、それはバッファアクセスルールに書いた理由によって問題になりません。

8.4では、バックグラウンドライターは、リカバリが必要な場合に、リカバリモー
ド中に起動されます。書き出したチェックポイントは技術的にはリスタートポ
イントになる、という点を除き、通常と同じ処理を行います。

--
Tatsuo Ishii
SRA OSS, Inc. Japan
English: http://www.sraoss.co.jp/index_en.php
Japanese: http://www.sraoss.co.jp

pgsql-jp メーリングリストの案内