047: "the leaf is the commit" measured against the bars set before: appends pass, sparse updates do not, as said beforehand that means two units, not one: list bytes a message at 1 / 16 / 256 a commit, entries' appends today 65.5 / 15.7 / 12.4, leaves cow 1,636 / 102 / 14.5, leaves with appends in place past every kept snapshot's count (tail) 25.9 / 10.9 / 10.0; the bank's transfers today 122 / 35.6 / 30.1 (bars 244 / 71 / 60), cow 7,428 / 2,098 / 996, tail 4,826 / 1,975 / 992, cells written in place 186 / 126 / 122 but seen by kept snapshots (933,888 / 542,208 / 10,848 times); after the run, a leaf with room for changes (delta, 16 B each, the leaf written anew when full): 739 / 545 / 292 with room 8, 363 / 268 / 176 with 32, 249 / 161 / 136 with 128, every one over (today's log puts a change in about 7.5 B: varint places, zigzag wholes, one frame a commit); no kept snapshot sees a write of cow, tail or delta; rows as leaves (packet.c): 44.4 machine instructions a row to check and take 32-row column chunks against pure_list_read's 1,318 (cycles 14.2 against 372), every cell the same

1 files changed, 42 insertions, 7 deletions

diff --git a/research/experiments/047-leaf-commit/model.py b/research/experiments/047-leaf-commit/model.py
index a441166..9d9e890 100644
--- a/research/experiments/047-leaf-commit/model.py
+++ b/research/experiments/047-leaf-commit/model.py
@@ -30,6 +30,10 @@ The bars, set before running (today's list bytes, the log and images, by groupin
 - 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).
+After the run (not in the bars above, so not held to them): delta, the leaf with room for 8 changes after its cells
+(16 B each: its place, field and cell), appended in place, a full room writing the leaf anew with them folded in. One
+object still: the log's records live in the leaf they change. Its readers' price (a read looks at the room) is not
+counted here.
 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.
@@ -42,6 +46,9 @@ 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
+DELTAS, DELTA = 8, 16  # delta: a leaf's room for changes after its cells (u32 place, u8 field, pad, the 8-byte cell)
+import os  # noqa: E402
+DELTAS = int(os.environ.get('MODEL_DELTAS', DELTAS))
 
 
 class List:
@@ -51,6 +58,8 @@ class List:
         self.name, self.cell, self.items = name, cell, items
         self.leaf = HEADER + FANOUT * cell
         self.version = {}  # node (level, index) -> the commit that wrote it
+        self.deltas = {}   # delta: a leaf's changes in its room since it was last written whole
+        self.written = {}  # delta: how often a leaf was written whole (its version: a new one is another object)
 
     def leaves(self):
         return max(1, -(-self.items // FANOUT))
@@ -71,7 +80,7 @@ class List:
         return out
 
     def live(self):
-        n, total, level = self.leaves(), self.leaves() * self.leaf, 0
+        n, total, level = self.leaves(), self.leaves() * (self.leaf + DELTAS * DELTA * (self.way == 'delta')), 0
         while n > 1:
             n = -(-n // FANOUT)
             total += n * INNER
@@ -97,7 +106,11 @@ def workload(name, messages, seed=47):
 
 def run(name, messages, batch, way):
     lists, changes = workload(name, messages)
-    written = {'leaves': 0, 'cells': 0, 'inner': 0, 'entries': 0, 'records': 0, 'compaction': 0}
+    for l in lists.values():
+        l.way = way
+        if way == 'delta':
+            l.leaf += DELTAS * DELTA  # the room is part of the leaf
+    written = {'leaves': 0, 'cells': 0, 'inner': 0, 'entries': 0, 'deltas': 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}
@@ -106,6 +119,8 @@ def run(name, messages, batch, way):
         group = changes[start:start + batch]
         touched = {n: set() for n in lists}  # leaves to write anew
         tail_cells = {n: 0 for n in lists}
+        delta_writes = {n: 0 for n in lists}
+        delta_leaves = {n: set() for n in lists}
         for message in group:
             for list_name, op, position in message:
                 l = lists[list_name]
@@ -113,7 +128,7 @@ def run(name, messages, batch, way):
                     at = l.items
                     l.items += 1
                     leaf = at // FANOUT
-                    if way in ('tail', 'inplace'):
+                    if way in ('tail', 'inplace', 'delta'):
                         for snapshot in kept:  # a kept snapshot never reads at or past its count
                             if at < snapshot.get(list_name, 0):
                                 violations += 1
@@ -129,6 +144,21 @@ def run(name, messages, batch, way):
                                 written['inner'] += HEADER
                     else:
                         touched[list_name].add(leaf)
+                elif way == 'delta':  # the change appended into its leaf's room, in place; a full room: the leaf anew
+                    leaf = position // FANOUT
+                    n, version = l.deltas.get(leaf, 0), l.written.get(leaf, 0)
+                    for snapshot in kept:  # a kept snapshot reads no more of its leaf's room than its commit said
+                        seen = snapshot.get((list_name, leaf))
+                        if seen and seen[0] == version and n < seen[1]:
+                            violations += 1
+                    if n < DELTAS:
+                        l.deltas[leaf] = n + 1
+                        delta_writes[list_name] += 1
+                        delta_leaves[list_name].add(leaf)
+                    else:
+                        l.deltas[leaf] = 0
+                        l.written[leaf] = version + 1
+                        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):
@@ -148,19 +178,24 @@ def run(name, messages, batch, way):
         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])
+        for n in lists:  # delta: each change's 16 bytes, and each leaf with new ones its 16 in the commit record
+            written['deltas'] += delta_writes[n] * DELTA + PER_LIST * len(delta_leaves[n])
+            size += delta_writes[n] * DELTA + PER_LIST * len(delta_leaves[n])
+        changed = sum(1 for n in lists if touched[n] or tail_cells[n] or delta_writes[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()})
+            snapshot = {n: l.items for n, l in lists.items()}
+            snapshot.update({(n, leaf): (l.written.get(leaf, 0), c) for n, l in lists.items() for leaf, c in l.deltas.items()})
+            kept.append(snapshot)
             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']
+    lists_bytes = written['leaves'] + written['cells'] + written['inner'] + written['entries'] + written['deltas']
     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()},
@@ -170,7 +205,7 @@ def run(name, messages, batch, way):
 def main():
     name, messages = sys.argv[1], int(sys.argv[2])
     for batch in (1, 16, 256):
-        for way in ('cow', 'tail', 'inplace'):
+        for way in ('cow', 'tail', 'inplace', 'delta'):
             print(json.dumps(run(name, messages, batch, way)), flush=True)