[GH-ISSUE #4837] [RFC]: [Store] HA: Protect in-flight PutStart allocations across failover with a segment-owner ledger #1232

Open
opened 2026-10-29 21:24:13 +00:00 by bsakaguchi · 1 comment
Owner

Originally created by @SongOf on GitHub (Oct 21, 2026).
Original GitHub issue: https://github.com/kvcache-ai/Mooncake/issues/4837

Changes proposed

Summary

In HA mode, memory allocations (PutStart, UpsertStart, CopyStart, MoveStart, PromotionAllocStart and their variants) are not written to the OpLog. After a failover, the promoted leader therefore cannot see ranges that are still being written. It may give such a range to another key, or serve an object as COMPLETE while an in-place upsert is still overwriting it. Either way a reader can get wrong bytes, with no error.

The HA roadmap (#3808, RL02, from RFC #2979) fixes this by making REPLICA_CREATE durable before PutStart returns. That adds at least one etcd commit to every write.

This RFC proposes a lighter protection for memory replicas, with no quorum write on the write path. The process that owns a segment keeps a small ledger of the ranges being written in it, fenced by the leader's term. At failover, the promoted leader learns those ranges from the owners and keeps them reserved.

It is a proposal for review. Nothing here is implemented.

Motivation

  • Unlogged ranges look free after failover. The promoted leader rebuilds its index from the snapshot and the durable OpLog, which do not include ranges handed out but not yet completed.
  • In-place upserts are not logged. When the size is unchanged, UpsertStart rewrites the existing buffers in place. A promoted leader still sees the old object as COMPLETE.
  • Writers can be arbitrarily late. #4491 shows timed-out slices landing long after a put was revoked. A fix that waits for writers to finish cannot rely on a time bound.
  • RL02 puts etcd latency on every write. Its tail latency follows etcd.

Goals and non-goals

Goals:

  • After a failover, no reader gets wrong bytes from a memory replica because a range was reused while still being written, or because an object was served while being overwritten in place.
  • No etcd commit, or other quorum write, on the write path.
  • No reliance on how long a writer can take.
  • Safe rolling upgrades in any order, and no behavior change until the mode is raised to takeover or enforce.

Non-goals:

  • Losing a recent PUT_END on failover. Per #3885, that is part of the cache contract.
  • Readers that hold descriptors from a former leader.
  • Non-HA masters, and NoF, DFS and CXL replicas (see "Scope").

Proposal

Overview

  1. Ledger on the segment owner. Each client that mounts a memory segment keeps an in-process ledger of the ranges that may still be written in it. A segment's memory and its RDMA registration live and die with that process, so no quorum store is needed.

  2. Register before writing. A writer registers each range with the segment's owner before its first transfer to it, under the term of the leader that allocated the range. The owner returns a unique ledger token for that write attempt. The writer writes only after the registration is acknowledged.

  3. Fencing by term. A term is the pair (view_version, leader session token). The owner accepts registrations only under its current term.

  4. Takeover on mount and remount. When the owner mounts or remounts a segment, it moves to the current leader's term and reports its entries before the remount. From then on it rejects registrations under any other term. The leader accepts a report only under its own term, and applies it before the segment can be allocated from.

  5. Reconciliation. For each reported entry, the leader does one of three things:

    • if the entry is the same allocation as a restored replica that is already complete, it keeps that replica;
    • if the entry overlaps any other restored replica, it hides that replica and later removes it, never serving it again (this covers in-place upserts);
    • if the entry overlaps nothing it restored, it reserves the range.
  6. Completion identity. Completion RPCs (PutEnd, PutRevoke and the others) carry the term of their allocation. A leader rejects completions from another term, so a write that started before a failover cannot complete or free a write started after it.

  7. Safe clearing. A writer clears its entry by token, and only after both of these:

    • its completion RPC has returned;
    • its transfers have fully drained.

    The owner tells the leader when reported entries are cleared, so the leader can release them.

Why this is safe

Within the scope below, every writer of a segment registers. The owner processes a registration and a takeover in some order. If the registration comes first, the takeover reports it, and the new leader protects the range. If the takeover comes first, the registration carries an older term and is rejected, so the writer never writes. A stale leader that keeps allocating is fenced the same way.

The argument rests on six rules, none of which involves a timeout or a clock:

  1. No two leaders share a term, and the owner never moves to an older term.
  2. A writer writes a range only after its registration is acknowledged.
  3. A leader allocates on a segment only after applying that segment's report, made under its own term.
  4. A leader accepts a completion only if it was issued under its own term.
  5. An entry is removed only by its own token.
  6. An entry is cleared only after its completion has returned and its transfers have drained.

Terms are safe on all three HA backends (etcd, Redis, k8s), because session tokens are unique per leadership. If a backend's view_version ever goes backwards, the affected segments stop accepting remounts until an operator intervenes. That loses capacity, not data.

Scope

  • Covered: memory replicas (host, GPU and EGM memory) on segments whose owner and leader run ledger-enabled builds, with the mode at enforce. The guarantee is per segment, because an unregistered writer could corrupt a registered one. So in enforce the leader refuses memory allocations to clients that have not declared ledger support.
  • Not covered:
    • NoF: it has no long-lived owner process, and NoF failover has a separate open issue (#3826).
    • DFS: HA promotion with DFS is not supported today; #3819 covers its allocator.
    • CXL: not analyzed.
    • Allocations outside the covered scope get no guarantee. In off and shadow they behave exactly as today.
  • Known limitations, not blocking:
    • A remount to the same leader relies on today's offboarding wait for in-progress replicas.
    • Reserved ranges hold capacity until their entries clear.
    • Orphaned entries are released only when their writer is known to be gone; a timeout release is opt-in.

Compatibility

  • Wire: a few struct_pack::compatible fields: the issuing term in ObjectMeta, the session token and the cluster's ledger mode in PingResponse, and the ledger address in Segment. Also a few new RPCs: registration, clear, ledger report, address lookup, a capability declaration (also used to acknowledge mode changes), and term-carrying variants of the non-struct completion RPCs. Old peers fall back to today's behavior. No allocation RPC signature changes.
  • Persistent formats: none change. Ledger entries live in owner memory, and reservations exist only in the leader's runtime state.
  • Mixed versions: in off and shadow, any mix behaves as today. takeover needs ledger-enabled masters and owners, and enforce also needs every client upgraded.

Performance

  • Write path: one intra-datacenter round trip to the segment owner before the first byte. It is a local call when the writer owns the segment, and one round trip per batch for batch APIs.
  • Clears: asynchronous and batched, off the latency path.
  • Master: no added steady-state cost.
  • Failover: one report per segment before its remount.
  • Measurement: the shadow mode measures the cost on real workloads before enforcement is proposed. If the cost is not acceptable, the feature stays off, and RL02 remains the alternative.

Alternatives considered

RL02: durable REPLICA_CREATE Quarantine free space after failover Owner ledger (this RFC)
Write-path cost At least one etcd commit None One intra-DC round trip
Relies on a writer time bound No Yes; #4491 shows none exists No
Capacity loss at failover None All free space, for a while Only ranges still being written
Media covered All master-allocated media All Memory replicas

The ledger and RL02 can coexist, for example the ledger for memory and RL02 for NoF.

Implementation plan

The work is split into small PRs. One setting, allocation_ledger_mode, gates it, with four levels:

  • off: the default; no ledger work at all;
  • shadow: register and report, but only count failures and mismatches;
  • takeover: also reconcile reported entries after a failover;
  • enforce: also reject unregistered writes and refuse allocations to undeclared clients.

The mode is set on the masters. The leader advertises it in PingResponse, and clients follow it, so a single setting switches the whole cluster. Clients learn of a change only at their next ping. So a raise takes effect only after every connected client has acknowledged the new mode, or has left. Clients acknowledge by resending their capability declaration. This way a client never acts on a lower mode than the leader. A client that reconnects pings before it allocates, so it starts with the current mode. A lowering takes effect at once.

I plan to implement it once the direction is agreed.

Phase PRs Result Behavior change
1. Plumbing 1. Leader session token and ledger mode in PingResponse; client term tracking; capability declaration and mode acknowledgement
2. Completion identity: issuing term on completion RPCs
3. Ledger RPC service on segment providers; ledger address lookup
Terms and identities flow end to end None; counts only, in shadow
2. Shadow mode 4. Owner-side ledger: register, token, clear, local takeover
5. Writer-side registration in TransferSubmitter's write entry points, covering every write path
Ledger populated on real traffic None; counts only, in shadow
3. Takeover 6. Report on mount and remount, applied inside the remount's critical section
7. Reconciliation: reserve, hide and remove, release on clear
A promoted leader protects in-flight ranges In takeover
4. Enforcement 8. Reject unregistered writes; refuse allocations to undeclared clients
9. Reclaim orphaned entries
Guarantee in effect In enforce
5. Validation 10. Fault-injection tests, including real etcd HA failover
11. Benchmarks against no ledger and an RL02-style prototype
12. Documentation and an operations guide
Evidence for enabling by default None

Dependencies:

  • Clearing on the revoke and timeout path relies on the drain work in #4780 and #4491.
  • The takeover builds on the remount path being changed by #4802 and #3666.
  • Rule 3 must survive the master lock rework in #4700 and #4801.

Rollout process

  1. Land the PRs phase by phase, with the default mode off. Nothing changes.
  2. Upgrade all clients and masters, in any order, then switch to shadow. Watch registration latency and failures, owner load, live entry counts, and completion-term mismatches.
  3. Switch a staging HA cluster to takeover. Run the fault-injection suite and real failovers. Verify that no protected range is reused, and that hidden replicas are removed rather than served.
  4. Move production clusters to takeover, then to enforce, one cluster at a time. A cluster moves to enforce only after every client in it has declared ledger support.
  5. Consider a non-off default once maintainers accept the benchmark results and the staging evidence.

Rollback: lowering the mode, down to off, takes effect immediately and returns the cluster to today's protection. No persistent state needs migration, because ledger entries and reservations live only in memory.

Open questions

  1. Is one client-to-client round trip on the write path acceptable, compared with RL02's etcd commit?
  2. Should this replace RL02 for memory replicas, or ship as a mode next to it?
  3. Should the completion term travel in term-carrying RPC variants or in an RPC attachment (#3848)?
  4. Is failing a put that straddles a failover cleanly enough, or should a follow-up complete it on the new leader?

Issues and PRs: #2979, #3808, #4491, #3885, #3030, #2953, #3819, #3826, #4780, #4802, #3666, #4700, #4801, #3848.

AI assistance disclosure

The analysis and this text were prepared with an AI coding assistant (Claude Code), which read the code on main at 042ab8a1. The submitter directed and reviewed it.

Before submitting a new issue...

  • Make sure you already searched for relevant issues and read the documentation
Originally created by @SongOf on GitHub (Oct 21, 2026). Original GitHub issue: https://github.com/kvcache-ai/Mooncake/issues/4837 ### Changes proposed ## Summary In HA mode, memory allocations (`PutStart`, `UpsertStart`, `CopyStart`, `MoveStart`, `PromotionAllocStart` and their variants) are not written to the OpLog. After a failover, the promoted leader therefore cannot see ranges that are still being written. It may give such a range to another key, or serve an object as `COMPLETE` while an in-place upsert is still overwriting it. Either way a reader can get wrong bytes, with no error. The HA roadmap (#3808, RL02, from RFC #2979) fixes this by making `REPLICA_CREATE` durable before `PutStart` returns. That adds at least one etcd commit to every write. This RFC proposes a lighter protection for memory replicas, with no quorum write on the write path. The process that owns a segment keeps a small **ledger** of the ranges being written in it, fenced by the leader's term. At failover, the promoted leader learns those ranges from the owners and keeps them reserved. It is a proposal for review. Nothing here is implemented. ## Motivation - **Unlogged ranges look free after failover.** The promoted leader rebuilds its index from the snapshot and the durable OpLog, which do not include ranges handed out but not yet completed. - **In-place upserts are not logged.** When the size is unchanged, `UpsertStart` rewrites the existing buffers in place. A promoted leader still sees the old object as `COMPLETE`. - **Writers can be arbitrarily late.** #4491 shows timed-out slices landing long after a put was revoked. A fix that waits for writers to finish cannot rely on a time bound. - **RL02 puts etcd latency on every write.** Its tail latency follows etcd. ## Goals and non-goals Goals: - After a failover, no reader gets wrong bytes from a memory replica because a range was reused while still being written, or because an object was served while being overwritten in place. - No etcd commit, or other quorum write, on the write path. - No reliance on how long a writer can take. - Safe rolling upgrades in any order, and no behavior change until the mode is raised to `takeover` or `enforce`. Non-goals: - Losing a recent `PUT_END` on failover. Per #3885, that is part of the cache contract. - Readers that hold descriptors from a former leader. - Non-HA masters, and NoF, DFS and CXL replicas (see "Scope"). ## Proposal ### Overview 1. **Ledger on the segment owner.** Each client that mounts a memory segment keeps an in-process ledger of the ranges that may still be written in it. A segment's memory and its RDMA registration live and die with that process, so no quorum store is needed. 2. **Register before writing.** A writer registers each range with the segment's owner before its first transfer to it, under the term of the leader that allocated the range. The owner returns a unique ledger token for that write attempt. The writer writes only after the registration is acknowledged. 3. **Fencing by term.** A term is the pair (`view_version`, leader session token). The owner accepts registrations only under its current term. 4. **Takeover on mount and remount.** When the owner mounts or remounts a segment, it moves to the current leader's term and reports its entries before the remount. From then on it rejects registrations under any other term. The leader accepts a report only under its own term, and applies it before the segment can be allocated from. 5. **Reconciliation.** For each reported entry, the leader does one of three things: - if the entry is the same allocation as a restored replica that is already complete, it keeps that replica; - if the entry overlaps any other restored replica, it hides that replica and later removes it, never serving it again (this covers in-place upserts); - if the entry overlaps nothing it restored, it reserves the range. 6. **Completion identity.** Completion RPCs (`PutEnd`, `PutRevoke` and the others) carry the term of their allocation. A leader rejects completions from another term, so a write that started before a failover cannot complete or free a write started after it. 7. **Safe clearing.** A writer clears its entry by token, and only after both of these: - its completion RPC has returned; - its transfers have fully drained. The owner tells the leader when reported entries are cleared, so the leader can release them. ### Why this is safe Within the scope below, every writer of a segment registers. The owner processes a registration and a takeover in some order. If the registration comes first, the takeover reports it, and the new leader protects the range. If the takeover comes first, the registration carries an older term and is rejected, so the writer never writes. A stale leader that keeps allocating is fenced the same way. The argument rests on six rules, none of which involves a timeout or a clock: 1. No two leaders share a term, and the owner never moves to an older term. 2. A writer writes a range only after its registration is acknowledged. 3. A leader allocates on a segment only after applying that segment's report, made under its own term. 4. A leader accepts a completion only if it was issued under its own term. 5. An entry is removed only by its own token. 6. An entry is cleared only after its completion has returned and its transfers have drained. Terms are safe on all three HA backends (etcd, Redis, k8s), because session tokens are unique per leadership. If a backend's `view_version` ever goes backwards, the affected segments stop accepting remounts until an operator intervenes. That loses capacity, not data. ### Scope - **Covered:** memory replicas (host, GPU and EGM memory) on segments whose owner and leader run ledger-enabled builds, with the mode at `enforce`. The guarantee is per segment, because an unregistered writer could corrupt a registered one. So in `enforce` the leader refuses memory allocations to clients that have not declared ledger support. - **Not covered:** - **NoF:** it has no long-lived owner process, and NoF failover has a separate open issue (#3826). - **DFS:** HA promotion with DFS is not supported today; #3819 covers its allocator. - **CXL:** not analyzed. - Allocations outside the covered scope get no guarantee. In `off` and `shadow` they behave exactly as today. - **Known limitations, not blocking:** - A remount to the same leader relies on today's offboarding wait for in-progress replicas. - Reserved ranges hold capacity until their entries clear. - Orphaned entries are released only when their writer is known to be gone; a timeout release is opt-in. ### Compatibility - **Wire:** a few `struct_pack::compatible` fields: the issuing term in `ObjectMeta`, the session token and the cluster's ledger mode in `PingResponse`, and the ledger address in `Segment`. Also a few new RPCs: registration, clear, ledger report, address lookup, a capability declaration (also used to acknowledge mode changes), and term-carrying variants of the non-struct completion RPCs. Old peers fall back to today's behavior. No allocation RPC signature changes. - **Persistent formats:** none change. Ledger entries live in owner memory, and reservations exist only in the leader's runtime state. - **Mixed versions:** in `off` and `shadow`, any mix behaves as today. `takeover` needs ledger-enabled masters and owners, and `enforce` also needs every client upgraded. ### Performance - **Write path:** one intra-datacenter round trip to the segment owner before the first byte. It is a local call when the writer owns the segment, and one round trip per batch for batch APIs. - **Clears:** asynchronous and batched, off the latency path. - **Master:** no added steady-state cost. - **Failover:** one report per segment before its remount. - **Measurement:** the `shadow` mode measures the cost on real workloads before enforcement is proposed. If the cost is not acceptable, the feature stays off, and RL02 remains the alternative. ### Alternatives considered | | RL02: durable `REPLICA_CREATE` | Quarantine free space after failover | Owner ledger (this RFC) | | --- | --- | --- | --- | | Write-path cost | At least one etcd commit | None | One intra-DC round trip | | Relies on a writer time bound | No | Yes; #4491 shows none exists | No | | Capacity loss at failover | None | All free space, for a while | Only ranges still being written | | Media covered | All master-allocated media | All | Memory replicas | The ledger and RL02 can coexist, for example the ledger for memory and RL02 for NoF. ## Implementation plan The work is split into small PRs. One setting, `allocation_ledger_mode`, gates it, with four levels: - `off`: the default; no ledger work at all; - `shadow`: register and report, but only count failures and mismatches; - `takeover`: also reconcile reported entries after a failover; - `enforce`: also reject unregistered writes and refuse allocations to undeclared clients. The mode is set on the masters. The leader advertises it in `PingResponse`, and clients follow it, so a single setting switches the whole cluster. Clients learn of a change only at their next ping. So a raise takes effect only after every connected client has acknowledged the new mode, or has left. Clients acknowledge by resending their capability declaration. This way a client never acts on a lower mode than the leader. A client that reconnects pings before it allocates, so it starts with the current mode. A lowering takes effect at once. I plan to implement it once the direction is agreed. | Phase | PRs | Result | Behavior change | | --- | --- | --- | --- | | 1. Plumbing | 1. Leader session token and ledger mode in `PingResponse`; client term tracking; capability declaration and mode acknowledgement<br>2. Completion identity: issuing term on completion RPCs<br>3. Ledger RPC service on segment providers; ledger address lookup | Terms and identities flow end to end | None; counts only, in `shadow` | | 2. Shadow mode | 4. Owner-side ledger: register, token, clear, local takeover<br>5. Writer-side registration in `TransferSubmitter`'s write entry points, covering every write path | Ledger populated on real traffic | None; counts only, in `shadow` | | 3. Takeover | 6. Report on mount and remount, applied inside the remount's critical section<br>7. Reconciliation: reserve, hide and remove, release on clear | A promoted leader protects in-flight ranges | In `takeover` | | 4. Enforcement | 8. Reject unregistered writes; refuse allocations to undeclared clients<br>9. Reclaim orphaned entries | Guarantee in effect | In `enforce` | | 5. Validation | 10. Fault-injection tests, including real etcd HA failover<br>11. Benchmarks against no ledger and an RL02-style prototype<br>12. Documentation and an operations guide | Evidence for enabling by default | None | Dependencies: - Clearing on the revoke and timeout path relies on the drain work in #4780 and #4491. - The takeover builds on the remount path being changed by #4802 and #3666. - Rule 3 must survive the master lock rework in #4700 and #4801. ## Rollout process 1. **Land the PRs phase by phase, with the default mode `off`.** Nothing changes. 2. **Upgrade all clients and masters, in any order, then switch to `shadow`.** Watch registration latency and failures, owner load, live entry counts, and completion-term mismatches. 3. **Switch a staging HA cluster to `takeover`.** Run the fault-injection suite and real failovers. Verify that no protected range is reused, and that hidden replicas are removed rather than served. 4. **Move production clusters to `takeover`, then to `enforce`, one cluster at a time.** A cluster moves to `enforce` only after every client in it has declared ledger support. 5. **Consider a non-`off` default** once maintainers accept the benchmark results and the staging evidence. Rollback: lowering the mode, down to `off`, takes effect immediately and returns the cluster to today's protection. No persistent state needs migration, because ledger entries and reservations live only in memory. ## Open questions 1. Is one client-to-client round trip on the write path acceptable, compared with RL02's etcd commit? 2. Should this replace RL02 for memory replicas, or ship as a mode next to it? 3. Should the completion term travel in term-carrying RPC variants or in an RPC attachment (#3848)? 4. Is failing a put that straddles a failover cleanly enough, or should a follow-up complete it on the new leader? ## Related Issues and PRs: #2979, #3808, #4491, #3885, #3030, #2953, #3819, #3826, #4780, #4802, #3666, #4700, #4801, #3848. ### AI assistance disclosure The analysis and this text were prepared with an AI coding assistant (Claude Code), which read the code on `main` at `042ab8a1`. The submitter directed and reviewed it. ### Before submitting a new issue... - [x] Make sure you already searched for relevant issues and read the [documentation](https://kvcache-ai.github.io/Mooncake/)
Author
Owner

@github-actions[bot] commented on GitHub (Oct 21, 2026):

Thanks for opening this issue, @SongOf!

Field Value
Issue #4837
GitHub user ID 46475785
Reporter @SongOf

A maintainer will triage this when possible. To help us respond faster, please include:

  • Mooncake version or commit SHA
  • Environment (OS, CUDA/driver, RDMA stack if relevant)
  • Steps to reproduce and expected vs. actual behavior

Useful links: Documentation · Contributing guide

This message was posted automatically by the issue bot.

<!-- gh-comment-id:6321813664 --> @github-actions[bot] commented on GitHub (Oct 21, 2026): Thanks for opening this issue, @SongOf! | Field | Value | |-------|-------| | **Issue** | #4837 | | **GitHub user ID** | `46475785` | | **Reporter** | @SongOf | A maintainer will triage this when possible. To help us respond faster, please include: - Mooncake version or commit SHA - Environment (OS, CUDA/driver, RDMA stack if relevant) - Steps to reproduce and expected vs. actual behavior Useful links: [Documentation](https://kvcache-ai.github.io/Mooncake/) · [Contributing guide](https://github.com/kvcache-ai/Mooncake/blob/main/CONTRIBUTING.md) > This message was posted automatically by the issue bot.
Sign in to join this conversation.
No milestone
No project
No assignees
1 participant
Notifications
Due date
The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference
kvcache-ai/Mooncake#1232
No description provided.