v0.3.31

Ten pull requests and no milestone has closed, so this is a patch.

Two things dominate it. Cluster mode arrives in four pieces, going from a server that knew nothing about any other server to a node that joins a cluster of real Redis 8.10.1 nodes, is treated as an ordinary member of it, and can hand a slot to a neighbour and take one back. And the write path stops being the slowest thing in this build: the arena was grow only between compactions, so every overwrite that changed a value's length left a hole nothing could ever use and a collector copying live records around it, which on the cache benchmark's own workload cost nine gigabytes copied to write three. Freed space now goes back into circulation directly, which is 2.47x the SET rate on the box that measurement was taken on. The rest is replication finishing its second half, a deliberate failover, and two fixes to how connections and work land across the I/O threads. Nothing here changes the on-disk format and no record kind was added.

Added

• Cluster mode: slots, the routing table and the redirections. Every key belongs to one of 16384 slots, worked out from CRC16 of the key modulo 16384 with the hash tag rule on top, and every node knows which node owns which slot. There is no coordinator and no lookup service, so the whole of routing is that function and that table. The hash tag edge cases are all here because they are the only way a client has of making two keys land together, which is the only way a command naming two keys can run at all: a brace with no closing brace hashes whole, {} is not a tag, and only the first closing brace after the first opening one counts, so {a}{b} hashes a. The slot table is written out rather than computed at startup, because every key on the command path goes through it and a table in the binary is already in cache when the first command arrives. Beside it are two more tables for the slots that are moving, and a gate that runs after the ACL check and answers MOVED or ASK.
• The cluster bus. The binary protocol nodes talk to each other over, on the client port plus ten thousand, in the wire format 8.10.1 uses. A 2256 byte header carrying the signature, the length, the protocol version, the sender id, its slot bitmap, its epochs, its replication offset, its flags and its state, then either a gossip section of 104 byte entries or a typed body. PING, PONG and MEET carry gossip, PUBLISH and PUBLISHSHARD carry a channel and a message, and FAIL, UPDATE and the failover messages carry what their names say. The extension block on a ping carries the shard id and the internal secret, both padded to eight bytes the way getAlignedPingExtSize does it, and the secret converges on the lexicographically smallest one anybody has seen. A listener thread and a cron thread on a hundred millisecond tick run it, and a yo node now joins a cluster of real Redis nodes rather than being a node that thinks it is alone.
• Moving a slot between two nodes. RESTORE-ASKING, which is the third of a slot migration's four steps and the one that was missing: MIGRATE sent keys across and got MOVED back for every one of them, because the receiving node does not own the slot yet and a plain RESTORE arriving there is redirected straight back. The sender switches to that spelling on one condition and nothing else, whether it is a cluster node, so a MIGRATE between two servers not in a cluster still sends the ordinary word and still works against a server too old to have heard of the other one. The routing gate reads the command's own asking flag rather than knowing the name.
• The internal connection. AUTH "internal connection" <secret> is not a login as a user: the secret is the forty characters the bus gossips until the whole cluster agrees on one, so a client cannot get past it without knowing something only the nodes know, and a server that is not a cluster node has no secret at all and says so before it looks at what it was sent. The name is compared exactly rather than as a keyword, which is the reference, so AUTH "INTERNAL CONNECTION" is an ordinary failed login and reads like one. CLUSTER SYNCSLOTS is what that opens, and a connection that is not a node gets the refusal and then gets hung up on.
• Replication, the replica half. The other side of the master half from 0.3.30. REPLICAOF and SLAVEOF do it at runtime and --replicaof HOST PORT does it at startup, with --masterauth and --masteruser for a master that wants a password and --replica-read-only deciding whether an ordinary client may write while the server follows somebody, which is yes by default because a write that lands on a replica is one the master never hears about and the next full resync throws away. The link is one thread and one socket rather than a place on the reactor, because the handshake is a handful of blocking round trips and the snapshot is one very large read, and neither is the shape an event loop measured in nanoseconds per command wants. What arrives is a stream of ordinary commands and what runs them is the ordinary dispatcher through a session the link owns, which is the point rather than a shortcut: a replica applying writes through a second path would be a second implementation of every command.
• FAILOVER, handing the master's job over on purpose. Everything else about replication is a machine that keeps running when a server dies, and this is the case where nobody has died and an operator wants the master somewhere else. Three steps and the order is the whole trick. The master stops accepting writes, not by closing anything but with the same pause CLIENT PAUSE arms, so a write that arrives is held on its connection and the client sees a slow command rather than a failure, and reads carry on. Then it waits for a replica to acknowledge every byte it has ever written, which is a wait that finishes because nothing is being written any more. Then it becomes a replica of that one and tells it to become the master in the same breath, with a PSYNC carrying a fourth word, FAILOVER, that a replica promotes itself on before answering.
• The yo-cli serve bench can measure writes. It could only send GETs, and #518 was about SETs, so the one number the threading milestone was stuck on could not be reproduced on whatever machine is in front of you, which is the whole point of that bench existing. YO_BENCH_OP picks what the measured window sends, YO_BENCH_OP_AGAINST sets the far side of a pair so the ratio between a write and a read comes out of one paired measurement rather than two absolute ones taken minutes apart, and YO_BENCH_SIZE now takes a range as well as a number, so YO_BENCH_SIZE=1-1024 is memtier's --data-size-range and means the same thing here as in the harness. That last one is a different setting from a fixed 1024 rather than a longer one, and the difference is the point.

Changed

• The arena reuses freed runs. Arena::free used to be a counter: it raised the owning segment's dead byte total and nothing else, so a freed run was space no allocation could land on again and the only way space came back was compaction, which empties a segment by copying every live record out of it. At the quarter it starts from that is three bytes moved for every byte reclaimed. A freed run now goes on a list of runs of exactly its size and the next request for that size takes it back, with no copying, no index write and nothing left for a collector to do. The links live in the freed run itself, because a vector per size class would grow and growing is a call to the system allocator on a command path, which Y7 forbids. Runs under 32 bytes have nowhere to keep the links and stay off the lists. Doubly linked, so that a segment being reclaimed can take its runs off in constant time, which compaction now does as it walks. INFO memory gains mem_arena_listed, the number of runs waiting on a list, which beside mem_compact_bytes says which of the two collectors is doing the work.
• Connections are shared out by how many each thread is already holding. Every worker has the listeners in its own poller and keeps a connection for as long as it is open, so how connections land is how work lands. A worker that has just accepted is awake and running while the others are coming back from a wait, so it wins the door again and again: at sixteen threads over a unix socket with 256 connections, one thread took 215 of 771 accepts and another took 22, and the command counts follow the accept counts exactly. A worker now steps out of the queue for the doors once it is holding more than the fewest any of them is holding, and steps back in when it is level, which turns a burst into round robin with no turn counter anywhere.
• The load generator's per thread times are reported. Every run of the sweep records how long each of its threads ran for, and the ratio of the longest to the shortest is now in the output. That is what made the imbalance above visible rather than inferred: yo sat at 1.00 on one thread and was the loosest engine on the board above one, at 1.68 on eight and 1.80 on sixteen against 1.00 to 1.08 for everything except rugo, and individual runs were worse than the medians at 12.75 and 8.05.

Performance

• 2.47x the SET rate on the cache benchmark's own workload, and ten percent less resident memory. Development measurement, not a gate number. Eight core AMD EPYC virtual machine, 24 GB, server pinned to cores 0 to 3 and memtier 2.5.1 to cores 4 to 7, two I/O threads, pipeline 50, 2.5 million keys, values drawn from 1 to 1024, --maxmemory 8gb. Before, 138257 sets a second at 1529 MB resident with 7200775196 bytes copied by compaction over the measured pass. After, 341955 sets a second at 1383 MB with compaction not running at all, mem_compact_walked and mem_compact_bytes both exactly zero. Paired three times alternating, 120527, 113961 and 132809 against 224436, 279573 and 251397. The fixed length cell is the control and is unchanged, 518042 against 549343 with nothing listed and no compaction on either side.
• The GET column of those runs moves around by as much as 1.5x and none of it is this change. The second binary of a pair meets a warmer box, and running the fixed length cell with the order reversed puts the win on the other foot on a cell where the two binaries provably do identical work.

Known gaps

• The three number gates on the threading milestone are all still unticked. What is above is one cell of one box measured once, not thirty one runs a cell with the coefficient of variation reviewed, and the sweep that would settle it has not been run since the arena changed.
• About half of the remaining write path gap is the out of place write itself rather than the collector. With compaction turned off, the old binary still only reached 272 thousand on that cell against 605 thousand for a fixed length overwrite, which is two index probes instead of one, the header and the key copied again, the tagged set moved, and fresh pages faulted in.
• The per batch memory reading takes a lock on every stripe of all sixteen databases and asks each for seven running totals, which was 3.86 percent of cycles on the profile taken for #518. Fifteen of those databases are empty on every benchmark cell there is.
• 0.3.28 has a tag, no crates.io release and no GitHub release, from a probe that timed out on 8 September. It is being left as a gap rather than published out of order behind 0.3.30, and the retry that stops it happening again went in with 0.3.30.