Sean Quah created KAFKA-21528:
---------------------------------

             Summary: Improve shard scheduling in group coordinator's 
EventAccumulator
                 Key: KAFKA-21528
                 URL: https://issues.apache.org/jira/browse/KAFKA-21528
             Project: Kafka
          Issue Type: Improvement
          Components: group-coordinator
            Reporter: Sean Quah


h3. Background
  {{MultiThreadedEventProcessor}} pulls events from {{EventAccumulator}}, which 
keeps a queue per coordinator shard ({{TopicPartition}}) and ensures that only 
one event per shard is in flight at a time. On each {{poll}}, a shard is chosen 
uniformly at random from {{availableKeys}}
  ({{EventAccumulator#randomKey}}). One event is dequeued, and the shard is 
returned to {{availableKeys}} by {{done}} if it still has pending events.

  h3. Problems
  # *Random shard selection has an unbounded tail.* The expected wait for a 
ready shard matches round-robin, but a shard can lose many draws in a row. This 
inflates the tail of {{event-queue-time-ms}}. For a small 3-broker cluster, 
each node hosts ~17 shards. The p99 number of lost draws when all shards are 
busy is 75.
  # *{{enqueueFirst}} only takes priority within its own shard.* 
{{HighWatermarkUpdate}} and {{FlushBatch}} events go to the front of their 
shard's queue, but the shard still competes equally with every other ready 
shard. When the processor threads are saturated, a write request pays the 
processor queue time    
  once for its write event and again for its {{HighWatermarkUpdate}}, plus once 
more for {{FlushBatch}} when linger is enabled. These events are cheap, and a 
single {{HighWatermarkUpdate}} completes every deferred write on the shard up 
to the new high watermark.

  h3. Proposal
  # Replace random selection with a deterministic policy. Options:
  #* *Round-robin:* a FIFO ready queue ({{ArrayDeque<K>}}). This is O(1) and 
bounds a shard's wait to one rotation of the other ready shards.
  #* *Most delayed first:* a heap of ready shards keyed by the 
{{createdTimeMs}} of their head event. This directly minimizes the maximum 
queue time, at O(log n) per operation. A shard whose queue keeps growing gets 
picked more often, so it gives less isolation between shards than round-robin.
  # Give shards made ready by {{addFirst}} precedence over other ready shards. 
With round-robin, put the shard at the head of the ready queue. With a heap, 
the HWM event is newer than the writes it completes, so the key can't be the 
head event's {{createdTimeMs}}. It needs a priority class or the age of the     
  oldest deferred write instead. {{addFirst}} also changes the head of a shard 
that is already in the heap, so the shard would have to be re-keyed.




--
This message was sent by Atlassian Jira
(v10.3.26#10030026)

Reply via email to