The Kivaloo Data Store
tarsnap.com
tarsnap.com
For reference, on my laptop (Dell Latitude 7390 with an i7-8650U CPU):
* Bulk inserts run at ~600,000/second (up from 125,000).
* Bulk extracts run at ~660,000/second while in RAM (up from 30,000) and ~220,000/second from disk (up from 20,000).
* Bulk updates run at ~700,000/second in RAM dropping to ~300,000 from disk (up from 110,000 dropping to 60,000).
* Random reads run at ~800,000/second in RAM dropping to ~20,000 from disk (up from 220,000 dropping to 11,000).
* Random mixed run at ~400,000/second in RAM dropping to ~10,000 from disk (up from 30,000 dropping to 4,000).
* Hot-spot reads run at ~800,000/second in RAM dropping to ~500,000 from disk (up from 220,000 dropping to 60,000).
Note that "in RAM" means "the dataset fits into RAM" -- in all cases data is durably stored to disk.
There is almost certainly room for improvement; I haven't done extensive profiling yet.
Does the fact that you're still maintaining Kivaloo this many years later imply it's now being used by Tarsnap?
The Kivaloo page notes that it was designed for Tarsnap, but I'm curious as to the "why" - eg, an eventual-consistency/consensus building block, a simple local metadata service, server-side housekeeping...?
(I'm also curious what "{indexed ,}sorted files" means, and how UFS is significant.)
Do you mean with the OS file cache disabled?
Other questions:
1. What are, off top of your head, some design changes or code changes required that'd bring drastic performance improvements?
2. What are some key internals that you think differentiate Kivaloo from other embedded KV stores? I assume you must have gone through a lot of existing literature on the topic before building this. For example, LMDB, BDB, RocksDB, LevelDB, SQLite and the likes come to mind that can double-up as KV stores.
3. Does it store the database in flat files with a WAL in front? Is the file format of the database custom, or based on existing formats?
4. Does the database auto index the fields? Or, use any other such aids to speed up access to data?
Thanks.
No, I mean with a dataset which is too large to fit into the amount of RAM on the system.
1. What are, off top of your head, some design changes or code changes required that'd bring drastic performance improvements?
Nothing immediately comes to mind. Profiling may reveal some improvements, of course.
2. What are some key internals that you think differentiate Kivaloo from other embedded KV stores? I assume you must have gone through a lot of existing literature on the topic before building this. For example, LMDB, BDB, RocksDB, LevelDB, SQLite and the likes come to mind that can double-up as KV stores.
Well... kivaloo isn't an embedded KV store, so that would be a big differentiating factor. It's a network daemon.
3. Does it store the database in flat files with a WAL in front? Is the file format of the database custom, or based on existing formats?
The "on-disk" format is the pages of a append-only B+Tree, with the last page being the tree root.
I put "on-disk" in scare quotes because there are other backends, e.g. using Amazon DynamoDB to store pages.
4. Does the database auto index the fields? Or, use any other such aids to speed up access to data?
There are no fields. Key-value pairs, nothing more.
You might not get the same level of sophistication right away, of course, but that's just a matter of time and diligence.
A few questions:
- Why 255 bytes to 255 bytes? Does this have any performance consequences?
- Your laptop is SSD right?
- Is there any more documentation on how to use Kivaloo? (not just facts about it)
Yes, my laptop has a Intel 660p 512 GB NVMe disk.
No documentation per se, although I hope the library interfaces are reasonably understandable. I'd be happy to help though -- this code deserves to be used!
But if you're willing to make those adjustments and use 64 kB pages, I imagine it would work just fine. Please stay in touch!
This restriction could be relaxed, e.g. to require only that internal nodes are at least 2/3 full, in which case for the small key / large value case you could have pages which are barely larger than the largest value. I didn't bother doing that since it wasn't relevant to my usage.
FYI, that's a very American English centric way of explaining how to pronounce 'loo'!
British English pronounces the lone word 'lieu' differently (with a y/j in front of the 'ū'), as in 'lieutenant' as 'leff', and is already familiar with 'loo's and pronounces them 'loo'.
'lieu' is of course of French origin, and they pronounce it differently again.
It's obvious, given 'kivaloo', how it's supposed to be. But unless it's a deliberate joke I think repeating 'loo' is a better pronunciation key!
Rhymes with pew, few, you, new, yew, Kew, etc.
If I see "loo" absent context I would normally pronounce it without that intervening sound. Whereas "lieu" has it.
Now I'm confused over whether Kivaloo is '~oo' as I assumed, or (roughly, weaker 'y') '~yoo' as I think we agree 'lieu' is?
I was wondering if that is a common Canadian pronounciation.
Wiktionary suggests Canada generally follows the pronunciation your familiar with.
The last one is in jest. The word is pronounced the same--in the US, often the US is called America, seemingly excluding Canada, Central America, South America.
And a fact that I didn't know until recently was that the Philippines prior to WW II was part of the United States. See "How to hide an empire" by Daniel Immerwahr: https://www.amazon.com/How-Hide-Empire-History-Greater/dp/03...
I do commonly hear the expression "in lieu of" rendered "in loo of" but have always considered that incorrect, much like pronouncing the t in "often".
It is, of course, just dialect, and the entire idea of 'incorrect pronunciation' is suspect! But I can't help but consider /lyu/ to indicate a higher, er, register.
From my experience, the more north you go the more you talk with your tongue/mouth. In my examples I was almost able to complete full sentences without moving my lips at all.
> and is already familiar with 'loo's and pronounces them 'loo'.
It's not just (and predominantly not) the 'toilet' though, it's the room or facility; what you would call a 'washroom'.
Is there a way to compare it to other key-value stores in a fair apples to apples comparison?
https://news.ycombinator.com/item?id=7602237
https://news.ycombinator.com/item?id=9899766
https://news.ycombinator.com/item?id=13624926
https://news.ycombinator.com/item?id=13854431
https://news.ycombinator.com/item?id=18037613
Some other K/V stores often see ~Zipfian key distribution, e.g., a search index.
Limiting values to 255 bytes is quite constraining, to say the least.
Also, it seems that there are no transactions in kivaloo. That makes a big difference.
And sure, small values and a lack of transactions are intentional limitations which allowed me to improve performance for the use case I cared about. Of course there's nothing stopping you from constructing that functionality in other ways; in fact I'm planning on releasing a daemon which provides key-blob storage by storing large objects in Amazon S3 and using the core kivaloo functionality as an indirection table.
Interesting that the author is here commenting as well on a 9 year old project.
As for how I find it so quickly... I might spend too much time on HN...
I read the document on it, then tried to imagine what I would use it for, and couldn't really come up with a use case. I had trouble understanding where I would apply the 255 byte key to 255 byte value paradigm. I also didn't know how the benchmarks compared to similar applications.
One thought that comes to mind is a distributed store with centralized master, 255 bytes is plenty for a hostname and resource ID.
If they're hashes, sure. If you want to answer range requests -- e.g. "give me everything starting with ABCDEF" -- you may have a less densely utilized address space (rather like IP networking has had).
My accounting database has keys of the form "usage/"<256-bit user ID><20-byte timestamp><64-bit machine ID><usage type string>. Not 255 bytes, to be sure, but not trivially short either.
Kind of a reckless decision.
You mean the GPG-signed client code?
Edit: On second thought, I recognize this whole subthread started with the wrong tone ("ironic", "reckless"), kind of dismissive or patronizing and not calling for a constructive discussion, so please disregard this comment of mine, sorry.
Considering there's no disadvantage in deploying HSTS and there's no good reason to serve an insecure website, especially since they already have HTTPS set up, I'm baffled by that decision. Maybe it's just an oversight but that's not too reassuring either.
HTTPS+HSTS adds no security here.
The only (reasonable) way to validate a payload end-to-end is an offline signature validation. This is true regardless of transport-level security measures like HTTPS.
Doing this properly with gpg makes even more sense due to the service targeting the paranoid, who is exactly the group of individuals who are certain to validate a signature.
> Considering there's no disadvantage in deploying HSTS and there's no good reason to serve an insecure website, especially since they already have HTTPS set up, I'm baffled by that decision. Maybe it's just an oversight but that's not too reassuring either.
It's easy, but adds nothing in ways of security here. Just privacy.
(Not that privacy does not have value, of course, but that's an entirely different argument.)
(However, Encrypted SNI is not widely adopted yet.)
Hardly surprising that it didn't gain much traction.