Samenvatting Gedistribueerde Systemen Dumon Willem 2009 - 2010
Hoofdstuk 1
Basis 1.1 1.1.1
Karakterisatie v/e Gedistribueerd Systeem Terminologie
Gedistribueerd systeem = software/hardware componenten, netwerk & communicatie, co¨oordinatie via message passing → concurrency, gn globale klok & onafhankelijke failures ⇒ verz onafh pc’s die overkomen als 1 systeem Waarom: • prijs/performantie ratio: nt lineaire curve maar stijgt zr snel, meerdere CPU’s → performantie verdubbelen vr dubbele kost als nt tevl overhead (1 pc → 100 pc’s → datacentrum) • zinvol vr bepaalde domeinen (versch geldautomaten met CPUs die netwerken met bank, grafische processing, wrgeven v computer animaties) • geografische spreiding: elektronische whiteboards, distributed document systems, audio/video conferencing, email, file transfer, gaming • betrouwbaarheid: wnnr e machine uitvalt blijft totale systeem intact • incrementele groei • gebruik v Remote Services: web browsing, remote file acces • mobiliteit : laptops, Palms, WAP, phones Gedistribueerde functies: • Communicatiestructuur: SW vr ondersteuning v/e groep pc’s verbonden via netwerk • Netwerkbesturingssysteem: elke pc eigen OS, netwerkBS = aanvulling op lokale • Gedistribueerd OS: gemeenschappelijk OS gedeeld dr e netwerk v pc’s • Gedistribueerd algoritme: verz op elkaar afgestemde algoritmen die gebruik maken v message passing om een bepaald doel samen te bereiken (bvb voorkomen dat versch processen dezelfde resources tegelijkertijd gebruiken = mutual exclusion) Interconnectie v CPU’s: Flynn Taxonomy • SISD = Single Instruction Stream, Single Data Stream (uniprocessor) • SIMD = SI, Multiple Data Stream (arrayprocessor) • MIMD = Multiple Instruction Stream, MD (parallel & distributed systems) 1
– Memory: multiprocessors (shared memory, single virtual address) & multicomputers (private memory, private address space) – Interconnection: single network bus / switched – Coupling: Tight-coupled (short message delays, high BW, total system reliability) & Loosely-coupled (longer message delays, lower BW, realibility expectations on failures) Focus op switched, loosely-coupled multicomputers Internet = intranets geconnecteerd via backbones, met bep services (WWW, email, filetransfer) Intranet = verz LAN’s geconnecteerd via backbones, via routers aan internet, eigen security policy & admin Mobile computing = transparante toegang tt intranets, toegang tt lokale resources aan remote site ⇒ Location-aware computing Ubiquitous computing = kleine computerapparaten overal, communicatie tss apparaten Nieuwe toepassingen: • Sensor netwerken, Animaties, Multi-Agent systemen (Robotic Soccer) • Grid Computing: pc-kr8 even toegankelijk maken als elektriciteit, open standaarden, pcresources niet geadministreerd • Cluster Computing: cluster = set v nodes op 1 locatie, grid = meerdere clusters en andere resources (netwn , opslag) • Cloud Computing: Infrastructure as a Service (IaaS), Platform as a Service (PaaS) & Software as a Service (SaaS) • Parallel Computing: alle cpu’s toegang tt shared memory om info uit te wisselen • Distibuted Computing: elke CPU eigen (‘distributed’) geheugen, info uitwisselen dr message passing
1.1.2
Software design v/e Gedistribueerd Systeem
1. Heterogeniteit: versch nivo’s (netw, OS, HW, programmeertalen,...) ⇒ Middleware: Java RMI, CORBA → implementatie v/e hoger nivo API 2. Openheid: open systemen laten uitbreidingen v/h systeem toe zonder onderbrekingen en/of duplicatie v bestaande services door uniform communicatie mechanisme & gepubliceerde en standaard interfaces ⇒ open systemen met heterogene HW mogelijk 3. Security: aanvallen tgn vertrouwelijkheid/privacy, integriteit v berichten, gebruikersauthenticatie, beschikbrheid (onbevoegd gebruik v bronnen: bestanden & printers, Denial of Service (server blokkeren dr overspoelen met requests & mobiele code k¯ onbevoegde operaties uitvoeren)) 4. Schaalbaarheid: kost resources, performantieverlies, uitputting resources (cf IP-adressen), performantie bottlenecks voorkomen ⇒ replication & partioneren v data, caching & meerdere servers Schalen met zelfde SW als nu? 5. Optreden v falingen (failures): zijn partieel → moeilijk te detecteren/behandelen ⇒ detecteren (vb checksums), maskeren (vb message retransmission), tolereren (vb browser: server not available), herstellen (vb save & restore state) & redundancy: replicating services 6. Concurrency: versch clients willen simultaan toegang tt gedeelde resource ⇒ gelijktijdige verwerking (nt triviaal & synchronisatie technieken (vb semaphoren)) 2
7. Transparantie: systeem = transparant vr feature als deze nt observeerbaar is vr gebruiker v systeem (vb rlogin: lokaal vs remote computer, Java RMI: lokaal vs remote object, GSM: locatie = transparant & emailadress: netw-locatie transparant) → uniformiteit belangrijk vr gebruiker
1.2
Gedistribueerde Architectuur Modellen
1. Software Layers - Lagenmodel: door met layers & services te werken w ¯ complexiteit v/e systeem doorbroken: • Layer = groep gerelateerde functionele componenten • Service = functionaliteit die aangeboden w ¯ a/d volgende layer Oorspronkelijk: layers of modules in 1 enkele computer ↔ Nu: services/requests tss processen in dezelfde of versch computers 2. Middleware: • Verbergen v heterogeniteit, vrziet abstracter communicatiemodel (remote method invocatie (RMI, CORBA, DCOM), groepscommunicatie, notificatie v events, partitioneren & replication v shared data) & vrziet infrastructurele services (naming, transactions, persistent storage) • Verz gereedschappen die voorziet i/e uniforme manier & stijl v toegang tt systeembronnen op alle platforms • Biedt programmeurs mogelijkheid om toepassingen te bouwen die er nt all1 hetzelfde uitzien & werken mr ook dezelfde manier vr toegang tt gegevens gebruiken, onge8 locatie ervan • Beperking: end-to-end argument (communicatie zovl mog tss eindptn ); sommige aspecten vereisen echter support o/d applicatie-laag 3. Design: meest evidente aspect v gedistribueerd systeemdesign = verdeling v verantw-hn tss componenten (appies , servers, andere processen...) & de plaatsing v/d componenten over computers i/h netwerk ⇒ be¨ınvloedt rechtstreeks performantie, betrouwbrh & veiligheid v/h systeem 4. Overzicht modellen: • Client-Server: clients meestal pc’s/werkstations vr 1 gebruiker, bieden eindgebruiker zr gebruiksvriendelijke interface. Elke server verzorgt verz gedeelde gebruikersdiensten vr client, biedt vl clients de mogheid toegang tt zelfde databank te delen & maakt gebruik v/e kr8ig pc-systeem vr beheren v/d databank mogelijk server k¯ ook client zijn v/e andere server (vb webserver = client v fileserver) server & client moeten enkel zelfde communicatieprotocollen gebruiken, rest mag verschillen (vb OS, platform) vb databankserver: transacties (query - respons), server verantw vr onderhoud databank, verbinding server-client via software wrmee verzoeken w ¯ verstuurd (vb SQL) – One-Tier Appie architectuur: pc verbonden via netwerk aan mainframe dat instaat vr presentatie, processing & data – Two-Tier Appie architectuur (a) Thin Client: client enkel verantw vr presentatie (UI) → k¯ bottleneck maken v mainframe die alles moet processen (b) Fat Client: client verantw vr presentatie & processing → updaten v code in clients zr moeilijk & nt gebruiksvriendelijk want versch systemen mog
3
– Multi-Tier Appie architectuur: SW v/d toepassing verdeeld over 3 types machines: gebruikersmachine (= thin client, UI), Middle-Tiermachine (application server, processing, doorgeefstation, omzetten procollen & versch databronnen samenvoegen & integreren) & Backend server (database server) ⇒ betere performantie & flexibeler ↔ communicatie tss 3 partijen: transacties? – Service ge¨ımpl dr meerdere servers: ofwel objn verdelen over versch servers, ofwel kopie op elke host (betere perfomantie, beschikbrh & fout tolerantie) – Proxy servers & caches: bestandscache gebruikt vr opslag v recent gebruikte bestandsrecords, consistent als exacte kopie bevatten v externe gegevens, technieken vr bestands-vergrendeling (mutual exclusion, mr 1 client gelijktijdig per bestand) Web Caching Protocol: browser/proxy valideert resource i/d cache dr vgling met origineel i/d web-server o/h moment dat e clientrequest toekomt. Web server kent resources ‘approximate expiry time’ toe, bij webserverresponse w ¯ huidige servertijd & expirytime meegegeven → browser berekent leeftijd v/e resource – Mobiele code: clientrequest → krijgt appletcode trug → client interageert met applet ⇒ snelle interactietijd & applets gelimiteerde access tt lokale bronnen (veiligh%) Mobiele agenten = werkend programma (code & data) dat zich verplaatst i/e netw & autonoom taken uitvoert, meestal in opdracht v andere processen ⇒ flexibel, besparen op communicatiekost ↔ evt bedreiging vr veiligheid v/d server, lokale omgeving afschermen (vb crawlers, web servers) & agenten zelf ook kwetsbaar, zonder toegang gn taken afwerken. netwerk pc = OS en appies at runtime downloaden ↔ thin client = UI op client, appies op remote pc uitvoeren spontane netwerken ivm mobiele toestellen: services ontdekken → registration service (services publiek maken) & look-up service (services ontdekken adhv bep vereisten) Client-Server: 1voudig o/t zetten, services & onderhoud centraal ↔ slechte schaling, altijd via breedbandverbinding • Peer-to-Peer netwerken: alle processen gelijkaardige rol, werken samen om gedistr processen uit te voeren, gn onderscheid client-server, bronnen delen tss groot # versch pc’s ⇒ complex Design Requirements: • Performantie: snelle, consistente antw-tijd (caching & replication), throughput & balanceren v workload • QoS: betrouwbrh, veiligh & aanpasbaarheid • Afhankelijkhn : correcth, veiligh, omgaan met fouten & applies moeten k¯ verder werken ook met fouten in HW, SW of netwn
1.2.1
Fundamentele eigenschn v gedistribueerde architecturen
Architecturen bestaan uit set v processen die onderling communiceren dr sturen v berichten over pc-netwerk, bel eign : sync, delays, failures, security: • Interaction Model: behandelt performantie & plaatsen v tijdslimieten Processen interageren dr sturen v berichten ⇒ communicatie (information flow) & co¨ordinatie (synch & ordening). 2 belangrijke factoren: 1. performantie v communicatie: comm-kanaal opzetten dmv streams of simpele message passing over netw ⇒ performantie criteria: latency (= delay tss start transmissie dr ene process & begin ontvangst dr andere), bandbreedte (totale # info dat overgebr8 k¯ w ¯ i/e gegeven tijd, comm-kanalen die hetzelfde netw gebruiken moeten beschikbare BW delen) & jitter (variatie in tijd nodig om e serie v berichten over te brengen) 4
2. notie v globale tijd: elke pc eigen interne klok, w ¯ dr lokale processen gebruikt → wnnr 2 processen hun klok lezen op zelfde moment k¯ dit toch verschillen (= computer clock drift: elke computer klok vertoont e verschil met e referentie-klok), zelfs wnnr klokken op zelfde moment ge¨ınitialiseerd w, ¯ zal tijd verschillen want drift is verschillend per pc ⇒ correcties: GPS met accuraatheid v ≈ 1µs 2 varianten: 1. Synchrone Gedistr Systemen (moeilijk te verwezenlijken): tijd om executiestap uit te voeren heeft boven- & ondergrens, bericht bezorgen over kanaal k¯ i/e eindige begrensde tijd & elk proces heeft lokale klok met begrensde drift 2. Asynch GS: gn enkele grens op procesuitvoeringssnelheid, delay v berichten & klok drift-rates. Real-Time ordening v events: alle events & volgorde bijhouden (adhv oorspronkelijke tijdstip v event) → juiste ordening ook als versch klokken • Failure Model: specifieert fouten die k¯ optreden in processen – Omission failure: iets verloren gegaan (vb communication omission failure = dropping messages: onvoldoende buffer ruimte in sender/receiver/gateway & network transmission error, send-omission-, receive-omission-failure) – Arbitrary failure: proces stuurt willekeurige berichten op willekeurige tijdstippen → proces stopt of neemt foute stap, moeilijk te behandelen
Figuur 1.1: Omission & Arbitraty failures – Timing failure
Figuur 1.2: Timing failures
5
Failures maskeren: mogelijk betrouwbare services te bouwen met componenten die onderhevig zijn aan failures, kennis v bep failures v/e component k¯ e andere service toelaten om deze failure te maskeren (verstoppen of omzetten nr e failure v/e ander type). vb: replication → als 1 crasht nt alles crasht, checksum: zet arbitrary om in omission (maskeren corrupte berichten) & procescrash maskeren dr proces te herstellen met externe info (vb status vr crash) • Security Model: bespreekt mogelijke bedreidingen vr processen & communicatiekanalen, veiligheid v/e gedistr syst k¯ bekomen w ¯ dr beveiligen v processen & kanalen die gebruikt w ¯ vr interactie & dr objn die ze bevatten te beveiligen tgn nt bevoegde toegang (dmv access rights, identiteit altijd nagaan & rechten checken, zowel client die server nagaat als server die client nagaat) De vijand modelleren: k¯ berichten met valse source genereren, berichten kopi¨eren en herzenden, DoS & mobiele code ⇒ Encryptie, authenticatie, identiteit kennen v/d ‘principal ’ wrvoor proces w ¯ uitgevoerd
1.3
TCP/IP
• Protocol = verz regels & formaten nodig vr comm tss processen met welbepaald doel, omvat specificatie v/e sequentie v berichten die uitgewisseld moeten w ¯ & formaat v/d data, w ¯ ge¨ımpl dr gekoppelde softwaremodules in zender & ontvanger & laten toe dat versch SW componenten v/h gedistr syst onafh k¯ ge¨ımp w ¯ i versch programeertalen op pc’s met mogelijk versch data representaties • Layer: levert service naar bovenliggende layer & breidt service v onderliggen layers uit • Open System Interconnectie (OSI) Model: frameworks wrin protocollen k¯ gedefinieerd w, ¯ gn definitie vr e bep protocol
Figuur 1.3: OSI vs DoD Model – Fysieke laag: fysieke interface tss zendapparaat & transmissiemedium of netwerk, houdt rekening met kenmerken medium, aard signalen & overdr8snelheid – Netwerklaag: uitwisseling v gegevens tss eindsysteem & netwerk, specifieke software = afh v/h type netw & versch standaarden (Circuit-, Packet Switching & LAN = ethernet) – Internetlaag: procedures nodig om data door versch gekoppelde netwn te laten passeren, w ¯ gebruikt vr padbepalings-ftie & in routers – Transportlaag: garandeert dat alle gegs bij toepassing o/d bestemming arriveren & dat gegs in juiste volgorde arriveren (mst toegepaste protocol = TCP) – Applicatielaag: logica nodig vr ondersteuning v verschgebruikerstoepassingen (vb bestandsoverdracht) • IPv6 = functionele verbeteringen tov IPv4: ontworpen vr hoger wordende snelheden v netwn & vr mix v data (stilstaand & bewegend bld), 128bits adres ipv 32bits 6
• Transport Control Protocol TCP: betrouwbaar end-to-end delivery protocol, basisidee = Zender zendt pakket → Ontvanger stuurt bij ontvangst ACK → Wnnr zender gn ACK ontvangt, herstuurt hij het pakket – Flow control: zorgen dat snelle zender ontvanger niet vooruitloopt ⇒ # verstuurde pakketten na elke ‘round trip time’ (RTT) = 1 window, als gn verloren pakketten → window +1 per RTT ↔ wel verloren pakketten: window gehalveerd per RTT – TCP gebruiken als alle pakketten moeten toekomen & delay nt uitmaakt ⇒ email, web browsing (meerdere TCP connecties per pagina) & file downloads – CONS, error-checks vertragen overdr8 & stream based • User Datagram Protocol UDP: gn garantie ivm aankomst/volgorde, enkel inhoud, CLNS, packet based, wel snelle zend rate → Real Time appies cf VoIP
1.4
Interprocess Communication
• Middleware = RMI & RPC, request/reply protocol, (un)marshalling & external data representation. Zit tss appie -laag & UDP/TCP • Karakteristieken: zenden/ontvangen omvat synch & datarepresentatie, zenden = bericht aan remote queue toevoegen, ontvangen = v lokale queue halen • Synchroon: zowel send als receive zijn blocking: send w8 op corresponderende receive & receive w8 op aankomst bericht, vr elk bericht synch • Asynch: send = non-blocking, receive k¯ blocking of non-bl zijn: non-blocking = niet w8en, buffer k¯ in 8rgrond gevuld w ¯ → ontvanger o/d hoogte brengen. Java mbv multithreads = 1voudiger dan inkomend bericht uit control flow halen • Bestemmingen: bericht nr IP & poort (= bestemming binnen pc) sturen – poort: 1 receiver, meerdere zenders mogelijk, meerdere poorten per proces mogelijk, transparantie k¯ voorzien w ¯ door ondermeer ‘name server/binder’ & location-independent identifiers mappen nr locaties – proces: single entry point per proces vr alle messages – mailbox: k¯ vele receivers hebben & message queue • Betrouwbaarheid: failures mogelijk (corrupted messages, duplicated messages, omission: loss of messages, messages out of order, receive-process failure) ⇒ betrouwbare communicatie = nt-beschadigd bericht, in juiste volgorde, zonder duplicaten ↔ perfecte betrouwbare communicatie k¯ vaak nt gegarandeerd w ¯ • Sockets: eindpunt vr comm tss 2 processen: poort + inetadres, receive-methode bevat ook poort & inetadres v zender om te k¯ antwen , poort duidt appie aan, inetadres (IP) duidt hostsystemen aan 1. Streamsockets: werken met TCP, geeft een verbindingsgerichte, betrouwbare gegevensoverdracht (alle blokken gegarandeerd afgeleverd in juiste volgorde) – communicatiekanaal gecre¨eerd tss sockets: client zendt request tt communicatie nr Server-poort → Server accepteert request → typisch cre¨eert Server e nieuwe thread die verdere comm afhandelt. – berichtgrootte: appie k¯ zelf kiezen hoeveel data o/d stream k¯ geschreven w, ¯ de onderliggende implementatie v TCP beslist hoeveel data gecollecteerd w ¯ vraleer te zenden
7
– berichten: acknowledgement scheme & retransmitting, flow control, duplicatie & volgorde, synch semantics (non-blocking send, uitgezonderd vr flow control (als buffers v zender/ontvanger vol) & blocking receive) – gebruikt als betrouwbare message service: garantie op integriteit, geldig (checksums, sequence numbers, timeouts & heruitzending) ⇒ HTTP, FTP, SMTP – wel gn betrouwbare communicatie → als verbroken connecties – overhead vgl met UDP: buffering, connectie opzetten = extra berichten, zenden = ACK trugsturen, overhead aanvaardbr als slechts enkel bericht versturen 2. Datagram sockets: werken met UDP, bezorging 6= gegarandeerd: – berichten: gelimiteerde pakketgrootte (IP laat slechts groottes toe < 216 , meeste omgevingen laten slechts <2 13 (8kB), grotere pakketten w ¯ getrunceerd) & gn conversie → bit transmission – non-blocking send & blocking receive – time-outs: gebruiker k¯ e timeout specifi¨eren o/d receive operatie – receive from any: receive geeft poort + inetadres v zender (sockets k¯ ook gebonden w ¯ aan remote (IP-adres + poort)) – onbetrouwbare berichten service: verloren, verkeerde volgorde, duplicaten maar gn beschadigde berichten advh checksum → enkel inhoud gegarandeerd, transport nt ⇒ gebruik als occasionele fouten aanvaard – overhead vr betrouwbare message delivery: opslaan v state info (source & destination), extra berichten die verzonden moeten w ¯ & latency vr de zender • Data representatie: nt alle pc’s representeren nummers op zelfde manier (big-endian ↔ littleendian), progr-nivo: info in data structuren → info in berichten = sequentie v bytes ⇒ Marshalling = info omzetten nr externe datarepresentatie, transmissie data, converteren nr lokale vorm bij ontvangst = unmarshalling → info w ¯ in formaat v zender doorgestuurd + indicatie v gebruikte formaat vb: CORBA CDR (Common Data Repres = binair formaat, externe data representatie vr gestructureerde & primitieve data types & ondersteunt versch programeertalen), Java Object Serialisatie (binair formaat, objn omgezet nr extern formaat, type info meegestuurd & all1 Java) & XML (txt-formaat vr gestructureerde data, data vrstellen in web based client server appies & type info meegestuurd (namespaces)) • CORBA = Common Object Request Broker Architecture: ORB = client helpen methode aanroepen in remote object (lokaliseren, activeren & request communiceren)
8
Hoofdstuk 2
Remote Communication 2.1
Communicatie patronen
2.1.1
Client Server Communicatie
• Request/Reply Protocol: synchroon, connectie nt altijd nodig, gn flow control, evt. (un)marshalling • TCP vaak overkill: reply = enkel ACK = redundant, grootte datapakket gelimiteerd, ontime communicatie ⇒ verbinding leggen = overkill, gn stream/flow control nodig ⇒ UDP met geschikte bufferlengte • Failure Model: omission failures, gn volgorde → time-outs, gn dubbele requests & history v berichten zodat herzenden 6= volledige operatie herdoen • vb HTTP: content negotiation, password style authentication, connectie openen → request → reply → sluiten. Get, Head, Post, Put, Delete, Options, Trace • RPC exchange protocols: R = Reply, RR = Request/Reply & RRA = Request/Reply/Ack
2.1.2
Groepscommunicatie
• multicast = bericht v/e bepaald proces w ¯ nr elk proces behorende tt groep processen gestuurd • nuttig als fault tolerance gebaseerd op replicated services, zoeken v discovery services in spontane netwerken, betere performantie dmv replicated data & propagatie v event notifications • IP Multicast: – multicast groep gespecifieerd dr klasse D inetadres: 1e 4 bits = 1110 – dynamisch membership – enkel via UDP op appie -nivo – bijvoegen a/d groep dr socket a/d groep te hangen, mbv Session Directory programma (ook opstarten groep) – multicast routers & Time To Live TTL – multicast adres allocation permanent/tijdelijk – varianten: reliable multicast, totally ordered multicast
9
2.2
Remote Procedure Call RPC
Gedistr Object systemen: objn mappen op gedistr services, services modelleren als objn • location & access transparancy (zelfde methodes lokaal als remote), overerving & polymorfisme • gedistr object = interface + service implementatie die 1 of meerdere interfaces impl • zelfde als gwne objn : k¯ gebruikt w ¯ als parameter & return value, k¯ geactiveerd w, ¯ subklassen mogelijk & synchroon geactiveerd • MAAR – state access enkel via methoden – gn constructors – invocation: maybe, at-least-once & at-most-once – transparantie: verstoppen (un)marshalling, message passing, locatiebepaling & contacteren v remote-object → latency, failures – parameter passing: by reference ipv by value → nieuwe exception types • implementatie adhv ‘Object Bus’ = Stubs (vervangen remote object, voeren RPC’s uit, stub in client = proxy, stub in server = skeleton) & Broker (= middlewarelaag, verdeelt invocations) • Comm-module: voert request/reply protocol uit volgens juiste semantiek (at-most-once,...) • Remote Reference module: verantw vr local/remote object references (adressen geven) • Servant: instantie v klasse v/e remote object, handelt remote request af (in server)
Figuur 2.1: Implementatie RPC
2.3
Remote Method Invocation RMI
• Proxy ≡ lokaal object mr forward alle berichten nr remote object, zorgt vr transparantie nr client & verzorgt (un)marshalling • Server heeft e dispatcher & skeleton vr elke klasse v/e remote object: dispatcher ontvangt request, kiest juiste methode i/d skeleton adhv/d methodID → skeleton unmarshalt request & activeert juiste methode i/d servant • dynamische proxies/skeletons: interfaces mss nt beschikbaar bij compilen → dynamische invocatie via generieke doOperation & dynamisch downloaden v klassen in clients & servers • andere: Binder (cf RMIRegistry ≈ name server vr RMI), Persistent Object Stores, Location Sevices & Distributed garbage collection (vb remote algoritme dat lease time v object bijhoudt, als client lease time nt vernieuwt wordt obj-referentie verwijderd, co¨operatie met lokale GC) 10
2.3.1
Java RMI
Figuur 2.2: Implementatie RMI • RMIRegistry: simpele naming service aan serverzijde, client k¯ zo referentie nr serverobject bekomen • Java.RMI.Naming: naming class, methodes om referenties in RMIRegistry op te slaan/af te halen – void rebind(String name, Remote obj): gebruikt dr server om remote object te registeren – void bind(String name, Remote obj): alternatief – void unbind(String name, Remote obj): binding verwijderen – Remote lookup(String name): dr client om remote object op te zoeken, referentie w ¯ teruggegeven
2.3.2
Corba RMI
Object Management Group OMG: non-profit org, gesponsord dr 500 orgies , aanpak tt standardisatie, globale doel = theorie & impl v object-technologie promoten vr ontwikkeling v gedistr systn Common Object Request Broker Architecture: taal onafh & platform afh (ORB impl vr elk nieuw platform vereist) ⇒ A homogenous view on a heterogeneous world
Figuur 2.3: Corba architectuur • Interface Definition Language IDL: beschrijft ifaces v lokale objn op taalonafh manier, w ¯ gecompileerd naar bepaalde taal dr IDL compiler, uitkomst hiervan gwn compileren = objn , clients moeten zich hieraan houden om met serverobj te k¯ commn 11
• architectuur, incl services (Naming , Notification , Event - & Security Service) • CDR: externe date representatie • Internet InterORB Protocol IIOP = protocol wrmee ORB’s communiceren over TCP • appie initialiseert ORB en hft interne Object Adapter (reference count, lifetime, policies) • Object = programmeerentiteit bestaande uit identiteit, interface en implementatie (defineert de operaties die de IDL ondersteunt) • Servant = implementatie v/e object • Client = entiteit die operatie invokeert • Object Request Broker ORB: – Object bus, middleware: transformatie v procesdata v/nr byteinfo die verstuurd w ¯ over netw (marshalling/serialization) adhv IDL vorm v gwn object met methodes, e lokaal obj maakt verbinding met ORB wrdoor zijn methodes remote accessible w, ¯ ORB verkrijgt adres vr dit (nu remote) obj & zorgt vr interactie tss versch appies in client/server. – voordelen: statische/dynamische method invocations, high-level language binding, zelfbeschrijvend (Interface Repository), lokaal/remote transparantie, ingebouwde security/transacties, polymorfe berichten & co¨existence met bestaande systemen, transparantie nr hostlocatie, OS & programmeertaal – onderdelen: ORB kern, IDL, taalmappings, iface repository, proxies/skeletons, dynamische invocatie & dispatch, object adapters & IIOP • IDL stubs: statische iface v object services (gedefinieerd adhv IDL), ≈ proxy vr remote server objn • IDL Skeleton: statische ifaces vr elke ge¨exporteerde service (dr server), skeletons gecre¨eerd dr IDL compiler, zend method invocations nr servant, unmarshalt args v requests & marshalt exceptions/resultaten in reply • Dynamic Invocation Interface DII: API vr dynamische constructie v object invocations, als client nts weet over object dat het wil invokeren, lijst v parameters marschallen, functie w ¯ benoemd en request for service verstuurd naar object server. methoden ontdekken die pas at-runtime k¯ toegepast w, ¯ ondernemen v remote call & opvangen v resultaten. • Interface Repository: bevat type informatie over alle geregistreerde interfaces (+ ondersteunde methodes & vereiste parameters), raadplegen wnnr client gn proxy bevat vr remote referentie v/e obj. Repository ID = type identifier v/e iface • Dynamic Skeleton Interface DSI: run-time binding mechanisme vr servers die methode calls moeten opvangen v componenten die gn IDL-gebaseerde stubs hebben, inspecteert inhoud v/e request om doelobject te vinden, de opgeroepen methode & de bijhorende args • The Object Adapter OA: – behandelt services requests vr server objn (cf remote reference & dispatcher module) via skeleton – biedt run-time environment om server objn (servants) te instanti¨eren, requests door te geven & object Id’s toe te kennen – (de)activeert servants wnnr nodig → performantie%
12
– geeft elk CORBA object unieke naam → deel v remote object referentie – CORBA object = geregistreerd via OA, die via object table CORBA objn mapt nr servants – Portable Object Adapter POA laat appies & servants toe v ORB’s ge¨ımpl dr versch ontwikkelaars • Implementation Repository: verantw vr activeren v geregistreerde services op aanvraag & lokaliseren v aanwezige actieve services, OA-naam gebruikt, entry bevat OA-naam, pad nr object impl, hostname & poortnummer server • General Inter-ORB Protocol GIOP: CDR, specificaties vr request/reply proctol onafh v OS. = IIOP request/reply als over TCP
13
Hoofdstuk 3
Gedistribueerd Procesbeheer 3.1
Procesmigratie
= overbrengen v voldoende hoeveelh procestoestand v/d ene nr de andere pc om dat proces uit te voeren o/d doelpc. 1. Argumenten: • Delen v belasting, afweging overhead ↔ winst • Prestatie v communicatie: processen die intensief met elkr communiceren k¯ nr zelfde knooppt w ¯ verplaatst, maar voert proces gegevensanalyse uit op ≥1 bestanden > proces zelf ⇒ proces nr bestandlocatie verplaatsen • Beschikbaarheid: als langdurig proces wil overleven, mogelijk verplaatsen (geplande uitschakeling systeem, gemelde storingen) • Gebruik v speciale mogelijkheden: HW of SW v bep knooppt nodig 2. Mechanismen: • begin migratie: wie begint = afh v doel: – module v OS begint als verdelen v belasting = doel, module mt proces/processn onderbreken, signaliseren & communiceren met andere modules – proces begint als doel = bep HW/SW/bronnen gebruiken, proces k¯ zichzelf migreren & mt o/d hoogte zijn v gedistr systeem • wat migreren: proces nt kopi¨eren, enkel procesbeeld (= minstens procescontroleblok PCB, 1voudig te verplaatsen) → proces verwijderen & opnieuw cre¨eren, koppelingen mt andere processen bijwerken, adresruimte v proces verplaatsen: – ‘eager-all ’: voll adresruimte overgezet → gn enkel spoor v proces op oud syst als adresruimte zr groot & proces grootste deel nt nodig → onnodige belasting – ‘pre-copy’: proces ng steeds uitgevoerd op bronknooppt terwijl adresruimte w ¯ gekopieerd → gewijzigde pagina’s ng eens kopi¨eren, proces minder lang bevroren & minder lang w8en op uitvoering tijdens migratie – ‘eager-dirty’: all1 pagina’s in hoofdgeheugen & gewijzigde overzetten → extra’s op aanvraag overzetten & bronpc voortdurend betrokken bij levenscyclus v proces – ‘copy-on-reference’: pag’s all1 overgezet als ernr w ¯ verwezen → laagste overhead & snel – ‘flushing’: pag’s v proces w ¯ gewist uit geheugen v bronpc dr ‘vuile’ pag’s nr hdd te schrijven & nodige pag’s w ¯ bij bronpc v/d hdd gehaald als nodig ipv uit hoofdgeh → gn pag’s v gemigreerde proces mr in geh v bronpc → geheugenblok direct vr andere processn gebruiken 14
• berichten & signalen: mechanisme nodig om uitstaande berichten & signalen tijdelijk o/t slaan, nadien naar nieuwe bestemming sturen, evt tijdje info over doorsturen op bronpc bewaren vb migratie (OS AIX v IBM): (a) proces besluit te migreren → selecteert doelpc & verstuurt taakbericht (b) ontvangstzijde: kernelserverproces cre¨eert kindproces & geeft info dr nr bronpc (c) nieuw proces haalt gegevens over v oude pc (d) oorspr proces w ¯ ingelicht als migratie voltooid, zend voltooiingsbericht nr nieuw proces & vernietigt zichzelf 3. Onderhandelen over migratie Migratiestrategie, scheduling op lange termijn & geheugentoewijzing = verantwh v hulpprogramma Starter, elk Starter-proces bestuurt cluster & 2 Starter-processen moeten het eens zijn over migratiebeslissing 4. Ontruiming Stel pc nt gebruikt → processen migreren nr die pc → gebruiker meld aan → processen lozen om antwoordtijd te garanderen aan gebruiker → processen trug migreren nr bronpc 5. Pre¨ emptief - nt pre¨ emptief: pre¨emptieve procesoverdr8 bij gedeeltelijk uitgevoerde processen & als enkel creatie v proces al voltooid, rest ng nt nt-pre¨emptieve procesoverdr8 als uitvoering ng nt gestart (gn procestoestand emigreren), nuttig vr verdelen v belasting ↔ reageert trager op veranderingen v systeembelasting
3.2
Gedistribueerde globale toestanden
OS k¯ onmogelijk huidige toestand v alle processen in gedistr.syst. kennen ↔ proces k¯ huidige toestand v alle processen op lokale systeem kennen & externe processen kennen all1 info over toestand via berichten (= info uit verleden!) Voorbeeld slides! → termen: • Kanaal = tussen 2 processen als deze berichten uitwisselen • Toestand v/e proces = reeks berichten die via kanalen dr proces zijn verstuurd & ontvangen • Momentopname = snapshot: registreert toestand v/e proces • Globale toestand = gecombineerde toestand v alle processen • Gedistribueerde momentopname = verz momentopnames, 1 per proces globale toestand = consistent als ∀ procestoestand (snapshot) wrin de ontvangst v/e bericht is vastgelegd, het versturen v dat bericht is vastgelegd i/d procestoestand v/h proces dat het bericht hft gestuurd ⇒ vb slides: inconsistent omdat M3 ng nt is verstuurd bij snapshot SA maar wel ontvangen w ¯ bij Sc (fig a), consistent omdat M3 wel al verstuurd bij SC (fig b, ontvangst ng nt geregistreerd bij SA mr nt belangrijk) Algoritme vr gedistr. momentopname: alg v Chandy & Lamport • elementen: processen (p, q,...) met inkomende & uitgaande kanalen, markeerberichten = markers & 2 soorten regels (ontvangen & zenden v markers) • start: bep proces start dr zichzelf te registreren & marker te sturen nr alle uitgaande kanalen
15
• 2 regels: markering ontvangen (vb p ontvangt marker v q over kanaal c) & wnnr versturen i f ( p h e e f t z i j n s t a a t nog n i e t g e r e g i s t r e e r d ) p r e g i s t e e r t z i j n s t a a t Sp ; p r e g i s t r e e r t de t o e s t a n d v/h inkomend k a n a a l c a l s l e e g ; p s t u u r t de marker door naar a l l e buren v i a u i t g a a n d e k a n a l e n ; p a c t i v e e r t h e t ontvangen v markers o v e r a n d e r e k a n a l e n else p r e g i s t r e e r t de t o e s t a n d v/h k a n a a l c a l s de r e e k s v b e r i c h t e n ontvangen v a n a f Sp end i f
Algoritme eindigt bij bep proces als marker via alle inkomende kanalen ontvangen
3.3
Gedistribueerde mutual exclusion
proces tijdelijk privilege geven (privilege = recht om gedeelde resource te gebruiken) 1. Concepten: • dwingend: slechts 1 proces v alle processen met kritieke sectie (KS) vr gedeelde bron/object w ¯ tegelijkertijd i/d KS toegelaten • veiligheid: (a) proces dat stopt in zijn nt-KS moet dat doen zonder andere processen te verstoren (b) proces dat toegang wenst tt zijn KS mag nt ∞ w ¯ vertraagd → gn deadlock & uithongering • levendigheid: als gn enkel proces in zijn KS → elk proces dat toegang tt KS verzoekt krijgt zonder vertraging toegang • orde & fairness: (a) gn veronderstellingen gebruiken over relatieve snelheden v processen of # processen (b) proces bevindt zich slechts beperkte tijd in zijn KS 2. versch benaderingen vr gedistr algoritmen: • gecentraliseerd: 1 centraal knooppt vr toewijzen v toegang tt alle gedeelde objn – all1 centrale knooppunt neemt beslissingen over toewijzen v systeembronnen – alle benodigde info w ¯ verzameld i/h centrale knooppt, incl info over identiteit & locatie v alle systeembronnen & toewijzingsstatus v elke systeembron ⇒ overzichtelijk & 1voudig te constateren of wederzijdse uitsluiting nageleefd ↔ als centrale knooppt problemen → wederzijdse uitsluiting (tijdelijk) nt nageleefd • gedistribueerd → voorwaarden: – alle knoopptn bevatten gemiddeld dezelfde hoeveelh info – elk knooppt ziet maar deel v/h totale systeem & moet obv die info beslissingen nemen (want info soms ng onderweg dus info in knooppt nt volledig) – alle knoopptn zelfde verantwrdelijkh vr uiteindelijke beslissing – uitvallen v/e knooppt leidt doorgaans nt tt uitvallen v totale systeem – gn globale, gemeensch klok vr reguleren v tijdstippen wrop gebeurtenissen plaats vinden 3. Gebeurtenissen rangschikken: • tijdsrangschikking v gebeurtenissen = belangrijk vr wederzijdse uitsluiting & deadlocks ↔ beperking: gn gemeensch klok of synchr-manier v lokale klokken
16
• mogelijks vertraging tss tijdstip wrop gebeurtenis zich voordeed & tijdstip wrop gebeurtenis w ¯ waargenomen (o/e ander systeem) • gebrek in synchr k¯ leiden tt verschillen i/h lezen v/d klok op uiteenlopende systn • event (gebeurtenis) = actie die plaatsvindt o/e lokaal systeem (vb proces betreedt/vrlaat KS) maar processn communiceren dmv berichten → events koppelen aan berichten ¯ gerangschikt & fysieke klokken w ¯ nt • ⇒ Tijdstempeling: events i/e gedistr.syst. w gebruikt – – – – –
elk systeem i i/h netwerk beschikt over lokale teller Ci , functioneert als klok bericht = (m, Ti , i): message + tijdstempel v bericht (= Ci ) + id v zender per verzonden bericht (dr systeem i) → Ci + + (v´o´or verzending) bij ontvangen bericht (in systeem j) → Cj = max[Cj , Ti ] + 1 2 berichten zelfde tijdstempel → ordenen op locatie (i < j)
Algoritme werkt ondanks verschillen in overdr8stijden tss systemen ↔ toegepaste volgorde komt per definitie nt over1 met chronologische volgorde MAAR volgorde bij elk proces wel zelfde 4. Gedistribueerde wachtrij: • Systeem bestaat uit N knoopptn (allemaal uniek nr & netw volledig gemaasd), elk knooppt bevat 1 proces dat wederzijdse uitsluiting aanvraagt • Berichten w ¯ in zelfde volgorde ontvangen als verstuurd & w ¯ binnen bep tijd afgeleverd • Alle locaties beschikken over kopie v dezelfde w8rij • Proces neemt pas toewijzingsbeslissing obv eigen w8rij als het bericht heeft ontvangen v alle andere knoopptn om er zeker v te zijn dat gn ouder bericht, dan bericht bovenaan eigen wachtrij, nog onderweg is Versie 1 = Lamport: – array q met 1 vermelding per locatie: q[j] bevat altijd bericht v Pj , j=1..N – 3 soorten berichten: (Request, Ti ,i), (Reply,Tj ,j),(Release,Tk ,k) – Algoritme: Stap 1: (Request, Ti ,i) door Pi , neemt dit op in eigen array q[i] & verstuurt bericht nr alle andere processen Stap 2: Pj ontvangt bericht, stelt q[i]=(Request, Ti ,i). Als q[j] gn verzoekbericht bevat stuurt Pj (Reply,Tj ,j) naar Pi (waardr gn oudere verzoekberichten onderweg zijn bij een beslissing) Stap 3: Pi heeft toegang tt de bron als q[i] het oudste verzoekbericht bevat (in elk proces zelfde → mutual exclusion) & alle andere berichten in q zijn jonger dan bericht in q[i] (→ Pi = o/d hoogte v alle verzoeken) Stap 4: Pi geeft bron vrij door bericht (Release,Ti ,i), dit w ¯ opgenomen in q[i] Stap 5: Pj ontvangt (Release,Ti ,i) & vervangt q[i] Stap 6: Pi ontvangt (Reply,Tj ,j) & vervangt q[j] ⇒ eerlijk, mutual exclusion, gn starvation & gn deadlock. 3*(N-1) berichten Versie 2 = Ricart & Agrawala: elimineren v Release-berichten Stap 1: Pi stuurt (Request,Ti ,i) & set q[i] Stap 2: Pj ontvangt (Request,Ti ,i) → regels: A. als Pj in KS: stel reply uit B. als Pj nt w8 op toegang tt KS: (Reply,Tj ,j) sturen C. als Pj w8 op toegang tt KS & verzoek is ouder: stel reply uit en set q[i] D. als Pj w8 op toegang tt KS & verzoek is jonger: (Reply,Tj ,j) sturen & set q[i] 17
Stap 3: Pi heeft toegang tt bron (= k¯ KS betreden) als elk ander proces heeft geantwoord Stap 4: Pi verlaat KS → stuur uitgestelde replies ⇒ eerlijk, mutual exclusion, gn deadlock & gn starvation. 2*(N-1) berichten ⇔ elk proces moet andere processen kennen & betrouwbare communicatie vereist 5. Doorgeven v tokens: Token = object dat op 1 moment slechts dr 1 proces in bezit k¯ zijn, proces dat token heeft k¯ KS betreden zonder toestemming. Als KS verlaten → token doorgeven aan ander proces • token[k] = tijdstempel v laatste keer dat token Pk bezocht • request[k] = tijdstempel v laatste verzoek dr Pk • Stappen: Stap 1: token initieel willekeurig toegekend Stap 2: toegang tt KS dr Pi als i over token beschikt, als nt over token beschikt → request nr alle processen Stap 3: Pj verlaat KS → token toekennen aan ander proces request doorlopen in volgorde j+1,j+2,...,1,2,...,j = ring based → token nr proces Pk wrvoor request[k] > token[k] N-1 berichten vr requests + 1 bericht om token door te geven = N berichten voldoet aan vw 1 & 4 v voorwaarden om gedistr algoritme te zijn 6. Voting algoritme v Maekawa: communicatie met slechts deelverz v alle processen moet volstaan → proces dat in KS wil gaan, moet voldoende stemmen verzn ⇒ voting set: • Vi = voting set vr Pi • ∀ i,j: Vi ∩ Vj 6= ∅ • | Vi | = K • Pj zit in M voting sets • optimale oplossing: K ∼
√
N &M=K
Bij i n i t i a l i s a t i e s t a t e := RELEASED; v o t e d := FALSE ; Pi w i l t o e g a n g t t KS s t a t e := WANTED; r e q u e s t s t u r e n naar a l l e p r o c e s s e n i n (Vi−Pi ) ; wachten t t (# r e p l i e s = (K−1) ) ; s t a t e := HELD; Pj k r i j g t een r e q u e s t v Pi i f ( s t a t e = HELD o r v o t e d = TRUE) queue r e q u e s t v Pi z o n d e r t e antwoorden else s t u u r antwoord naar Pi v o t e d := TRUE; end i f a l s Pi z i j n KS v e r l a a t s t a t e := RELEASED; M u l t i c a s t r e l e a s e naar a l l e p r o c e s s e n i n (Vi−Pi ) ; Pj o n t v a n g t een r e l e a s e v Pi i f ( r e q u e s t q u e u e != l e e g ) remove 1 e u i t queue ( s t e l Pk ) s t u u r r e p l y naar Pk v o t e d := TRUE; else v o t e d := FALSE ; end i f
18
deadlock mogelijk → Lamport tijdstempel toevoegen aan requests, laagste tijdstempel w ¯ 1st √ √ geprocessed, om toegang te krijgen tt KS 2* N berichten, bij verlaten KS N berichten Crash v proces in andere voting set k¯ getolereerd w, ¯ betrouwbare communicatie vereist
3.4
Gedistribueerde deadlock
1. Voorwaarden: • Wederzijdse uitsluiting: systeembron k¯ mr dr 1 proces tegelijk w ¯ gebruikt ¯ • Vasthouden & wachten: proces k toegewezen systeembronnen vasthouden terwijl het w8 o/h toewijzen v andere bronnen • Geen pre¨emptieve onderbreking: proces k¯ nt w ¯ gedwongen systeembron o/t geven • Cirkelvormig wachten: gesloten cirkel v processen, waarbij elk proces minstens 1 bron vasthoudt die nodig is vr volgende proces i/d cirkel 2. vb: Phantom Deadlock: 3 processen w8en op elkaars bronnen, P3 geeft zijn bron vrij en stuurt bericht daarvoor, maar vraagt ook de bron v P1 . • vrijgeefbericht w ¯ 1st ontvangen → gn probl • request-bericht w ¯ 1st ontvagen → ‘deadlock’ 6= echte deadlock want gn globale toestand 3. Deadlock voorkomen: • cirkelvormig w8en vrkomen dr lineaire rangschikking v brontypen te defini¨eren, is bron R toegewezen → proces k¯ enkel bronnen die volgen i/d rangschikking op R aanvragen ↔ nadeel: bronbehoefte moet vooraf gekend zijn • vasthouden & w8en vrkomen dr te eisen dat e proces alle benodigde systeembronnen in 1x opvraagt & proces te laten w8en tt dat alle aanvragen gelijktijdig toegekend k¯ w ¯ ↔ nadeel: bronbehoefte moet vooraf gekend zijn 4. Deadlock vermijden: • tijdstempels gebruiken vr transacties → oud proces (O) & jong proces (Y)
Figuur 3.1: Wait/Die vs Wound/Wait • elk knooppunt moet globale toestand v systeem i/d gaten houden • controleren o/e veilige globale toestand moet wederzijds exclusief zijn • controleren of het veilig is verzoek toe te kennen vereist extra verwerkingskr8 vr gedistr syst met groot # processen & systeembronnen 5. Deadlock detectie: elke locatie heeft all1 info over de eigen systeembronnen ↔ deadlock heeft mogelijk betrekking op gedistribueerde systeembronnen • Centraal beheer: 1 locatie verantw vr deadlockdetectie • Hi¨erarchisch beheer: deadlock w ¯ ontdekt op knooppt dat dient als gemeenschappelijk vertakkingspunt vr locaties wrtoe systeembronnen behoren die het conflict veroorzaken • Gedistribueerd beheer: alle processen werken samen bij deadlockdetectie
19
vb: elke transactie j heeft 4 parameters: • Ti = unieke identificatie v/d transactie • Held by(Ti ) = nil als transactie in uitvoering of gereed. zo niet = id v transactie die beschikking heeft over object dat Ti nodig heeft • Wait for(Ti ) = nil als Ti nt w8 o/e andere transactie. Anders = id v transactie die als 1e staat i/e geordende lijst v geblokkeerde transacties (6= Held by(Ti )!!) • Request Q(Ti ) = w8rij v alle uitstaande requests vr objn vastgehouden dr Ti , indeling (Dk ,Tk ) met Tk = object dat Dk wenst 6. Deadlock bij berichtencommunicatie: • Wederzijds wachten: deadlock treedt op bij berichtencommunicatie wnnr alle leden v/e groep processen w8en o/e bericht v/e ander proces i/d groep & er gn berichten onderweg zijn Afhankelijkheidsverz DS(Pi ) = alle processen wrvan Pi e bericht verw8 → deadlock i/d verz S als (a) alle processen in S zijn gestopt in afw8ing v berichten (b) S bevat de afhankelijke verzameling v alle processen in S (c) gn berichten onderweg tss leden v S deadlock als de opvolgers v 1 v/d leden v S zelf ook deel uitmaakt v S, cf figuur 3.2
Figuur 3.2: geen resp wel deadlock bij berichtencommunicatie • Niet-beschikbare berichtenbuffers: – betrekking op toewijzen v buffers vr berichten die onderweg zijn, komt vl vr in datanetwerken – vb directe deadlock: bufferruimte vr A zit vol met pakketten vr B en omgekeerd & gn v/d 2 accepteert berichten omdat buffers vol ⇒ nt toestaan buffer gebruikt vr 1 verbinding – vb indirecte deadlock: buffers vol met berichten vr volgende node i/d rij ⇒ gestructureerde bufferpool gebruiken = hi¨erarchisch (buffer vullen adhv # hops al afgelegd, alles vol tem ‘k hops’ = gn berichten aanvaarden die < k hops gedaan hebben)
3.5
Elections
election algortime = proces kiezen uit groep v processen o/e bepaalde rol te spelen, versch processen k¯ gelijktijdig de stemming starten • hoofddoel = unieke keuze maken & proces met grootste identifier kiezen → id moet uniek zijn 1 & moet k¯ geordend w ¯ (vb proces-id, proces kiezen met laagste belasting → id = < load ,i > → zelfde load = ordenen adhv proces-id) • ∀ Pi heeft variabele electedi , initieel = ⊥ (ng nt geset) & requirements: E1 (safety): e deelnemend proces Pi → electedi = ⊥ of electedi = P met P proces met hoogste identifier 20
E2 (liveness): alle processen nemen deel a/d verkiezing & uiteindelijk moet elk proces elected 6= ⊥ kiezen of crashen • Bully election: – elk proces heeft identifier, proces k¯ falen tijdens election, elk proces k¯ election starten (initiator), betrouwbare communicatie & proces weet welke processen hogere identifier hebben – doel: proces met hoogste identifier dat ng actief is moet dr ieder proces als co¨ordinator gekozen w ¯ – 3 soorten berichten: ∗ election: gestuurd dr initiator nr elk ander proces met hogere identifier ∗ response: antw op election ∗ co¨ ordinator bericht: verstuurd dr proces dat verkozen is tt coordinator nr alle processen met lager id – gecrasht proces dat w ¯ heropgestart stuurt election bericht, onafh v wel/geen co¨ordinator (= BULLY) – proces dat election bericht (v processen met lager id) ontvangt stuurt reply en start zelf election om te kijken of er gn processen zijn met hogere id of hemzelf – initiator: ∗ als gn reply ontvangen binnen (2Ttr + Tpr ) zelf co¨ordinator (Ttr = tranmissietijd, Tpr = tijd nodig om bericht te processen) ∗ als reply ontvangen is er proces met hogere identifier ∗ als gn co¨ ordinator bericht ontvangen na bep tijd → nieuwe election opstarten • Ring based election: nodes in ring verbonden, betrouwbare communicatie in wijzerzin, elk proces k¯ election beginnen 1. initieel elk proces gemarkeerd als nt-participerend 2. initiator markeert zichzelf als participerend dr identifier in election bericht te plaatsen → nr buurman zenden 3. bij buurman: – ontvangen id > eigen id → doorsturen & zichzelf op participerend zetten – ontvangen id < eigen id & ontvanger 6= participerend → eigen id in election bericht, doorsturen & zichzelf op participerend zetten – ontvangen id < eigen id & ontvanger = participerend → bericht nt doorsturen – ontvangen id = eigen id → co¨ordinator → zichzelf op nt-participerend zetten & elected bericht nr buurman sturen 4. elected bericht ontvangen → zichzelf op nt-participerend zetten & electedi op id v co¨ ordinator zetten & doorsturen (als nt zelf co¨ordinator)
21
Hoofdstuk 4
Shared Data 4.1
Transacties
• doel: synchrie op hoger niveau brengen • transactie = set v operaties die logisch gezien bij elkaar horen, atomair – Begin transaction → markeer de start – End transaction → markeer het einde & poging tot commit (= transactie effectief uitvoeren) – Abort transaction → kill transaction & herstel originele toestand (= startsituatie) – Read data - write data – Statements, procedure calls, ... • complexiteit: – mr dan sequentie v operaties → specifieer welke operaties deel uit maken v/d transactie – transactie moet telkens correct uitgevoerd w, ¯ zelfs wnnr vl transacties samen op zelfde data uitgevoerd w ¯ – transacties nooit partieel uitgevoerd, maar atomair – zakelijke transacties moeten bij wet op papier bekrachtigd w, ¯ elektronische ook! – transactie systemen zijn veeleisend: high throughput, snelle responstijd, highly available • Database Managementsysteem DBMS: verantw vr lezen v & schrijven nr databank → nood aan gelijktijdigh: terwijl databank iets uit geheugen haalt k¯ CPU SQL-statements v andere transacties parsen & compileren • Eigenschappen: Eig. 1 = Atomair: transactie = enkelvoudig, nt opdeelbaar wnnr ze ofwel volledig uitgevoerd, ofwel nt uitgevoerd w ¯ → alles of niets – als transactie T commits → gebruiker k¯ zkr zijn dat alle acties v T o/d databank uitgevoerd w ¯ – transactie T k¯ onderbreken (abort) of onderbroken w ¯ → gebruiker k¯ zeker zijn dat de acties die eventueel al ondernomen w ¯ ongedaan w ¯ gemaakt → alsof T nooit opgestart w ¯ – local recovery = verantw vr elimineren v parti¨ele resultaten
22
Eig. 2 = Consistent: wnnr bij begin transactie db = consistent, na toepassing transactie db = consistent, verantw v/d appie → transactie k¯ fouten introduceren → systeem moet integriteitschecks voorzien & k¯ transactie verwerpen Eig. 3 = Isolation = serialiseerbrh: gebruikers k¯ ≥1 transacties gelijktijdig comitten, mr elke gebruiker denkt dat zijn transactie ge¨ısoleerd gebeurd → DBMS laat meerdere transacties gelijktijdig toe op dezelfde data → CPU blijft draaien & meer transacties/tijds1heid ⇒ Concurrency Control Protocol: schedule v orders die serializable is (netto effect v transacties in bep volgorde sequentieel verwerken = gelijk) Eig. 4 = Durability: garantie dat eens transactie T uitgevoerd, resultaten zijn blijvend → optreden v/e failure na commit mag gn effect hebben o/d resultaten v transactie → bij optreden failures: global recovery procedure opstarten: – Server Crash: databank opnieuw consistent brengen → transacties ng in executie ongedaan maken – Disk Crash: replicatie → backups & mirrors
4.2
Concurrency control
Meerdere transacties gelijktijdig k¯ uitvoeren → transacties schedulen zodat effect op gedeelde data serieel equivalent zijn (serializability) = steeds sequenti¨ele volgorde v transacties vinden zodat effect op data hetzelfde is ⇒ toestand v data mag nt i/e vorm zijn die nt dr sequentieel toepassen v/d transacties te bereiken is (vb 2 transacties die data gelijktijdig wijzigen) Concurrency control = proces dat verantw is vr genereren v serializable schedule • Lost update problem: 2 bankrekeningen, 2 transacties die geld gelijktijdig toevoegen → incorrect omdat update v 1e transactie overschreven w ¯ door 2de transactie. • Inconsistent retrievals: 2 bankrekeningen, totaal v allemaal berekenen en erna ng 100 bijzetten bij 1 v/d 2 • Serial equivalence: 1e transactie doet alles op bep rekening, vr 2de transactie iets erop doet ⇒ serieel equivalente transacties als alle paren v conflicterende operaties v/d 2 transacties op alle objn in dezelfde volgorde w ¯ uitgevoerd → objn in zelfde volgorde benaderen
Figuur 4.1: Read & Write operation conflict regels • dirty read: T2 leest data in, voordat T1 zijn operaties gecommit heeft op die data (door isolatie-eigensch) ⇒ T1 & T2 aborten = cascading aborts • read/write conflict (unrepeatable reading): T1 leest 2x zelfde data uit, mr tss deze 2 reads wijzigt T2 de data • overwriting uncommited values: T1 past data aan, T2 past data aan vr T1 commit, net alsof T1 nt heeft plaatsgehad
23
1. Locking: transacties k¯ exclusieve locks aanvragen vr resources die ze nodig (zullen) hebben, wnnr andere transactie zelfde resource aanvraagt → w8en tt lock vrijgegeven • gedistr syst: lock manager verantw vr implementatie = gecentralizeerde mutual exclusion server: – – – – –
lock tabel: entry vr elk object dat momenteel locked is transactie k¯ slechts 1 lock per object bekomen shared lock (vb ≥1 tranactie die 1 obj lezen) k¯ ge-upgrade w ¯ nr exclusive lock (un)locking = atomaire operatie transactie T houdt transactietabel met verwijzingen nr eigen locks • serialiseerbaarh garanderen dr 2-phase locking 2PL: transactie k¯ gn nieuwe lock mr aanvragen nadat het al 1 terug heeft vrijgegeven Phase 1 = growing: locks aanvragen, gn locks vrijgeven Phase 2 = shrinking: enkel locks vrijgeven tt gn locks meer Strict 2-phase locking S2PL = abort-cascades vermijden → write locks aanhouden tt commit of abort typisch enkel kleine delen locken (vb gegevens v 1 klant ipv gans klantenbestand) • verschillende locks → gelijktijdige verwerking ⇒ shared lock – read lock: gn probleem als ≥1 transacties tegelijkertijd data v 1zelfde object lezen – write lock: slechts 1 transactie k¯ tegelijkertijd data v/e object aanpassen & tijdens aanpassen mag er ook nt gelezen w ¯ – Multiple reader/single writer: ∗ object nt gelockt: transactie k¯ zowel read als write lock krijgen ∗ object read locked: transactie k¯ read lock krijgen maar gn write lock → w8en ∗ object write locked: transactie k¯ gn read of write lock krijgen → w8en 2. Deadlock: vermijden dr bij begin alle nodige resources in 1 atomaire operatie te locken ⇔ nood aan resources nt op vrhand gekend & gedeelde bronnen onnodig vastzetten 3. 2-version locking: verhogen gelijktijdigh • read operatie nt blokkeren op write operatie v andere transactie → nieuwe lock toevoegen: commit lock • transacties met write lock, schrijven in voorlopig versie v object, andere transacties k¯ lezen uit oorspr object • transactie krijgt gn read/write lock wnnr object commit locked • wnnr transactie wil comitten: – alle write locks w ¯ commit locks – wnnr object uitstaande read locks heeft moet transactie w8en tt deze wr vrij gegeven w ¯ • read operaties all1 geblokt dr commit lock, die duidelijk minder tijd vragen, maar read lock k¯ oorzaak zijn wrdoor andere transactie nt k¯ committen 4. Nadelen locks: deadlock, overhead & concurrency daalt wnnr locks vast tijdens voll levenstijd v transactie (commit/abort) 5. Optimistic Concurrency Control (Kung & Robinson): • Observatie: kans dat 2 transacties tt zelfde object toegang willen <<< • Optimistic control:
24
Phase 1 = working phase: transactie mag ervan uitgn dat gn conflicten & gn locks hoeven aangevraagd w ¯ Phase 2 = validation phase: vr transactie k¯ committen → valideren Phase 3 = update phase: als validatie suc6 → comitten & tijdelijke versies w ¯ permanent bij conflicten → aborten & later weer opstarten • Eigenschappen: deadlockvrij, maximum parallellisme & transacties moeten soms heropgestart w ¯ 6. Timestamp ordening (Reed): • elke transactie unieke tijdsstempel (fysische of logische klok) • elk object read & write tijdstempel – read tijdstempel RTS = v be¨eindigde transactie die dit object laatst gelezen heeft – write tijdstempel WTS = v be¨eindigde transactie die laatst in obj geschreven heeft • volgorde in tijdstempels: (a) WTS & RTS moet ouder zijn (<) TS v/e transactie die ernaar wil schrijven want recentere thread hangt af v/d huidige waarde (b) WTS < TS v/e transactie die dat object wil lezen want recentere thread heeft de waarde overschreven als deze volgorde niet voldaan ⇒ abort & restart
4.3
Gedistribueerde transacties
1. clienttransactie = gedistr als operaties in meerdere servers induceert, zowel i/d vorm v/e vlakke (flat) transactie of geneste (nested ) transactie: • Flat: start operaties op objn in versch servers, maar toegang tt serverobjecten = sequentieel (dus pas nr volgende server als operaties in vorige volbr8) • Nested: top-level transactie start subtransacties, welke verder subtransacties k¯ starten enz & subtransacties v zelfde level k¯ parallel lopen 2. Co¨ ordinator: • client spreekt co¨ ordinator aan o/e bep server, deze kent uniek id toe a/d transactie (TID = server id (vb IPadres) + uniek nr in server) • co¨ ordinator = verantw vr uiteindelijke commit/abort • co¨ ordinator houdt referentielijst nr participanten bij & omgekeerd houdt participant link nr co¨ ordinator bij 3. 2-phase commit protocol 2PC: in gedistr transactie moeten alle servers samen akkoord gn over commit/abort actie v/d transactie → 1 server neemt co¨ordinerende rol met verantwh om beslissing samen te nemen ⇒ 2-phase commit protocol: servers moeten via communicatie e gezamenlijke beslissing nemen rond commit of abort operatie Phase 1 = voting: elke deelnemer stemt vr committen of aborten v transactie i. co¨ ordinator stuurt canCommit(T) naar alle participanten ii. participanten replyen met Yes of No, afh of hun deel v transactie gelukt Phase 2 = execution: uitvoeren beslissing i. co¨ ordinator verz stemmen (incl eigen stem) ii. als gn failures → alle stemmen = Yes ⇒ stuurt doCommit(T) nr participanten die hun deel v/d transactie mogen committen 25
iii. anders co¨ ordinator stuurt doAbort(T) nr alle participanten die Yes gestemd hebben, deze maken hun deel v transactie ongedaan & sturen ACK trug iv. participanten die Yes gestemd hebben w8en op doCommit(T), hierna sturen ze haveCommited(T) terug nr co¨ordinator v. indien ze gn doCommit(T) of doAbort(T) ontvangen sturen ze getDecision(T) om antwoord te krijgen Aanpassingen bij nested transactions: • openSubTransaction(T): opent nieuwe subtransactie met als ouder T & geeft unieke subtransactie-id terug • getStatus(T): vraagt status v T aan co¨ordinator, return = committed, aborted of provisional (= voorlopig) • als subtransactie vervolledigd → provisional commit of abort (6= klaar om te committen), gn permanente backup • finale beslissing commit/abort gebeurt op top-level transactie • oudertransactie k¯ committen ook als 1 v/d subtransacties abort, omgekeerd nt mog • als top-level vervolledigd start de 2-phase commit – 1e fase = stemming: ∗ hi¨erarchisch: canCommit(T, Tsub ): co¨ordinator vraagt aan T, die co¨ord. is v Tsub , of Tsub gecommit mag w ¯ → Yes/No ⇒ berichten v beneden nr boven in hi¨erarchie sturen ∗ vlak: canCommit(T, abortList): co¨ordinator vraagt aan T of T mag gecommit w ¯ → Yes/No ⇒ rechtstreeks met alle betrokken deelnemers communiceren, wel abortlijst bijhouden – 2de fase = analoog aan nt-geneste transacties 4. Concurrency control vr gedistr transacties: • Locking: locks lokaal bijhouden (1 server), lokale lockmanager, lock pas releasen als transactie commited/aborted op alle servers → gedistr deadlock dr versch ordening v transacties op versch systemen • Tijdstempel-ordenen: vereist dat zelfde volgorde in alle servers bekomen w ¯ → logische klok & tijdstempel =
• Optimistische concurrency control: validatie moet over alle servers gebeuren tijdens 1e fase v 2-phase commit & commitment deadlock: X valideert T vr U, Y valideert U vr T, validaties starten gelijktijdig → slechts 1 validatie/update per server 5. Gedistr deadlock: als gn cirkelvormig w8en in lokale wait-for-graphs WFG k¯ er toch gedistr deadlock zijn! → aflezen op globale WFG, die partieel w ¯ bijgehouden i/d deelnemende servers ⇒ goeie communicatie nodig OF centrale deadlockdetectie → veel overhead ⇒ Edge chasing: • servers forwarden berichten (‘probes’) die de edges v/d graph dr het gedistr syst volgen • volgorde: (a) Initiation: als server object aanvraagt dat dr andere server locked is → mogelijke deadlock ⇒ probe sturen probebericht = server-id & pad dr gedistr syst dat bericht al hft afgelegd (b) Detection: probes ontvangen → ofwel deadlock detecteren, ofwel doorsturen (c) Resolution: als deadlock gedetecteerd → bep transactie aborten 6. Transaction recovery: recovery manager = verantw vr durability & failure atomicity: • objn opslaan in permanent geheugen (recovery file) vr committed transactions 26
• serverobjn na crash restoren • recoveryfile reorganiseren → performantie v recovery verbeteren • opeisen v opslagplaats i/d recovery file Technieken: logging & shadow versions
4.4
Replicatie
= meerdere kopie¨en v data → performantie (load-balancing), fout-tolerantie (servers met juiste data k¯ servers met slechte/oude data wegstemmen), schaalbrh (clusters ipv groter mainframe) & beschikbrheid 1. Vereisten: • Replication transparantie: gebruikers zien 1 object, vragen daartoe toegang & krijgen 1 resultaat • Consistentie: versch gebruikers aangesloten op 1 obj, moeten zelfde data zien 2. System Model: • elk logisch obj = ge¨ımplementeerd dr collectie v fysische replicas (nt noodz allemaal consistent) • stel asynchr systeem & proces faalt enkel dr te crashen • replica manager: – bevat replica’s o/e pc & heeft directe toegang – voeren herstelbare operaties uit op replica’s → laten gn inconsistente resultaten 8r als crash – objn w ¯ gekopieerd nr alle RM’s (behalve als anders nodig) – statisch systeem = vast # RM’s ↔ dynamisch syst (RM’s k¯ systeem verlaten & vervoegen (vb crash)) – RM k¯ e state machine zijn → voert atomische operaties uit, staat = vorige staat + uitgevoerde operaties, alle replica’s starten identiek & voeren dezelfde operaties uit & operaties w ¯ nt gehinderd dr uitlezen v/d klok e.d. – collectie RM’s levert service nr client, client ziet enkel die service die toegang tt logische objn verleent • client doet request aan Front End (maakt replication transparant): read-only of update requests
Figuur 4.2: Basis architectuur model • garanties: requests dr 1 client nr e state machine w ¯ FIFO behandeld & wnnr e bep request v/e client e 2de request v/e andere client teweeg brengt, w ¯ de 1e request 1 behandeld dr de state machine 27
• fasen v request uitvoeren: fase 1 = request doen: ofwel zend de FE request nr 1 RM die rondzendt, ofwel multicast nr alle RM’s (state machine approach) fase 2 = co¨ ordinatie: de RM’s beslissen of request aanvaard & over ordening tss andere requests (FIFO (volgorde in FE bepaalt), causaal (tijdstip v request uitvaren bepaalt) of totale ordening) fase 3 = uitvoering: RM’s voeren request uit (soms enkel voorlopig) fase 4 = overeenkomst: RM’s komen overeen over effect v requestresponse → ≥1 RM’s antwoorden nr FE → 1e antwoord nr client ofwel stemmen vr beste (tgn fouten) • alle replica’s starten in zelfde staat, ontvangen zelfde requests & voeren zelfde sequentie v requests uit → requests ordenen & unieke id geven 3. Groepscommunicatie: cf multicastcommunicatie praktisch → dynamisch lidmaatschap: processen k¯ groep verlaten & vervoegen ⇒ lidmaatschapsmanagement: • interface vr lidmaatschapveranderingen: operaties om groepen verwijderen/aanmaken, processen verwijderen/toevoegen aan groep • failure detectie: detecteren v leden die crashen, onbereikbaar w ¯ → proces = ‘suspected ’ dat gecrasht ⇒ verwijderen uit groep • leden waarschuwen ivm veranderingen • groepsadres uitbreiding: multicastadres omzetten nr adressen v alle leden ↔ IP multicast = zwak lidmaatschapmanagement
Figuur 4.3: Groepscommunicatie 4. View Delivery: view = overzicht v/e groep (welke processen), view verandert als leden bijkomen/verlaten → requirements: • Orde: als proces p een view v(g) aflevert v´o´or v’(g), dan k¯ gn enkel ander proces q 6= p v’(g) afleveren vr v(g) • Integriteit: als proces p view v(g) levert ⇒ p ∈ v(g) • Non-trivialiteit: als proces q groep toetreedt & w ¯ onbepaald bereikbr vanaf proces p 6= q ⇒ q zit altijd i/d view die p levert view-synchrone communicatie → extra garanties tov hierboven: • overeenkomst: correcte processen leveren zelfde sequentie v views (dwz als e correct proces bericht m stuurt in view v(g) → alle andere correcte processen die m sturen doen dat ook in v(g))
28
• integriteit: als e correct proces bericht m stuurt → zal m nt nog eens sturen & als p ∈ group(m) → proces dat m stuurde zit in view v p • geldigheid: stel p = e correct proces dat bericht m stuurt in v(g) → als proces q ∈ v(g) m niet stuurt in v(g), zal q niet i v’(g) v p zitten Stel p stuurt m nr q & r → p crasht direct ⇒ q & r mogen nt 1st view leveren & daarna bericht m leveren want ze weten dat m komt v p die gecrasht is vb State transfer: stel nieuwe RM komt erbij → moet state v replica krijgen v andere RM ↔ wat als updates gebeuren tijdens state transfer ⇒ bij nieuwe view wrin nieuwe member zit, stuurt (stel oudste) RM de state dr & stopt executie, ook alle andere RM’s stoppen executie tt nieuwe RM ‘begin’ bericht stuurt → executie hervatten 5. Fout-tolerante services: correcte service leveren ook al hebben meerdere servers foute/oude data? • stel: betrouwbre communicatie, gn partities & individuele operaties (= gn transacties) • replica-service = correct als het blijft antwoorden ondanks fouten & als client gn onderscheid k¯ maken tss deze service & service v 1 correcte RM replica-object service = Lineariseerbr als ∀ executie het verweven v versch operaties v versch clients voldoet aan • de verweven sequentie v operaties voldoet a/d specificaties v/e (enkele) correcte kopie v/d objn ⇒ resultaten v client operaties komen overeen met deze v/d interleaving • de volgorde v verweven operaties = consistent met effectieve tijd wrop de operaties vrkwamen tijdens executie ⇒ clients moeten up-to-date info krijgen ↔ moeilijk ivm synchroniseren v klokken ⇒ sequenti¨ele consistentie: consistentie met programmavolgorde ipv real time seq.cons in vb: volgens programmeervolgorde moet het kloppen (saldo opvragen nadat saldo veranderd) maar real time is de update ng nt doorgekomen → nt lineariseerbr 6. Passief (primary-backup) replication model: altijd 1 primaire RM & meerdere secundaire = backup RM’s, FE communiceert met primaire RM, die de operaties uitvoert & updates stuurt nr backups → als primaire faalt, backup w ¯ primaire → FE moet primaire vinden na crash Fase 1 = request: FE stuurt request met unieke id nr primaire RM Fase 2 = co¨ ordinatie: primaire bekijkt elke request atomisch, FIFO tov andere requests & checks id, als request met dat id al afgewerkt w ¯ antwoord herzonden Fase 3 = uitvoering: primaire voert request uit & slaat antwoord op Fase 4 = overeenkomst: als de request = update w ¯ (nieuwe staat + antw + id) nr alle backups gestuurd die een ACK trugsturen Fase 5 = antwoord: primaire antw nr FE die antw drstuurt nr client ⇒ lineariseerbr want: • primaire voert alle operaties op gedeelde objn sequentieel uit • als primaire uitvalt: – bakcups krijgen view zonder primaire → berekenen wie volgende primaire w ¯ – nieuwe primaire registreert met naamservice
29
– dmv view-synchrone communicatie k¯ de backups over1komen welke operaties al uitgevoerd w ¯ v´ o´ or de primaire uitviel – als de FE gn antw krijgt stuurt hij request nr nieuwe primaire – nieuwe primaire hervat bij fase 2 = co¨ordinatie: kijken welke requests al w ¯ afgehandeld & antw herzenden beide vwn vr lineariseerbrh voldaan als primaire view-synchrone communicatie gebruikt nr backups toe Passieve replicatie: • als f processen crashen → f+1 RM’s nodig (k¯ nt overweg met arbitrary failures want clients k¯ gn antwn krijgen v backup RM’s) • lineariseerbrh dr view-synchr-commun → overhead, meerdere berichten/multicast & na falen primaire delay dr nieuwe groepsview leveren • variant wrbij clients v backup RM’s k¯ lezen → reduceert werk vr primaire & seq.consistentie mr gn lineariseerbrh • vb Sun NIS: zwakker (gn seq. cons) mr aangepast aan soort data, hoge bereikbrh & performantie, clients k¯ met master of slave communiceren & updates nt via RM’s mr direct op files i/d master Actieve replicatie: • alle RM’s zelfde, beginnen initieel zelfde & voeren zelfde operaties in zelfde volgorde uit (vereist totally ordered betrouwbare multicast v FE nr alle RM’s) • als 1 RM crasht → gn effect op performantie • tolereert arbitrary (byzantijnse) fouten want FE k¯ versch antwn vgln • fasen: Fase 1 = Request: FE hangt uniek id aan request & gebruikt totally ordered betrouwbre multicast om ze te versturen nr alle RM’s (in slechtste geval crasht FE) Fase 2 = Co¨ ordinatie: multicast levert requests bij alle RM’s in zelfde (totale) volgorde Fase 3 = Uitvoering: elke RM voert request uit, allemaal state machines & ontvangen requests in zelfde volgorde → zelfde effecten Fase 4 = Overeenkomst: nt nodig want alle RM’s voeren zelfde uit in zelfde volgorde Fase 5 = Antwoord: FE’s ontvn antwn v RM’s, k¯ 1 gebruiken (snelste, crash failures tolereren) of stemmen vr beste • nt lineariseerbr want gn real time order → wel seq.cons want state machines → synchr & zelfde operaties in zelfde volgorde • byzantijns falen vrkomen: 2f+1 RM’s & f+1 identieke antwn verzamelen in FE • performantie↑ dr read-only requests enkel nr 1 RM te sturen 7. Zeer beschikbare services: geeft clients toegangt tt service met zovl mog redelijke antwtijden, ook als resultaten nt conform seq. cons (blijven ontvangen, inconsistenties later oplossen) • eager updates (vr fout-tolerante services): updates nr RM’s zo vlug mogelijk sturen & over1komen vrdat antw nr client w ¯ gestuurd → vr hoge beschikbaarh: minimum # RM’s contacteren & minimum tijd nodig om over1 te komen • lazy updates (zwakkere consistentie): minder over1komst nodig & data meer beschikbr Vb - Gossip Architectuur: 30
• data dicht bij clients gekopieerd • RM’s wisselen ‘gossip’ berichten uit met updates • 2 soorten operaties: queries = read-only & updates = staat aanpassen mr nt lezen • FE zend queries/updates nr gelijk welke RM (beschikbre met redelijke antw-tijd) • 2 garanties (ook als RM’s even onbeschikbr): (a) elke client krijgt consistente sevice na bep tijd (data reflecteert de updates die de klant doorvoerde ook als bij versch RM’s) → vector tijdstempels, 1 entry per gebruikte RM (b) ‘ontspannen’ consistentie tss replica’s → alle RM’s krijgen uiteindelijk alle updates • 5 fasen: Fase 1 = Request: FE’s gebruiken (nrml) zelfde RM & k¯ geblokkeerd zijn op bep queries & update operaties keren terug nr client vanaf dat operatie doorgegeven is nr de FE → client k¯ verder doen, update i/d 8rgrond afhandelen dr FE Fase 2 = Update antwoord: RM antw vanaf hij de update ontvangen heeft Fase 3 = Co¨ ordinatie: RM w8 mt request uitvoeren tt de request voorkomt in de totale volgorde (er k¯ gossip berichten tss zitten) Fase 4 = Uitvoering: RM voert request uit Fase 5 = Query antwoord: als request = query antwoord de RM Fase 6 = Overeenkomst: RM’s daten elkr up dr gossip berichten (lazily: meerdere updates samen of als RM bep update tekort heeft) • FE houdt vector tijdstempel bij die versie v laatste geziene data reflecteerd = prev, deze w ¯ bij iedere query nr RM meegestuurd, nieuwe waarde new w ¯ bij antw teruggestuurd v RM samen met de gevraagde info (val ) cf figuur 4.4
Figuur 4.4: Gossip Architectuur • Gossip Replica Manager, cf figuur 4.5
31
Figuur 4.5: Gossip Replica Manager – value = waarde v/d appie -staat in de RM – value timestamp = vectortijdstempel die alle updates wrgeeft in de value, w ¯ upgedate iedere de value veranderd w ¯ (maw wnnr een update request binnenkomt) – update log: alle update operaties w ¯ bijgehouden → bijhouden omdat update ng nt mag uitgevoerd w ¯ want ng nt zijn beurt (unstable) & als uitgevoerd, ng gn bevestiging dat uitgevoerd bij andere RM’s – replica tijdstempel: geeft alle updates wr die dr RM geaccepteerd zijn (dus i/h log staan) ↔ 6= uitgevoerde updates! – uitgevoerde operaties tabel: vrkomt dat e operatie 2x w ¯ uitgevoerd (ontvangen v andere RM’s als v FE) – tijdstempel tabel: verz vectortijdstempels onvtvangen v andere RM’s in gossipberichten → om te weten wnnr RM’s updates hebben ontvangen • gossip bericht bevat log & replica tijdstempel → RM die gossip bericht ontvangt moet: – zijn log met ontvangen log samenvoegen – in causale volgorde nieuwe updates die nu stabiel zijn toepassen – redundante entries uit log & uitgevoerde operaties-tabel vrwijderen als geweten dat ze dr alle RM’s w ¯ uitgevoerd – zijn replica tijdstempel samenvoegen met die ontvangen zodat dit over1komt met wat in het log w ¯ bijgevoegd • nt nuttig vr real-time, nt vr bankaccounts, schaalbaar mr hoe meer RM’s hoe meer gossipberichten → als queries frequenter dan updates: read-only replicas gebruiken die enkel dmv gossipberichten upgedate w ¯ & # updates per gossipbericht↑
4.5
Transacties met replicated data
1. transactie op replicated data moet vr client gebeuren zoals op gwne (enkele) data 2. bij nt-replicated data → transacties sequentieel, 1 per 1 in juiste volgorde, dr serieel equivalente verweving v transacties v versch clients ⇒ effect op replicated data moet zelfde zijn alsof transacties 1 per 1 w ¯ uitgevoerd op 1 set v objn = one-copy serializability 3. Architecturale vragen: • Waar updates submitten? – update everywhere = update transacties op elke RM uitvoeren
32
– primary copy = updates enkel uitvoeren bij primaire RM (= master), backups (= slave) enkel read-only • Wanneer updates doorgeven naar andere RM’s? – eager = update binnenkrijgen → update drsturen → antwoorden nr FE – lazy = update binnenkrijgen → antwoorden nr FE → update drsturen 4. Primary Copy Replication: alle requests (updates & queries) nr primaire RM Eager: • Primary copy = primaire RM: – – – –
request = request = request = bij abort:
read: lokaal lezen & antwn nr FE write: lokaal schrijven, doorgeven naar backup RM’s & antwn nr FE commit: controleren of alle RM’s de update doorgevoerd hebben abort & andere RM’s informeren over abort
• Secondary Copy = backup RM: – – – –
request = read: lokaal lezen write v primaire: writes die elkr interfereren in FIFO volgorde uitvoeren write v client: weigeren → write moet via primaire request = commit v read-only: lokaal comitten
backup = deelnemer ivm commit request v primaire • bij deadlock: backup RM’s moeten read-transacties aborten Lazy: • Primary copy = primaire RM: – – – –
request request request request
= = = =
read: lokaal lezen & antwn nr FE/gebruiker write: lokaal schrijven & antwn nr FE/gebruiker abort: lokaal stoppen commit: soms alle updates in 1 multicastbericht nr andere RM’s
• Secondary copy = backup RM: – – – – –
request = read: lokaal lezen bericht v primaire: alle veranderingen FIFO doorvoeren write v client: weigeren → write moet via primaire request = commit/abort v read-only: lokaal stoppen opm: transactie mag data schrijven die nt replicated is OF wrvr deze RM primaire is
• enkel lokale deadlocks mogelijk • systemen laten toe dat versch objn versch primaire RM’s hebben ⇒ transactie die op 2 primairen wil schrijven = meestal nt toegestaan 5. Read-One/Write-All = ROWA = update everywhere Eager: • bij read: lokaal read-lock aanvragen, lokaal lezen & antwn nr FE/gebruiker • bij write v client: lokaal write-lock vragen, lokaal schrijven & write-request multicasten nr andere RM’s • bij write v andere RM: lokaal write lock vragen, lokaal schrijven & OK terug sturen • bij OK ontvangen v alle andere RM’s, OK antwn nr FE/gebruiker • bij commit request: controleren of alle RM’s de update doorgevoerd hebben 33
• bij abort: aborten & andere RM’s informeren over abort • deadlock mogelijk Lazy: • bij read: lokaal lezen & antwn nr FE/gebruiker • bij write: lokaal schrijven & write-request multicasten nr andere RM’s • bij commit/abort: lokaal stoppen & soms na commit 1 multicastbericht sturen nr andere RM’s met gewijzigde objn FIFO volgorde • bij ontvangen bericht v andere RM: conflicten detecteren & veranderingen doorvoeren 6. Lazy vs Eager: • lazy primary copy: inconsistente reads • lazy update everywhere: inconsistenties & verzoening (reconciliation) • gn communicatie tss RM’s binnen transactie antw-tijd • mogelijks transactieverlies bij crash • optimalisaties vr update-forwarding mogelijk 7. Primary vs ROWA • simpeler gelijktijdigheidcontrole • minder co¨ ordinatie nodig & gemakkelijkere optimalisaties • nt-flexibel: clients moeten primaire RM kennen om te k¯ updaten & verschil tss read-only & update-request moet gekend zijn • primaire = enigste punt v falen & mogelijks bottleneck • meerdere gedistr primairen: sommige types v transacties verboden, meer lokaal & minder bottleneck 8. ROWA Available (Copies Replication) = ROWAA tgn RM falingen • primaire houdt lijst U v alle beschikbare kopie¨en bij & polst bij nodes om falingen te detecteren • algoritme: Stap Stap Stap Stap
1: 2: 3: 4:
in backup RM: haal U op v/d primaire lees een kopie, bij time-out lees een volgende submit lokale veranderingen in alle nodes in U commit bij alle nodes in U
• RM die crashte & terug komt: – alle gemiste & lopende transacties ophalen bij de primaire – primaire k¯ sequentie-nrs toevoegen aan transacties → als RM transacties gemist gemakkelijker detecteren – alternatief: zend vr elk data-obj de laatste versie (enkel vr objn wrv gecrashte RM minstens 1 update gemist heeft) • probleem: site die crashte & terugkomt k¯ transacties missen die gebeuren tijdens dat RM terugkomt ⇒ transactie T moet bij commit checken of versie v U (lijst met nodes die kopie¨en hebben) ng klopt
34
9. ROWA + Quorum Consensus Protocols tgn communicatiefalingen probleem: netwerk k¯ gescheiden zijn, berichten k¯ verloren gaan & gelijktijdige views zijn mogelijk ⇒ enkel views met ‘quorum’ v replicas mag doorgaan quorum = subgroep v RM’s wrv de grootte aangeeft of ze het recht hebben om operaties uit te voeren ⇒ zorgen dat operaties binnen 1 netwerkpartitie afgehandeld w ¯ (vb quorum: meerderheid v replica’s in systeem) vb: elke read-operatie moet een read quorum v R stemmen verzn vr het k¯ lezen v gelijk welke up-to-date kopie & elke write-operateie moet e write quorum v W stemmen verzn vr het e update-operatie mag doorvoeren ⇒ R & W instellen vr groep RM’s zodat W > helft v totaal # stemmen & R+W > totaal # stemmen v/e groep
KUTCURSUS
35
