apache / apache/incubator-pegasus

The hash method in hotkey coarse detection can be fast

Open
#628 0 comments 0 reactions 0 assignees View on GitHub
type/enhancement
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.