1
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ I don't think this is an appropriate place to ask this question. It strikes me as more appropriate for Software Engineering, although I don't hang out there so I don't really know what their criteria are. From a theoretical point of view, hash collisions are always possible, and if the consequences are sufficiently severe then saying "it's very unlikely" may not be a sufficient safeguard. From a more practical POV, memcmp will practically never take more time than a single-word comparison precisely because strings in the same hash set typically differ in the first few bytes. $\endgroup$
    – rici
    Jun 16 at 16:18
  • $\begingroup$ @rici Thanks for the alert. +1 $\endgroup$ Jun 18 at 2:27
  • $\begingroup$ @rici "because strings in the same hash set typically differ in the first few bytes." ... This is some thing I was not aware of. Can you please point me to any reference on this? $\endgroup$ Jun 18 at 2:29
  • $\begingroup$ It's a simple consequence of how hashing has to work if it is going to do a good job. It's not saying anything different from your point 6; similar keys have different hashes. $\endgroup$
    – rici
    Jun 18 at 4:40
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you +1. I wanted to use SHA256, however felt that it is computationally very expensive than murmur3. In absence of any other solution, that is where I am heading to. Good to know that someone else thinks that this is doable. $\endgroup$ Jun 18 at 2:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.