The Kivaloo Data Store • Hacker News Board

Re: The Kivaloo Data Store

#31

Post by tedunangst » Mon, Sep 21, 2020, 8:47 PM UTC

quixoticaxolotl wrote: post #23

cperciva wrote: post #2

Note: The performance values mentioned on that page (on an EC2 c1.medium instance using spinning-rust disks!) is wildly out of date. I'll get around to updating them some day. 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).…

Have you ever considered getting a Jepsen test done for kivaloo? The claims re: durability and linearizability are worth proving out that way

Correct me if wrong, but kivaloo isn't distributed. Jepsen seems fairly overkill without replication, partition, etc.

Re: The Kivaloo Data Store

#32

Post by cperciva » Mon, Sep 21, 2020, 8:50 PM UTC

tedunangst wrote: post #31

quixoticaxolotl wrote: post #23

Earlier quoted context omitted.

Have you ever considered getting a Jepsen test done for kivaloo? The claims re: durability and linearizability are worth proving out that way

Correct me if wrong, but kivaloo isn't distributed. Jepsen seems fairly overkill without replication, partition, etc.

You are correct, as things are at the present time. I designed kivaloo to be composable with the intention that I could put a replication/sharding layer in front of it later, however.

Re: The Kivaloo Data Store

#33

Post by cperciva » Mon, Sep 21, 2020, 8:52 PM UTC

nwsm wrote: post #28

cperciva wrote: post #20

Earlier quoted context omitted.

I didn't bother doing releases for a while, since nobody else (AFAIK) was using the code.

No worries there, I was just wondering out loud why OP posted, and how you found the thread so quickly

I assume this and a lower-voted thread were both fallout from my front-page post yesterday.

As for how I find it so quickly... I might spend too much time on HN...

Re: The Kivaloo Data Store

#34

Post by cperciva » Mon, Sep 21, 2020, 8:53 PM UTC

remram wrote: post #16

jnwatson wrote: post #11

I would be curious how this compares to LMDB. They both use B+Trees (which are just B-trees with siblings linked). 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.

B+tree is a B-tree with no data except at the leaves, and with sibling leaves linked.

The "sibling leaves linked" criterion is optional for B+trees. Kivaloo does not do that (it isn't possible for an append-only data structure).

Re: The Kivaloo Data Store

#35

Post by koolba » Mon, Sep 21, 2020, 9:22 PM UTC

cperciva wrote: post #4

aclindsa wrote: post #3

Earlier quoted context omitted.

> It was designed to satisfy the needs of the Tarsnap online backup service for high-performance key-value storage, although it is not yet being used for that purpose Does the fact that you're still maintaining Kivaloo this many years later imply it's now being used by Tarsnap?

Tarsnap has recently started using Kivaloo. Over time I intend to use it far more -- but since Tarsnap is a backup service, I'm starting with the least critical parts first.

It wasn’t using it till now? What was the equivalent component previously?

Re: The Kivaloo Data Store

#36

Post by ignoramous » Mon, Sep 21, 2020, 9:25 PM UTC

cperciva wrote: post #2

Note: The performance values mentioned on that page (on an EC2 c1.medium instance using spinning-rust disks!) is wildly out of date. I'll get around to updating them some day. 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).…

> ...dropping to ~20,000 from disk

Do you mean with the OS file cache disabled?

Re: The Kivaloo Data Store

#37

Post by jasonwatkinspdx » Mon, Sep 21, 2020, 9:34 PM UTC

cperciva wrote: post #2

Note: The performance values mentioned on that page (on an EC2 c1.medium instance using spinning-rust disks!) is wildly out of date. I'll get around to updating them some day. 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).…

Is there a place I could learn more about how the background cleaning works?

Re: The Kivaloo Data Store

#38

Post by morelisp » Mon, Sep 21, 2020, 9:36 PM UTC

cperciva wrote: post #7

koeng wrote: post #5

Earlier quoted context omitted.

These are actually some really good numbers for a certain application I'm looking at ( https://news.ycombinator.com/item?id=24191307 ), especially with bulk inserts being so high. 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)

The 255 byte limit is because I store keys and values as a one-byte length followed by the relevant data. For Tarsnap what I typically want is ~40 byte keys and data (hence using those sizes for benchmarking). 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!

Is the one-byte length central to some logic (or some performance concerns), or could one hack the `uint8_t` to a `uint16_t` in kvldskey and so on to get something that could store a bit more? We have some systems that need only 16-32 byte keys but upwards of around 16k values, we're currently using RocksDB but these performance numbers + no compaction process + mux approach are making me interested...

Re: The Kivaloo Data Store

#39

Post by cperciva » Mon, Sep 21, 2020, 9:37 PM UTC

koolba wrote: post #35

cperciva wrote: post #4

Earlier quoted context omitted.

Tarsnap has recently started using Kivaloo. Over time I intend to use it far more -- but since Tarsnap is a backup service, I'm starting with the least critical parts first.

It wasn’t using it till now? What was the equivalent component previously?

Many things for different purposes. Files in UFS filesystems. Sorted files. Indexed sorted files. In one case, Amazon SimpleDB.

Re: The Kivaloo Data Store

#40

Post by cperciva » Mon, Sep 21, 2020, 9:43 PM UTC

morelisp wrote: post #38

cperciva wrote: post #7

Earlier quoted context omitted.

The 255 byte limit is because I store keys and values as a one-byte length followed by the relevant data. For Tarsnap what I typically want is ~40 byte keys and data (hence using those sizes for benchmarking). 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!

Is the one-byte length central to some logic (or some performance concerns), or could one hack the `uint8_t` to a `uint16_t` in kvldskey and so on to get something that could store a bit more? We have some systems that need only 16-32 byte keys but upwards of around 16k values, we're currently using RocksDB but these performance numbers + no compaction process + mux approach are making me interested...

Interesting question. You would need to adjust kvldskey and all of the places where they are serialized (e.g. in pages and in the network protocol). You would also need a much larger page size -- the maximum key+value pair size has to fit into 1/3 of a page.

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!