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

21–30 of 55 posts

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

#21

Post by minimax »

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 noticeable CPU activity

This shouldn't be surprising either, as the redis documentation states that "If a specially encoded value will overflow the configured max size, Redis will automatically convert it into normal encoding." Their higher level hashing strategy of dividing the media id by 1000 guarantees that 1000 is the maximum number of entries in any zipmap. Setting hash-max-zipmap-entries to anything lower than 1000 means some of their zipmaps will be converted to normal redis key/value encodings.

https://github.com/antirez/redis/blob/unstable/src/zipmap.c

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

#22

Post by antirez »

cperciva wrote: post #10
mikeyk wrote: post #3

Earlier quoted context omitted.

Back when we were getting started with Redis, the readability / concise nature of the project was one of the things that most excited me about it (here's what it looked like around then: https://github.com/antirez/redis/tree/0b420168b485d0a9c4b66d... )

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 good code should be readable since the purpose of different files, functions, statements, data structures, should be obvious (at different levels of course), and every time it is not obvious there should be a comment helping the reader to understand what is going on.

My idea is that programmers with time develop a feeling about when a comment is needed. For instance a comment is needed all the times you are writing something that avoids a specific problem but you'll likely not remember why it was needed in a few weeks. Other times comments are useful since the flow of the function is complex and there is no easy way to refactor it into many pieces, so comments help to organize the function in smaller conceptual parts, and so forth.

There is no absolute rule, but the reality is that IMHO the test is simple to do for external people: good code is easy to understand and modify without being an expert of that code base.

This topic is a good idea for a blog post, since I thought a lot about this issues lately. For instance if you want a place in Redis where code should be improved is in the handling of blocking operations: there are a few things in that code that are absolutely non obvious even adding comments, and you either are a lot "into it" or you'll not have an easy time understanding it. I'm planning a refactoring of that piece of code.

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

#24

Post by cperciva »

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 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 lacking in commentary; and by the time I've read the code in function C to understand what it does and gone back to function B to understand what it's doing I've completely lost track of what I was looking at in function A.

Of course, if you already know what most of the code is doing you don't run into such stack overflows because whatever code you're looking at is probably only calling functions you already understand. But for people who are new to the code -- or people who haven't looked at it for a couple years and have forgotten most of the details -- I think asking people to read the code to figure out what a function does is too much of a bar to understanding.

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

#25

Post by cperciva »

Retric wrote: post #20
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.

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.

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

#26

Post by gorset »

maurits wrote: post #18
gorset wrote: post #9

1 million pair using 16 MB is about 16 bytes per pair, which is perfectly fine but nothing impressive. The dataset is static, so a simple naive solution would be to create a big array sorted by key. Assuming both photo and user IDs use 4 bytes each, this would result in about 2GB of data. Then use binary search to lookup values. However, if we really want to reduce the size, we could build a finite state machine from…

build a finite state machine from the dataset Could you elaborate on that? Or provide a link for the novice?

Sure,

I implemented the paper "How to squeeze a lexicon" http://www.n3labs.com/pdf/lexicon-squeeze.pdf with a few tweaks a while back. It uses a simple fixed format for all nodes, which works very well for datasets which contains many common prefixes and suffixes. For example, a polish dictionary containing 1.3 million strings is compressed down to 726KB. One of the thing I'm using it for is in a database for geopip stuff. It uses less than 1 byte per IP and can answer queries such as "find all values for the given IP-range" in O(k).

Dawid Weiss has a talk about how fine state machines are used in lucene at http://vimeo.com/26517310

The two approaches I've seen used to store key-value pairs in lexicons are:

1. Embed the value using a magic separator. E.g. (key0, value0), (key1, value1) becomes "key0.value1" and "key1.value1". The lexicon supports fast prefix lookups, which is used when looking up a key. As an added bonus, it supports multiple values per key out of the box, and you can easily find all key/values for a given prefix.

2. Add support for perfect minimal hashing to the lexicon. It will give you a unique ID for all keys, which can be used to do a direct lookup in another array containing the values. How to do this is not covered by the paper, but is an interesting exercise for the reader :-)

Now, back to the article. As cperciva mentioned, the dataset in the article isn't completely static and the usefulness for finite state machines drops fast if they need to be recompiled often. However, the key-value pairs are immutable, so it would be straightforward to implement a level-based scheme by using a simple structure for new items and move them into compressed lexicons periodically.

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

#27

Post by simplify »

cperciva wrote: post #24
antirez wrote: post #22

Earlier quoted context omitted.

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

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

#28

Post by mbreese »

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.

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.

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

#29

Post by pjscott »

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.

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

#30

Post by maurits »

gorset wrote: post #26
maurits wrote: post #18

Earlier quoted context omitted.

build a finite state machine from the dataset Could you elaborate on that? Or provide a link for the novice?

Sure, I implemented the paper "How to squeeze a lexicon" http://www.n3labs.com/pdf/lexicon-squeeze.pdf with a few tweaks a while back. It uses a simple fixed format for all nodes, which works very well for datasets which contains many common prefixes and suffixes. For example, a polish dictionary containing 1.3 million strings is compressed down to 726KB. One of the thing I'm using it for is in a database for geopip…

Thanks for your answer, I do appreciate that.
Post reply on HN