データベースの本を読んでまとめる作業のついでにブログに書いちゃいます。 読んでるのはこの本

データベースの基本がしっかりと書かれている有名な本。らしい。結構でかいです。 いきなり9章から始めます。

自分の理解は間違ってるかもしれません。あまり自信なし。

9章:Disks and Files

DBMSではデータをどうやって蓄えるか。ディスクマネージメント,バッファマネージメントなどの話.

■メモリー階層

(CPU )- キャッシュ - メインメモリ - 磁気ディスク - (テープ) アクセス:  速い→遅い 容量当たりの値段: 高い→安い 電源切ったら: データ消える→消えない(不揮発性)

DBMSを使うことで,データがメモリにあるのかディスクにあるのか,などを意識しなくてよくなる.
メモリだけでは全てのデータを格納しきれないから,ディスクが必要.

■磁気ディスク

いろいろな部分の名前がややこしい。図を見て理解する http://images.google.co.jp/images?gbv=2&hl=ja&q=disk+track+block+sector+platter&sa=N&start=20&ndsp=20

  • データはディスクブロックという単位でディスクに読み書きされる。ディスクブロックは連続したバイトの並び
  • これがトラックと呼ばれるプラッター上の輪っかに並ぶ(図参照).プラッターはハードディスク内の円盤上のやつで,両面にデータを持てる.
  • 同じ直径を持つトラックのセットをシリンダーという.(=シリンダーはプラッターの表面にトラックを持つ)
  • トラックは,セクターとよばれる固有の単位に分けられる.ディスクブロックは,セクターn個分と最初にサイズが決められる.
  • ディスクヘッドとは,データの読み書きのときブロックの頭に位置する.プラッターの両面の数だけ存在し,一体となって動く(図参照)
  • チェックサムは,セクターがおかしかったり読み込みに失敗したりするのをチェックするのに用いられる.
  • データを処理するには一度ディスクからメモリに置く必要がある。
  • I/Oは,たとえアイテム1つのためでもブロック単位で行われる.

・ディスクアクセスに要する時間とは,seek time + rotational delay + transfer time

  • seek time: ディスクヘッドが目的のブロックがある「トラックの位置」まで動くのにかかる時間。プラッタがでかいとその分かかる
  • rotational delay: ブロックがディスクヘッドのところに来るまで回ってくるのにかかる時間.平均で半周回る。seek timeより短い。
  • transfer time: データのブロックへの読み書きにかかる時間.

だから,読み書きにかかる時間を減らすには,データをディスクのどこに置くのか,というのが重要. 同時に読み書きされるものは,固めておいておくべき. データの近さは 同じブロック > 同じトラック > 同じシリンダ > 近いシリンダ

シーケンシャルに読み書きされるデータはシーケンシャルに置いておけ.

■データストライピングと冗長化

ストライピングするとI/Oが速くなって,冗長化すると信頼性が上がる. RAID: redundant arrays of independent disks

ストライピング

  • データを同じサイズに分割して複数のディスクに分散.このサイズをストライピングユニットという.
  • ラウンドロビンで分散.

冗長化

ディスクのMTTF(平均故障寿命)が5年で100枚ディスクがあれば21日に1つ壊れる. - 冗長化情報を持つことで,データの再構築ができる.冗長化情報はいくつかのディスクに置いておく - パリティ情報を蓄える RAIDではデータディスクとチェックディスクを作る.チェックディスクの数はRAIDレベルによる.

RAID0はパフォーマンスがあがるだけ.
RAID0+1はあまりストレージがいらないシステムや書込が多いアプリケーション向け
RAID2とRAID4はRAID3,RAID5に劣る
RAID3はまとまったブロックの読み書きが多い場合によい
RAID5はいろんな用途につかえる
RAID6はより信頼性が欲しいとき

■ディスクスペースマネージメント

  • ページ単位でデータを扱い,ディスクスペースの割り当て,解放,読み書きを行う.
  • ページの読み書きが一度のディスクI/Oに対応するため,ページの大きさはディスクブロックに等しく,ディスクブロックとして書き込まれる
  • ディスクスペースマネージャによって,これより上の層はハードのことは気にせずページの読み書きをやっていればよい
  • データの読み書きを繰り返していると,ディスクスペースにデータのない部分(holes)ができてしまう
  • フリーなブロックのリストを作るか,それぞれのブロックが使用かどうかのビットマップを持つかして,このfree blocksの管理をする.

・OSも連続したバイトをファイルとして扱うことができる

ファイルf の i バイト目を読む = ディスクd のシリンダーc のトラックt のブロックm を読む と対応させる. ディスクスペースマネージャはOSのファイルを使ってつくることができる.

多くのデータベースはそうしないで,ディスクスペースマネージャを自前で用意するか,OSの機能を拡張するかして実現する なぜなら,多くの環境で動くものにしたいから,自己完結するコードにしたい,32ビットシステムでは4GBまでのファイルサイズしか扱えない,ディスクをまたがってデータを扱いたい,などの理由がある.

■バッファマネージャ

必要な分だけディスクからメモリにデータを持ってくる.メモリ上(バッファプールと呼ばれる領域)をページ単位で区切って,ページを読み込んだりする.バッファプール内のページ単位のスロットをフレームという. これより上の層はページがメモリ上にあるかどうかを気にしなくていい.問い合わせ,返還,変更の通知 を行うだけ.

それぞれのフレームに対してdirtyとpin count という2つの変数を持つ.

  • dirty:ページに変更があったかどうか
  • pin count:最初0.その時のページのリクエストの数
  • ページリクエストがあると,まずはフレームから代わりに出て行って貰うモノを探し,pin countをふやす(pinning)
  • dirtyビットがonならディスクに書く
  • あけたところにページを読み込む
  • そのページを持つフレームのアドレスを返す
  • 解放されたらpin countを減らす(unpinning)
  • 修正したらunpinでdirty on
  • pin countが0でなければページはそのままフレームにとどまる
  • pin countが0のなかで,どのフレームを入れ替えるかはルールがある
  • 修正されていないもの:ディスクに書き込む必要がないからフレームに上書きできる
  • pin count =0 がないなら,待つか,トランザクションを禁止して割り当てる
  • 異なるトランザクション:衝突(不整合)を生み出すから,同時には割り当てない(排他的ロック)

・フレーム入れ替えルール

  • LRU: least recently used

pin count0のフレームへのポインタのキュー

  • clock: キューではなくて,時計のような円にフレームをみなし,pinが0のものはリファレンスビットが1になっている

時計の針のようなもので見ていく.pinが0でビットが1なら0にする.pinが0,ビットも0なら入れ替えへ.これは最近参照されたページはなるべく残すため

  • FIFOやmost recently used もある

■バッファマネージメント vs OS

バッファマネージメントとOSの仮想メモリは似てる なぜ仮想メモリを使わないかというと,DBMSは次に参照されるデータなどをある程度予測し,先に読み込んでおくといったことをやることで,より速くデータを用意でき,また同じページに対する参照をまとめることもできるので,仮想メモリより高速なデータの参照を実現できる.また,CPUも先にディスクI/Oを指示して次の仕事に回れる

また,ディスク上のページをメモリ上のページに同期させておきたい

■file of records

ファイル:ページのセット,コレクション ファイルの中には同じサイズのページが並び,レコードはそれぞれridを持つ ファイルに対しての作成と削除,レコードの挿入と削除,ridを指定したデータの取得,全てのデータのスキャン ができる

それぞれのファイルのページと空きスペースを含むページを把握する必要がある. ページはファイルの中での索引付けのために2つのポインタを記憶する必要がある.

■ページ管理手法

・線形リスト:双方向の線形リストとしてページを管理,全てのページのリストとフリースペースを持つページのリストの2つのリストを持つ. DBMSはヒープファイルの名前とそのヘッダファイルへのアドレスを記憶している.
新たなページが必要になる場合,ディスクスペースマネージャにリクエストして得たページをリストに追加する. 可変長のレコードの場合ほとんとのページがフリーリストに行ってしまうという欠点がある.

・ディレクトリ ページのコレクション(セット)がディレクトリで,それがリストを作る.ディレクトリのエントリはそれぞれがページを示す. DBMSはそれぞれのファイルの頭のディレクトリを把握している.
フリースペースの把握には,エントリ毎の空きスペースのあるなしのビット,あるいはフリースペースの量を示すカウントを保持する.

■ページフォーマット

ページはレコードを持つスロットのセット レコードはページのidとスロットナンバー(rid)で特定できる.

・固定長のレコード

固定長であればレコードのあるなしの管理だけ.あいてるところを探して新たなモノをいれる.あいてるスロットの管理が重要. 1つめの方法:前からつめていく.途中があいたら一番後ろのレコードをそこに移す.それぞれのレコードがオフセットで表現可能. 動いたレコードにアクセスがくるとよくない

・可変長のレコード

  • ページ内の空きスペースをつなげて連続させる.どうやってレコードを移動するかが大事.
  • ページ毎のスロットディレクトリ(レコードオフセットとレコードの長さ)を持つのがいい.
  • レコードオフセットはレコードへのポインタ.消すのはポインタを-1にする.
  • ページ内ではridは変わらないので自在に動かせる.
  • フリースペースの管理には,フリースペースの頭へのポインタを持つ.
  • スロットの途中が消えても,スロットナンバーの入れ替えが必要になるならそのままスロットディレクトリには残る.次にきたレコードに使う.

■レコードフォーマット

  • レコードも固定長と可変長で扱いが異なる.
  • どちらの場合もフィールド数は固定
  • フィールドの情報はシステムカタログに置いておく

固定長レコードの場合

  • 長さとフィールド数が固定
  • フィールドの長さから各フィールドへのアドレスが分かる

可変長レコードの場合

  • レコードフォーマットフィールド数は固定,いくつかが可変長のフィールド
  • フィールドをデリミタで区切る
  • レコードの頭にフィールドへのオフセット配列を持つ(レコード終端へのオフセットも入る)

オーバーヘッドがあるが後者の方がダイレクトにアクセスできるのでよい ヌルはスペースを使わない(2つのフィールドへのポインタが同じになる)