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

Storing hundreds of millions of simple key-value pairs in Redis

instagram-engineering.tumblr.com

Post reply on HN
Print view View original

41–50 of 55 posts

Re: Storing hundreds of millions of simple key-value pairs in Redis

#41

Post by qeorge »

cperciva wrote: post #40
qeorge wrote: post #36

Earlier quoted context omitted.

Gotcha. I'm not an OS guy, and didn't know that convention. Thanks! Dumb question though: If rehash can only return -1 or 0, won't if(rehash(H)) always fail?

Dumb question though... There's no such thing as a dumb question, only people too dumb to take every available opportunity to learn. ;-) In C, "if (foo)" means "if (foo != 0)" if foo has integer type, so that line means "if (rehash(H) != 0)" or (since rehash only returns 0 or -1) equivalently "if (rehash(H) == -1)".

Thanks so much Colin, I'm learning a lot today. :)

Re: Storing hundreds of millions of simple key-value pairs in Redis

#42

Post by cperciva »

nkurz wrote: post #39
cperciva wrote: post #35

Earlier quoted context omitted.

Very readable for something so dense. Nice work! Thanks! you could return 1 on success, and keep returning something falsy on failure I come from an OS background, so to me 0 is success and non-zero is failure. It doesn't really matter which convention a project uses as long as it's consistent, so I documented this in my /STYLE file: "In general, functions should return (int)(-1) or NULL to indicate error."

Both you and Salvatore have very readable code. I'm uncomfortable with having both 'H' and 'h' in the same function, and with using 'l' as a variable, but both of these files are exemplary C. Still, although it may just be personal preference, I give the slight edge to Salvatore on clarity. I have no real problem with 0 for success, but I'm with 'qeorge' on this. How is someone looking at only this function call supp…

I'm uncomfortable with having both 'H' and 'h' in the same function

To be honest, I don't like that either, and normally wouldn't do it. In this case I decided that the benefits of consistency with other code ([H]ash table structure; [h]ash of some data) outweighed the ugly near-collision.

How is someone looking at only this function call supposed to determine if rehash() returns an integer or a pointer?

If it returned a pointer, that line would have been "if ((foo = rehash(H)) == NULL)" -- I don't return pointers which aren't going to be used, and I don't write "if (pointer)". Again, it's a matter of knowing the house style.

I think even better would be to return KV_SUCCESS or KV_FAILURE (defined however you choose) and check explicitly

If it was just a matter of one function, that might be reasonable. But applying that to the entire project I'd have LBS_STORAGE_SUCCESS, LBS_WORKER_SUCCESS, LBS_DISK_SUCCESS, LBS_DISPATCH_SUCCESS, KVLDS_DISPATCH_SUCCESS, KVLDS_SERIALIZE_SUCCESS, BTREE_FIND_SUCCESS, BTREE_MUTATE_SUCCESS, BTREE_SUCCESS, BTREE_CLEANING_SUCCESS, BTREE_NODE_SUCCESS, MUX_DISPATCH_SUCCESS, NETBUF_SUCCESS, PROTO_LBS_SUCCESS, PROTO_KVLDS_SUCCESS, EVENTS_SUCCESS, WIRE_READPACKET_SUCCESS, WIRE_WRITEPACKET_SUCCESS, WIRE_REQUESTQUEUE_SUCCESS, UTIL_SUCCESS, ELASTICQUEUE_SUCCESS, PTRHEAP_SUCCESS, SEQPTRMAP_SUCCESS, and ELASTICARAY_SUCCESS. Plus all the _FAILUREs.

Much simpler to just say "0 is success, -1 is failure" once.

Re: Storing hundreds of millions of simple key-value pairs in Redis

#43

Post by petercooper »

First, I love Redis :-)

Second, this functionality seems to be a stop gap to support old users who may be using old clients. So they need an array of 300 million elements each containing an integer of 12 million or less. Assuming 32 bit values (24 would work but.. efficiency), that's a 1,144MB array which, in theory, could be stored as a file and cached through the filesystem cache.

I wonder how the performance of that would stack up against Redis. The convenience of Redis being a network daemon out of the box is potentially the big win here, though the memory usage even in the optimized case seems to be around 4x given that it's doing more than the task necessarily requires (from my interpretation of it - I could be wrong!)

Re: Storing hundreds of millions of simple key-value pairs in Redis

#44

Post by ryanpetrich »

mbreese wrote: post #28
simplify wrote: post #27

Earlier quoted context omitted.

In my opinion, if you can't figure out what a function does by its name and its parameter names, it is a poorly named and thus poorly documented function. I think function and variable naming is the one of the most important aspects of programming. Without good naming, you can easy double the amount of time it takes to edit and extend functionality.

A function may have the perfect name at the time you wrote it. It may make perfect sense within the context that you initially conceived of it. However, after some time away from it, when you're trying to mentally rebuild that context, it may make as much sense as def foo(). Good naming is important, but you also have to know the context, which is more difficult to remember.

If it only makes sense within the context it was conceived under, that's not a perfect name. A function name should make sense for someone with understanding of the domain, but no understanding of the code. When that's not possible, comments definitely help.

Re: Storing hundreds of millions of simple key-value pairs in Redis

#45

Post by nkurz »

cperciva wrote: post #42
nkurz wrote: post #39

Earlier quoted context omitted.

Both you and Salvatore have very readable code. I'm uncomfortable with having both 'H' and 'h' in the same function, and with using 'l' as a variable, but both of these files are exemplary C. Still, although it may just be personal preference, I give the slight edge to Salvatore on clarity. I have no real problem with 0 for success, but I'm with 'qeorge' on this. How is someone looking at only this function call supp…

I'm uncomfortable with having both 'H' and 'h' in the same function To be honest, I don't like that either, and normally wouldn't do it. In this case I decided that the benefits of consistency with other code ([H]ash table structure; [h]ash of some data) outweighed the ugly near-collision. How is someone looking at only this function call supposed to determine if rehash() returns an integer or a pointer? If it return…

That's fair, although it seems like in that case TARSNAP_FAILURE and TARSNAP_SUCCESS would then be a fine alternative.

I think the whole question is how much it's OK to have an house style that isn't immediately accessible, and how much that benefits the project. Is it really a benefit if outsiders can grasp the code immediately, or is it actually good to have a hurdle?

Do you have an argument against "rehash(H) < 0" other than the visual distraction? It seems like it would parallel better with a literal comparison to NULL.

Re: Storing hundreds of millions of simple key-value pairs in Redis

#46

Post by cperciva »

nkurz wrote: post #45
cperciva wrote: post #42

Earlier quoted context omitted.

I'm uncomfortable with having both 'H' and 'h' in the same function To be honest, I don't like that either, and normally wouldn't do it. In this case I decided that the benefits of consistency with other code ([H]ash table structure; [h]ash of some data) outweighed the ugly near-collision. How is someone looking at only this function call supposed to determine if rehash() returns an integer or a pointer? If it return…

That's fair, although it seems like in that case TARSNAP_FAILURE and TARSNAP_SUCCESS would then be a fine alternative. I think the whole question is how much it's OK to have an house style that isn't immediately accessible, and how much that benefits the project. Is it really a benefit if outsiders can grasp the code immediately, or is it actually good to have a hurdle? Do you have an argument against "rehash(H) < 0"…

TARSNAP_FAILURE and TARSNAP_SUCCESS would then be a fine alternative

Sure, until someone looking at kivaloo or spiped or scrypt asks "what the heck is tarsnap?" ;-)

house style that isn't immediately accessible

I think it's very likely that people working on the kivaloo code will have at least a passing familiarity with UNIX system call conventions, and would find my house style entirely accessible.

Do you have an argument against "rehash(H)

I would interpret that to indicate that the function has several potential return codes, not just 0 or -1.

Re: Storing hundreds of millions of simple key-value pairs in Redis

#47

Post by nknight »

pedigree wrote: post #16

Why use clear text numbers? Most of the time, you're going to be using large numbers, so binary pack them as save more space. i had the same issue, normal storage was 1.1gb of space, HSET down to 200mb and binary packing every integer down dbl() bought it right down to 163mb of memory (32bit instance). For that 163mb, I was slicing a md5 of the field for the hset prefix, packing that and then using the remainer as th…

Redis is a series of tradeoffs between simplicity, performance, and power. For the moment, simplicity won as far as keys go -- they're all strings, period, end of story.

Supporting other key types is potentially useful, but brings complications, some of which will be visible to users of Redis.

Your own measurements are telling. Your memory usage went down by about 82%, packing the integers brought that to a bit less than 86%. It's easy to justify a small increase in complexity to save 82%, it's a lot harder to justify even more complexity to bring that number to 86%.

Re: Storing hundreds of millions of simple key-value pairs in Redis

#48

Post by catwell »

pjscott wrote: post #29
catwell wrote: post #12

Lookups are not really O(1), they're O(number of keys per hash) as long as the hashes are zipmaps. When they become full blown hashes the memory usage increases. Still, this is a very good way to store a lot of key/value pairs in Redis.

Big-O notation refers to asymptotic behavior. The zipmap encoding of hashes only matters for small values bounded by a constant, so hash lookups are still expected O(1) time in Redis.

Your point would be valid if the memory gain observed was not directly dependent on the fact that hashes are zipmap-encoded. So the trade-off here is between the constant factor of time complexity and the constant factor of memory complexity.

Re: Storing hundreds of millions of simple key-value pairs in Redis

#49

Post by catwell »

cperciva wrote: post #25
Retric wrote: post #20

Earlier quoted context omitted.

I wonder how individualistic that really is. I like well documented code, I don't trust that documentation to be accurate so I don't include it in my readability score. I like to have around 10 to 40 lines per function, reasonable levels of reuses, a reasonable overall structure and function depth to stay reasonable aka f1 call f2... calls f10 is fine, f1 calls f2... calls f40 smells bad. f1 calls f2 calls f1 is fine…

I generally don't trust external documentation, but I do trust in-line comments.

You're probably wrong. Look at the comment above "stretches" here: https://github.com/binarylogic/authlogic/blob/master/lib/aut...

This is crypto-related code in of the most popular Rails authentication gems. And this is one among many examples. I'm sure you've already come across something like that more than once.

I trust code rather than comments. At least it doesn't lie.

Re: Storing hundreds of millions of simple key-value pairs in Redis

#50

Post by vijaydev »

catwell wrote: post #49
cperciva wrote: post #25

Earlier quoted context omitted.

I generally don't trust external documentation, but I do trust in-line comments.

You're probably wrong. Look at the comment above "stretches" here: https://github.com/binarylogic/authlogic/blob/master/lib/aut... This is crypto-related code in of the most popular Rails authentication gems. And this is one among many examples. I'm sure you've already come across something like that more than once. I trust code rather than comments. At least it doesn't lie.

Fixed :-) https://github.com/binarylogic/authlogic/commit/f52a699bbc9e...
Post reply on HN