Implementing a Key-Value Store
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.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.1 – Not reinventing the wheel
2.2 – Model candidates and selection criteria
2.3 – Overview of the selected key-value stores
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.1 – Hash tables
5.2 – Implementations
6.1 – Open-addressing hash tables
6.2 – Metrics
6.3 – Experimental Protocol
6.4 – Results and Discussion
7.1 – Fast data structures on SSDs
7.2 – File I/O optimizations
7.3 – Done is better than perfect
Coming next, the final article:
11 – Mistakes and learnings
This article series was translated to Simplified Chinese by Xiong Duo.
Looking for a job?
Do you have experience in infrastructure, and are you interested in building and scaling large distributed systems? My employer, Booking.com, is recruiting Software Engineers and Site Reliability Engineers (SREs) in Amsterdam, Netherlands. If you think you have what it takes, send me your CV at emmanuel [at] codecapsule [dot] com.