Storage Engine — file, page, slotted page, tuple

লক্ষ্য: PostgreSQL-এর page-machinery-র হাড়কাঁটা — indirection, দুই-cursor free space, tombstone, compaction — সব milestone এক struct-দুটোতে:

import struct

PAGE_SIZE = 4096
HEADER = 8                      # mini-header: lower@0, upper@2
SLOT = 4                        # '>HH' → offset, len(+0x8000 tombstone bit)
DEAD = 0x8000

class PageFull(Exception):
    pass

class SlottedPage:
    def __init__(self):
        self.buf = bytearray(PAGE_SIZE)
        self.lower = HEADER          # slot array-র শেষ প্রান্ত
        self.upper = PAGE_SIZE       # tuple region-র শুরু

    def _slot(self, i):
        off, ln = struct.unpack_from('>HH', self.buf, HEADER + i * SLOT)
        return off, ln

    def _set_slot(self, i, off, ln):
        struct.pack_into('>HH', self.buf, HEADER + i * SLOT, off, ln)

    def insert(self, data: bytes) -> int:
        if self.upper - self.lower < SLOT + len(data):
            self.compact()                       # গর্ত সরিয়ে আবার চেষ্টা
            if self.upper - self.lower < SLOT + len(data):
                raise PageFull(f'{len(data)}B needs {SLOT + len(data)}B')
        off = self.upper - len(data)
        self.buf[off:self.upper] = data
        self.upper = off
        sid = (self.lower - HEADER) // SLOT
        self._set_slot(sid, off, len(data))
        self.lower += SLOT
        return sid

    def get(self, sid: int) -> bytes:
        off, ln = self._slot(sid)
        if ln & DEAD:
            raise KeyError(f'slot {sid} deleted')
        return bytes(self.buf[off:off + ln])

    def delete(self, sid: int) -> None:
        off, ln = self._slot(sid)
        if not ln & DEAD:
            self._set_slot(sid, off, ln | DEAD)  # data থাকে, flag-ই মৃত্যুসনদ

    def compact(self):
        """live tuple-গুলো page-এর শেষে টেনে slot-offset rewrite"""
        moved = 0
        top = PAGE_SIZE
        nslots = (self.lower - HEADER) // SLOT
        for i in range(nslots):                   # পুরনো ক্রমেই
            off, ln = self._slot(i)
            if ln & DEAD:
                self._set_slot(i, 0, 0)           # dead slot সম্পূর্ণ মুছি
                continue
            if ln == 0:
                continue
            new_off = top - ln
            if new_off != off:
                self.buf[new_off:top] = self.buf[off:off + ln]
                moved += ln
            self._set_slot(i, new_off, ln & 0x7FFF)
            top = new_off
        self.upper = top
        return moved

    def report(self):
        nslots = (self.lower - HEADER) // SLOT
        live = dead = 0
        for i in range(nslots):
            _, ln = self._slot(i)
            if ln == 0:
                continue
            dead += ln & 0x7FFF if ln & DEAD else 0
            live += (ln & 0x7FFF) if not ln & DEAD else 0
        used = PAGE_SIZE - self.upper
        frag = dead / used * 100 if used else 0.0
        print(f'slots={nslots} live={live}B dead={dead}B '
              f'slack={self.upper - self.lower}B '
              f'fragmentation={frag:.1f}%')

if __name__ == '__main__':
    pg = SlottedPage()
    payload = lambda k: f'record-{k:04d}'.encode() * 3      # 33 B each
    slots = [pg.insert(payload(k)) for k in range(60)]
    print('after 60 inserts:')
    pg.report()
    for s in slots[::3]:                                     # প্রতি তৃতীয়টা মারো
        pg.delete(s)
    print('after deleting every 3rd:')
    pg.report()
    extra = [pg.insert(payload(1000 + k)) for k in range(10)]
    print('after re-inserting 10 new (holes still there):')
    pg.report()
    moved = pg.compact()
    print(f'compact() moved {moved}B:')
    pg.report()
    assert all(pg.get(slots[k]) == payload(k)
               for k in range(60) if k % 3 != 0)            # Id-রা stable!
    assert pg.get(extra[0]) == payload(1000)
    print('survivors readable via same slot numbers ✓')

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

after 60 inserts:
slots=60 live=1980B dead=0B slack=1868B fragmentation=0.0%
after deleting every 3rd:
slots=60 live=1320B dead=660B slack=1868B fragmentation=33.3%
after re-inserting 10 new (holes still there):
slots=70 live=1650B dead=660B slack=1498B fragmentation=28.6%
compact() moved 1650B:
slots=70 live=1650B dead=0B slack=2158B fragmentation=0.0%
survivors readable via same slot numbers ✓

লক্ষ্য করুন দুইটা জিনিস: (১) reinsert করলেও dead bytes জমেই থাকে — allocator শুধু উপরে append করে; PostgreSQL-ও এই কারণেই vacuum-এর ভরসা। (২) compact-এর পরেও বেঁচে থাকা record-রা একই slot number-এ পড়া যায় — indirection-ই promise।

নিজে বাড়ান: (১) update(sid, data) — delete+insert + forwarding slot hint; (২) max-tuple cap (PG-র ~২ KB rule-এর মতো) — বড় payload-এ TOAST-style exception; (৩) header-এ checksum যোগ করে torn-page detect।