jm + timing-wheels   2

Ratas - A hierarchical timer wheel
excellent explanation and benchmarks of a timer wheel implementation
timer-wheels  timing-wheels  algorithms  c  linux  timers  data-structures 
august 2016 by jm
Apache Kafka, Purgatory, and Hierarchical Timing Wheels
In the new design, we use Hierarchical Timing Wheels for the timeout timer and DelayQueue of timer buckets to advance the clock on demand. Completed requests are removed from the timer queue immediately with O(1) cost. The buckets remain in the delay queue, however, the number of buckets is bounded. And, in a healthy system, most of the requests are satisfied before timeout, and many of the buckets become empty before pulled out of the delay queue. Thus, the timer should rarely have the buckets of the lower interval. The advantage of this design is that the number of requests in the timer queue is the number of pending requests exactly at any time. This allows us to estimate the number of requests need to be purged. We can avoid unnecessary purge operation of the watcher lists. As the result we achieve a higher scalability in terms of request rate with much better CPU usage.
algorithms  timers  kafka  scheduling  timing-wheels  delayqueue  queueing 
october 2015 by jm

Copy this bookmark: