buffer poolとか - mir the developer

buf0buf.cのソースファイル先頭コメントをとりあえず訳してみますた。たぶん理解不十分で誤訳してる個所もあるとおもいまふ。突っ込み大歓迎っす。以下、原文の引用および自分の訳文を載せます。

        Performance improvement: 
        ------------------------
Thread scheduling in NT may be so slow that the OS wait mechanism should
not be used even in waiting for disk reads to complete.
Rather, we should put waiting query threads to the queue of
waiting jobs, and let the OS thread do something useful while the i/o
is processed. In this way we could remove most OS thread switches in
an i/o-intensive benchmark like TPC-C.

A possibility is to put a user space thread library between the database
and NT. User space thread libraries might be very fast.

SQL Server 7.0 can be configured to use 'fibers' which are lightweight
threads in NT. These should be studied.

NT方式のスレッドスケジューリングは非常に遅く、OSの待機メカニズムはディスクの読み込み完了待ちの間であっても使うべきでありません。むしろ、我々はそのディスクの読み込み待ちをしているスレッドをジョブ待ちのキューに入れ、I/O処理中はOSのスレッドに何か他の有益なことをさせるべきです。この方法によってTPC-CのようなI/Oが重いベンチマークテストにおけるOSスレッドのコンテキストスイッチをほとんど無くすことができました。

他の可能性としては、RDBMSとNTの間のユーザ空間で動作するスレッドライブラリを使用することです。

SQL Server 7.0はNTにおける軽量スレッドである'fibers'を使うように設定することができます。これはぜひ調査すべきです。

        Buffer frames and blocks
        ------------------------
Following the terminology of Gray and Reuter, we call the memory
blocks where file pages are loaded buffer frames. For each buffer
frame there is a control block, or shortly, a block, in the buffer
control array. The control info which does not need to be stored
in the file along with the file page, resides in the control block.

GrayとReuterの用語に従い、ファイルのページがロードされるメモリブロックをバッファフレームと呼ぶことにします。各バッファフレームにつき、バッファを制御する配列の中に、制御ブロック、あるいはもっと短くいうとブロックというのが存在します。ファイルのページとともにファイルに格納される必要がない制御情報といったようなものが、この制御ブロックの中に存在します。

        Buffer pool struct
        ------------------
The buffer buf_pool contains a single mutex which protects all the
control data structures of the buf_pool. The content of a buffer frame is
protected by a separate read-write lock in its control block, though.
These locks can be locked and unlocked without owning the buf_pool mutex.
The OS events in the buf_pool struct can be waited for without owning the
buf_pool mutex.

buf_poolバッファはそれに含まれる全ての制御データのための構造体を保護するためのひとつのmutexを含んでいます。しかしながら、バッファフレームの中身は、制御ブロックの中で分かれているリード/ライトロックによって保護されています。buf_poolのmutexを所有することなく、 buf_pool構造体の中で発生するOSイベントを待つことができます。

The buf_pool mutex is a hot-spot in main memory, causing a lot of
memory bus traffic on multiprocessor systems when processors
alternately access the mutex. On our Pentium, the mutex is accessed
maybe every 10 microseconds. We gave up the solution to have mutexes
for each control block, for instance, because it seemed to be
complicated.

buf_poolのmutexは主記憶におけるホットスポットであり、マルチプロセッサシステムで複数プロセッサからmutexへ交互にアクセスが発生すると、大量のメモリバスのトラフィックが発生します。私たちが保有しているPentiumマシンでは、mutexはおよそ10マイクロ秒ごとに1回アクセスされています。このmutexを各制御ブロックに分割することは諦めました。というのも、これは非常に複雑に見えるからです。

A solution to reduce mutex contention of the buf_pool mutex is to
create a separate mutex for the page hash table. On Pentium,
accessing the hash table takes 2 microseconds, about half
of the total buf_pool mutex hold time.

buf_poolのmutexへの競合を減らすためには、各ページのハッシュページごとにmutexを分ける必要があります。Pentiumマシンでは、ハッシュテーブルへのアクセスには2マイクロ秒を要し、これはbuf_poolのmutexを保持する時間の約半分を占めています。

        Control blocks
        --------------

The control block contains, for instance, the bufferfix count
which is incremented when a thread wants a file page to be fixed
in a buffer frame. The bufferfix operation does not lock the
contents of the frame, however. For this purpose, the control
block contains a read-write lock.

例えば制御ブロックには、各スレッドがあるファイルのページをバッファフレームの中で修正したいというようなときにカウントアップされる bufferfixカウントというような情報が含まれています。しかし、このbufferfixの操作では、バッファフレームの中身に対してロックは行いません。この目的のために、制御ブロックはリード/ライトロックを含んでいます。

The buffer frames have to be aligned so that the start memory
address of a frame is divisible by the universal page size, which
is a power of two.

バッファフレームは整列に並んでいる必要があり、それによりバッファフレームの先頭アドレスはユニバーサルページサイズ（2の累乗）で割り切れる位置になっています。

We intend to make the buffer buf_pool size on-line reconfigurable,
that is, the buf_pool size can be changed without closing the database.
Then the database administarator may adjust it to be bigger
at night, for example. The control block array must
contain enough control blocks for the maximum buffer buf_pool size
which is used in the particular database.
If the buf_pool size is cut, we exploit the virtual memory mechanism of
the OS, and just refrain from using frames at high addresses. Then the OS
can swap them to disk.

buf_poolバッファは起動中にサイズの再設定を行えるようになっており、データベースを閉じることなくそのサイズを変更することができます。データベース管理者は例えば夜間にこのbuf_poolを大きくするとったようなことが可能です。制御ブロックの配列は、特定のデータベースで使用される buf_poolバッファの最大サイズに対して十分なだけの制御ブロックを含んでいる必要があります。but_poolのサイズが削減された場合には、 OSの仮想メモリ機構が活用され、高い位置のアドレスにあるバッファフレームの使用を控えるようになります。これによりOSはそれらをディスクにスワップできます。

The control blocks containing file pages are put to a hash table
according to the file address of the page.
We could speed up the access to an individual page by using
"pointer swizzling": we could replace the page references on
non-leaf index pages by direct pointers to the page, if it exists
in the buf_pool. We could make a separate hash table where we could
chain all the page references in non-leaf pages residing in the buf_pool,
using the page reference as the hash key,
and at the time of reading of a page update the pointers accordingly.
Drawbacks of this solution are added complexity and,
possibly, extra space required on non-leaf pages for memory pointers.
A simpler solution is just to speed up the hash table mechanism
in the database, using tables whose size is a power of 2.

ファイルのページを含んでいる制御ブロックは、ページのファイルアドレスに則って、ハッシュテーブルに追加されます。"pointer swizzling"(直訳：ポインタのがぶ飲み)を使うことによって、個々のページへのアクセス速度を向上させることができます。buf_poolの中にページへの直接のポインタが存在する場合には、それを使ってnon-leaf indexページ上にあるページへの参照を置換することができます。buf_poolの中に存在するnon-leafページの中のページへの参照を全てつなげることができる場所に、ページへの参照をハッシュのキーとして利用して、ページを読み込むタイミングで、複数に分割したハッシュテーブルを作成することができます。この方法の欠点は複雑さが増すことと、可能性としてメモリポインタのためのnon-leafページが必要とする領域が増加することです。各データベースにおいて、サイズが2の累乗であるようなテーブルによるハッシュテーブルメカニズムを高速化することが単純な解決策となります。

        Lists of blocks
        ---------------

There are several lists of control blocks. The free list contains
blocks which are currently not used.

制御ブロックのリストというのが複数存在します。フリーなリストは、現在使用されていないブロックを含んでいます。

The LRU-list contains all the blocks holding a file page
except those for which the bufferfix count is non-zero.
The pages are in the LRU list roughly in the order of the last
access to the page, so that the oldest pages are at the end of the
list. We also keep a pointer to near the end of the LRU list,
which we can use when we want to artificially age a page in the
buf_pool. This is used if we know that some page is not needed
again for some time: we insert the block right after the pointer,
causing it to be replaced sooner than would noramlly be the case.
Currently this aging mechanism is used for read-ahead mechanism
of pages, and it can also be used when there is a scan of a full
table which cannot fit in the memory. Putting the pages near the
of the LRU list, we make sure that most of the buf_pool stays in the
main memory, undisturbed.

LRUリストはbufferfixカウントが0ではないページ以外の全てのページに対するブロックを含んでいます。各ページはLRUリストのなかで、最後にアクセスした順番に従って大雑把に並んでおり、最も古いページはリストの最後尾にあります。またLRUリストの最後尾に近い位置にポインタを維持しており、buf_poolの中にあるページの世代管理の際にそれを使うことができます。これはあるページがしばらくの間必要とされていないということが分かったときに使用されます。そのとき、ポインタの位置のすぐ後ろにブロックを追加し、すばやく置き換えされるようにしています。現在このagingメカニズムはページのread-aheadメカニズムのために使用されています。またこれはメモリに収まりきらないようなテーブルのフルスキャンの際にも使用されます。ページをLRUリストの近くに置くことで、ほとんどのbuf_poolを主記憶に置いたままにし、その影響を受けないようにすることができます。

The chain of modified blocks contains the blocks
holding file pages that have been modified in the memory
but not written to disk yet. The block with the oldest modification
which has not yet been written to disk is at the end of the chain.

修正されたブロックのチェインは、メモリ上では修正されているもののディスク上にはまだ書かれていないファイルのページを保有しているブロックを含んでいます。ディスクにまだ書き込まれていないものの中で最も古い修正情報を持つブロックは、チェインの一番最後にあります。

        Loading a file page
        -------------------

First, a victim block for replacement has to be found in the
buf_pool. It is taken from the free list or searched for from the
end of the LRU-list. An exclusive lock is reserved for the frame,
the io_fix field is set in the block fixing the block in buf_pool,
and the io-operation for loading the page is queued. The io-handler thread
releases the X-lock on the frame and resets the io_fix field
when the io operation completes.

最初に、置き換えの対象となるブロックをbuf_poolから見つける必要があります。フリーリストから選ばれるか、あるいはLRUリストの最後から探し出されます。排他ロックがフレームに対して獲得され、buf_poolの中にあるブロックを修正するブロックの中で、io_fixフィールドがセットされ、ページを読み込むためのio操作がキューに追加されます。ioハンドラスレッドはフレームの排他ロックを開放し、io操作が完了した時にio_fix フィールドをリセットします。

A thread may request the above operation using the buf_page_get-
function. It may then continue to request a lock on the frame.
The lock is granted when the io-handler releases the x-lock.

スレッドはbuf_page_get-関数を使用して上記の操作を要求します。その後、フレームに対してロックを要求することができます。ioハンドラが排他ロックを開放した後に、ロックが許可されます。

        Read-ahead
        ----------

The read-ahead mechanism is intended to be intelligent and
isolated from the semantically higher levels of the database
index management. From the higher level we only need the
information if a file page has a natural successor or
predecessor page. On the leaf level of a B-tree index,
these are the next and previous pages in the natural
order of the pages.

先読みのメカニズムは、データベースのインデックス管理のための高水準なセマンティクスから独立し、インテリジェントであることを意図しています。高水準なレベルでは、ファイルページが後方に続くページを持つのか、前方に続くページを持つのかといった情報のみ必要とします。B-treeインデックスのリーフレベルでは順序付けられたページの中に、継続する、あるいは先立つページが存在します。

Let us first explain the read-ahead mechanism when the leafs
of a B-tree are scanned in an ascending or descending order.
When a read page is the first time referenced in the buf_pool,
the buffer manager checks if it is at the border of a so-called
linear read-ahead area. The tablespace is divided into these
areas of size 64 blocks, for example. So if the page is at the
border of such an area, the read-ahead mechanism checks if
all the other blocks in the area have been accessed in an
ascending or descending order. If this is the case, the system
looks at the natural successor or predecessor of the page,
checks if that is at the border of another area, and in this case
issues read-requests for all the pages in that area. Maybe
we could relax the condition that all the pages in the area
have to be accessed: if data is deleted from a table, there may
appear holes of unused pages in the area.

最初に、B-treeのリーフが昇順ないし降順でスキャンされる時の先読みのメカニズムについて説明しましょう。読み込み対象のページがbuf_pool の中で初めて参照されるような場合では、バッファマネージャはページが直線的な先読み領域の境界線上にあるのかどうかを確認します。例えば、テーブルスペースはこのための領域として64個のブロックに分割されます。従って、ページがこの領域の境界線上にある場合には、先読みメカニズムは、同じ領域内のすべてのブロックに対して、昇順ないし降順の並びによるアクセスを行うのか否かを確認します。これに該当する場合には、システムは継続／先行するページに対して、そのページが領域の境界線上にあるのかどうかを確認し、その場合にはその領域内にあるすべてのページに対する読み込み要求を行います。もしかすると、同一領域内のすべてのページに対してアクセスが必要という条件を緩和することは可能かもしれません。テーブルからデータが削除された場合、領域内には使用されていないページの穴が出現する可能性があります。

A different read-ahead mechanism is used when there appears
to be a random access pattern to a file.
If a new page is referenced in the buf_pool, and several pages
of its random access area (for instance, 32 consecutive pages
in a tablespace) have recently been referenced, we may predict
that the whole area may be needed in the near future, and issue
the read requests for the whole area.！

別の先読みメカニズムは、ファイルに対してランダムなアクセスパターンが現れたときに使用されます。buf_pool内で新しいページが参照される場合、そしてランダムアクセス領域（例えばテーブルスペース内の32個の連続したページ）のいくつかのページが最近参照されたばかりであるような場合、すべての領域が近い将来必要とされるであろうと予測し、すべての領域に対して読み込み要求を出すかもしれません！

        AWE implementation
        ------------------

By a 'block' we mean the buffer header of type buf_block_t. By a 'page'
we mean the physical 16 kB memory area allocated from RAM for that block.
By a 'frame' we mean a 16 kB area in the virtual address space of the
process, in the frame_mem of buf_pool.

'block'(ブロック)とはbuf_block_t型のバッファのヘッダのことを意味しています。'page'(ページ)とは、そのブロックのために RAMから割り当てる16KBの物理メモリを意味しています。'frame'(フレーム)はbuf_poolのframe_menにある16KBの仮想アドレス空間を意味してます。

We can map pages to the frames of the buffer pool.

1) A buffer block allocated to use as a non-data page, e.g., to the lock
table, is always mapped to a frame.
2) A bufferfixed or io-fixed data page is always mapped to a frame.
3) When we need to map a block to frame, we look from the list
awe_LRU_free_mapped and try to unmap its last block, but note that
bufferfixed or io-fixed pages cannot be unmapped.
4) For every frame in the buffer pool there is always a block whose page is
mapped to it. When we create the buffer pool, we map the first elements
in the free list to the frames.
5) When we have AWE enabled, we disable adaptive hash indexes.

ページはバッファプールのフレームにマップすることができます。

1. バッファブロックはデータ以外に用いられるページとして使用するために割り当てられます。例えばロックテーブルは常にフレームにマップされます。
2. bufferfixedおよびio-fixedデータページは常にフレームにマップされます。
3. ブロックをフレームにマップする必要がある場合には、awe_LRU_free_mappedリストの中から最後のブロックをマップ解除しようとしますが、bufferfixexあるいはio-fixedページはマップ解除されることはありません。
4. バッファプール内の全てのフレームに対して、それぞれのページが各フレームにマップされるようなブロックが常に存在します。
5. AWEが有効となっている場合には、適合ハッシュインデックスは無効化されます。

※補足･･･AWE(Adress Windows Extention)はWindows on IA-32で4GB以上のメモリ空間を扱うための仕組みです。