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 801: Region Merge

RAFTSTORE 604 showed how one Region splits into two. A Region merge goes in the opposite direction: it combines two adjacent Regions so that TiKV does not keep many small Raft groups.

Suppose two Regions cover adjacent key ranges:

source Region: [a, m)
target Region: [m, z)

After the merge, the source Region disappears. The target Region remains and expands its range:

target Region: [a, z)

This looks like a simple metadata change, but source and target are two independent Raft groups. Each has its own leader, log, and apply progress. TiKV cannot place one entry in both logs atomically.

TiKV coordinates the merge through two Raft commands:

source Raft group: PrepareMerge
target Raft group: CommitMerge

The merge proceeds in five steps:

  • Align the replicas. PD puts a source peer and a target peer on the same stores.
  • Prepare and freeze the source. PrepareMerge fixes the handoff boundary and stops ordinary writes.
  • Commit in the target. The target Raft group commits CommitMerge.
  • Catch up the local source peer. Each store applies any source history it still needs before completing the merge.
  • Change ownership. The target expands to the combined range and the source is removed.

Align the Replicas

A Region is considered small based on both its size and key count. The current default thresholds are 54 MiB and approximately 540,000 keys.

Before PD initiates a merge, it ensures that the Regions are adjacent and that their peers are placed on the same TiKV stores.

For example, their placement may initially differ:

source peers: Store 2, Store 3, Store 4
target peers: Store 1, Store 2, Store 3

PD first moves the source peer on Store 4 to Store 1 using the replica-movement process from RAFT 602: Replica Movement. The resulting placement is aligned:

Store 1: source peer | target peer
Store 2: source peer | target peer
Store 3: source peer | target peer

This preliminary alignment may move data. Once it is complete, the merge itself needs no cross-store copy of the source key-value data. Every store already holds both adjacent ranges.

Prepare the Source

PD sends the merge request to the source Region's leader. Before it proposes the merge, the leader confirms that the target is still valid and checks how far each source follower has replicated. TiKV retries later if a source peer is too far behind or the history it would need to keep would be too large.

For each follower, Raft tracks a matched index: the highest source-log index known to be replicated on that peer.

source leader's last index: 120

peer on Store 1 matched:    120
peer on Store 2 matched:    118
peer on Store 3 matched:    116

minimum matched index:      116

The target peer will eventually take over the source range on each store. Before that can happen, the local source peer must catch up to the source leader's committed history; otherwise, the store would be missing source writes.

In the example above, index 116 is known to exist on every source peer.

The source leader then proposes PrepareMerge. The entry identifies the target Region and records 117 as the first source-log index that TiKV must not truncate during the merge. Suppose the PrepareMerge entry itself receives index 121:

all source peers have: [ ... 116]
keep for later:        [117 ... 121 (PrepareMerge)]

After proposing PrepareMerge, the source leader stops accepting ordinary writes. User writes can no longer extend the source history being handed to the target.

After a source peer applies PrepareMerge, TiKV stops compacting that peer's Raft log. The source leader can later read the needed entries from this interval for CommitMerge.

Commit the Target

After a source peer applies PrepareMerge, it asks the target peer on the same store to commit the merge. The request carries the source Region metadata and the source log entries read from that kept interval.

Only the target leader can turn this request into a CommitMerge proposal. The resulting entry is replicated and committed in the target Raft group like any other Raft command.

source peer on target leader's store
              |
              | source metadata and log entries
              v
        target leader
              |
              | propose CommitMerge
              v
       target Raft group

Once the target group commits CommitMerge, the merge cannot be rolled back. The target replicas must now complete it on their own stores.

Catch Up Each Source Peer

A target replica may apply CommitMerge before the source peer on the same store has applied PrepareMerge. Some committed source entries may therefore be missing from that store's KV state. The target cannot take over the source range until those entries have been applied.

PrepareMerge has already stopped source writes, so the catch-up endpoint is fixed. CommitMerge carries the needed source log entries, so the target can complete this local catch-up without waiting for the source leader.

The target therefore pauses its CommitMerge application and gives the carried log entries to its local source peer:

target starts applying CommitMerge
                |
                v
has the local source applied PrepareMerge?
                |
        +-------+-------+
        |               |
       yes              no
        |               |
        |        apply the missing source logs
        |               |
        +-------+-------+
                |
                v
stop the source apply path
                |
                v
resume CommitMerge

If the source peer has already applied PrepareMerge, every earlier source entry has also been applied, so no log replay is needed. Otherwise, it applies the missing entries in source-log order until it reaches PrepareMerge.

Only then can the local target finish the merge. TiKV persists two Region metadata changes together:

  • The target becomes responsible for the combined range.
  • The source is marked as removed.

The source peer can then be destroyed.

Rolling Back

The source may be unable to finish the merge. For example, the target may split or change its peer configuration after PD selects it, so its Region epoch no longer matches the target recorded by PrepareMerge. A network partition may also leave the target group unable to commit. As long as the target Raft group has not committed CommitMerge, the source group can commit RollbackMerge and resume normal writes.

After CommitMerge is committed, rollback is no longer possible. Even if a TiKV process crashes at that point, recovery must continue the target range update and source removal.

This chapter establishes the normal merge path. RAFTSTORE 901: Peer Lifecycle and Crash Recovery will examine how durable peer states, snapshots, and crash recovery preserve the same result when these steps are interrupted.