UPDATE July 21, 2016: This article series is still on-going, and the key-value store, KingDB, has already been released: http://kingdb.org. Over the coming weeks I will publish the last articles for the IKVS series, which will cover the architecture and data format of KingDB. To get an update when it’s done, you can subscribe to the newsletter from the top-right corner of the blog!
This post is the main article for the series “Implementing a Key-Value Store” (IKVS) that I am starting today. It aims at summing up all the articles of the series in a Table of Contents, and might later hold some general notes on the project.
Its content will change over time until the series is completed. In particular, in the Table of Contents, the titles of the parts that have not been written yet and their ordering might change. Some parts might also be removed and some others added as the writing advances.
More information on the project can be found in Section 1.3 of “Part 1: What are key-value stores, and why implement one?“
Enjoy, and if you have any questions, post a comment!
Table of Contents
1 – What are key-value stores, and why implement one?
1.1 – A quick overview of key-value stores
1.2 – Key-value stores versus relational databases
1.3 – Why implement a key-value store
1.4 – The plan
2 – Using existing key-value stores as models
2.1 – Not reinventing the wheel
2.2 – Model candidates and selection criteria
2.3 – Overview of the selected key-value stores
3 – Comparative Analysis of the Architectures of Kyoto Cabinet and LevelDB
3.1 – Intent and methodology of this architecture analysis
3.2 – Overview of the Components of a Key-Value Store
3.3 – Structural and conceptual analysis of Kyoto Cabinet and LevelDB
3.4 – Code review
4.1 – General principles for API design
4.2 – Defining the functionalities for the public API of KingDB
4.3 – Comparing the APIs of existing databases
5 – Hash table implementations
5.1 – Hash tables
5.2 – Implementations
6 – Open-Addressing Hash Tables
6.1 – Open-addressing hash tables
6.2 – Metrics
6.3 – Experimental Protocol
6.4 – Results and Discussion
7 – Optimizing Data Structures for SSDs
7.1 – Fast data structures on SSDs
7.2 – File I/O optimizations
7.3 – Done is better than perfect
9 – Data Format and Memory Management in KingDB
10 – High-Performance Networking: KingServer vs. Nginx
Coming next, the final article:
11 – Mistakes and learnings
Join my email list
Translations
This article series was translated to Simplified Chinese by Xiong Duo.
Why just hashtables? Why not b+tree’s? B+Tree’s can also effectively store key-value pairs isn’t it? I am currently researching about implementing a KV store using B+Tree (ofcourse a custom implementation) with memcached. I am interested on the thing that why just hashtables? My work is little inspired along the lines of innodb’s adaptive hash index, but as a simple KV-store.
Nice to hear you’re also implementing a key-value store! The reason why I picked hash tables is because I wanted to focus on a single data structured first to get it really right, as I figured that doing multiple at once would just dilute my focus and effort. I may try other data structures in the future, but for now I’ll only do hash tables.
As for B-Trees, it is true that they are a great solution for key-value stores, however I want my key-value store to be persistent on drive, more specifically solid-state drives. B-Trees were originally designed to cope with the physical limitations of rotational devices, hard drives mostly, therefore their inherent access patterns will not take advantage of the internals of SSDs. There are trees that make good use of SSDs, such as the log-structured merge tree on which LevelDB is based.
B-Trees were certainly not ‘designed’ for optimizing disk reads. That’s certainly where they founds their fame :).
Using hashtables is fine as long as you are not doing range queries. Kingdb doesn’t support range queries over the key. right?
I guess I want to turn the question around and ask you why did you choose b-trees over Hashtables ?
Just wondering, what benefits would implementing a KV store with a B+Tree provide over using a hash table? Hash tables provide O(1) access.
Any plans on continuing this series. Its quite interesting and I am curious to see how you implement the file structure.
Hi Hans, thanks for your interest!
Yes, the next parts of the IKVS are coming soon. During my research I ended up going down various rabbit holes, such as hashing algorithms and SSD architecture, which were all necessary steps for my key-value store project but that I chose not to include in the IKVS series itself. I am currently running simulations and gathering data on hopscotch hashing and Robin Hood hashing in order to write the next part of the IKVS series, which will be about hashing algorithms. I’m hoping to finish this part within the next couple of weeks or so, and after that, I’ll be implementing the whole thing!
If you want to receive an alert when an article is posted, you can subscribe to the newsletter, using the form at the top-right corner of the blog.
Cheers!
Is this series will go on?
Thanks for your interest! This article series is still going on, I am currently implementing the key-value store and will write a post about it when it’s done. Each of these articles take a very long time to write. To get an update when it’s done, you can subscribe to the newsletter from the top-right corner of the blog.
吾闻博学切问，所以广知。今顾曲周郎，莫不超群绝伦。
Great work! I just want to read the deep researches just like these posts. Thank you! And I wonder if you just want to do some research and experimental jobs or is it becoming a industrial work? Anyway is great for starters and engineers. Could I translate these posts into Chinese? For I want to introduce your jobs to more people. Thank you again!
KingDB is currently just a side project for me, but I’d be happy to see it used in the industry when it’s finished. The code, still under development, can be found here: http://kingdb.org.
And thanks a lot for proposing to do a Chinese translation! But actually, this is already in progress: http://blog.jobbole.com/75842/
Thank you! This is very valuable!
You are writing very nice and good article. I am following your key value store flow. I am planning to implement the key value store without using dynamic memory/memcpy function. I am using the static array for it.
Please let me know in case any one implemented it or provide me your code so then i can change it.
Thanks
Pradeep
I like the series of these articles！
Thank you very much! This is a really good article about implementing a KV-Store.
I am just missing the final thoughts about
11 – Mistakes and learnings
what is always the most important part of such a project. 🙂
all the best&take care
Rainer
I’m working on it! :p
Hi, I really learned so much from your project and the well-organized articles. May I know if you still want to post the topic 11？I am very eager to learn more from you. Thanks very much. Good luck!
Thanks for a wonderful article, great insights.
Its wire compatible with memcached
Would love this to be storage and wire-compatible with REDIS.