Replicated, Highly-Available Data Store (OMNeT++ Simulation)

This project is an OMNeT++ simulation of a distributed key-value store that provides high availability and causal consistency. The system is designed to tolerate message loss and network delays while ensuring a consistent view of the data.

The implementation successfully achieves its core goals through:

• Asynchronous Replication: Allowing servers to accept writes even when partitioned, ensuring high availability.
• Vector Clocks: Enforcing a causal ordering on all update operations.
• Last-Writer-Wins (LWW) Conflict Resolution: Deterministically resolving concurrent writes.
• Gap-Repair Protocol: Robustly handling message loss through an anti-entropy mechanism with exponential backoff.

---

Contents

• System Architecture
• Assumptions
• Causal Consistency & Replication
• Fault Tolerance: Handling Message Loss
• Concurrency Scenarios
• Running the Simulation
  • Configuration (omnetpp.ini)
  • Simulation Output

---

System Architecture

Topology

The network topology is fully configurable through the omnetpp.ini file. By default, it consists of 4 fully-meshed servers and 8 clients, with 2 clients permanently connected ("sticky") to each server. This can be easily scaled to simulate larger or smaller systems.

Client Module

• Generates a random workload of PUT (~60%) and GET (~40%) requests.
• The workload can be time-limited (stopAfter) or operation-limited (maxOps).
• Can be scripted to send specific sequences of operations to demonstrate consistency and concurrency scenarios.

Server Module

• Storage: Maintains a per-key, append-only history of all versions.
• Replication Model: The system uses asynchronous broadcast replication. When a server receives a PUT from a client:
  1. It immediately applies the write to its local data store.
  2. It then broadcasts an UPDATE message to all peer servers.
• This model ensures that client PUT operations are fast and are not blocked by network latency, fulfilling the high-availability requirement.

---

Assumptions

• Omission failures only: Messages may be lost or reordered.
• Sticky Clients: Clients remain connected to the same server for their lifetime.
• Reliable Nodes: Clients and servers themselves do not crash.

---

Causal Consistency & Replication

Vector Clocks

Causal consistency is enforced using vector clocks. Every server maintains a vector clock seen[] of size N (where N is the number of servers), representing the number of updates it has seen from each peer.

An UPDATE message from a source server src with a vector clock V can only be delivered by a receiving server if both of the following causal pre-conditions are met:

1. V[src] == seen[src] + 1 (It is the very next update expected from that source).
2. V[k] <= seen[k] for all other servers k != src (The receiver has seen all the prerequisites that the sender had seen).

If these conditions are not met, the update is buffered until the missing dependencies are fulfilled.

Conflict Resolution: Last-Writer-Wins (LWW)

When concurrent writes to the same key occur during a network partition, a conflict arises. Our system resolves these conflicts using a deterministic Last-Writer-Wins (LWW) strategy.

When a GET request is processed, the server examines the key's version history and identifies the "winning" version by sorting all versions and selecting the latest one according to the following ordered criteria:

1. The version with the highest clientTs (client timestamp).
2. If timestamps are equal, the version from the server with the higher src ID.
3. If both are equal, the version with the higher opId.

This ensures that all servers will eventually converge on the same value for any given key once they have received the same set of updates.

---

Fault Tolerance: Handling Message Loss

The system is resilient to message loss (omission failures) using a gap-detection and repair protocol.

If a server B receives an UPDATE from server A that it cannot yet deliver (due to missing causal dependencies), it:

1. Buffers the out-of-order update in a pending queue.
2. Sends GAPREQ messages to the appropriate servers to request the missing update ranges:
   • Direct Gaps: Asks server A for the sequence [seen[A]+1 .. V[A]-1].
   • Transitive Gaps: For any other server k where V[k] > seen[k], it asks server k for the sequence [seen[k]+1 .. V[k]].
3. Arms a retry timer with exponential backoff (1s, 2s, 4s, …) for each source it is waiting on. This anti-entropy mechanism ensures eventual delivery without flooding the network with redundant requests.

---

Concurrency Scenarios

The model is designed to explore complex distributed systems dynamics:

• Concurrent PUTs: When different servers receive PUTs for the same key, vector clocks ensure every server eventually stores both versions in a causally consistent order. The LWW rule determines which value is returned on a GET.
• Loss + Concurrency: If s2 misses an update from s1 while s3 receives a different update, s2 and s3 may end up with incomparable vector clocks. The gap-repair logic robustly requests the exact missing ranges from the correct sources, allowing the buffers to eventually drain and the system to converge.

---

Running the Simulation

Configuration (omnetpp.ini)

Key simulation parameters can be configured in the .ini file:

Module	Parameter	Type	Default	Meaning
Client	plot_enabled	bool	false	If true, runs plotting scripts at the end for that client.
Client	stopAfter	double	-1	Stop random workload after this many seconds (if ≥ 0).
Client	maxOps	int	-1	Stop random workload after this many ops (if ≥ 0).
Client	keySpace	int	10	Size of the keyspace for random put and get.
Server	plot_enabled	bool	false	If true, runs plotting scripts at the end for that server.
Server	lossProb	double	0.1	Probability to drop any incoming message.
Server	serverNum	int	4	Total number of servers.
Server	clientGateCount	int	2	Total number of clients per server.
-	pythonCmd	string	optional	Path to Python interpreter.
-	seed-set	int	optional	Seed of the random simulation.

Simulation Output

The simulation produces .csv data files in the results/ folder and can generate plots to visualize the results.

• Data Files:
  • results/client_ops/: Records put, get, hit, and miss counts for each client.
  • results/puts_by_key/: Records the number of puts per key for each client.
  • results/puts_per_key/: Records the number of puts per key stored at each server.
  • results/plots/:
    • client_ops_summary.png: plot of the number of put and get requests from each client
    • puts_by_key_c*.png: plot of the number of puts per each key from client c*
    • res_accesses_s*.png: plot of the number of put requests for each key in the server s*
• Plots scripts:
  • plot_client_ops.py: called by the client, plots the data from each client_ops_c*.csv into client_ops_summary.png
  • plot_key_puts.py: called by the client c* if plot_enabled is true, generate the puts_by_key_c*.png plot by using each puts_by_key_c*.csv file
  • plot_res_accesses.py: called by the server s* if plot_enabled is true, generate the res_accesses_s*.png plot by using each puts_per_key_s*.csv file

The following plots were generated from a sample run with seed-set = 2 = 10, **.maxOps = 10, **.lossProb = 0.1 and **.keyspace = 10: