Buffer Pool — disk যখন memory-তে ভাড়া থাকে

লক্ষ্য: policy-দের মতভেদ মুখস্থ না করে দেখা — একই workload-এ তিন manager চালিয়ে hit-rate আর resume-storm পাশাপাশি:

import random
from collections import OrderedDict

HOT_KEYS = 1_500            # app-এর hot working set


def workload(pool_size, cycles=5, hot_ops=15_000, seed=7):
    """app চলছে (hot random) → nightly-batch style একান্ত বিশাল scan (৩× pool)
    → app আবার শুরু — বাস্তব production-এর ছন্দ"""
    rng = random.Random(seed)
    for _ in range(cycles):
        for _ in range(hot_ops):
            yield ('hot', rng.randrange(HOT_KEYS))
        for j in range(pool_size * 3):
            yield ('scan', j)


class BufferPool:
    def __init__(self, nframes, policy, ring=0):
        self.n, self.policy = nframes, policy   # 'lru' | 'clock'
        self.ring_cap = ring                    # >0 = scan-bypass ring (PG-style)
        self.ring_buf, self.ring_i = [], 0
        self.page_of = [None] * nframes         # frame -> page
        self.slot = {}                          # page -> frame
        self.lru = OrderedDict()
        self.ref = [0] * nframes                # CLOCK reference bits
        self.hand = 0
        self.hits = self.misses = self.storm = 0
        self.storming = False

    def access(self, page, kind='hot'):
        if self.ring_cap and kind == 'scan':
            self._ring_access(page)             # sweep মূল pool ছোঁয় না!
            return
        if page in self.slot:
            self.hits += 1
            f = self.slot[page]
            if self.policy == 'lru':
                self.lru.move_to_end(page)
            else:
                self.ref[f] = 1
        else:
            self.misses += 1
            if self.storming:
                self.storm += 1
            self._load(page)

    def _ring_access(self, page):
        if page in self.slot or page in self.ring_buf:
            self.hits += 1
            return
        self.misses += 1
        if len(self.ring_buf) < self.ring_cap:
            self.ring_buf.append(page)
        else:
            self.ring_buf[self.ring_i] = page   # round-robin overwrite
            self.ring_i = (self.ring_i + 1) % self.ring_cap

    def _load(self, page):
        f = next((i for i in range(self.n) if self.page_of[i] is None), None)
        if f is None:
            f = self._evict()
        self.page_of[f] = page
        self.slot[page] = f
        self.ref[f] = 1                         # নতুন page ref-bit-সহ জন্মায়
        if self.policy == 'lru':
            self.lru[page] = None

    def _evict(self):
        if self.policy == 'lru':
            victim, _ = self.lru.popitem(last=False)
            f = self.slot.pop(victim)
            self.page_of[f] = None
            return f
        while True:                             # CLOCK sweep
            p = self.page_of[self.hand]
            if self.ref[self.hand]:
                self.ref[self.hand] = 0         # second chance!
                self.hand = (self.hand + 1) % self.n
            else:
                f = self.hand
                self.slot.pop(p)
                self.page_of[f] = None
                self.hand = (self.hand + 1) % self.n
                return f

    def rate(self):
        return self.hits / max(1, self.hits + self.misses) * 100


def run(policy, ring=0, pool_size=2_000):
    pool = BufferPool(pool_size, policy, ring)
    storm_left, just_scanned, warm = 0, False, False
    for kind, key in workload(pool_size):
        if kind == 'scan':
            just_scanned = True
        else:
            if just_scanned:                    # scan সবে শেষ → app resume
                just_scanned = False
                if warm:                        # প্রথম cycle warm-up বাদ
                    storm_left = 3_000
            if storm_left > 0:
                pool.storming = True
                storm_left -= 1
                if storm_left == 0:
                    pool.storming = False
            warm = True
        pool.access(key, kind)
    return pool


if __name__ == '__main__':
    POOL = 2_000
    print(f'{POOL} frames; 5 cycles: 15k hot reads -> scan {POOL*3} pages')
    print('policy       overall   resume-storm')
    for label, args in (('lru       ', ('lru', 0)),
                        ('clock     ', ('clock', 0)),
                        ('clock+ring', ('clock', 32))):
        p = run(*args)
        print(f'{label}  {p.rate():5.1f}%    {p.storm}')

প্রত্যাশিত output:

2000 frames; 5 cycles: 15k hot reads -> scan 6000 pages
policy       overall   resume-storm
lru          71.4%    5185
clock        71.4%    5185
clock+ring   77.1%    0

পড়ার নিয়ম তিনটা লাইনে: (১) LRU আর bare CLOCK হুবহু একই ভেঙে পড়ে — ৩× pool-এর scan second-chance-কেও গিলে ফেলে; (২) resume-storm ৫১৮৫ মানে প্রতিটা scan-এর পরে hot set (~১৫০০ page × ৪ cycle) পুরো আবার-পড়া; (৩) ring-এ storm শূন্য — scan-কে isolate করাই আসল scan resistance, policy নিজে নয়। PostgreSQL-এর সিদ্ধান্তের নকল।

নিজে বাড়ান: (১) pin/unpin + dirty flag যোগ করে victim-flush cost মডেল করুন (write-back হিসাব); (২) InnoDB midpoint insertion variant — নতুন page-কে half-way-তে ঢোকান; (৩) hot_ratio আর scan_len sweep করে কোথায় boundary তা heat-map করুন।