Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Codex KV: How to Build a KV Storage from Scratch

DZone's Guide to

Codex KV: How to Build a KV Storage from Scratch

Want to know how to build a KV storage from scratch? Read this article to find out how.

· Database Zone ·
Free Resource

RavenDB vs MongoDB: Which is Better? This White Paper compares the two leading NoSQL Document Databases on 9 features to find out which is the best solution for your next project.  

We are exploring a few data structures for a particular feature in RavenDB, and I run into something that is elegant, simple, easy, and deep enough that we can discuss serious implementation details without getting too bogged down in the details.

The idea is that I’m going to be using this series of articles to post a detailed walkthrough about building a key-value store from scratch, including all the intermediate steps and wrong turns along the way. In other words, this is a “Show Your Work” kind of series. The end result is going to be a key/value store that can:

  • Store arbitrary keys/values.
  • Get key’s value by the key.
  • Support range queries and iteration.
  • Support some form of ACID.

In this case, I’m going to start from the very basics and build up. The challenge we are going to deal with is ingesting all the titles of articles in Wikipedia, about 277MB of them. I took them from here: (https://dumps.wikimedia.org/enwiki/latest/enwiki-latest-all-titles-in-ns0.gz). There are 13,755,095 of them in my case.

I’m calling the KV store that we’ll be creating Codex with, and I’m going to start from the most basic of examples, just being able to store and check if a value exists in the store. Here is the code that reads from the titles list and add them to the store. Note that the articles are sorted, but we don’t want this advantage of adding sorted data, so we randomize things.

var writer = new CodexWriter(file);
 var lines = File.ReadAllLines(@"C:\Users\ayende\Downloads\enwiki-20180220-all-titles-in-ns0");
 Shuffle(lines);
 foreach (var term in lines)
 {
     writer.Add(term);
 }

The question here is, how are we going to store these titles in a way that allow us fast retrieval? Here is the idea, we are going to write the strings to the output file as they come, and also record their positions. When we are done inserting strings to the codex, we’ll run a sort based on the positions, and that will give us an array of offsets to the strings in the files, sorted by their value. The first version of this code looks like this:

public class CodexWriter
{
    private readonly Stream _dest;
    private readonly BinaryWriter _writer;
    private List<long> _positions = new List<long>();
    private BinaryReader _reader;
    private HashSet<string> _repeated = new HashSet<string>();

    public CodexWriter(Stream dest)
    {
        _dest = dest;
        _writer = new BinaryWriter(_dest);
        _reader = new BinaryReader(_dest);
    }

    public void Add(string str)
    {
        if (_repeated.Add(str) == false)
            return;

        var pos = _dest.Position;
        _writer.Write(str);
        _positions.Add(pos);
    }

    private string ReadFrom(long pos)
    {
        _dest.Position = pos;
        return _reader.ReadString();
    }

    public void Complete()
    {
        var pos = _dest.Position;
        _positions.Sort((x, y) => ReadFrom(x).CompareTo(ReadFrom(y)));
        _dest.Position = pos;
        foreach (var item in _positions)
        {
            _writer.Write(item);
        }
        _writer.Write(_positions.Count);
    }
}

If you’ll run this code on the Wikipedia titles, you’ll find that it takes a while to run. On my machine, that took just under 50 minutes.

Well, we are dealing with the full set of Wikipedia titles, but even so, that doesn’t sound like it should take this long. What gives?

Let’s analyze what is going on here, okay? If you run this code, you’ll note that it isn’t using CPU or I/O or really seems to be doing much. What is going on?

The key here is in the ReadFrom method. There, we do two seemingly innocent actions. We set the file’s position (translate to SetFilePointer call) and read a short string (translate to a ReadFile call). Now, why is that expensive? Well, the ReadFrom method is called twice each time we need to sort an entry. In this case, it means that ReadFrom will be called a total of 575,616,878 times.

That is not a typo. And each invocation means two separate system calls. In other words, this innocent-seeming piece of code executed over 1.15 billion system calls.

For reference, simple by reading the entire file to a MemoryStream and keeping everything else the same, I was able to bring the cost of this operation down to under 3 minutes.

Lesson learned, system calls are expensive, so let’s try to reduce them as much as we can.

Do you pay to use your database? What if your database paid you? Learn more with RavenDB.

Topics:
database ,kv store ,tutorial

Published at DZone with permission of

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}