Slide 1Snapshot: Replication “models”Replication protocolsToday: RicochetReplication Models: SummaryKen BirmanCornell University. CS5410 Fall 2008.Snapshot: Replication “models”By now we’re starting to see that “replication” comes in many flavorsNo model: UDP multicast (IPMC), Scalable Reliable Multicast, TCP. Often called “best effort” but not always clear what this really means. In practice, loss occurs on sockets, not network. SRM uses timesouts, NAKs, retransmission to recover from loss, but with timeout at the core, model is like TCP –weak semantics, State machine model (GMS views, Paxos). Needs strong determinism. No partitioning (split brain). Group membership confers strong semantics. Can’t guarantee termination (FLP)Even stronger: Byzantine (State Machines + malicious nodes), Transactional (for databases with ACID properties)Probabilistic: Ricochet, Gossip: Converge towards guaranteesReplication protocolsType Capsule Summary Pros ConsUDP multicast Fast, pretty reliable unless overloaded. But not always supported (“fear of multicast”, WAN issues)Raw speed: send 1, get n-1 deliveries for freeRouter load, “n:1” effect (instability), no flow controlSRM (Scalable Reliable Multicast)A reliable protocol that runs over UDP multicast, well known and fairly popular. eBay uses it internally.Uses UDP multicast for NAK, retransmissionsGreat when all goes well, but prone to sudden destabilizationGMS view updt Usually 2-phase, hence “pretty fast”. Can’t partition (no split brain)State machine model appliesSlower than UDP multicast, scales poorlyVsync Hosted within GMS, like a reliable UDP multicast + view synchronyLike state machine but more flexibilityUser needs to take cs5410 first! And can it scale?Paxos Like GMS view update, several versions. One has a very elegant proof of safetyState machine modelSlower than UDP multicast, scales poorlyByzantine These assume that at most t of N members of the service are malicious. Trusts clients.State machine modelHardens service but not its clientsRicochet Seeks rapid, probabilistically reliable deliveryVery stable, scalableNot as strong as vsync or state machine modelTransactions ACID database guarantees (1-copy serializability)Famous model Very poor scalabilityGossip Convergent probabilistic guarantees, constant overhead costsVery robust at constant (low) cost, scales wellToo slow for some usesToday: RicochetRemainder of today’s lecture will look at RicochetTime-critical multicast protocolMay become a standard in Red Hat Linux and other data center / enterprise settingsGreat stability and scalability, quasi-realtime guaranteesPaper in NSDI 2007 has