Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

RAFTSTORE 701: Batch System

RAFTSTORE 501 introduced the Raft batch system and the apply batch system. Both use batching: they combine independent work from many Region peers into fewer, larger I/O operations.

This chapter explains how TiKV schedules that work safely. Each Region still processes its events in order, while the batch systems collect work from many independent Regions and perform it together.

Routing Events to a Region

Every Region peer has a peer FSM, the state machine that drives its raft-rs instance. A store can host many peers, so an event first needs to find the right one.

The Router is an address book from a Region ID to its mailbox. A mailbox has two parts:

  • a queue of pending messages for one FSM;
  • the FSM itself when no worker is currently handling it.

When an incoming Raft message, local proposal, apply result, or timer event arrives, the Router finds the mailbox for its Region. The mailbox first puts the event into its per-Region event queue. If the FSM is idle, the mailbox sends the FSM to a shared scheduler queue.

A poller is a worker thread in the batch system. It receives scheduled FSMs from that channel and handles their pending events.

There are two layers of batching before a poller runs:

  • A mailbox collects many events for one Region.
  • When an idle mailbox receives an event, its FSM becomes runnable and is sent to the shared scheduler queue.
events for Region 1                 events for Region 2
 Raft msg                           Raft msg
 proposal                           timer
     \   /                              \   /
      \ /                                \ /
       v                                  v
+---------------------+             +---------------------+
| mailbox: Region 1   |             | mailbox: Region 2   |
| per-Region event    |             | per-Region event    |
| queue               |             | queue               |
+----------+----------+             +----------+----------+
           | one runnable FSM                  | one runnable FSM
           +------------------+----------------+
                              v
                 shared scheduler queue of FSMs
                              |
                    +---------+---------+
                    v                   v
                 poller 1            poller 2

While a poller processes a Region's FSM, new events simply wait in its mailbox queue. This guarantees that two pollers do not process the same Region peer at the same time, so the peer's Raft state remains ordered.

Pollers Process Batches

Each batch system has several pollers. A poller takes scheduled FSMs from the shared scheduler queue and lets the appropriate Raftstore handler process their pending events.

One pass over a group of FSMs is a batch round. In a typical round, a poller processes at most 256 FSMs. This batch-size limit is configurable; 256 is the default.

scheduled FSMs
      |
      v
poller
      |
      +--> Region 1 FSM
      +--> Region 2 FSM
      +--> Region 3 FSM
      |
      v
handler processes one round of work for each FSM

At the beginning of every new round, a poller takes in at least one newly scheduled FSM, even if its existing batch has reached the configured limit. This prevents a fixed group of hot Regions from starving other Regions.

A hot FSM can remain in a poller's batch across several rounds. To keep other Regions from waiting forever, the batch system uses rescheduling: once FSMs have stayed in a batch longer than the reschedule threshold, five seconds by default, it reschedules roughly half of them. Later rounds can then mix in other work.

This scheduling mechanism is shared by the Raft and apply paths. What their handlers do is different.

The Raft Batch System

The Raft batch system handles peer FSMs. For one peer, its normal handler takes at most 4,096 events from the mailbox in one turn, then feeds them into the peer's Raft event loop.

The bound prevents one peer with a large queue from keeping a poller forever. The events include incoming Raft messages, local proposals, apply results, and timer-driven work.

As described in RAFTSTORE 402, an incoming Raft message enters raft-rs through its step() API. A local proposal uses the proposal API instead, while timer events can advance the peer's Raft state. These operations may produce a Ready containing Raft log entries to persist, outgoing Raft messages, and committed entries to apply.

The important batching boundary appears after several peers have been processed:

Region 1 Ready ---\
Region 2 Ready ----> batch Raft Engine writes and outgoing messages
Region 3 Ready ---/
                         |
                         v
                    committed entries
                         |
                         v
                 send to the apply batch system

Each peer still has its own Raft log and ordering. Raftstore batches only the physical work that is independent across peers.

The Apply Batch System

Committed entries move from the Raft batch system to one ApplyFsm per Region. An ApplyFsm interprets its Region's committed entries in log order and produces changes for the KV Engine, such as writing a key, deleting a key, or advancing the apply index.

The apply batch system uses the same general model:

committed entries for many Regions
              |
              v
     ApplyFsms add changes
     to one shared WriteBatch
              |
              v
       write to RocksDB

An apply poller keeps one WriteBatch shared by the ApplyFsms it is processing. It adds each Region's RocksDB changes to that batch. When the batch reaches its internal capacity limit, TiKV writes the accumulated changes to RocksDB. It also writes the pending batch before certain operations that require up-to-date state.

This differs from the Raft batch system, which creates one batched Raft Engine write I/O task per round. An apply poller can write to RocksDB multiple times in one turn.

Yielding

After each of these persistence points, TiKV checks the Region it is currently processing. If that Region has contributed at least 32 KiB of writes in its turn, or its turn has lasted 500 ms, its ApplyFsm yields. TiKV saves the current unprocessed entry and the entries after it, then resumes them in a later turn.

If neither limit has been reached, the Region keeps applying entries and can contribute to another shared WriteBatch in the same turn. Yielding prevents a hot Region with a large backlog from monopolizing an apply poller. The tradeoff is that its backlog takes longer to drain because it may need several turns.

With this picture in mind, Raftstore is no longer just a collection of independent event loops. TiKV keeps each Region ordered while making the whole store efficient. Later chapters build on this picture through slow-score probes, Region-worker tasks, and peer-lifecycle details.