-
Notifications
You must be signed in to change notification settings - Fork 3
Home
RaftShop is an implementation of a distributed e-commerce store based on the [Raft consensus algorithm] (https://raft.github.io/) in the [Jolie language] (http://www.jolie-lang.org/) created for the Operating Systems course at Unibo. The goal of the project is to maximise concurrency in the distributed system while mantaining correctness even in the most improbabale scenarios. Fault-tolerance is guaranteed by Raft. The implementation takes advantage of many of Jolie's features, including most notably a microservice architecture, the possibility of dynamic binding between ports and addresses and the use of code referencing other code. An online GUI is present for Client and Admin.
Raft is a distributed consensus algorithm based on the replication of a log. It produces a result equivalent to Paxos, and it is as efficient as Paxos, but it is more understandable and also provides a better foundation for building practical systems. In order 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 states that must be considered. Results from a user study demonstrate that Raft is easier for students to learn than Paxos. Raft has several novel features which makes it distiguishable from other consensus algorithms, such as: strong leader (a stronger form of leadership than other consensus algorithms. For example, log entries only flow from the leader to other servers); leader election (Raft uses randomized timers to elect leaders. This adds only a small amount of mechanism to the heartbeats already required for any consensus algorithm, while resolving conflicts simply and rapidly).
RaftShop is made up by four distinct subjects: Client, Admin, Server and Network Visualizer. Client and Admin model the figures respectively of an user and a vendor, Network Visualizer is an administrative tool that displays the shop's status and Server is responsible for the interactions. The implementation offers five servers, one network Visualizer and unlimited clients and admins. Servers are made up of tho distinct modules: one that executes Raft and another one, called DataManager which manages the application of the entries on state machine. A client (or an admin) submits its request to one of the servers: if it's not the leader, the replay is leader's address and client starts another connection to the leader bringing the same request using dynamic binding to change output port's address without changing the port itself. When a request is sent to the leader, the Raft algorithm begins and only when the former is safely committed is sent another request to the internal DataManager. DataManager provides the execution of the instruction in client's request on the state machine, and supports parallel reading and writing. A request's process through Raft is totally independent from another's execution, thus allowing a significant improvement on system's degree of concurrency. During the execution of Raft dnamic binding is not used because it would mean lower the parallelism of the system: e.g. use one port with dynamically changing address to send log entries from the leader to followers leads to a sequential sending of requests, while the use of four output ports allows the leader to send in parallel the requests. In each server are embedded a series of five governing the execution of Raft, e.g. ElectionTimer. Even if it is possible implement the algorithm using only two timers (for election and log replication respectively), embedding a timer for each follower allows, as above, a higher level of concurrency. ![A graphic representation of RaftShop's architecture] (/path/image.png)
To mantain an high degree of parallelism without losing sense in the response to a client, the leader contains a list of semaphores - each one with an unique mane, thanks to the "new" feature of Jolie which allows the creation of a unique string - which creates a queue-like behaviour in the response of the client. When a client request is sent to leader, it creates a new semaphore and locks its response to the client until that entry is safely committed, when it's performed a release operation on the semaphore. This allows RaftShop to have more than one entry in replication, but to send responses in FIFO order. Another improvement to concurrency is present at the moment when request arrive: the leader cheks the nature of every request and, if it's a read-only one (e.g. asks the list of items in the shop), that one is sent directly to DataManager without entering in Raft algorithm, because it does not change any data.
DataManager is the microservice responsible for the execution of instruction on the machine. It contains dynamic lists of items ans carts. Its access is concurrent and it is regulated following the reading-writing problem's solution as known in literature, with a little improvement that takes advantage of the use of two lists: every list has a lock for reading and a lock for writing, allowing concurrent access in situation where the known solution does not, e.g. it is possible to concurrenty write in carts' list and in items' list. In accordance with known solution, for each list multiple reading are allowed but only one writing at a time.
Server's code differs one from another only for a little part, the declaration of ports and the initialization. This can lead to a lot of replicated code in each file, but Jolie's feature include allows to avoid this problem. The code referring to the initial and the main part is written in two separate files (header.iol and main.iol respectively) and included in the code with include.