antirez/redis — pull request #717 by aluzzardi (2012-10-22 03:05:31+00:00)
Title: Enhanced key-value store using the trie data structure

Hey,

These commits implement the Trie data structure into Redis and provide a new data type which makes use of it.

The main advantages over hash tables are:
- Memory efficient. No node in the tree stores the key associated with that
node. Instead, its position in the tree defines the key with which it's
associated. This results in memory savings as common key prefixes are stored
only once.

- No collisions. One of the biggest problems with hash tables are collisions.
They yeild a worst case performance of O(N), require constant re-hashing,
and can be attack vectors, as seen here:
https://github.com/antirez/redis/issues/663

- Prefix search. Traversing a trie from a given prefix doesn't require walking
through every node, which opens up a lot of new possibilities.

In addition to the data structure, I've implemented the TRIE data type which
makes use of it.

The TRIE data type is 100% compatible with the HASH type and supports
all of its commands (HGET becomes TGET, HSET becomes TGET and so on).

In fact, the trie unit tests were simply copied from the hash table and
slightly modified.

Additionally, tries support prefix-based traversal for TKEYS, TVALS and
TGETALL with the same performance.

Example:
> tset trie hello xxx
(integer) 1
> tset trie hey xxx
(integer) 1
> tset trie foobar xxx
(integer) 1
> tkeys trie
1) "foobar"
2) "hey"
3) "hello"
> tkeys trie he
1) "hey"
2) "hello"

This opens up many possibilities, such as using Redis to build an efficient
Auto Complete service.

Performance wise, this implementation delivers about the same performance as
hash tables.

I've run a couple of benchmarks on my laptop, so please don't consider those
as a reference:

./redis-benchmark -n 1000000 -r 1000000 -t HSET,HGET
HSET: 35617.61 requests per second
HGET: 35335.69 requests per second
used_memory_human:75.85M
used_memory_peak_human:80.69M

./redis-benchmark -n 1000000 -r 1000000 -t TSET,TGET
TSET: 36926.26 requests per second
TGET 36587.15 requests per second
used_memory_human:42.31M
used_memory_peak_human:45.01M

While the performance is about the same, it saves more than 50% of memory.

Note that the redis-benchmark test is a little biased:
In real world tests the memory usage will highly depend on the key distribution
and the values it holds.
Because redis-benchmark uses the same key prefix and increments the suffix
of the keys, tries perform very well on it, which might not reflect real-world
usage patterns.

For now, tries live as a separate data type.

If the concept is accepted, 3 things could happen:

1/ Keep it as is - a new data type compatible with hashes that provide some
extra features.

2/ Make HT-based data types (HASH, SET, ...) use the trie data structure

3/ Whatever the outcome of 1 and 2 are, another possibility is to replace the
main object database with a Trie. Not only this could lead to improved memory
efficiency, but the KEYS command could be special cased to take advantage of
tries for prefix-based lookups (e.g. KEYS foo*).

Please keep in mind that I've just started wrapping my head around Redis
internals, so this should not be considered production ready.

Let me know what you think.