implementation

Implementing a Key-Value Store – Part 9: Data Format and Memory Management in KingDB

Published by Emmanuel Goossaert on August 3, 2015

This is Part 9 of the IKVS series, “Implementing a Key-Value Store”. You can also check the Table of Contents for other parts. In this series of articles, I describe the research and process through which I am implementing a key-value database, which I have named “KingDB”. The source code is available at http://kingdb.org. Please note that you do not need to read the previous parts to be able to follow. The previous parts were mostly exploratory, and starting with Part 8 is perfectly fine.

In this article, I explain how the storage engine of KingDB works, including details about the data format. I also cover how memory management is done through the use of a compaction process.

Implementing a Key-Value Store – Part 8: Architecture of KingDB

Published by Emmanuel Goossaert on May 25, 2015

This is Part 8 of the IKVS series, “Implementing a Key-Value Store”. You can also check the Table of Contents for other parts. In this series of articles, I describe the research and process through which I am implementing a key-value database, which I have named “KingDB”. The source code is available at http://kingdb.org. Please note that you do not need to read the previous parts to be able to follow. The previous parts were mostly exploratory, and starting with Part 8 is perfectly fine.

In the previous articles, I have laid out the research and discussion around what needs to be considered when implementing a new key-value store. In this article, I will present the architecture of KingDB, the key-value store of this article series that I have finally finished implementing.

Implementing a Key-Value Store – Part 7: Optimizing Data Structures for SSDs

Published by Emmanuel Goossaert on October 18, 2014

This is Part 7 of the IKVS series, “Implementing a Key-Value Store”. You can also check the Table of Contents for other parts. In this series of articles, I describe the research and process through which I am implementing a key-value store database, which I have named “KingDB”.

In the previous articles, I have spent a fair amount of time reviewing existing key-value stores, interfaces, architectures, and I focused greatly on hash tables. In this article, I will talk about hardware considerations for storing data structures on solid-state drives (SSDs), and I will share a few notes regarding file I/O optimizations in Unix-based operating systems.

This article will cover:

1. Fast data structures on SSDs
2. File I/O optimizations
3. Done is better than perfect
4. References

Implementing a Key-Value Store – Part 6: Open-Addressing Hash Tables

Published by Emmanuel Goossaert on May 7, 2014

This is Part 6 of the IKVS series, “Implementing a Key-Value Store”. You can also check the Table of Contents for other parts.

In this article, I will compare several open-addressing hash tables: Linear Probing, Hopscotch hashing, and Robin Hood hashing. I have already done some work on this topic, and in this article I want to gather data for more metrics in order to decide which hash table I will use for my key-value store.

The result section also contains an interesting observation about the maximum DIB for Robin Hood hashing, which originated from Kristofer Karlsson, a software engineer at Spotify and the author of the key-value store Sparkey.

This article will cover:

1. Open-addressing hash tables
2. Metrics
3. Experimental Protocol
4. Results and Discussion
5. Conclusion
6. References

Implementing a Key-Value Store – Part 5: Hash table implementations

Published by Emmanuel Goossaert on May 13, 2013

This is Part 5 of the IKVS series, “Implementing a Key-Value Store”. You can also check the Table of Contents for other parts.

In this article, I will study the actual implementations of hash tables in C++ to understand where are the bottlenecks. Hash functions are CPU-intensive and should be optimized for that. However, most of the inner mechanisms of hash tables are just about efficient memory and I/O access, which will be the main focus of this article. I will study three different hash table implementations in C++, both in-memory and on-disk, and take a look at how the data are organized and accessed. This article will cover:

1. Hash tables
    1.1 Quick introduction to hash tables
    1.2 Hash functions
2. Implementations
    2.1 unordered_map from TR1
    2.2 dense_hash_map from SparseHash
    2.3 HashDB from Kyoto Cabinet
3. Conclusion
4. References

Implementing a Key-Value Store – Part 1: What are key-value stores, and why implement one?

Published by Emmanuel Goossaert on November 7, 2012

This is Part 1 of the IKVS series, “Implementing a Key-Value Store”. You can also check the Table of Contents for other parts.

In this article, I will start with a short description of what key-value stores are. Then, I will explain the reasons behind this project, and finally I will expose the main goals for the key-value store that I am planning to implement. Here is the list of the things I will cover in this article:

1. A quick overview of key-value stores
2. Key-value stores versus relational databases
3. Why implement a key-value store
4. The plan

Image segmentation using the Lambertain color model

Published by Emmanuel Goossaert on September 1, 2010

As part of my research on image segmentation, I have explored different methods for selecting areas in an image. Recently, I found a statistical color model based upon Lambertain surface reflectance. I have implemented this model using OpenCV 2.1. This article presents the results of some experiments I have run, along with my personal feelings about the model. At the end of the article, you will find links to the source code and to the research papers I used.

Active Appearance Models in C++ (Paamela)

Published by Emmanuel Goossaert on August 12, 2010

My implementation of the Active Appearance Models (AAMs) in C++ is almost done, it is called Paamela. I am currently fixing a couple design issues and finishing up the documentation. Even though I am still not sure whether or not I will make the code open source, I thought it would be nice to share what I have developed so far, in order to help other developers working on similar problems.

Tag: implementation