Implementing a Key-Value Store | Code Capsule


UPDATE July 21, 2016: This article series is still on-going, and the key-value store, KingDB, has already been released: 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 – API Design

    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

8 – Architecture of KingDB

9 – Data Format and Memory Management in KingDB

10 – High-Performance Networking: KingServer vs. Nginx

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,, 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.

Kommentieren Sie den Artikel

Please enter your comment!
Please enter your name here