Published
Last week we packed Galactus DB a smaller suitcase and celebrated a third less memory. Then we did what everyone does after a holiday: we turned the suitcase upside down to check the pockets.
There was a lot more in the pockets.
Galactus DB 1.5.5 takes another 19 to 31% off what a database holds in memory, compared with 1.5.0, on our benchmark graph and three public example datasets. A database kept entirely in memory uses about 16% less. Loading is a little quicker, queries are as fast or faster, and nothing on disk has changed.
What was in the pockets?
Every node was carrying its own packing list
Each node and relationship kept a little list of its property keys, so it could
answer "do I have a name?" without asking anyone. But the property store
already knew the answer, because it holds the values. That was like writing
your home address on every sock. The lists are gone, and the property store is
now the only place keys live, so they can never disagree with the values.
Every property had a spare copy of its receipt
In a Hybrid database, values live on disk and memory keeps a note of where each one is. That note was 24 bytes, and 8 of them were a copy of a checksum that is already written next to the value on disk. We stopped carrying the copy. Reads still check every value against the checksum on disk, and still check it belongs to the node and key that asked for it. The note is now 12 bytes.
Most nodes pack the same things
Look inside a graph and you will find that nodes with the same labels nearly
always have the same keys. Every :Person has a name, an age and an
email; every KNOWS has a since. Across six public example datasets with
up to 1.3 million elements we found between 2 and 180 distinct combinations of
keys. So 1.5.5 writes each combination down once, as a shape, and every
node that matches it points at the shape and keeps only its values.
Shapes cost a 4-byte id per element and save 4 bytes on every property, so they pay for themselves from two properties up, which covers almost every node you are likely to meet. They are on by default. They only exist in memory, so they never touch your files and replicas never notice them.
The wins
| 1.5.0 | 1.5.5 | ||
|---|---|---|---|
| Benchmark graph (200k nodes, 400k relationships) | 152 MB | 109 MB | −29% |
| fraud-detection (333k nodes, 980k relationships) | 206 MB | 144 MB | −30% |
| recommendations (29k nodes, 166k relationships) | 42 MB | 29 MB | −31% |
| network-management (84k nodes, 182k relationships) | 36 MB | 29 MB | −19% |
| In-memory engine, benchmark graph per node | 785 bytes | 662 bytes | −16% |
The network-management graph saves least because its elements carry few properties: less luggage, less to tidy.
Taking things out of memory usually costs speed. This time it didn't:
Grouping by a property takes 13% less time and a one-hop expand 9% less, partly because there is less memory to walk through and partly because adding or changing many properties in one transaction got cheaper. Loading nodes is 4% quicker. An index seek came out level, within a fraction of a per cent.
How we measured
The memory figures are the live heap a reopened database holds, measured with a counting allocator, using the Hybrid storage engine (the server default) with its property cache switched off, so they show the database's own structures rather than how full a cache is. The speed figures are medians of eight rounds that alternated between versions on the same data, pinned to the same CPU cores, with buffered durability and one query worker. Both versions were built with the same release settings and run on an Intel Core i9-13900K with 64 GB of RAM on Windows 11. The example datasets are public sample graphs imported as they are.
Upgrading
Pull and restart:
docker pull ianknowles/galactus-db:1.5.5
The data, commit log and snapshot formats are unchanged, so 1.5.0 and 1.5.5 open each other's databases. The image is still under 9 MB, and a 3.4 MB download.
If you would rather keep the old layout, start the server with
GDB_PROPERTY_SHAPES=false. Because shapes only live in memory, you can switch
at any restart, in either direction, without touching your data.
What's next
The property cache. Its budget counts each value's size on disk rather than what the cached copy really costs, so the default "16 MiB" holds a good deal more than that. We want the setting to mean exactly what it says without giving back any speed, and we will write about it when it is done.
Two releases, two suitcases. We may need a smaller car.