https://ryuichi1208.hateblo.jp/entry/2025/02/11/165445

PostgreSQLのキャッシュ管理

PostgreSQLは高速データベースシステムとして広く使用されていますが、その高速性を支える重要な技術の一つに「Clock-Sweepアルゴリズム」があります。このアルゴリズムは、PostgreSQLのバッファキャッシュ(shared_buffers)を最適に管理するための方法で、実際のパフォーマンスに大きな影響を与えます。

xtech.nikkei.com

Clock-Sweepアルゴリズムとは？

Clock-Sweepアルゴリズムは、実際にはLRU (Least Recently Used)に基づいた方式を便利化したものです。LRUアルゴリズムは最も使用されていないページを解放することを目的としますが、その管理コストや複雑性が高いという問題がありました。

Clock-Sweepは、このLRUを基盤にしつつも、使用頻度を考慮してより簡単で高速な処理を実現する方式です。

taedium.hatenadiary.org

実装

以下はChatGTPに生成してもらったコードから重要な部分だけを抜き出していて動かないですがわかりやすくしています。

package main

import (
    "fmt"
)

// BufferPage は、バッファプール内の単一のページを表す
type BufferPage struct {
    PageID     int  // ページの一意な識別子
    Referenced bool // 最近アクセスされたことを示す参照ビット
    Dirty      bool // ページが変更されたかどうかを示す
}

// ClockBuffer は、Clock-Sweep アルゴリズムによって管理されるバッファプールを表す
type ClockBuffer struct {
    Pages         []BufferPage // バッファ内のページを格納するスライス
    Pointer       int
    MaxBufferSize int          // バッファの最大サイズ
}

// NewClockBuffer は、指定されたサイズの ClockBuffer を初期化する
func NewClockBuffer(size int) *ClockBuffer {
    return &ClockBuffer{
        Pages:         make([]BufferPage, 0, size),
        Pointer:       0,
        MaxBufferSize: size,
    }
}

// AccessPage は、バッファ内のページにアクセスする操作をシミュレートする
func (cb *ClockBuffer) AccessPage(pageID int) {
    for i := range cb.Pages {
        if cb.Pages[i].PageID == pageID {
            cb.Pages[i].Referenced = true
            fmt.Printf("ページ %d にアクセスし、参照ビットを設定しました。\n", pageID)
            return
        }
    }
    fmt.Printf("ページ %d はバッファに存在しません。追加します。\n", pageID)
    cb.AddPage(pageID)
}

// AddPage は、新しいページをバッファに追加し、必要に応じてページを置換する
func (cb *ClockBuffer) AddPage(pageID int) {
    if len(cb.Pages) < cb.MaxBufferSize {
        // バッファに空きがある場合、新しいページを追加
        cb.Pages = append(cb.Pages, BufferPage{PageID: pageID, Referenced: true})
        fmt.Printf("ページ %d をバッファに追加しました。\n", pageID)
    } else {
        // バッファが満杯の場合、ページを置換する
        evictedPage := cb.evictPage()
        fmt.Printf("ページ %d をバッファから置換しました。\n", evictedPage.PageID)
        cb.Pages[cb.Pointer] = BufferPage{PageID: pageID, Referenced: true}
        fmt.Printf("ページ %d をバッファの位置 %d に追加しました。\n", pageID, cb.Pointer)
        cb.advancePointer()
    }
}

// evictPage は、Clock-Sweep アルゴリズムを使用して置換するページを見つける
func (cb *ClockBuffer) evictPage() BufferPage {
    for {
        page := cb.Pages[cb.Pointer]
        if page.Referenced {
            // 参照ビットをクリアし、次のページへ移動
            cb.Pages[cb.Pointer].Referenced = false
            cb.advancePointer()
        } else {
            // 参照ビットがクリアされているページを置換対象とする
            return page
        }
    }
}

func (cb *ClockBuffer) advancePointer() {
    cb.Pointer = (cb.Pointer + 1) % cb.MaxBufferSize
}

func (cb *ClockBuffer) DisplayBuffer() {
    fmt.Println("現在のバッファ状態:")
    for i, page := range cb.Pages {
        ref := 0
        if page.Referenced {
            ref = 1
        }
        fmt.Printf("スロット %d: PageID=%d, 参照ビット=%d\n", i, page.PageID, ref)
    }
    fmt.Println()
}

func main() {
    // 3 スロットの ClockBuffer を初期化
    buffer := NewClockBuffer(3)

    // ページアクセスをシミュレート
    buffer.AccessPage(1)
    buffer.DisplayBuffer()

    buffer.AccessPage(2)
    buffer.DisplayBuffer()

    buffer.AccessPage(3)
    buffer.DisplayBuffer()

    // ページ 1 を再度アクセス（参照ビットがセットされる）
    buffer.AccessPage(1)
    buffer.DisplayBuffer()

    // 新しいページを追加（置換が発生する）
    buffer.AccessPage(4)
    buffer.DisplayBuffer()

    // 別の新しいページを追加（さらにページを置換）
    buffer.AccessPage(5)
    buffer.DisplayBuffer()

    // ページ 1 を再度アクセス（まだバッファに存在するか確認）
    buffer.AccessPage(1)
    buffer.DisplayBuffer()
}

まとめ

Clock-Sweepアルゴリズムは、PostgreSQLの高速性を支える重要な要素であり、シンプルな構造ながらも高い効率を達成します。このアルゴリズムを理解することで、PostgreSQLのパフォーマンスチューニングにおいても最適な設定を行い、システム全体の効率を最大化することが可能となります。