Home
M. Berti, A. Cesco, and S. Fiorilla
RaftShop is an implementation of a distributed e-commerce store based on the Raft consensus algorithm. RaftShop is implemented using the Jolie language and it has been created as part of the final examination for the Operating Systems course, Autumn 2017; a second-year course of the Information Science for Management bachelor degree at the Department of Computer Science and Engineering, Università di Bologna.
Goal of the project is to maximise concurrency in the distributed system, while maintaining consistency of data among a cluster of servers. Fault-tolerance is guaranteed by the Raft algorithm. Besides the technical details illustrated below, the main interesting feature of RaftShop is that it is implemented as a microservice architecture. To do this, we took advantage of some primitives provided by the Jolie language; namely, dynamic binding of ports and addresses and service embedding. The project also comprises a web-based GUI for both the customers of the e-commerce (Clients) and the shop administrators (Admins). RaftShop is distributed as an open-source project under the LGPL license.
Raft is a distributed consensus algorithm based on the replication of a log. It produces a result equivalent to the renowned Paxos algorithm, with analogous efficiency but increased understandability, providing a better foundation for building practical systems. To enhance understandability, Raft separates the key elements of consensus, such as leader election, log replication, and safety, and it enforces a stronger degree of coherency to reduce the number of system states that must be considered. Raft has several novel features which make it distinguishable from other consensus algorithms, two above all:
- strong leader, a stronger form of leadership than other consensus algorithms, e.g., log entries only flow from the leader to other servers;
- leader election, Raft uses randomized timers to elect a leader. This adds only a small amount of logic to the heartbeats already required for any consensus algorithm, while resolving conflicts simply and rapidly.
For a comprehensive introduction to the Raft algorithm, please refer to the official presentation paper by Ongaro and Ousterhout.
RaftShop mainly consists in four Jolie microservices: Client, Admin, Server, and Network Visualizer. Client and Admin model the behaviour respectively of a user and a vendor. The Network Visualizer is an administrative tool displaying both the status of the shop and of the Servers (liveness, leadership, etc.). A Server handles the resources of the shop (items and carts), accepting requests to manipulate them, also taking care of status replication following the Raft algorithm. Our implementation assumes the presence of five servers, one network Visualizer and an unlimited number of Clients and Admins. Note, although we assume the presence of five server, thanks to Raft our system can reliably run, store, and replicate information with at least three live servers.
From a software engineering point of view, the Servers in RaftShop comprise two distinct modules: one that executes Raft and the other, called DataManager, which manages the processing of orders (management of stocks, purchases, etc.). Following the leader model of Raft, a client (or admin) submits a request to one of the servers. If the recipient of the request is not the leader, it will respond with the leader address. Dually, when the client receives a server's address as a response, it automatically re-sends its request to the leader. Concretely, we used Jolie dynamic binding to rebind a client to the correct (leader) server in a quick and structured way. This is also an optimisation from an architectural standpoint: once the port of the client has been updated to contact the current leader, all subsequent requests (until the fall of that leader) will be addressed directly to the leader, without requiring additional probing on the followers.
When an order is sent to the leader, the Raft data replication protocol begins. At system level, an order is executed by DataManager of all servers only after the leader knows it has been safely replicated by all followers. The internal service DataManager manages the execution of orders on the replicated state of the shop, supporting parallel readings and writings. The processing of orders through RaftShop is independent from one another, guaranteeing a high degree of concurrency in the system.
While dynamic binding could have been used also to implement the Raft algorithm --- i.e., in such a way that each server had just one binding (a port, in Jolie terms), rebound to contact each server. However we chose to define a specific port for each server so that each one-to-one interaction among servers could happen in parallel, avoiding evident bottlenecks due to the presence of only on communication channel available at a time. Thus, in any RaftShop server we send log entries from the leader to the followers using four dedicated ports. Following Raft, each server embeds a set of timers, each dedicated to the interaction with another specific server, governing Raft execution. Even if it is possible implement the algorithm using only two timers (for election and log replication respectively), embedding a set of timers for each server provides a higher degree of concurrency.
Notable feature of our implementation of RaftShop is that, since we separated the logic of replication (Raft) and the logic of the shopping (DataManager), other developers can easily reuse our project to implement Raft-based replication systems just by changing the logic (and the interface of interaction) of the DataManager, leaving the sub-services implementing Raft untouched.
To maintain a high degree of parallelism and to prevent race conditions due to the concurrent handling of orders, our implementation of the leader uses a set of semaphores --- each one with a unique name --- used as services.
To guarantee uniqueness of semaphore names, we use Jolie "new" construct, which generates unique identifiers for sessions (e.g., cookie identifiers), database entries, etc. Thanks to semaphores, at runtime RaftShop automatically linearises the handling of orders, which follow a queue-like behaviour. When a Client (Admin) sends a request to the leader, that request creates a new semaphore and locks its response to the requester until the entry is safely committed; after the commit the semaphore is released, enabling the delivery of the response. This expedient constitutes an important optimisation for RaftShop, where more than one order can be replicated within the same replication cycle, although preserving the FIFO order linearised at runtime by the semaphores. Another improvement to concurrency regards request handling: the leader checks the nature of every request and, if it does not trigger any state change (e.g., a request for the list of items in the shop), it is sent directly to the DataManager. As expected, read-only requests are not replicated as Raft log entries.
As mentioned, the DataManager is the a microservice embedded within each server, responsible for the execution of orders. Technically, it contains dynamic lists of items and shopping carts, accessed concurrently. Concurrent access to resources of the DataManager is regulated following the renowned readers-writers solution, as described in Dijkstra's "Solution of a problem in concurrent programming control". In addition, our implementation takes advantage of the presence of two lists: we associate with each of them a lock for reading and a lock for writing, enabling independent access to each list when orders affect only one of the two. For example, it is possible to concurrently create a new cart (which entails no consequences on the items list), while updating the items list by adding new stocks into it. In accordance to Dijkstra's solution, lists support the concurrent execution of multiple readings, while allowing only one writing at a time.
RaftShop Servers are very similar to each other. Indeed they share the most part of their code, beside some distinctive settings regarding their deployment. Thanks to Jolie source inclusion construct "include" the code structure of Servers is divided into a shared part, which corresponds to the RaftShop behaviour implementation, and a distinctive part, which defines dedicated inbound and outbound ports. Concretely, the structure of a Server is summarised as
include "header.iol"
// input Ports
// output Ports
include "main.iol"
where "header.iol" and "main.iol" respectively contain constants and variables common to all Servers and the implementation of the behaviour of a RaftShop server.