CS514: Intermediate Course in Operating SystemsScalabilityDimensions of ScalabilitySlide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11ApproachesDangersTechnologies we’ve seenHow well do they scale?Web serverSlide 17Slide 18PorcupineSlide 20TransactionsSlide 22Slide 23Slide 24Slide 25Replicated DataAir Force JBIJBI has many subproblemsSlide 29Publish-subscribeUse Gryphon in JBI?JBI ScalabilityHow do people evaluate such questions?Two Side-by-Side Case StudiesBackgroundPoliticsTechnologyCore Technical Issue?Slide 39Why is this Hard?Slide 41Disaster StrikesSummary of SimplificationsCrash and BurnWhat came out?Contrast with FrenchSlide 47Virtual Synchrony ModelLearning by DoingTestingSoftware BugsAll of this worked!Scalability Conclusions?CS514: Intermediate Course in Operating SystemsProfessor Ken BirmanBen Atkin: TALecture 26: Nov. 28Scalability•We’ve heard about many technologies•Looked at implementations and features and reliability issues–Illustrate with real systems•But what about scalability?Dimensions of Scalability•We often say that we want systems that “scale”•But what does scalability mean?•As with reliability & security, the term “scalability” is very much in the eye of the beholderScalability•Marketing perspective:–Does a technology potentially reach large numbers of consumers?–Can the vendor sell it without deploying human resources in proportion to the size of the market?–Is the market accessible with finite resources?•Not our “worry” here in CS514, but in the real world you’ll need to keep this point of view in mind!Scalability•As a reliability question:–Suppose a system experiences some rate of disruptions r–How does r change as a function of the size of the system?•If r rises when the system gets larger we would say that the system scales poorly•Need to ask what “disruption” means, and what “size” means…Scalability•As a management question–Suppose it takes some amount of effort to set up the system–How does this effort rise for a larger configuration?–Can lead to surprising discoveries•E.g. the 2-machine demo is easy, but setup for 100 machines is extremely hard to defineScalability•As a question about throughput–Suppose the system can do t operations each second–Now I make the system larger•Does t increase as a function of system size? Decrease?•Is the behavior of the system stable, or unstable?Scalability•As a question about dependency on configuration–Many technologies need to know something about the network setup or properties–The larger the system, the less we know!–This can make a technology fragile, hard to configure, and hence poorly scalableScalability•As a question about costs–Most systems have a basic cost•E.g. 2pc “costs” 3N messages–And many have a background overhead•E.g. gossip involves sending one message per round, receiving (on avg) one per round, and doing some retransmission work (rarely)•Can ask how these costs change as we make our system larger, or make the network noisier, etcScalability•As a question about environments–Small systems are well-behaved–But large ones are more like the Internet•Packet loss rates and congestion can be problems•Performance gets bursty and erratic•More heterogeneity of connections and of machines on which applications run–The larger the environment, the nastier it may be!Scalability•As a pro-active question–How can we design for scalability?–We know a lot about technologies now–Are certain styles of system more scalable than others?Approaches•Many ways to evaluate systems:–Experiments on the real system–Emulation environments–Simulation–Theoretical (“analytic”)•But we need to know what we want to evaluateDangers•“Lies, damn lies, and statistics”–It is much to easy to pick some random property of a system, graph it as a function of something, and declare success–We need sophistication in designing our evaluation or we’ll miss the point•Example: message overhead of gossip–Technically, O(n)–Does any process or link see this cost?•Perhaps not, if protocol is designed carefullyTechnologies we’ve seen•TCP/IP and O/S message-passing architectures like U-Net•RPC and client-server architectures•Transactions and nested transactions•Virtual synchrony and replication•Other forms of multicast•Object oriented architectures•Cluster management facilitiesHow well do they scale?•Consider a web server•Life consists of responding to HTTP requests – RPC over TCP•Where are the costs?–TCP: lots of channels, raises costs•For example, “SO_LINGER” issue•Also uncoordinated congestion issue–Disk I/O bottleneck…Web server•Usual solution is to split server over many machines, spray requests•Jim Gray calls this a cloned architecture•Works best for unchanging data (so-called soft-state replication)Web server•Failure detection: a scaling limit–With very large server, failure detection gets hard•If a node crashes, how should we detect this?•Need for “witnesses”? A “jury”?•Notification architecture…•Modes of failure may grow with scaleWeb server•Sample scaling issue–Suppose failure detection is “slow”–With more nodes, we have•More failures•More opportunities for anomalous behavior that may disrupt response–Load balancing system won’t know about failures for a while… so it might send work to faulty nodes, creating a perception of down time!Porcupine•This system was a scalable email server built at U. Wash•It uses a partitioning scheme to spread load and a simple fault-tolerance scheme•Papers show near-linear scalability in cluster sizePorcupine•Does Porcupine scale?–Papers says “yes”–But in their work we can see a reconfiguration disruption when nodes fail or recover•With larger scale, frequency of such events will rise•And the cost is linear in system size–Very likely that on large clusters this overhead would become dominent!Transactions•Do transactional systems scale?–A complicated question–Scale in:•Number of users & patterns of use•Number of participating servers•Use or non-use of replication–Different mixes give different resultsTransactions•Argus didn’t scale all that well–This was the MIT system we discussed, with transactions in the language itself–High costs of 2PC and concurrency control motivated a whole series of work-arounds•Some
View Full Document
Unlocking...