Practical Networked Applications in Rust, Part 1: Non-Networked Key-Value Store

The PingCAP company, makers of the TiDB NewSQL database and the TiKV key-value store, have kindly made publicly available, as well as open-sourced, a set of training courses that they call the "PingCAP Talent Plan". These courses train programmers in writing distributed systems in the Go and Rust languages. They are originally intended by PingCAP to train students, new employees and new contributors to TiDB and TiKV and focus as such on subjects relevant to those projects, but are still appropriate to anyone with an interest in learning to make distributed systems in Go and/or Rust.

This is perfect for myself, as I’m eager to learn more about developing distributed systems and especially in the Rust language.

Practical Networked Applications in Rust

I’ve embarked on the first course in the series, which is Practical Networked Applications in Rust. The aim of this course is to develop a networked and multithreaded/asynchronous key-value store in the Rust language. The course consists of several successive modules, the first of which (disregarding basic preparations) is to make the core, non-networked, key-value store. I will in this article series document my progress in developing the different modules. In this installation of the series, I’ll give the reader a run-down of my solution to the first course module.

Key-Value Store Implementation

The first PNA course module is about implementing a basic, command-line controlled, key-value store, without networking capabilities. It’s dead simple functionality-wise, but still plenty challenging to implement (at least if you ask me).

Storage Algorithm

The core logic of the key-value store uses a log-file based storage algorithm inspired by Bitcask, which is both easy to grasp and leads to desirable performance characteristics.

Basically, the storage algorithm consists of writing storage operations to append-only log files, and maintaining an in-memory lookup table from keys to log entries. The downside to this is that the entire key space must be contained in memory (while values remain on disk). At certain intervals, the log files are also compacted in order to reclaim disk space.

Show Me the Code

As mentioned initially, the key-value store is entirely written in Rust. I’ve published the source code of my implementation at GitLab. I’ll now give you a rundown on the workings of the implementation.

The code is structured as a typical Rust application, with the source tree in the src/ directory and tests in the tests/ directory (and the all-important Cargo.toml file in at root level).

The source tree contains two files, lib.rs and bin/kvs.rs. The former file contains the core module kvs, whereas the latter contains the command line interface, which is implemented with the help of the clap crate, which is a great choice for command line argument parsing in Rust.

Command Line Interface

This project, when built, produces a command line executable called kvs (as defined in Cargo.toml). The application supports three basic sub-commands:

  • get: Get the value for a key.

  • set: Set the value for a key.

  • rm: Remove a key/value pair.

A global flag, --verbose, is also supported, which allows you to enable logging, a helpful ally in figuring out why things don’t work the way you expect. While there are numerous logging libraries out there for Rust, I’ve picked Fern as it is simple to use and lets me configure the logger to the required extent.

The actual operations are carried out by the KvStore struct in the kvs module though, the command line interface is just a thin shell.

Library

The core of the project is implemented in src/lib.rs, as the kvs module. Most importantly, this module defines a struct called KvStore, that clients (i.e. the command line interface) use to interact with a key-value store persisted in a sub-directory of the current directory, called .kvs/.

The KvStore struct exposes one function to instantiate itself: open(dpath: &Path) → Result<KvStore>). It returns an object that allows you to manipulate the key-value store in the current directory. The object has the following public methods:

  • set(self: &mut KvStore, key: String, val: String) → Result<()>: Set the value for a key.

  • get(self: &mut KvStore, key: String) → Result<Option<String>>: Get the value for a key.

  • remove(self: &mut KvStore, key: String) → Result<()>: Remove a key/value pair.

Setting Data

The set method will first of all call the build_index private method to generate the in-memory index mapping keys to log entries, from log files in the .kvs/ directory, if this hasn’t already been done. Each index entry is basically a pointer into a certain log file so you can read the corresponding value directly from disk. It also contains the length of the record, to help with calculating compacting potential:

#[derive(Debug)]
struct LogPointer {
    file: Arc<File>,
    offset: u64,
    length: u64,
}

As you might notice from the above code listing, I use shared pointers (std::sync::Arc) in order to reference corresponding file objects from index entries (LogPointer instances). It’s a simple solution to referring to the same file objects from many key representations, but I’ll possibly revisit this in the future in conjunction with performance testing.

As part of building the index, compaction potential is also calculated, which means we determine how much disk space could be reclaimed through log compaction. This means basically dropping overridden set commands and any remove commands (as these simply correspond to dropping previous set commands for the same key).

Commands are read from log files by deserializing binary on-disk data using a combination of Serde (the prevalent Rust deserialization framework) and Bincode, a binary serialization protocol (for pairing with Serde).

Once the in-memory index is built, the set method first checks if the current value for the key is the same as the incoming one. If that is the case, it returns without doing anything. Otherwise, it adds to the compaction potential if a value has already been set for the key (as the old value is overridden). Then it proceeds to write a set command to the current log file.

Commands are represented as instances of the Command struct and serialized to a compact binary representation with the help of Bincode/Serde:

#[derive(Serialize, Deserialize, Debug)]
enum CommandType {
    Set,
    Remove,
}

#[derive(Serialize, Deserialize, Debug)]
struct Command {
    typ: CommandType,
    key: String,
    value: String,
}

The serialized command gets written to the log file and recorded for the key in the index, as a LogPointer instance.

After writing the set command, the method will check if the compaction potential threshold is reached, and if so perform a compaction of the log files. Compaction is carried out by writing set commands corresponding to all entries in the in-memory index and writing them to the file .kvs.new/log-1.

After, .kvs/ gets renamed to .kvs.old/, .kvs.new/ gets renamed to .kvs/ and finally, .kvs.old/ is deleted. Thus, all the old log files are safely replaced by a single new one.

The in-memory index now gets rebuilt.

Getting Data

Same as when setting data, the get method will first of all build the in-memory index if it hasn’t already been done. Then it will simply get the value, by finding the corresponding LogPointer and reading the value in question using the recorded file and offset (deserialized from Bincode format).

Removing Data

Same as when setting data, the remove method will first of all build the in-memory index if it hasn’t already been done. Then it will proceed to remove the key/value pair from the index, update the compaction potential and write a corresponding remove command to the current log file. If compaction threshold is reached, compaction is additionally triggered.

Conclusion

I hope you found this article fun and useful! Maybe you even felt inspired to try taking the course yourself? Stay tuned for more content in this series!