apache / apache/incubator-pegasus
The hash method in hotkey coarse detection can be fast
- Dominant language
- C++
- Stars
- 2.1k
- Forks
- 328
- PR merge metrics
- No merged PRs in 30d
Description
`boost::hash_range` is used as the common method to calculate the hash value in hotkey_detection https://github.com/apache/incubator-pegasus/pull/624
After testing we find some faster algorithms to replace it.
One way is to use [xxhash](https://github.com/Cyan4973/xxHash), the other way is to use `boost::hash`.
We did a benchmark to evaluate the performance of the algorithm: set a random fixed-length string set, and loop to hash them. Here is a rough test result.
```shell
smilencer@smilencer-OptiPlex-7040 ~/Code/test_code/test_blob_xxhash $ ./hash_test
xxhash used time: 50993 us
boost_hash used time: 333000 us
smilencer@smilencer-OptiPlex-7040 ~/Code/test_code/test_blob_xxhash $ ./hash_test
xxhash used time: 78303 us
boost_hash used time: 331219 us
smilencer@smilencer-OptiPlex-7040 ~/Code/test_code/test_blob_xxhash $ ./hash_test
xxhash used time: 77513 us
boost_hash used time: 342499 us
smilencer@smilencer-OptiPlex-7040 ~/Code/test_code/test_blob_xxhash $ ./hash_test
xxhash used time: 79580 us
boost_hash used time: 333332 us
smilencer@smilencer-OptiPlex-7040 ~/Code/test_code/test_blob_xxhash $ ./hash_test
xxhash used time: 76561 us
boost_hash used time: 335781 us
smilencer@smilencer-OptiPlex-7040 ~/Code/test_code/test_blob_xxhash $ ./hash_test
xxhash used time: 81304 us
boost_hash used time: 335682 us
smilencer@smilencer-OptiPlex-7040 ~/Code/test_code/test_blob_xxhash $ ./hash_test
xxhash used time: 75173 us
boost_hash used time: 331603 us
smilencer@smilencer-OptiPlex-7040 ~/Code/test_code/test_blob_xxhash $ ./hash_test
xxhash used time: 81142 us
boost_hash used time: 335251 us
smilencer@smilencer-OptiPlex-7040 ~/Code/test_code/test_blob_xxhash $ ./hash_test
xxhash used time: 76805 us
boost_hash used time: 332577 us
smilencer@smilencer-OptiPlex-7040 ~/Code/test_code/test_blob_xxhash $ ./hash_test
xxhash used time: 77515 us
boost_hash used time: 333144 us
```
I plan to replace it in future PR. `xxhash` is really fast.
Contributor guide
Research direction
Start by locating the boost::hash_range call in hotkey_detection and review how its hash value is used. Compare xxhash with boost::hash in the existing benchmark setup, resolve which replacement is appropriate, and verify that hotkey detection remains correct while achieving the intended performance improvement.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- databases, performance
- Issue type
- Refactor
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 28/100