antirez/redis — pull request #2143 by mattsta (2014-11-18 18:45:15+00:00)
Title: Quicklist (linked list + ziplist)

What
====

My implementation of what Twitter has previously described as ziplists in a linked list for better memory efficiency.

Longer writeup with improvement graphs at https://matt.sh/redis-quicklist

How
====

Redis currently uses two list encodings. This replace both. The code in this PR/branch removes the two current list encodings of `REDIS_ENCODING_ZIPLIST` and `REDIS_ENCODING_LINKEDLIST` and replaces them with `REDIS_ENCODING_QUICKLIST`.

The only parameter for the new list type is the existing `list-max-ziplist-entries` field which tells Redis how many elements to allow per ziplist node before creating a new node. The other param of `list-max-ziplist-value` is now deleted.

The RDB format remains the same. A quicklist is written to the RDB as a linked list, so the RDB is still usable by prior Redis versions. The existing RDB format for saved ziplists and linkedlists both get converted to quicklists when the RDB is loaded. Quicklists are saved as RDB linkedlist types so on reload, Redis will re-create a new compact quicklist with full interior ziplists even if the saved quicklist had not-full interior ziplists.

Tests
====
All test pass for me. You should try to break it too. There is one spurious timing error in Redis tests (waiting too long for RDB loading), but I don't think it's new. (?)

The quicklist code also includes [~1,000 lines of internal tests](https://github.com/mattsta/redis/blob/quicklist/src/quicklist.c#L1160-L2013).

I added a new compile parameter of "REDIS_TEST" — if you compile with `-DREDIS_TEST` you can run Redis code tests with `redis-server test `. So, to test quicklist with code-level tests, compile with that define and run `redis-server test quicklist`. Also supported: ziplist, util, intset, [and more](https://github.com/mattsta/redis/blob/quicklist/src/redis.c#L3522-L3542).

Extras
=====
Also includes [`DEBUG JEMALLOC INFO`](https://github.com/mattsta/redis/commit/ab7c6492e883e097be25f7970cf328dd852a4828) to get [internal jemalloc stats](https://gist.github.com/mattsta/c2d3db5aa19f34355d69).

Figuring out what any of that means is left as an exercise for the reader.

Future Work
==========
This approach could be applied to some other areas too. Redis currently converts hashes from ziplists to full hash tables when they get too big, but we could make a hash table of ziplists to save a lot of space too.