PolarDB:WAL parallel replay

Parallelizing WAL replay

A single WAL record may modify multiple data blocks. Define the smallest replay unit, a replay subtask, as Task(i,j) = LSN(i) → Block(i,j), which means replaying the *i*-th WAL record on data block Block(i,j).

A WAL record that modifies m blocks produces m replay subtasks. Across multiple WAL records, not every subtask depends on the result of the preceding one—subtasks that touch different data blocks are independent and can run in parallel.

For example, given three WAL records with the following subtask sets:

• Task[0,*] = [Task[0,0], Task[0,1], Task[0,2]]

• Task[1,*] = [Task[1,0], Task[1,1]]

• Task[2,*] = [Task[2,0]]

If Block[0,0] = Block[1,0], Block[0,1] = Block[1,1], and Block[0,2] = Block[2,0], then three groups can execute in parallel: [Task[0,0], Task[1,0]], [Task[0,1], Task[1,1]], and [Task[0,2], Task[2,0]].

PolarDB exploits this independence in its parallel task execution framework, applied directly to the WAL replay path.

Key concepts

Parallel task execution framework

Shared memory is divided equally based on the number of concurrent processes. Each segment acts as a circular queue assigned to one process. The depth of each queue is configurable.

The framework has two roles:

• Dispatcher process: Dispatches tasks to specific processes and removes completed tasks from queues.

• Process group: Each process retrieves a task from its circular queue and executes it based on the task's state.

Task states

Each Task Node in a circular queue has one of five states:

State	Description
Idle	The Task Node has no assigned task.
Running	The Task Node is assigned a task and is waiting or executing.
Hold	The task depends on a preceding task and must wait for it to finish.
Finished	All processes in the process group have completed the task.
Removed	The Dispatcher has confirmed that the task and all its prerequisites are Finished, and has deleted them from the management struct. This ensures dependent task results are processed in the correct order.

In the state machine above, transitions along black lines are performed by the Dispatcher process; transitions along orange lines are performed by the parallel replay process group.

Dispatcher process: task scheduling and dependency management

The Dispatcher uses three data structures:

• Task HashMap: Records the hash mapping between Task Tags and their corresponding task execution lists. Each task has a Task Tag; tasks that share a dependency share the same Task Tag.

• Task Running Queue: Records tasks currently being executed.

• Task Idle Nodes: Records Task Nodes in the Idle state for each process in the process group.

The Dispatcher applies two scheduling policies:

1. Affinity scheduling: If a task with the same Task Tag is already running, assign the new task to the process handling the last task in that Tag's linked list. This keeps dependent tasks on the same process, reducing inter-process synchronization overhead.

2. Round-robin fallback: If the preferred process's queue is full, or no task with the same Task Tag is running, select the next process in the group and assign an Idle Task Node from its queue. This distributes tasks evenly across all processes.

Process group: parallel execution and retry

During process group initialization, SchedContext is configured with three function pointers:

Function	Purpose
TaskStartup	Runs initialization before a process begins executing tasks.
TaskHandler	Executes a specific task based on the incoming Task Node.
TaskCleanup	Runs cleanup before a process exits.

Each process retrieves a Task Node from its circular queue:

• If the state is Hold, the process inserts the node at the tail of the Hold List.

• If the state is Running, the process calls TaskHandler. If TaskHandler fails, the system sets a retry count of 3 for the Task Node and inserts it at the head of the Hold List.

The process then searches the Hold List from the beginning for an executable task:

• If a task's state is Running and its wait count is 0, the process executes it.

• If the wait count is greater than 0, the process decrements it by 1 and moves on.

WAL parallel replay workflow

LogIndex data records the mapping between WAL records and the data blocks they modify, and supports retrieval by log sequence number (LSN). During continuous WAL replay on a standby node, PolarDB uses the parallel execution framework to distribute replay tasks across multiple processes.

The four processes involved and their roles:

The Dispatcher enumerates PageTags and their corresponding LSNs in LogIndex insertion order to build {LSN → PageTag} Task Nodes, then dispatches them to the process group.