Background
lm2 is my ordered key-value storage library. You can read my post
about it here. There’s a lot to say about this little
library, so this will be the first of a few posts about how lm2
works and why I chose to do things a certain way.
Caching
lm2 is essentially a linked list on disk. Everyone knows linked
lists aren’t very fast. Searches take a ridiculously long time
and require a lot of seeking. That’s why lm2 has a record cache,
which stores a subset of the key-value records in memory. This
cache really speeds up searches, but it’s used for much more.
It’s also used for the write path. All writes in lm2 happen in
memory before they’re durably recorded to disk.
There is only one level of caching at the moment. If you think
about it, the architecture looks like a 2-level skip list.
A cache like …
[Read more]