search

jhuckaby / megahash

A super-fast C++ hash table with Node.js wrapper, tested up to 1 billion keys.
Other
411 stars 29 forks source link

Disappearing keys #4

Closed svaraborut closed 4 years ago

svaraborut commented 4 years ago

I tough it was a serious blame of the system integrity; hence I investigated it further to be sure.

Example: when updating keys '4723640122' and '4723640123' in a 100k elements list, the key '4723640123' as disappearing from the Map.

This is due to those keys having a close hash [0, 0, 0, 0, 11, 4, 5, 4] and [0, 0, 0, 0, 11, 4, 5, 5] and hence ending on the same leaf list. The issue is not to complex to reproduce as long as two keys stay in the same linked-list update of one will affect the other (but not the other way around).

The second key will disappear (effectively returning undefined from get and false from has) but the key counter from stats will not decrease but will further increase if the key is set again.

It is quite serious as it causes almost 40% of the key/value pair being lost (and not freed from memory).

svaraborut commented 4 years ago

Proposed a fix: https://github.com/svaraborut/megahash/tree/patch-1

jhuckaby commented 4 years ago

Thank you very much for not only reporting this bug, but also fixing it in the code. I cannot believe I missed this, as it seems like such an obvious mistake on my part. All my unit tests didn't catch it either!

I hope you don't mind, but I applied the fix myself instead of merging your pull request, because it contained a bunch of unrelated comments, and I also wanted to also write a unit test that explicitly reproduces the bug, and made sure that the unit test passes in the new version.

Thanks again! Great work!