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

31–40 of 55 posts

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

#31

Post by cperciva »

simplify wrote: post #27
cperciva wrote: post #24

Earlier quoted context omitted.

I tend to add comments where my code risks to be not clear by itself I used to take that position, but I've started adding more comments in order to avoid "mental stack overflows". Suppose I'm reading function A and trying to understand it, then I find a call to function B which doesn't have any comment explaining what it does; I then go look at function B, and find it has a call to function C which is equally lackin…

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.

There's a tradeoff in the naming of functions. If you have lots of functions named functionWhoseNameMakesItVeryClearExactlyWhatItDoesToItsParameters(), your code will end up being hard to read simply by virtue of the volume of text people need to read through. I prefer to have gist_of_functionality() with more details easily accessible in an obviously-placed comment.

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

#32

Post by LeafStorm »

eurleif wrote: post #17
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…

Internally, redis stores integers as 64-bit binary values, not strings: http://redis.io/commands/incr .

I don't think it does that for keys and values in hashes though. The only int-related optimization it does in the collections is integer sets.

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

#33

Post by sbov »

simplify wrote: post #27
cperciva wrote: post #24

Earlier quoted context omitted.

I tend to add comments where my code risks to be not clear by itself I used to take that position, but I've started adding more comments in order to avoid "mental stack overflows". Suppose I'm reading function A and trying to understand it, then I find a call to function B which doesn't have any comment explaining what it does; I then go look at function B, and find it has a call to function C which is equally lackin…

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.

I don't understand how you can really have a function name that properly says what it does without it being overly long.

In particular, function names seem to focus more on expressing the postcondition but make no mention of preconditions, exceptions, error conditions - all which also need to be known when figuring out what a function does.

In other words, strlen becomes strlen_segfaultifstrnull. You could theoretically encode that in the parameter name, but it becomes even messier when you have functions that raise exceptions. And now instead of long function names, all your functions are using long variable names that serve no purpose other than documenting said error conditions.

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

#34

Post by qeorge »

cperciva wrote: post #15
mikeyk wrote: post #13

Earlier quoted context omitted.

Honestly, it was mostly the concision that struck me at the time. Looking at the zipmap source now, I think it's more or less where my code tends to end up in terms of comments--some motivation / higher-level comments at the top, and most functions have a comment before, hopefully with some explanation of any edge/NULL cases as well. Any open-source projects you'd point to as good examples of what looks readable to y…

I like to think that most of my recent code is pretty readable. The largest chunk of open source is my kivaloo data store ( http://www.tarsnap.com/kivaloo.html , browsable svn repository at http://code.google.com/p/kivaloo/source/browse/ ).

Very readable for something so dense. Nice work!

One suggestion from the peanut gallery:

In http://code.google.com/p/kivaloo/source/browse/trunk/lib/dat..., at line 178 you have:

    if (rehash(H))
        goto err0;
That's because rehash returns 0 upon success, and -1 on failure.

To me, that's very confusing, because it reads to be erroring upon success. When I read rehash's body, I learn that 0 means success and -1 means failure.

I'd prefer one of two methods. First, you could return 1 on success, and keep returning something falsy on failure. Then the code would read:

    if (!rehash(H))
        goto err0;
Which I think is more readable. Perhaps even better would be to use a constant, i.e.,

    if (rehash(H) != REHASH_SUCCESS)
        goto err0;
although that can easily lead to a mess of redundant constants, or a headache managing them.

Just my personal preference. Really nice code, thank you for sharing it.

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

#35

Post by cperciva »

qeorge wrote: post #34
cperciva wrote: post #15

Earlier quoted context omitted.

I like to think that most of my recent code is pretty readable. The largest chunk of open source is my kivaloo data store ( http://www.tarsnap.com/kivaloo.html , browsable svn repository at http://code.google.com/p/kivaloo/source/browse/ ).

Very readable for something so dense. Nice work! One suggestion from the peanut gallery: In http://code.google.com/p/kivaloo/source/browse/trunk/lib/dat... , at line 178 you have: if (rehash(H)) goto err0; That's because rehash returns 0 upon success, and -1 on failure. To me, that's very confusing, because it reads to be erroring upon success. When I read rehash's body, I learn that 0 means success and -1 means fail…

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

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

#36

Post by qeorge »

cperciva wrote: post #35
qeorge wrote: post #34

Earlier quoted context omitted.

Very readable for something so dense. Nice work! One suggestion from the peanut gallery: In http://code.google.com/p/kivaloo/source/browse/trunk/lib/dat... , at line 178 you have: if (rehash(H)) goto err0; That's because rehash returns 0 upon success, and -1 on failure. To me, that's very confusing, because it reads to be erroring upon success. When I read rehash's body, I learn that 0 means success and -1 means fail…

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

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?

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

#37

Post by josephg »

antirez wrote: post #22
cperciva wrote: post #10

Earlier quoted context omitted.

I'm curious, what in particular makes you say that code is "readable"? Coding style varies dramatically from person to person, and I don't mean this as a criticism of antirez, but any code which doesn't have at minimum a one-line comment before each function explaining its purpose immediately fails the "readability" test for me. Obviously this isn't a problem for you, so I'm curious to hear what your tastes are.

Hi cperciva, I actually think that comments are not a so important part of code quality. I tend to add comments where my code risks to be not clear by itself, and the zipmap.c code is indeed more commented than my average code since it is all about encoding stuff in a binary blob string, playing with pointers, and so forth. So actually too much comments may even be a sign that something is bad about the code. IMHO go…

I used to consider most comments a sign of poorly factored code. (If you need comments, you've probably written your code in an obtuse way).

I started a new project a few weeks ago and went to the other extreme to see what it was like. I think I have more comments than code:

https://github.com/josephg/node-browserchannel/blob/master/l...

Rendered with docco: http://josephg.github.com/node-browserchannel/docs/server.ht...

The comments in this file also describe the spec of what I'm implementing and give running commentary on the implemention. It took me awhile to get used to writing like this, but I really like the result. When I want to add a function or something I talk about what I want to achieve in a comment block before writing the code.

Somehow, the whole feeling of programming is different. By making the documentation the highest priority, I feel like I'm writing rather than coding. (I hate writing generally, but I really enjoyed it here.)

I'm not sure if it helps or hinders readability. Obviously there's way more information in there about my intensions. You can tell if surprising behaviour in the code is intended or if its a bug. But the code has become really long and you have to scroll heaps to be able to move through the file. I feel like my monitor has shrunk. Maybe I just need to split the code out into more files.

I'm not sure if I want to program like this all the time; but I'm writing a lot more inline documentation now. When you get stuck trying to decide how to implement something, talking about the design choices in a block comment has the same effect as explaining the problem to a coworker. Only this way you don't bother your coworkers and you have documentation on the choice when you're done.

Its also a fun experiment because of how weird it feels - I highly recommend giving it a go sometime.

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

#38

Post by firefoxman1 »

minimax wrote: post #21
cperciva wrote: post #4

Best of all, lookups in hashes are still O(1), making them very quick. How quick is "very quick"? I was hoping to see some performance benchmarks, not just memory usage benchmarks.

Best of all, lookups in hashes are still O(1), making them very quick. Based on the zipmap code (linked below), a zipmap is implemented as an array of adjacent (key, value) pairs. Lookup in a zipmap is actually linear search. There is no hashing. The lookup will run in time proportional to the number of entries in the map. We found this setting was best around 1000; any higher and the HSET commands would cause notice…

Wow I didn't realize that redis zipmap lookups aren't actually O(1). I found a document that describes zipmaps as "very memory efficient data structure to represent string to string maps, at the cost of being O(N) instead of O(1) for most operations. Since the constant times of this data structure are very small, and the zipmaps are converted into real hash tables once they are big enough, the amortized time of Redis hashes is still O(1), and in the practice small zipmaps are not slower than small hash tables because they are designed for good cache locality and fast access."

http://redis-docs.readthedocs.org/en/latest/Hashes.html

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

#39

Post by nkurz »

cperciva wrote: post #35
qeorge wrote: post #34

Earlier quoted context omitted.

Very readable for something so dense. Nice work! One suggestion from the peanut gallery: In http://code.google.com/p/kivaloo/source/browse/trunk/lib/dat... , at line 178 you have: if (rehash(H)) goto err0; That's because rehash returns 0 upon success, and -1 on failure. To me, that's very confusing, because it reads to be erroring upon success. When I read rehash's body, I learn that 0 means success and -1 means fail…

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 supposed to determine if rehash() returns an integer or a pointer? My first guess would have been that you were checking for a non-NULL pointer. The 'goto err' makes it relatively clear after the fact, but not at a glance.

If you want to keep returning -1, I think a better convention would be 'if (rehash(H) < 0)', which makes it more clear that you expect an int and better implies an error condition. But I think even better would be to return KV_SUCCESS or KV_FAILURE (defined however you choose) and check explicitly. This would also let you remove a bunch of lines by getting rid of every comment next to every return statement! :)

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

#40

Post by cperciva »

qeorge wrote: post #36
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."

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

Post reply on HN