Thread by @gallir

Something that nobody tells and I've learned the hard way: don't use radix trees if you have to delete nodes.

Consul and Vault use an immutable radix tree and that's why people complain of the everlasting massive keys' deletions. It's the tree.

radix trees are good for fast in-memory searches and adding nodes but very bad for deleting them. You will fall back to the old good BTrees.

But now we have copy-on-write btrees, so you can cheaply O(1) clone a tree, do the inserts in the close and then swap the roots...

And the reads will be fast as usual.
And so it finishes my report after sleeping 6 hours in 48 hours optimizing massive btrees operations ;)

Some details, massive trees in memory, for example in one node. Radix consumed 72 GB but sky rocketed to 140 for eternal deletions (expires)

Very fast for reading, average of < 10 ms but useless because expirations killed completely the system. Had to go back to btress...

Initially the average was higher that 10 ms, sad. But the I started to optimize it, first I moved the keys tree to a map. Although...

BTrees' fans will telly you that trees are often faster than hashing tables (map in Go) and that normally is O(k), it's a lie! A big lie.

For massive trees you really notice the difference of the (ish) O(1) vs the O(log n) of a tree. The map for the unique keys improved a lot.

Next I created two versions of every tree (one per index plus the expiration's) with a COW clone and switch them at the end of transactions

This also allowed me to get rid the reader lock for reads operations, now they are lockless!

At the end, similar or better response times than radixes', deletions are unnoticeable and it consumes < 30GB w/o increasing in deletions.

And this is the story of perhaps the best engineering work I ever made. I couldn't even stop for eating or sleeping, like a drug.

OTOH estoy solo en casa (toda mi familia de viaje), me da pereza salir o cocinar porque pierdo tiempo. Creo que perdí 2 kg en 3 días.