Seminar 7: Quorum for consistency in distributed systems
Goal: To study and practice the concept of Quorum for consistency
Background: What happens if one server can't handle serving all of your customers any longer? The apparent solution is to increase the number of servers and employ the majority method to ensure consistency. But, even if you purchase a million servers, a client will still need to make requests to many of them to increase fault tolerance and double the efficiency.(Availability)
But how can we be sure we are doing this in a consistent manner?
Quorum in a distributed system is the minimal number of replicas on which a distributed operation (commit/abort) must be completed before the operation can be declared successful. In systems with multiple replicas there is a possibility that the user reads inconsistent data. For example there are 3 replicas, A, B and C in a cluster and a user writes value v1 to node A and then another user reads from node B or C which is still behind A and thus will not have the value v1, so the second user will not get the consistent state of data.
But this is what happens in the nodes with the quorum mechanism.
Quorum-based protocols
- Resolves write-write or read-write conflicts
- Client processes are required to request and acquire the permission of multiple servers before reading and writing a replicated data item.
- Example protocol (on a distributed file system):
- A process that wants to update a replicated file first contacts at majority of servers and get them to agree to do the update.
- Once they agree, the file is changed and a new version number is associated with the file.
- To read a replicated file, a client must also contact at least half the servers plus one and ask them to send the version numbers associated with the file.
- If all version numbers agree then the file is the most recent one.
- Gifford’s scheme for N replicas
- Read quorum: client needs permission from arbitrary Nr servers - Prevents read-write conflicts
- Write quorum: client needs permission from arbitrary Nw servers - Prevents write-write conflicts
- Conditions that must be met: If a given data item has a total number of N replicas then
- Nr + Nw > N
- Nw > N/2
N.B Usually there is more than half of the number of nodes in cluster. (N/2 + 1)
Examples:
Exercise Given below are the N, Nr, Nw, Where N denotes the total number of replica servers available; Nr denotes the read quorum and Nw denotes the write quorum. Against each, denote whether the combination is a correct choice or not using above mentioned constraints:
1. N = 5 , Nr = 2 , Nw = 4
2. N = 16 , Nr = 8 , Nw = 10
3. N = 16 , Nr = 9 , Nw = 8
4. N = 10 , Nr = 1 , Nw = 10
5. N = 11 , Nr = 4 , Nw = 5
6. N = 20 , Nr = 6 , Nw = 11
Deliverables of practical session: A PDF file containing the answers to above exercise and show workings or reasons