047: "the leaf is the commit" (feedback 009) set up before it runs: today's store measured as the base (baseline.py, 046's shim and journal: list bytes a message, the log and images, at 1 / 16 / 256 messages a commit: entries' appends 65.5 / 15.7 / 12.4, the bank's transfers 122 / 35.6 / 30.1, the tree apart), and a byte-accounting model (model.py) of commits writing the leaves they changed in memory's own bytes (leaf 296 to 1,320 B, inner node 680 B, cow; tail appends in place past every kept snapshot's count; inplace, which may not be, to show why), its bars written before the run (appends at most today's, sparse updates at most twice, no write a kept snapshot sees) and what a pass for appends with a miss for updates would mean (two units, not one); 046's Run takes pure-run's arguments; 045's keyed file says 24 refused, not the 26 its commit said

1 files changed, 178 insertions, 0 deletions

diff --git a/research/experiments/047-leaf-commit/model.py b/research/experiments/047-leaf-commit/model.py
new file mode 100644
index 0000000..a441166
--- /dev/null
+++ b/research/experiments/047-leaf-commit/model.py
@@ -0,0 +1,178 @@
+#!/usr/bin/env python3
+"""Research 047: "the leaf is the commit" (feedback 009) before any store code: what a store whose commit writes the
+list leaves it changed, in the bytes memory keeps them in, would write for a workload, against what today's store
+writes (baseline.py: the log and the images). A byte-accounting model, not a store.
+
+The layout (the memory's, core/module-list.c, as the disk's: one byte shape):
+- a leaf: a 40-byte header (Node) and, per field, 32 cells (8 bytes; a text a 16-byte span, its bytes elsewhere):
+  296 B for one number, 1,320 B for the bank's account (three numbers and a text), 808 a teller, 552 a branch,
+  1,320 a transfer;
+- an inner node: 680 B (the header, 32 children, the guide: 32 counts before and 32 keys);
+- a commit: a 128-byte record (as the tree's today) and 16 bytes a list it changed (its root and count).
+Two ways to write a commit:
+- cow: every leaf the commit changed is written anew, and every inner node above them (the root too); the old copies
+  are garbage until a compaction.
+- inplace: tail, and a change elsewhere written in place too (its cell alone): not a way the store may take (a kept
+  snapshot reads the cell, and a crash between the write and the commit loses the old value): counted to show it.
+- tail: as cow, but an append at a list's end writes only its cells, in place, into its last leaf's free slots (and a
+  new leaf its header, and its parent one child entry, 20 B, in place): what a reader of an older commit cannot see,
+  since it reads no cell past its commit's count. Changes elsewhere are cow.
+Compaction by the tree's own rule: when the file's end past its 8 KiB of slots passes 4 x live + 1 MiB, the live nodes
+are written again (counted). Snapshots: one kept every 64 commits for 16 x 64 commits; every in-place write is checked
+against the counts the kept ones read (a write a kept snapshot could see stops the model).
+
+Workloads (each as baseline.py drives the store):
+- entries: one number appended a message (046's entries.aup);
+- bank: 10 branches, 100 tellers, 10,000 accounts loaded first (leaves full), then a transfer a message: its account's,
+  teller's and branch's balance set (uniform aid, tid, bid; the same generator as baseline.py), a transfer appended.
+
+The bars, set before running (today's list bytes, the log and images, by grouping 1 / 16 / 256 messages a commit):
+- appends: the leaf commit's list bytes a message at most today's (entries: 65.5 / 15.7 / 12.4);
+- sparse updates: at most twice today's (bank: 2 x 122 / 35.6 / 30.1 = 244 / 71.2 / 60.2);
+- snapshot: no in-place write a kept snapshot can see (cow and tail; inplace is there to break it).
+What it means, said before: if appends pass and updates do not, "one unit" fails as stated: the leaf is the unit for
+appends and bulk, and a sparse change needs a delta form, which is what the log is; the honest design is then two
+units (or the log kept for updates alone), not one.
+
+  model.py WORKLOAD MESSAGES     one JSON line a way and grouping"""
+import json
+import random
+import sys
+
+HEADER, INNER, FANOUT, RECORD, PER_LIST, SLOTS, SLACK = 40, 680, 32, 128, 16, 8192, 1 << 20
+ENTRY = 20  # a child entry written into a parent in place: its pointer (8), count before (4) and key (8)
+KEEP_EVERY, KEPT = 64, 16
+
+
+class List:
+    """A list's tree, its leaves full as loaded: leaf i holds items 32 i .. 32 i + 31."""
+
+    def __init__(self, name, cell, items):
+        self.name, self.cell, self.items = name, cell, items
+        self.leaf = HEADER + FANOUT * cell
+        self.version = {}  # node (level, index) -> the commit that wrote it
+
+    def leaves(self):
+        return max(1, -(-self.items // FANOUT))
+
+    def levels(self):
+        """Inner levels above the leaves (0 when one leaf is the root)."""
+        n, levels = self.leaves(), 0
+        while n > 1:
+            n, levels = -(-n // FANOUT), levels + 1
+        return levels
+
+    def path(self, leaf):
+        """The inner nodes above a leaf: (level, index) from the leaves' parents up."""
+        out, index = [], leaf
+        for level in range(1, self.levels() + 1):
+            index //= FANOUT
+            out.append((level, index))
+        return out
+
+    def live(self):
+        n, total, level = self.leaves(), self.leaves() * self.leaf, 0
+        while n > 1:
+            n = -(-n // FANOUT)
+            total += n * INNER
+        return total
+
+
+def workload(name, messages, seed=47):
+    """Each message's changes: (list, 'set', position) or (list, 'append', None)."""
+    if name == 'entries':
+        lists = {'entries': List('entries', 8, 0)}
+        return lists, [[('entries', 'append', None)] for _ in range(messages)]
+    rng = random.Random(seed)
+    accounts = 10000
+    lists = {'accounts': List('accounts', 40, accounts), 'tellers': List('tellers', 24, 100),
+             'branches': List('branches', 16, 10), 'history': List('history', 40, 0)}
+    out = []
+    for _ in range(messages):
+        aid, tid, bid = rng.randrange(accounts), rng.randrange(100), rng.randrange(10)
+        rng.randint(-5000, 5000)  # the delta, drawn as baseline.py draws it (the same stream)
+        out.append([('accounts', 'set', aid), ('tellers', 'set', tid), ('branches', 'set', bid), ('history', 'append', None)])
+    return lists, out
+
+
+def run(name, messages, batch, way):
+    lists, changes = workload(name, messages)
+    written = {'leaves': 0, 'cells': 0, 'inner': 0, 'entries': 0, 'records': 0, 'compaction': 0}
+    end, live0 = SLOTS, sum(l.live() for l in lists.values())
+    end += live0  # what the setup loaded (not counted: baseline.py takes it away too)
+    kept = []  # snapshots kept: {list name: count it reads}
+    violations, commits = 0, 0
+    for start in range(0, messages, batch):
+        group = changes[start:start + batch]
+        touched = {n: set() for n in lists}  # leaves to write anew
+        tail_cells = {n: 0 for n in lists}
+        for message in group:
+            for list_name, op, position in message:
+                l = lists[list_name]
+                if op == 'append':
+                    at = l.items
+                    l.items += 1
+                    leaf = at // FANOUT
+                    if way in ('tail', 'inplace'):
+                        for snapshot in kept:  # a kept snapshot never reads at or past its count
+                            if at < snapshot.get(list_name, 0):
+                                violations += 1
+                        tail_cells[list_name] += 1
+                        if at % FANOUT == 0:  # a new leaf: its header, and an entry in its parent (in place); a
+                            written['leaves'] += HEADER  # parent full: a new one (its header) and an entry above it
+                            index = leaf
+                            while index:
+                                written['entries'] += ENTRY
+                                if index % FANOUT:
+                                    break
+                                index //= FANOUT
+                                written['inner'] += HEADER
+                    else:
+                        touched[list_name].add(leaf)
+                elif way == 'inplace':  # the cell written where it is: what a kept snapshot (and a crash) would see
+                    for snapshot in kept:
+                        if position < snapshot.get(list_name, 0):
+                            violations += 1
+                    tail_cells[list_name] += 1
+                else:
+                    touched[list_name].add(position // FANOUT)
+        size = 0
+        for n, leaves in touched.items():
+            l = lists[n]
+            inner = set()
+            for leaf in leaves:
+                inner.update(l.path(leaf))
+            size += len(leaves) * l.leaf + len(inner) * INNER
+            written['leaves'] += len(leaves) * l.leaf
+            written['inner'] += len(inner) * INNER
+        for n, cells in tail_cells.items():
+            written['cells'] += cells * lists[n].cell
+            size += cells * lists[n].cell
+        changed = sum(1 for n in lists if touched[n] or tail_cells[n])
+        written['records'] += RECORD + PER_LIST * changed
+        end += size + RECORD + PER_LIST * changed
+        commits += 1
+        if commits % KEEP_EVERY == 0:
+            kept.append({n: l.items for n, l in lists.items()})
+            kept = kept[-KEPT:]
+        live = sum(l.live() for l in lists.values())
+        if end - SLOTS > 4 * live + SLACK:
+            written['compaction'] += live
+            end = SLOTS + live
+    total = sum(written.values())
+    lists_bytes = written['leaves'] + written['cells'] + written['inner'] + written['entries']
+    return {'workload': name, 'messages': messages, 'batch': batch, 'way': way, 'commits': commits,
+            'list_bytes_per_message': round((lists_bytes + written['records'] - RECORD * commits) / messages, 1),
+            'by_part_per_message': {k: round(v / messages, 1) for k, v in written.items()},
+            'all_bytes_per_message': round(total / messages, 1), 'snapshot_violations': violations}
+
+
+def main():
+    name, messages = sys.argv[1], int(sys.argv[2])
+    for batch in (1, 16, 256):
+        for way in ('cow', 'tail', 'inplace'):
+            print(json.dumps(run(name, messages, batch, way)), flush=True)
+
+
+if __name__ == '__main__':
+    main()