Sorock Multi-Raft Implementation

You can estimate the efficiency gain of heartbeat multiplexing based on the number of nodes, shards, and replication factor.

Given:

• $N$: Total number of nodes
• $L$: Total number of shards
• $K$: Replication factor per shard

The Logic:

1. The total number of heartbeats sent in a period is $L imes K$.
2. The total number of directed paths connecting two nodes is $N(N-1)$.
3. Assuming heartbeats are evenly distributed across these paths, the number of heartbeats sent per path is $\frac{LK}{N(N-1)}$.

Example Calculation: If you have 5 nodes, 1000 shards, and a replication factor of 3: $$\text{Reduction Rate} = \frac{1000 \times 3}{5(5-1)} = \frac{3000}{20} = 150$$

A reduction rate of 150 means the multiplexing optimization reduces the heartbeat RPC load by a factor of 150.

Sorock implements in-process multi-raft, which allows you to run multiple independent Raft processes within a single gRPC server process.

This approach addresses scalability issues found in naive Raft implementations (where all operations are serialized) and deployment complexities found in independent cluster deployments. By using in-process multi-raft, you can:

1. Scale via Sharding: Distribute keys across multiple Raft clusters (shards) to handle operations concurrently.
2. Efficient Resource Sharing: Multiple Raft processes can share the same underlying resources (like IP addresses, ports, and embedded datastores) within the same process, enabling efficient I/O and write batching.
3. Simplified Deployment: Avoid the need to allocate unique network identities (IPs/ports) for every individual shard/node.

In Sorock's Multi-Raft implementation, shards process write requests independently. To avoid the high overhead of performing a separate storage transaction for every single shard's log entry, Sorock uses a batched write optimization.

How it works:

1. Virtual Logs: Instead of writing directly to a physical log, each shard maintains a virtual log.
2. Shared Queue: Entries from these virtual logs are temporarily queued in a shared queue.
3. Single Transaction: A background process (the Reaper) pulls entries from the queue and processes them in a single, unified transaction to the underlying redb::Database.

This mechanism is designed to increase system throughput by reducing the total number of transactions required, while minimizing the latency impact typically associated with batching.

The Log is a critical data structure for managing the sequence of operations in the Raft process. Entries in the log exist in several states:

• Applied Entries: Entries that have already been used to update the application state (e.g., the 'lastly applied entry').
• Unapplied Entries: Entries with an index higher than the last applied entry. These may be either committed or uncommitted.
• Snapshot Entries: A special entry in the log that points to a snapshot in the snapshot repository. This allows the log to be compacted by replacing a range of entries with a single snapshot reference.
• Garbage Collected Entries: Old log entries that are removed from the log once they are safely represented by a snapshot, or when they are no longer needed for consistency.

In Sorock, cluster bootstrapping is the process of initializing a Raft cluster from an empty state.

When a node receives an AddServer command and determines that the cluster is currently empty, that node attempts to form a new cluster consisting solely of itself. This process triggers a self-election, causing the node to immediately become the cluster leader.

Sorock manages cluster membership changes using the single server change approach. This method treats membership changes as extensions of the normal log replication mechanism by using specific commands to add or remove Raft processes.

To modify the cluster, an admin client must send AddServerRequest or RemoveServerRequest messages to the cluster leader. These commands specify the target shard and the unique identifier of the server being added or removed.

message AddServerRequest {
  uint32 shard_id = 1;
  string server_id = 2;
}

message RemoveServerRequest {
  uint32 shard_id = 1;
  string server_id = 2;
}

In Multi-Raft environments, a naive implementation where every shard leader sends independent heartbeats to followers creates significant RPC load.

Heartbeat Multiplexing optimizes this by reducing the number of RPC messages through a Mux/Demux pattern:

1. Multiplexer (Mux): Installed on the source node. It buffers heartbeats from different shard leaders and bundles them into a single batched RPC sent to the destination node.
2. Demultiplexer (Demux): Installed on the destination node. It receives the batched RPC, splits it back into individual heartbeats, and routes them to the correct local processes.

This pattern transforms multiple independent network paths into a single batched communication path per node pair, significantly reducing network overhead.

In the Sorock Raft process, RaftApp serves as the primary abstraction representing both the application state and the snapshot repository. Because the application state and its snapshots are strongly coupled, they are managed together within this single structure.

Key behaviors of RaftApp:

• State Updates: The application state is updated by applying entries from the Raft Log.
• Snapshot Generation: RaftApp can generate snapshots at any time to compact the log. When a snapshot is created and stored in the snapshot repository, an internal thread automatically updates the log by replacing the snapshot entry with the new snapshot index.
• Snapshot Recovery: If a node falls significantly behind the leader and the leader has already garbage-collected the necessary log entries, RaftApp can fetch snapshots from other nodes to catch up.