Thursday, August 24, 2017

We continue discussing the ZooKeeper. It is a co-ordination service with elements from group messaging, shared registers and distributed lock services. It provides a interface that guarantees wait-free property and FIFO execution of requests from each client.  Requests across all clients are also linearized.
We were discussing the throughput of ZooKeeper when the system is saturated and changes on various injected failure. A large number of clients connected and this number was kept the same while the servers were varied. This simulated a large load and it was seen that the number of servers had a negative impact on performance. Read throughput is consistently higher than write throughput.Write requests had to go through atomic broadcast. Transactions are logged to non-volatile store. These contribute to the difference in throughput.
In production systems, some performance is traded off for reliability especially because ZooKeeper is the source of truth for applications. More servers are used to tolerate more faults and partition write throughput. Load can be distributed because ZooKeeper has relaxed consistency guarantee. If all the requests were to be directed towards the leader, the read throughput goes down and even the write throughput is lower. This can be explained as the diminished ability of the leader to perform the atomic broadcast operations while servicing all requests. In fact, atomic broadcast is the only true limiting factor for the ZooKeeper. To measure this, the requests are all directed towards the leader  and the system is saturated. The broadcast protocol becomes CPU bound at maximum throughput  It is not the same as the performance with all write requests because some work goes towards client communication, ACL checks and transaction conversions.As mentioned earlier, some performance is traded off in favor of correctness and reliability but that said the authors stated that there is room for improvement with elimination of extra copies, multiple serializations and efficient internal data structures.
The experiments performed by the authors also included injecting failures such as killing server processes. For this the write requests were maintained at 30%.  It was seen that the throughput tanked for failure and recovery of a follower, failure and recovery of a different follower, failure of the leader, failure of the two followers in the first two marks and recovery at the third mark, and recovery of the leader. The most dip in throughput occurred with the failures of the leader. On the other hand, failure of the followers is tolerated with a quorum and therefore the throughput falls only as much as the failing read requests Also the leader election algorithm helps mitigate this further. Third even if the followers take more time to recover, ZooKeeper is able to raise the throughput with the distribution of the load after recovery.

#codingexercise
Given a list of 1s and 0s and an integer m, find the positions of upto m zeros which when flipped gives the maximum contiguous 1s.

void PrintPositions(List<int> A, int m)
{
// sliding window boundaries
int l = 0;
int r = 0;
// solution involving best size and boundaries
int best = INT_MIN;
int start = 0;
int end = 0;
// count of zeros
int c = 0;
while (r < A.Count)
{
if ( c <= m)
{
   r++;
   if (A[r] == 0) c++;
}
if (c > m)
{
   if (A[l] == 0) c--;
   l++;
}
if ( r - l > best)
{
best = r - l;
start = l;
end = r;
}
}
if ( best > INT_MIN)
{
   Console.WriteLine();
   for (int i = start; I <= end; I++)
        if (A[I] == 0)
            Console.Write("{0} ", i);
   Console.WriteLine();
}
}

In the above sliding window, we can also eliminate one of the best, start and end variables.

No comments:

Post a Comment