We continue reading "Modern data Fraud Prevention at Big Data Scale". Feedzai enables companies to move from broad segment based scoring of transactions to individual oriented scoring with machine learning based techniques. Feedzai claims to use a new technology on a new platform. They claim to have highest fraud detection rates with lowest false positives. Feedzai uses real-time behavioral profiling as well as historical profiling that has been proven to detect 61% more fraud. They have true real time processing. They say they have true machine learning capabilities. Feedzai relies on Big Data and therefore runs on commodity hardware. The historical data goes as far back as three years. In addition, Feedzai processes realtime data in 25 milli seconds against vast amounts of data at 99th percentile.  This enables fraud to be detected almost as early as when it is committed.

We mentioned their machine learning capabilities. These include:
In-memory event streaming processing which enables fast response
use of NoSQL on commodity servers which enable it to scale
Continuous learning as history builds and the accruing transactions are used to learn
Detection of anomalies no matter how outlier they may be
Reduction in time to process the transactions and 
reducing the cost overall for all transaction processing
The challenge that comes with fraud detection is that fraud often mimics genuine customer behavior so they are harder to tell apart. The classifiers used by Feedzai have very low false positives. The manually learned rules over the years had not yielded such low level of false positives as these algorithms do. Consequently, it the size and computation that distinguish Feedzai from its competitors. 
#codingexercise
describe merge-sort
Merge-Sort(A,p,r)
if (p < r)
  then q <- (p + r) / 2
         Merge-Sort(A, p, q)
         Merge-Sort(A, q+1, r)

         Merge(A, p, q, r)

MERGE(A,p,q,r)
// Initialize L and R arrays with left and right partitions of A at boundary q
// and to have one more element at the end to have a max integer value
i = 1
j = 1
for k = p to r
     if L[i] <= R[j]
         A[k] = L[i]
         i = i + 1
     else
         A[k] = R[j]
         j = j + 1

We continue reading "Modern data Fraud Prevention at Big Data Scale". Feedzai enables companies to move from broad segment based scoring of transactions to individual oriented scoring with machine learning based techniques. Feedzai claims to use a new technology on a new platform. They claim to have highest fraud detection rates with lowest false positives. Feedzai uses real-time behavioral profiling as well as historical profiling that has been proven to detect 61% more fraud. They have true real time processing. They say they have true machine learning capabilities. Feedzai relies on Big Data and therefore runs on commodity hardware. The historical data goes as far back as three years. In addition, Feedzai processes realtime data in 25 milli seconds against vast amounts of data at 99th percentile.  This enables fraud to be detected almost as early as when it is committed.
Feedzai has three primary deployment steps:
1) It evaluates data sets and models
2) It evaluates data sources
3) It connects to case management systems

If we compare Splunk with its connectors, machine learning abilities and use of Big Data, commodity machines and clusters for analytics on machine data in a time series database, it seems the primary difference is the customer orientation of data and analytics. That said, Splunk has immense power in the way it handles machine data. It can collect and tag these data from a variety of sources and it can enable a wide variety of alerts on the data. Even machine learning tools are available but the logic for fraud detection may need to be customized. Feedzai specializes in fraud detection.

#codingexercise
Find the weighted mean of elements with duplicates in a contiguous sorted sequence
Solution:
        1. For each element in a contiguous sequence
        2.        Insert the element, count of repetitions in a dictionary
        3. for each key-value pair in the dictionary
                  sum the value of element times the count
                  also sum the counts
         4. divide the sums for the weighted mean.

#As we read about fraud detection, I'm going to see if delegated identity can help alleviate fraud detection: https://1drv.ms/w/s!Ashlm-Nw-wnWsE3BHcaes2F7Lsoi 

We continue reading "Modern data Fraud Prevention at Big Data Scale". Feedzai enables companies to move from broad segment based scoring of transactions to individual oriented scoring with machine learning based techniques. Feedzai claims to use a new technology on a new platform. They claim to have highest fraud detection rates with lowest false positives. Feedzai uses real-time behavioral profiling as well as historical profiling that has been proven to detect 61% more fraud. They have true real time processing. They say they have true machine learning capabilities. Feedzai relies on Big Data and therefore runs on commodity hardware. The historical data goes as far back as three years. In addition, Feedzai processes realtime data in 25 milli seconds against vast amounts of data at 99th percentile.  This enables fraud to be detected almost as early as when it is committed. Moreover the monitoring and alerting components of Feedzai can work independently from its inflight transactions. Therefore for those purposes, Feedzai can work independently and in a non-intrusive manner. It is also deployed quickly as an appliance that can be trained and activated.
Feedzai involves an in-memory analytics engine which can compute multi-dimensional fraud scores based on 250,000 KPI in the same second every second.  This provides a new industry standard for real-time fraud protection. It also comes in useful to augment machine learning capabilities. For example, the individual transactions being scored are also used train the models.  Moreover the scoring and flagging are intuitive which helps comprehension and reduces manual intervention.
The ability to process 100,000 events per second enables them to detect risk and fraud patterns that would have otherwise gone undetected. The actions taken by Feedzai are configurable from merely reporting to blocking. As such, it is a non-intrusive system. Approximately, ninety percent of all Feedzai customers connect the solution to message queuing but it comes with a variety of connectors that can take the feed from other sources. As opposed to a rules based engine where the deployment and refinement of rules may take time, Feedzai can install its analytic engine and connectors within a day.
If we compare Splunk with its connectors, machine learning abilities and use of Big Data, commodity machines and clusters for analytics on machine data in a time series database, it seems the primary difference is the customer orientation of data and analytics,

#codingexercise
We discussed an exercise yesterday involving topological sort. Let's revisit it:

topological sorting DFS ( V, E)

For each vertex v in V

       V.color=white

       V.d = nil

  Time = 0

 For each vertex v in V:

       If v.color == white:

              DFS-Visit (V, E)

     

 DFS-VISIT (V,E, u)

  time = time + 1

   u.d = time

   u.color = gray

   foreach  vertex v adjacent to u

        If v.color == white

           DFS-VISIT(V,E,v)

         Else

               If v.d  <= u.d < u.f <= v.f  throw back edge exception.

 u.color = black

time = time + 1

 u.f = time

#As we read about fraud detection, I'm going to see if delegated identity can help alleviate fraud detection: https://1drv.ms/w/s!Ashlm-Nw-wnWsE3BHcaes2F7Lsoi 

We continue reading "Modern data Fraud Prevention at Big Data Scale". Feedzai enables companies to move from broad segment based scoring of transactions to individual oriented scoring with machine learning based techniques.Traditional approaches such  as those based on SAS suffered from the limitation that they have become old and difficult to maintain. Second, they are inflexible and unable to keep up with dynamic requirements.Feedzai claims to use a new technology on a new platform. They claim to have highest fraud detection rates with lowest false positives. They have true real time processing. They have true machine learning capabilities. They run on commodity hardware. They are non-intrusive and they are easily deployed.
The difference comes from the approach taken by traditional versus Feedzai techniques. The earlier models used to score transactions based on global perspectives. Feedzai uses real-time behavioral profiling as well as historical profiling that has been proven to detect 61% more fraud.  It also reduced  the false alarms significantly.  The historical data goes as far back as three years. In addition, Feedzai processes realtime data in 25 milli seconds against vast amounts of data at 99th percentile.  This enables fraud to be detected almost as early as when it is committed.
Although the machine learning techniques are not enumerated, we will pend reviewing this for later. The takeaway is that Feedzai relies on Big Data and therefore runs on commodity hardware.
Moreover the monitoring and alerting components of Feedzai can work independently from its inflight transactions. Therefore for those purposes, Feedzai can work independently and in a non-intrusive manner. It is also deployed quickly as an appliance that can be trained and activated.

#codingexercise
Given a sorted dictionary of an alien language, find the order of characters
The solution includes the following:
1) Create a graph G with the number of vertices as the number of distinct alphabets in the alien language
2) For every word pair in sequence, find the first mismatching character pair between the words and draw an edge between them in G
3) do a topological sort of the graph and print the characters encountered.

#As we read about fraud detection, I'm going to see if federated identity can help alleviate fraud detection: https://1drv.ms/w/s!Ashlm-Nw-wnWsE3BHcaes2F7Lsoi 

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 with various injected failure.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 the leader election algorithm helps mitigate this further.
We now start reading "Modern data Fraud Prevention at Big Data Scale". Feedzai enables companies to move from broad segment based scoring of transactions to individual oriented scoring with machine learning based techniques.Traditional approaches such  as those based on SAS suffered from the limitation that they have become old and difficult to maintain. Second, they are inflexible and unable to keep up with dynamic requirements.Feedzai claims to use a new technology on a new platform. They claim to have highest fraud detection rates with lowest false positives. They have true real time processing. They have true machine learning capabilities. They run on commodity hardware. They are non-intrusive and they are easily deployed.
we will read about them in the coming week. But I have a question to ask will fraud detection go down if we can differentiate that the transaction was indeed made by the genuine user ? do we always need the user to sign in to let us know that he or she is the real user. Will we recognize them by the phone they carry. we allow websites to delegate authentication such as with OAuth. Why don't we delegate it to Androids and  Apple's ?

#Fraud detection service introduction: https://1drv.ms/w/s!Ashlm-Nw-wnWsEv9woJ7ynzJAPpv 

#codingexercise
any contiguous sorted collection with duplicates has linear runtime complexity to find the weighted mean

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 with various injected failure.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 the leader election algorithm helps mitigate this further.
The latency of requests was also measured. The requests processed per second seemed to increase with the number of the workers but decrease with the number of servers. The average request latency was  found to be between 1.2ms - 1.4 ms.
We conclude with discussion of related work as cited by the authors.  They mention Chubby which also uses a file system interface and an agreement protocol to guarantee the replicas but it is a lock service. Clients using ZooKeeper can choose to implement locks. Also Chubby only allows clients to connect to the leader and not with any other server. ZooKeeper has better performance and a more relaxed consistency model
Some systems focus on fault-tolerance such as ISIS which transforms abstract type specifications into fault tolerant distributed objects thus making fault tolerance mechanism transparent to users.  Other systems like Totem guarantee order of messages in an architecture that exploits hardware broadcasts of local area networks. ZooKeeper also implements the notion of synchronization on a virtual timeline and ordering of requests. ZooKeeper also supports a variety of network topology.
Some systems utilize a state machine replication as for example, Paxos that combines transaction logging for consensus with write-ahead logging for data recovery Some replicated state machines are fully Byzantine tolerant. ZooKeeper is not so but it can be made one without modifying the server code.  Boxwood uses Paxos to form a distributed lock service but it is a higher level primitive while ZooKeeper does not restrict clients from having different primitives. Sinfonia introduced mini-transactions . a new paradigm for building scalable distributed systems. Sinfonia has been designed to store application data but ZooKeeper stores application metadata.Moreover ZooKeeper can add watches where as Sinfonia cannot.  Dynamo  allows clients to put data in a distributed key - value store. The key space in Dynamo is not hierarchical unlike ZooKeeper which also provides better consistency and durability guarantees.
#codingexercise
Find the number of elements who have the same minimum number of duplicates in a contiguous sorted sequence
Solution:
        1. For each element in a contiguous sequence
        2.        Insert the element, count of repetitions in a dictionary
        3. Find the min count from the values in a dictionary
        4. for each key-value pair in the dictionary
                  if the value == min count
                      print the key

This can be improved without use of a hash table by retaining only a single key value pair that is updated when the value is lower than the previous. A count is maintained for every match with the key value pair and reset when the key value pair changes.
#Fraud detection service introduction: https://1drv.ms/w/s!Ashlm-Nw-wnWsEv9woJ7ynzJAPpv 

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 with various injected failure.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.
The latency of requests was also measured. A worker process creates and deletes new node except that the deletes are asynchronous. The number of worker process is varied but a large number of nodes are attempted. The requests processed per second seemed to increase with the number of the workers but decrease with the number of servers. The average request latency was  found to be between 1.2ms - 1.4 ms.
A number of barriers was also executed sequentially to evaluate the behavior of primitives with ZooKeeper. For each barrier like a mutex, a client waits for all other clients before moving on to the instruction succeeding it. This is true for both entry and exit. The number of barriers were executed one after the other.  The time to process the barriers increased linearly with the number of barriers which indicated that the concurrent access to the data tree does not hamper the execution.  Also, the latency increased proportionally to the number of clients.
#codingexercise
Find the number of elements who have the same maximum number of duplicates in a contiguous sorted sequence
Solution:
        1. For each element in a contiguous sequence
        2.        Insert the element, count of repetitions in a dictionary
        3. Find the max count from the values in a dictionary
        4. for each key-value pair in the dictionary
                  if the value == max count
                      print the key

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.

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.

#codingexercise
Find three elements in an array that satisfy Pythagorean theorem
Solution:
        1. Square all the elements
        2. Sort all the squares
        3. For every element from the end as item
                  Iterate from start to the element just previous to this item as candidate
                            let difference = item - candidate
                                 if difference >= candidate and difference exists between candidate and item by binary_search
                                     return Tuple<int, int, int> as candidate, difference, item

Software for  Email Campaign updated: https://1drv.ms/w/s!Ashlm-Nw-wnWsEXQ3UmFVYv0GpFe  

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 durability guarantee of ZooKeeper. On every read request, a zxid is returned that relates to the last transaction seen by the server. Since the writes are all transactional, this zxid indicates a partial order of the read requests.  If a client connects to a different server, that server ensures that its view of the ZooKeeper data is at least as current as that of the client by comparing its zxid with that of the client. If the client is more recent, the server does not reestablish a session until it has caught up. Since a majority of the ZooKeepers would be current before the client received the zxid, the client is guaranteed to find another server that has a recent view of the system.
Client session failures are detected using timeouts. The leader determines that the client is gone if none of the servers received anything within the timeout. The client is encouraged to send a heartbeat if there are no active requests for a long time. This is automatically done in the client library from ZooKeeper.
The evaluations done with ZooKeeper by the authors included measuring throughput 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.

Software for  Email Campaign updated: https://1drv.ms/w/s!Ashlm-Nw-wnWsEXQ3UmFVYv0GpFe  

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 components of ZooKeeper - the request processor, the atomic broadcast and the replicated database. The request processor is one which prepares the request for processing that also includes co-ordination activities among servers for write requests. If the request processing involves co-ordination, it is handled by an agreement protocol which is an implementation of atomic broadcast. The changes are committed in ZooKeeper database that is replicated across all servers.  This database is periodically snapshot because replaying all the messages in order would take too long to recover state. During the snapshot, the ZooKeeper state is not locked so the snapshots don't really reflect the state of the ZooKeeper at any point of time. However since the transactions are idempotent, snapshots allow the state to be restored because the changes can be applied more than once and they are in the same order as in replay.
We will now see how ZooKeeper provides durability.  On every read request, a zxid is returned that relates to the last transaction seen by the server. Since the writes are all transactional, this zxid indicates a partial order of the read requests. All responses including the heartbeats during periods of idle activity include the last zxid seen by the server that the client is connected to. If a client connects to a different server, that server ensures that its view of the ZooKeeper data is at least as current as that of the client by comparing its zxid with that of the client. If the client is more recent, the server does not reestablish a session until it has caught up. Since a majority of the ZooKeepers would be current before the client received the zxid, the client is guaranteed to find another server that has a recent view of the system. This gurantees durability. ZooKeeper also maintains a session timeout to detect client  session failures. Generally clients re-establish a session. The client library for ZooKeeper actually sends client heartbeats and switches servers if the servers are not responsive enough.
Software for  Email Campaign: https://1drv.ms/w/s!Ashlm-Nw-wnWsEXQ3UmFVYv0GpFe  
#codingexercise
Another method for finding the number of duplicates in a sorted contiguous sequence is similar to the earlier  binary search based method of traversing linearly from the current element but searching for the previous and next elements instead.

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 components of ZooKeeper - the request processor, the atomic broadcast and the replicated database. The request processor is one which prepares the request for processing that also includes co-ordination activities among servers for write requests. If the request processing involves co-ordination, it is handled by an agreement protocol which is an implementation of atomic broadcast. The changes are committed in ZooKeeper database that is replicated across all servers.  This database is periodically snapshot because replaying all the messages in order would take too long to recover state. During the snapshot, the ZooKeeper state is not locked so the snapshots don't really reflect the state of the ZooKeeper at any point of time. However since the transactions are idempotent, snapshots allow the state to be restored because the changes can be applied more than once and they are in the same order as in replay.
Writes and reads for clients are now handled easily with the above design  Since the server processes writes in order and there is no concurrency for writes, even the notifications are strictly ordered. On every write, the notifications are sent out and cleared.  Only the server that the client connects to, sends out notifications to the client. Read requests are also handled locally. Read requests are also directly served from the in-memory database and do not involve the request processor or the atomic broadcast. Such fast reads however however do not guarantee a precedence order for the reads which means they may read state values even though more recent changes have been committed. To alleviate this a 'sync' primitive is provided that ensures global consistency by performing the equivalent of flushing all writes. There is no broadcast required for sync, instead  it is placed at the end of the queue of requests between the leader and the server executing the call to sync.  The follower must be sure that the leader has not changed. This can be ascertained by looking at the pending queue. if the queue is not empty, then the leader is the same. If the queue is empty, the leader needs to issue a null transaction and orders the sync after that transaction.  A null transaction is not issued then the leader realizes it is not a leader before the follower abandon the leader.
#codingexercise
int binary_search(String input, int start, int end, char val)
{
int mid = (start + end)/2;
if (input[mid] == val) return mid;
if (start == end && input[mid] != val) return -1;
if (input[mid] < val)
return binary_search(nums, mid+1, end, val);
else
return binary_search(nums, start, mid, val);

}
int GetCount(String input, char val)
{
int current = binary_search(input, 0, input.Length - 1, val);
if (current == -1) return 0;
int mid = current;
while (current >= 0 && input[current] == val) current--;
current++;
int start = current;
current = mid;
while (current <= input.Length-1 && input[current] == val)
     current++;
current--;
int end = current;
return end-start+1;
}

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 saw a few examples of primitives that are possible with ZooKeeper. These primitives exist only on the client side. These included implementing dynamic configuration in a distributed application, specifying group membership and to implement locks and double barriers. These have been put to use with applications such as Yahoo web crawler which uses this for its page fetching service. Katta, a distributed indexer uses this for coordination. Even high traffic Yahoo message broker which is a distributed publish-subscribe system uses this for managing configuration, failure detection and group membership. We discussed their usages in detail.
We next review the components in the implementation of ZooKeeper. It provides high availability by replicating the ZooKeeper data  These include the following 1) request processor, 2) Atomic Broadcast and 3) replicated database
The request processor is one which prepares the request for processing that also includes co-ordination activities among servers for write requests. If the request processing involves co-ordination, it is handled by an agreement protocol which is an implementation of atomic broadcast. The changes are committed in ZooKeeper database that is replicated across all servers.  This database is an in-memory database containing the entire data tree. Each Znode is about 1MB of data by default and this can be configured. Disk updates are logged and updates are write-through.  They also keep a replay or write ahead log of committed operations and take snapshots of their in-memory database.
Clients connect to only one server each. If they perform read operations, they directly read the database avoiding the agreement protocol.  Write requests are forwarded to a leader which notifies the others with messages consisting of state changes and agreed upon state changes. Write requests are in a transaction and the messaging layer is atomic, so servers do not have local replicas that diverge. A request may not be idempotent but a transaction is one.  The leader converts a request into a transaction describing the state of the system when the request is applied. With the help of transactions, all requests are translated into success transactions or error transactions and the database is kept consistent. The agreement protocol is initiated by the leader which executes the request and broadcasts the change with Zab using a simple majority quorum.  The request processing pipeline is kept full to achieve high throughput.  Zab delivers the messages in order and exactly once. Even if a message is redelivered during recovery, all transactions are idempotent.

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 saw a few examples of primitives that are possible with ZooKeeper. These primitives exist only on the client side. These included implementing dynamic configuration in a distributed application, specifying group membership and to implement locks and double barriers. These have been put to use with applications such as Yahoo web crawler which uses this for its page fetching service. Katta, a distributed indexer uses this for coordination. Even high traffic Yahoo message broker which is a distributed publish-subscribe system uses this for managing configuration, failure detection and group membership.
The fetching service is part of the Yahoo crawler and involves a master that commands page fetching processes. The masters provide the fetchers with configuration, and the fetchers keep the master posted with status and health. ZooKeeper gives the advantage to recover from failures of masters, guaranteeing availability despite failures and decoupling  the client from the servers.
Similarly Katta divides the work into shards and a master assigns shards to slaves Katta uses this to track the status of slave servers and the master to handle reelecting a master. Katta uses the ZooKeeper to track and propagate the assignment of shards to slaves.
The servers of a Yahoo message broker use a shared-nothing distributed architecture which makes co-ordination essential for correct operation and ZooKeeper is used to manage the distribution of topics, deal with failures and control system processes.
#codingexercise
Given an index of an element in a sorted array with duplicates, count the number of duplicates
int GetCount(String input, char val)
{
int current = binary_search(input, 0, input.Length - 1, val);
if (current == -1) return 0;
int mid = current;
while (current >= 0 && input[current] == val) current--;
current++;
int start = current;
current = mid;
while (current <= input.Length-1 && input[current] == val)
          current++;
current--;
int end = current;
return end-start+1;
}

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 saw a few examples of primitives that are possible with ZooKeeper. These primitives exist only on the client side. For example, 1) ZooKeeper can be used to implement dynamic configuration in a distributed application.  This is one of the basic schemes where each configuration is stored in the form of ZNode and tasks that are dependent on each other are stored as Rendezvous nodes. 2) GroupMembership is another common co-ordination requirement. This primitive is implemented using ephemeral nodes. 3) ZooKeeper can also be used to implement locks. Applications implement locks using lock files represented by a ZNode. To acquire a lock, the client tries to create the designated node with the ephemeral flag. If the create succeeds, the client holds the lock otherwise the client watches the node in case the leader dies. Whenever the znode is deleted, other clients may try to acquire the lock.  We see that this locking scheme  ensures that the removal of a znode causes only one client  to wake up. There is no polling or timeouts. and the state of the ZNodes helps with monitoring, troubleshooting and debugging.  In addition to simple locks, ZooKeeper also has read-write locks These locks differ from simple locks where only earlier write lock znodes prevent a client from obtaining a read lock. Read locks may be shared. Here the herd effect is put to use so that all read clients may be used.
Double barriers are yet another locking mechanism. They enable client to synchronize the beginning and end of a computation.  The threshold for the barrier decides how many processes join. They leave the barrier only when they are done. These processes create and delete a child of the znode maintained by the barrier. Processes can leave the barrier when all of the processes have removed their children. When the threshold is exceeded, a ready znode is created which is watched by all waiting processes. This allows the processes to know when to enter. Similarly to leave, the processes watch for a znode to disappear. Together these locking services enable a wide variety of applications.  For example, Yahoo web crawler uses this for its page fetching service. Katta, a distributed indexer uses this for coordination. Even high traffic Yahoo message broker which is a distributed publish-subscribe system uses this for managing configuration, failure detection and group membership.
#codingexercise
Given a sorted string, find number of occurrences of a given character in string.
int binary_search(String input, int start, int end, char val)
{
int mid = (start + end)/2;
if (input[mid] == val) return mid;
if (start == end && input[mid] != val) return -1;
if (input[mid] < val)
return binary_search(nums, mid+1, end, val);
else
return binary_search(nums, start, mid, val);
}
int GetCount(String input, char val)
{
int current = binary_search(input, 0, input.Length - 1, val);
if (current == -1) return 0;
while (current >= 0 && input[current] == val) current--;
current++;
int start = current;
while (current <= input.Length-1 && input[current] == val)
          current++;
current--;
int end = current;
return end-start+1;
}
Optimization: We could also skip ahead to resume counting in the other direction from the location we started 

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 now look at some examples of primitives that are possible with ZooKeeper. These primitives exist only on the client side.
ConfigurationManagement - ZooKeeper can be used to implement dynamic configuration in a distributed application.  This is one of the basic schemes where each configuration is stored in the form of ZNode. Processes wake up with the fullname of ZNode and set a watch on it. If the configuration is updated, the processes are notified and they apply the updates.
Rendezvous Node. Sometimes a configuration change is dependent others. For example, host and port may be known only afterwards. In this case clients can co-ordinate with a rendezvous node.
The node is filled in with details as and when they become available. The workers set a watch on this node before they begin their changes.
GroipMembership is another common co-ordination requirement. This primitive is implemented using ephemeral nodes. A node is designated to represent the group and is created at the start of the session. When a process member of the group starts, it creates an ephemeral child node under this group node. This child node keeps information for the process that creates it. If the process fails or exits, the node is automatically removed. Group membership can simply be enumerated by listing these child nodes.
Simple Locks: ZooKeeper can also be used to implement locks. Applications implement locks using lock files represented by a ZNode. To acquire a lock, the client tries to create the designated node with the ephemeral flag. If the create succeeds, the client holds the lock otherwise the client watches the node in case the leader dies. Whenever the znode is deleted, other clients may try to acquire the lock. There are two side-effects of this locking mechanism: First, there is a herd effect when all clients vie for a lock even though only one acquires it. Second, it only implements exclusive locking.
Locks can also be created without herd effect.   A node is designated as the lock node. Each of the clients do the following:
Create an ephemeral or sequential node as a child node under the lock node.
Enumerate the children under the lock node.
If the created node is the lowest sequential among the children, the client has acquired the lock and exits
If there is a node preceding the created node, a watch is set on it
The process is repeated by enumerating the children under the lock node.
To release the lock, the node may merely be deleted.
This completes the locking primitive implemented by ZooKeeper.

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.
ZooKeeper has two basic guarantees - linearizable writes and FIFO client order.  All requests that update the state of ZooKeeper are serializable and respect precedence. All requests from a given client are executed in order that they were sent by the client. ZooKeeper handles both by designating a path as the "ready" ZNode. The other clients may make changes only when that ZNode exists.
There are a few caveats with these guarantees.
If a process sees the ready exists before the new leader starts to make a change, then starts reading the configuration while the change is in progress, then it will see an inconsistent state.  This is solved with the ordering guarantees of the notifications where the notification happens before the client sees the new state.
Another consideration is that clients may have their own communication channels in addition to ZooKeeper. For example, two clients may have  a shared configuration and a shared communication channel. Changes from one may lag behind the other and may not see the updates until it issues a write before re-reading the configuration. For this purpose, ZooKeeper provides a sync request which when followed by a read is equivalent to a slow read. This primitive is similar to flush.
Since ZooKeeper maintains several servers, it is able to provide durability guarantees based on a simple majority. As long as there is a simple majority of servers up and running, it will respond successfully to a change request. Similarly as long as this quorum of servers is maintained, it can eventually recover from any number of failures. These guarantees therefore conclude the requirements for durability and consistency from this co-ordination service.
#codingexercise
Generate palindromes less than n
int ReverseAndAppend(int number, int base, bool isOdd)
{
int n = number;
int result = number;
if (isOdd)
    n /= base;
while (n > 0)
{
result = result * base + (n % base);
n /= base;
}
return result;
}
void GeneratePalindromes(int n)
{
int  result = 1;
for (int j = 1; j <= 2; j++)
{
int i = 1;
result = ReverseAndAppend(i, 10, j%2);
while( result < n)
{
Console.WriteLine(result);
i++;
result = ReverseAndAppend(i, 10, j%2);
}
}
}

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.
Both the linearizable writes and the FIFO client order form the guarantees for ZooKeeper. These two guarantees also interact.  ZooKeeper handles both by designating a path as the "ready" ZNode. The other clients may make changes only when that ZNode exists.
There are a few caveats with these guarantees.
If a process sees the ready exists before the new leader starts to make a change, then starts reading the configuration while the change is in progress, then it will see an inconsistent state.  This is solved with the ordering guarantees of the notifications where the notification happens before the client sees the new state.
Ideas for source code visualization tool: https://1drv.ms/w/s!Ashlm-Nw-wnWsEOTGP5op9hPrVVe  

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.
Both the linearizable writes and the FIFO client order form the guarantees for ZooKeeper. These two guarantees also interact.  ZooKeeper handles both by designating a path as the "ready" ZNode. The other clients may make changes only when that ZNode exists.
ZNodes can be both regular and ephemeral. Regular nodes are the ones that clients can create and delete explicitly. Ephemeral nodes are the ones that the clients can create for the duration of the session. Sessions have an associated timeout. A session is initiated when the client connects and ends when the client closes or ZooKeeper deems faulty. Sessions come with associated state changes that inform the stage in which the execution of the operations are. Sessions also enable a client to move from one ZooKeeper server to another.
Perhaps the most important aspect of ZooKeeper is the interface it provides the clients. These include the following methods:
1) create (path, data, flags) : Used to create a ZNode with the name path and to store data array in it. It returns the name of the newly created ZNode.
2) delete(path, version) : delete the ZNode path if it is at the expected version
3) exists(data, path): Returns trues if ZNode with name path exists, and returns false otherwise
4) getData (path, watch) : returns the data and metadata for the node.
5) setData (path, data, version): writes the data object array to the node path if the version matches
6) getChildren(path, watch) - returns the set of names of the children of a node
7) sync(path) - Waits for all updates pending at the start of the operation to the concerned Zookeeper server.
#codingexercise
Find the position of the number closest to the midpoint of the range of numbers in a row-wise and column-wise sorted two dimensional array
Tuple<int, int> GetPosition(int [,] A, int r, int c)
{
int min = A[0,0];
int max = A[r-1, c-1];
int mid = (min+max)/2;
var t = new Tuple<int, int>();
int threshold = INT_MAX;
for (int i = 0; i < r-1; i++) // row wise
   for (int j = 0; j < c-1; j++) // column wise
    // we could optimize this to picking the element bottom-right, or bottom or right for the one closet to mid
   // here we simply traverse through the numbers
   { int distance = Math.Abs(A[i,j] - mid);
      if (distance <= threshold){
           threshold = distance;
           t.first = i;
           t.second = j;
   }
return t;
}

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.
Both the linearizable writes and the FIFO client order form the guarantees for ZooKeeper. These two guarantees also interact. For example, when many clients elect a leader, the leader may take some time to complete its work before it can notify others. During this time, the other clients may not make any changes. And if the leader dies, the partial changes may not be used. Chubby service does not handle the latter requirement. ZooKeeper handles both by designating a path as the "ready" ZNode. The other clients may make changes only when that ZNode exists. Therefore the leader is only responsible for deleting ready, making changes and creating ready. If the leader dies, the ready is not available, so the other clients won't use the changes. If there are a large number of clients, then the latency per client ZNode change will aggregate but because the requests are asynchronous and the changes are pipelined. it does not take that much time.
There are two types of nodes a client can create
clients can create and delete the nodes explicitly and these are called regular ZNodes
clients can create the nodes for the duration of a session and these are called ephemeral ZNodes
#codingexercise
Find the majority element in an array.
using Moore's voting algorithm:
int GetMajorityCandidate(List<int> A)
{
int mindex = 0;
int count = 1;
for (int i = 1; i < A.Count; i++)
{
if (A[mindex] == A[i])
     count++;
else
     count--;
if count == 0;
{
   mindex = i;
   count = 1;
}
}
return A[mindex];
}
bool IsMajorityCandidate(List<int>A,  int candidate)
{
int i, count = 0;
for (int i = 0; i < A.Count; i++)
     if (A[i] == candidate)
         count ++;
if (count > n/2)
   return true;
return false;
}

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.
Both the linearizable writes and the FIFO client order form the guarantees for ZooKeeper. These two guarantees also interact. For example, when many clients elect a leader, the leader may take some time to complete its work before it can notify others. During this time, the other clients may not make any changes. And if the leader dies, the partial changes may not be used. Chubby service does not handle the latter requirement. ZooKeeper handles both by designating a path as the "ready" ZNode. The other clients may make changes only when that ZNode exists. Therefore the leader is only responsible for deleting ready, making changes and creating ready. If the leader dies, the ready is not available, so the other clients won't use the changes. If there are a large number of clients, then the latency per client ZNode change will aggregate but because the requests are asynchronous and the changes are pipelined. it does not take that much time.
#codingexercise
Find the majority element in an array.
Naive implementation
int GetMajority(List<int> A)
{
 var h = new Hashtable();
 for (int i = 0; i < A.Count; i++)
     if (h.ContainsKey(A[i]) == false)
         h.Add(A[i], 1);
     else
         h[A[i]] += 1;
int max = INT_MIN;
int count =  0;
foreach (var kvp in h)
{
     if (kvp.value > count){
          count = kvp.value;
          max = kvp.key;
     }
}
return max;
}

We continue discussing the ZooKeeper. It incorporates elements from group messaging, shared registers and distributed lock services in a replicated, centralized service. It provides a interface that guarantees wait-free property and FIFO execution of requests from each client.  Requests across all clients are also linearized.
Caching is also used to improve performance. The id of the leader is useful to cache because it is frequently required and avoids asking other servers.  ZooKeeper uses a watch mechanism to enable clients to cache data without managing the client cache directly.  With this mechanism, a client can watch for an update to a given data object, and receive notification about update.
ZooKeeper organizes data objects around in a hierarchical namespace
Chubby service provides strong locking and synchronization guarantees.  Locks come in useful to implement leader election and group membership.  ZooKeeper does not implement primitives, rather it implements a co-ordination service with an interface. Such a choice led to the implementation of a co-ordination kernel that enables new primitives without changing the service core. Exposing primitives also had an inherent issue. The processing of requests depended on responses and failure detection of other clients. On the other hand, ZooKeeper uses a wait free data objects organized hierarchically as in filesystems.
#codingexercise
Print all possible decodings of integer sequence
private int GetCount(string A, int n)
{
int count = 0;
if ( n ==0 || n == 1) return 1;
if (A[n-1] > '0')
   count = GetCount(A, n-1);
if(A[n-1] == '1' || A[n-2] == '2' && A[n-1] <= '7')
    count += GetCount(A, n -2);
return count;
}

We continue discussing the ZooKeeper. It incorporates elements from group messaging, shared registers and distributed lock services in a replicated, centralized service. It provides a interface that guarantees wait-free property and FIFO execution of requests from each client.  Requests across all clients are also linearized. In order to do this, it implements a leader based atomic broadcast protocol called Zab. Zab is only used to linerarize writes. Reads can happen in any order and ZooKeeper services them at the local server.
Caching is also used to improve performance. The id of the leader is useful to cache because it is frequently required and avoids asking other servers.  ZooKeeper uses a watch mechanism to enable clients to cache data without managing the client cache directly.  With this mechanism, a client can watch for an update to a given data object, and receive notification about update.  Chubby on the other hand centrally updates the data and blocks updates to invalidate the caches of all clients caching the data being changed. Leases are used to prevent a client from blocking the update indefinitely but leases only affect slow or faulty clients whereas ZooKeeper avoids this problem altogether.
ZooKeeper therefore demonstrates the following :
1) A co-ordination kernel  which provides a wait free co-ordination service with relaxed consistency guarantees to be used in distributed systems
2) A set of higher level co-ordination primitives  that are easy to be used in distributed computing.
3) Experience with co-ordination in a variety of distributed systems.
In ZooKeeper terminology, a client denotes the user of a ZooKeeper service, a server denotes a process providing ZooKeeper service, and znode denotes an in-memory data node which is organized in a hierarchical namespace as the data tree.
#codingexercise
Print Level order traversal of a tree
Void PrintSpiral (Node root)
{
bool change = false;
for (int i = 1; i < height (root); i++)
{
      PrintGivenLevel (root, i, change);
       change = !change;
}
}
void PrintGivenLevel(Node root, int level, bool direction)
{
   if (root == null) return;
   if (level ==1) print(root.data);
   else if level > 1{
       if (direction){
            PrintGivenLevel(root.left, level - 1, direction);
            PrintGivenLevel(root.right, level -1, direction);
       }else{
            PrintGivenLevel(root.right, level-1, direction);

            PrintGivenLevel(root.left, level -1, direction);
       }
    }
}
Instead of the recursive option above, we can also enumerate each level with the help of a queue and reverse only alternate levels. Here we can serialize the nodes with level demarcators and then switch alternatively in one pass.

The ZooKeeper incorporates elements from group messaging, shared registers and distributed lock services in a replicated, centralized service. It provides a interface that guarantees wait-free property and FIFO execution of requests from each client.  Requests across all clients are also linearized. Read requests are satisfied by local servers. It can handle hundreds of thousands of transactions per second. Zookeeper differentiates from other co-ordination services by being a one stop shop. Services like Amazon Simple Queue Service is great for queuing. There are other services specific to leader election. Chubby service provides strong locking and synchronization guarantees.  Locks come in useful to implement leader election and group membership.  ZooKeeper does not implement primitives, rather it implements a co-ordination service with an interface. Such a choice led to the implementation of a co-ordination kernel that enables new primitives without changing the service core. Exposing primitives also had an inherent issue. The processing of requests depended on responses and failure detection of other clients. On the other hand, ZooKeeper uses a wait free data objects organized hierarchically as in filesystems. The interface for ZooKeeper looks very much like that of a filesystem. It also looks Chubby without the lock methods, open and close. Moreover it can implement consensus for any number of processes with FIFO client ordering and linearized writes.
Availability and performance is improved with a collection of servers The service itself implements a pipelined architecture that enables hundreds of thousands of requests to be outstanding which still achieving low latency. Moreover it also enables clients to be asynchronous and generate more requests than they could with being synchronous.  This is especially true for a client that wishes to be a leader. 

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. It is also used for distributed cluster management. It can be used for distributed synchronization in the form of locks, barriers and queues.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. Paths are appended with a monotonically increasing number. ZNode with the path ending in the lowest number is elected the leader. 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
ZooKeeper introduces elements from group messaging, shared registers, and distributed lock services in a replicated centralized service.
#codingexercise
Yesterday we discussed an optimal solution for this problem: Given an integer array, find the maximum for each and every contiguous subarray of size k
Today we see a simple solution which works for small k
void PrintMaxInWindowSizeK(List<int> A, int k)
{
for (int i = 0; i <= A.Count - k; i++)
{
   int max = A[i];
   for (j = 1; j < k ; j++)
   {
       if (A[i+j] > max)
            max = A[i+j];
   }
   Console.WriteLine("{0},", max);
}
}
The same works with a deque of size k by making only one pass over the list of integers.

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()]);
}

Today we start discussing 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. ZNode paths are canonical, absolute and slash-separted and they have no relative references.
#coding exercises
Find the product of first K magic numbers
int GetMagicN(int n)
{
int power = 1;
int result = 0;
while (n)
{
power = power * 5;
if  ( n & 1)
    result += power;
n >> = 1;
}
return result;
}
long GetMagicProduct (int k)
{
 long result = 0;
 for (int I = 1; I <= k; I++)
      result *= GetMagicN(k);
return result;
}
It might be interesting to note that since the magic numbers map to bit representations of consecutive integers, we can easily tell how far apart are perfect powers of 5 in the magic number sequence.