DEV Community: Chaimaa Zegoumou

KVS implementation in C++ : A series - Hash table implementations (4)

Chaimaa Zegoumou — Sun, 18 Oct 2020 20:12:39 +0000

Before digging into Emmanuel’s article, I decided to look into other articles regarding hash tables and hash maps. Ozturk here discusses a simple hash map implementation in c++, which I think can potentially be a very good article to start with before getting our hands dirty.

If you are/were a computer science student, you have certainly heard of hash functions, and collisions. The first time I personally have heard of this, I wasn’t sure whether a collision was good or bad (oh well, lol). Bottom line is: we don’t like collisions.

We want to have a hash function close to a bijection, or at least, have outputs uniformly distributed, and we want the computation of hashed values to be efficient and fast.

1- State of the art in hash functions for hash tables:

I’m not sure if It’s interesting to look at the variety of hash functions that are out there, but It’s important to say that for hash tables we’re not really worried about attackers to bother ourselves with cryptographic hash functions so we won’t be using those. Non-cryptographic hash functions are much faster : Bob Jenkins has been developing extensively a bunch of hash functions (see here) and his latest interesting hf is lookup3 (0.5 bytes/cycle), MurmurHash3 is faster than lookup3 (1byte/cycle), CityHash was afterwards released by Google and Jenkins also released SpookyHash (happy hALLoWEeN) which are 2 times faster than MurmurHash3 but have other inconvenients of their own (interesting state of the art study here).

========> In a nutshell, the best ones out there so far are MurmurHash3 (for 32 bit machines) and CityHash-SpookyHash(for 64 bit machines).

2- A deep dive into the hash function implementations in pre-existing Key-Value stores:

GCC offers a hash table library called unordered_map in TR1, and It basically is very similar to Java’s implementation of a hashtable, in the sense that every (key, value) pair

The next attribute here helps with the collision handling: just like Java, if two keys have the same hashcode, we have a linked list structure where we store the pairs with the same hashcode for their keys.

(PS: we store both the key and the value, don’t bother me with the whole “how would i know which value corresponds to my key).

I found this figure in Emmanuel’s blog which describes how the hash table is stored in the heap, and as you can see there are memory spaces called ‘Node’ which means we have space where we store a pointer to the actual (key,value) pair.

Google offers a hash table library called dense_hash_map in SparseHash v2.0.2. This hash table structure is more interesting than the latter since, first of all, we don’t lose a bunch of space just writing addresses. We also don’t use linked list to handle collisions, we use quadratic internal probing in case of collisions, and in terms of locality, it’s better than the linked list structure since in every cache line we have 64 bytes and every pair is 16 bytes long, so we can very likely find the pair we’re looking for on the same line (see quadratic internal probing formula here).

Both of the previous hash table implementations are in-memory, which isn’t what we’re going to be implementing ourselves. But It was still interesting to see how It works.

Now on to something similar to what we’ll be doing, HashDb from Kyoto Cabinet.

So HashDB is one of the data structures KC developed, it’s persistent on-disk and it uses separate chaining through a BST for every bucket. AND, the bucket array has a fixed size, so no matter how bad the load factor is, you can never change that and you’re just going to suffer.

It’s not impossible, but it’s costly, since everything is stored on disk and re-hashing the keys after resizing the bucket array will require access to the disk for all the keys, and once you have so many entries, basically, trying to do this is a death wish. You can store the hashed keys, but that comes down to a space/time compromise, so Kyoto Cabinet just thought “fk all” and fixed the bucket array’s size.

Of course, the BST needs a comparable type to classify the nodes, so they use a function called fold_hash which helps with that (honest to God, I didn’t get it; it’s meant to make these keys ‘comparable’, but the function seems to apply operations on the same hash so it’s kinda like...not doing anything? Anyways, let’s hope Emmanuel answers my question on his blog post about this.

An extra cool thing about HashDB, even though It can be a total pain when we have collisions and we’ll have to find the correct pair..., is that memory management should be handled by KC and not the OS, like It’s the case for dense_hash_map and unordered_map. So, we actually store everything in a file and we also have as to where the free blocks of space are (we have the offset, the size of this space).

These free blocks are allocated using std::set’s upper_bound method, which will return the closest free space possible.

KVS implementation in C++ : A series - How to design a good API (3)

Chaimaa Zegoumou — Tue, 06 Oct 2020 10:55:55 +0000

Great reference for API design

Intro

Basically, designing a good API means it should be easily usable and it should make developing wrong things difficult. Since KVS already exist, we should manage user expectations well; they’ve already seen a lot of key-value stores, and we shouldn’t diverge from what’s already pretty common.

Emmanuel calls his KVS KingDB, I guess I’ll call mine QueenDB? Honestly, the name doesn’t matter as much as the code so yeah QueenDB It is.

Basic features of a KVS:

open, close db
read, write to db
iterate over keys and values in a db
offer a way to choose parameters
offer a decent error notification interface That seems about right, we’re not dealing with documents like MongoDB, and we won’t have several fields since it’s a mere A->B entry, so we don’t need filtering features for search..

What's out there already:

To open and close db : a lot of different approaches, which were judged to be C-style, LevelDB creates a pointer for the db, calls open(db) then destroys the pointer as a method of closing it.. So, in QueenDB, we will keep the open and close methods

To read and write : honestly, just a get and set method, where we have the read/write options, the key and the value (as a ptr ofc for get, and by value for set). We could return an integer to see if the operation happened without an error.

To iterate : an iterator lol

To choose parameters : Kyoto has a tune_* method to be called directly on the database for every parameter, LevelDB has an Options class with different attributes (parameters) to set then to pass to the open method, you can also set every parameter and pass it by value to the put method (just check their source code). SQLite3 has a config method where you just pass flags (one at once), before initializing the database and opening it

LevelDB’s way is better because we don’t have to call a method to change the options, we can merely change the options class. It can also be shared among different databases. However, LevelDB passes these options as a 1st parameter so we always have to set them. Maybe, QueenDB will put it as a last parameter to make sure that if it doesn’t need to be set then we can skip it, and we’ll use method overloading with no options parameters.

To manage errors : LevelDB returns a Status object for every method and we can check using an ok method if no error has occurred. Kyoto Cabinet returns true or false, SQLite3 returns an integer too, same thing for Berkeley DB. LevelDB’s way seems much better, especially since the Status class has many attributes and it’s easy to use to test for errors.

KVS implementation in C++ : A series - 2012's State of the art in KVS (2)

Chaimaa Zegoumou — Sun, 04 Oct 2020 21:36:36 +0000

This article is Emmanuel’s somewhat exhaustive comparison of LevelDB and Kyoto Cabinet. I guess he didn’t compare the others because he was only looking at cpp code. Anyways i’ll try to sum up the main points which really caught my eye in this article.

Parametrization: LevelDB takes the lead here, because it decoupled its implementation for the database from the parameters, and implemented instead a totally separate component for parameters (general, for read, for write), unlike Kyoto.

String: The main goal here is to get rid of O(n) when checking the size of a string, since at a huge scale, it becomes a real pain. So, the idea LevelDB had was to make a class which stores both the byte array and its size, so the size() method is O(1) in time. Redis does the same thing. Kyoto Cabinet uses std::string.

Error management : It will be inspired by LevelDB’s status object. We avoid unnecessary space if we just have a variable we need to set, in our case, it’s null unless something is wrong. And the error is treated by the Status class.

Memory management : Kyoto Cabinet uses a memory mapped file (meaning the OS handles virtual memory by itself- working set fits in RAM , otherwise the OS will have to access part of it it on disk)

Data storage : file system vs memcached (memcached stores everything in RAM)

KVS implementation in C++ : A series - Finding inspo (1)

Chaimaa Zegoumou — Sun, 04 Oct 2020 20:08:06 +0000

Since a lot of KVS (key-value stores, settling on this acronym) already exist, It’d be interesting to look at previously developed models, to get some inspiration.

Examples of KVS :

DBM
Berkeley DB
Kyoto Cabinet
Memcached and MemcacheDB
LevelDB
MongoDB
Redis
OpenLDAP
SQLite

Requirements for our KVS :

KVS designed for OOP
everything will be on-disk
network access to data store
no ACID properties necessarily
no need for a query engine

Small intros to available KVS :

Berkeley DB : implemented in C, is an open source embedded (runs in the same address as the app, no inter-process comm for database operations) database library for scalable, high-performance, transaction-protected data management services to apps.

Kyoto Cabinet : implemented in C++, implements a hash table a B+ tree and other DS,but performance changes if the database’s size goes above a limit (ooooof course).

LevelDB: implemented in C++, implements a LSM (log-structured merge tree, which are optimized for SSD drives). For more than one million entries, performance drops. Clear source code though, and for a personal project, we don’t require a heavy load so that’s fine.

Redis : implemented in C, it supports different types of values, not just string values. It’s implemented using hash tables for big sets, for smaller ones however, arrays are used. Its code is very clear and it’s well documented (see github repo)

Key-Value store implementation in C++ : A series

Chaimaa Zegoumou — Sun, 04 Oct 2020 14:31:08 +0000

I will be posting a series of posts where I will be documenting a project inspired by Emmanuel Goossaert’s Code Capsule blog post : http://codecapsule.com/2012/11/07/ikvs-implementing-a-key-value-store-table-of-contents/

An example of a KVS is dict in Python, or HashMap in JAVA. It’s a simple database format, where we can store a value attached to a key. It’s also considered a NoSQL type of database, much like MongoDB.

The interesting part of the project is that unlike other KVS projects, we’re targeting specific data representations, operations (read/write..), and It will be applicable to respond to a specific issue. We also want it to allow different access methods other than the simple get method (sorting keys like TreeSet in JAVA..).

It's not completely original, since as I already mentioned, is basically my documentation of a project made by Emmanuel Goossaert.
(I tried to document this on Tumblr lol, but the dev community is non-existent so I would never get any input from anybody)