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 をイメージしている

B Tree Index を実装する

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

はじめに

どうも、最近眼精疲労がひどすぎるけど眼球ってどうやって休めたらいいかわからないけんつです。

今日明日は現状最も苦戦した B Tree Index と Buffer Pool の実装話になります。

B Tree を実装する

今回は B+ Tree でなく B Tree を実装する。また削除は考慮しない。
完全に考慮しない訳ではなくて一応削除を実装することを考慮はしている。ただ物理削除ではなく論理削除としている。
というのもなぜかと言うと、B Tree のなかで最もコストの高い動作が発生するのが物理削除であるという理由から。

どのように論理削除するというとフラグを立てて探索をスキップするという単純なものを実装している。

インデックスの色々

インデックスと言っても色々あってここではその話をする。あくまでも MySQL が前提。

クラスタインデックス

MySQL のインデックスには２種類あってクラスタインデックスとセカンダリインデックスというものが存在する。クラスタインデックスは雑に言うと主キーで構成されたインデックスで暗黙的に構築される。 PK が定義されていないなら全てのカラムから NOT NULL な UNIQUE インデックスを最初に検索し、それを元に構成する。それすらもない場合は InnoDB が内部的に行に自動で付与されるインクリメントカラムを追加しその値で構成する。

セカンダリインデックス

クラスタインデックス以外のインデックスを全てセカンダリインデックスと呼ぶ。これは特定のカラムに貼るものと思って間違いは無いはず。
そして実際にセカンダリインデックスとクラスタインデックスがどのように関連しているかというと、セカンダリインデックスで探索するものは主キー、つまりクラスタインデックスであることが多く
セカンダリインデックスで探すべき主キーを見つけ、そのあとクラスタインデックスを探索してその主キーに紐付いている行を見つけている。
しかし、セカンダリインデックスに必要な情報が全て格納されていれば、クラスタインデックスによる探索をスキップできるため高速に動作させることができる。

B Tree アルゴリズム

「B Tree 実装」とかってググるとなぜか MySQL のインデックスなどが引っかかってきてハイパーわかりにくかったのでアルゴリズムの手順的なものは以下のスライドを参考にした。

speakerdeck.com

これを見れば大体行ける。
そして、以下のデモサイトを見ると困った時に B Tree がどのように処理を行っていくかが試せるからすごく良かった。
www.cs.usfca.edu

実装方針

• B+ Tree ではなく B Tree
• 物理削除は実装しない
• 数値と文字列*1に対応させる
• クラスタインデックスとしての利用を想定

実装するにあたっての知見・感想

アイテムの閾値

ノードが最大何個までアイテムを持つかという値を決める必要があるが、これは間違いなく奇数がいい。
なぜかというと、閾値を 3 にした場合を例に説明するならばノードが持つアイテムが３つになった段階で最大値・最小値を2番目のアイテムの子ノードにする必要があるから。
偶数にする場合はまた何かしら別に処理する必要があるっぽいが単純に面倒くさいので 3, 5, 7 あたりの真ん中の値が一意に求まるものにすると実装しやすい。

ラッチの実装

CMU の講義でも言われているが、ノードを探索、追加、更新する場合にはラッチを利用するのがよいと言われている。
例えば探索なら、まずルートノードのロック*2をとり、探索する前に子ノードのロックも確保する。
ルートノードの探索が終わったら、ロックを開放して子ノードの更に子ノードのロックを取得する、というプロセスを値が見つかるまで繰り返す。

今回は Github の PR でもわかる通り、今回はラッチをノードレベルではなくインデックスのツリー構造単位でかけている。
これはめちゃくちゃパフォーマンスが悪いのは知っているけど、↑のようにロックをノードレベルで取得がめちゃくちゃめんどくさくて*3 そうなってしまった。

Golang の interface を上手く使う

ノードが保持するアイテムを Item という以下の interface として宣言している

type Item interface {
        Less(itm Item) bool
        Equal(itm Item) bool
        IsSkip() bool
}

そのため B Tree で使うデータ型は上記のメソッドを実装していればいいから、データ型によって異なる大小比較とかが抽象化できて
B Tree 自体のコードがあまり複雑にならなかった。
データ型の宣言は以下の様になっている。

package storage


type IntItem struct {
        Value int32
        Delete bool
}
type StringItem struct {
        Value string
        Delete bool
}

type Item interface {
        Less(itm Item) bool
        Equal(itm Item) bool
        IsSkip() bool
}

func (i IntItem) Less(itm Item) bool {
        v, ok := itm.(IntItem)
        if !ok {
                return false
        }

        return i.Value < v.Value
}

func (i IntItem) Equal(itm Item) bool {
        v, ok := itm.(IntItem)
        if !ok {
                return false
        }
        return i.Value == v.Value
}

func (i IntItem) IsSkip() bool {
        return i.Delete
}

func (s StringItem) Less(itm Item) bool {
        v, ok := itm.(StringItem)
        if !ok {
                return false
        }
        return s.Value < v.Value
}

func (s StringItem) Equal(itm Item) bool {
        v, ok := itm.(StringItem)
        if !ok {
                return false
        }
        return s.Value == v.Value
}

func (s StringItem) IsSkip() bool {
        return s.Delete
}

B Tree の実装

もう解説がめんどくさくなったので、これは本当に自信が無いが*4 コード載せて終わりとする

package storage

import (
        "sort"
        "sync"
)

const (
        MergeThreshold = 3
)

type Items []Item

type Node struct {
        Items Items
        Children []*Node
}

type BTree struct {
        Top *Node
        Mutex sync.RWMutex
}

func NewBTree() *BTree {
        return &BTree{
                Top: nil,
                Mutex: sync.RWMutex{},
        }
}

func (b *BTree) Insert(item Item) {

        b.Mutex.Lock()
        defer b.Mutex.Unlock()

        if b.Top == nil {
                node := new(Node)
                node.Items.InsertAt(item, 0)
                b.Top = node
        } else {
                b.Top.Insert(item)
        }
}

func (n *Node) Insert(item Item) {

        _, index := n.Items.Find(item)

        if len(n.Children) == 0 {

                n.Items.InsertAt(item, index)

                if len(n.Items) == MergeThreshold {
                        n.Split()
                }
                return
        }

        if len(n.Children[index].Items) == MergeThreshold - 1 {
                n.SplitChildren(item, index)

                if len(n.Items) == MergeThreshold {
                        n.Split()
                }
                return
        }

        n.Children[index].Insert(item)
}

func (n *Node) SplitChildren(item Item, index int) {

        _, i := n.Children[index].Items.Find(item)
        n.Children[index].Items.InsertAt(item, i)

        leftItem := n.Children[index].Items[MergeThreshold/2-1]
        middleItem := n.Children[index].Items[MergeThreshold/2]
        rightItem := n.Children[index].Items[MergeThreshold/2+1]

        n.Children = append(n.Children[:index], n.Children[index+1:]...)

        _, middleIndex := n.Items.Find(middleItem)
        n.Items.InsertAt(middleItem, middleIndex)

        leftNode := new(Node)
        rightNode := new(Node)

        leftNode.Insert(leftItem)
        rightNode.Insert(rightItem)

        n.Children = append(n.Children, leftNode)
        n.Children = append(n.Children, rightNode)

        sort.Slice(n.Children, func(i, j int) bool {
                return n.Children[i].Items[0].Less(n.Children[j].Items[0])
        })

}

func (n *Node) Split() {

        left := new(Node)
        middle := n.Items[MergeThreshold/2]
        right := new(Node)

        left.Items.InsertAt(n.Items[MergeThreshold/2-1], 0)
        right.Items.InsertAt(n.Items[MergeThreshold/2+1], 0)
        n.Items = append([]Item{}, middle)

        if len(n.Children) == MergeThreshold + 1 {

                var nodes []*Node

                left.Children = append(left.Children, []*Node{n.Children[0], n.Children[1]}...)
                right.Children = append(right.Children, []*Node{n.Children[2], n.Children[3]}...)

                nodes = append(nodes, left)
                nodes = append(nodes, right)
                n.Children = nodes
                return
        }

        n.Children = append(n.Children, left)
        n.Children = append(n.Children, right)
}

func (b *BTree) Find(item Item) (bool, int) {

        b.Mutex.RLock()
        defer b.Mutex.RUnlock()

        if b.Top == nil {
                return false, -1
        }

        return b.Top.Find(item)
}

func (n *Node) Find(item Item) (bool, int) {
        ok, index := n.Items.Find(item)
        if ok {
                return ok, index
        }

        if len(n.Children) == 0 {
                return false, -1
        }

        return n.Children[index].Find(item)
}

func (i *Items) Find(item Item) (bool, int) {
        for index,itm := range *i {

                if itm.IsSkip() {
                        continue
                }

                if itm.Equal(item) {
                        return true, index
                }

                if !itm.Less(item) {
                        return false, index
                }

        }
        return false, len(*i)
}

func (i *Items) InsertAt(item Item, index int) {
        *i = append(*i, nil)
        if index < len(*i) {
                copy((*i)[index+1:], (*i)[index:])
        }
        (*i)[index] = item
}

func (b *BTree) Get(item Item) Item {

        b.Mutex.RLock()
        defer b.Mutex.RUnlock()

        if b.Top == nil {
                return nil
        }

        return b.Top.Get(item)
}

func (n *Node) Get(item Item) Item {
        found, i := n.Items.Find(item)
        if found {
                return n.Items[i]
        } else if len(n.Children) > 0 {
                return n.Children[i].Get(item)
        }
        return nil
}

終わりに

次は、インデックスより苦戦した Buffer Pool について

*1:文字列は辞書順で比較

*2:ここでいうロックとは同時実行制御のロックではなくマルチスレッドの排他処理のロックをイメージして欲しい

*3:INSERT, UPDATE 時のような更新、追加処理のラッチはもっと面倒くさい

*4:テストが本当の正常系しか担保できていない

Clock Sweep と LRU Cache を実装する

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

はじめに

どうも、最近遊戯王が netflix で配信されていてめちゃくちゃ幼少期を思い出しているけんつです。

今回は Buffer Pool に関連して、キャッシュ周りの実装を進めていく。

DBMSのキャッシュ

これは MySQL と PostgreSQL でかなり違いがある。
少し前に記事でもまとめたが、MySQL は LRU で PostgreSQL はクロックスイープを使っている。

MySQL の LRU キャッシュ

MySQL では List 構造を２つ持っていて、LRU 全体サイズの 5/8 が New List、3/8 が Old List となっている。
最初に要素が LRU キャッシュに追加されるときは Old List に追加され、再度参照されることで New List に移動される。
これによって追加されて以降参照されていない要素を優先的に開放する仕組みが構築される。

PostgreSQL の Clock Sweep

こちらはクロックスイープで実装されている。
クロックスイープではそれぞれの要素が参照された総数を持っている。リストがいっぱいになった場合、この参照回数をそれぞれ１ずつ減算し、0 になったものを開放するという仕組みを取っている。

実装

とりあえず両方とも実装してみた。

LRU

LRU は要素に key, value のセットを持つようにしている。

type Lru struct {
        Size int
        NewSublist LruCache
        OldSublist LruCache
        Mutex sync.RWMutex
}

type Entry struct {
        Key interface{}
        Value interface{}
}

type LruCache []Entry

この構造体とデータ型を宣言している。
LRU に対する要素の追加と取得は次のように実装している。

func (l *Lru) Append(key interface{}, value interface{}) {

        if OldSublistSizeLimit < len(l.OldSublist) {
                l.OldSublist.RemoveOldest()
        }

        l.OldSublist.Append(key, value)
}

func (l *Lru) Get(key interface{}) interface{} {
        e := l.NewSublist.Get(key)
        if e != nil {
                return e.Value
        }

        e = l.OldSublist.Get(key)
        if e != nil {

                if NewSublistSizeLimit < len(l.NewSublist) {
                        l.NewSublist.RemoveOldest()
                }

                l.NewSublist.Append(key, e.Value)
                l.OldSublist.RemoveFirst()
                return e.Value
        }

        return nil
}

それぞれのリストに対する一番最後に参照された要素を削除するコードは雑に次のようになっている。

func (l *LruCache) MoveToFront(index int) {
        e := (*l)[index]
        *l = append((*l)[:index], (*l)[index+1:]...)
        *l = append(LruCache{e}, (*l)[0:]...)
}

// fix return value
func (l *LruCache) RemoveOldest() *Entry {
        e := l.Last()
        *l = (*l)[:len(*l)-1]
        return e
}

// fix return value
func (l *LruCache) RemoveFirst() *Entry {
        e := l.First()
        *l = (*l)[1:]

        return e
}

今回実装した LRU キャッシュはサブリストを２つ保持するようになっているからすこし Append 周りが複雑になってしまった。

Clock Sweep

クロックスイープは以下のような構造体として宣言されている。

type ClockSweep struct {
        Cap int
        Cache Clocks
}

type Clocks [BufferPoolLimitSize]*BufferDescriptor

ここで登場する BufferDescripor とは明日紹介する BufferPool において、ページの情報や Pin/Referrence Counter などを持っている構造体のこと。
今回実装する Clock Sweep では基本的に固定長の配列を構造体で保持していて、空きスロットに追加していく形となる。

スロットを開放する必要がある場合は、Usage を１ずつ減算していく。ただしこの時参照カウンタが1以上の場合は探索をスキップする必要がある。

おわりに

LRU, Clock Sweep の実装はこれにて終わり。
結構使いやすいデータ構造がなくて作るはめになってしまったけど、おそらく Clock Sweep の方が実装が簡単なので
それをベースに Buffer Pool のキャッシュを作れるとよさそう。

Page を実装する

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

はじめに

どうも、なんかブログ記事を書きまくってたら右手親指の付け根が痛くてたまらないけんつです。
今日は Page の実装に関する話です。

BufferPool あたりの実装が完了した段階で思ったことなどなど書いていきます。

Page の実装

基本的に Page Header と Tuple の塊となっている。
先頭 4byte を Page Header として、残りの領域で Tuple を追加された順番で保持する単純な構造になっている。
全体の容量は約 16 KB で固定。mmap は使用しない。

バイナリへのシリアライズなどなどは、前回実装したタプルのシリアライズをそのまま使う。
というのも、Page Header が今のところ 4 byte しかなく、あとはタプルが列挙するだけどとわかっているからバイナリにシリアライズするのは比較的簡単にできるようになっている。

また、ページは単にテーブル毎のディレクトリに格納されているだけでヒープや単方向リストを使って参照を持っているわけではない。

削除を考慮しない

削除を考慮しないのであれば、ただタプルを列挙すればいいだけとなる。
しかし、これで削除を考えようとすると一気に考えることが多くなる。

というのも、テーブル単位でそれぞれページを複数もっているが、タプルが追加されるだけとわかっていれば既に存在しているページを探索して空きスロットを探すとかしなくても良いため。

もしも削除を考慮するとするなら、同時実行制御をどのように実装するかを考える必要がある。
というのも、仮にデータを追加・更新する際に、PostgreSQL のように追記型を採用しているなら単にページを追加していき、タプルを末尾に追加すればいいだけとなる。削除なら単に論理削除すればいいだけなのでそこまで難しくない。

しかし MySQL の様に、更新型を取る場合は削除を考慮すると空きスロットが発生する可能性がある。
これを単にタプルを並べただけの構造から見つけ出すのは明らかにコストとなる。

これは CMU の講義のなかでも触れられている。
それらの問題を解決するために Slotted Page や Log-Structured File Organization などがある。
今回はそういった実装を現段階ではしないこととしている。

番外

特にタプルとページは愚直に実装したので特に話すことがない。
だから少しだけ Golang でこまった配列、スライス周りの話をする。

これら固定長のページやタプルを実現するために、固定長の配列を基本的には使用している。
例えばページを扱う構造体はこうなっている。

// Max Size: 16KB
type Page struct {
        Header PageHeader // 4byte
        Tuples [PageBodySize]Tuple // 128 byte per Tuple
}

そう、ここから固定長にしている。
ただこれの問題は色々あって、この配列を扱う場合はその関数やメソッドの引数や戻り値の型を全て固定長にしないといけない。
そのため、スライスで扱ったあり配列として扱ったりとかなり処理が忙しないことになっている。

Golang, 排他制御とかめちゃくちゃ便利なのに配列、スライスまわりとリスト、循環リストなど
データ構造に関わる部分が柔軟でないから少し実装にこまるときがある。
これは Clock Sweep の実装と、 Buffer Pool の実装でも同様に頭を悩ませた。

おわりに

次は Clock Sweep だったかな、そろそろメモリ上でページやタプルを管理する話になる。

Tuple を実装する

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

はじめに

どうも、最近バイトに卒研にアドカレと目を酷使しまくっていつも目が充血しているけんつです。眼球ってどうやって休ませたらいいんでしょうか。
そろそろ結構勉強だけという状況に飽きてきたので、ストレージから実装していきます。
まずは Tuple です。
行を表現するため本来であれば色々考慮する必要がありますが、比較的妥協を重ねてシンプルにしています。

実装

といっても、github で Pull Request を作りながら開発しているのでそちらを見ると全体像が見えてきます。
なのでここでは実装していて色々と考えたこと、妥協したことなどまとめます。

タプルの構成

Tuple は次の様に構成されます。

name	length
Magic Number	2byte
MinTxId	8byte
MaxTxId	8byte
Len	2byte
Tuple Body	var-length
total	128byte

Tuple Body

name	length
Magic Number	2byte
Data Type	2byte
Data Size	4byte
Data	var-length

コード上では以下の通りです。

type Tuple struct {
        Magic uint16
        MinTxId uint64
        MaxTxId uint64
        Len uint16
        Body [TupleBodySize]TupleData // TODO: fix length
}

type TupleData struct {
        Magic uint16
        Type uint16
        Size uint32
        Number int32
        String_ string
}

先行事例では、この部分は Protocol Buffer を使用していましたが、 TableSpace などでまとめて管理したい場合に
Protocol Buffer にまかせてしまうとかゆいところに手が届かなかったので
バイナリへのシリアライズは自作して byte 列に直しています。

gob をつかえばよいという声もあるかもしれませんが、あれはバイナリを構造体に変換するための情報もバイナリにシリアライズされるため 128 byte という固定長が困難と判断して使用しませんでした。

データ型の扱い

今回、自作する DBMS では int32 相当の int 型と varchar or text 相当の string 型があります。
これらは interface{} 型で扱ってしまうと gob を使うしかバイナリにシリアライズする方法がなくなってしまうので
TupleData 構造体でデータ型の分だけ専用にフィールドを持っています。

CMU の講義内では浮動小数点数の記載もありますがあれを実現しようとすると IEE754 あたりに準拠させる必要があるので今回はシンプルに実装できる文字列と整数としています。

タプルサイズ問題

これは完全に妥協点です。
タプルを固定長にしたせいで、構造体⇔バイナリの変換が複雑になってしまったために実際に保持できるデータは 70 ~ 80 byte 程しかないはずです。
これは明日まとめる Page の構成に大きく関係しているのでその時にまたまとめますが、1 Page = 16 KB という容量制限を確実に設けるために妥協しました。

おわりに

今回は複雑な処理の割にシンプルなタプルになったのでここまでです。
明日はページについて書きます。

ストレージ周りの設計を考える

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

はじめに

どうも、最近書き溜めた記事がなくなってきてエクストリーム開発になりそうであせっているけんつです。
今日はとりあえず、雑にストレージの全体構造を考えてみようかなと思っています。

詳細は、それぞれ実装した記事で書くのでかなり短くなりそう。

ストレージの設計を考える

ひとまずデータベースストレージから作っていくことにしたのでザッと設計を考えていく。
ただあくまでもこうやって実装したいなという目安なので今後変更する部分はありそう。

実装する DBMS の仕様

まず先に大まかな仕様から考える。
今回は次のような限定的な仕様とする。

• SQL はCREATE, SELECT, INSERT の単純なもののみで削除などは考慮しない
• 複数のクライアントからの接続を想定する
• データ型は int32 相当の整数型と、文字列型の２つのみ
• 各行はタプルのヘッダーなどを考慮しても 128 byte まで
• 1 Page = 16 KB とする
• 各行の先頭には必ず整数型の PK が存在する
• PK には B Tree を使ってクラスタインデックスを貼る
• タプルは固定長で、 128 byte 未満でもバイナリファイルになる場合に必ず 128 byte となる

ストレージの全体像を考える

現状は次のように実装することを考える。

メモリ上の処理

今のところはメモリ上に置くものはバッファプールのみとしている。
これが同時実行制御を考慮し始め MySQL のような更新型を取る場合はチェンジバッファや、ロックも Two-Phase Locking などを採用する場合は
それ単体では ACID 特性を満たすのに不十分なことからログバッファを追加して、 WAL を実装する可能性も考慮している。

また図中にはないがこのバッファプールには、インデックスを保持する領域も存在している。

ディスク上の処理

基本的にデータを最大 16 KB のページとして保持することを考える。テーブルはページをひとつ以上保持することで実現する。
またテーブルには 128 byte が上限のタプルを 127 個最大で配置する。*1
ページはバイナリにシリアライズして保持するが、それは Protocol Buffer を利用するのではなく気合で byte 列にすることまずやってみる。
gob は事前にシリアライズをテストしていて、構造体を素直にシリアライズするとデシリアライズするために必要なデータとして 280 byte ほど容量が増えるため使用しない。

これらのディスク上に永続化する必要があるものは DiskManager のような何かを用いて行うが、出来るなら Direct I/O を使いながらやってみたい。

おわりに

これ、実はいくつかもう実装しているけど詳しいことはそれぞれのパートで書くことにする。
ここにまとめるには要素が多い。あと、DBMSってストレージがほとんどな気がしてきた。

*1:ページヘッダーを考慮するとタプルの最大数を127にする必要がありそう

BufferPool の実例を調べる

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

はじめに

どうも、最近 B Tree Index を実装しても、重複ありで範囲検索するのめっちゃ難しくない？って思い始めたけんつです。
インデックスにとりつかれている気がする。

今日は、 Buffer Pools を実装しているなかでどうやって設計すると良いのか迷ったので PostgreSQL の Buffer Pool の仕組みを追うことでもうちょい理解を深めていこうかなと思っています。
使えそうな部分を重点的に列挙していくので短くなりそうです。

Buffer Pool

参考資料↓
http://www.interdb.jp/pg/pgsql08.html
(ぽすぐれって内部仕様の詳細ドキュメントが充実してていいよね)

そもそも Buffer Pool ってなんぞというところから始めると、Buffer Pool はストレージエンジンが担保していることが多いが
ストレージ的な機能を提供するのではなく物理的なストレージのデータをメモリ上に展開したり、データが追加された際に一時的に保持するためのメモリ領域のことを指す。
言わばファイルキャッシュのようなもので、更に平たくいうなら単にキャッシュと思ってもらっても差し支えないと思う。

実際以下のような構図になっている。

ここでいうところの Backend Process とはマルチスレッドでそれぞれ動作する SQL の解析や実行計画の決定、最適化よりユーザ側の面の全てを指す。

それでは順を追ってみていく。

Buffer Pool Manager の構成

バッファプールを管理するバッファプールマネージャーはバッファテーブル、バッファディスクリプタ、バッファプールから構成されている。
このあたりの詳しい解説はこのあとまとめる。
ここでまず大事なのはバッファプールは配列であり、各スロットに 1 page が配置されるようになっているということである。そして、その配列のインデックスを buffer_id と呼ぶこと。
これが、バッファプールマネージャを通したバッファプールの扱いに関連している。

バックエンドプロセスによるバッファプールの操作

バッファプールのデータを扱う場合に、以下のプロセスを踏む。

• テーブルやインデックスを読み込む場合、バックエンドプロセスはページの buffer_tag をバッファプールマネージャに渡す。
• バッファプールマネージャは既にページがバッファプールに存在する場合はそのインデックス*1を返す。バッファプールに存在しない場合はストレージから読みだしてバッファプールに対象のページを格納した上でそのインデックスを返す。
• バックエンドプロセスは buffer_id を利用して、バッファプールにアクセスする。

データの読み込みではなく、書き込みが走った場合はそのページをダーティページ*2として認識する必要がある。

また、読み込む際に空きスロットがない場合は LRU ではなくクロックスイープを使用してスロットを開放する。

バッファプールマネージャの構造

バッファプールマネージャは以下の構造をとる。

ポイントは以下の通り。

• Buffer Pool は配列であり、各スロットにページデータを持つ。また Buffer Pool のインデックスを buffer_id という。
• Buffer Descriptor は配列であり、 Buffer Pool の buffer_id と同一の*3 buffer_id で参照できる。この Descriptor はページのメタデータを保持する。
• Buffer Table は格納された buffer_tag と、 Buffer Descriptor の buffer_id とを対応付けるハッシュテーブルとなっている

Buffer Table

バッファテーブルはハッシュ関数、ハッシュスロット、データエントリの３要素で構成されている。
ここでは、まずハッシュ関数を使って buffer_tag をハッシュスロットにマッピングする。またハッシュを使用するということは当然ハッシュが衝突する可能性があるがバッファテーブルはそのような状態を単方向リストを使用したチェーン方式で解決する。
具体的に何をするかというと、以下の図がわかりやすい。

このように、同じハッシュスロットを用いる場合、それらを単方向リストとして表現する。

データエントリはページのバッファタグと、メタデータを持つ buffer_id の２つから構成されている。

Buffer Descriptor

バッファディスクリプタはページのメタデータを保持している。PostgreSQL では次のフィールドから構成される。

• tag: Buffer Tag を持つ
• buffer_id: 前述の通り
• refcount: ディスクリプタが示すページに現在アクセスしているプロセスの数を示す。 Pin Count とも言われる。この数値が 0 よりも大きければページは固定*4され、そうでないならページの固定は解除される。*5
• usage_count: これはアクセスされた回数。この回数をクロックスイープで使用する。
• context_lock, io_in_progress_lock: おそらく排他制御、軽量ロックと書かれているのでラッチに近い機能をもっていると考えられる。*6
• dirty bit :ページがダーティページかどうかを示す
• valid bit :保存されたページが読み取り、書き込みが可能かどうかを示す。
• io_in_progress bit : 関連するページをストレージから読み書きするかどうかを示す。

基本的にロックやラッチに関わる値を保持している。

番外編 MySQL の Buffer Pools

dev.mysql.com

ここにもあるし、前にもどこかでまとめた記憶があるが LRU キャッシュとなっている。
バッファプールを 5/8, 3/5 に分割してそれぞれをサブリストとすることで二度目以降の使用がないデータを優先的に開放するようになっている。

ただこれ以上詳細な情報がなかったので、どういったフィールドを保持していてどのようにロックやラッチを使っているかというところまではわからない。

まとめ

参考文献を使った章以降は、基本的にそのバッファプールマネージャの構造においてどのようにページを開放するかなどなので説明を省略した。

*1:buffer_id のこと

*2:ストレージに永続化されていない、バッファプールでのみ変更されたページのこと

*3:一対一の対応になっている

*4:どういう状況かよくわからない

*5:こう書いていると、おそらくキャッシュから除去されるかどうかだと思っている。

*6:PostgreSQL は MySQL と異なりマルチプロセスなので少し意味合いが変わりそう