Implementing a Key-Value Store

2012 November 7
by Emmanuel Goossaert

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 – 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

Translations

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.

24 Responses leave one →
  1. Kalyankumar Ramaseshan permalink
    February 24, 2014

    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.

    • February 26, 2014

      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.

      • meowlicous99 permalink
        July 24, 2016

        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?

    • meowlicous99 permalink
      July 24, 2016

      I guess I want to turn the question around and ask you why did you choose b-trees over Hashtables ?

    • Walt permalink
      July 9, 2017

      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.

  2. Hans Uhlig permalink
    April 14, 2014

    Any plans on continuing this series. Its quite interesting and I am curious to see how you implement the file structure.

    • April 15, 2014

      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!

  3. July 8, 2014

    Is this series will go on?

    • July 8, 2014

      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.

  4. July 10, 2014

    吾闻博学切问,所以广知。今顾曲周郎,莫不超群绝伦。

  5. October 22, 2014

    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!

    • October 22, 2014

      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/

      • October 23, 2014

        Thank you! This is very valuable!

      • Pradeep permalink
        January 26, 2016

        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

  6. October 29, 2014

    I like the series of these articles!

  7. Rainer permalink
    November 11, 2016

    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

Trackbacks and Pingbacks

  1. Implementing a Key-Value Store – Part 1: What are key-value stores, and why implement one? | Code Capsule
  2. Implementing a Key-Value Store – Part 2: Using existing key-value stores as models | Code Capsule
  3. Implementing a Key-Value Store – Part 3: Comparative Analysis of the Architectures of Kyoto Cabinet and LevelDB | Code Capsule
  4. Implementing a Key-Value Store – Part 4: API Design | Code Capsule
  5. Implementing a Key-Value Store – Part 5: Hash table implementations | Code Capsule
  6. Cuckoo Hashing | Code Capsule
  7. Implementing a Key-Value Store – Part 9: Data Format and Memory Management in KingDB | Code Capsule

Leave a Reply

Note: You can use basic XHTML in your comments. Your email address will never be published.

Subscribe to this comment feed via RSS