A visual representation of a Skip List. Sourced from WikipediaFor the final project of one of my university computer science courses, we had to choose a data structure or algorithim we learned in class and write a research paper about the concept, alongside it’s uses in everyday computing. My group chose to do our paper on Skip Lists, a data structure that can be used in-lieu of a self-balancing binary tree, such as an AVL tree or Red-Black tree.
You can read our paper here if you’re interested.
After doing this research project I decided to try using a Skip List in a real-world project, a key-value database.
A visual representation of a Skip List. Sourced from Wikipedia
A skip list is essentially a bunch of linked-lists stacked on top of each other. Each higher layer acts as an “express lane” that skips over elements below it, allowing for significantly faster lookups. Skip Lists use a “coin flip” to randomly promote elements to higher layers, keeping the structure roughly balanced without needing to implement complex balancing logic like in AVL or Red-Black trees.
This results in Skip Lists having an average insertion, search, and deletion time of O(log(n)), similar to binary trees. However, there are very rare cases where these actions will take O(n); the vast majority of datasets will have logarithmic insertions, deletions, and lookups.1
One of the major downsides to using Skip Lists is that each node will be allocated in a different place in memory, resulting in very poor spatial (cache) locality. If you don’t know what spatial locality is, it’s the idea that if a certain area of memory is accessed, the memory around it will most likely be accessed very soon. Modern computer systems use this principle (alongside other principles) to choose which data should be moved from slower RAM to faster CPU cache.
After doing this research project, I had the idea to build a simple, embedded (SQLite-like) key-value database in C that uses a Skip List as it’s primary index. I wanted this to be more of a proof-of-concept, rather than a production-ready library so I wanted to keep the scope very limited. The features I wanted to implement were:
Luckily, Skip Lists have been around for a while so there are tons of resources about how to implement them, so using these resources I made a basic C implementation that could insert, search, and delete nodes. I just decided to use C strings as the key, for compatibility/simplicity, but if you were to use fixed-size strings or integers you could have much faster operations as the comparisons could be done in constant time, rather than linear time.
I also wanted to address the downside of Skip Lists’ poor cache locality due to the nodes being allocated all throughout the computer’s memory. The best way to fix this is to ensure that every node is allocated in relatively the same area of memory.
I chose to use an Arena allocator to address this issue. An Arena allocator, or arena for short, is a data structure that stores a pointer to a large chunk of memory and a
pointer to the “top” of that memory chunk. Rather than calling malloc() for every node, you call malloc() once with a large size and then use that chunk of memory to
allocate new nodes. If you run out of space, you can just create a new arena and link it to the old one in a chain (basically a linked list of arenas). If you were to
reallocate the old arena, all of your old pointers would become invalid. It also has the benefit of only needing a single free() call, meaning that memory leaks are much
less likely to occur.
Another benefit of this is the fact that if a node is deleted, we can reuse it for another value. For example, if we have a Skip List of numbers: 1,2,3,4,8,9 and we delete 5, we can insert any number between 4 and 8 without needing to allocate a new node.
Since this database is a library, and not a constatnly running server, we can’t just check every second if any keys have expired and delete them, we need to be able to do it asynchronously. I decided to store pairs of keys and their expiration timestamps in a hashmap and every time an operation is run (insert, search, delete) the library checks the hashmap to see if the key has an expiry and if it has already expired. If it has, we just remove it from the database and the hashmap, otherwise we continue the operation as normal.
While this could in theory leave keys who are never accessed still in the database, since this is more of a proof-of-concept project I felt it wasn’t necessary to implement. In the future I might create a system where every 30 seconds or so, the database prunes all expired keys that haven’t been removed already.
This project is still a work in progress, but you can view the source code here. I haven’t implemented data persistence yet, due to the fact that I have been busy but when I do I will update this post with more information about it.
