Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Kivaloo Data Store

tarsnap.com

Post reply on HN
Print view View original

41–50 of 78 posts

Re: The Kivaloo Data Store

#41

Post by cperciva »

jasonwatkinspdx wrote: post #37
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?

I don't think I wrote much documentation about this, sorry. Basically the idea is that there's a pointer which moves through the key-space looking at pages, and if it passes any pages which are "old" it marks them as dirty so that they're rewritten as part of the next batch. The rate at which the cleaning pointer moves through key-space depends on the accumulated "cleaning debt", which is based on the amount of garbage along with the current I/O rate; the aim is to hit a steady-state where the total amount of I/O is constant and the cleaning gets the "left over" I/O after requests are serviced.

Re: The Kivaloo Data Store

#42

Post by cperciva »

ignoramous wrote: post #36
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? 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 thi…

Do you mean with the OS file cache disabled?

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.

Re: The Kivaloo Data Store

#43

Post by jasonwatkinspdx »

cperciva wrote: post #41
jasonwatkinspdx wrote: post #37

Earlier quoted context omitted.

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

I don't think I wrote much documentation about this, sorry. Basically the idea is that there's a pointer which moves through the key-space looking at pages, and if it passes any pages which are "old" it marks them as dirty so that they're rewritten as part of the next batch. The rate at which the cleaning pointer moves through key-space depends on the accumulated "cleaning debt", which is based on the amount of garba…

Thanks! I'll check out the code in a bit, but that context will help.

Re: The Kivaloo Data Store

#44

Post by OJFord »

> Kivaloo (pronounced "kee-va-lieu")

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!

Re: The Kivaloo Data Store

#46

Post by cperciva »

OJFord wrote: post #44

> Kivaloo (pronounced "kee-va-lieu") 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',…

Maybe we disagree about how to pronounce the word "value". I pronounce it roughly "val-ee-oo" but maybe you pronounce it simply as "val-oo"?

Re: The Kivaloo Data Store

#48

Post by dfischer »

ALittleLight wrote: post #30
nwsm wrote: post #28

Earlier quoted context omitted.

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

Paul Graham tweeted yesterday[1] an essay that the author had written which references kivaloo. At least, that's how I came to know about it yesterday. 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 simila…

For DHT’s? BitTorrent Kad

Re: The Kivaloo Data Store

#49

Post by axaxs »

cperciva wrote: post #46
OJFord wrote: post #44

> Kivaloo (pronounced "kee-va-lieu") 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',…

Maybe we disagree about how to pronounce the word "value". I pronounce it roughly "val-ee-oo" but maybe you pronounce it simply as "val-oo"?

I'm ashamed to admit I didn't get the connection of the name to "key value" until this comment. So do you yourself pronounce it kee va loo or kee va lyoo? As an American, I see no distinction between the sounds of 'loo' and 'lieu'.

Re: The Kivaloo Data Store

#50

Post by OJFord »

cperciva wrote: post #46
OJFord wrote: post #44

> Kivaloo (pronounced "kee-va-lieu") 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',…

Maybe we disagree about how to pronounce the word "value". I pronounce it roughly "val-ee-oo" but maybe you pronounce it simply as "val-oo"?

Er, neither really, 'val-you'. Two syllables, definitely not three, but there is a 'y'.

Rhymes with pew, few, you, new, yew, Kew, etc.

Post reply on HN