Key / Value store development porting to modern C++

Question

I am developing a database server similar to Cassandra.

Development were started in C, but things became very complicated without classes.

Currently I ported everything in C++11, but I am still learning "modern" C++ and have doubts about lot of things.

Database will work with Key / Value pairs. Every pair have some more information - when is created also when it will expire (0 if not expires). Each Pair is immutable.

Key is C string, Value is void *, but at least for the moment I am operating with the value as C string as well.

There are abstract IList class. It is inherited from three classes

• VectorList - C dynamic array - similar to std::vector, but uses realloc
• LinkList - made for checks and performance comparison
• SkipList - the class that finally will be used.

In the future I might do Red Black tree as well.

Each IList contains zero or more pointers to pairs, sorted by key.

If IList became too long, it can be saved on the disk in a special file. This special file is kind of read only list.

If you need to search for a key,

• first in memory IList is searched (SkipList, SkipList or LinkList).
• Then search is send to the files sorted by date
  (newest file first, oldest file - last).
  All these files are mmap-ed in memory.
• If nothing found, then key is not found.

I have no doubts about the implementation of the IList things.

---

What is currently puzzling me is following:

The pairs are with different size, they are allocated by new() and they have std::shared_ptr pointed to them.

class Pair{
public:
    // several methods...
private:
    struct Blob;

    std::shared_ptr<const Blob> _blob;
};

struct Pair::Blob{
    uint64_t    created;
    uint32_t    expires;
    uint32_t    vallen;
    uint16_t    keylen;
    uint8_t     checksum;
    char        buffer[2];
};

"buffer" member variable is the one with different size. It stores the key + value.
E.g. if key is 10 characters, and value is another 10 bytes, the whole object will be sizeof(Pair::Blob) + 20 (buffer have initial size of 2, because of two null terminating bytes)

This same layout is used on the disk as well, so I can do something like this:

// get the blob
Pair::Blob *blob = (Pair::Blob *) & mmaped_array[pos];

// create the pair, true makes std::shared_ptr not to delete the memory,
// since it does not own it.
Pair p = Pair(blob, true);

// however if I want the Pair to own the memory,
// I can copy it, but this is slower operation.
Pair p2 = Pair(blob);

However this different size is a problem on lots of places with C++ code.

For example I can not use std::make_shared(). This is important for me, because if I have 1M Pairs, I would have 2M allocations.

From the other side, If I do "buffer" to dynamic array (e.g. new char[123]), I will lose mmap "trick", I will have do two dereferences if I want to check the key and I will add single pointer - 8 bytes to the class.

I also tried to "pull" all members from Pair::Blob into Pair, so Pair::Blob to be just the buffer, but when I tested it, it was quite slow, probably because of copying the object data around.

Another change I am also thinking is to remove Pair class and replace it with std::shared_ptr and to "push" all methods back to Pair::Blob, but this will not help me with variable size Pair::Blob class.

I am wondering how I can improve on the object design in order to be more C++ friendly.

---

The full source code is here:
https://github.com/nmmmnu/HM3

Answer 1

The approach I would recommend is to focus on the interface of your key-value store, so as to make it as clean as possible and as nonrestrictive as possible, meaning that it should allow maximum freedom to the callers, but also maximum freedom for choosing how to implement it.

Then, I would recommend that you provide an as bare as possible, and as clean as possible implementation, without any performance concerns whatsoever. To me it seems like unordered_map should be your first choice, or perhaps map if some kind of ordering of keys must be exposed by the interface.

So, first get it to work cleanly and minimally; then, put it to use in a real application; in doing so, you will find what issues you need to address on the interface; then, go ahead and address them. Most chances are that as a result of changing the interface, you will need to rewrite big parts of the implementation, so any time you have already invested on the first iteration of the implementation beyond the bare minimum amount of time necessary to get it to just barely work is time wasted.

Then, profile it, and see what needs to be improved in the implementation, without altering the interface. Or you may have your own ideas about how to improve the implementation, before you even profile. That's fine, but it is still no reason to work on these ideas at any earlier point in time.

You say you hope to do better than map; there are two things that can be said about that:

a) you probably won't;

b) avoid premature optimization at all costs.

With respect to the implementation, your main issue appears to be memory allocation, since you seem to be concerned with how to structure your design in order to work around problems that you foresee that you are going to have with respect to memory allocation. The best way to address memory allocation concerns in C++ is by implementing a suitable memory allocation management, not by twisting and bending the design around them. You should consider yourself lucky that you are using C++, which allows you to do your own memory allocation management, as opposed to languages like Java and C#, where you are pretty much stuck with what the language runtime has to offer.

There are various ways of going about memory management in C++, and the ability to overload the new operator may come in handy. A simplistic memory allocator for your project would preallocate a huge array of bytes and use it as a heap. (byte* heap.) You would have a firstFreeByte index, initialized to zero, which indicates the first free byte in the heap. When a request for N bytes comes in, you return the address heap + firstFreeByte and you add N to firstFreeByte. So, memory allocation becomes so fast and efficient that it becomes virtually no issue.

Of course, preallocating all of your memory may not be a good idea, so you may have to break your heap into banks which are allocated on demand, and keep serving allocation requests from the at-any-given-moment-newest bank.

Since your data are immutable, this is a good solution. It allows you to abandon the idea of variable length objects, and to have each Pair contain a pointer to its data as it should, since the extra memory allocation for the data costs virtually nothing.

If you want to be able to discard objects from the heap, so as to be able to reclaim their memory, then things become more complicated: you will need to be using not pointers, but pointers to pointers, so that you can always move objects around in the heaps so as to reclaim the space of deleted objects. Everything becomes a bit slower due to the extra indirection, but everything is still lightning fast compared to using standard runtime library memory allocation routines.

But all this is of course really useless to be concerned with if you don't first build a straightforward, bare-minimal, working version of your database, and put it to use in a real application.