7 ms·

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

153 points by mikeyk 15y ago

moxiemk1 15y ago
The the code the article links to for zipmap.c (https://github.com/antirez/redis/blob/unstable/src/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 15y ago
  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/0b420168b485d0a9c4b66d0a6c341597fb155947 https://github.com/antirez/redis/tree/0b420168b485d0a9c4b66d...)
  - cperciva 15y ago
    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.
    - mikeyk 15y ago
      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.
      - cperciva 15y ago
        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 http://www.tarsnap.com/kivaloo.html, browsable svn repository at http://code.google.com/p/kivaloo/source/browse/ http://code.google.com/p/kivaloo/source/browse/).
        qeorge 15y ago
        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/datastruct/kvhash.c 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.
        cperciva 15y ago
        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."
        qeorge 15y ago
        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?
    - Retric 15y ago
      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?
      - cperciva 15y ago
        I generally don't trust external documentation, but I do trust in-line comments.
        catwell 15y ago
        You're probably wrong. Look at the comment above "stretches" here: https://github.com/binarylogic/authlogic/blob/master/lib/authlogic/crypto_providers/sha512.rb 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.
        vijaydev 15y ago
        Fixed :-) https://github.com/binarylogic/authlogic/commit/f52a699bbc9e99d5a73afc49d60e257eb27a01fd https://github.com/binarylogic/authlogic/commit/f52a699bbc9e...
        catwell 15y ago
        Incorrectly, see my comment on your link. But thanks for trying :) If you want my PoV on this, the right way to fix it is delete the comment.
    - antirez 15y ago
      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 15y ago
        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.
cperciva 15y ago
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.
- Aqua_Geek 15y ago
  Redis includes a benchmark utility (http://redis.io/topics/benchmarks http://redis.io/topics/benchmarks). I ran it on my MacBook Pro a couple of weeks ago and got north of 50,000 req/s with a bunch of other crap running. I don't think the utility has any tests for hashes, though.
  - cperciva 15y ago
    Oh, I've seen other redis benchmarks. But it's always nice to see more -- that way when someone wants to guess how fast their problem set will run on their hardware they will have a more similar benchmark to compare it against.
- minimax 15y ago
  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 https://github.com/antirez/redis/blob/unstable/src/zipmap.c
  - firefoxman1 15y ago
mythz 15y ago
I love companies like Instagram who take the time to share their scaling issues and experiences.
thezilch 15y ago
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 http://redis.io/topics/memory-optimization
gorset 15y ago
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 15y ago
  The dataset is static If I read the article correctly, existing entries won't change but new entries will be inserted.
  - mikeyk 15y ago
    Yep, ~30 inserts per second go in, so it's not static.
- maurits 15y ago
  build a finite state machine from the dataset Could you elaborate on that? Or provide a link for the novice?
  - gorset 15y ago
    Sure, I implemented the paper "How to squeeze a lexicon" http://www.n3labs.com/pdf/lexicon-squeeze.pdf 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 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.
catwell 15y ago
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 15y ago
  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 15y ago
    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 15y ago
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 15y ago
  Internally, redis stores integers as 64-bit binary values, not strings: http://redis.io/commands/incr http://redis.io/commands/incr.
  - LeafStorm 15y ago
    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.
- nknight 15y ago
  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%.
- ctoestreich 15y ago
  I would like to see some example code or a gist of what you did. I played around with custom number packing and using the hashset in redis inspired by the original thread topic and your comment. You can find the post here: http://www.christianoestreich.com/2011/11/redis-hashsets-performance/ http://www.christianoestreich.com/2011/11/redis-hashsets-per...
examancer 15y ago
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 https://github.com/lyconic/redis-native_hash
zellyn 15y ago
Why use the whole Media ID as the key within the bucket, rather than just the last three digits?
- ctoestreich 15y ago
  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.
petercooper 15y ago
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!)

153 points by mikeyk 15y ago

The the code the article links to for zipmap.c (https://github.com/antirez/redis/blob/unstable/src/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 15y ago
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/0b420168b485d0a9c4b66d0a6c341597fb155947 https://github.com/antirez/redis/tree/0b420168b485d0a9c4b66d...)
- cperciva 15y ago
  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.
  - mikeyk 15y ago
    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.
    - cperciva 15y ago
      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 http://www.tarsnap.com/kivaloo.html, browsable svn repository at http://code.google.com/p/kivaloo/source/browse/ http://code.google.com/p/kivaloo/source/browse/).
      - qeorge 15y ago
        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/datastruct/kvhash.c 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.
        cperciva 15y ago
        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."
        qeorge 15y ago
        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?
  - Retric 15y ago
    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?
    - cperciva 15y ago
      I generally don't trust external documentation, but I do trust in-line comments.
      - catwell 15y ago
        You're probably wrong. Look at the comment above "stretches" here: https://github.com/binarylogic/authlogic/blob/master/lib/authlogic/crypto_providers/sha512.rb 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.
        vijaydev 15y ago
        Fixed :-) https://github.com/binarylogic/authlogic/commit/f52a699bbc9e99d5a73afc49d60e257eb27a01fd https://github.com/binarylogic/authlogic/commit/f52a699bbc9e...
        catwell 15y ago
        Incorrectly, see my comment on your link. But thanks for trying :) If you want my PoV on this, the right way to fix it is delete the comment.
  - antirez 15y ago
    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 15y ago
      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.

cperciva 15y ago

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.

Aqua_Geek 15y ago
Redis includes a benchmark utility (http://redis.io/topics/benchmarks http://redis.io/topics/benchmarks). I ran it on my MacBook Pro a couple of weeks ago and got north of 50,000 req/s with a bunch of other crap running. I don't think the utility has any tests for hashes, though.
- cperciva 15y ago
  Oh, I've seen other redis benchmarks. But it's always nice to see more -- that way when someone wants to guess how fast their problem set will run on their hardware they will have a more similar benchmark to compare it against.
minimax 15y ago
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 https://github.com/antirez/redis/blob/unstable/src/zipmap.c
- firefoxman1 15y ago

mythz 15y ago

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

thezilch 15y ago

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 http://redis.io/topics/memory-optimization

gorset 15y ago

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 15y ago
The dataset is static If I read the article correctly, existing entries won't change but new entries will be inserted.
- mikeyk 15y ago
  Yep, ~30 inserts per second go in, so it's not static.
maurits 15y ago
build a finite state machine from the dataset Could you elaborate on that? Or provide a link for the novice?
- gorset 15y ago
  Sure, I implemented the paper "How to squeeze a lexicon" http://www.n3labs.com/pdf/lexicon-squeeze.pdf 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 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.

catwell 15y ago

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 15y ago
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 15y ago
  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 15y ago

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 15y ago
Internally, redis stores integers as 64-bit binary values, not strings: http://redis.io/commands/incr http://redis.io/commands/incr.
- LeafStorm 15y ago
  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.
nknight 15y ago
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%.
ctoestreich 15y ago
I would like to see some example code or a gist of what you did. I played around with custom number packing and using the hashset in redis inspired by the original thread topic and your comment. You can find the post here: http://www.christianoestreich.com/2011/11/redis-hashsets-performance/ http://www.christianoestreich.com/2011/11/redis-hashsets-per...

examancer 15y ago

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 https://github.com/lyconic/redis-native_hash

zellyn 15y ago

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

ctoestreich 15y ago
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.

petercooper 15y ago

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