gortiz opened a new issue, #19852: URL: https://github.com/apache/pinot/issues/19852
## Summary In `ReplicaGroupInstanceSelector.updateSegmentMapsForUpsertTable` (used by `StrictReplicaGroupInstanceSelector` for upsert and dedup tables), the rebuild cost grows faster than linearly with the number of distinct ideal state instance sets. The cause is hash collisions in the map of unavailable instances, which uses `Set<String>` keys. Found while benchmarking #19785 (see [this review thread](https://github.com/apache/pinot/pull/19785#discussion_r4256310760)). The problem also exists on master before that PR. ## Background The rebuild groups old segments by the instances in their ideal state: ```java Map<Set<String>, Set<String>> unavailableInstancesMap = new HashMap<>(); ... unavailableInstancesMap.computeIfAbsent(instancesInIdealState, k -> new HashSet<>()); // line ~241 ... unavailableInstancesMap.get(idealStateInstanceStateMap.keySet()); // line ~260 ``` `Set.hashCode()` is the sum of the element hash codes. Server instance names usually differ only in a numeric suffix (for example `Server_pinot-server-17.pinot-server-headless...`). Thus many different instance sets have the same or nearly the same hash code. Sets are not `Comparable`, so `HashMap` cannot use the tree order in a collided bin. Each lookup then scans a long bin, and the rebuild becomes close to quadratic. Example: with 200 servers named `Server_pinot-server-<i>.pinot-server-headless.ns.svc.cluster.local_8098` and 3 replicas, the 1,313,400 possible instance sets have only about 5,000 distinct `Set.hashCode()` values. ## Measurement Synthetic realtime upsert table, 380k segments, 200 servers, 3 replicas, one `onAssignmentChange` on master (43ecf19): | Distinct ideal state instance sets | Wall time | |---|---| | 64 | 0.5 s | | 4,096 | 0.6 s | | 8,192 | 0.75 s | | 50,000 | 2.1 s | | 380,000 | 18.5 s | A JFR profile shows most samples in `HashMap.getNode` and `HashMap$TreeNode.find`, called from the two lines above. ## Impact Strict replica-group tables normally have assignments that are aligned with partitions, so the number of distinct instance sets is small and this path is fast. The cost appears when a table has many distinct instance sets, for example after a rebalance without replica groups, or with many servers. The rebuild runs on every ideal state or external view change of the table. ## Possible fix Key the map by a value with a strong hash. For example, use a key object that holds the sorted instance names and hashes them in order (like `List.hashCode()`), or map instance names to integer ids and key by the sorted id array. The candidate sharing from #19785 does not fix this, because this map is keyed by the ideal state instance set, not by the instance state map pair. -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
