Internet Server ClustersInternet Server ClustersUsing Clusters for Scalable ServicesUsing Clusters for Scalable ServicesClusters are a common vehicle for improving scalability and availability at a single service site in the network.Are network services the “Killer App” for clusters?• incremental scalabilityjust wheel in another box...• excellent price/performancehigh-end PCs are commodities: high-volume, low margins• fault-tolerance“simply a matter of software”• high-speed cluster interconnects are on the marketSANs + Gigabit Ethernet...cluster nodes can coordinate to serve requests w/ low latency• “shared nothing”The Porcupine WheelThe Porcupine Wheelscaleavailabilityperformance manageabilityReplicationFunctional homogeneityAutomatic reconfigurationDynamic transaction schedulingPorcupine: A Highly Available ClusterPorcupine: A Highly Available Cluster--based Mail Servicebased Mail ServiceYasushi SaitoBrian BershadHank LevyUniversity of Washington Department of Computer Science and Engineering,Seattle, WAhttp://porcupine.cs.washington.edu/[Saito]Yasushi’s SlidesYasushi’s SlidesYasushi’s slides can be found on his web site at HP.http://www.hpl.hp.com/personal/Yasushi_Saito/I used his job talk slides with a few of my own mixed in, which follow.Porcupine Replication: OverviewPorcupine Replication: OverviewTo add/delete/modify a message:• Find and update any replica of the mailbox fragment.Do whatever it takes: make a new fragment if necessary...pick a new replica if chosen replica does not respond.• Replica asynchronously transmits updates to other fragment replicas.continuous reconciling of replica states• Log/force pending update state, and target nodes to receive update.on recovery, continue transmitting updates where you left off• Order updates by loosely synchronized physical clocks.Clock skew should be less than the inter-arrival gap for a sequence of order-dependent requests...use nodeID to break ties.• How many node failures can Porcupine survive? What happens if nodes fail “forever”?Key PointsKey Points• COTS/NOW/ROSE off-the-shelf• Shared-nothing architecture (vs. shared disk)• Functionally homogeneous (anything anywhere)• Hashing with balanced bucket assignment to nodes• ROWA replication with load-balancing readsRead one write all• Soft state vs. hard state: minimize hard state• Leverage weak consistency: “ACID vs. BASE”• Idempotent updates and total orderingLoosely synchronized clocks• Operation logging/restart• Spread and affinityHow Do Computers Fail?How Do Computers Fail?Porcupine’s failure assumptionsLarge clusters are unreliable.Assumption: live nodes respond correctly in bounded time time most of the time.• Network can partition• Nodes can become very slow temporarily.• Nodes can fail (and may never recover).• Byzantine failures excluded.[Saito]Taming the Internet Service Construction BeastTaming the Internet Service Construction BeastSteven D. [email protected] Research Group (http://ninja.cs.berkeley.edu)The University of California at BerkeleyComputer Science DivisionPersistent, ClusterPersistent, Cluster--based Distributed Data Structuresbased Distributed Data Structures(in Java!)(in Java!)Gribble’s SlidesGribble’s SlidesSteve Gribble’s slides can be found on his web site at UW.http://www.cs.washington.edu/homes/gribble/pubs.htmlGo to “selected talks” and for the slides on DDS.I actually used his job talk slides with a few of my own mixed in on the basics of two-phase commit, which follow.It is important to understand the similarities/differences between Porcupine and DDS, and how they flow from the failure assumptions and application assumptions for each project.Committing Distributed TransactionsCommitting Distributed TransactionsTransactions may touch data stored at more than one site.Each site commits (i.e., logs) its updates independently.Problem: any site may fail while a commit is in progress, but after updates have been logged at another site.An action could “partly commit”, violating atomicity.Basic problem: individual sites cannot unilaterally choose to abort without notifying other sites.“Log locally, commit globally.”TwoTwo--Phase Commit (2PC)Phase Commit (2PC)Solution: all participating sites must agree on whether or not each action has committed.• Phase 1. The sites vote on whether or not to commit.precommit: Each site prepares to commit by logging its updates before voting “yes” (and enters prepared phase).• Phase 2. Commit iff all sites voted to commit.A central transaction coordinator gathers the votes.If any site votes “no”, the transaction is aborted.Else, coordinator writes the commit record to its log.Coordinator notifies participants of the outcome.Note: one server ==> no 2PC is needed, even with multiple clients.The 2PC ProtocolThe 2PC Protocol1. Tx requests commit, by notifying coordinator (C)C must know the list of participating sites.2. Coordinator C requests each participant (P) to prepare.3. Participants validate, prepare, and vote. Each P validates the request, logs validated updates locally, and responds to C with its vote to commit or abort.If P votes to commit, Tx is said to be “prepared” at P.4. Coordinator commits.Iff P votes are unanimous to commit, C writes a commit record to its log, and reports “success” for commit request. Else abort.5. Coordinator notifies participants.C asynchronously notifies each P of the outcome for Tx.Each P logs outcome locally and releases any resources held for Tx.Handling Failures in 2PCHandling Failures in 2PC1. A participant P fails before preparing.Either P recovers and votes to abort, or C times out and aborts.2. Each P votes to commit, but C fails before committing.Participants wait until C recovers and notifies them of the decision to abort. The outcome is uncertain until C recovers.3. P or C fails during phase 2, after the outcome is determined.Carry out the decision by reinitiating the protocol on recovery.Again, if C fails, the outcome is uncertain until C recovers.More SlidesMore SlidesThe following are slides on “other” perspectives on Internet server clusters. We did not cover them in class this year, but I leavethem to add some context for the work we did discuss.Clusters: A Broader ViewClusters: A Broader ViewMSCS (“Wolfpack”) is designed as basic infrastructure for commercial applications on clusters.• “A cluster service is a