Understanding TCP Timers and Timer Wheels

Slide Note

Explore the purpose-built TCP timers designed by Dave Barach for fd.io Foundation. Delve into the two-level wheel algorithm with a timer granularity of 100ms, capable of handling up to 20 million concurrent timers. Learn about the timer wheels' operation, APIs for starting, stopping, and processing timers, as well as callback mechanisms. Discover the lightweight API details for managing timers efficiently.

elff727 Follow

Uploaded on Dec 07, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript

TCP Timers Dave Barach, 11/17/2016 1 fd.io Foundation

Introduction Purpose-built TCP timers, not necessarily suitable for other use- cases Two-level wheel algorithm Design / scale parameters Timer granularity 100ms. Easy enough to change to 50 or 200 ms Required max period: 2.5 hours => 150 minutes => 90,000 ticks Rounding up to 256K ticks yields a two-level, 512 slot-per-level wheel ~7 hr max timer duration Tested to 20e6 concurrent timers, 28 million operations per second 2

Timer wheels An odometer algorithm, vaguely related to WW2 Enigma machines When the fast wheel finishes a complete revolution, we advance the slow ring one slot Fast wheel slots correspond to one timer tick (100ms) Slow wheel slots correspond to 512 timer ticks (51.2s) At each slow wheel tick, we redistribute timers from the slow wheel into the fast wheel 3

APIs Start timer Stop timer Process expired timers Initialize a timer wheel object Destroy a timer wheel object 4

Callbacks Here s a vector of new stop-timer handles When we advance the slow wheel, we redistribute timers from the now- current slot in the slow wheel to the appropriate slots the fast wheel Stop timer handles encode (wheel, slot, element within slot) Happens once every 51.2 seconds Here s a vector of expired timers 5

API details u32 tcp_timer_start (tcp_timer_wheel_t * tw, u32 pool_index, u32 timer_id, u32 interval) Starts a timer to expire in <interval> 100ms clock ticks When the timer expires, the expired-session callback will receive the indicate timer as a vector element in a vector of (pool_index, timer_index) tuples Returns a timer cancellation handle which encodes the timer s (ring, slot, element-within-slot). The caller must memorize the handle. 6

API details void tcp_timer_stop (tcp_timer_wheel_t * tw, u32 pool_index, u32 timer_id, u32 cancellation_handle) Stop the indicated timer Pool_index and timer_id are passed to allow consistency checking Super light-weight: sets one bit to 0 in a bitmap 7

API details void tcp_timer_expire_timers (tcp_timer_wheel_t * tw, f64 now) Expires timers now is expected to be in (double) seconds 8

Callback details static void expired_timer_callback (u32 * expired_timers) Process a (u32 *) vector Each vector element encodes a (pool-index, timer-id) pair for (i = 0; i < vec_len(expired_timers); i++) { pool_index = expired_timers[i] & 0x0FFFFFFF; timer_id = expired_timers[i] >> 28; /* $$$ your message in this space */ } 9

Callback details static void new_stop_timer_handle_callback (new_stop_timer_callback_args_t * a_vec) Each vector element contains a (pool-index, timer-id, new-handle) tuple: for (i = 0; i < vec_len(a_vec); i++) { a = a_vec + i; session = pool_elt_at_index (xxx->sessions, a- >pool_index); session->timers[a->timer_id].stop_timer_handle = a->new_stop_timer_handle; } 10