Pre-RFC: Built-in timeout/deadline functionality for Futures

[srijs]

So I just finished converting rusoto to futures/tokio, and we'll be cutting a new release soon! 🎉

With that out of the door, I wanted to see if I can feed some ideas back that I had while working on the conversion...

One of the major challenges in that process was implementing timeouts. The design goal was to keep the core of Rusoto independent of any event loop functionality (no direct tokio dependency), and only based it on futures. This made implementing timeouts tricky, since current approaches are either coupled to tokio (Timeout in tokio-core) or need to spawn an additional thread (tokio-timer). This required us to push the complexity of timeout handling into the pluggable parts that do depend on tokio/hyper, but IMO it would have been preferable to separate these concerns.

It would be neat if there was some built-in timeout functionality in futures itself, perhaps as part of thread park/wait mechanism. This would enable things like a pure-futures Timeout combinator, or perhaps even implementing some idle timeout tracking for AsyncRead. If there is general interest to support something like it, I'd be willing to write up an RFC to facilitate more discussion around how to approach it.

Familiarising myself with the futures 0.2 architecture, I came up with the following straw-man proposal (I'm confident there are much better ways to achieve this). I thought I'd just float this and see if something sticks :)

Let me know what you think! (and please also don't hesitate to tell me if I'm way off track here)

---

Staw-man Proposal

Changes to futures-core

The idea here is to keep track of a deadline/timeout on the task context.

struct Waker {
    ...,
    timeout_ms: AtomicUsize // initialised to usize::MAX
}

impl Waker {
    ...

    fn set_timeout_ms(&self, ms: usize) {
        // atomically set `self.timeout_ms` to the min of `ms` and `self.timeout_ms`
    }

    fn reset_timeout_ms(&self) -> usize {
      // atomically reset `self.timeout_ms` to usize::MAX and return the last timeout set
    }
}

impl<'a> Context<'a> {
    pub fn set_timeout_ms(&self,  ms: usize) {
        self.waker.set_timeout(ms);
    }
}

Changes to futures-executor

Executors will now need to be aware of the timeout setting on the Waker, and incorporate that into their parking logic.

Example for local-pool.rs

fn run_executor<T, F: FnMut(&Waker) -> Async<T>>(mut f: F) -> T {
    ...

    ThreadNotify::with_current(|thread| {
        let waker = &Waker::from(thread.clone());
        loop {
            if let Async::Ready(t) = f(waker) {
                return t;
            }
            let timeout = waker.reset_timeout_ms();
            thread.park_timeout(Duration::from_millis(timeout as u64));
        }
    })
}

Alternatives

An alternative could be to extend the Async<T> enum to be Async::Ready(T) or Async::NotReady(Option<Duration>). That would avoid having to move the timeout as atomics into Waker, but on the downside it complicates the futures contract for the 90% of futures that don't need timeouts.

[srijs]

Expanding on this, a Timeout combinator (mimicking tokio_core::reactor::Timeout) could then be implemented like:

struct Timeout {
    instant: Instant
}

impl Timeout {
    pub fn new(duration: Duration) -> Timeout {
        Timeout { instant: Instant::now() + duration }
    }
}

impl Future for Timeout {
    type Item = ();
    type Error = Never;

    fn poll(&mut self,  cx: &mut task::Context) -> Poll<Self::Item, Self::Error> {
        let now = Instant::now();
        if now < self.instant {
            cx.set_timeout_ms(/* figure out distance in ms between now and self.instant */);
            // the futures contract would be expanded, so that when a poll() returns NotReady, it either:
            // - must wake up the task at a later point, or
            // - must have set a timeout on the context before returning
            Ok(Async::NotReady)
        } else {
            Ok(Async::Ready(()))
        }
    }
}

[alexcrichton]

This is how I personally at least interpreted #198 and my conclusion was that this isn't something we should put into the core futures themselves.

Is there a reason though that something like futures-timer wouldn't work?

[carllerche]

IMO, the best strategy is going to be some trait that lib authors can use.

Tokio will be giving tokio-timer an overhaul and integrating it into the runtime. Specifically, the timer logic will be embedded as part of the work-stealing scheduler such that timers are kept close to the tasks that need them.

[srijs]

Hmm, somehow #198 wasn't on my radar when proposing this.

Based on the discussion happening there and your comments here, it seems to me like this may be a classical 2/3 situation where two out of these three are achievable, but not all:

1. The implementation of an executor does not need to worry about timeouts
2. Timeouts are possible without spawning an additional thread to handle a timer wheel
3. Timeouts are decoupled from the event loop implementation

From my understanding, futures-timer would tick (1) and (3), by sacrificing (2), and tokio embedding the logic as part of its scheduler would tick (1) and (2) by sacrificing (3), is that accurate?

As someone who's never written an executor, perhaps unsurprisingly, my view was that 2 and 3 are desirable over 1, with the rationale that the number of executors that will be implemented in the futures ecosystem are likely much fewer than the number of users that would like to use futures-based timeouts in their library or application, so therefore the impact of 1 would be smaller.

From your comments in the other issue it sounds like you are concerned about the impact of (1), would that be fair to say, @alexcrichton?

I'll keep thinking about this, maybe there's a way to achieve all three after all...

[aturon]

FWIW I'd love to see timeout functionality integrated into futures in a pluggable manner (much like the new executor model). @carllerche and I have worked through API designs that may allow that, but we need to revisit after the dust settles with 0.2.

@srijs, I'd love to work with you on this! I don't have time today, but I can try soon to write up a braindump of what we'd explored in the past.

[srijs]

That sounds great, @aturon, I'd love to help make this happen!

I'll continue exploring this avenue here a bit, and once you find the time to write up the brain dump that should provide a better direction to probe :)

To understand the broader context a bit better, what was the envisioning like around having different executors? For instance, in which cases would you write your own executor, how many different executors would we generally expect to appear in the ecosystem (order of magnitude?), etc.

If there's anything written up on it, please just point me there and I'll go and do my homework! :)

[carllerche]

I wrote this up at one point: tokio-rs/tokio-rfcs#2 (comment)

[srijs]

Okay, I'm getting back to exploring this today.

@carllerche Thanks for the pointer! You wrote this in your comment:

Now, given that locality is key. The way timers would fit in to futures-pool would be for each thread in the pool to have its own timer. This way, when a future sets a timeout, it would require no cross thread communication and when the timeout fires, it would notify a future that is (ideally) on its thread.

Do I understand this correctly in that you believe timers should be a responsibility of the executor rather than the event loop (or some external logic/thread)?

[cramertj]

There are existing libraries that can be used to add timeouts to futures, but the core Future trait defined in std does not include any special allowances for timeouts-- I don't believe it needs any.

[Ekleog]

@cramertj What do you suggest, for a library that wants to add timeouts to the future combinators it generates?

[cramertj]

@Ekleog something like tokio-timer or futures-timer which uses either the eventloop or a separate thread to track a queue of timing events.

[Ekleog]

@cramertj I'm not sure about futures-timer, but tokio-timer enforces using the tokio executor, does it not? (that's how I read the hard-dep on tokio-executor at least) I wouldn't want that from a library.

And AFAIU futures-timer means that on platforms that can't spawn new threads the library wouldn't work, which doesn't really make sense (eg. a library for a protocol could perfectly run over serial wire on a bare-metal embedded device, without such a requirement -- just need to code the clock).

So both of those mean that using timeouts would unnecessarily split the ecosystem, either between tokio and not-tokio, or between thread-able and non-thread-able. While the second one sounds much less bad, I still think that we can do a better job abstracting such common things out? Not necessarily built-in Future, but in some enshrined place.

That said, I've for a while thought of writing a trait-only crate that'd abstract over the exact executor and only provide only bare capabilities (timeout, network, file, etc.), that each executor would then implement; maybe it'd be better to start this way actually. Never had the time to actually work on that, unfortunately.

[Pauan]

@Ekleog That split already exists: wasm does not support threads, so it cannot use any of the futures-executor Executors, instead it has to create its own Executor from scratch.

And similarly, we can't use existing timer crates (since they don't work on wasm), so we had to create our own timer system. That's just how it is for some targets, you can't really expect perfect portability.

Having said that, I think it would be reasonable for the futures-timer crate to use cfg (and features) to provide different implementations for different targets, so that way it can work even on targets which don't have threads (instead it would use some other primitive).

[Ekleog]

@Pauan I'm not saying we don't have to write executors or timer systems, what I'm saying is it'd be way better for third-party libraries (random interested thought: a library for the SMTP protocol that uses just future combinators and timeouts, plus an optional part for opening network sockets) to not have to say “I won't work on platform X, Y and Z.” Actually your point reinforces mine, I would think? :)

[Pauan]

@Ekleog It sounded like you were against the idea of a futures-timer crate, and I was just pointing out that it's possible for such a crate to work on thread-less targets. So yes, perhaps we are in agreement.

[Ekleog]

@Pauan Do you mean having futures-timer embed the implementation for all targets under #[cfg]? I'm assuming that's unreasonable, and we'd need to have distinct futures-timer and futures-timer-wasm crates -- and then my SMTP library can't be generic over these two unless they share some kind of trait.

[Pauan]

@Ekleog Why is that unreasonable? It's quite common: that's what rand and chrono do, for example (they have a separate wasm implementation behind a cfg).

Another example is how we use cfg to automatically enable a multi-threaded implementation when threads are supported. It's really not a big deal.

In fact, that's the standard idiomatic way of handling different targets in Rust (it's literally what cfg was designed to do).

It's also not hard at all to use the same implementation for multiple targets, since cfg supports or. (Or you could use features for that, which would also work fine). So there won't be any code duplication.

[Ekleog]

@Pauan What I mean is that, for the similarity with rand and chrono to be correct, your work should be upstreamed as a #[cfg] of futures-timer.

My SMTP library should not have to make a choice between wasm and not-wasm, because it's not something it should be interested in.

Another solution to upstreaming all the targets into futures-timer would be to parameterize my SMTP library over a timer implementation, which could be done if the timer implementation was a trait of some sort. I must say I even prefer this way, though that's not the idiomatic way of doing it, because it's much more flexible when a new target arises -- it's possible to hack on it without having to upstream anything, yet use the whole ecosystem.

[Pauan]

@Ekleog What I mean is that, for the similarity with rand and chrono to be correct, your work should be upstreamed as a #[cfg] of futures-timer.

Yes, and? Why is that a problem? The wasm code has to live somewhere, and the best place for it to live is in futures-timer (or a similar crate).

My SMTP library should not have to make a choice between wasm and not-wasm, because it's not something it should be interested in.

And it doesn't need to make that choice. It can just depend on futures-timer and everything will work fine. That's how rand and chrono (and others) work today.

Another solution to upstreaming all the targets into futures-timer would be to parameterize my SMTP library over a timer implementation, which could be done if the timer implementation was a trait of some sort.

There's really no need (or benefit) for a trait in this case. It just adds a lot of extra complexity both for the implementation and the users.

Of course there's nothing wrong with creating a trait for this, but the cfg approach must also be provided (for those that don't want to use the trait).

because it's much more flexible when a new target arises -- it's possible to hack on it without having to upstream anything, yet use the whole ecosystem.

You would still have to make a new impl for the trait, so it isn't more flexible. And it's far better to upstream, because then everybody benefits immediately, rather than only you. Upstreaming really isn't that hard, people do it all the time.

Also, the cfg approach is much more flexible because you can use not patterns, so you can have a default implementation which works for all targets (including new targets), and then have specialized cfg only for the targets which need it (like wasm). You can't do that with traits (at least not yet).

It does not need to make a new implementation for every single target (which you seem to be assuming). Like I said, there won't be any code duplication. The cfg system works well, it was specifically designed for this use case.

[Ekleog]

@Pauan Based on your latest message, I guess we agree on the problem statement, just not on the solution.

Upstreaming really isn't that hard, people do it all the time.

Then why is rustwasm's implementation not upstream? Note I don't mean this as an attack, it's just that I do believe upstreaming stuff for weird targets is hard. Especially when it comes to platforms that are under NDA and you, if you are unlucky, just cannot upstream, even if you wanted to.

Also, the cfg approach is much more flexible because you can use not patterns, so you can have a default implementation which works for all targets (including new targets), and then have specialized cfg only for the targets which need it (like wasm).

This is not more flexible, though, it's more convenient. The trait approach would, as you state, be much less convenient (in particular because there are no default generic arguments yet that work in my experience -- unless things have changed recently), but would not be more flexible.

Like I said, there won't be any code duplication. The cfg system works well, it was specifically designed for this use case.

If it is at all possible to use the cfg system, then yes. My issue is I've already been hit by it, and do not trust it to do its job.

For instance, the mere existence of tokio-timer is proof that the cfg system does not work well in practice, as otherwise tokio-timer would just be futures-timer with a cfg of tokio -- this split between the two is the first crack in the cfg system, that works well only when there is a single well-known implementation of the crate.