future explained(1)

在Post not found: rust/future-explained0 上一篇文章中，我们深入分析了 async/await 状态机的底层实现，接下我们就可以进一步探究，Rust 中的 Future ，以及为什么会出现 自引用结构。

1. Future 是什么

在浏览本节之前，希望你可以大致了解一下 Future 设计思想的演进过程，比如 javascript 中的 Promise

那么 Rust 中的 Future 是什么？

Future 是一些将在未来完成操作的表示。

Rust 中的异步机制使用的是基于轮询（Poll）的方法，一个异步任务会有三个阶段。

1. 轮询阶段。 对一个 Future 进行轮询，推进其向前执行，直到不能再执行下去（被阻塞）。我们常把运行时中对 Future 进行轮询的部分称为执行器（executor）。
2. 等待阶段。 一个事件源，最常被称为反应器（reactor），它注册一个 Future 正在等待一个事件的发生，并确保在该事件准备好时，它将唤醒 Future。
3. 唤醒阶段。 事件发生了，Future 被唤醒了。现在，在第 1 步中轮询 Future 的执行器要安排 Future 再次被轮询，并继续推进其执行，直到它完成或达到一个新的阻塞点，重复这个循环。

你可能对上面的一些术语不是很清楚，接下来我会慢慢解释。

1.1 Executor

首先，你可以大致将 executor 看成是 future queue + poll loop，它的任务就是不断从 future 队列中取出 future，然后执行 poll 方法。一个最简单的 executor 其实很简单，基本上等同于一个 loop 循环。但是如果想要高效地进行调度，那就需要利用到很多策略了。

loop {
    while let Some(f) = receiver.recv() {
        f.poll(...);
        ...
    }
}

1.2 Reactor

有了 executor 还不够，因为一个应用，终归是要和底层 IO 打交道的（纯计算应用勿Q），如果 executor 很高效，但是 Io 效率很低，那么 Io 就会成为应用的性能瓶颈。

系统层面的 Io，大致可以按照 同步/异步，阻塞/非阻塞 分为几种模型：

1. 同步阻塞
2. 同步非阻塞
3. 异步阻塞
4. 异步非阻塞

目前各个操作系统的底层，几乎都采用了事件驱动的 IO 多路复用模型，在 Linux 上是 epoll，而在 windows 和 macOS 这种成熟的系统上，也分别有 iocp 和 kqueue。它们本质上做了这件事：当某一次操作依赖于某些资源的时候，需要向操作系统注册，告诉系统：等这个资源准备好之后，再来通知我，否则将我挂起。

因此可以做一个跨平台的抽象：reactor。含义是：当事件发生的时候，对此做出反应。

Tips:
  其实系统的阻塞 API 也是完成了这件事情，比如 socket 默认就是阻塞的模型，当 accept 一个 socket 的时候，整个进程都有可能陷入阻  塞状态，造成当前进程无法充分利用 CPU。但是 epoll 这种 IO 多路复用的模型，其实可以通过一个红黑树，高效地帮助我们监听多个文件描  述符，每次从内核返回，会将所有的 ready 状态的描述符都返回给用户，达到了 batch 操作的效果。

1.3 executor + reactor

当我们将 executor 和 reactor 组合在一起，一个 runtime 框架就已经成型了。因为一个应用，要么在耗费 CPU 计算，要么在等待 Io 操作（资源）。

可以想象，如果是一个既涉及 CPU 计算，也要涉及底层 IO 的 future，其实会不断地在 executor 和 reactor 之间轮转：需要计算时，交给 executor 执行，需要 IO 的时候，交给 reactor，由 reactor 负责事件通知，资源准备好了之后，又交给 executor 执行，循环往复，直到该 future 执行完毕。

2. Leaf Future VS Non-Leaf Future

上面提到，future 可以区分为 CPU/IO 两种类型，那么反映在其创建方式上，又是什么样的呢？

future 有两种实现方式，一种是手动为某一个类型实现 Future trait，另一种是通过 async/await 关键字创建，分别对应 Leaf-future 和 Non-leaf-future（第二小节会解释为什么这样取名）。

2.1 叶子 Futures

先来看 Leaf Futures，它们代表系统中的 IO 资源，比如 socket，file，timer。

// stream is a leaf-future
let mut stream = tokio::net::TcpStream::connect("127.0.0.1:3000");

对 IO 资源的操作，比如对 socket 的 Read 将是非阻塞的，并返回一个 future，称之为叶子 future。之所以要求非阻塞，是因为只有这样，才能将所有权牢牢抓在用户态的 runtime 手里，否则一旦阻塞，当前进程就会被操作系统调度出去，效率就降低了。

Tips:
  除非你要写一个 runtime，否则你不太可能自己实现一个叶子 Future，或者更多的是针对 Leaf-Future 的封装。

2.2 非叶子 Futures

Non-leaf-futures 是指作为 runtime 的用户，使用 async 关键字自己编写的 Future，用于创建一个可以在执行器上运行的任务。

一个异步程序大部分由非叶子 Futures 组成，它是一种可暂停的计算。这是一个重要的区别，因为这些 Futures 代表了一组操作。通常，这样的任务会等待（await）一个叶子 Future 作为完成任务的许多操作之一。

// Non-leaf-future
let non_leaf = async {
    let mut stream = TcpStream::connect("127.0.0.1:3000").await.unwrap();// <- yield
    println!("connected!");
    let result = stream.write(b"hello world\n").await; // <- yield
    println!("message sent!");
    ...
};

3. async 状态机

之前的文章已经详细解释了 async/await 的实现原理，本质上是一个状态机。

一个 Future 在某个时刻只会都只有唯一的状态，因此，可以用 enum 表示，为每一个可能存在的状态，都生成一个对应的 State，比如下面的 AsyncState，这样，我们只需要为 future 分配状态最大需要占用的内存，其余的状态下，都可以复用这块空间。理论上来说，这是最高效的模型了。

async fn root_future(){
    let fut_one = /* ... */;
    let fut_two = /* ... */;
    async move {
        fut_one.await;
        fut_two.await;
    }.await
}

// The `Future` type generated by our `async { ... }` block
struct AsyncFuture {
    fut_one: FutOne,
    fut_two: FutTwo,
    state: AsyncState,
}

// List of states our `async` block can be in
enum AsyncState {
    AwaitingFutOne,
    AwaitingFutTwo,
    Done,
}

impl Future for AsyncFuture {
    type Output = ();

    fn poll(mut self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<()> {
        loop {
            match self.state {
                AsyncState::AwaitingFutOne => match self.fut_one.poll(..) {
                    Poll::Ready(()) => self.state = AsyncState::AwaitingFutTwo,
                    Poll::Pending => return Poll::Pending,
                }
                AsyncState::AwaitingFutTwo => match self.fut_two.poll(..) {
                    Poll::Ready(()) => self.state = AsyncState::Done,
                    Poll::Pending => return Poll::Pending,
                }
                AsyncState::Done => return Poll::Ready(()),
            }
        }
    }
}

之前提到了 Leaf-Future 和 Non-leaf-Future，大家可能有一点困惑，为什么要这样命名？

如果将 future 看成是一个树状结构，答案就很明了了。一个 future 内部会包含多个 child future，每一个 child future 可能也有自己的 child …，直到最后的 left future，不会再有其叶子结点了。

poll 一个 future，其实就是在遍历这颗 future 树，交给 executor 执行的其实是整个 future 树，而编译器早就根据 async/await 帮我们构造好了树的遍历路径（状态匹配），但是涉及到底层 Io 的时候，一定是交给程序员完成的。