Make hash collisions in the registry much less likely #657
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Signed-off-by: beorn7 <beorn@grafana.com>
This makes the collisions a bit less likely by XOR'ing descIDs rather than adding them up for the collectorID. Signed-off-by: beorn7 <beorn@grafana.com>
This is a much stronger hash function than fnv64a and comparably fast (with super-fast assembly implementation for amd64). Performance is not critical here anyway. The old fnv64a is kept for vectors, where collision detection is in place and the weakness of the hashing doesn't matter that much. I implemented a vector version with xxhash and found that xxhash is slower in all cases except very very high cardinality (where it is only slightly faster). Also, ``xxhash.New`` comes with an allocation of 80 bytes. Thus, to keep vectors alloc-free, we needed to add a `sync.Pool`, which would have an additional performance overhead. Signed-off-by: beorn7 <beorn@grafana.com>
|
@awilliams this will be of interest for you. |
|
Thanks @beorn7, this looks like a great bridge between now and v2. Nice to see the collision test case as well! |
|
Thanks for having a look. |
cstyan
reviewed
Oct 15, 2019
| @@ -24,6 +24,8 @@ import ( | |||
|
|
|||
| const separatorByte byte = 255 | |||
|
|
|||
| var separatorByteSlice = []byte{255} // For convenient use with xxhash. | |||
There was a problem hiding this comment.
not that it's likely to change, but should this not be []byte{separatorByte}
There was a problem hiding this comment.
Yeah, that's better. (Originally, I wanted to remove separatorByte altogether, but then realized I want to keep the old hashing for vectors.) Will sent you a PR.
1 task
thaJeztah
added a commit
to thaJeztah/containerd
that referenced
this pull request
Jan 13, 2020
full diff: prometheus/client_golang@v0.9.4...v1.1.0 Using v1.1.0, because version v1.2.0 and up use versioned import paths for the github.com/cespare/xxhash/v2 dependency (prometheus/client_golang#657), which causes vendoring with vndr to break due to the v2 in the import-path. Signed-off-by: Sebastiaan van Stijn <github@gone.nl>
thaJeztah
added a commit
to thaJeztah/docker
that referenced
this pull request
Jan 16, 2020
full diff: prometheus/client_golang@v0.9.4...v1.1.0 Using v1.1.0, because version v1.2.0 and up use versioned import paths for the github.com/cespare/xxhash/v2 dependency (prometheus/client_golang#657), which causes vendoring with vndr to break due to the v2 in the import-path. Signed-off-by: Sebastiaan van Stijn <github@gone.nl>
docker-jenkins
pushed a commit
to docker/docker-ce
that referenced
this pull request
Jan 17, 2020
full diff: prometheus/client_golang@v0.9.4...v1.1.0 Using v1.1.0, because version v1.2.0 and up use versioned import paths for the github.com/cespare/xxhash/v2 dependency (prometheus/client_golang#657), which causes vendoring with vndr to break due to the v2 in the import-path. Signed-off-by: Sebastiaan van Stijn <github@gone.nl> Upstream-commit: 34a65cb3bad3cfc626bf0b15715680ed9633e455 Component: engine
tussennet
pushed a commit
to tussennet/containerd
that referenced
this pull request
Sep 11, 2020
full diff: prometheus/client_golang@v0.9.4...v1.1.0 Using v1.1.0, because version v1.2.0 and up use versioned import paths for the github.com/cespare/xxhash/v2 dependency (prometheus/client_golang#657), which causes vendoring with vndr to break due to the v2 in the import-path. Signed-off-by: Sebastiaan van Stijn <github@gone.nl>
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Sadly, that's not yet a complete solution (like the one planned for v2, see last item in #222). However, using xxhash for the registry improves things a lot. It also moves from summing to XOR'ing for the collectorID. (Hashing the hashes would be an option, too, but it would require sorting of the hashes. I didn't want to go down that rabbit hole and rather stick with a commutative and associative operation.)
(Interestingly, just moving from sum to XOR solved #633 already, but of course, other hash collisions might happen in practice despite the XOR. In fact, hash collisions might still occur. This PR is mostly there to make this sufficiently unlikely so that the world will survive until v2 is released.)