zu2: what is left of the anonymous budget once the log pages are mapped

[tamnd]

#759 takes the log pages out of anonymous memory. This is what is left, worked out from the code, so that the next thing to cut is picked by arithmetic rather than by guess.

At a million ycsb records on server2, zu2 held 1152.6 MiB of anonymous memory against lmdb's 17.6. Almost all of that is log pages, and with map_settled and a bound they become a mapping of the file the kernel can drop. Then the anonymous total is these four:

• The mutable window. mutable_pages at 4 MiB a page, 16 MiB at the default of four. Fixed, and it has to be anonymous: those are the pages an in place update writes to.
• The scan plane. Measured on server2, 56.0 MiB over 1000000 keys, 58.7 bytes a key. A node is an 8 byte header, then 8 bytes a link with a geometric height at p=1/4 so about 10.7 bytes on average, then the key inline, in an 8 byte aligned bump arena. For a 23 byte ycsb key that is about 42 bytes of node and the rest is alignment and arena.
• The index. A bucket is SLOTS 8 byte entries, 64 bytes, and the table doubles, so a million keys sit in a table of 262144 buckets, 16.8 MiB, and a doubling holds both tables at once for as long as it takes to drain.
• The cold tier and whatever the sessions hold.

So roughly 90 to 110 MiB of anonymous memory a million records, call it 90 to 110 bytes a key. That is ten times better than 1152 and five times worse than lmdb, and the largest single line is the scan plane at more than half.

What to do about the scan plane is a design question with a real trade in it, which is why this is an issue rather than a change:

1. Keep the key by address rather than inline. Eight bytes for a log address instead of the key, and every comparison in a search reads the record. Cheap while the page is resident and a pread when it is not, which is exactly the case a bound makes common. This trades the memory for read amplification on the scan path and needs measuring before it is believed.
2. Hold a prefix inline and the address behind it. Most comparisons finish inside the prefix and only a tie reads the record. More code, and the win depends on the key distribution, which for ycsb is a common prefix and a counter, the worst case for a short prefix.
3. Put the arena chunks in a file of their own and map them. The same trick Every resident page is anonymous memory, so zu2 holds 65x more of it than lmdb and the kernel cannot reclaim any of it #757 plays on the log pages, and the arena never moves, which is what makes it possible at all. The chunks would have to be written before they can be mapped, so this is a real piece of work.
4. Leave it. 56 MiB a million keys is not what makes a resident set 1152 MiB, and the honest answer may be that after memory_pages evicts mapped pages, which gives back no anonymous memory and costs a pread #759 the memory column is no longer where the gap is.

Blocked on the #759 numbers, and the first thing to do here is measure rather than choose: run the four arm A/B with the per plane figures printed, so the four lines above are measured on a host rather than counted off the source.

[tamnd]

The measurement half of this is now possible, which it was not when the issue was written.

Three of the four planes were already reportable. The log pages through zu2_anonymous_pages since #759, the scan plane through zu2_ordered_bytes, and the mutable window is inside the anonymous page count by construction, since those pages are anonymous whatever else happens. The index was not, so the largest line after the scan plane was the one nobody could ask a running database about.

zu2_index_bytes reports it as of 4244e8c: the live table, plus the table being drained and its state array while a doubling is in flight. Maintained rather than counted, because a migration is only a valid reference inside an epoch and a metric has no business taking one. The resting figure is exact rather than an estimate, since a bucket is eight 8 byte entries in a repr(align(64)) struct, and tests/resizing.rs asserts exactly that: buckets times the cacheline at rest, strictly more while a doubling is in flight, and back to exact once the drain finishes.

go-ycsb prints the total and the split, in tamnd/go-ycsb cd4c3a8:

zu2 anonymous: X MiB total, log X, index X (N buckets), scan X, X bytes a key

Mapped pages are deliberately not in that total. They are a mapping of a file the kernel can drop under pressure, which is the whole distinction #757 turns on, so counting them in something called anonymous would undo the thing being measured.

The four arm A/B on server3 is queued behind a sqlite workload E retake and both jobs reset to origin and rebuild, so it picks this up without requeueing. The numbers on this issue stay arithmetic until that lands.

One thing found while reading for this and worth knowing before option 3 is chosen. Option 3 is putting the arena chunks in a file and mapping them, the same trick #757 plays on the log pages, and #768 says what that trick currently costs: one VMA per mapping, because the addresses are chosen by the kernel and run the opposite way to the file offsets. Measured on server1, 512 pages mapped a page at a time added 512 lines to /proc/self/maps, and the same 512 into one reservation with MAP_FIXED added one. An arena chunk is a megabyte, so option 3 done the current way would be four times as many mappings per byte as the log pages are. Whatever #768 settles on has to land before option 3 is worth costing.

[tamnd]

Two things about the scan plane before anyone picks one of the four options.

First, Options::ordered is off by default. The doc on it says the plane is a node per key held for as long as the database is open, and a host that only ever does point operations should not be paying for keys in an order it never asks for. So for workloads A through D the scan plane is not in the anonymous total at all, and option 4, leave it, already applies to every point only run without anybody doing anything. The 56.0 MiB measured on server2 was a run with ordered on. That narrows this issue to workload E and to anything else that scans.

Second, the 58.7 bytes a key is not waste, it is the layout. Working it through against crates/zu2/src/scan.rs:

• A node is LINKS + 8 * height + key.len(), so 8 bytes of header (key_len as a u32 and height as a u32), 8 bytes a level of forward pointer, then the key inline.
• Arena::alloc rounds every request up to a multiple of 8, because the next node's base has to stay 8 aligned for its links.
• height() is geometric at one over four, so the mean height is 4/3 and the mean pointer cost is 10.7 bytes.
• The key go-ycsb hands us is usertable: plus user plus the decimal of a positive 63 bit fnv hash. That is 10 + 4 + 18.9 = 32.9 bytes, since 89 percent of an int63 is 19 digits.

Put those together. At height one the node is 8 + 8 + 33 = 49 bytes, which rounds to 56. At height two, 64. Weighted by the height distribution the mean node is 57.8 bytes. The arena takes memory a 1 MiB chunk at a time, so a million keys is 55.2 MiB of nodes held in 56 chunks, and 56 MiB over a million keys is 58.7 bytes a key. That is the measured figure to within the rounding, so there is no leak here and nothing is being held that should not be.

Which also says where the bytes are: 33 of the 58.7 are the key itself, 8 are the header, 10.7 are the forward pointers, and about 6 are the round up to 8.

Of those, the header and the round up are the ones we can have back. Pack key_len and height into a single u32, height needs 5 bits to reach MAX_HEIGHT of 20 and the length gets the other 27, and move the links to the front of the node so the base staying 8 aligned keeps the links 8 aligned without the header sitting in front of them. The node becomes [links][u32 header][key], a height one node is 4 + 8 + 33 = 45 bytes rounding to 48, and the mean node drops from 57.8 to 50.6. That is 8 bytes a key, 14 percent of the plane, for a layout change with no change to the walk.

The other two directions do not survive contact:

• Prefix coding a key against its predecessor would kill the 14 shared bytes of usertable:user, but a skip list node is immutable and its predecessor changes as inserts land, so the thing a node was coded against can stop being its neighbour. Not viable here.
• Storing an 8 byte log offset instead of the key would take the node to about 26 bytes, but then every comparison on the walk dereferences a page that may not be resident, which is the exact cost this plane exists to avoid. An inline prefix to short circuit the common comparison does not help either, because with 14 shared leading bytes an 8 byte prefix always ties.

So the plane decision is: nothing to do for A through D because ordered is off, and for E the concrete win is the packed header. Filing that separately.

[tamnd]

Following the plane arithmetic through to the total, because the four planes this issue lists do not add up to what was measured and the gap is the whole story.

On server2 at a million records zu2 held 1152.6 MiB of anonymous memory against lmdb's 17.6. The four planes account for a small part of that:

• the mutable window, 4 pages at 4 MiB, so 16.0 MiB
• the scan plane, 56.0 MiB, and only when ordered is on, which it is not by default
• the index, 64 bytes a bucket
• the cold tier and the sessions

Call the index generously and that is under 100 MiB of the 1152.6. The other thousand is the log, and it is there on purpose: memory_pages defaults to usize::MAX, whose doc says in as many words that it never evicts, and map_settled defaults to off. So at defaults every page the log has ever appended is still anonymous heap, and a million YCSB records at about a kilobyte each is 288 pages of 4 MiB, which is the number.

That reframes this issue. Shaving the planes is worth doing and #772 does 7 bytes a key of it, but nothing in the plane list moves the memory figure while the default is to hold the entire log. The two knobs that do are already here and both are off:

• memory_pages bounds the anonymous pages and evicts above it
• map_settled turns a settled page into a read only mapping of the file it is byte for byte identical to, which puts it outside the bound, and the doc says the pair of them together say what lmdb says: the cache is the kernel's job and the bound is on what the database keeps for itself

So the question this issue actually has to answer is what those two default to, not what a node costs. And the evidence that a bound is close to free is already on #636: on server3, workload C at 200000 records and 4 threads, a 5 page bound of 20 MiB still did 25742.2 ops against sqlite's 3544.7. That is a fiftyfold cut in held memory for a number that is still seven times the rival.

The four arm A/B on #757, off and on and bound and bound plus mapping, is exactly the measurement that decides this, and it is queued on server3 behind the sqlite E retake. Nothing here should change until it lands. What changes now is what this issue is about: the default eviction policy, with the plane sizes as the second order term they are.