3 ms·

I was looking at Redis yesterday and noticed this. Is there any particular reason you chose skip list instead of btrees except for simplicity? Skip lists consum

by ntoshev 17y ago

I was looking at Redis yesterday and noticed this. Is there any particular reason you chose skip list instead of btrees except for simplicity? Skip lists consume more memory in pointers and are generally slower than btrees because of poor memory locality so traversing them means lots of cache misses. I also suggested a way to improve throughput when you guarantee each command's durability (at the end of the wiki page): http://code.google.com/p/redis/wiki/AppendOnlyFileHowto http://code.google.com/p/redis/wiki/AppendOnlyFileHowto Also, have you thought about accommodating read-only traffic in an additional thread as a way to utilize at least two cores efficiently while sharing the same memory?

crux_ 17y ago
Without knowing how Redis works, maybe they were chosen because it's really quite easy to build a highly concurrent (lock-free) skip list?
- ntoshev 17y ago
  No, Redis is single-threaded so they sidestep all concurrency issues. This and persisting the data in a forked process are my favorite parts of Redis' architecture.
antirez 17y ago
There are a few reasons: 1) They are not very memory intensive. It's up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees. 2) A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees. 3) They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code. About the Append Only durability & speed, I don't think it is a good idea to optimize Redis at cost of more code and more complexity for a use case that IMHO should be rare for the Redis target (fsync() at every command). Almost no one is using this feature even with ACID SQL databases, as the performance hint is big anyway. About threads: our experience shows that Redis is mostly I/O bound. I'm using threads to serve things from Virtual Memory. The long term solution to exploit all the cores, assuming your link is so fast that you can saturate a single core, is running multiple instances of Redis (no locks, almost fully scalable linearly with number of cores), and using the "Redis Cluster" solution that I plan to develop in the future.
Andys 17y ago
I have implemented a skip list library that stores all nodes of the same "level" together in the same file/memory map. This fixes the cache locality problem. Skip lists also lend themselves well to concurrent multi-threaded access, especially update and deletion.

by ntoshev 17y ago

crux_ 17y ago

Without knowing how Redis works, maybe they were chosen because it's really quite easy to build a highly concurrent (lock-free) skip list?

ntoshev 17y ago
No, Redis is single-threaded so they sidestep all concurrency issues. This and persisting the data in a forked process are my favorite parts of Redis' architecture.

antirez 17y ago

There are a few reasons: 1) They are not very memory intensive. It's up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees. 2) A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees. 3) They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code. About the Append Only durability & speed, I don't think it is a good idea to optimize Redis at cost of more code and more complexity for a use case that IMHO should be rare for the Redis target (fsync() at every command). Almost no one is using this feature even with ACID SQL databases, as the performance hint is big anyway. About threads: our experience shows that Redis is mostly I/O bound. I'm using threads to serve things from Virtual Memory. The long term solution to exploit all the cores, assuming your link is so fast that you can saturate a single core, is running multiple instances of Redis (no locks, almost fully scalable linearly with number of cores), and using the "Redis Cluster" solution that I plan to develop in the future.

Andys 17y ago

I have implemented a skip list library that stores all nodes of the same "level" together in the same file/memory map. This fixes the cache locality problem. Skip lists also lend themselves well to concurrent multi-threaded access, especially update and deletion.