I am trying to build a key-value store (to learn, I am a student) that would serve as a persistence layer for software applications. I have looked into the database literature and dived a little bit in the internals of LevelDB and SQLite. Here are my objectives:No cap size on the size of keys or valuesNo constraints on the types of keys or valuesMinimize costly disk operations Grace under pressure (write intensive applications)Fast membership checksAnd following is the design I have came up with. First a quick disclaimer to let you know that I understand it would be bad practice for a production app to rely on an unproven not peer-reviewed database format. As I said, I am just a student trying to learn more though I want to do things the best way possible as well.Since we want to allow key/values of unlimited size, I thought that using a hash function to obtain a normalized and unique key identifier would be useful. I haven't researched which hash function would be best suited so we will assume that we use FNV-1a where each resulting hash is 8 bytes.My strategy to handle collision is not well defined yet, I have to investigate and see it would be a good idea to keep a memory mapped collision table or rather add a pointer on my metadata record ([collision: uint8 1 byte][offset: uint64 8 bytes][reserved: 1 byte])So we have a key := input() and a hKey := hash(key) to which is assigned a value stored on-disk in <value of hKey>.db. Let's call that file a hashfile.Record metadata stored over the first 12 bytes of a hash file:[total_size: uint64 8 bytes][overflow_pointer: uint16 2 bytes][size_chunk: uint16 2 bytes]And following is a value record, directly following metadata:    [value: blockSize - 32 bytes]Here blockSize := 4096BWe allow only up to 4096B (or whatever is the disk's block size) to be stored in a hashfile. If the value is greater than this, we increment overflow_pointer and store the rest of the of the value in a new hashfile <overflow_pointer>_<value hKey>.db. And so on until value is exhausted. This is a point of the design that I am the most uncertain about: would it be more efficient or practical to store it in the same file?I plan to have a watcher process look for cases where a set of adjacent keys are containing small data chunks and can be merged to form a bucket. But that is for later.Additionally, since hashes are only 8 bytes wide I plan to maintain a memory mapped index of hashfiles to provide fast membership checks.Please let me know your thoughts on this, I look forward to hear from you all!
Is my persistent storage strategy efficient for my project's objectives?
algorithms;database design;performance;hashing;file systems