We continue to discuss ZooKeeper which is a wait free coordination for Internet scale systems. It allows distributed processes to co-ordinate with each other through a shared hierarchical namespace of data registers. We can think of it as a distributed lock server but it involves much more. It is available as open-source and introduces simple interface involving naming, configuration management,  lock and synchronization and group services. This can be customized. It is used in configuration management in an unattended manner or for simpler deployment or provisioning. It is also used for distributed cluster management. It can be used for distributed synchronization in the form of locks, barriers and queues. We recall that the gossip protocol was used to propagate the updates via message exchanges.  The Zookeper service is replicated over a set of machines. All machines store a copy of the data (in memory). A leader is elected on service startup. Clients only connect to a single zookeeper server and maintains a TCP connection. Clients can only read from any Zookeeper server, writes go through the leader and need majority consensus. The data model consists of a hierarchical namespace where each node in the namespace is called a ZNode. Every such node in a Zookeeper's namespace is identified by a path. ZNode paths are canonical, absolute and slash-separted and they have no relative references. Nodes may have varying lifetimes - from persistent which remains until deleted to ephemeral which remains until session close.  These nodes can also be sequence-based where a monotonically increasing number is appended to the end of the path. Each node allows creation-deletion operations, getting and setting data or ACLs and syncing. These can easily be issued from the command line. Each node supports clients to set watch operations which the zookeeper uses to send notifications to the client. All watches are time-ordered but client should handle latency. APIs supported by all nodes are both synchronous and asynchronous.
Read requests are processed locally at the Zookeeper server to which the client connects. However, write requests are forwarded to the leader and go through a majority consensus before  response is generated. Consistency is enforced via sequential updates, atomicity, a single system image, reliability and timeliness. To illustrate with an example of Zookeper as a cluster manager, we see the following operations : Each client host sets a watch on all the cluster members. Each host as a cluster member is also an ephemeral node. Whenever a node joins or leaves, it generates an alert. It keeps updating members periodically for node status changes.
In this case, we can also walkthrough the operations for leader election.  Each znode has a path.  All participants of the election process create an ephemeral-sequential node on the same election path. The node with the smallest sequence number is the leader. Each follower node listens to the leader until the next lower sequence number. When the leader is removed, another one is elected. When a session expires, re-election is conducted. We can see this in action when clients request to acquire a distributed lock. Each client creates a sequential ephemeral znode under a common path. The client corresponding to the lowest number is the winner of the lock. When the lock is release, the number is deleted forcing a re-election. Zookeeper ships client libraries in many languages so that programmability options are expanded. It should be noted that watches are one time triggers, continuous watches require reset after every trigger of a watch. This leads to a design issue with "herd effect" when there are many watches on the same node. Therefore some performance improvements involve steps such as separating the zookeper transaction log to its own disk, setting the heap size to avoid swapping, keeping session timeouts long enough to allow proper cleanup and carefully handling changes in z-node.  Note that since a cluster is involved, addition or removal of hosts is easy. This comes in very handy for production hosts. Services that are deployed on production hosts where hosts change frequently can now easily be tracked with Zookeeper. In fact, Twitter uses this very technique for its service discovery.
#codingexercise
Given an integer array, find the maximum for each and every contiguous subarray of size k
void PrintMaxInWindowSizeK(List<int> A, int k)
{
   var d = new deque<int>();
   if (k > A.Count) return;
   int i;
   for (int i = 0; i < k; ++i)
    {
        while ( (!d.empty()) && A[i] >= A[d.back()])
            d.pop_back();

        d.push_back(i);
    }
    for ( int i = k; i < A.Count; ++i)
    {
        Console.WriteLine("{0},", A[d.front()]);
        while ( (!d.empty()) && d.front() <= i - k)
           d.pop_front();
        while ( (!d.empty()) && A[i] >= A[d.back()])
            d.pop_back();
        d.push_back(i);
    }
    Console.WriteLine("{0},", A[d.front()]);
}