RFC: Delayed cancellation of timer

[ADD-SP]

Summary

Please check out the #6504 for initial context.

This design reduces the lock contention of the time module, this improves the scalability for the async server to read/write async sockets with timeout.

• Use a local wheel for each worker thread instead of a global wheel.
• Do not register the timer into the wheel on creation.
• Register timer into the local wheel on the first poll.
• Cancel a timer by removing it from the local wheel directly if this timer is canceled by local thread.
• Cancel a timer by sending the intrusive list entry using std::sync::mpsc to the worker thread that owns it if this timer is canceled by remote thread.

Current Implementation

You can skip it if you are already familiar with the codebase.

There is a global wheel protected by std::sync::Mutex, so we have to acquire the Mutex before registering and cancelling a timer.

Resetting a timer doesn't acquire the Mutex as it just updates an AtomicU64.

What's the problem?

Worker threads can concurrently process their owned sockets, this is scalable.

However, since timer is heavily used for socket timeout in async server/client, there are many lock contentions while read/write a async socket with timeout, which introduces much lock contentions.

What have we tried?

commit: time: use sharding for timer implementation

This commit splits the global wheel into several wheels (indexed by thread_id), and wraps it by Mutex in the Runtime,

• To calculate the earliest timer, it locks all wheels one-by-one while parking the driver.
• To register/cancel a timer, it locks the specific wheel and removes it.

Unfortunately, this was reverted by 1ae9434 due to the overhead of locking multiple Mutex in hot paths is much more expensive than the global lock contention.

How does the kernel handle this case?

I'm not a kernel developer, please correct me if I'm wrong.

For non-hrtimer, all timers are registered into a per-CPU timer wheel, and the kernel also locks the per-CPU timer wheel when registering/canceling the timer.

This looks just like what we did in time: use sharding for timer implementation (already been reverted).

However, I think the big difference is that kernel spinlocks the per-CPU wheel, this is much more efficient than user space Mutex since the kernel is able to control the kernel scheduler and interrupt.

With the benefits of spinlock in kernel context, the lock contention should be much less than userspace Mutex.

So we cannot reference the kernel's design directly.

How does Golang handle this case?

I'm not a Golang expert, please correct me if I'm wrong.

Golang uses per-GOPROC 4-ary heap to register all timers.

Golang marks the timer as deleted canceling a timer, and marked timers will be deleted while registering a new timer if the marked timer is at the top of the heap.

Because all timers are delayed for removing from the per-GOPROC heap, registering a new timer doesn’t need to acquire the lock.

The cost of this design is that if too many (>= 1/4) marked timers are not at the top of the heap, GOPROC must be stopped to scan the entire 4-ary heap, which means trigger a O(nlgn) operations at an any time, which could lead to task starvation.

This might not acceptable in tokio.

How does pingora handle this case?

Pingora faced the similar issue, so it has its own timeout implementation.

• Per-thread RwLock<BTreeMap<u128, Timer>>
• A dedicated thread periodically polls all per-thread BTreeMap, fires expired timers, and removes canceled timers.
• All timers will be rounded to next 10ms.
• Cloning the existing timer instead of inserting a new one (into BTreeMap) if there is already a timer at the same 10ms while registering a new one.
• Canceling a timer does nothing, its memory can only be released after that dedicated thread reaches that timestamp.

Pingora's solution is good at dealing with the socket timeout, we can reference something during the implementing.

Proposed design

The initial idea came from @carllerche .

What does the new TimerEntry look like?

struct TimerEntry {
   // -- omitted -- 
   deadline: Instant,
   node: Option<NonNull<TimerShared>>, // stored into the intrusive list
   // -- omitted --
}

Where is the local wheel stored?

It stores in the Core that also stores the queue::Local.

How to register a new timer?

1. Retrieve the runtime handle using thread-local CONTEXT.
   1. panic on error (such as no context).
2. Retrieve the local worker Context.
   1. Register timer to the local wheel if the Core is here.
   2. Otherwise, push into the inject timer list, this list will be drained while maintaining the local core.

How to cancel a timer?

1. Just drop the handle if this timer has never been registered.
2. Otherwise, mark the timer as deleted in AtomicU64.
3. Send the timer using std::mpsc::Sender, the Receiver is owned by Core, the sender was stored in TimerEntry when creating it.
4. The core drains the receiver and remove timers from the local wheel.

How to wake up timer?

Timers that were registered in the current worker thread's local wheel will be polled while maintaining the local core, and the AtomicWaker is used for waking up.

Overhead of the extra memory allocation

This design requires the extra memory allocation of the node to be saved in an intrusive list compared to the current design.

This should not be a big concern because modern allocator has well multi-core scalability, so the extra allocation should be cheaper than global lock contention.

FAQ

Will be added progressively as the discussion progresses.

Will the timer be delayed too much if the worker thread is blocked for a long timer?

Yes, timers were registered on the local wheel might be delayed too much in this case, but I think is not a big issue, please check out the #7384 (comment) for detailed explanation.

Does sending pending cancel timers through std::sync::mpsc causes extra memory allocation?

Yes, an extra slot will be allocated for saving the value in the channel. The good news is that the standard mpsc optimises this case, please check out the #7384 (comment) for detailed explanation.

[Darksonn]

I think the biggest question here is how wakeups are carried out. Right now, the single worker thread that sleeps on epoll does so with a timeout equal to the globally smallest timer, which meant that whenever the thread goes to sleep on epoll, it has to lock every shard to determine the smallest timer. The question is ... what is your proposal here? Do we change it so that each worker thread sleeps with a timeout equal to the smallest timer on its own local queue?

Currently, the runtime continues working okay if one of your worker threads get blocked, and people might rely on that. Yes, there are some caveats to this such as the LIFO slot, but I still suspect people still rely on it working.

[ADD-SP]

@Darksonn Thanks for you comment!

Do we change it so that each worker thread sleeps with a timeout equal to the smallest timer on its own local queue?

Yes, I propose let each worker thread sleep with a local-smallest timeout. The highly level summary is getting the local-smallest timer before try_locking the driver.

For example, I propose to fire expired timer and get the local-smallest timer before line 763.

tokio/tokio/src/runtime/scheduler/multi_thread/worker.rs

Lines 753 to 782 in c38de96

	fn park_timeout(&self, mut core: Box<Core>, duration: Option<Duration>) -> Box<Core> {
	self.assert_lifo_enabled_is_correct(&core);
	// Take the parker out of core
	let mut park = core.park.take().expect("park missing");
	// Store `core` in context
	*self.core.borrow_mut() = Some(core);
	// Park thread
	if let Some(timeout) = duration {
	park.park_timeout(&self.worker.handle.driver, timeout);
	} else {
	park.park(&self.worker.handle.driver);
	}
	self.defer.wake();
	// Remove `core` from context
	core = self.core.borrow_mut().take().expect("core missing");
	// Place `park` back in `core`
	core.park = Some(park);
	if core.should_notify_others() {
	self.worker.handle.notify_parked_local();
	}
	core
	}

[ADD-SP]

@Darksonn Just another section for the original reply to avoid long comment.

---

Currently, the runtime continues working okay if one of your worker threads get blocked

Just checking to see if I understood the quote correctly. The local timer may be significantly delayed if the worker thread is blocked (such as synchronous I/O) for a long time. Is this what you are trying to indicate?

---

and people might rely on that

I agree that there is a law which states that any feature (or perhaps a bug) which has been released will always have users who rely on it.

In my opinion, it's not a big issue because two asynchronous runtimes also face this issue, yet this hasn't prevented them from being widely used (or becoming a major issue).

Golang also uses the work-stealing scheduler, but not for the timer itself. This causes a significant delay. There is a relevant open issue (golang/go#45632) from 2021.

Nginx is facing the same issue. The following code snippet calculates the smallest timer for the worker process, which will be used for the epoll_wait timeout.

https://github.com/nginx/nginx/blob/5b8a5c08ce28639e788734b2528faad70baa113c/src/event/ngx_event_timer.c#L47

ngx_msec_t
ngx_event_find_timer(void)
{
    ngx_msec_int_t      timer;
    ngx_rbtree_node_t  *node, *root, *sentinel;

    if (ngx_event_timer_rbtree.root == &ngx_event_timer_sentinel) {
        return NGX_TIMER_INFINITE;
    }

    root = ngx_event_timer_rbtree.root;
    sentinel = ngx_event_timer_rbtree.sentinel;

    node = ngx_rbtree_min(root, sentinel);

    // `ngx_current_msec` is a cached timestamp,
    // and will be updated after the epoll_wait.
    timer = (ngx_msec_int_t) (node->key - ngx_current_msec);

    return (ngx_msec_t) (timer > 0 ? timer : 0);
}

A developer of Nginx modules asked about the same issue on the mailing list How to avoid blocking Nginx with long requests, and the answer was to avoid blocking the event loop.

In summary, I believe this is a native limitation of the async runtime. It's not worth letting best-effort mitigation hinder subsequent development.

[Darksonn]

I guess this is another instance of #6315.

[ADD-SP]

I guess this is another instance of #6315.

@Darksonn I left some of my thoughts in #6315.

[carllerche]

Thanks for the detailed RFC. It explains the situation and proposal well.

Regarding canceling a timer:

Send the timer using std::mpsc::Sender, the Receiver is owned by Core, the sender was stored in TimerEntry when creating it.

Before sending the timer using a channel, the cancellation routine can check if the timer is registered with the local wheel and immediately remove it. My second thought is that using a channel will result in an allocation per cancellation. If it is limited to cross-thread cancellations, it might be OK. However, the allocation isn't strictly necessary as the timer itself is already allocated and could include an extra pointer slot to handle a mechanism to send the timer across threads.

Currently, the runtime continues working okay if one of your worker threads get blocked

Alice's point here is valid. If a worker gets blocked because of a slow task, all timers on that worker will be delayed. I don't necessarily think that this is a blocker because 1) Tokio expects apps to be well behaved in general 2) Tokio timers not intended to be precise, so a delay isn't the end of the world 3) I'm starting to believe the best way to have the runtime "tolerate slow task polls" is a completely new runtime strategy that is overall slower but more tolerant of slow polls (the user can pick the runtime they want).

Personally, I am OK with continuing with this avenue of exploration.

[Noah-Kennedy]

Nginx is facing the same issue. The following code snippet calculates the smallest timer for the worker process, which will be used for the epoll_wait timeout.

https://github.com/nginx/nginx/blob/5b8a5c08ce28639e788734b2528faad70baa113c/src/event/ngx_event_timer.c#L47

ngx_msec_t
ngx_event_find_timer(void)
{
ngx_msec_int_t timer;
ngx_rbtree_node_t *node, *root, *sentinel;

if (ngx_event_timer_rbtree.root == &ngx_event_timer_sentinel) {
    return NGX_TIMER_INFINITE;
}

root = ngx_event_timer_rbtree.root;
sentinel = ngx_event_timer_rbtree.sentinel;

node = ngx_rbtree_min(root, sentinel);

// `ngx_current_msec` is a cached timestamp,
// and will be updated after the epoll_wait.
timer = (ngx_msec_int_t) (node->key - ngx_current_msec);

return (ngx_msec_t) (timer > 0 ? timer : 0);

}

A developer of Nginx modules asked about the same issue on the mailing list How to avoid blocking Nginx with long requests, and the answer was to avoid blocking the event loop.

Nginx is a shared-nothing system, and as such the timer wheels are going to be local because everything is local.

[ADD-SP]

Nginx is a shared-nothing system, and as such the timer wheels are going to be local because everything is local.

@Noah-Kennedy Yes, I agreed that (almost) everything is local in Nginx.

I don't think it's appropriate for me to mention the Nginx example in this issue, I think #6315 is a more appropriate place. This example focuses on the tolerance of cpu-hogged task for async runtime.

[Noah-Kennedy]

At Cloudflare, we wrote our own timer wheel for our Pingora family of proxies which addresses many of the issues listed here for us: https://github.com/cloudflare/pingora/tree/main/pingora-timeout

As someone who would like to get rid of it, I'm going to walk through what we did differently when this was written several years ago.

The first change we made was to lazily register timers as was done in tokio last year in #6512 - this was by far the most significant change we made.

The second change we made was to not de-register timers until they expire and to reduce timer precision and batch together timer events, similar to what golang does. This has led to past production issues with memory leaks when timer events are scheduled very far out, and thus is something I think we should be careful about doing here, unless we garbage collect these if the number of pending registrations gets too great, similar to golang.

The third change we made was to have per-thread timer wheels for insertion purposes only - these wheels are still synchronized and are advanced by a common driver, thus meaning that they aren't susceptible to the previously-discussed issues around blocking on worker threads. This optimization was aimed specifically at reducing contention due to multiple registrations happening at once.

[ADD-SP]

@carllerche Thanks for your comment!

My second thought is that using a channel will result in an allocation per cancellation.

Thanks for pointing this out.

I agree, theoretically we need n additional memory allocations to cancel the n timers. So I took a while to look at the implementation of std::sync::mpsc.

https://github.com/rust-lang/rust/blob/6c8138de8f1c96b2f66adbbc0e37c73525444750/library/std/src/sync/mpmc/list.rs#L61

I think the standard mpsc optimises the memory allocation, it doesn't allocates an slot for per send, so the extra allocations might be N / BLOCK_CAP, this might reduce your concern on this area.

I also added this answer to the FAQ section.

[Darksonn]

The std::sync::mpsc channel has logic so that the receiver can block until a message is sent. We don't need that - we just want to check whether there are messages or not, so we don't need a channel. We just need a queue or stack.

[Congyuwang]

Maybe something like a ringbuffer: https://github.com/agerasev/ringbuf