MVCC — PostgreSQL-এর বাস্তব implementation

লক্ষ্য: PG-visibility-র core — snapshot + version-list + GC rule — scripted scenario-তে verify।

from collections import defaultdict

class Engine:
    def __init__(self):
        self.rows = defaultdict(list)   # key -> [[xmin, xmax, value], ...]
        self.status = {}                # xid -> 'c'(ommitted)/'a'(borted)
        self.next_xid = 1
        self.snapshots = {}

    def begin(self):
        xid = self.next_xid; self.next_xid += 1
        self.snapshots[xid] = {
            'me': xid, 'horizon': xid,
            'running': {s for s, _ in self.snapshots.items()
                          if s not in self.status},
        }
        return xid

    def _st(self, xid): return self.status.get(xid, 'p')  # p=pending
    def commit(self, x): self.status[x]='c'; self._forget(x)
    def abort(self, x):  self.status[x]='a'; self._forget(x)
    def _forget(self, x): self.snapshots.pop(x, None)

    def insert(self, tx, key, value):
        self.rows[key].append([tx, 0, value])

    def read(self, tx, key):
        for xmin, xmax, value in reversed(self.rows[key]):
            if self.visible(xmin, xmax, self.snapshots[tx]):
                return value
        return None

    def update(self, tx, key, value):
        assert self.read(tx, key) is not None, "key invisible!"
        for v in self.rows[key]:
            if self.visible(v[0], v[1], self.snapshots[tx]):
                v[1] = tx                       # old: মৃত্যু-stamp
        self.rows[key].append([tx, 0, value])   # new version

    # ---------- the heart ----------
    def visible(self, xmin, xmax, snap):
        born_ok = (xmin == snap['me']) or (
            self._st(xmin)=='c' and xmin <= snap['horizon']
                                and xmin not in snap['running'])
        if not born_ok: return False
        if xmax == 0: return True
        gone_ok = (self._st(xmax)!='c') or (xmax==snap['me']) or \
                  (xmax>snap['horizon']) or (xmax in snap['running'])
        return gone_ok                 # মৃত্যু আমার ছবিতে এখনো নেই

    # ---------- garbage collection ----------
    def gc(self):
        removed = 0
        for key in list(self.rows):
            keep = []
            for v in self.rows[key]:
                needed = any(self.visible(*v[:2], s)
                             for s in self._live_snaps()) or \
                         self.visible(v[0], v[1],
                             {'me': -1, 'horizon': self.next_xid,
                              'running': set()})
                if needed: keep.append(v)
                else: removed += 1
            self.rows[key] = keep
        return removed

    def _live_snaps(self):
        return self.snapshots.values()


# ---------- scripted scenario ----------
e = Engine()
t1 = e.begin(); e.insert(t1, 'acct', 100)      # T1: acct=100
e.commit(t1)

tR = e.begin()                                  # T_R: লম্বা reader (RR)

t2 = e.begin(); e.update(t2, 'acct', 200)       # T2: 100→200
e.commit(t2)

print("T_R sees:", e.read(tR, 'acct'))          # 100 — snapshot-এ আটকে
print("new reader:", e.read(e.begin(), 'acct')) # 200 — fresh
print("GC removed:", e.gc())                    # 0! T_R-এর জন্য old দরকার

e.commit(tR)                                    # reader চলে গেল
print("after release:", e.gc())                 # 1 — old version মৃত

t3 = e.begin()
print("post-GC read:", e.read(t3, 'acct'))      # 200 — কিছুই হারায়নি
e.commit(t3)

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

T_R sees: 100
new reader: 200
GC removed: 0
after release: 1
post-GC read: 200

তিন যাচাই একসাথে: (১) long-reader পুরনো ছবি — isolation; (২) GC তার version রাখে — correctness; (৩) release-পরে ময়লা যায়, নতুন reader- উত্তর অক্ষত — economy। এখন abort-path: e.abort(t2) দিলে পুরনো version-ই জীবিত থাকত — atomicity-by-invisibility, transactions-লেসন-প্রতিশ্রুতির engine-রূপ।

নিজে বাড়ান: (১) abort-scenario print করে প্রমাণ করুন aborted write সবার কাছে invisible; (২) future-reader-check ছাড়া gc() কী ভুল করবে — edge-case দেখান; (৩) RC-mode: read()-এ প্রতিবার fresh snapshot — ফল কী বদলায়; (৪) xid mod-256 circular-comparison — কোথায় ভাঙে।