Vi beskriver tillämpningar av en praktiskt taget synkron miljö för distribuerad programmering, som ligger till grund för en samling distribuerade programmeringsverktyg i 1SIS2-systemet. En praktiskt taget synkron miljö tillåter processer att struktureras in i processgrupper, och gör att händelser som sändningar till gruppen som en enhet, förändringar i gruppmedlemskap, och även migration av en aktivitet från en plats till en annan verkar ske omedelbart - med andra ord, synkront. En stor fördel med detta tillvägagångssätt är att många aspekter av en distribuerad ansökan kan behandlas självständigt utan att äventyra korrektheten. Dessutom kan användarkod som är utformad som om systemet var synkron ofta köras samtidigt. Vi hävdar att denna strategi för att bygga distribuerad och feltolerant programvara är enklare, mer flexibel och mer benägna att ge korrekta lösningar än alternativa tillvägagångssätt. Tänk på utformningen av ett distribuerat system för fabriksautomation, till exempel för VLSI chip tillverkning. Ett sådant system skulle behöva gruppera kontrollprocesser till tjänster som ansvarar för olika aspekter av tillverkningsförfarandet. En tjänst kan acceptera partier av chips som behöver fotografiska emulsioner, en annan övervaka transport av chips från station till station, etc. Inom en tjänst skulle algoritmer behövas för schemaläggning arbete, replikering data, coordiDetta arbete stöddes av Defense Advanced Research Projects Agency (DoD) under ARPA order 5378, kontrakt MDA903-85-C-0124 och N00140-87-C-8904, och av National Science Foundation under bidrag DCR-8412582. De åsikter, åsikter och slutsatser som finns i denna rapport är författarnas och bör inte tolkas som en officiell Department of Defense position, policy, eller beslut. Tillstånd att utan avgift kopiera hela eller delar av detta material beviljas under förutsättning att kopiorna inte görs eller distribueras för direkt kommersiell fördel, ACM-upphovsrättsmeddelandet och titeln på publikationen och dess datum visas, och meddelande ges om att kopiering sker genom tillstånd från Föreningen för datormaskiner. För att kopiera på annat sätt, eller för att återpublicera, krävs en avgift och / eller specfic tillstånd. nating åtgärder på fysiska separata platser, lastbalansering och dynamisk omkonfigurering av systemet efter att en komponent går ur linjen eller kommer tillbaka på linjen. Utgångspunkten för ISIS-projektet och detta dokument är att den befintliga programvaruutvecklingsmetoden är otillräcklig för att hantera denna typ av tillämpningar. Här lägger vi fram ett nytt tillvägagångssätt som gör det möjligt att dela upp ansökningarna i ortogonala komponenter som kan behandlas separat och på ett förvånansvärt "icke-distribuerat" sätt. Vår forskning syftar till att tillhandahålla en verktygslåda för distribuerad programmering för att hjälpa till att lösa de underproblem som oftast uppstår i distribuerade system. Varje verktyg består av en uppsättning subrutiner som kan anropas från applikationsprogram, i vissa fall förstärkt av ett distribuerat program som upprätthåller beständig tillståndsinformation. Användare utvecklar programvara genom att koppla samman icke distribuerade program med hjälp av verktygen. ISIS2 tillhandahåller verktyg för att initiera asynkrona åtgärder, uppdatera replikerade data utan blockering, erhålla ömsesidig uteslutning med hjälp av feltolerant replikerade semaforer, och många andra. Ett distribuerat program som använder replikerade data skulle bestå av en uppsättning konventionella program, som var och en utför subrutinsamtal till lämpliga verktyg för att få tillgång till sitt delade tillstånd. Den viktigaste frågan vid utformningen av verktygslådan är att se till att verktygen har ortogonal funktionalitet, eftersom det är denna aspekt som gör det möjligt för programmeraren att dela upp en applikation i komponenter som kan lösas självständigt och gradvis utvidgas till ett komplett system. En andra fråga gäller samstämmighet. För att fullt ut kunna utnyttja de möjligheter till samstämmighet som finns i ett distribuerat system måste processerna kunna fatta lokala beslut när det är möjligt, eftersom en process som måste samverka med andra innan ett beslut fattas skulle skjutas upp tills de svarar. För att ta itu med dessa frågor har vi ©1987 [Peterson] (som utvecklar mekanismer för att stödja asynkrona utföranden som uppvisar egenskaper som liknar virtuell synkronisering). Eftersom virtuell synkroni kombinerar ett begrepp om atomicitet med en orderbegränsning, är det också relaterat till transaktionell serialisering, även om ingenting som liknar "transaktionen" existerar i en praktiskt taget synkron inställning. Vad vi har gjort i 1SIS 2 projektet är i huvudsak att förena dessa begrepp, försvaga vissa aspekter som visade sig vara alltför begränsande, och optimera beteende i de vanliga situationer som uppstår när asynkron beräkning önskas och misslyckanden kan uppstå. Resultatet är ett system som kan tillfredsställa även krävande utövare som samtidigt är formellt rigorös. Detta dokument börjar med att utforska begreppet virtuell synkronisering och de sätt på vilka det återspeglas i gränssnitten som tillhandahålls av verktygslådan 1SIS 2. Vi illustrerar dessa mekanismer genom att undersöka den interna stegvisa utvecklingen av en ISIS 2-tillämpning och en typisk verktygslåda rutin. Vi undersöker sedan resultatfrågor. Virtuell synkronisering I detta arbete utgår vi ifrån att ett distribuerat system består av processer med separata adressutrymmen som kommunicerar över ett konventionellt LAN med meddelanden som passerar. Processer antas utföras på datorplatser. Enskilda processer och hela platser kan krascha; den tidigare typen av krasch antas upptäckas av vissa övervakningsmekanismer på platsen för processen, medan den senare endast kan upptäckas av en annan plats med hjälp av en timeout. Det antas att misslyckade processer inte skickar felaktiga meddelanden. Vårt system tolererar meddelandeförlust, men inte partitionera fel (där länkar som kopplar samman grupper av webbplatser misslyckas). Skiljedom kan få delar av vårt system att hänga tills kommunikationen är återställd. Vi räknar nu upp några av de specifika underproblem vi vill lösa i denna inställning; var och en av dessa motsvarar ett separat verktyg inom 1SIS 2. ofta önskvärt att strukturera ett system i "grupper" av (eventuellt icke-identiska) processer -- en sådan grupp skulle kunna genomföra en hög nivå abstraktion som emulsion insättningstjänst, eller en låg nivå en, som en replikerad dataobjekt. I idealfallet bör en sådan mekanism göra det möjligt för varje process att tillhöra flera processgrupper, tillhandahålla flexibla mekanismer för att gå med i och lämna grupper och vara billig. Det behövs också en möjlighet att kommunicera med medlemmarna i en grupp medan medlemskapet förändras. Bestämmer hur man ska svara på en begäran. När en grupp av processer tar emot en begäran måste en strategi utarbetas för att genomföra den. Processgruppsmekanismen bör göra det möjligt för en process att svara på en begäran med hjälp av endast lokal information (utan att köra något avtalsavtal mellan gruppens medlemmar), om det är praktiskt att göra det. Så mycket som möjligt måste formgivarna utnyttja den samstämmighet som finns tillgänglig i ett distribuerat system, till exempel genom att arrangera flera processer för att vidta åtgärder samtidigt, eller fortsätta att utföra asynkront efter att ha skickat ett meddelande för att informera andra processer om vissa händelser (utan att vänta på att meddelandet ska levereras). Synkronisering. På myntets baksida kommer processer som genomförs samtidigt att behöva låsa 124 och mekanismer för ömsesidig uteslutning för att undvika störningar mellan samtidiga aktiviteter. Dessa mekanismer måste också hantera misslyckandet med en process h01d-ring ett lås eller semafor, och med dödläge upptäckt. R e p l i c a t e d data. Många tillämpningar kräver effektiva mekanismer för att replikera data, på nivån för enskilda datastrukturer, och bland samarbetsvilliga men inte nödvändigtvis identiska processer. Upptäcka och reagera på ett misslyckande. Det krävs en mekanism för att upptäcka fel och informera berörda parter om ett fel. När t.ex. medlemmarna i en grupp samarbetar för att svara på en begäran från en uppringare, bör operativa medlemmar informeras om en medlem misslyckas, och uppringaren bör informeras om alla medlemmar misslyckas. Man skulle också vilja ha en försäkran om att ett meddelande från en misslyckad process aldrig kommer att försenas så länge som man kommer fram efter att misslyckandet redan har observerats. D y n a m i c omkonfigurering. Efter ett fel, återhämtning eller som svar på vissa typer av förfrågningar eller ändringar av systembelastningen kan det vara önskvärt att justera systemkonfigurationen. För att vara praktiskt måste detta så lite som möjligt påverka nya och pågående verksamheter. Om processer behöver återställa sitt tillstånd efter ett fel, behövs en mekanism för att skapa periodiska kontrollpunkter eller loggar som kan spelas upp på återhämtning. Det bör vara möjligt att utforma programvara som kan återhämta sig efter fel. Efter ett totalt misslyckande, där alla processer som utgör en applikation krasch samtidigt, behovet är att starta om hela programmet graciöst med hjälp av dess stabila tillstånd. Det andra och vanligaste problemet är att återhämta sig från ett partiellt fel, när en misslyckad process försöker återhämta sig medan resten av systemet fortfarande är i drift. Mekanismer behövs för att återinföra en sådan process i systemet och kanske för att överföra en del av det nuvarande systemet till det. Transaktioner. Program som hanterar delade komplexa diskbaserade datastrukturer eller distribuerade sådana behöver ibland sätt att komma åt och uppdatera dem som en transaktion. Även om fokus för ISIS 2 ligger på icke-transaktionsprogramvara kommer sådana program att behöva stödjas, och de bör kunna använda resten av ISIS 2 också. I den utsträckning det är praktiskt måste IS1S2-systemet skydda sig själv och sina kunder mot felaktiga kunders agerande. Överensstämmelse. Genomträngande av ovanstående diskussion är en implicit uppfattning om konsekvens. Trots osäkerheten i systemstaten som införts genom samstämmighet och misslyckanden, behöver konstruktören veta att det finns någon mening i vilken de operativa processerna i systemet kommer att tillfredsställa en global korrekthetsbegränsning. Så långt det är möjligt, med tanke på lokalt korrekta algoritmer skulle man vilja veta att ett globalt korrekt system kommer att bli resultatet av sammankopplingen av dem. I synnerhet bör samstämmighet inte medföra subtila korrekthetsproblem, inte ens när processerna ibland är ur synk med andra processer som de behöver interagera med. Det som gör det svårt att lösa problem i en konventionell miljö är den asynkrona spridningen av information mellan processer. I avsaknad av delat minne, det enda sättet en process kan lära sig om beteendet hos andra processer är genom meddelanden som den tar emot. Eftersom meddelandeöverföringstiderna varierar från process till process och ändras med belastningen på systemet, kan meddelanden som rör en enda händelse komma fram till olika processer vid olika tidpunkter och i olika order i förhållande till andra meddelanden. Dessutom kan en processs misslyckande endast upptäckas när en timeout inträffar medan man väntar på ett meddelande från den, och kan därför inte skiljas från ett tillfälligt kommunikationsfel eller en överbelastning. Allt detta gör det svårt för en uppsättning processer att upprätthålla en konsekvent syn på varandras status, eller för dem att samordna sina åtgärder på ett effektivt sätt. Vi anser att de nuvarande distribuerade programplaneringsmetoderna är otillräckliga mot bakgrund av dessa farhågor. De flesta distribuerade system är baserade på fjärrprocedursamtal (RPC) med timeout för feldetektering [Birrell]: en mekanism som ger nästan inget stöd för någon av de frågor som nämns ovan. Den nuvarande trenden är att vända sig till inhägnade transaktioner [Moss] eller atomiska åtgärder för feltolerans, men dessa ger bara en begränsad lösning. Transaktioner underlättar hanteringen av stabil lagring, men de erbjuder ingen hjälp med att integrera ett återvunnet tillstånd med det nuvarande tillståndet för resten av systemet. I stora system, transaktionell konvergens kontroll kan vara alltför restriktiv: många av de beteenden som listas ovan är i sig icke-serializable. Dessutom tenderar långa beräkningar att låsa delade datastrukturer under längre perioder, vilket försenar andra beräkningar. Vi hävdar att transaktioner är den lämpliga mekanismen in situa-125 som innebär kortlivad tillgång till delade data som lagras på en disk. Alternativ behövs i andra situationer. En väg ut ur de problem som räknas upp i Sec. 2.2 skulle vara att basera systemet på atomiska multicast-protokoll.1 En multicast är atomär om alla dess operativa destinationer tar emot meddelandet om inte avsändaren misslyckas, i vilket fall antingen alla tar emot det eller ingen gör det. Dessutom ser alla mottagare samma meddelande order. Vi måste utvidga denna definition av atomicitet till att omfatta fallet med en multicast vars destinationer omfattar processgrupper med medlemskap som kan komma att förändras. En sådan multicast bör logiskt sett levereras till det gruppmedlemskap som gällde när den åberopades, men detta kanske inte är det som är aktuellt vid tidpunkten för leveransen. Vi kommer därför att kräva att leveransen av en atomisk multicast alltid slutförs innan en grupp som utgör en del av dess destinationer tillåts ta emot en ny medlem. Vi påpekar att många befintliga atomiska multicast protokoll antar statiska uppsättningar av destinationer som är kända när protokollet initieras [Chang] [Cristian] [Schneider-b]. Vi kommer att använda termen synkron till en beskrivning av en miljö där multisändningar är atomiska och händelser såsom meddelandeleveranser, process- och platsfel, återvinningar och andra händelser som beskrivs nedan, sker i samma ordning överallt. I en synkron miljö kan mekanismer som löser alla de problem som nämns ovan genomföras utan större svårigheter. Processer kan enkelt upprätthålla en konsekvent syn på varandra, eftersom varje process alltid befinner sig i samma punkt i sin beräkning som någon annan. Synkronisering, när det behövs, är enkel av samma anledning. Processfel kan hanteras konsekvent eftersom alla operativa processer lär sig av ett fel samtidigt, i samma beräkningssteg. Tyvärr är detta oöverkomligt dyrt. Problemet är att det kräver att alla meddelandeleveranser ska beställas i förhållande till varandra, oavsett om tillämpningen behöver detta för att upprätthålla enhetligheten. De protokoll som behövs för att uppnå en så stark beställning är alltid dyra, både i termer av 1Detta är en multi'cast till en uppsättning processer, inte en sändning till alla maskiner anslutna till ett lokalt nätverk med en hårdvara sändningskapacitet. Sådan hårdvara kan dock utnyttjas för att optimera genomförandet av multicast-protokollet [Babaoglu]. Antalet skickade meddelanden och hur lång tid det tar att vänta på att de ska upphöra. Detta leder oss till begreppet virtuell synkronisering. Grundidén är att bevara illusionen att händelser sker ögonblickligen, men att använda olika kommunikationsimperialer som tvingar fram svagare leveransbeställningar i situationer där applikationen eller verktyget är okänsligt för leveransordern. Till exempel kan man föreställa sig en multicast primitiv som levererar meddelanden i den ordning som den sändande processen skickade dem, men är helt oordnad i förhållande till multisändningar från andra ursprung. En process med privat tillgång till en replikerad FIFO kö kunde använda denna primitiva för att uppdatera den, eftersom uppdateringar skulle behandlas i samma ordning på alla kopior. Å andra sidan, om mer än en process kan utföra operationer i kön, denna primitiva skulle vara otillräcklig, eftersom uppdateringar från olika processer kan bearbetas ur ordning. Fördelen med att använda denna primitiva i det förra fallet är att det sannolikt kommer att ha ett billigare genomförande än en fullständig atomisk multicast, och ändå ger graden av synkronisering som behövs för den applikationen. En praktiskt taget synkron körning kännetecknas således av följande egenskap: Det kommer att framstå för alla observatörer -- vilken process som helst med hjälp av systemet -- att alla processer observerade samma händelser i samma ordning. Detta gäller inte bara för meddelanden leverans händelser, men också för misslyckanden, återhämtningar, förändringar grupp medlemskap, och andra händelser som beskrivs nedan. Som vi kommer att se i nästa avsnitt, gör detta att man kan göra apriori antaganden om de åtgärder andra processer kommer att ta, och förenklar algoritmisk design. Kom ihåg att den faktiska sekvensen av händelser ibland kommer att skilja sig från process till process i situationer där de resulterande åtgärderna är samma (eller semantiskt likvärdiga) som de som skulle ha tagits om händelsesekvenserna faktiskt hade varit identiska. Vi kommer att utnyttja detta för att öka samstämmigheten. Ovanstående diskussion är så fokuserad på atomisk multicasting att man kan dra slutsatsen att detta är allt 1SIS 2 ger. I själva verket betraktar vi atomiska multisändningar som bara en av en familj av verktyg som alla ger praktiskt taget synkront beteende. Det finns till exempel ett verktyg som stöder massöverföringar av information mellan processer på ett sätt som ser ögonblickligt ut. Ytterligare 126 verktyg gör uppdateringar av replikerade data verkar vara ögonblickliga. De faktiska implementeringarna av verktygen är dessutom mycket samtidiga och asynkrona. Huvudpunkten är att de kan användas som om de vore synkrona. Dessutom uppfyller verktygen vårt mål om ortogonalitet. Efter att ha utvecklat ett program med hjälp av replikeringsverktyget kan man utöka det med hjälp av verktyget för statsöverföring: dessa två typer av "instantantiska" händelser garanteras att inte strida. Dessa och andra verktyg beskrivs i nästa avsnitt. I detta avsnitt granskas några av de verktyg som stöds av 1S1S 2, som beskriver både rollen för varje verktyg och den betydelse i vilken dess beteende är praktiskt taget synkront. Vårt mål med att välja denna uppsättning verktyg var att göra det möjligt för en att utveckla applikationer med hjälp av en liten uppsättning verktyg, och sedan lägga till funktionalitet genom att åberopa ytterligare verktyg, gör endast mindre ändringar i den befintliga koden. Vi förväntar oss att verktygen växer till en omfattande samling som täcker de flesta av de problem som ofta uppstår i distribuerade system. Vi börjar vår diskussion med den lägsta nivån av systemet, som ger kommunikation primitiva, och sedan arbeta upp till högre nivå verktyg, varav många använder dessa primitiva. Förutom i avsnitt 3.11 begränsar vi oss till verktyg som är fullt funktionsdugliga (från och med augusti 1987). De tre primitiva som beskrivs nedan, ABCAST, CBCAST och GBCAST har beskrivits i [Birman-a]. Genomförandet är trogen det som står i det dokumentet och diskuteras inte här. Läsare som känner till de primitiva kan vilja hoppa över till Avsnitt 3.2. ABCAST primitivt. En ofta förekommande situation innebär ett antal processer som samtidigt utför processer som kommunicerar med en delad distribuerad resurs, vars interna tillstånd är känsligt för den ordning i vilken förfrågningar kommer fram till olika delar av resursen. Till exempel måste samtidig verksamhet på en delad replikerad FIFO kö tas emot och behandlas på alla kopior i samma ordning. Detta beställa krav motsvarar den primitiva vi kallar ABCAST, som levererar meddelanden atomärt och i samma ordning överallt. Om alla förfrågningar om köoperationer överförs med hjälp av denna primitiva, skulle enqueuing-operationerna se synkrona ut i förhållande till andra sådana operationer i samma kö. CBCAST primitivt. Korrektheten hos en replikerad FIFO-kö beror på att ordningen för all verksamhet som utförs på den bevaras. Tänk i stället på en tjänst som upprätthåller en uppsättning replikerade variabler för flera kunders räkning. Varje kund har exklusiv tillgång till sina variabler. Även om tjänsten sannolikt kommer att ta emot förfrågningar samtidigt från många kunder, är det bara nödvändigt att bevara beställningsordern från samma kund. Det är uppenbart att en multicast primitiv svagare än ABCAST skulle kunna användas i detta fall. Å andra sidan, på grund av fjärrprocedursamtal, en beräkning kan spänna över flera processer, och därför meddelanden som skickas av samma klient kan komma från flera olika processer. Förutom att beställa alla multicasts, finns det ett sätt att karakterisera beställningskravet som gäller i detta fall? Lamport konstaterade att i ett distribuerat system är beställningen av händelser meningsfull endast när information kunde ha strömmat från den ena till den andra genom någon kedja av meddelandeöverföringar, mottagningar och mellanliggande lokala beräkningar [Lamport-b]. Härav följer att vi kan definiera två multicast-händelser som potentiellt orsakssamband om information om den första kunde ha nått den punkt där den andra startades innan den initierades där. Lägg märke till att två multicaster som utfärdas genom en enda beräkning enligt denna definition alltid kan ha ett orsakssamband. Detta leder oss till den primitiva kallas CBCAST, som garanterar att om några anrop av CBCAST är potentiellt kausalt relaterade, motsvarande meddelanden levereras överallt i ordningen för anrop. Detta är en konservativ 2 strategi för att se till att alla genuint relaterade operationer kommer att ses i rätt ordning.
Samordning uppnås automatiskt genom användning av en delad tuple utrymme, där två implementationer testades-en centraliserad en, och en decentraliserad en baserad på begreppet virtuell synkronisering REF.
Exploiting virtual synchrony in distributed systems
{'venue': "SOSP '87", 'journal': None, 'mag_field_of_study': ['Computer Science']}