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

11–20 of 55 posts

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

#11

Post by cperciva »

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…

The dataset is static

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

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

#13

Post by mikeyk »

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.

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 you? Always trying to improve my own coding habits as well.

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

#14

Post by mikeyk »

cperciva wrote: post #11
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…

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

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

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

#15

Post by cperciva »

mikeyk wrote: post #13
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.

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

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

#16

Post by 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)

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

#17

Post by eurleif »

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.

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

#18

Post by maurits »

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?

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

#20

Post by Retric »

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.

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 though. And stay away from the more colorful parts of the language.

How about you?

Post reply on HN