Clock Sweep と LRU Cache を実装する - それが僕には楽しかったんです。

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

はじめに
DBMSのキャッシュ
- MySQL の LRU キャッシュ
- PostgreSQL の Clock Sweep
実装
- LRU
- Clock Sweep
おわりに

はじめに

どうも、最近遊戯王が 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 のキャッシュを作れるとよさそう。