1CS514: Intermediate Course in Operating SystemsProfessor Ken BirmanVivek Vishnumurthy: TAQuicksilver: Multicast for modern settingsn Developed by Krzys Ostrowskin Goal is to reinvent multicast with modern datacenter and web systems in mindTalk outlinen Objectiven Two motivating examplesn Our idea and how it “looks” in Windowsn How Quicksilver works and why it scalesn What next? (perhaps, gossip solutions)n SummaryOur Objectiven Make it easier for people to build scalable distributed systemsn Do this byn Building better technologyn Making it easier to usen Matching solutions to problems people really are facingMotivating examplesn Before we continue, look at some examples of challenging problemsn Today these are hard to solven Our work needs to make them easiern Motivating examples:(1) Web 3.0 – “active content”(2) Data center with clustered servicesMotivating example (1)Web 1.0… 2.0… 3.0…n Web 1.0: browsers and web sitesn Web 2.0: Google mashups and web services that let programs interact with services using Web 1.0 protocols. Support for social networks.n Web 3.0: A world of “live content”Motivating example (1)2Motivating example (1)“Publish-Subscribe” Services (I)Motivating example (1)Observations?n Web 3.0 could be a world of highly dynamic, high-data rate pub-sub n But we would need a very different kind of pub-sub infrastructuren Existing solutions can’t scale this way…n … and aren’t stable at high data ratesn … and can’t guarantee “consistency”Motivating example (1)Motivating example (2)n Goal: Make it easy to build a datacentern For Google, Amazon, Fnac, eBay, etcn Assume each center n Has many computers (perhaps 10,000)n Runs lots of “services” (hundreds or more)n Replicates services & data to handle loadn Must also interconnect centersMotivating example (2)Today’s prevailing solutionClientsMiddle tier runs business logicBack-end shareddatabase systemMotivating example (2)Concerns?n Potentially slow (especially after crashes)n Many applications find it hard to keep all their data in databasesn Otherwise, we wouldn’t need general purpose operating systems!n Can we eliminate the database?n We’ll need to replicate the “state” of the service in order to scale upMotivating example (2)3Response?n Industry is exploring various kinds of in-memory database solutionsn These eliminate the third tierMotivating example (2)A glimpse inside eStuff.comEventing middlewareLBserviceLBserviceLBserviceLBserviceLBserviceLBservice“front-end applications”Web content generation Web services dispatchersMotivating example (2)Front endFront endxyzApplication structure…Front endService-oriented client system issues parallel requests…Data center dispatcher parallelizes request among services within centerServer partitions requests and then uses clusters for parallelization of query handlingMotivating example (2)x y zx y zx y zx y zx y zx y zx y zA RAPS of RACS (Jim Gray)n RAPS: A reliable array of partitioned subservicesn RACS: A reliable array of cloned server processesKen searching for “digital camera”Pmap “D-F”: {x, y, z} (equivalent replicas)Here, y gets picked, perhaps based on loadA set of RACSRAPSMotivating example (2)A-CD-F“RAPS of RACS” in Data CentersQuery source Update sourceServices are hosted at data centers but accessible system-widepmappmappmapServer pooll2P mapLogical partitioning of servicesLogical services map to a physical resource pool, perhaps many to oneData center AData center BOperators can control pmap , l2P map, other parameters. Large-scale multicast used to disseminate updatesMotivating example (2)Our examples have similaritiesn Both replicate data in groupsn … that have a state (evolved over time)n … and a name (or “topic”, like a file name)n … updates are done by multicastsn … queries can be handled by any membern There will be a lot of groupsn Reliability need depends on application4Our examples have similaritiesn A communication channel in Web 3.0 is similar to a group of processesn Other roles for groupsn Replication for scale in the servicesn Disseminating updates (at high speed)n Load balanced queriesn Fault-toleranceSounds easy?n After 20 years of research, we still don’t have group communication that matches these kinds of uses!n Our solutionsn Are mathematically elegant…n But have NOT been easy to usen Sometimes perform poorlyn And are NOT very scalable, either!Integrating groups with modern platforms… and make it easy to use!n It isn’t enough to create a technologyn We also need to have it work in the same settings that current developers are expectingn For Windows, this would be the .net frameworkn Visual studio needs to “understand” our tools!New Style of ProgrammingTopics = ObjectsTopic x = Internet.Enter(“Game X”);Topic y = x.Enter(“Room X”);y.OnShoot += new EventHandler(this.TurnAround);while (true)y.Shoot(new Vector(1,0,0));Or go further…n Can we add new kinds of live objects to the operating system itself?n Think of a file in Windowsn It has a “type” (the filename extension)n Using the type Windows can decide which applications can access itn Why not add communications channels to Windows with live content & “state”n Events change the state over time5Exploiting the Type SystemTyped Publish-SubscribeVision: A new style of computingn With groups that could represent…n A distributed service replicated for fault-tolerance or availability or performancen An abstract data type or shared objectn A sharable mapped filen A “place” where things happenThe “Type” of a Group means “The properties it supports”Examples of propertiesn Best effortn Virtual synchronyn State machine replication (consensus)n Byzantine replication (PRACTI)n Transactional 1-copy serializability6Virtual Synchrony ModelcrashG0={p,q} G1={p,q,r,s} G2={q,r,s} G3={q,r,s,t}pqrstr, s request to joinr,sadded; state xfert added, state xfert requests to joinp fails... to date, the ... to date, the only only widely adopted model for consistency andwidely adopted model for consistency andfaultfault--tolerance in highly available networked applicationstolerance in highly available networked applicationsQuicksilver systemn Quicksilver: Incredibly scalable infrastructure for publish-subscriben Each topic is a groupn Tightly integrated with Windows .netn Tremendous performance and robustnessn Being developed step by stepn
View Full Document
Unlocking...