CS514: Intermediate Course in Operating SystemsApplications of these ideasSlide 3Specific topics we’ll coverSolutions “inspired” by paradigmsLet’s start with 2PC and transactionsProblem: Pictorial versionIssues?2PC is a good match!SolutionLow availability?Next example: AuditingAuditingUses for auditingPractical worriesPros and consNext in our list?Distributed Garbage CollectionSlide 19Slide 20Slide 21Slide 22Review: what makes it hard?Conceptual solutionChallengesOptions?More practical issuesOther consistent snapshot uses?Review of practical challengesSlide 30Leaders in snapshot protocolsFault-tolerance concernsSlide 33Concurrently running instancesIn your banking project…Last topic for todayeScience systemsThe fault-tolerance problemSlide 39How they approach itThis is a big project at CornellTask migrationScenarioSlide 44What makes this hard?What makes it hard?Slide 47Why is this hard to do?Could one “move” a TCP connection?Migrating a TCP connectionTCP connection stateGeneralizing the ideaFault-tolerant TCP connectionSlide 54Recap and summaryWhat next?CS514: Intermediate Course in Operating SystemsProfessor Ken BirmanVivek Vishnumurthy: TAApplications of these ideasOver the past three weeks we’ve heard aboutTransactionsLogical time, consistent cutsDistributed checkpoint mechanismsAgreement protocols, such as 2PC and 3PCBefore we drill down and learn more mechanisms like these… what good are these things?Applications of these ideasToday, we’ll review some practical applications of the mechanisms we’ve studiedEach is representative of a class Goal is to illustrate the wide scope of these mechanisms, their power, and the ways you might use them in your own workSpecific topics we’ll coverTransactions on multiple serversAuditing a systemDetecting deadlocksFault-tolerance in a long-running eScience applicationDistributed garbage collectionRebalancing objects in a clusterComputing a good routing structureMigrating tasks and TCP connections from server to serverSolutions “inspired” by paradigmsThe solutions we arrive at won’t always use the earlier protocol in a literal wayThink of “paradigms” or “templates”When they match a problem…… you can specialize them to create a good solutionLet’s start with 2PC and transactionsThe problem:Some applications perform operations on multiple databasesWe would like a guarantee that either all the databases get updated, or none doesThe relevant paradigm? 2PCProblem: Pictorial versionGoal? Either p succeeds, and both lists get updated, or something fails and neither doespEmployeesdatabaseCoffeefundCreate new employeeAdd to 3rd-floor coffee fundIssues?P could crash part way through…… a database could throw an exception, e.g. “invalid SSN” or “duplicate record”… a database could crash, then restart, and may have “forgotten” uncommitted updates (presumed abort)2PC is a good match!Adopt the view that each database votes on its willingness to commitUntil the commit actually occurs, update is considered temporaryIn fact, database is permitted to discard a pending update (covers crash/restart case)2PC covers all of these casesSolutionP runs the transactions, but warns databases that these are part of a transaction on multiple databasesThey need to retain locks & logsWhen finished, run a 2PC protocolUntil they vote “ok” a database can abort2PC decides outcome and informs themLow availability?One concern: we know that 2PC blocksThe failure scenario isn’t all that rareOptions?Could use 3PC to reduce this risk, but will pay a cost on every transactionOr just accept the riskCan eliminate the risk with special hardware but may pay a fortune!Next example: AuditingOur goal is to “audit” a systemInvolves producing a summary of the stateShould look as if system was idleOur options?Freeze the whole system, then snapshot the state. This is very disruptiveOr could use the Chandy/Lamport “consistent snapshot” algorithmAuditingAssets Liabilities$1,241,761,251.23$875,221,117.17Uses for auditingIn a bank, may be the only practical way to understand “institutional risk”Need to capture state at some instant in time. If branches report status at closing time, a bank that operates world-wide gets inconsistent answers!In a security-conscious system, might audit to try and identify source of a leakIn a hospital, want ability to find out which people examined which recordsIn an airline, might want to know about maintenance needs, spare parts inventoryPractical worriesSnapshot won’t occur at a point in real timeCould be noticeable to certain kinds of auditorsIn some situations only a truly instantaneous audit can be accepted, but this isn’t commonWhat belongs in the snapshot?Local states… but handling messages in transit can be very hard to doWith Web Services, some forms of remote server calls are nearly transparent!Pros and consImplementing the algorithm is only practicalIf we can implement lossless FIFO channels…… and can intercept and log messages… and in this way capture a “fake” instant in time,So if all of that works… we’re goldenBut doing so may be challengingWS doesn’t really have channels. So how can we interpose a logging mechanism between processes?We’ll be forced to implement a “user-level” version of the algorithm by structuring the application itself appropriatelyThis is one of our project assignmentsNext in our list?Distributed garbage collectionArises more and more commonly in big systems!The problem: applications create objects and pass one-another URLsWe would like to delete objects if there are no URLs pointing to them in the systemWe’ll assume that these URLs all live in machine-readable objects in the file systemAssume we know “root” object in each file system (and are given a list of file systems)Distributed Garbage Collectionroot rootDistributed Garbage CollectionMake a list of candidates at each siteroot rootDistributed Garbage CollectionRemove items from that list if there is a live pointer to them from a remote siteroot rootDistributed Garbage CollectionDelete dead itemsroot rootDistributed Garbage CollectionObject being moved can confuse our search. So can a crashed file serverroot rootReview: what
View Full Document
Unlocking...