News for hackers. Stuff that matters.
Re:Storing hundreds of millions of simple key-value pairs in... by cperciva on Tuesday November 01, 2011 @03:08PM (#3183610)
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.

Re:Storing hundreds of millions of simple key-value pairs in... by minimax on Tuesday November 01, 2011 @04:45PM (#3184062)
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... by firefoxman1 on Tuesday November 01, 2011 @08:35PM (#3184828)
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... by Aqua_Geek on Tuesday November 01, 2011 @03:16PM (#3183657)
Redis includes a benchmark utility (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.
Re:Storing hundreds of millions of simple key-value pairs in... by cperciva on Tuesday November 01, 2011 @03:34PM (#3183742)
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.