kvcache-ai/Mooncake

Fork 0

mirror of https://github.com/kvcache-ai/Mooncake.git synced 2026-11-05 01:17:55 +00:00

[GH-ISSUE #1200] [RFC]: Hot Standby Mode for Master Service Metadata High Availability #408

New issue

Open

opened 2026-10-29 21:14:07 +00:00 by bsakaguchi · 4 comments

bsakaguchi commented

2026-10-29 21:14:07 +00:00

Owner

Originally created by @Libotry on GitHub (Dec 12, 2025).
Original GitHub issue: https://github.com/kvcache-ai/Mooncake/issues/1200

Introduction

To address the issue where all metadata is lost after a master service failure and recovery, this solution proposes a hot-standby synchronization mechanism and a hybrid approach combining hot standby with snapshots, ensuring rapid data recovery following a master service failure.

Motivation

The current HA (High Availability) mode only supports rapid restart of the master service after a failure but cannot guarantee fast data recovery. The pain points of the current HA mode are as follows:

Issue	Impact	Severity
Complete loss of metadata after Leader failure	All KV cache location information is lost and must be rebuilt	🔴 Critical
Follower lacks data pre-warming	After successful election, the new Leader must start serving from scratch	🟠 Medium
Long recovery time	Relies on clients to re-register; may take several minutes to tens of minutes	🟠 Medium
Service unavailability window	Requests cannot be processed during Leader failover	🟡 Low

Goals:

Near-zero RPO: Minimize the data loss window
Fast failover: Achieve second-level RTO (Recovery Time Objective)
Data consistency guarantee: Ensure correct synchronization between primary and standby
Verifiability: Include mechanisms to validate data integrity
Low performance overhead: Avoid impacting normal business operations

Proposal

1. Core Design Approach

Use etcd as an intermediate reliability component to implement OpLog primary-standby synchronization:

OpLog Mechanism: Primary Master records all state change operations to OpLog
etcd Storage: OpLog is written to etcd, leveraging etcd's strong consistency and persistence capabilities
Watch Mechanism: Standby Master receives OpLog in real-time through etcd Watch mechanism
Ordering Guarantee: Guarantee operation order through global sequence_id and key-level key_sequence_id

2. Architecture Design

(1) Overall Architecture

The overall architecture diagram shows the interaction relationships between Primary Master, etcd Cluster, and Standby Master:

Architecture Description:

Primary Master: Handles client requests, records OpLog and writes to etcd
etcd Cluster: Acts as intermediate storage, providing strong consistency and Watch mechanism
Standby Master: Receives OpLog in real-time by watching etcd and applies to local metadata store

(2) Data Flow Diagram

The data flow diagram shows the complete flow from Client request to Standby synchronization:

Flow Description:

a. Client sends PutEnd request to Primary Master
b. Primary Master records operation through OpLogManager, generating sequence_id
c. EtcdOpLogStore writes OpLog to etcd
d. etcd notifies Standby Master through Watch mechanism
e. OpLogWatcher receives events and passes to OpLogApplier
f. OpLogApplier checks order and applies to Standby's metadata store

(3) Failover Sequence

The failover sequence diagram shows the complete process from Primary failure to Standby promotion to Primary:

Flow Description:

a. Normal Operation: Primary maintains Lease, Standby continuously synchronizes OpLog through Watch
b. Primary Failure: Primary's Lease expires, etcd notifies Standby
c. Standby Promotion: Stop Standby service, initialize Lease, clean expired metadata, start leader election

3. Core Component Design

(1) OpLogManager (Primary Side)

Responsibilities:

Record all state change operations (PUT_END, PUT_REVOKE, REMOVE)
Generate global sequence_id and key-level key_sequence_id
Maintain memory buffer (for fast queries)

Key Methods:

class OpLogManager {
    uint64_t Append(OpType type, const std::string& key, 
                    const std::string& payload = "");
    std::vector<OpLogEntry> GetEntriesSince(uint64_t since_seq_id, 
                                            size_t limit = 1000) const;
    uint64_t GetLastSequenceId() const;
};

(2) EtcdOpLogStore (Primary Side)

Responsibilities:

Write OpLog to etcd
Update latest sequence_id
Record snapshot corresponding sequence_id
Clean up old OpLog

etcd Key Design:

OpLog Entry: mooncake-store/oplog/{cluster_id}/{sequence_id}
Latest Sequence ID: mooncake-store/oplog/{cluster_id}/latest
Snapshot Sequence ID: mooncake-store/oplog/{cluster_id}/snapshot/{snapshot_id}/sequence_id

(3) OpLogWatcher (Standby Side)

Responsibilities:

Watch etcd OpLog changes
Read historical OpLog (for initial synchronization)
Process Watch events and pass to OpLogApplier

Key Methods:

class OpLogWatcher {
    void Start();
    void Stop();
    bool ReadOpLogSince(uint64_t start_seq_id, 
                        std::vector<OpLogEntry>& entries);
};

(4) OpLogApplier (Standby Side)

Responsibilities:

Apply OpLog Entry to local metadata store
Check global and key-level order
Handle sequence number discontinuities and out-of-order cases
Periodically clean up key_sequence_map_ (memory optimization)

Key Methods:

class OpLogApplier {
    bool ApplyOpLogEntry(const OpLogEntry& entry);
    bool CheckSequenceOrder(const OpLogEntry& entry);
    void CleanupStaleKeySequences();
};

(5) HotStandbyService (Standby Side)

Responsibilities:

Manage Standby mode lifecycle
Coordinate OpLogWatcher and OpLogApplier
Handle Standby promotion to Primary logic

Key Methods:

class HotStandbyService {
    void StartStandby();
    void Stop();
    void Promote();
};

4. OpLog Entry Data Structure

struct OpLogEntry {
    uint64_t sequence_id{0};        // Globally monotonically increasing sequence
    uint64_t timestamp_ms{0};        // Timestamp (milliseconds)
    OpType op_type{OpType::PUT_END}; // PUT_END, PUT_REVOKE, REMOVE
    std::string object_key;          // Object key
    std::string payload;             // Optional payload (carries replica info for PUT_END)
    uint32_t checksum{0};           // Checksum
    uint32_t prefix_hash{0};        // Key prefix hash
    uint64_t key_sequence_id{0};     // Per-key operation sequence (for ordering guarantee)
};

JSON Serialization Format:

{
  "sequence_id": 12345,
  "timestamp": 1704110400123,
  "op_type": "PUT_END",
  "key": "object_key_123",
  "payload": "optional_payload",
  "checksum": 1234567890,
  "prefix_hash": 987654321,
  "key_sequence_id": 5
}

5. Ordering Guarantee Mechanism

(1) Global Sequence Number (sequence_id)

Purpose: Guarantee global order of all OpLog events
Generation: Generated globally incrementally by Primary's OpLogManager
Check: Standby checks if sequence_id is continuous

(2) Key-Level Sequence Number (key_sequence_id)

Purpose: Guarantee operation order for the same key
Generation: Incremented separately for each key on Primary side
Check: Standby checks if key_sequence_id is increasing

(3) Out-of-Order Handling

When key_sequence_id out-of-order is detected:

Rollback: Delete all state of the key from metadata_store
Replay: Re-read all OpLog from etcd starting from the key's first sequence_id
Rewrite: Re-apply all OpLog in correct order to rebuild metadata

6. Snapshot Integration

(1) Record Sequence ID During Snapshot

When snapshot is generated, record current OpLog sequence_id
Write snapshot info to etcd: mooncake-store/oplog/{cluster_id}/snapshot/{snapshot_id}/sequence_id

(2) OpLog Cleanup

After snapshot generation, OpLog before snapshot can be cleaned up
Cleanup strategy: Query minimum existing sequence_id from etcd, use DeleteRange to delete

7. Standby Service Integration

(1) Problem

In existing code, Standby only blocks and waits during leader election, without running Standby service to synchronize OpLog.

(2) Solution

In MasterServiceSupervisor::Start():

Check if there is currently a leader
If there is a leader and it's not self → Start Standby service (watch OpLog and apply)
After successful election → Stop Standby service and promote to Primary

8. Lease Initialization When Standby Promotes to Primary

(1) Problem

Objects on Standby all have lease = 0 (because OpLog only contains PUT_END, not renewal information), and all objects will expire immediately after promotion to Primary.

(2) Solution

In HotStandbyService::Promote():

Stop Standby service
Iterate through all metadata
For objects with lease_timeout = 0, grant default lease time (default_kv_lease_ttl)

9. Memory Optimization: key_sequence_map_ Cleanup

(1) Problem

key_sequence_map_ on Standby side is used to track key_sequence_id for each key. After metadata is deleted, these entries are still retained, which may cause memory leaks during long-term operation.

(2) Solution

Implement periodic cleanup mechanism:

Cleanup Condition: Last operation is REMOVE and more than 1 hour has passed
Cleanup Frequency: Scan once per hour
Retention Strategy: Keys with PUT_END and PUT_REVOKE operations are not cleaned

Key Design Points Summary

etcd as Intermediate Storage: Leverage etcd's strong consistency and Watch mechanism
Record Only Critical Operations: PUT_END, PUT_REVOKE, REMOVE, do not record LEASE_RENEW
Dual Sequence Number Guarantee: Global sequence_id + key-level key_sequence_id
Snapshot Integration: Integrate with existing snapshot mechanism, support OpLog cleanup
Standby Service Runs in Parallel: Continuously synchronize data during election waiting period
Memory Optimization: Periodically clean up expired entries in key_sequence_map_

Before submitting a new issue...

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

Originally created by @Libotry on GitHub (Dec 12, 2025). Original GitHub issue: https://github.com/kvcache-ai/Mooncake/issues/1200 ## Introduction To address the issue where all metadata is lost after a master service failure and recovery, this solution proposes a **hot-standby synchronization mechanism** and a **hybrid approach** combining hot standby with snapshots, ensuring rapid data recovery following a master service failure. ## Motivation The current HA (High Availability) mode only supports rapid restart of the master service after a failure but cannot guarantee fast data recovery. The pain points of the current HA mode are as follows: | Issue | Impact | Severity | | -------------------------------------------------- | ------------------------------------------------------------ | ---------- | | **Complete loss of metadata after Leader failure** | All KV cache location information is lost and must be rebuilt | 🔴 Critical | | **Follower lacks data pre-warming** | After successful election, the new Leader must start serving from scratch | 🟠 Medium | | **Long recovery time** | Relies on clients to re-register; may take several minutes to tens of minutes | 🟠 Medium | | **Service unavailability window** | Requests cannot be processed during Leader failover | 🟡 Low | ## Goals: 1. **Near-zero RPO**: Minimize the data loss window 2. **Fast failover**: Achieve second-level RTO (Recovery Time Objective) 3. **Data consistency guarantee**: Ensure correct synchronization between primary and standby 4. **Verifiability**: Include mechanisms to validate data integrity 5. **Low performance overhead**: Avoid impacting normal business operations ## Proposal ### 1. Core Design Approach **Use etcd as an intermediate reliability component to implement OpLog primary-standby synchronization**: - **OpLog Mechanism**: Primary Master records all state change operations to OpLog - **etcd Storage**: OpLog is written to etcd, leveraging etcd's strong consistency and persistence capabilities - **Watch Mechanism**: Standby Master receives OpLog in real-time through etcd Watch mechanism - **Ordering Guarantee**: Guarantee operation order through global sequence_id and key-level key_sequence_id ### 2. Architecture Design #### (1) Overall Architecture The overall architecture diagram shows the interaction relationships between Primary Master, etcd Cluster, and Standby Master: <img width="2258" height="1547" alt="Image" src="https://github.com/user-attachments/assets/48471cd3-c91e-47db-b1f5-eb88634be2a7" /> **Architecture Description**: - **Primary Master**: Handles client requests, records OpLog and writes to etcd - **etcd Cluster**: Acts as intermediate storage, providing strong consistency and Watch mechanism - **Standby Master**: Receives OpLog in real-time by watching etcd and applies to local metadata store #### (2) Data Flow Diagram The data flow diagram shows the complete flow from Client request to Standby synchronization: <img width="1361" height="935" alt="Image" src="https://github.com/user-attachments/assets/e7c22aaa-4e2c-4efe-a2b0-247692cd93fc" /> **Flow Description**: a. Client sends `PutEnd` request to Primary Master b. Primary Master records operation through `OpLogManager`, generating sequence_id c. `EtcdOpLogStore` writes OpLog to etcd d. etcd notifies Standby Master through Watch mechanism e. `OpLogWatcher` receives events and passes to `OpLogApplier` f. `OpLogApplier` checks order and applies to Standby's metadata store #### (3) Failover Sequence The failover sequence diagram shows the complete process from Primary failure to Standby promotion to Primary: <img width="1166" height="913" alt="Image" src="https://github.com/user-attachments/assets/fa767c24-195f-4ad1-bb9f-10e8d1aca1c8" /> **Flow Description**: a. **Normal Operation**: Primary maintains Lease, Standby continuously synchronizes OpLog through Watch b. **Primary Failure**: Primary's Lease expires, etcd notifies Standby c. **Standby Promotion**: Stop Standby service, initialize Lease, clean expired metadata, start leader election ### 3. Core Component Design #### (1) OpLogManager (Primary Side) **Responsibilities**: - Record all state change operations (PUT_END, PUT_REVOKE, REMOVE) - Generate global sequence_id and key-level key_sequence_id - Maintain memory buffer (for fast queries) **Key Methods**: ```cpp class OpLogManager { uint64_t Append(OpType type, const std::string& key, const std::string& payload = ""); std::vector<OpLogEntry> GetEntriesSince(uint64_t since_seq_id, size_t limit = 1000) const; uint64_t GetLastSequenceId() const; }; ``` #### (2) EtcdOpLogStore (Primary Side) **Responsibilities**: - Write OpLog to etcd - Update latest sequence_id - Record snapshot corresponding sequence_id - Clean up old OpLog **etcd Key Design**: - OpLog Entry: `mooncake-store/oplog/{cluster_id}/{sequence_id}` - Latest Sequence ID: `mooncake-store/oplog/{cluster_id}/latest` - Snapshot Sequence ID: `mooncake-store/oplog/{cluster_id}/snapshot/{snapshot_id}/sequence_id` #### (3) OpLogWatcher (Standby Side) **Responsibilities**: - Watch etcd OpLog changes - Read historical OpLog (for initial synchronization) - Process Watch events and pass to OpLogApplier **Key Methods**: ```cpp class OpLogWatcher { void Start(); void Stop(); bool ReadOpLogSince(uint64_t start_seq_id, std::vector<OpLogEntry>& entries); }; ``` #### (4) OpLogApplier (Standby Side) **Responsibilities**: - Apply OpLog Entry to local metadata store - Check global and key-level order - Handle sequence number discontinuities and out-of-order cases - Periodically clean up key_sequence_map_ (memory optimization) **Key Methods**: ```cpp class OpLogApplier { bool ApplyOpLogEntry(const OpLogEntry& entry); bool CheckSequenceOrder(const OpLogEntry& entry); void CleanupStaleKeySequences(); }; ``` #### (5) HotStandbyService (Standby Side) **Responsibilities**: - Manage Standby mode lifecycle - Coordinate OpLogWatcher and OpLogApplier - Handle Standby promotion to Primary logic **Key Methods**: ```cpp class HotStandbyService { void StartStandby(); void Stop(); void Promote(); }; ``` ### 4. OpLog Entry Data Structure ```cpp struct OpLogEntry { uint64_t sequence_id{0}; // Globally monotonically increasing sequence uint64_t timestamp_ms{0}; // Timestamp (milliseconds) OpType op_type{OpType::PUT_END}; // PUT_END, PUT_REVOKE, REMOVE std::string object_key; // Object key std::string payload; // Optional payload (carries replica info for PUT_END) uint32_t checksum{0}; // Checksum uint32_t prefix_hash{0}; // Key prefix hash uint64_t key_sequence_id{0}; // Per-key operation sequence (for ordering guarantee) }; ``` **JSON Serialization Format**: ```json { "sequence_id": 12345, "timestamp": 1704110400123, "op_type": "PUT_END", "key": "object_key_123", "payload": "optional_payload", "checksum": 1234567890, "prefix_hash": 987654321, "key_sequence_id": 5 } ``` ### 5. Ordering Guarantee Mechanism #### (1) Global Sequence Number (sequence_id) - **Purpose**: Guarantee global order of all OpLog events - **Generation**: Generated globally incrementally by Primary's `OpLogManager` - **Check**: Standby checks if sequence_id is continuous #### (2) Key-Level Sequence Number (key_sequence_id) - **Purpose**: Guarantee operation order for the same key - **Generation**: Incremented separately for each key on Primary side - **Check**: Standby checks if key_sequence_id is increasing #### (3) Out-of-Order Handling When key_sequence_id out-of-order is detected: - **Rollback**: Delete all state of the key from metadata_store - **Replay**: Re-read all OpLog from etcd starting from the key's first sequence_id - **Rewrite**: Re-apply all OpLog in correct order to rebuild metadata ### 6. Snapshot Integration #### (1) Record Sequence ID During Snapshot - When snapshot is generated, record current OpLog sequence_id - Write snapshot info to etcd: `mooncake-store/oplog/{cluster_id}/snapshot/{snapshot_id}/sequence_id` #### (2) OpLog Cleanup - After snapshot generation, OpLog before snapshot can be cleaned up - Cleanup strategy: Query minimum existing sequence_id from etcd, use DeleteRange to delete ### 7. Standby Service Integration #### (1) Problem In existing code, Standby only blocks and waits during leader election, without running Standby service to synchronize OpLog. #### (2) Solution In `MasterServiceSupervisor::Start()`: - Check if there is currently a leader - If there is a leader and it's not self → Start Standby service (watch OpLog and apply) - After successful election → Stop Standby service and promote to Primary ### 8. Lease Initialization When Standby Promotes to Primary #### (1) Problem Objects on Standby all have lease = 0 (because OpLog only contains PUT_END, not renewal information), and all objects will expire immediately after promotion to Primary. #### (2) Solution In `HotStandbyService::Promote()`: - Stop Standby service - Iterate through all metadata - For objects with lease_timeout = 0, grant default lease time (`default_kv_lease_ttl`) ### 9. Memory Optimization: key_sequence_map_ Cleanup #### (1) Problem `key_sequence_map_` on Standby side is used to track `key_sequence_id` for each key. After metadata is deleted, these entries are still retained, which may cause memory leaks during long-term operation. #### (2) Solution Implement periodic cleanup mechanism: - **Cleanup Condition**: Last operation is `REMOVE` and more than 1 hour has passed - **Cleanup Frequency**: Scan once per hour - **Retention Strategy**: Keys with `PUT_END` and `PUT_REVOKE` operations are not cleaned ## Key Design Points Summary 1. **etcd as Intermediate Storage**: Leverage etcd's strong consistency and Watch mechanism 2. **Record Only Critical Operations**: PUT_END, PUT_REVOKE, REMOVE, do not record LEASE_RENEW 3. **Dual Sequence Number Guarantee**: Global sequence_id + key-level key_sequence_id 4. **Snapshot Integration**: Integrate with existing snapshot mechanism, support OpLog cleanup 5. **Standby Service Runs in Parallel**: Continuously synchronize data during election waiting period 6. **Memory Optimization**: Periodically clean up expired entries in key_sequence_map_ ### Before submitting a new issue... - [ ] Make sure you already searched for relevant issues and read the [documentation](https://kvcache-ai.github.io/Mooncake/)

bsakaguchi added the

good first issue

label

2026-10-29 21:14:07 +00:00

bsakaguchi commented

2026-10-29 21:14:08 +00:00

Author

Owner

@Libotry commented on GitHub (Dec 15, 2025):

1. Problem & Assumptions

1.1 Problem

After a Delete (or eviction) on the primary master:

The primary frees a replica’s memory (returns buffer to allocator’s free list).
The Delete event is not replicated to the standby master.
The primary then crashes; the standby is promoted to new master.
The new master still believes that this replica exists, and returns its address to clients.
That buffer may already have been reused by another object, or may still contain logically deleted data.

We must never return data that belongs to some other key/object/tenant due to buffer reuse, even if we allow some metadata loss.

1.2 Accepted Semantic Constraints

We explicitly accept the following semantics:

Metadata / delete operations may be lost across failover:
- A delete acknowledged by the old master may be “rolled back” after failover.
- That is acceptable because the KV cache can be recomputed.
Hard safety requirement:
- It is strictly forbidden to read data that belongs to another key/object/tenant as if it were the requested key.
- In other words: buffer reuse must not cause cross-key contamination.

Under these constraints, it is acceptable that:

A key that was “deleted” on the old master may reappear after failover (logical delete rolled back).
But it is not acceptable to read someone else’s data due to buffer reuse.

2. Idea

We upgrade each replica from a “raw pointer” into a versioned capability:

In-memory layout of a replica buffer becomes:

The master generates a 64-bit version for each successful Put of a key.
This version is stored:
- In ObjectMetadata on the master.
- In the ReplicaDescriptor returned to clients.
- In the first 8 bytes of the actual buffer in the KV store.
On Get, the client always verifies:
- Read the first 8 bytes of the buffer.
- Compare with the expected version from ReplicaDescriptor.
- If versions match → buffer still belongs to this key/epoch → safe to read payload.
- If versions differ → buffer was reused by someone else → mark this replica invalid, do not use it.

Thus, even if the physical address is reused for a different object, the client will detect it and reject the replica.

3. Data Model Changes

3.1 Version Type

using Version = uint64_t;

Version can be constructed as:

High bits: timestamp (e.g., microseconds since epoch).
Low bits: per-node monotonic sequence ID.

Requirements:

For a single master process, each successful Put for a given key gets a unique, monotonically increasing version.
Version collisions are practically impossible within a process lifetime.

3.2 Replica Descriptor Extension

Extend Replica::Descriptor (or equivalent) to carry version information:

On PutStart, the master generates version, stores it in metadata, and includes it in each replica descriptor.

4. Write Path (Put) Design

4.1 Master: PutStart

Client invokes Put(key, slices, config).
MasterService::PutStart(key, slice_lengths, config):
- Validates input.
- Allocates replicas as it does today (segments, buffers, etc.).
- Generates a new Version version = MakeVersion() for this key.
- Stores version in ObjectMetadata for this key.
- Fills ReplicaDescriptor.version = version for each allocated replica.
- Returns the list of descriptors to the client.

All replicas of the same key for this Put share the same version.

4.2 Client: Writing to Store

We enhance TransferWrite to enforce the following write order per replica:

Write 8-byte version header at buffer_address.
Write payload at buffer_address + 8 for length size.

There are two implementation options:

Option A: Two-step write (simpler):
- First, TE/local memcpy writes the 8-byte version.
- Then, existing TransferWrite writes the payload (slices) starting from buffer_address + 8.
Option B: Single write with reserved header:
- Treat size as header + payload, and always write version || payload in one TE operation.

Option A is recommended initially because it avoids invasive changes to the allocation logic.

5. Read Path (Get) Design

We modify as follows.

5.1 Version Validation Before Payload Read

Given a chosen ReplicaDescriptor with:

version_expected (generated at PutStart).
buffer_address.
size.

The client performs:

Read 8-byte header:

This can be done via TE (small transfer) or via a combined read (see below).

Compare versions:

If version_actual == version_expected:
- The buffer still belongs to this key and this write epoch.
- It is safe to read the payload.
If version_actual != version_expected:
- The buffer was reused by another object, or overwritten by a tombstone, etc.
- Mark this replica as INVALID_REPLICA and try another replica if available.
- If all replicas fail, return an error (INVALID_REPLICA / OBJECT_NOT_FOUND) and let the upper layer recompute.

Read payload:

Implementation detail:

We can extend ReplicaDescriptor with a payload_offset field, or enhance TransferRead to accept an offset.

5.2 Optimization

To minimize RTTs:

Use a single TE read for (8 + payload) bytes.
First examine the first 8 bytes locally:
- If version mismatch → discard payload and mark replica invalid.
- If match → use the rest as the payload.

6. Behavior Under Deletes and Failover

According to the accepted semantic constraints, we do not require writing tombstones at delete time.

6.1 Primary Delete Not Replicated, Memory Not Reused

Old primary:
- Deletes metadata and returns buffer to allocator’s free list.
- Does not write anything to the buffer.
Delete is not replicated to standby; primary then crashes.
New master:
- Still has ReplicaDescriptor with (addr, version) for this key.
The buffer has:
- Header: still the old version.
- Payload: old KV cache data.

Client behavior:

Reads header → version matches → treat buffer as valid.
Reads payload → returns old value.
This is semantically equivalent to: delete never happened.

Since you accept “delete may be lost, old data may reappear”, this is allowed.

6.2 Primary Delete Not Replicated, Memory Reused

Old primary:
- Deletes metadata and frees the buffer.
- Allocates the same address to a different key B.
- Writes a new version_B and new payload for key B.
Neither delete nor new Put is replicated to standby; primary crashes.
New master:
- Still thinks the old key A has replica at that address with version_A.
The buffer now contains:
- Header: version_B.
- Payload: data for key B.

Client behavior:

Reads header:
- version_B != version_A → treat as INVALID_REPLICA.
It will not read payload for this replica.
It may fall back to:
- Another replica of key A (if any).
- Or return an error / object not found.

Thus, we never interpret key B’s data as key A’s data.

7. Failure Model & Safety Guarantees

Under the agreed semantics:

Allowed:
- A key that was deleted on the old primary may appear as “not deleted” after failover (delete lost).
Guaranteed by this scheme:
- A buffer that has been reused for another object will not be interpreted as belonging to the old key, because the version in memory will no longer match the version in ReplicaDescriptor.

This scheme therefore:

Prevents cross-key data contamination caused by buffer reuse.
Accepts that some delete metadata may be lost around failover.
Does not require introducing Raft or a distributed log.

8. Overhead & Implementation Complexity

8.1 Overhead

Write:
- Additional 8-byte write per replica (can be merged with main write).
Read:
- Additional 8-byte compare per replica (can be included in the same TE read).

Compared to typical KV cache object sizes (KB–MB), this overhead is negligible.

8.2 Implementation Complexity

Extend ReplicaDescriptor and related RPC/serialization to carry version.
Generate version in MasterService::PutStart, store in ObjectMetadata.
Update TransferWrite and TransferRead (or a thin wrapper) to:
- Prefix/write version to buffer.
- Validate version before decoding payload.
Update client-side Get and batch-get helpers to respect version validation and error handling.

9. Summary

We introduce an 8-byte version header at the beginning of each replica buffer and carry the same version in ReplicaDescriptor. On Get, the client validates the version in memory against the expected version before reading the payload.
Under the agreed semantic that deletes may be lost across failover but cross-key data contamination is strictly forbidden, this design effectively prevents reading data from a reused buffer that now belongs to another object, while keeping implementation and performance overhead low.

@Libotry commented on GitHub (Dec 15, 2025): ### 1. Problem & Assumptions #### 1.1 Problem After a `Delete` (or eviction) on the primary master: - The primary frees a replica’s memory (returns buffer to allocator’s free list). - The `Delete` event is **not** replicated to the standby master. - The primary then crashes; the standby is promoted to new master. - The new master still believes that this replica exists, and returns its address to clients. - That buffer may already have been **reused by another object**, or may still contain **logically deleted data**. We must **never** return data that belongs to some other key/object/tenant due to buffer reuse, even if we allow some metadata loss. #### 1.2 Accepted Semantic Constraints We explicitly accept the following semantics: - **Metadata / delete operations may be lost across failover**: - A delete acknowledged by the old master may be “rolled back” after failover. - That is acceptable because the KV cache can be recomputed. - **Hard safety requirement**: - It is strictly forbidden to read data that **belongs to another key/object/tenant** as if it were the requested key. - In other words: buffer reuse must not cause **cross-key contamination**. Under these constraints, it is acceptable that: - A key that was “deleted” on the old master may reappear after failover (logical delete rolled back). - But it is **not** acceptable to read someone else’s data due to buffer reuse. --- ### 2. Idea We upgrade each replica from a “raw pointer” into a **versioned capability**: - In-memory layout of a replica buffer becomes: <img width="603" height="119" alt="Image" src="https://github.com/user-attachments/assets/203156cf-6335-4a59-9d0e-f23550872341" /> - The master generates a **64-bit version** for each successful `Put` of a key. - This `version` is stored: - In `ObjectMetadata` on the master. - In the `ReplicaDescriptor` returned to clients. - In the first 8 bytes of the actual buffer in the KV store. - On **Get**, the client always verifies: - Read the first 8 bytes of the buffer. - Compare with the expected version from `ReplicaDescriptor`. - If versions match → buffer still belongs to this key/epoch → safe to read payload. - If versions differ → buffer was reused by someone else → mark this replica invalid, do not use it. Thus, even if the physical address is reused for a different object, the client will detect it and reject the replica. --- ### 3. Data Model Changes #### 3.1 Version Type ```cpp using Version = uint64_t; ``` Version can be constructed as: - High bits: timestamp (e.g., microseconds since epoch). - Low bits: per-node monotonic sequence ID. Requirements: - For a single master process, each successful `Put` for a given key gets a **unique, monotonically increasing** version. - Version collisions are practically impossible within a process lifetime. #### 3.2 Replica Descriptor Extension Extend `Replica::Descriptor` (or equivalent) to carry version information: On `PutStart`, the master generates `version`, stores it in metadata, and includes it in each replica descriptor. --- ### 4. Write Path (Put) Design #### 4.1 Master: PutStart 1. Client invokes `Put(key, slices, config)`. 2. `MasterService::PutStart(key, slice_lengths, config)`: - Validates input. - Allocates replicas as it does today (segments, buffers, etc.). - Generates a new `Version version = MakeVersion()` for this key. - Stores `version` in `ObjectMetadata` for this key. - Fills `ReplicaDescriptor.version = version` for each allocated replica. - Returns the list of descriptors to the client. All replicas of the same key for this `Put` share the same version. #### 4.2 Client: Writing to Store We enhance `TransferWrite` to enforce the following **write order** per replica: 1. Write **8-byte version header** at `buffer_address`. 2. Write **payload** at `buffer_address + 8` for length `size`. There are two implementation options: - **Option A: Two-step write** (simpler): - First, TE/local memcpy writes the 8-byte version. - Then, existing `TransferWrite` writes the payload (`slices`) starting from `buffer_address + 8`. - **Option B: Single write with reserved header**: - Treat `size` as `header + payload`, and always write `version || payload` in one TE operation. Option A is recommended initially because it avoids invasive changes to the allocation logic. --- ### 5. Read Path (Get) Design We modify as follows. #### 5.1 Version Validation Before Payload Read Given a chosen `ReplicaDescriptor` with: - `version_expected` (generated at PutStart). - `buffer_address`. - `size`. The client performs: 1. **Read 8-byte header**: This can be done via TE (small transfer) or via a combined read (see below). 2. **Compare versions**: - If `version_actual == version_expected`: - The buffer still belongs to this key and this write epoch. - It is safe to read the payload. - If `version_actual != version_expected`: - The buffer was reused by another object, or overwritten by a tombstone, etc. - Mark this replica as `INVALID_REPLICA` and try another replica if available. - If all replicas fail, return an error (`INVALID_REPLICA` / `OBJECT_NOT_FOUND`) and let the upper layer recompute. 3. **Read payload**: Implementation detail: - We can extend `ReplicaDescriptor` with a `payload_offset` field, or enhance `TransferRead` to accept an offset. #### 5.2 Optimization To minimize RTTs: - Use a single TE read for `(8 + payload)` bytes. - First examine the first 8 bytes locally: - If version mismatch → discard payload and mark replica invalid. - If match → use the rest as the payload. --- ### 6. Behavior Under Deletes and Failover According to the accepted semantic constraints, we do **not** require writing tombstones at delete time. #### 6.1 Primary Delete Not Replicated, Memory Not Reused - Old primary: - Deletes metadata and returns buffer to allocator’s free list. - Does **not** write anything to the buffer. - Delete is not replicated to standby; primary then crashes. - New master: - Still has `ReplicaDescriptor` with `(addr, version)` for this key. - The buffer has: - Header: still the **old version**. - Payload: old KV cache data. Client behavior: - Reads header → version matches → treat buffer as valid. - Reads payload → returns **old value**. - This is semantically equivalent to: **delete never happened**. Since you accept “delete may be lost, old data may reappear”, this is **allowed**. #### 6.2 Primary Delete Not Replicated, Memory Reused - Old primary: - Deletes metadata and frees the buffer. - Allocates the same address to a different key B. - Writes a **new version_B** and new payload for key B. - Neither delete nor new Put is replicated to standby; primary crashes. - New master: - Still thinks the old key A has replica at that address with `version_A`. - The buffer now contains: - Header: `version_B`. - Payload: data for key B. Client behavior: - Reads header: - `version_B != version_A` → treat as `INVALID_REPLICA`. - It will **not** read payload for this replica. - It may fall back to: - Another replica of key A (if any). - Or return an error / object not found. Thus, we **never** interpret key B’s data as key A’s data. --- ### 7. Failure Model & Safety Guarantees Under the agreed semantics: - **Allowed**: - A key that was deleted on the old primary may appear as “not deleted” after failover (delete lost). - **Guaranteed by this scheme**: - A buffer that has been reused for another object **will not** be interpreted as belonging to the old key, because the version in memory will no longer match the version in `ReplicaDescriptor`. This scheme therefore: - Prevents **cross-key data contamination caused by buffer reuse**. - Accepts that some delete metadata may be lost around failover. - Does not require introducing Raft or a distributed log. --- ### 8. Overhead & Implementation Complexity #### 8.1 Overhead - **Write**: - Additional 8-byte write per replica (can be merged with main write). - **Read**: - Additional 8-byte compare per replica (can be included in the same TE read). Compared to typical KV cache object sizes (KB–MB), this overhead is negligible. #### 8.2 Implementation Complexity - Extend `ReplicaDescriptor` and related RPC/serialization to carry `version`. - Generate version in `MasterService::PutStart`, store in `ObjectMetadata`. - Update `TransferWrite` and `TransferRead` (or a thin wrapper) to: - Prefix/write version to buffer. - Validate version before decoding payload. - Update client-side `Get` and batch-get helpers to respect version validation and error handling. --- ### 9. Summary > We introduce an **8-byte version header** at the beginning of each replica buffer and carry the same version in `ReplicaDescriptor`. On Get, the client validates the version in memory against the expected version before reading the payload. > Under the agreed semantic that deletes may be lost across failover but cross-key data contamination is strictly forbidden, this design effectively prevents reading data from a reused buffer that now belongs to another object, while keeping implementation and performance overhead low.

bsakaguchi commented

2026-10-29 21:14:08 +00:00

Author

Owner

@ykwd commented on GitHub (Dec 16, 2025):

Thanks for sharing the proposal. Unfortunately, this approach is not safe and does not actually guarantee the hard safety requirement you described, for two reasons:

First, RDMA reads and writes do not provide ordering and atomicity guarantees, which breaks the version-only validation scheme. In your design, correctness relies on the assumption that the first 8 bytes (the version) and the payload are written and observed atomically and in order. That assumption does not hold.

Second, the allocator does not guarantee alignment between successive allocations, which makes the embedded-version assumption invalid. Your scheme assumes that when a buffer is freed and later reused, the next allocation will reuse the same start address and layout, so that the version stored in the first 8 bytes corresponds exactly to the logical object boundary.

@ykwd commented on GitHub (Dec 16, 2025): Thanks for sharing the proposal. Unfortunately, this approach is not safe and does not actually guarantee the hard safety requirement you described, for two reasons: First, RDMA reads and writes do not provide ordering and atomicity guarantees, which breaks the version-only validation scheme. In your design, correctness relies on the assumption that the first 8 bytes (the version) and the payload are written and observed atomically and in order. That assumption does not hold. Second, the allocator does not guarantee alignment between successive allocations, which makes the embedded-version assumption invalid. Your scheme assumes that when a buffer is freed and later reused, the next allocation will reuse the same start address and layout, so that the version stored in the first 8 bytes corresponds exactly to the logical object boundary.

bsakaguchi commented

2026-10-29 21:14:08 +00:00

Author

Owner

@github-actions[bot] commented on GitHub (Jun 10, 2026):

This issue has had no activity for 90 days and will be closed in 7 days if there is no further activity. Please comment or react if it should stay open.

@github-actions[bot] commented on GitHub (Jun 10, 2026): This issue has had no activity for 90 days and will be closed in 7 days if there is no further activity. Please comment or react if it should stay open.

bsakaguchi commented

2026-10-29 21:14:08 +00:00

Author

Owner

@github-actions[bot] commented on GitHub (Jun 18, 2026):

Closing due to 3 months of inactivity. If this is still relevant, please comment and we can reopen.

@github-actions[bot] commented on GitHub (Jun 18, 2026): Closing due to 3 months of inactivity. If this is still relevant, please comment and we can reopen.

bsakaguchi referenced this issue

2026-10-29 21:28:21 +00:00

[PR #408] [MERGED] [Fix] Store Metrics-related Bugs #1549