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

51–60 of 78 posts

Re: The Kivaloo Data Store

#51

Post by exikyut »

cperciva wrote: post #39
koolba wrote: post #35

Earlier quoted context omitted.

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.

Out of curiosity, what was the use case/upstream requirement for building Kivaloo in the first place?

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.)

Re: The Kivaloo Data Store

#52

Post by exikyut »

cperciva wrote: post #40
morelisp wrote: post #38

Earlier quoted context omitted.

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!

Forgive my complete ignorance/inexperience, but why does the page size need to be increased to 64kB, and why does the key+value length(?) have to fit into 1/3 of a page?

Re: The Kivaloo Data Store

#53

Post by exikyut »

iamwil wrote: post #24

I was looking at this yesterday because of the post on "use of a life" post by cperciva. One thing on the benchmarks was I didn't know what was considered "good" numbers, even though I know it's dependent on the type of workload. Is there a way to compare it to other key-value stores in a fair apples to apples comparison?

(Note the current top comment with updated benchmark numbers, FWIW)

Re: The Kivaloo Data Store

#54

Post by cperciva »

OJFord wrote: post #50
cperciva wrote: post #46

Earlier quoted context omitted.

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.

Fair enough. Yes, two syllables, but there's a sound between the "val" and the "oo" parts.

If I see "loo" absent context I would normally pronounce it without that intervening sound. Whereas "lieu" has it.

Re: The Kivaloo Data Store

#55

Post by exikyut »

fisherjeff wrote: post #26

Is there somewhere I can nominate kivaloo for some sort of easily understandable code award? Granted I'm a little biased as it looks a lot like code I would write myself, but wow, it's so refreshing to see code that's full of (useful! illuminating!) comments. Thanks cperciva!

One potentially workable approach: mention it next time someone does a "good source code to read through?" thread, like one of these old ones:

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

https://news.ycombinator.com/item?id=18293159

https://news.ycombinator.com/item?id=20556336

Re: The Kivaloo Data Store

#56

Post by OJFord »

cperciva wrote: post #54
OJFord wrote: post #50

Earlier quoted context omitted.

Er, neither really, 'val-you'. Two syllables, definitely not three, but there is a 'y'. Rhymes with pew, few, you, new, yew, Kew, etc.

Fair enough. Yes, two syllables, but there's a sound between the "val" and the "oo" parts. If I see "loo" absent context I would normally pronounce it without that intervening sound. Whereas "lieu" has it.

For me that intervening sound is a hard 'y' though (as in 'yes') not long 'ee'.

Now I'm confused over whether Kivaloo is '~oo' as I assumed, or (roughly, weaker 'y') '~yoo' as I think we agree 'lieu' is?

Re: The Kivaloo Data Store

#57

Post by cperciva »

exikyut wrote: post #52
cperciva wrote: post #40

Earlier quoted context omitted.

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!

Forgive my complete ignorance/inexperience, but why does the page size need to be increased to 64kB, and why does the key+value length(?) have to fit into 1/3 of a page?

B+Tree leaf nodes contain keys and values. In kvlds (which is the core B+Tree component of kivaloo), the code aims to keep nodes at least 2/3 full, in order to keep the tree approximately balanced. If a key-value pair can take more than 1/3 of a page, you could have a situation where a node is less than 2/3 of a page but adding another key-value pair would take it above the maximum allowed size.

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.

Re: The Kivaloo Data Store

#58

Post by cperciva »

OJFord wrote: post #56
cperciva wrote: post #54

Earlier quoted context omitted.

Fair enough. Yes, two syllables, but there's a sound between the "val" and the "oo" parts. If I see "loo" absent context I would normally pronounce it without that intervening sound. Whereas "lieu" has it.

For me that intervening sound is a hard 'y' though (as in 'yes') not long 'ee'. Now I'm confused over whether Kivaloo is '~oo' as I assumed, or (roughly, weaker 'y') '~yoo' as I think we agree 'lieu' is?

It's pronounced "key-value". The "kee-va-lieu" thing was a joke. ;-)

Re: The Kivaloo Data Store

#59

Post by aidenn0 »

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…

255 bytes is obviously overkill for a key (a 32 or 64 byte secure hash of anything larger than 255 bytes can be assumed to unique), so it's just a question of what values are usefully in 255 bytes:

One thought that comes to mind is a distributed store with centralized master, 255 bytes is plenty for a hostname and resource ID.

Re: The Kivaloo Data Store

#60

Post by samatman »

axaxs wrote: post #49
cperciva wrote: post #46

Earlier quoted context omitted.

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'.

Also American, I pronounce loo /lu/ and lieu /lyu/, in IPA.

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.

Post reply on HN