1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
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()
|
