Isolation Levels ও Anomalies — কতটা 'একা' দরকার

লক্ষ্য: anomaly detection + conflict-serializability test — নিজের হাতে।

from collections import defaultdict
from itertools import permutations

def parse(log):
    return [(s, int(t[1]), t[0],
             t[t.index('(')+1:-1] if '(' in t else None)
            for s, t in enumerate(log)]

def anomalies(hist):
    """hist: [(step, tx, kind, item)] -> পাওয়া anomaly-র তালিকা"""
    found, commits = [], set()
    seen_read, seen_write = defaultdict(list), defaultdict(list)
    for step, tx, kind, item in hist:
        if kind == 'c': commits.add(tx); continue
        if kind == 'r':
            ws = [w for w in seen_write[item] if w[1] < step]
            if ws and ws[-1][0] not in commits:
                found.append(f"DIRTY READ : T{tx} পড়ল '{item}' "
                             f"T{ws[-1][0]}-এর uncommitted write")
            seen_read[item].append((tx, step))
        elif kind == 'w':
            seen_write[item].append((tx, step))
        elif kind == 'q':              # predicate scan -> phantom
            for s2, tx2, k2, it2 in hist[:step]:
                if tx2 != tx and it2 == item and k2 == 'i':
                    found.append(f"PHANTOM    : T{tx}-র scan-এ "
                                 f"T{tx2}-র নতুন row")
    # non-repeatable: r_i(x) ... w_j(x) ... r_i(x)
    for item, rs in seen_read.items():
        for i in range(len(rs)):
            for j in range(i+1, len(rs)):
                t1, s1 = rs[i]; t2, s2 = rs[j]
                if t1 != t2: continue
                mid = [wt for wt, ws_ in seen_write[item]
                         if t1 != wt and s1 < ws_ < s2]
                if mid:
                    found.append(f"NON-REPEATABLE: T{t1} '{item}' "
                                 f"দুইবার ({s1},{s2}) — মাঝে T{mid[-1]}")
    # lost update: দুই tx দুজনেই পড়ে দুজনেই লিখেছে একই item
    for item, rs in seen_read.items():
        rw = {t for t, _ in rs} & {t for t, _ in seen_write[item]}
        for a, b in permutations(sorted(rw), 2):
            if b > a:
                found.append(f"LOST UPDATE: T{a}, T{b} দুজনেই "
                             f"'{item}' পড়ে লিখেছে")
    return found

def serialization_graph(hist):
    """Conflict edges (ww, wr/rw): একই item, ভিন্ন tx"""
    edges = defaultdict(set)
    writes, reads = defaultdict(list), defaultdict(list)
    for step, tx, kind, item in hist:
        (writes if kind == 'w' else reads)[item].append(tx)
    for item, ws in writes.items():
        for tx1 in ws:
            for tx2 in ws + reads.get(item, []):
                if tx1 != tx2: edges[tx1].add(tx2)
    return edges

def has_cycle(edges):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = defaultdict(int)
    def dfs(u, path):
        color[u] = GRAY
        for v in edges[u]:
            if color[v] == GRAY: return path + [v]
            if color[v] == WHITE:
                c = dfs(v, path + [v])
                if c: return c
        color[u] = BLACK
        return None
    nodes = set(edges) | {v for vs in edges.values() for v in vs}
    for n in sorted(nodes):
        if color[n] == WHITE:
            c = dfs(n, [n])
            if c: return c
    return None

def validate(log):
    hist = parse(log)
    print(f"History: {' '.join(log)}")
    found = anomalies(hist)
    for f in found: print("  ⚠", f)
    if not found: print("  ✔ কোনো চেনা anomaly নেই")
    cyc = has_cycle(serialization_graph(hist))
    if cyc:
        print(f"  ✗ Conflict-SERIALIZABLE নয় — cycle: "
              f"{' -> '.join('T%d'%t for t in cyc)}")
    else:
        print("  ✔ Conflict-serializable (acyclic graph)")

validate(["r1(x)", "r2(x)", "w1(x)", "w2(x)", "c1", "c2"])   # lost update
validate(["w1(x)", "r2(x)", "c2", "a1"])                     # dirty read
validate(["r1(x)", "w2(x)", "c2", "r1(x)", "c1"])            # non-repeatable
validate(["r1(y)", "w1(x)", "w2(x)", "w2(y)", "c2", "c1"])   # SI-ফাঁক

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

History: r1(x) r2(x) w1(x) w2(x) c1 c2
  ⚠ LOST UPDATE: T1, T2 দুজনেই 'x' পড়ে লিখেছে
  ✗ Conflict-SERIALIZABLE নয় — cycle: T1 -> T2 -> T1
History: w1(x) r2(x) c2 a1
  ⚠ DIRTY READ : T2 পড়ল 'x' T1-এর uncommitted write
  ✔ Conflict-serializable (acyclic graph)
History: r1(x) w2(x) c2 r1(x) c1
  ⚠ NON-REPEATABLE: T1 'x' দুইবার (0,3) — মাঝে T2
  ✗ Conflict-SERIALIZABLE নয় — cycle: T1 -> T2 -> T1
History: r1(y) w1(x) w2(x) w2(y) c2 c1
  ✔ কোনো চেনা anomaly নেই
  ✗ Conflict-SERIALIZABLE নয় — cycle: T1 -> T2 -> T1

শেষ উদাহরণই শিক্ষণীয়: কোনো anomaly নেই, তবু serializable নয় — anomaly আর non-serializability এক নয়; snapshot isolation ঠিক এই ফাঁকে বাস করে।

নিজে বাড়ান:

1. Abort-aware graph: a1-এর পরে T1-এর সব edge বাদ দিন
2. Topological order ছাপান — equivalent serial order
3. Write-skew detector: ভিন্ন item লিখলেও উভয়ে একই predicate পড়েছে কি না চেক