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 -
- Compute a murmur 3 hash for given key.
- Using the hash find the set where the data should be stored.
- Let us say the cache is 4 way associative, therefore I have four slots where I can store the data.
- If the slots are already full I kick out the one earliest used.
- I store the hash in-place of key itself. But I understand that collisions are possible.
- 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.
- 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.
- 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 -
- no need to store keys and hence huge space can be saved
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?