You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@pinot.apache.org by "BackendArchitectX (via GitHub)" <gi...@apache.org> on 2026/10/17 00:37:09 UTC
[PR] Reduce hash collisions in replica-group instance lookup [pinot]
BackendArchitectX opened a new pull request, #19915:
URL: https://github.com/apache/pinot/pull/19915
## Summary
Fixes #19852.
The replica-group instance selector previously used `Set<String>` as a `HashMap` key when tracking unavailable instances. Server instance names with similar numeric suffixes could produce excessive hash collisions and slow down routing-map updates.
This change:
- Introduces an immutable `InstanceSetKey` with sorted instance names and improved hashing.
- Updates unavailable-instance lookups to use the new key.
- Adds regression tests for hash collisions, routing isolation, recovery and hash distribution.
## Validation
- `InstanceSelectorTest`: 95 tests passed, 0 failures.
- Maven reactor build: 29 modules successful.
- Targeted Checkstyle: 0 violations.
- Git whitespace validation passed.
## Notes
The hash-distribution test covers 100,000 instance combinations. A production-scale routing rebuild benchmark has not yet been performed.
Assisted-by: GPT-6 (ChatGPT).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] Reduce hash collisions in replica-group instance lookup [pinot]
Posted by "BackendArchitectX (via GitHub)" <gi...@apache.org>.
BackendArchitectX commented on code in PR #19915:
URL: https://github.com/apache/pinot/pull/19915#discussion_r4345291143
##########
pinot-broker/src/main/java/org/apache/pinot/broker/routing/instanceselector/ReplicaGroupInstanceSelector.java:
##########
@@ -292,8 +336,8 @@ void updateSegmentMapsForUpsertTable(IdealState idealState, ExternalView externa
Set<String> onlineInstances = entry.getValue()._onlineInstances;
Map<String, String> idealStateInstanceStateMap = idealStateAssignment.get(segment);
Map<String, String> sortedIdealStateInstanceStateMap = sortByKeyIfNeeded(idealStateInstanceStateMap);
- Set<String> unavailableInstances =
- unavailableInstancesMap.getOrDefault(idealStateInstanceStateMap.keySet(), Set.of());
+ Set<String> unavailableInstances = unavailableInstancesMap.getOrDefault(
+ new InstanceSetKey(idealStateInstanceStateMap.keySet()), Set.of());
Review Comment:
Good point. The additional allocation is worth considering, especially for large segment counts. I'd prefer to keep the implementation simple for now and validate the tradeoff with a representative routing-rebuild benchmark before introducing caching or further optimization.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] Reduce hash collisions in replica-group instance lookup [pinot]
Posted by "BackendArchitectX (via GitHub)" <gi...@apache.org>.
BackendArchitectX commented on code in PR #19915:
URL: https://github.com/apache/pinot/pull/19915#discussion_r4345289536
##########
pinot-broker/src/main/java/org/apache/pinot/broker/routing/instanceselector/ReplicaGroupInstanceSelector.java:
##########
@@ -73,6 +75,45 @@ public class ReplicaGroupInstanceSelector extends BaseInstanceSelector {
private static final Logger LOGGER = LoggerFactory.getLogger(ReplicaGroupInstanceSelector.class);
+ // Immutable key for instance groups that reduces hash collisions.
+ static final class InstanceSetKey implements Comparable<InstanceSetKey> {
+ private final String[] _instances;
+ private final int _hashCode;
+
+ InstanceSetKey(Set<String> instances) {
+ _instances = instances.toArray(new String[0]);
+ Arrays.sort(_instances);
+
+ int hash = 1;
+ for (String instance : _instances) {
+ hash = 31 * hash + HashCommon.mix(instance.hashCode());
+ }
+ _hashCode = hash;
+ }
+
+ @Override
+ public int hashCode() {
+ return _hashCode;
+ }
+
+ @Override
+ public boolean equals(Object object) {
+ if (this == object) {
+ return true;
+ }
+ if (!(object instanceof InstanceSetKey)) {
+ return false;
+ }
+ InstanceSetKey other = (InstanceSetKey) object;
+ return _hashCode == other._hashCode && Arrays.equals(_instances, other._instances);
+ }
+
+ @Override
+ public int compareTo(InstanceSetKey other) {
Review Comment:
Thanks for the review! I kept `Comparable` intentionally because `HashMap` uses it to navigate treeified collision buckets when keys have identical hashes. Since this change specifically addresses hash-collision performance, I think it's worth retaining as a safeguard against residual collisions.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] Reduce hash collisions in replica-group instance lookup [pinot]
Posted by "BackendArchitectX (via GitHub)" <gi...@apache.org>.
BackendArchitectX commented on code in PR #19915:
URL: https://github.com/apache/pinot/pull/19915#discussion_r4416884798
##########
pinot-broker/src/main/java/org/apache/pinot/broker/routing/instanceselector/ReplicaGroupInstanceSelector.java:
##########
@@ -73,6 +75,45 @@ public class ReplicaGroupInstanceSelector extends BaseInstanceSelector {
private static final Logger LOGGER = LoggerFactory.getLogger(ReplicaGroupInstanceSelector.class);
+ // Immutable key for instance groups that reduces hash collisions.
+ static final class InstanceSetKey implements Comparable<InstanceSetKey> {
+ private final String[] _instances;
+ private final int _hashCode;
+
+ InstanceSetKey(Set<String> instances) {
+ _instances = instances.toArray(new String[0]);
+ Arrays.sort(_instances);
Review Comment:
Thanks for the detailed review, Jackie. I've updated the implementation in `1b24c35fac` to address the key-allocation concern.
The unavailable-instance map now uses `Object2ObjectOpenCustomHashMap` with a custom `Hash.Strategy`, reusing the existing assignment `keySet()` views. This eliminates the per-lookup wrapper, array copy and sort.
I used order-independent mixed hashing with `Set.equals()` rather than iteration-order equality. This preserves consistent hashing and equality when assignments contain the same instances in different iteration orders.
Validation:
- 97/97 targeted tests passed.
- Added coverage for reordered sets and assignment/Helix serialization round trips.
- Hash-distribution regression covers 100,000 combinations.
- Scoped Checkstyle and Spotless passed.
JMH results for 50,000 segments, 200 servers, 3 replicas and 3 JVM forks:
| Implementation | Healthy (ms) | Partial failure (ms) | Healthy alloc. (MiB) |
|---|---:|---:|---:|
| Original Set-key | 186.64 | 191.32 | 34.91 |
| Sorted InstanceSetKey | 78.58 | 82.72 | 40.35 |
| Custom fastutil strategy | 114.10 | 93.28 | 32.95 |
The custom strategy reduces allocation versus the sorted-key approach, but is slower in these measurements. Healthy-case results also showed significant fork-to-fork variation.
The 380,000-segment workload, additional distinct-set counts and GC measurements remain outstanding, so the production-scale performance trade-off is not yet established.
I'd appreciate your feedback on this approach and whether further changes are needed.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] Reduce hash collisions in replica-group instance lookup [pinot]
Posted by "BackendArchitectX (via GitHub)" <gi...@apache.org>.
BackendArchitectX commented on PR #19915:
URL: https://github.com/apache/pinot/pull/19915#issuecomment-6506283034
Hi @Jackie-Jiang and @xiangfu0,
I've pushed the requested changes in `1b24c35fac` and addressed the review feedback. All 97 targeted regression tests, Spotless and scoped Checkstyle pass locally.
The GitHub Actions workflows currently show `action_required` and have not executed.
Could you please help approve the pending workflows or direct me to the appropriate maintainer so CI validation can proceed?
Thank you for your time and review.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] Reduce hash collisions in replica-group instance lookup [pinot]
Posted by "xiangfu0 (via GitHub)" <gi...@apache.org>.
xiangfu0 commented on code in PR #19915:
URL: https://github.com/apache/pinot/pull/19915#discussion_r4344731996
##########
pinot-broker/src/main/java/org/apache/pinot/broker/routing/instanceselector/ReplicaGroupInstanceSelector.java:
##########
@@ -73,6 +75,45 @@ public class ReplicaGroupInstanceSelector extends BaseInstanceSelector {
private static final Logger LOGGER = LoggerFactory.getLogger(ReplicaGroupInstanceSelector.class);
+ // Immutable key for instance groups that reduces hash collisions.
+ static final class InstanceSetKey implements Comparable<InstanceSetKey> {
+ private final String[] _instances;
+ private final int _hashCode;
+
+ InstanceSetKey(Set<String> instances) {
+ _instances = instances.toArray(new String[0]);
+ Arrays.sort(_instances);
+
+ int hash = 1;
+ for (String instance : _instances) {
+ hash = 31 * hash + HashCommon.mix(instance.hashCode());
+ }
+ _hashCode = hash;
+ }
+
+ @Override
+ public int hashCode() {
+ return _hashCode;
+ }
+
+ @Override
+ public boolean equals(Object object) {
+ if (this == object) {
+ return true;
+ }
+ if (!(object instanceof InstanceSetKey)) {
+ return false;
+ }
+ InstanceSetKey other = (InstanceSetKey) object;
+ return _hashCode == other._hashCode && Arrays.equals(_instances, other._instances);
+ }
+
+ @Override
+ public int compareTo(InstanceSetKey other) {
Review Comment:
Nit: `InstanceSetKey` only ever serves as a `HashMap` key here, never in a sorted collection, so `Comparable`/`compareTo` is dead code. Fine to drop it to keep the key minimal (or keep if you expect a `TreeMap` use soon).
##########
pinot-broker/src/main/java/org/apache/pinot/broker/routing/instanceselector/ReplicaGroupInstanceSelector.java:
##########
@@ -292,8 +336,8 @@ void updateSegmentMapsForUpsertTable(IdealState idealState, ExternalView externa
Set<String> onlineInstances = entry.getValue()._onlineInstances;
Map<String, String> idealStateInstanceStateMap = idealStateAssignment.get(segment);
Map<String, String> sortedIdealStateInstanceStateMap = sortByKeyIfNeeded(idealStateInstanceStateMap);
- Set<String> unavailableInstances =
- unavailableInstancesMap.getOrDefault(idealStateInstanceStateMap.keySet(), Set.of());
+ Set<String> unavailableInstances = unavailableInstancesMap.getOrDefault(
+ new InstanceSetKey(idealStateInstanceStateMap.keySet()), Set.of());
Review Comment:
Minor: this builds a fresh `InstanceSetKey` (array copy + sort) per new segment, which the old `keySet()` lookup avoided. Arrays are tiny (replica-group size) so the cost is negligible, just flagging the added per-segment allocation.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] Reduce hash collisions in replica-group instance lookup [pinot]
Posted by "Jackie-Jiang (via GitHub)" <gi...@apache.org>.
Jackie-Jiang commented on code in PR #19915:
URL: https://github.com/apache/pinot/pull/19915#discussion_r4383150890
##########
pinot-broker/src/main/java/org/apache/pinot/broker/routing/instanceselector/ReplicaGroupInstanceSelector.java:
##########
@@ -73,6 +75,45 @@ public class ReplicaGroupInstanceSelector extends BaseInstanceSelector {
private static final Logger LOGGER = LoggerFactory.getLogger(ReplicaGroupInstanceSelector.class);
+ // Immutable key for instance groups that reduces hash collisions.
+ static final class InstanceSetKey implements Comparable<InstanceSetKey> {
+ private final String[] _instances;
+ private final int _hashCode;
+
+ InstanceSetKey(Set<String> instances) {
+ _instances = instances.toArray(new String[0]);
+ Arrays.sort(_instances);
Review Comment:
Can we avoid the extra copy per entry/lookup here? Each `InstanceSetKey` construction allocates a wrapper, copies the instance names into a new array, and sorts it. We do this twice per processed old `InstanceStateMaps` (collection and lookup), and once per new segment. When candidate sharing is exhausted or assignments are distinct, that becomes two constructions per old segment. Even with small replica counts, this adds allocation and GC work across large routing rebuilds.
The normal assignment writers create natural-order `TreeMap`s, and the Helix serialization/deserialization path preserves their iteration order even when the result is a `LinkedHashMap`. We should be able to use the existing `idealStateInstanceStateMap.keySet()` views directly with an `Object2ObjectOpenCustomHashMap<Set<String>, Set<String>>` and a custom `Hash.Strategy`:
- Compute the hash in iteration order, retaining the same mixed fold used here:
```java
int hash = 1;
for (String instance : instances) {
hash = 31 * hash + HashCommon.mix(instance.hashCode());
}
```
- Compare sizes and then compare the two iterators element by element. Only instance names participate; state values must not affect grouping.
- Handle identity/nulls in the strategy, since fastutil also calls `equals(key, null)` internally.
This removes the wrapper, array copy, and sort while retaining the same hash for naturally ordered inputs. The map is local to the rebuild, so the backing assignment maps only need to remain unchanged for that lifetime. Please document the natural-order iteration precondition and cover the actual assignment/serialization round trip in a test; account for the existing shuffled-map tests when defining that contract.
Could you also share some before/after performance numbers? The hash-distribution test demonstrates fewer collisions, but does not measure the rebuild cost or the added allocation. Reusing the workload from #19852 (380k segments, 200 servers, 3 replicas) would make the results comparable:
- End-to-end `onAssignmentChange` time and allocated bytes per rebuild, with GC time/count if available.
- A few distinct-instance-set counts, such as 64, 4,096, 50,000, and 380,000, to cover both heavily shared and mostly distinct assignments.
- Healthy assignments and a case with unavailable instances, using the same JVM/configuration and reporting the candidate-sharing limit.
- Baseline versus this PR; include the custom-strategy version if you try it. Please use warmup and repeated measurements so we can see the variation.
This would show both the collision-related improvement and whether the extra copying adds meaningful overhead in the common case.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] Reduce hash collisions in replica-group instance lookup [pinot]
Posted by "BackendArchitectX (via GitHub)" <gi...@apache.org>.
BackendArchitectX commented on PR #19915:
URL: https://github.com/apache/pinot/pull/19915#issuecomment-6334597172
Thanks again for the review, @xiangfu0! I've addressed both comments. The six CI workflows are still awaiting maintainer approval. Could you please approve them when convenient so the checks can run?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org