跳轉到

2.3 緩衝池管理演算法#

概念說明#

緩衝池（buffer pool） 是檔案系統或資料庫在主記憶體中開闢的「頁快取」：把磁碟資料以頁為單位載入這個有限大小的記憶體區域，並在空間不足時依替換演算法（eviction policy）淘汰某頁。它扮演磁碟 I/O 的第一道關卡，命中率直接決定整體效能。

常見演算法：

  1. FIFO：最先進入的頁先淘汰。實作簡單但不反映使用狀況。
  2. OPT（理想）：淘汰「將來最久不被使用」的頁，需要預知未來，只能作為基準。
  3. LRU：淘汰「最久未被使用」的頁，利用時間區域性，接近 OPT。
  4. Clock（second chance）：用「引用位元」近似 LRU，避免維護精確時間戳，開銷小。
  5. LRU-K：避免「一次性的全表掃描污染快取」：只被用過一次的頁排在 LRU 尾，被多次使用後才晉級。
  6. MRU：淘汰最近使用的頁，適合循環式重複存取（例如 nested loop join 的錯誤 LRU 情境）。

緩衝池污染（buffer pool pollution）：全表掃描的頁接連進入，把熱資料擠出，引起命中率崩墜。實務透過 LRU-K、шейся部（把冷熱分區）、或「掃描時 pin 一次然後立刻可優先淘汰」等技巧減輕。

演算法步驟：LRU 和 Clock 的設計#

LRU 步驟：存取頁時把它移到鏈頭；驅逐時取鏈尾。 Clock 步驟： 1. 所有頁排成環，類似時鐘，有一個 手（hand） 指針。 2. 每頁有引用位元，被存取時置 1。 3. 需要淘汰時，手向前走；遇到引用位元 1 的頁則清為 0（它是第二次機會），遇到 0 的頁就淘汰。

# 02.3 範例：LRU 與 Clock 緩衝池
from collections import OrderedDict

class LRUPool:
    def __init__(self, n):
        self.cap, self.pool = n, OrderedDict()

    def get(self, pid):
        if pid in self.pool:
            self.pool.move_to_end(pid)
            return True, self.pool[pid]
        data = f"page@{pid}"
        if len(self.pool) >= self.cap:
            self.pool.popitem(last=False)     # 淘汰最久未用
        self.pool[pid] = data
        return False, data


class ClockPool:
    def __init__(self, n):
        self.cap, self.ring, self.ref, self.data = n, [], {}, {}
        self.hand, self.hard_miss = 0, 0

    def get(self, pid):
        if pid in self.data:
            self.ref[pid] = 1
            return True, self.data[pid]
        self.hard_miss += 1
        if len(self.data) >= self.cap:
            # 手持續前進直到找到 ref=0 的頁
            while True:
                victim = self.ring[self.hand]
                if self.ref[victim] == 0:
                    break
                self.ref[victim] = 0          # 給第二次機會
                self.hand = (self.hand + 1) % self.cap
            victim = self.ring[self.hand]
            del self.data[victim]; del self.ref[victim]
            self.ring[self.hand] = pid
            self.hand = (self.hand + 1) % self.cap
        else:
            self.ring.insert(self.hand, pid)
            self.hand = (self.hand + 1) % self.cap
        self.ref[pid] = 1
        self.data[pid] = f"page@{pid}"
        return False, self.data[pid]


def trace_demo(trace):
    for cls in (LRUPool, ClockPool):
        pool = cls(3)
        hits = sum(pool.get(p)[0] for p in trace)
        print(f"{cls.__name__:10s} 命中率 = {hits/len(trace):.0%}")


def demo():
    print("== 情境1：區域性好的重複模式 ==")
    trace_demo([1, 2, 3, 1, 2, 3, 1, 2, 3] * 5)
    print("== 情境2：全表掃描污染 ==")
    trace_demo([1, 2, 3] * 5 + [10, 11, 12, 13, 14] + [1, 2, 3])
    print("== 情境3：循環式掃描（LRU 反而最差） ==")
    trace_demo([1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4])

if __name__ == "__main__":
    demo()

執行可觀察到：情境 3 中 LRU 因「環形掃描每次淘汰剛好會再被用到的頁」而命中率 0%，Clock 因第二次機會避免了這個最差情況，說明為何實務（SQLite）常用 Clock。

複雜度與 I/O 成本分析#

  • LRU：get/evict 由 OrderedDict 做到攤均 O(1)；缺點是記憶體占用與链状态維護需要鎖。
  • Clock：攤均 O(cap/頁，最差 O(cap))，實作只需要 ring + 引用位元，無鎖友好。
  • 成本衡量：設緩衝命中率 h，則實際 I/O 次數 = 請求次數 × (1-h)。命中率從 99% → 90% 會讓 I/O 量放大 10 倍。
  • OPT：理論下界，僅供基準比較。Belady 的定理：替換演算法無法同時複製 OPT 的行為。

練習#

  1. 為 ClockPool 加入「在 ref 掃過第二圈都沒淘汰時給優先度最高頁」的 просchanging改進，並比較在三個情境下的命中率。
  2. 實作 LRU-K（K=2）：頁需要被存取至少 2 次才晉級 LRU 頭部，否則視為冷頁先淘汰。以情境 2 比較 LRU 與 LRU-2。
  3. 資料庫引擎在「作為查詢的 catalog 全表掃描」裡常 pin 頁（不能淘汰）。加入 pin 旗標，並說明如何避免 pin 所有的頁造成緩衝池整體凍結。