Avoid Storing Keys in Key-Value Store by Replacing the Key with 128-bit Murmur3 Hash

Question

I want to develop LRU key-value data store and in that wanted to get rid of space to store the key itself. Instead wanted to store a 128 bit murmur hash. The structure of data-store that I want to explore is similar to CPU k-way set-associative caches.

So the algorithm I want to pursue is -

1. Compute a murmur 3 hash for given key.
2. Using the hash find the set where the data should be stored.
3. Let us say the cache is 4 way associative, therefore I have four slots where I can store the data.
4. If the slots are already full I kick out the one earliest used.
5. I store the hash in-place of key itself. But I understand that collisions are possible.
6. Banking on avalanche effect (this is risky and hence the question), I am assuming that if the two strings differ only by a little, the hash will be different. However, two 'largely' different strings may still collide.
7. Since the hash is of fixed size (128 bit) let us say, I can get rid of memcmp() of the whole key length, which is 256-byte long (max) in my system.
8. I store just the hash, and compare hash to the stored hash (which acts like TAG in the cache). In case the two strings collide, I also store few bytes (say 15-20 bytes) along with their offsets which needs to be compared only if hash values match.

Assumed benefit of this is -

1. no need to store keys and hence huge space can be saved
2. avoid memcmp() on full length of the key, and the hash which is calculated once is used both for matching keys and identifying slots.

I want evaluation and review of this method and if there are ways on we can solidify this. I understand that comparison of bytes at some offsets may not be the reliable way. Are there any other existing methods which avoid storing of keys?

Answer 1

I think this is a reasonable approach. To make it more solid, I suggest replacing Murmur3 with a cryptographic hash, such as SHA256. Then we get a kind of guarantee: it is believed to be intractable to find a collision for the hash function. In other words, for all engineering purposes, we expect you will never in your lifetime encounter a pair of inputs with the same SHA256 hash. So, you can ignore the risk of collisions. There's no need to store an extra 15-20 bytes -- just rely on the SHA256 hash. As a side benefit, the SHA256 hash is only 256 bits long, not 256 bytes, so it'll save you additional space.