[RFC]: [Store] Partitioned multi-SubMaster metadata plane with CVM coordination and VSegment striping #57

Changes proposed

• Status: Implemented on an internal branch, except commit-time fencing (see Open Questions); the implementation is being aligned with this design before PRs are opened.
• Target: kvcache-ai/Mooncake
• Component: mooncake-store (Master, client routing, segment mounting, transfer submission), plus a one-time quota planning tool
• Proposed PR prefix: [Store]

cc: @ykwd @stmatengss (Store) @Icedcoco @Aionw (HA / MasterService) @llfl @Bo-Vincent @zxpdemonio (Store-RS)

Summary

Today one active Master serves every client of the C++ Mooncake Store, and hot standbys are used only for failover. This RFC lets several SubMasters serve the metadata plane in parallel, and builds VSegment striping on top of it:

• SubMaster + KV partition routing. Keys hash to one of 16384 fixed KV partitions, which a pure function groups into G contiguous KVPT groups. Each group has one primary SubMaster (the existing MasterService, scoped to its groups), recorded in ETCD as one record per group. Clients compute the owner locally and call it directly. An optional paired standby replays the group's OpLog and takes over without an inter-Master metadata transfer.
• CVM (Cache View Master). Coordination logic embedded in every Master process, with no separate process and no elected leader. Every CVM applies the same deterministic rules (role assignment, standby promotion, reshard), and every ownership change is an ETCD compare-and-swap. CVM is never on the request path.
• VSegment. Stripes one replica across several physical segments on different hosts, so a large Put/Get can use several devices in parallel. A one-time planner divides physical space statically between partitions, so SubMasters never race for the same bytes.

The data path does not change: payloads move directly between clients and segments through Transfer Engine (TE) or TENT. With G = 1, behaviour is identical to today's single Master, and VSegment is off by default.

Consistency. Within a KVPT group, consistency is unchanged in steady state: one primary, linearizable metadata updates. Across ownership changes, preventing stale commits requires fencing at the metadata commit point; that mechanism is an open design item for the first multi-SubMaster release.

Non-goals.

• A new store implementation, or changes to the semantics of existing client APIs, replica types, offload, NoF, DFS or HA. Partitioning changes which Master owns a key, not what the Master does with it.
• Moving object bytes on ownership changes. Only metadata moves.
• Changing G online, and cross-cluster or cross-datacenter federation.
• Adding replicas or redundancy through striping.

Motivation

One active Master carries every client's metadata RPCs, allocator management and background scans, and failover must restore the entire metadata set before any client is served again. Large deployments have reported these limits:

• kvcache-ai/Mooncake#2117: about 10,000 clients behind one Master, with allocator management too heavy, RPC threads exhausted and HA recovery too slow.
• kvcache-ai/Mooncake#3517: a cluster-wide scan under global locks turns a routine scale-up into minutes of PutStart timeouts.
• kvcache-ai/Mooncake#990: master capacity for deployments targeting up to 1M metadata QPS.

Tenant-first locking (kvcache-ai/Mooncake#3670 / kvcache-ai/Mooncake#4557) and finer global locking (kvcache-ai/Mooncake#4700) make one Master more efficient. This RFC is complementary: capacity scales with G, and a failure affects only one KVPT group.

Separately, a replica today occupies one contiguous range in one segment, so a large Put/Get is capped by one device and inherits its queueing. VSegment addresses this. It needs a Master-side owner to divide physical space between partitions deterministically, and the partitioned metadata plane provides one.

Terminology

• KV partition (KVPT): one of 16384 fixed partitions of the key space; partition_id = CRC32C(tenant, key) mod 16384, computed on the client.
• KVPT group (rank), G: one of G contiguous ranges of partitions; rank = KvptToRank(partition_id, G) = partition_id × G / 16384. The unit of ownership, failover and reshard. G is fixed at cluster creation.
• SubMaster, paired standby, caretaker: a SubMaster is a MasterService that is the primary of one or more KVPT groups. A paired standby replays one group's primary and takes over on failover. When a group has no native primary, the primary of the preceding non-empty group serves it as caretaker. M is the total number of Master processes.
• kvpt_groups/{rank}, epoch: the ETCD ownership record of one group, {primary_id, standby_ids, state, migrating_to_id, epoch}; there are G records, not 16384. The epoch is incremented by every ownership change through ETCD CAS and is the fencing token between generations of owners.
• psegment: an existing physical Segment registered by a client.
• VSegment, profile: a VSegment is an immutable logical address space striped round-robin over N equal-length extents on different psegments. A profile names its layout: member count, extent size, stripe size and medium.

Proposed Architecture

Segments, Transport Engine and the Offloading Service are unchanged.

Hot path. In steady state, a metadata request costs one RPC from the client to the owning SubMaster. ETCD, CVM and the planner are off the request path, server-side forwarding is only a fallback for badly stale routes, and data never passes through a SubMaster. The client refreshes its route cache in the background and on stale-route or transport errors.

Object addressing. Routing finds the owning SubMaster; that SubMaster's metadata finds the bytes.

graph LR
    K["(tenant, key)"] -->|"CRC32C mod 16384"| S["KV partition<br/>(partition_id)"]
    S -->|"KvptToRank (pure function)"| G["KVPT group (rank)"]
    G -->|"kvpt_groups/{rank}"| O["primary SubMaster"]
    O --> OM["ObjectMetadata"]
    OM --> R1["Replica: single segment<br/>(segment, offset, length)"]
    OM --> R2["Replica: VSegment<br/>(partition_id, vsegment_id,<br/>logical_offset, length)"]
    R2 --> V["VSegmentView<br/>(immutable)"]
    V --> X1["extent on psegment 1"]
    V --> X2["extent on psegment 2"]
    V --> XN["extent on psegment N"]

Routing and Ownership

Why KVPT groups. Persisting one record per partition rewrote thousands of ETCD records on every membership change and grew the ETCD database monotonically. A pure consistent-hash ring avoided those writes but reshuffled ownership on every primary failure, landing partitions on survivors without their metadata. KVPT groups combine both lessons:

partition_id → rank    = KvptToRank(partition_id, G)   // pure function, never stored
rank → primary         = kvpt_groups[rank]              // stable state, G records in ETCD

ETCD layout

/cvm/{namespace}/
├── masters/{master_id}            # MasterRegistration {master_id, address, role, registered_at_ms} (leased)
├── cluster_meta                   # RingMeta {submaster_count, kvpt_group_count = G}
├── kvpt_groups/{rank:05d}          # KvptGroupAssign {rank, primary_id, standby_ids[], state, migrating_to_id, epoch} (not leased)
├── reshard_intent/{rank:05d}      # pending reshard target (admin intent, resumable)
├── segments/{segment_id}          # segment descriptor (capacity, endpoint, protocol, host, ranges)
└── snapshot/{master_id}/segments/{segment_id}   # this Master's mount record (leased)

/mooncake/vsegment/partition-quota/current      # PartitionPhysicalQuotaSnapshot (immutable, checksummed; written once by PartitionQuotaPlanner)

Liveness and ownership are separate: masters/{id} carries a lease, kvpt_groups/{rank} does not, so the epoch survives a primary's death and can fence it. Records are created with CreateKvptGroupAssign (only if absent) and changed with CASSwitchKvptGroupOwner (only if the stored epoch matches; writes epoch + 1); a lost race returns STALE_ROUTE. OpLogs and metadata snapshots stay in the existing HA backend; this RFC adds no new OpLog keys.

Request routing

sequenceDiagram
    participant C as Client
    participant A as Cached primary of rank r
    participant E as ETCD kvpt_groups
    C->>C: partition_id = CRC32C(tenant, key) mod 16384, r = KvptToRank(partition_id, G)
    C->>A: request(partition_id, ...)
    alt A can serve the request
        A-->>C: result
    else A is freezing writes or the partition is not ready
        A-->>C: KVPT_MIGRATING
        C->>C: back off, refresh route, retry (bounded)
    else A no longer owns rank r
        A->>A: try forwarding to the current owner (fallback)
        alt forwarding succeeds
            A-->>C: forwarded result
        else forwarding fails
            A-->>C: KVPT_NOT_OWNED
            C->>E: reload kvpt_groups
            C->>C: retry on the current primary
        end
    else connection failure or timeout
        C->>E: reload kvpt_groups
        C->>C: retry within budget if safe for this operation
    end

• Reads and writes use the same route; during a reshard, the source keeps serving reads until the owner switch while writes are frozen. After a timeout, the client retries only operations that are safe to retry, since a write's outcome may be unknown.
• Batch APIs issue one RPC per primary and return per-key results. Global operations (RemoveAll, RemoveByRegex) are broadcast to every primary.

Fencing

• Control plane. Every ownership change uses an epoch CAS on kvpt_groups/{rank}. The record names one primary, and concurrent changes using the same expected epoch have one winner.
• Request admission. Each Master watches kvpt_groups and uses its local ownership view and lease state to admit writes. Once the former primary observes the ownership change, it drops the group from its local owner set and rejects local writes with KVPT_NOT_OWNED.
• Commit-time fencing (open). Before the former primary observes the change, its local view can still admit writes, and operations already in flight can reach the commit path. The release must also fence commits from the former owner, including PutEnd for a reservation created before the ownership change. See Open Questions.

SubMaster, Failover and CVM

• Ownership. A SubMaster serves only partitions of the KVPT groups it is primary (or caretaker) of. A partition that is assigned but whose metadata is not yet installed returns KVPT_MIGRATING.
• Segments. Each client mounts every local segment on every primary and heartbeats every primary, so any owner can allocate on any client's memory. Each psegment is split into ranges by KVPT group, and a SubMaster allocates ordinary replicas only inside the ranges of the groups it owns. VSegment space is divided by the static quota below.
• Pairing. Each SubMaster keeps its OpLog and snapshots through the existing HA path. Pairing is 1:1. New Masters fill a missing primary first, then a missing standby, and otherwise join an idle pool. With M < 2G, some groups have no standby; with M < G, caretakers keep every group served.
• Failover. When a primary's lease expires, its standby catches up the OpLog, wins the promotion CAS (epoch + 1) and starts serving once the group is ready. Only that group is affected and no metadata moves. A returning old primary sees it is no longer primary and steps down. Clients may hold a stale route until they refresh.
• No standby. A caretaker takes the group over and rebuilds its metadata from client remounts. This is a degraded path, and it is why production groups should have a standby.
• CVM. Every Master embeds CvmController, EtcdViewStore and CvmHttpServer. Masters are ordered by ETCD create_revision and each decides its own role from masters/ and kvpt_groups/. The first Master bootstraps rank 0 and caretakes the other ranks; later Masters claim ranks through reshard. Operators use GET /kvpt_groups and POST /reshard?rank=&target= on any Master. Because every CVM applies the same rules to the same ETCD state and every change is a CAS, concurrent actions converge without a leader.

Scale-out and Reshard

A reshard moves one KVPT group from a source primary A to a target C'. It is used when a new Master claims a caretaken group and when an operator rebalances. Failover uses standby promotion, not reshard. Only metadata moves.

sequenceDiagram
    participant Op as Operator / new Master
    participant E as ETCD
    participant A as Source primary A
    participant C as Target C'
    Op->>E: reshard_intent/{r} = C'
    C->>E: CAS kvpt_groups/{r}: state=kMigrating, migrating_to=C' (epoch+1)
    E-->>A: watch: rank r kMigrating
    A->>A: stop admitting new writes (KVPT_MIGRATING), continue reads
    A->>A: resolve in-flight mutations, then stage the export
    C->>A: ExportKvptBatch(rank r)
    A-->>C: object metadata + VSegment state of rank r
    C->>C: durably install the imported state
    C->>A: AckKvptRangeImported(rank r)
    C->>E: CAS kvpt_groups/{r}: primary=C', state=kStable (epoch+1)
    E-->>C: ownership switch confirmed
    C->>C: start serving rank r
    E-->>A: watch confirms rank r moved to C'
    A->>A: clean up the former copy of rank r metadata
    A-->>C: cleanup complete
    C->>E: clear the completed reshard intent

• Write barrier, not dual write. The source stops admitting new writes, resolves in-flight mutations, then exports a snapshot; it keeps its metadata and serves reads while it owns the group. The target durably installs the snapshot before acknowledging. Clients receiving KVPT_MIGRATING back off within a bounded time and refresh the route.
• Owner switch. One CAS switches the whole group. The target serves only after the CAS succeeds; the source cleans up only after observing the switch.
• Resumability and concurrency. The persisted intent and ownership record tell a restarted driver whether to resume or abandon the import, or to retry post-switch cleanup. A standby promoted before the switch invalidates the old intent. Only one reshard can be in kMigrating per group.

VSegment

Data model

VSegmentView                       // immutable, checksummed
  vsegment_id, partition_id, mapping_algorithm = ROUND_ROBIN, stripe_size,
  members: PSegmentExtent[]        // ordered, >= 2, equal length
  logical_capacity, checksum

PSegmentExtent      = {segment (stable identity), base_offset, length}
ReplicaDescriptor   += {partition_id, vsegment_id, logical_offset, length}   // new variant

• A layout change creates a new vsegment_id; views are never rewritten.
• The view has no owner field. The owner is derived from partition_id, so ownership changes do not alter the view.
• Runtime attributes (endpoint, medium, health) are resolved at expansion time and are not part of the view.
• Committed occupancy is derived only from ReplicaDescriptors. VSegment state is replayed by the standby and moves with the KVPT group in a reshard.

Static per-partition quotas

At cluster initialization, PartitionQuotaPlanner runs once. It reads the partitions, the segment metadata and a quota policy of named profiles (for example, nvme_default: 4 members × 64 GiB extents, 1 MiB stripes). In balanced mode it splits each profile's segments by bytes across partitions, deterministically. It validates the plan (no overlap, in bounds, correct medium and alignment), publishes one immutable snapshot to /mooncake/vsegment/partition-quota/current with an ETCD CAS, and exits. At runtime an owner uses only the quotas of the partitions it serves. Re-planning requires downtime.

Stripe mapping

stripe_index     = floor(L / S)
member_index     = stripe_index mod N
physical_offset  = B[member_index] + floor(stripe_index / N) × S + (L mod S)

TransferSubmitter splits a logical range at stripe boundaries and client slice boundaries into ordinary TE requests. Sub-requests may complete out of order; the task succeeds only if all of them succeed.

Lifecycle, Put and Get

• Lifecycle: preparing → active → draining → retired.
• Creation is one owner transaction, single-flight per (partition_id, profile). It takes exactly member_count distinct segments from the quota or fails with VSEGMENT_STATIC_QUOTA_INSUFFICIENT; it never shrinks the layout.
• Put. PutStart durably reserves a logical range in an active VSegment, or returns a retryable VSEGMENT_CREATING while one is created. The client writes all members in parallel through TE, then calls PutEnd, or PutRevoke if any write fails. Get uses the same expansion with reads.
• Reclaim and delete. A reservation is reclaimed only after lease expiry, a confirmed ownership change or owner restart, and an I/O grace period longer than the TE timeout. Delete removes object metadata before returning the range, so a crash in between is safe.
• Availability. A striped replica is unreadable if any member is lost: availability drops from A to A^N (0.999 → about 0.996 for N = 4), and the only repair is to delete and re-Put. VSegment is off by default, operators must not lower replica counts because of striping, and the recommended deployment pairs striped cache-tier replicas with durable single-segment replicas.

Relationship to Existing Work

Delivery Plan

Every PR builds, passes tests and is correct on its own; with G = 1, behaviour is unchanged until the final PRs.

1. Hashing and KVPT groups: KvHashMap, KvptToRank.
2. Ownership records: KvptGroupAssign, ETCD load/watch and the two CAS primitives.
3. Client routing and segment mounting on every primary, with backoff, route refresh and global-operation broadcast.
4. Server ownership checks, forwarding fallback, and commit-time fencing before multi-SubMaster writes are enabled.
5. Embedded CVM: roles, standby pairing, failover, caretaking and bootstrap.
6. Reshard: write barrier, export/import, owner switch, resumable cleanup and admin endpoints.
7. VSegment core: view, descriptor variant, mapping and expansion.
8. Static quotas: PartitionQuotaPlanner and snapshot publish.
9. VSegment lifecycle and recovery, including replay and reshard.
10. Documentation and deployment guide.

Validation and Acceptance Criteria

• With G = 1 and VSegment off, existing test suites pass unchanged; every PR adds unit and integration tests.
• Concurrent promotion attempts against the same epoch produce exactly one successful ownership CAS.
• Clients refresh routing on KVPT_NOT_OWNED, connection failure or timeout, and retry eligible requests within their retry budget.
• Bootstrap, scale-out through reshard, and failover with and without a standby lose or duplicate no objects and leave each group with exactly one primary.
• An operation accepted by the former primary cannot commit after ownership changes, including a delayed PutEnd while the former primary's watch is stale.
• VSegment mapping matches golden vectors, quota ranges and extents never overlap, and losing one member never produces a partial or corrupt read.
• The implementation PRs will report metadata throughput and latency for G = 1, 2, 4, 8, failover and reshard impact, and VSegment Put/Get bandwidth and tail latency.

Compatibility and Rollout

• G = 1 is today's behaviour and the rollback path; an old RingMeta deserializes as G = 1. New RPCs, fields and error codes are additive.
• Multi-SubMaster mode is enabled by deploying more Masters with G > 1. Start one Master first, then add the others.
• Clients without KVPT-group routing must not connect to a cluster with G > 1. Unknown descriptor variants fail closed.
• VSegment-committed objects cannot be read by old binaries and must be drained before a downgrade.

Open Questions

1. Commit-time fencing. Where should the commit path enforce the KVPT-group epoch, and how should it handle in-flight operations from a previous owner? The mechanism needs to reject a stale commit even if the former primary has yet to observe the ownership change.
2. Changing G. Is a cold rebuild acceptable for a first version, or is online G change required?
3. Stuck reshard. If the target hangs while keeping its lease, the group stays write-frozen. Should kMigrating carry a TTL?
4. Failover without a standby. A caretaker may lose that group's historical objects. Should production require M ≥ 2G Masters?
5. Tenant quota across SubMasters. Should it be split per SubMaster, coordinated centrally, or enforced approximately?
6. ETCD load. Should multi-SubMaster deployments require the Redis HA backend or a separate ETCD per SubMaster for OpLogs?
7. Naming. Are SubMaster, CVM and vsegment acceptable public names?

Before submitting a new issue...

• Make sure you already searched for relevant issues and read the documentation