
Storing hundreds of millions of simple key-value pairs in Redis - mikeyk
http://instagram-engineering.tumblr.com/post/12202313862/storing-hundreds-of-millions-of-key-value-pairs-in
======
moxiemk1
The the code the article links to for zipmap.c
(<https://github.com/antirez/redis/blob/unstable/src/zipmap.c>) is _rather_
literate.

I haven't dug extremely deeply into the sources for many F/OSS projects; the
code I'm interested in reading has been inevitably opaque (at least to my
inexperience). This particular source file (and maybe the rest of Redis?) is
really good. I think I'll be taking many more looks at Redis (code- and usage-
wise) in the future.

~~~
mikeyk
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...](https://github.com/antirez/redis/tree/0b420168b485d0a9c4b66d0a6c341597fb155947))

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

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

~~~
cperciva
_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.

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

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

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

------
gorset
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 the dataset (maybe reverse the values to increase the level of
shared suffixes) which should reduce the size by an order of magnitude.

~~~
cperciva
_The dataset is static_

If I read the article correctly, existing entries won't change but new entries
will be inserted.

~~~
mikeyk
Yep, ~30 inserts per second go in, so it's not static.

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

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

~~~
minimax
_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>

~~~
firefoxman1
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>

------
mythz
I love companies like Instagram who take the time to share their scaling
issues and experiences.

------
thezilch
You can find similar examples -- ruby code for the "exact" implementation as
described by Instagram -- of this and other redis, memory optimization(s) at
the Redis site: <http://redis.io/topics/memory-optimization>

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

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

</extreme-pedantry>

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

------
pedigree
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 the hset suffix.
(due to the data format of the input field)

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

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

------
zellyn
Why use the whole Media ID as the key within the bucket, rather than just the
last three digits?

~~~
ctoestreich
I think they were trying to keep the hash sizes to ~1000 elements each key. At
a 3 digit key you would be increasing the hashes to 300k elements each. You
should augment the scripts and see if that has an impact on the performance,
would be curious to see.

------
examancer
The hash data type is probably the most awesome and underused feature of
redis. Here is a small gem I wrote to expose it a little better in ruby:
<https://github.com/lyconic/redis-native_hash>

