How does Kafka's TimingWheel work and why is it used in Purgatory?

Kafka's purgatory holds delayed operations, such as a produce request waiting for enough acknowledgements or a fetch request waiting for a given number of bytes (fetch.min.bytes) to accumulate, until the condition is met or a timeout expires. Timeouts are tracked by a hierarchical timing wheel (the TimingWheel class). A simple timing wheel is a circular list of buckets, each covering a time range; the clock ticks to the next bucket and expires all timer tasks in it. One wheel only covers n times its tick interval, so tasks beyond that overflow into a wheel one level higher with coarser buckets; when the higher wheel ticks, its tasks are reinserted into the finer wheel (cascading) or run. The source documents that a timing wheel has O(1) insert and delete, whereas priority-queue based timers such as DelayQueue have O(log n); with hierarchical wheels insert costs O(m), where m is the number of wheels and is usually small, and delete stays O(1). This works especially well when operations complete before they time out, which is the common case for acknowledgements and fetches.

Expected key concepts: TimingWheel, hierarchical, circular list, buckets, cascading, O(1), O(m), O(log n), priority-queue, Purgatory, fetch.min.bytes