_____________

				SECTION7

			      Irene Zhang
			     _____________


Table of Contents
_________________

1 Chubby
2 ZooKeeper
3 Consensus protocols
4 Multi-Paxos: what people actually use
5 Batching: what many people use
6 Fast Paxos
7 Caches
8 Design Decisions
.. 8.1 Interface
.. 8.2 Service vs library
.. 8.3 Consistency
9 Chubby lessons learned
.. 9.1 machines are usually up for days at a time
.. 9.2 apps should not just crash when the leader changes


1 Chubby
========

  - basically a small file server + lock service
  - every file has an associated lock, but you don't have to hold it
  - Used similar to your view service to decide which servers are up and
    down and which one is the primary, etc.
  - supports notifications when files change (i.e., get a notification
    if the primary changes)


2 ZooKeeper
===========

  - open-source version of Chubby
  - used in Spark and Mesos (big processing engines used by Twitter)
  - serves the same functionality
  - has some different design decisions


3 Consensus protocols
=====================

  - Paxos is equivalent to Multi-Paxos, but Multi-Paxos is more
    efficient for deciding lots of instances at a time.
  - Multi-Paxos is the same as VR and Atomic Broadcast. The abstractions
    are slightly different: Multi-Paxos is log, VR provides
    state-machine replication and Atomic Broadcast provides a guaranteed
    communication mechanism


4 Multi-Paxos: what people actually use
=======================================

  - Pick a leader
  - Give the leader a lease
  - Allow them to serve reads locally and replicate only gets
  - Lease means that they always have all up-to-date puts, so no need to
    replicate gets


5 Batching: what many people use
================================

  - Have the leader batch up a bunch of puts to send at a time
  - Better for high throughput systems, usually doesn't hurt latency too
    much


6 Fast Paxos
============

  - Send to all replicas, have them send to the leader
  - What happens if there is re-ordering? Have the leader pick an order
    and send it out


7 Caches
========

  - More copies!
  - these have to be consistent too :(
  - Chubby uses invalidations (not updates), leader keeps list of
    clients that have signed up for them.
  - ZooKeeper uses non-blocking invalidation, so clients may see stale
    data. However, watch will always return before later reads see the
    updated value and clients can use sync to make sure they see the
    latest (kind of like a memory barrier)


8 Design Decisions
==================

8.1 Interface
~~~~~~~~~~~~~

  - Both use a file system interface. Useful?


8.2 Service vs library
~~~~~~~~~~~~~~~~~~~~~~

  - Both use a service vs a library.


8.3 Consistency
~~~~~~~~~~~~~~~

  - Chubby has slightly stricter consistency (linearizability with no
    stale reads) Better?


9 Chubby lessons learned
========================

9.1 machines are usually up for days at a time
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


9.2 apps should not just crash when the leader changes
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

  - in fact, maybe these should be invisible