Project for Distributed Systems (Politecnico di Milano, 2022-2023)

Quorum-based replicated datastore

This is the Omnet++ implementation of a distributed key-value datastore that accepts two operations from clients:

• put ( k, v )   insert/update value v for key k;
• get ( k )   get the value associated with key k (or NULL if the key is not present).

The store is internally replicated across N nodes (processes) and offers sequential consistency using a quorum-based protocol.

Modules

The modules defined in replication.ned are:

• replica
• client

Channels

Each client is connected to each replica through the following channels:

• C50: delay = 50ms, datarate = 100Mbps
  
• C500: delay = 500ms, datarate = 100Mbps

The default channel used is C50, however both client0 and client2 have channel of type C500 to connect to R3 and R4.

Parameters

• read_quorum
• write_quorum
• plot_enabled to allow for automatic data plotting at the end of the simulation

Assumptions

• reliable processes and links
• no network partitions
• FIFO channels

Concurrency

Example of read-write concurrency:
client2   put ( 3, Paris )
client4   get ( 3 )

Example of write-write concurrency:
client1   put ( 7, Venice )
client4   put ( 7, Milan )

To solve the concurrency problem, we implemented locking, since it ensures exclusive access to a resource for a write operation (put) and is released when the operation is completed.

• PUT
  • request lock
  • if lock granted, perform put
  • release lock
    
• GET
  • if resource is unlocked, perform get
    

Versioning

A slow put can potentially overwrite a new value with an old one.
For example:
client0   put ( 3, Paris )
client1   put ( 3, Singapore )

To avoid this problem, versioning has been implemented: replicas also stores the version of the data.

• PUT
  • client must include the version in the message
• GET
  • replicas also return the version

Update: read-repair

When a client performs a get, reaches the quorum on the value to read and detects some stale responses, it sends the new value to the replicas that are not up-to-date.
Please note that the replica updates the data only if the value is more recent (i.e. higher version).

Data collected

Data collected during the simulation are stored in the results/ folder.
A vector stores the time to lock a resource. Other data collected are stored in the following folders:

• results/client/
  • client_operations.csv stores the number of put, get and refused operations per client
  • the log files of all clients track the messages sent and received, and the reached quorum
• results/replica/
  • accesses folder contains the .csv files storing the number of accesses per resource
    
  • logs folder contains log files showing the evolution of the database of each replica
• results/plots/
  • client_operations.png is the plot of the number of operations per client
  • res_accesses.png is the plot of the number of accesses per resource (one plot per replica)

Plots

It is possible to enable the plotting of collected data on a bar chart by setting the 'plot_enabled' parameter. This setting will automatically trigger the execution of the following python files at the end of the simulation:

• plot_client_operations.py: number of operations per client
• plot_res_accesses.py: number of accesses per resource

Please note that different replicas can have different number of accesses per resource, since a resource can be locked on a replica for a long time, causing the rejection of other operations.