Praise The Tea

By the time I’m writing this article, I now already know that we’ll be implementing a hashtable using Robin Hood Hashing. So, as an extra step, Emmanuel explored hardware considerations for implementing QueenDB (or KingDB, whatever); in terms of I/O optimization and how our DS will be stored on disk.

I will try to sum up what’s been said in this article and what I personally understood (correct me if I’m wrong) : 

1- In-place updates are useless : no point in trying to come up with some fancy in-place updating algorithm because SSD’s don’t overwrite and they have to apply change to the entire page in an internal register and the new version is written in a totally different location in the SSD.

2- Avoid metadata : coming back to the idea that every change requires rewriting the entire page unless its size is 4/8/16KB.

3- Data’s not sequential : two pages that are sequential in the logical space aren’t necessarily sequential in the physical space. It would be good to try to write below the size of a page, and to just avoid rearranging data to be sequential logically.

4- Random writes are fast if they’re large enough : basically, clustered blocks can be accessed concurrently and are about 16/32MB, so writing these sizes can be internally parallel.

5- Random reads are fast : cc clustered blocks and internal parallelism in SSDs

6- Log-structured storage : LevelDB uses this approach in the form of Log-Structured Merge-Tree. The premise of LSS is that you apply all changes sequentially like they’re all coming in on a log. So updating a key’s value doesn’t mean you will make the change in-place (spoiler alert: SSD’s don’t even do that, look up), it means you will store the new value in the free space available after the latest operation, then point the key to it. Aaaand don’t worry about extra lost space, all is recovered during a compaction process.

7- Sys calls have a cost : that’s it

8- Memory maps :  they’re pretty cool, you map an area of a file to an address in memory which you can access in both write/read modes. 

I should have mentioned open-addressing in the latest post, but I didn’t. Quadratic internal probing is an open addressing scheme used to resolve hash collisions in hash tables, so there ya go.

WHY OPEN-ADDRESSING CHAI???? 

I can be like bold and stuff and try to choose separate chaining for hash collision handling (with BST’s or linked lists..), but Emmanuel chose open-addressing, I’m no C++ expert and  I have read an important reason and it seems to be pretty valid : We want a DS with a minimal number of I/O operations, especially since our key-value store will be on disk, so these operations will cost us more. 

We’ll be comparing linear probing, hopscotch hashing and robin hood hashing, and we’ll use the following metrics to evaluate their performances : 

DIB (distance to initial bucket): from initial bucket, which is the bucket referring to the initial hashed value to the bucket finally chosen.

DFB (distance to free bucket): distance put() has to scan from initial to free bucket.

DMB : (distance to missing bucket): distance get() has to scan from initial until it realizes that the entry is not even in the hash table. 

DSB (distance to shift bucket): i don’t know? still looking it up

nbr of bucket swaps: smth hopscoth and robin hood related

I’m going to stop here, because well, i’m tired and I’m not using any other metric.

A stupid glitch in Chrome made me lose my draft for a cool small intro to linear probing, hopscotch and robin hood hashing :( Google it, friends :’( Jk, i found these great references for the latter two hashing methods: Robin Hood here and Hopscotch here.

Aaaanyway, there are three main test cases important to evaluate hashing methods : 

1 -“loading” : inserting more and more entries until hash table is full with a load factor of 98%, whilst measuring our metrics at 2% increments.

2- “batch” : inserting entries until we reach a particular laod factor called LFM, then repeating the following ops 50 times: removing LFR entries of the total capacity, then reinserting them all at once, and measuring our metrics in every iteration.

3- “ripple” : basically batch except we reinsert the deleted entries one at a time.

Emmanuel shared his code for the tests as well as the results in his article as part of his IKVS series here. Overall, Robin Hood performs better than the other algorithms, and there is doubt around using Hopscotch because of neighborhood clusters, which , yes, can be resolved using linked lists but we lose cache locality which is the main reason why open-addressing is used.

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). 

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).

https://www.infoq.com/articles/API-Design-Joshua-Bloch/

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

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 

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 u can also set parameters for every parameter and pass it by value to the put method. 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.

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 what 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, at a huge scale, it becomes a real pain. So, the idea LevelDB made a Slice class  to store a byte array with its size so the size() method is O(1) in time. Redis does the same thing. Kyoto Cabinet uses std::string

Error management : 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 then all good, otherwise the os will have to access part of it it on disk) -tbc

Since a lot of KVS 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 

no need for a query engine 

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.

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.