Buffer Pool を実装する。

この記事は「けんつの１人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar」 16 日目の記事です。

はじめに

どうも、最近 co shu nie*1 にめちゃくちゃハマっているけんつです。
「asphyxia piano ver」 がめっちゃいいので聴いてください。壊れそうなぐらい綺麗な透き通った声がめちゃくちゃ好きです。

www.youtube.com

今回はくそがつくほど苦戦した Buffer Pool の実装についてです。
もう解説するのが非常に厳しいので単純に紹介していきます。

普段は MySQL に寄せようと頑張って来ましたが、いよいよ資料がなさすぎてついに PostgreSQL のおそらく Ver 8.x 系の文献を参考にしています。
http://www.interdb.jp/pg/pgsql08.html

CMU の講義に拠らない感じのできになっています。

Buffer Pool の実装

Buffer Pool が持つべき責務を考える

これができなくてめちゃくちゃ苦戦した。というのも、この後に DB Storage 全体を管理する Storage Manager を実装するから
どこからどこまでを Buffer Pool の責務として保証するのかが微妙に噛み合わなくて苦戦した。

その上で、Storage Manager はメモリ上の Buffer Pool とディスク周りの処理を担保する Disk Manager を操作するメソッドをコールするだけ*2にしようということになった。

どういうことかというと、例えばページが Buffer Pool 上に存在しない場合ディスクから読み取る必要があるがこれは Buffer Pool と Disk Manager 両方の機能を必要とするため Buffer Pool で簡潔させるのではなく
Storage Manager に該当する双方の処理を呼ばせて実現することにした。

Buffer Pool 全体の仕様

Buffer Pool とさっきからいっているが実際は Buffer Manager であり、そいつが Buffer Pool を内包している。
全体的には以下のようになっている。

Hash Table は可変長の map[string]*BufferTag を使っている。ここでこの Hash Table 、 Buffer Descriptor が Clock Sweep を使って Descriptor を開放したらそれに対応する hash が開放されない実装もれがあることを思い出した。

Buffer Descriptor は Clock Sweep によって開放されるキャッシュライクなもので、固定長の配列をベースにしている。
Buffer Pool は単に Page 構造体の参照を配列でもっているだけ。

ここに出てくる固定長の配列は全て同じサイズで宣言されている。
基本的に Descriptor が持っているインデックスを参照して、 Buffer Pool 内の Page を取得するがこの時にどちらかがスライスだと、ハッシュテーブルからディスクリプタ、ディスクリプタからプールのどちらかの処理をインデックスベースで行う事が面倒になるので
すべて固定長としている。

またハッシュテーブルは uint64 の pageId と string の tableName から SHA1 を計算している。
それをキーとして Buffer Tag を見つけ、その buffer tag が持っているインデックスを元にページを参照することができるという仕組み。

Buffer Pool で持つ他の情報

Buffer Pool では他の DBMS がそうなっているようにインデックスを持っている。また今回これより重要となるのがカタログと言われるテーブル情報を格納している代物で SystemPage と呼ばれているが、PageId の管理などを行っている。
これによってテーブル毎に 0 スタートで一意な pageid を割り振れるようにしている。

構造体

type BufferManager struct {
        Table map[string]*BufferTag
        Descriptors *ClockSweep
        Pools [BufferPoolLimitSize]*Page
        SysPage map[string]*SystemPage
        Indexes map[string]*BTree
}

type BufferTag struct {
        TableName string
        PageId uint64
        Index int
}

type BufferDescriptor struct {
        Ref int
        Usage int
        Dirty bool
        Index int
        Mutex sync.RWMutex
}

Buffer Pool の操作

Append, Read Page だけコードを載せておくけどこんな感じになった。要リファクタリング。

func (b *BufferManager) AppendPage(tableName string, p *Page) {

        sys := b.ReadSystemPage(tableName)
        pageId := sys.MaxPageId + uint64(1)
        sys.MaxPageId = pageId
        sha := Hash(tableName, pageId)

        newDesc := NewBufferDescriptor()
        victim, index := b.Descriptors.AppendPage(newDesc)

        if victim != nil {
                b.Pools[victim.Index] = nil
        }

        b.Pools[index] = p
        newDesc.Index = index

        tag := NewBufferTag(tableName, pageId)
        tag.Index = index

        b.Table[sha] = tag
}

func (b *BufferManager) ReadPage(tableName string, pageId uint64) (*Page, *BufferDescriptor) {

        hash := Hash(tableName, pageId)

        t, exist := b.Table[hash]
        if exist {
                desc := b.Descriptors.GetDescriptor(t.Index)
                //desc.IncreaseRef()
                desc.IncreaseUsage()

                return b.Pools[desc.Index], desc
        }

        // if page is null, storage manager read page from disk
        return nil, nil
}

おわりに

ここから怒涛の勢いで Storage Manager を実装する

*1:正しくは Cö shu Nie

*2:API をイメージしている