[jira] [Resolved] (KAFKA-20691) PersisterStateBatchCombiner.combineStateBatches() is O(n^2) worst-case; replace TreeSet-based iterative merge with single-pass sweep-line

["Ken Huang (Jira)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/KAFKA-20691?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Ken Huang resolved KAFKA-20691.
-------------------------------
    Resolution: Fixed

> PersisterStateBatchCombiner.combineStateBatches() is O(n^2) worst-case; replace TreeSet-based iterative merge with single-pass sweep-line
> -----------------------------------------------------------------------------------------------------------------------------------------
>
>                 Key: KAFKA-20691
>                 URL: https://issues.apache.org/jira/browse/KAFKA-20691
>             Project: Kafka
>          Issue Type: Bug
>          Components: core
>    Affects Versions: 4.2.1
>            Reporter: Shekhar Prasad Rajak
>            Assignee: Shekhar Prasad Rajak
>            Priority: Major
>              Labels: queue, queues-for-kafka
>             Fix For: 4.3.2, 4.5.0
>
>
> combineStateBatches() merges batchesSoFar + newBatches into a sorted, disjoint, (deliveryState, deliveryCount)-distinct cover clipped at SPSO. Pipeline:
> pruneBatches drops/clips ranges below SPSO.
> mergeBatches loads survivors into a TreeSet, repeatedly finds the first overlapping or contiguous-same-state pair.
> Improvement area :
>  iterative pairwise TreeSet merging. Simple contiguous same-state input is roughly O(n log n), but overlap-heavy inputs can trigger repeated split/reinsert rounds. The number of merge iterations is  data-dependent and can grow non-linearly, approaching O(n^2 log n) in pathological overlap cases.
>  
> User-visible as non-linear WriteShareGroupState latency when many small ack ranges accumulate per partition.
> We can make it Time: O(n log n) (sort) + O ( n ) merge 
> How:
> Replace the TreeSet + iterative findMergeCandidatePair loop with a single-pass sweep-line over a sorted array:
> 1. Sort phase (O(n log n)): prune + sort into ArrayList
> 2. Sweep phase (O( n )



--
This message was sent by Atlassian Jira
(v8.20.10#820010)