blk-mq: introduce Kyber multiqueue I/O scheduler
authorOmar Sandoval <osandov@fb.com>
Fri, 14 Apr 2017 08:00:02 +0000 (01:00 -0700)
committerJens Axboe <axboe@fb.com>
Fri, 14 Apr 2017 20:06:58 +0000 (14:06 -0600)
commit00e043936e9a1c274c29366c7ecd9e17c79418e6
tree600ca18eb94cb522b65f01381ec20c9565508c02
parentc05f8525f67b7d6489b0502211d4ed35622d9beb
blk-mq: introduce Kyber multiqueue I/O scheduler

The Kyber I/O scheduler is an I/O scheduler for fast devices designed to
scale to multiple queues. Users configure only two knobs, the target
read and synchronous write latencies, and the scheduler tunes itself to
achieve that latency goal.

The implementation is based on "tokens", built on top of the scalable
bitmap library. Tokens serve as a mechanism for limiting requests. There
are two tiers of tokens: queueing tokens and dispatch tokens.

A queueing token is required to allocate a request. In fact, these
tokens are actually the blk-mq internal scheduler tags, but the
scheduler manages the allocation directly in order to implement its
policy.

Dispatch tokens are device-wide and split up into two scheduling
domains: reads vs. writes. Each hardware queue dispatches batches
round-robin between the scheduling domains as long as tokens are
available for that domain.

These tokens can be used as the mechanism to enable various policies.
The policy Kyber uses is inspired by active queue management techniques
for network routing, similar to blk-wbt. The scheduler monitors
latencies and scales the number of dispatch tokens accordingly. Queueing
tokens are used to prevent starvation of synchronous requests by
asynchronous requests.

Various extensions are possible, including better heuristics and ionice
support. The new scheduler isn't set as the default yet.

Signed-off-by: Omar Sandoval <osandov@fb.com>
Signed-off-by: Jens Axboe <axboe@fb.com>
Documentation/block/kyber-iosched.txt [new file with mode: 0644]
block/Kconfig.iosched
block/Makefile
block/kyber-iosched.c [new file with mode: 0644]