Random Notes
  • Introduction
  • Reading list
  • Theory
    • Index
      • Impossibility of Distributed Consensus with One Faulty Process
      • Time, Clocks, and the Ordering of Events in a Distributed System
      • Using Reasoning About Knowledge to analyze Distributed Systems
      • CAP Twelve Years Later: How the “Rules” Have Changed
      • A Note on Distributed Computing
  • Operating System
    • Index
  • Storage
    • Index
      • Tachyon: Reliable, Memory Speed Storage for Cluster Computing Frameworks
      • Exploiting Commutativity For Practical Fast Replication
      • Don’t Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS
      • Building Consistent Transactions with Inconsistent Replication
      • Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System
      • Spanner: Google's Globally-Distributed Database
      • Bigtable: A Distributed Storage System for Structured Data
      • The Google File System
      • Dynamo: Amazon’s Highly Available Key-value Store
      • Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications
      • Replicated Data Consistency Explained Through Baseball
      • Session Guarantees for Weakly Consistent Replicated Data
      • Flat Datacenter Storage
      • Small Cache, Big Effect: Provable Load Balancing forRandomly Partitioned Cluster Services
      • DistCache: provable load balancing for large-scale storage systems with distributed caching
      • Short Summaries
  • Coordination
    • Index
      • Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases
      • Paxos made simple
      • ZooKeeper: Wait-free coordination for Internet-scale systems
      • Just Say NO to Paxos Overhead: Replacing Consensus with Network Ordering
      • Keeping CALM: When Distributed Consistency is Easy
      • In Search of an Understandable Consensus Algorithm
      • A comprehensive study of Convergent and Commutative Replicated Data Types
  • Fault Tolerance
    • Index
      • The Mystery Machine: End-to-end Performance Analysis of Large-scale Internet Services
      • Gray Failure: The Achilles’ Heel of Cloud-Scale Systems
      • Capturing and Enhancing In Situ System Observability for Failure Detection
      • Check before You Change: Preventing Correlated Failures in Service Updates
      • Efficient Scalable Thread-Safety-Violation Detection
      • REPT: Reverse Debugging of Failures in Deployed Software
      • Redundancy Does Not Imply Fault Tolerance
      • Fixed It For You:Protocol Repair Using Lineage Graphs
      • The Good, the Bad, and the Differences: Better Network Diagnostics with Differential Provenance
      • Lineage-driven Fault Injection
      • Short Summaries
  • Cloud Computing
    • Index
      • Improving MapReduce Performance in Heterogeneous Environments
      • CLARINET: WAN-Aware Optimization for Analytics Queries
      • MapReduce: Simplified Data Processing on Large Clusters
      • Dryad: Distributed Data-Parallel Programs from Sequential Building Blocks
      • Resource Management
      • Apache Hadoop YARN: Yet Another Resource Negotiator
      • Mesos: A Platform for Fine-Grained Resource Sharing in the Data Center
      • Dominant Resource Fairness: Fair Allocation of Multiple Resource Types
      • Large-scale cluster management at Google with Borg
      • MapReduce Online
      • Delay Scheduling: A Simple Technique for Achieving Locality and Fairness in Cluster Scheduling
      • Reining in the Outliers in Map-Reduce Clusters using Mantri
      • Effective Straggler Mitigation: Attack of the Clones
      • Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing
      • Discretized Streams: Fault-Tolerant Streaming Computation at Scale
      • Sparrow: Distributed, Low Latency Scheduling
      • Making Sense of Performance in Data Analytics Framework
      • Monotasks: Architecting for Performance Clarity in Data Analytics Frameworks
      • Drizzle: Fast and Adaptable Stream Processing at Scale
      • Naiad: A Timely Dataflow System
      • The Dataflow Model:A Practical Approach to Balancing Correctness, Latency, and Cost in Massive-Scale
      • Interruptible Tasks:Treating Memory Pressure AsInterrupts for Highly Scalable Data-Parallel Program
      • PACMan: Coordinated Memory Caching for Parallel Jobs
      • Multi-Resource Packing for Cluster Schedulers
      • Other interesting papers
  • Systems for ML
    • Index
      • A Berkeley View of Systems Challenges for AI
      • Tiresias: A GPU Cluster Managerfor Distributed Deep Learning
      • Gandiva: Introspective Cluster Scheduling for Deep Learning
      • Workshop papers
      • Hidden Technical Debt in Machine Learning Systems
      • Inference Systems
      • Parameter Servers and AllReduce
      • Federated Learning at Scale - Part I
      • Federated Learning at Scale - Part II
      • Learning From Non-IID data
      • Ray: A Distributed Framework for Emerging AI Applications
      • PipeDream: Generalized Pipeline Parallelism for DNN Training
      • DeepXplore: Automated Whitebox Testingof Deep Learning Systems
      • Distributed Machine Learning Misc.
  • ML for Systems
    • Index
      • Short Summaries
  • Machine Learning
    • Index
      • Deep Learning with Differential Privacy
      • Accelerating Deep Learning via Importance Sampling
      • A Few Useful Things to Know About Machine Learning
  • Video Analytics
    • Index
      • Scaling Video Analytics on Constrained Edge Nodes
      • Focus: Querying Large Video Datasets with Low Latency and Low Cost
      • NoScope: Optimizing Neural Network Queriesover Video at Scale
      • Live Video Analytics at Scale with Approximation and Delay-Tolerance
      • Chameleon: Scalable Adaptation of Video Analytics
      • End-to-end Learning of Action Detection from Frame Glimpses in Videos
      • Short Summaries
  • Networking
    • Index
      • Salsify: Low-Latency Network Video through Tighter Integration between a Video Codec and a Transport
      • Learning in situ: a randomized experiment in video streaming
      • Short Summaries
  • Serverless
    • Index
      • Serverless Computing: One Step Forward, Two Steps Back
      • Encoding, Fast and Slow: Low-Latency Video Processing Using Thousands of Tiny Threads
      • SAND: Towards High-Performance Serverless Computing
      • Pocket: Elastic Ephemeral Storage for Serverless Analytics
      • Fault-tolerant and Transactional Stateful Serverless Workflows
  • Resource Disaggregation
    • Index
  • Edge Computing
    • Index
  • Security/Privacy
    • Index
      • Differential Privacy
      • Honeycrisp: Large-Scale Differentially Private Aggregation Without a Trusted Core
      • Short Summaries
  • Misc.
    • Index
      • Rate Limiting
      • Load Balancing
      • Consistency Models in Distributed System
      • Managing Complexity
      • System Design
      • Deep Dive into the Spark Scheduler
      • The Actor Model
      • Python Global Interpreter Lock
      • About Research and PhD
Powered by GitBook
On this page
  • TL;DR:
  • Summary:
  • Implementation:(See Figure 4)
  • Some final notes:
  • Reference:

Was this helpful?

  1. Coordination
  2. Index

ZooKeeper: Wait-free coordination for Internet-scale systems

https://www.usenix.org/legacy/event/atc10/tech/full_papers/Hunt.pdf

TL;DR:

ZooKeeper is a centralized service for maintaining configuration information, naming, providing distributed synchronization, and providing group services.

Summary:

Zookeeper is a coordination[1] service for distributed systems. It provides to its clients the abstraction of a set of data nodes(zNodes), organized according to a hierarchical name space. A znode may act as both a file containing binary data and a directory with more znodes as children[2]. ZooKeeper supports the concept of ephemeral znodes and regular[3] znodes. An ephemeral znodes will be removed by the system automatically when the session that creates them terminates. An important feature of Zookeeper is that it allows client to receive timely notifications of changes without requiring polling.[4] The last important concept is sessions. A client connects to Zookeeper and initiates a session. Sessions have an associated timeout.

Although ZooKeeper provides both distributed storage and message queue, you will run into some issue if you have Zookeeper for everything. First, there is a size limit of each znode(~1MB). Thus, in practice, znodes are used for metadata or configuration in a distributed computation. Similarly, you are likely to end up with throughput issues if you use Zookeeper as a message queue.

Zookeeper has two basic ordering guarantees: Linearizable writes and FIFO client order[5]. ZooKeeper process read requests locally at each replica. This allows the service to scale linearly as servers are added to the system.

Implementation:(See Figure 4)

  • ZooKeeper provides high availability by replicating the ZooKeeper data on each server that composes the service. The replicated database is an in-memory database containing the entire data tree.(Each znode stores a maximum of 1MB of data by default). It will keep a replay log(a write-ahead log) of committed operations and generate periodic snapshots of the in-memory database.

  • Write requests are processed by an agreement protocol. All write requests are handled by the leader[6]. The rest of the Zookeeper servers are followers.

  • Request Processor: When the leader receives a write request, it calculates what the state of the system will be when the write is applied and transforms it into a transaction that captures this new state.

  • Atomic Broadcast: The leader executes the request and broadcasts the change to the Zookeeper state through Zab[7]. Zookeeper can only work if a majority of servers are correct. Zab guarantees that changes broadcast by a leader are delivered in the order they were sent and all changes from previous leaders are delivered to an established leader before it broadcasts its own changes. In normal operation, Zab does deliver all message in order and exactly once, but may redeliver a message during recovery.

  • Replicated database: Each replica has a copy in memory of the ZooKeeper state. For high performance, Zookeeper use periodic snapshots and only requires redelivery of messages since the start of the snapshot. Zookeeper uses fuzzy snapshots since it doesn't require any locks. The snapshot may not correspond to the sate of Zookeeper at any point in time.

  • Client-server Interaction: One drawback of handling reads locally is that a read operation may return a stale value. To guarantee that a give read operation returns the latest updated value, a client calls sync followed by read operation.

Some final notes:

  • Zookeeper is not a lock service, but it can be used by clients to implement locks. Unlike Chubby, ZooKeeper allows clients to connect to any ZooKeeper server, not just the leader.

  • Zookeeper does not assume that servers can be Byzantine, but it does employ mechanisms such as checksums and sanity checks.

  • Paxos may violate the FIFO client property.

  • As you add ZooKeeper Servers, the read throughput improves, but the write throughput degrades. This is because atomic broadcast needs to be done via Zab.(a write operation requires the agreement of (in general) at least half the nodes in an ensemble). Thus, Zookeeper scales well with increase in read operations, but does not with increase write operations. To alleviate this, observer replicas are used. Observers are non-voting members of an ensemble which only hear the results of votes, not the agreement protocol that leads up to them.[8]

Zookeeper is used for discovery, resource allocation, leader election and high priority notifications.

[1] Large-scale distributed applications require different forms of coordination.(e.g. discovery, resource allocation, leader election and configurations). See Section 2.4 for more example primitives.

[2] Ephemeral znodes cannot have children.

[3] When creating a new node, a client can set a sequential flag. Nodes created with the sequential flag set have the value of a monotonically increasing counter appended to its name.

[4] ZooKeeper gives guarantees about ordering. Every update is part of a total ordering. All clients might not be at the exact same point in time, but they will all see every update in the same order.

[5] All requests from a given client are executed in the order that they were sent by the client.

[6] Follower can receive requests, but all write requests are forwarded to the leader.

Reference:

PreviousPaxos made simpleNextJust Say NO to Paxos Overhead: Replacing Consensus with Network Ordering

Last updated 5 years ago

Was this helpful?

[7]

[8]

https://distributedalgorithm.wordpress.com/2015/06/20/architecture-of-zab-zookeeper-atomic-broadcast-protocol/#comments
https://zookeeper.apache.org/doc/r3.4.13/zookeeperObservers.html
LogoZooKeeper - The King of CoordinationElastic Blog