COP 706: YATP Read Pool

TiKV schedules the work of a cop request as a Rust Future task in the unified read pool. The unified read pool is a shared execution pool for cop and direct storage reads: it queues tasks and runs them on a limited set of workers.

An executor runs a Future in small turns. TiKV's unified read pool uses YATP as its executor.

Polling a Future

A Rust Future represents an operation whose result might not be available yet. It starts working when its executor first calls poll().

Each later call to poll() advances the Future. One poll has two possible results:

#![allow(unused)]
fn main() {
enum Poll<T> {
    Ready(T),
    Pending,
}
}

Ready means the task has finished. Pending means it is still waiting for an asynchronous event.

The Future keeps the operation's current progress, so it can wait and later continue from that point. For example, it might be waiting for a clock timeout or an I/O operation to complete.

While the Future is pending, the executor can run another ready task.

While a Future is Pending, polling it again before its event arrives would make no progress. Each poll() call passes it a waker, which the operation being awaited keeps. When the event occurs, it calls the waker to notify the executor that the task is ready for another poll. The executor is therefore driven by events rather than repeatedly checking waiting tasks.

Threads, Workers, and Tasks

YATP creates a limited set of long-lived worker threads to execute ready Futures. Each worker repeatedly takes a task from a queue and calls poll():

ready Future
    |
    v
YATP queue
    |
    +----> worker thread 1 -> poll()
    +----> worker thread 2 -> poll()
    +----> worker thread 3 -> poll()

The pool may contain thousands of tasks while using only a small number of worker threads.

The Task State Machine

Ready and Pending are the results of one poll() call. Separately, YATP records a small scheduling state for each Future task. That state tells YATP whether the task is queued, currently being polled, waiting for an event, or finished.

The two layers meet at the end of a poll. Ready changes a POLLING task to COMPLETED. Pending normally changes it to IDLE. A new task starts as NOTIFIED; when an event fires, its waker changes an IDLE task back to NOTIFIED so YATP can poll it again.

NOTIFIED does not mean the Future returned Ready. It only means the task is ready to be polled; Ready means the Future has finished.

new task
   |
   v
NOTIFIED -- worker polls --> POLLING -- Ready --> COMPLETED
   ^                          |
   |                        Pending
   |                          v
   +---------- wake -------- IDLE

If the waker fires while a worker is still polling, YATP records the task as NOTIFIED rather than losing that event. When the current poll returns Pending, YATP sees the notification and arranges another poll, either immediately or through its queue.

Cooperative Scheduling

The operating system can preempt a YATP worker thread, but YATP cannot interrupt a Future in the middle of a poll() call. A Future returns control only by finishing with Ready, waiting with Pending, or reaching an explicit asynchronous yield point.

An .await yields only when the awaited Future returns Pending. Synchronous work does not yield automatically. A RocksDB iterator call, a blocking file operation, or a long CPU loop keeps the worker occupied until that code returns.

short poll
  task A ---- Pending ----> worker runs task B

long synchronous poll
  task A ------------------------------> returns
              task B waits

This is cooperative scheduling: many waiting tasks can share a small number of threads, but a long poll can delay unrelated ready tasks.

Choosing the Next Task

YATP supports several queueing strategies that differ in how workers choose ready tasks.

Single-Level Queue

A single-level pool treats ready tasks alike. A task submitted from outside the pool first enters a shared queue. When a worker needs work, it takes a batch into its own local queue and runs that queue first.

An idle worker can take more tasks from the shared queue or steal a batch from another worker's local queue. This work stealing lets an idle worker help process another worker's backlog.

Multi-Level Queue

A multi-level pool has three queues. Level 0 is for work that has used little worker time and receives most scheduling opportunities. Levels 1 and 2 receive progressively fewer opportunities, so they carry longer-running work without making it compete equally with short work.

By default, YATP aims to spend 80% of worker time on level 0. The lower levels still receive a share. Levels do not give tasks different time slices: they affect which ready task a worker chooses next, while every Future still runs until it returns from poll().

For ordinary tasks, YATP assigns a level when the task enters a queue. It uses execution time accumulated for the same task identifier, not time spent waiting in a queue:

under 5 ms         -> level 0
5 ms to under 100  -> level 1
100 ms or more     -> level 2

A first task with an identifier starts at level 0. When completed work with that identifier pushes its accumulated execution time across a threshold, later tasks with the same identifier enter the appropriate lower level. Returning Pending alone does not change a Future's level. A task with an explicit priority stays at its assigned level instead. TiKV places high-priority tasks in level 0 and low-priority or background tasks in level 2.

This gives a workload that has already consumed substantial worker time fewer scheduling opportunities, leaving more for short reads. The tradeoff is higher queue delay for its later tasks under sustained short work, although YATP still schedules the lower levels. A long poll() can still occupy a worker regardless of its level.

Priority Queue

A priority pool places ready tasks in one global priority order. Workers choose the highest-priority task available. When TiKV resource control is enabled, it assigns priorities to configured workload groups, and YATP uses those priorities when choosing tasks.

In current TiKV, the unified read pool uses the priority queue when resource control is enabled. Without resource control, it uses the multi-level queue. The single-level queue remains YATP's basic work-stealing option.

YATP separates two decisions in TiKV's read pool. A Future decides when its work can make progress or must wait; the queue decides which ready task receives a worker next. This lets many reads share a bounded worker pool while YATP controls how ready work competes under load.

COP 707 applies this model to cop tasks: where scanning yields, how one task spans multiple polls, and how waiting and execution appear in TiKV's performance signals.