Samenvatting Gedistribueerde Systemen Dumon Willem 2009 - 2010
Hoofdstuk 1
Basis 1.1 1.1.1
Karakterisatie van een Gedistribueerd Systeem Terminologie
Gedistribueerd systeem = software/hardware componenten, netwerk & communicatie, co¨oordinatie via message passing → concurrency, geen globale klok & onafhankelijke failures ⇒ verzameling onafhankelijke pc’s die overkomen als ´e´en systeem Waarom: • prijs/performantie ratio: niet lineaire curve maar stijgt zeer snel, meerdere CPU’s → performantie verdubbelen voor dubbele kost als niet tevl overhead (1 pc → 100 pc’s → datacentrum) • zinvol voor 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: wanneer 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 voor ondersteuning van een groep pc’s verbonden via netwerk • Netwerkbesturingssysteem: elke pc eigen OS, netwerkBS = aanvulling op lokale • Gedistribueerd OS: gemeenschappelijk OS gedeeld door 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) 1
• MIMD = Multiple Instruction Stream, MD (parallel & distributed systems) – 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 bepaalde services (WWW, email, filetransfer) Intranet = verz LAN’s geconnecteerd via backbones, via routers aan internet, eigen security policy & admin Mobile computing = transparante toegang tot intranets, toegang tot lokale resources aan remote site ⇒ Location-aware computing Ubiquitous computing = kleine computerapparaten overal, communicatie tussen apparaten Nieuwe toepassingen: • Sensor netwerken, Animaties, Multi-Agent systemen (Robotic Soccer) • Grid Computing: pc-kracht even toegankelijk maken als elektriciteit, open standaarden, pc-resources niet geadministreerd • Cluster Computing: cluster = set v nodes op 1 locatie, grid = meerdere clusters en andere resources (netwerken, opslag) • Cloud Computing: Infrastructure as a Service (IaaS), Platform as a Service (PaaS) & Software as a Service (SaaS) • Parallel Computing: alle cpu’s toegang tot shared memory om info uit te wisselen • Distibuted Computing: elke CPU eigen (‘distributed’) geheugen, info uitwisselen door message passing
1.1.2
Software design van een Gedistribueerd Systeem
1. Heterogeniteit: versch niveau’s (netw, OS, HW, programmeertalen,...) ⇒ Middleware: Java RMI, CORBA → implementatie van een hoger niveau API 2. Openheid: open systemen laten uitbreidingen van het 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 door overspoelen met requests & mobiele code kan onbevoegde operaties uitvoeren)) 4. Schaalbaarheid: kost resources, performantieverlies, uitputting resources (cfr. 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
2
6. Concurrency: versch clients willen simultaan toegang tot gedeelde resource ⇒ gelijktijdige verwerking (nt triviaal & synchronisatie technieken (vb semaphoren)) 7. Transparantie: systeem = transparant voor feature als deze niet observeerbaar is voor gebruiker v systeem (vb rlogin: lokaal vs remote computer, Java RMI: lokaal vs remote object, GSM: locatie = transparant & emailadress: netw-locatie transparant) → uniformiteit belangrijk voor gebruiker
1.2
Gedistribueerde Architectuur Modellen
1. Software Layers - Lagenmodel: door met layers & services te werken wordt complexiteit van een systeem doorbroken: • Layer = groep gerelateerde functionele componenten • Service = functionaliteit die aangeboden wordt a/d volgende layer Oorspronkelijk: layers of modules in 1 enkele computer ↔ Nu: services/requests tussen 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 tot systeembronnen op alle platforms • Biedt programmeurs mogelijkheid om toepassingen te bouwen die er niet alleen hetzelfde uitzien & werken mr ook dezelfde manier voor toegang tot gegevens gebruiken, ongeacht locatie ervan • Beperking: end-to-end argument (communicatie zoveel mogelijk tussen eindpunten); sommige aspecten vereisen echter support o/d applicatie-laag 3. Design: meest evidente aspect v gedistribueerd systeemdesign = verdeling van verantwoordelijkhedeb tussen componenten (applicaties, servers, andere processen...) & de plaatsing van de componenten over computers in het netwerk ⇒ be¨ınvloedt rechtstreeks performantie, betrouwbrh & veiligheid van het systeem 4. Overzicht modellen: • Client-Server: clients meestal pc’s/werkstations voor 1 gebruiker, bieden eindgebruiker zeer gebruiksvriendelijke interface. Elke server verzorgt verz gedeelde gebruikersdiensten voor client, biedt vl clients de mogelijkheid toegang tot zelfde databank te delen & maakt gebruik van een krachtig pc-systeem voor beheren van de databank mogelijk server kan ook client zijn van een 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 voor onderhoud databank, verbinding server-client via software wrmee verzoeken worden verstuurd (vb SQL) – One-Tier Applicatie architectuur: pc verbonden via netwerk aan mainframe dat instaat voor presentatie, processing & data – Two-Tier Applicatie architectuur
3
–
– –
–
(a) Thin Client: client enkel verantw voor presentatie (UI) → kan bottleneck maken v mainframe die alles moet processen (b) Fat Client: client verantw voor presentatie & processing → updaten v code in clients zeer moeilijk & niet gebruiksvriendelijk want versch systemen mog Multi-Tier Applicatie architectuur: SW van de 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 tussen 3 partijen: transacties? Service ge¨ımpl door meerdere servers: ofwel objecten verdelen over versch servers, ofwel kopie op elke host (betere perfomantie, beschikbrh & fout tolerantie) Proxy servers & caches: bestandscache gebruikt voor opslag v recent gebruikte bestandsrecords, consistent als exacte kopie bevatten v externe gegevens, technieken voor bestands-vergrendeling (mutual exclusion, mr 1 client gelijktijdig per bestand) Web Caching Protocol: browser/proxy valideert resource in de cache door vergelijking met origineel in de web-server o/h moment dat e clientrequest toekomt. Web server kent resources ‘approximate expiry time’ toe, bij webserverresponse wordt huidige servertijd & expirytime meegegeven → browser berekent leeftijd van een resource Mobiele code: clientrequest → krijgt appletcode trug → client interageert met applet ⇒ snelle interactietijd & applets gelimiteerde access tot 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 voor veiligheid van de server, lokale omgeving afschermen (vb crawlers, web servers) & agenten zelf ook kwetsbaar, zonder toegang geen taken afwerken.
netwerk pc = OS en applicaties at runtime downloaden ↔ thin client = UI op client, applicaties op remote pc uitvoeren spontane netwerken ivm mobiele toestellen: services ontdekken → registration service (services publiek maken) & look-up service (services ontdekken adhv bepaalde 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, geen onderscheid client-server, bronnen delen tussen groot # versch pc’s ⇒ complex Design Requirements: • Performantie: snelle, consistente antw-tijd (caching & replication), throughput & balanceren v workload • QoS: betrouwbrh, veiligh & aanpasbaarheid • Afhankelijkheden: correcth, veiligh, omgaan met fouten & applicaties moeten kunnen verder werken ook met fouten in HW, SW of netwerken
1.2.1
Fundamentele eigenschappen v gedistribueerde architecturen
Architecturen bestaan uit set v processen die onderling communiceren door sturen v berichten over pc-netwerk, bel eigenschappen: sync, delays, failures, security:
4
• Interaction Model: behandelt performantie & plaatsen v tijdslimieten Processen interageren door 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 tussen start transmissie door ene process & begin ontvangst door andere), bandbreedte (totale # info dat overgebracht kan worden in een 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) 2. notie v globale tijd: elke pc eigen interne klok, wordt door lokale processen gebruikt → wanneer 2 processen hun klok lezen op zelfde moment kan dit toch verschillen (= computer clock drift: elke computer klok vertoont e verschil met e referentie-klok), zelfs wanneer klokken op zelfde moment ge¨ınitialiseerd worden, 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 kan in een eindige begrensde tijd & elk proces heeft lokale klok met begrensde drift 2. Asynch GS: geen 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 kunnen 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
5
Figuur 1.2: Timing failures Failures maskeren: mogelijk betrouwbare services te bouwen met componenten die onderhevig zijn aan failures, kennis van bepaalde failures van een component kunnen een andere service toelaten om deze failure te maskeren (verstoppen of omzetten naar e failure van een ander type). vb: replication → als 1 crasht niet alles crasht, checksum: zet arbitrary om in omission (maskeren corrupte berichten) & procescrash maskeren door proces te herstellen met externe info (vb status voor crash) • Security Model: bespreekt mogelijke bedreidingen voor processen & communicatiekanalen, veiligheid van een gedistribueerd systeem kan bekomen worden door beveiligen van processen & kanalen die gebruikt worden voor interactie & door objecten die ze bevatten te beveiligen tegen niet bevoegde toegang (d.m.v. access rights, identiteit altijd nagaan & rechten checken, zowel client die server nagaat als server die client nagaat) De vijand modelleren: kunnen berichten met valse source genereren, berichten kopi¨eren en herzenden, DoS & mobiele code ⇒ Encryptie, authenticatie, identiteit kennen van de ‘principal ’ waarvoor proces wordt uitgevoerd
1.3
TCP/IP
• Protocol = verz regels & formaten nodig voor comm tussen processen met welbepaald doel, omvat specificatie van een sequentie v berichten die uitgewisseld moeten worden & formaat van de data, wordt ge¨ımpl door gekoppelde softwaremodules in zender & ontvanger & laten toe dat verschillende SW componenten van het gedistribueerd systeem onafhankelijk kunnen ge¨ımp worden in verschillende programeertalen op pc’s met mogelijk verschillende data representaties • Layer: levert service naar bovenliggende layer & breidt service v onderliggen layers uit • Open System Interconnectie (OSI) Model: frameworks waarin protocollen kunnen gedefinieerd worden, geen definitie voor een bepaald protocol
Figuur 1.3: OSI vs DoD Model
6
– Fysieke laag: fysieke interface tussen zendapparaat & transmissiemedium of netwerk, houdt rekening met kenmerken medium, aard signalen & overdrachtsnelheid – Netwerklaag: uitwisseling v gegevens tussen eindsysteem & netwerk, specifieke software = afhankelijk van het type netw & versch standaarden (Circuit-, Packet Switching & LAN = ethernet) – Internetlaag: procedures nodig om data door versch gekoppelde netwerken te laten passeren, wordt gebruikt voor padbepalingsfunctie & in routers – Transportlaag: garandeert dat alle gegevens bij toepassing o/d bestemming arriveren & dat gegevens in juiste volgorde arriveren (mst toegepaste protocol = TCP) – Applicatielaag: logica nodig voor ondersteuning v verschgebruikerstoepassingen (vb bestandsoverdracht) • IPv6 = functionele verbeteringen tov IPv4: ontworpen voor hoger wordende snelheden v netwerken & voor mix v data (stilstaand & bewegend bld), 128bits adres ipv 32bits • Transport Control Protocol TCP: betrouwbaar end-to-end delivery protocol, basisidee = Zender zendt pakket → Ontvanger stuurt bij ontvangst ACK → Wanneer zender geen 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 geen verloren pakketten → window +1 per RTT ↔ wel verloren pakketten: window gehalveerd per RTT – TCP gebruiken als alle pakketten moeten toekomen & delay niet uitmaakt ⇒ email, web browsing (meerdere TCP connecties per pagina) & file downloads – CONS, error-checks vertragen overdracht & stream based • User Datagram Protocol UDP: geen garantie ivm aankomst/volgorde, enkel inhoud, CLNS, packet based, wel snelle zend rate → Real Time applicaties cfr. VoIP
1.4
Interprocess Communication
• Middleware = RMI & RPC, request/reply protocol, (un)marshalling & external data representation. Zit tussen applicatielaag & 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 wacht op corresponderende receive & receive wacht op aankomst bericht, voor elk bericht synch • Asynch: send = non-blocking, receive kan blocking of non-bl zijn: non-blocking = niet wachten, buffer kan in achtergrond gevuld worden → ontvanger o/d hoogte brengen. Java mbv multithreads = 1voudiger dan inkomend bericht uit control flow halen • Bestemmingen: bericht naar IP & poort (= bestemming binnen pc) sturen – poort: 1 receiver, meerdere zenders mogelijk, meerdere poorten per proces mogelijk, transparantie kan voorzien worden door ondermeer ‘name server/binder’ & locationindependent identifiers mappen naar locaties – proces: single entry point per proces voor alle messages – mailbox: kan vele receivers hebben & message queue
7
• 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 ↔ perfect betrouwbare communicatie kan vaak niet gegarandeerd worden • Sockets: eindpunt voor comm tussen 2 processen: poort + inetadres, receive-methode bevat ook poort & inetadres v zender om te kunnen antwoorden, poort duidt applicatie 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 tussen sockets: client zendt request tot communicatie naar Server-poort → Server accepteert request → typisch cre¨eert Server e nieuwe thread die verdere comm afhandelt. – berichtgrootte: applicatie kan zelf kiezen hoeveel data op de stream kan geschreven worden, de onderliggende implementatie v TCP beslist hoeveel data gecollecteerd wordt vooraleer te zenden – berichten: acknowledgement scheme & retransmitting, flow control, duplicatie & volgorde, synch semantics (non-blocking send, uitgezonderd voor 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 geen 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 worden getrunceerd) & geen conversie → bit transmission – non-blocking send & blocking receive – time-outs: gebruiker kan een timeout specifi¨eren o/d receive operatie – receive from any: receive geeft poort + inetadres v zender (sockets kunnen ook gebonden worden aan remote (IP-adres + poort)) – onbetrouwbare berichten service: verloren, verkeerde volgorde, duplicaten maar geen beschadigde berichten advh checksum → enkel inhoud gegarandeerd, transport niet ⇒ gebruik als occasionele fouten aanvaard – overhead voor betrouwbare message delivery: opslaan v state info (source & destination), extra berichten die verzonden moeten worden & latency voor de zender • Data representatie: niet alle pc’s representeren nummers op zelfde manier (big-endian ↔ little-endian), progr-niveau: info in data structuren → info in berichten = sequentie v bytes ⇒ Marshalling = info omzetten naar externe datarepresentatie, transmissie data, converteren naar lokale vorm bij ontvangst = unmarshalling → info wordt in formaat v zender doorgestuurd + indicatie v gebruikte formaat vb: CORBA CDR (Common Data Repres = binair formaat, externe data representatie voor gestructureerde & primitieve data types & ondersteunt versch programeertalen), Java Object Serialisatie (binair formaat, objecten omgezet naar extern formaat, type info meegestuurd & alleen Java) & XML (txt-formaat voor gestructureerde data, data vrstellen in web based client server applicaties & 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 niet altijd nodig, geen flow control, evt. (un)marshalling • TCP vaak overkill: reply = enkel ACK = redundant, grootte datapakket gelimiteerd, ontime communicatie ⇒ verbinding leggen = overkill, geen stream/flow control nodig ⇒ UDP met geschikte bufferlengte • Failure Model: omission failures, geen volgorde → time-outs, geen 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 van een bepaald proces wordt naar elk proces behorende tot 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 door klasse D inetadres: eerste 4 bits = 1110 – dynamisch membership – enkel via UDP op applicatieniveau – bijvoegen a/d groep door 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: objecten mappen op gedistr services, services modelleren als objecten • location & access transparancy (zelfde methodes lokaal als remote), overerving & polymorfisme • gedistr object = interface + service implementatie die 1 of meerdere interfaces impl • zelfde als gewone objecten: kan gebruikt worden als parameter & return value, kan geactiveerd worden, subklassen mogelijk & synchroon geactiveerd • MAAR – state access enkel via methoden – geen 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 voor local/remote object references (adressen geven) • Servant: instantie v klasse van een 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 naar remote object, zorgt voor transparantie naar client & verzorgt (un)marshalling • Server heeft e dispatcher & skeleton voor elke klasse van een remote object: dispatcher ontvangt request, kiest juiste methode in de skeleton adhv de methodID → skeleton unmarshalt request & activeert juiste methode i/d servant • dynamische proxies/skeletons: interfaces mss niet beschikbaar bij compilen → dynamische invocatie via generieke doOperation & dynamisch downloaden v klassen in clients & servers • andere: Binder (cfr. RMIRegistry ≈ name server voor RMI), Persistent Object Stores, Location Sevices & Distributed garbage collection (vb remote algoritme dat lease time v object bijhoudt, als client lease time niet vernieuwt wordt objectreferentie verwijderd, co¨operatie met lokale GC) 10
2.3.1
Java RMI
Figuur 2.2: Implementatie RMI • RMIRegistry: simpele naming service aan serverzijde, client kan zo referentie naar 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 door 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): door client om remote object op te zoeken, referentie wordt teruggegeven
2.3.2
Corba RMI
Object Management Group OMG: non-profit org, gesponsord door 500 organisaties, aanpak tot standardisatie, globale doel = theorie & impl v object-technologie promoten voor ontwikkeling v gedistr systemen Common Object Request Broker Architecture: taal onafhankelijk & platform afhankelijk (ORB impl voor elk nieuw platform vereist) ⇒ A homogenous view on a heterogeneous world
Figuur 2.3: Corba architectuur
11
• Interface Definition Language IDL: beschrijft interfaces v lokale objecten op taalonafhankelijke manier, wordt gecompileerd naar bepaalde taal door IDL compiler, uitkomst hiervan gewoon compileren = objecten, clients moeten zich hieraan houden om met serverobject te kunnen communiceren • architectuur, incl services (Naming , Notification , Event - & Security Service) • CDR: externe date representatie • Internet InterORB Protocol IIOP = protocol wrmee ORB’s communiceren over TCP • applicatie initialiseert ORB en heeft interne Object Adapter (reference count, lifetime, policies) • Object = programmeerentiteit bestaande uit identiteit, interface en implementatie (defineert de operaties die de IDL ondersteunt) • Servant = implementatie van een object • Client = entiteit die operatie invokeert • Object Request Broker ORB: – Object bus, middleware: transformatie v procesdata v/nr byteinfo die verstuurd wordt over netwerk (marshalling/serialization) adhv IDL vorm v gewoon object met methodes, een lokaal object maakt verbinding met ORB waardoor zijn methodes remote accessible worden, ORB verkrijgt adres voor dit (nu remote) object & zorgt voor interactie tussen versch applicaties 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 naar hostlocatie, OS & programmeertaal – onderdelen: ORB kern, IDL, taalmappings, interface repository, proxies/skeletons, dynamische invocatie & dispatch, object adapters & IIOP • IDL stubs: statische interface v object services (gedefinieerd adhv IDL), ≈ proxy voor remote server objecten • IDL Skeleton: statische interfaces voor elke ge¨exporteerde service (dr server), skeletons gecre¨eerd door IDL compiler, zend method invocations naar servant, unmarshalt argumenten v requests & marshalt exceptions/resultaten in reply • Dynamic Invocation Interface DII: API voor dynamische constructie v object invocations, als client niets weet over object dat het wil invokeren, lijst v parameters marschallen, functie wordt benoemd en request for service verstuurd naar object server. methoden ontdekken die pas at-runtime kunnen toegepast worden, ondernemen v remote call & opvangen v resultaten. • Interface Repository: bevat type informatie over alle geregistreerde interfaces (+ ondersteunde methodes & vereiste parameters), raadplegen wanneer client geen proxy bevat voor remote referentie van een obj. Repository ID = type identifier van een interface • Dynamic Skeleton Interface DSI: run-time binding mechanisme voor servers die methode calls moeten opvangen v componenten die geen IDL-gebaseerde stubs hebben, inspecteert inhoud van een request om doelobject te vinden, de opgeroepen methode & de bijhorende argumenten • The Object Adapter OA:
12
– behandelt services requests voor server objecten (cfr. remote reference & dispatcher module) via skeleton – biedt run-time environment om server objecten (servants) te instanti¨eren, requests door te geven & object Id’s toe te kennen – (de)activeert servants wanneer nodig → performantie% – geeft elk CORBA object unieke naam → deel v remote object referentie – CORBA object = geregistreerd via OA, die via object table CORBA objecten mapt naar servants – Portable Object Adapter POA laat applicaties & servants toe v ORB’s ge¨ımpl door versch ontwikkelaars • Implementation Repository: verantw voor activeren v geregistreerde services op aanvraag & lokaliseren v aanwezige actieve services, OA-naam gebruikt, entry bevat OA-naam, pad naar object impl, hostname & poortnummer server • General Inter-ORB Protocol GIOP: CDR, specificaties voor request/reply proctol onafhankelijk v OS. = IIOP request/reply als over TCP
13
Hoofdstuk 3
Gedistribueerd Procesbeheer 3.1
Procesmigratie
Het overbrengen v voldoende hoeveelh procestoestand van de ene naar 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 elkaar communiceren kunnen naar zelfde knooppunt worden verplaatst, maar voert proces gegevensanalyse uit op meerdere bestanden > proces zelf ⇒ proces naar bestandlocatie verplaatsen • Beschikbaarheid: als langdurig proces wil overleven, mogelijk verplaatsen (geplande uitschakeling systeem, gemelde storingen) • Gebruik v speciale mogelijkheden: HW of SW v bepaalde knooppt nodig 2. Mechanismen: • begin migratie: wie begint = afhankelijk v doel: – module v OS begint als verdelen v belasting = doel, module met proces/processen onderbreken, signaliseren & communiceren met andere modules – proces begint als doel = bepaalde HW/SW/bronnen gebruiken, proces kan zichzelf migreren & met o/d hoogte zijn v gedistr systeem • wat migreren: proces niet kopi¨eren, enkel procesbeeld (= minstens procescontroleblok PCB, eenvoudig te verplaatsen) → proces verwijderen & opnieuw cre¨eren, koppelingen met andere processen bijwerken, adresruimte v proces verplaatsen: – ‘eager-all ’: voll adresruimte overgezet → geen enkel spoor v proces op oud syst als adresruimte zeer groot & proces grootste deel niet nodig → onnodige belasting – ‘pre-copy’: proces ng steeds uitgevoerd op bronknooppt terwijl adresruimte wordt gekopieerd → gewijzigde pagina’s nog eens kopi¨eren, proces minder lang bevroren & minder lang wachten op uitvoering tijdens migratie – ‘eager-dirty’: alleen pagina’s in hoofdgeheugen & gewijzigde overzetten → extra’s op aanvraag overzetten & bronpc voortdurend betrokken bij levenscyclus v proces – ‘copy-on-reference’: pagina’s alleen overgezet als ernaar wordt verwezen → laagste overhead & snel – ‘flushing’: pagina’s van proces worden gewist uit geheugen van bronpc door ‘vuile’ pag’s naar HDD te schrijven & nodige pagina’s worden bij bronpc van de hdd gehaald als nodig ipv uit hoofdgeheugen → geen pagina’s v gemigreerde proces meer in geheugen v bronpc → geheugenblok direct voor andere processen 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 door naar bronpc (c) nieuw proces haalt gegevens over v oude pc (d) oorspr proces wordt ingelicht als migratie voltooid, zend voltooiingsbericht naar 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 niet gebruikt → processen migreren naar die pc → gebruiker meld aan → processen lozen om antwoordtijd te garanderen aan gebruiker → processen trug migreren naar bronpc 5. Pre¨ emptief - niet pre¨ emptief: pre¨emptieve procesoverdracht bij gedeeltelijk uitgevoerde processen & als enkel creatie v proces al voltooid, rest ng nt nt-pre¨emptieve procesoverdracht als uitvoering ng niet gestart (geen procestoestand emigreren), nuttig voor verdelen v belasting ↔ reageert trager op veranderingen v systeembelasting
3.2
Gedistribueerde globale toestanden
OS kan onmogelijk huidige toestand van alle processen in gedistr.syst. kennen ↔ proces kan huidige toestand va alle processen op lokale systeem kennen & externe processen kennen alleen info over toestand via berichten (= info uit verleden!) Voorbeeld slides! → termen: • Kanaal = tussen 2 processen als deze berichten uitwisselen • Toestand van een proces = reeks berichten die via kanalen door proces zijn verstuurd & ontvangen • Momentopname = snapshot: registreert toestand van een proces • Globale toestand = gecombineerde toestand v alle processen • Gedistribueerde momentopname = verz momentopnames, 1 per proces globale toestand = consistent als ∀ procestoestand (snapshot) waarin de ontvangst van een bericht is vastgelegd, het versturen v dat bericht is vastgelegd in de procestoestand van het proces dat het bericht heeft gestuurd ⇒ vb slides: inconsistent omdat M3 ng niet is verstuurd bij snapshot SA maar wel ontvangen wordt bij Sc (fig a), consistent omdat M3 wel al verstuurd bij SC (fig b, ontvangst ng niet geregistreerd bij SA mr niet belangrijk) Algoritme voor gedistr. momentopname: algoritme v Chandy & Lamport • elementen: processen (p, q,...) met inkomende & uitgaande kanalen, markeerberichten = markers & 2 soorten regels (ontvangen & zenden v markers)
15
• start: bepaald proces start door zichzelf te registreren & marker te sturen naar alle uitgaande kanalen • 2 regels: markering ontvangen (vb p ontvangt marker v q over kanaal c) & wanneer 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 van h e t 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 van h e t 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) voor gedeelde bron/object wordt tegelijkertijd in de KS toegelaten • veiligheid: (a) proces dat stopt in zijn nt-KS moet dat doen zonder andere processen te verstoren (b) proces dat toegang wenst tot zijn KS mag niet ∞ worden vertraagd → geen deadlock & uithongering • levendigheid: als geen enkel proces in zijn KS → elk proces dat toegang tot KS verzoekt krijgt zonder vertraging toegang • orde & fairness: (a) geen veronderstellingen gebruiken over relatieve snelheden v processen of # processen (b) proces bevindt zich slechts beperkte tijd in zijn KS 2. versch benaderingen voor gedistr algoritmen: • gecentraliseerd: 1 centraal knooppt voor toewijzen v toegang tot alle gedeelde objecten – alleen centrale knooppunt neemt beslissingen over toewijzen v systeembronnen – alle benodigde info wordt verzameld in het centrale knooppt, incl info over identiteit & locatie v alle systeembronnen & toewijzingsstatus v elke systeembron ⇒ overzichtelijk & eenvoudig te constateren of wederzijdse uitsluiting nageleefd ↔ als centrale knooppt problemen → wederzijdse uitsluiting (tijdelijk) niet nageleefd • gedistribueerd → voorwaarden: – alle knoopptn bevatten gemiddeld dezelfde hoeveelh info – elk knooppt ziet maar deel van het totale systeem & moet obv die info beslissingen nemen (want info soms ng onderweg dus info in knooppt niet volledig) – alle knoopptn zelfde verantwrdelijkh voor uiteindelijke beslissing – uitvallen van een knooppt leidt doorgaans niet tot uitvallen v totale systeem – geen globale, gemeensch klok voor reguleren v tijdstippen wrop gebeurtenissen plaats vinden 16
3. Gebeurtenissen rangschikken: • tijdsrangschikking v gebeurtenissen = belangrijk voor wederzijdse uitsluiting & deadlocks ↔ beperking: geen gemeensch klok of synchr-manier v lokale klokken • mogelijks vertraging tussen tijdstip wrop gebeurtenis zich voordeed & tijdstip waarop gebeurtenis wordt waargenomen (o/e ander systeem) • gebrek in synchr kan leiden tot verschillen in het lezen van de klok op uiteenlopende systemen • event (gebeurtenis) = actie die plaatsvindt op een lokaal systeem (vb proces betreedt/vrlaat KS) maar processen communiceren dmv berichten → events koppelen aan berichten • ⇒ Tijdstempeling: events i/e gedistr.syst. worden gerangschikt & fysieke klokken worden niet gebruikt – – – – –
elk systeem i in het 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 overdrachtstijden tussen systemen ↔ toegepaste volgorde komt per definitie niet overeen met chronologische volgorde MAAR volgorde bij elk proces wel zelfde 4. Gedistribueerde wachtrij: • Systeem bestaat uit N knooppunten (allemaal uniek nr & netw volledig gemaasd), elk knooppt bevat 1 proces dat wederzijdse uitsluiting aanvraagt • Berichten worden in zelfde volgorde ontvangen als verstuurd & worden binnen bepaalde tijd afgeleverd • Alle locaties beschikken over kopie v dezelfde wachtrij • Proces neemt pas toewijzingsbeslissing obv eigen wachtrij als het bericht heeft ontvangen v alle andere knoopptn om er zeker v te zijn dat geen 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 naar alle andere processen Stap 2: Pj ontvangt bericht, stelt q[i]=(Request, Ti ,i). Als q[j] geen verzoekbericht bevat stuurt Pj (Reply,Tj ,j) naar Pi (waardoor geen oudere verzoekberichten onderweg zijn bij een beslissing) Stap 3: Pi heeft toegang tot 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 wordt 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, geen starvation & geen deadlock. 3*(N-1) berichten
17
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 niet wacht op toegang tot KS: (Reply,Tj ,j) sturen C. als Pj wacht op toegang tot KS & verzoek is ouder: stel reply uit en set q[i] D. als Pj wacht op toegang tot KS & verzoek is jonger: (Reply,Tj ,j) sturen & set q[i] Stap 3: Pi heeft toegang tot bron (= kan KS betreden) als elk ander proces heeft geantwoord Stap 4: Pi verlaat KS → stuur uitgestelde replies ⇒ eerlijk, mutual exclusion, geen deadlock & geen 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 door 1 proces in bezit kan zijn, proces dat token heeft kan 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 door Pk • Stappen: Stap 1: token initieel willekeurig toegekend Stap 2: toegang tot KS door Pi als i over token beschikt, als niet over token beschikt → request naar 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 naar proces Pk wrvoor request[k] > token[k] N-1 berichten voor 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 verzamelen ⇒ voting set: • Vi = voting set voor 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 o 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 o 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
18
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
deadlock mogelijk → Lamport tijdstempel toevoegen aan √ √ requests, laagste tijdstempel wordt eerst geprocessed, om toegang te krijgen tot KS 2* N berichten, bij verlaten KS N berichten Crash v proces in andere voting set kan getolereerd worden, betrouwbare communicatie vereist
3.4
Gedistribueerde deadlock
1. Voorwaarden: • Wederzijdse uitsluiting: systeembron kan maar door 1 proces tegelijk worden gebruikt • Vasthouden & wachten: proces kan toegewezen systeembronnen vasthouden terwijl het wacht o/h toewijzen v andere bronnen • Geen pre¨emptieve onderbreking: proces kan niet gedwongen worden systeembron op te geven • Cirkelvormig wachten: gesloten cirkel v processen, waarbij elk proces minstens 1 bron vasthoudt die nodig is voor volgende proces in de cirkel 2. vb: Phantom Deadlock: 3 processen wachten op elkaars bronnen, P3 geeft zijn bron vrij en stuurt bericht daarvoor, maar vraagt ook de bron v P1 . • vrijgeefbericht wordt eerst ontvangen → geen probleem • request-bericht wordt eerst ontvagen → ‘deadlock’ (geen echte deadlock want geen globale toestand) 3. Deadlock voorkomen: • cirkelvormig wachten vrkomen door lineaire rangschikking v brontypen te defini¨eren, is bron R toegewezen → proces kan enkel bronnen die volgen in de rangschikking op R aanvragen ↔ nadeel: bronbehoefte moet vooraf gekend zijn • vasthouden & wachten vrkomen door te eisen dat e proces alle benodigde systeembronnen in 1x opvraagt & proces te laten wachten totdat alle aanvragen gelijktijdig toegekend kunnen worden ↔ nadeel: bronbehoefte moet vooraf gekend zijn 4. Deadlock vermijden: • tijdstempels gebruiken voor transacties → oud proces (O) & jong proces (Y)
Figuur 3.1: Wait/Die vs Wound/Wait
19
• elk knooppunt moet globale toestand v systeem in de gaten houden • controleren op een veilige globale toestand moet wederzijds exclusief zijn • controleren of het veilig is verzoek toe te kennen vereist extra verwerkingskracht voor 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 voor deadlockdetectie • Hi¨erarchisch beheer: deadlock wordt ontdekt op knooppunt dat dient als gemeenschappelijk vertakkingspunt voor locaties wrtoe systeembronnen behoren die het conflict veroorzaken • Gedistribueerd beheer: alle processen werken samen bij deadlockdetectie vb: elke transactie j heeft 4 parameters: • Ti = unieke identificatie van de 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 niet wacht op een andere transactie. Anders = id v transactie die als 1e staat i/e geordende lijst v geblokkeerde transacties (6= Held by(Ti )!!) • Request Q(Ti ) = wachtrij v alle uitstaande requests voor objecten vastgehouden door Ti , indeling (Dk ,Tk ) met Tk = object dat Dk wenst 6. Deadlock bij berichtencommunicatie: • Wederzijds wachten: deadlock treedt op bij berichtencommunicatie wanneer alle leden van een groep processen wachten op een bericht van een ander proces in de groep & er geen berichten onderweg zijn Afhankelijkheidsverz DS(Pi ) = alle processen wrvan Pi e bericht verwacht → deadlock in de verz S als (a) alle processen in S zijn gestopt in afwachting v berichten (b) S bevat de afhankelijke verzameling v alle processen in S (c) geen berichten onderweg tussen leden v S deadlock als de opvolgers v 1 van de leden v S zelf ook deel uitmaakt v S, cfr. figuur 3.2
Figuur 3.2: geen resp wel deadlock bij berichtencommunicatie • Niet-beschikbare berichtenbuffers: – betrekking op toewijzen v buffers voor berichten die onderweg zijn, komt vl voor in datanetwerken – vb directe deadlock: bufferruimte voor A zit vol met pakketten voor B en omgekeerd & geen van de 2 accepteert berichten omdat buffers vol ⇒ niet toestaan buffer gebruikt voor 1 verbinding – vb indirecte deadlock: buffers vol met berichten voor volgende node in de rij ⇒ gestructureerde bufferpool gebruiken = hi¨erarchisch (buffer vullen adhv # hops al afgelegd, alles vol tem ‘k hops’ = geen berichten aanvaarden die < k hops gedaan hebben) 20
3.5
Elections
election algortime = proces kiezen uit groep v processen op een bepaalde rol te spelen, versch processen kunnen gelijktijdig de stemming starten • hoofddoel = unieke keuze maken & proces met grootste identifier kiezen → id moet uniek zijn & moet geordend kunnen worden (vb proces-id, proces kiezen met laagste belasting → 1 , i > → zelfde load = ordenen adhv proces-id) id = < load • ∀ Pi heeft variabele electedi , initieel = ⊥ (ng niet geset) & requirements: E1 (safety): e deelnemend proces Pi → electedi = ⊥ of electedi = P met P proces met hoogste identifier 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 kan falen tijdens election, elk proces kan election starten (initiator), betrouwbare communicatie & proces weet welke processen hogere identifier hebben – doel: proces met hoogste identifier dat ng actief is moet door ieder proces als co¨ordinator gekozen worden – 3 soorten berichten: ∗ election: gestuurd door initiator naar elk ander proces met hogere identifier ∗ response: antwoord op election ∗ co¨ ordinator bericht: verstuurd door proces dat verkozen is tot coordinator naar alle processen met lager id – gecrasht proces dat wordt heropgestart stuurt election bericht, onafhankelijk van 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 geen processen zijn met hogere id dan zichzelf – initiator: ∗ als geen 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 geen co¨ ordinator bericht ontvangen na bep tijd → nieuwe election opstarten • Ring based election: nodes in ring verbonden, betrouwbare communicatie in wijzerzin, elk proces kan election beginnen 1. initieel elk proces gemarkeerd als nt-participerend 2. initiator markeert zichzelf als participerend door identifier in election bericht te plaatsen → naar 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 niet doorsturen – ontvangen id = eigen id → co¨ordinator → zichzelf op nt-participerend zetten & elected bericht naar buurman sturen 4. elected bericht ontvangen → zichzelf op nt-participerend zetten & electedi op id v co¨ ordinator zetten & doorsturen (als niet zelf co¨ordinator)
21
Hoofdstuk 4
Shared Data 4.1
Transacties
• doel: synchronisatie 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 van de transactie – transactie moet telkens correct uitgevoerd worden, zelfs wanneer veel transacties samen op zelfde data uitgevoerd worden – transacties nooit partieel uitgevoerd, maar atomair – zakelijke transacties moeten bij wet op papier bekrachtigd worden, elektronische ook! – transactie systemen zijn veeleisend: high throughput, snelle responstijd, highly available • Database Managementsysteem DBMS: verantw voor lezen v & schrijven naar databank → nood aan gelijktijdigh: terwijl databank iets uit geheugen haalt kan CPU SQL-statements v andere transacties parsen & compileren • Eigenschappen: Eig. 1 = Atomair: transactie = enkelvoudig, niet opdeelbaar wanneer ze ofwel volledig uitgevoerd, ofwel niet uitgevoerd wordt → alles of niets – als transactie T commits → gebruiker kan zeker zijn dat alle acties van T op de databank uitgevoerd worden – transactie T kan onderbreken (abort) of onderbroken worden → gebruiker kan zeker zijn dat de acties die eventueel al ondernomen worden ongedaan worden gemaakt → alsof T nooit opgestart werd – local recovery = verantwoordelijk voor elimineren v parti¨ele resultaten
22
Eig. 2 = Consistent: wanneer bij begin transactie db = consistent, na toepassing transactie db = consistent, verantw van de applicatie → transactie kan fouten introduceren → systeem moet integriteitschecks voorzien & kan transactie verwerpen Eig. 3 = Isolation = serialiseerbrh: gebruikers kunnen meerdere transacties gelijktijdig comitten, maar elke gebruiker denkt dat zijn transactie ge¨ısoleerd gebeurt → DBMS laat meerdere transacties gelijktijdig toe op dezelfde data → CPU blijft draaien & meer transacties/tijdseenheid ⇒ 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 van een failure na commit mag geen 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 kunnen 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 niet i/e vorm zijn die niet door sequentieel toepassen van de transacties te bereiken is (vb 2 transacties die data gelijktijdig wijzigen) Concurrency control = proces dat verantw is voor genereren v serializable schedule • Lost update problem: 2 bankrekeningen, 2 transacties die geld gelijktijdig toevoegen → incorrect omdat update van eerste transactie overschreven wordt door 2de transactie. • Inconsistent retrievals: 2 bankrekeningen, totaal v allemaal berekenen en erna ng 100 bijzetten bij 1 van de 2 • Serial equivalence: 1e transactie doet alles op bep rekening, voor 2de transactie iets erop doet ⇒ serieel equivalente transacties als alle paren v conflicterende operaties van de 2 transacties op alle objecten in dezelfde volgorde worden uitgevoerd → objecten 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 tussen deze 2 reads wijzigt T2 de data • overwriting uncommited values: T1 past data aan, T2 past data aan voor T1 commit, net alsof T1 niet heeft plaatsgehad 23
1. Locking: transacties kunnen exclusieve locks aanvragen voor resources die ze nodig (zullen) hebben, wanneer andere transactie zelfde resource aanvraagt → wachten tot lock vrijgegeven • gedistr syst: lock manager verantw voor implementatie = gecentralizeerde mutual exclusion server: – lock tabel: entry voor elk object dat momenteel locked is – transactie kan slechts 1 lock per object bekomen – shared lock (vb meerdere tranacties die 1 object lezen) kan ge-upgraded worden naar exclusive lock – (un)locking = atomaire operatie – transactie T houdt transactietabel met verwijzingen naar eigen locks • serialiseerbaarh garanderen door 2-phase locking 2PL: transactie kan geen nieuwe lock meer aanvragen nadat het al 1 terug heeft vrijgegeven Phase 1 = growing: locks aanvragen, geen locks vrijgeven Phase 2 = shrinking: enkel locks vrijgeven tot geen locks meer Strict 2-phase locking S2PL = abort-cascades vermijden → write locks aanhouden tot commit of abort typisch enkel kleine delen locken (vb gegevens v 1 klant ipv gans klantenbestand) • verschillende locks → gelijktijdige verwerking ⇒ shared lock – read lock: geen probleem als meerdere transacties tegelijkertijd data v eenzelfde object lezen – write lock: slechts 1 transactie kan tegelijkertijd data van een object aanpassen & tijdens aanpassen mag er ook niet gelezen worden – Multiple reader/single writer: ∗ object niet gelockt: transactie kan zowel read als write lock krijgen ∗ object read locked: transactie kan read lock krijgen maar geen write lock → wachten ∗ object write locked: transactie kan geen read of write lock krijgen → wachten 2. Deadlock: vermijden door bij begin alle nodige resources in 1 atomaire operatie te locken ⇔ nood aan resources niet op vrhand gekend & gedeelde bronnen onnodig vastzetten 3. 2-version locking: verhogen gelijktijdigh • read operatie niet blokkeren op write operatie v andere transactie → nieuwe lock toevoegen: commit lock • transacties met write lock, schrijven in voorlopig versie v object, andere transacties kunnen lezen uit oorspronkelijk object • transactie krijgt geen read/write lock wanneer object commit locked • wanneer transactie wil comitten: – alle write locks worden commit locks – wanneer object uitstaande read locks heeft moet transactie wachten tot deze weer vrij gegeven worden • read operaties alleen geblokt door commit lock, die duidelijk minder tijd vragen, maar read lock kan oorzaak zijn waardoor andere transactie niet kunnen committen 4. Nadelen locks: deadlock, overhead & concurrency daalt wanneer locks vast tijdens voll levenstijd v transactie (commit/abort) 5. Optimistic Concurrency Control (Kung & Robinson):
24
• Observatie: kans dat 2 transacties tot zelfde object toegang willen <<< • Optimistic control: Phase 1 = working phase: transactie mag ervan uitgaan dat geen conflicten & geen locks hoeven aangevraagd worden Phase 2 = validation phase: voor transactie kunnen committen → valideren Phase 3 = update phase: als validatie succes → committen & tijdelijke versies worden permanent bij conflicten → aborten & later weer opstarten • Eigenschappen: deadlockvrij, maximum parallellisme & transacties moeten soms heropgestart worden 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 object geschreven heeft • volgorde in tijdstempels: (a) WTS & RTS moet ouder zijn (<) TS van een transactie die ernaar wil schrijven want recentere thread hangt af van de huidige waarde (b) WTS < TS van een 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 in de vorm van een vlakke (flat) transactie of geneste (nested ) transactie: • Flat: start operaties op objecten in versch servers, maar toegang tot serverobjecten = sequentieel (dus pas naar volgende server als operaties in vorige volbracht) • Nested: top-level transactie start subtransacties, welke verder subtransacties kan starten enz & subtransacties v zelfde level kunnen parallel lopen 2. Co¨ ordinator: • client spreekt co¨ ordinator aan op een bep server, deze kent uniek id toe a/d transactie (TID = server id (vb IPadres) + uniek nr in server) • co¨ ordinator = verantw voor uiteindelijke commit/abort • co¨ ordinator houdt referentielijst naar participanten bij & omgekeerd houdt participant link naar co¨ ordinator bij 3. 2-phase commit protocol 2PC: in gedistr transactie moeten alle servers samen akkoord gaan over commit/abort actie van de 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 voor committen of aborten v transactie i. co¨ ordinator stuurt canCommit(T) naar alle participanten
25
ii. participanten replyen met Yes of No, afhankelijk of hun deel v transactie gelukt Phase 2 = execution: uitvoeren beslissing i. co¨ ordinator verz stemmen (incl eigen stem) ii. als geen failures → alle stemmen = Yes ⇒ stuurt doCommit(T) naar participanten die hun deel van de transactie mogen committen iii. anders co¨ ordinator stuurt doAbort(T) naar alle participanten die Yes gestemd hebben, deze maken hun deel v transactie ongedaan & sturen ACK trug iv. participanten die Yes gestemd hebben wachten op doCommit(T), hierna sturen ze haveCommited(T) terug naar co¨ordinator v. indien ze geen 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), geen permanente backup • finale beslissing commit/abort gebeurt op top-level transactie • oudertransactie kan committen ook als ´e´en van de subtransacties abort, omgekeerd niet mogelijk • 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 worden → Yes/No ⇒ berichten v beneden naar boven in hi¨erarchie sturen ∗ vlak: canCommit(T, abortList): co¨ordinator vraagt aan T of T mag gecommit worden → Yes/No ⇒ rechtstreeks met alle betrokken deelnemers communiceren, wel abortlijst bijhouden – 2de fase = analoog aan nt-geneste transacties 4. Concurrency control voor gedistr transacties: • Locking: locks lokaal bijhouden (1 server), lokale lockmanager, lock pas releasen als transactie commited/aborted op alle servers → gedistr deadlock door versch ordening v transacties op versch systemen • Tijdstempel-ordenen: vereist dat zelfde volgorde in alle servers bekomen worden → logische klok & tijdstempel =
• Optimistische concurrency control: validatie moet over alle servers gebeuren tijdens 1e fase v 2-phase commit & commitment deadlock: X valideert T voor U, Y valideert U voor T, validaties starten gelijktijdig → slechts 1 validatie/update per server 5. Gedistr deadlock: als geenn cirkelvormig wachten in lokale wait-for-graphs WFG kan er toch gedistribueerde deadlock zijn! → aflezen op globale WFG, die partieel wordt bijgehouden in de deelnemende servers ⇒ goeie communicatie nodig OF centrale deadlockdetectie → veel overhead ⇒ Edge chasing:
26
• servers forwarden berichten (‘probes’) die de edges van de graph door het gedistr syst volgen • volgorde: (a) Initiation: als server object aanvraagt dat door andere server locked is → mogelijke deadlock ⇒ probe sturen probebericht = server-id & pad door gedistribueerd systeem dat bericht al heeft afgelegd (b) Detection: probes ontvangen → ofwel deadlock detecteren, ofwel doorsturen (c) Resolution: als deadlock gedetecteerd → bep transactie aborten 6. Transaction recovery: recovery manager = verantw voor durability & failure atomicity: • objecten opslaan in permanent geheugen (recovery file) voor committed transactions • serverobjecten na crash restoren • recoveryfile reorganiseren → performantie v recovery verbeteren • opeisen v opslagplaats in de recovery file Technieken: logging & shadow versions
4.4
Replicatie
= meerdere kopie¨en v data → performantie (load-balancing), fout-tolerantie (servers met juiste data kunnen servers met slechte/oude data wegstemmen), schaalbaarheid (clusters ipv groter mainframe) & beschikbaarheid 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 object = ge¨ımplementeerd door collectie v fysische replicas (niet noodzakelijk allemaal consistent) • stel asynchr systeem & proces faalt enkel door te crashen • replica manager: – bevat replica’s op een pc & heeft directe toegang – voeren herstelbare operaties uit op replica’s → laten geen inconsistente resultaten achter als crash – objecten worden gekopieerd naar alle RM’s (behalve als anders nodig) – statisch systeem = vast # RM’s ↔ dynamisch syst (RM’s kunnen systeem verlaten & vervoegen (vb crash)) – RM kan een state machine zijn → voert atomische operaties uit, staat = vorige staat + uitgevoerde operaties, alle replica’s starten identiek & voeren dezelfde operaties uit & operaties worden niet gehinderd door uitlezen van de klok e.d. – collectie RM’s levert service naar client, client ziet enkel die service die toegang tot logische objecten verleent
27
• client doet request aan Front End (maakt replication transparant): read-only of update requests
Figuur 4.2: Basis architectuur model • garanties: requests door een client naar een state machine worden FIFO behandeld & wanneer e bep request van een client e 2de request van een andere client teweeg brengt, wordt de eerste request 1 behandeld door de state machine • fasen v request uitvoeren: fase 1 = request doen: ofwel zend de FE request naar 1 RM die rondzendt, ofwel multicast naar alle RM’s (state machine approach) fase 2 = co¨ ordinatie: de RM’s beslissen of request aanvaard & over ordening tussen 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 → meerdere RM’s antwoorden naar FE → 1e antwoord naar client ofwel stemmen voor beste (tegen fouten) • alle replica’s starten in zelfde staat, ontvangen zelfde requests & voeren zelfde sequentie v requests uit → requests ordenen & unieke id geven 3. Groepscommunicatie: cfr. multicastcommunicatie praktisch → dynamisch lidmaatschap: processen kunnen groep verlaten & vervoegen ⇒ lidmaatschapsmanagement: • interface voor lidmaatschapveranderingen: operaties om groepen verwijderen/aanmaken, processen verwijderen/toevoegen aan groep • failure detectie: detecteren v leden die crashen, onbereikbaar worden → proces = ‘suspected ’ dat gecrasht ⇒ verwijderen uit groep • leden waarschuwen ivm veranderingen • groepsadres uitbreiding: multicastadres omzetten naar adressen v alle leden ↔ IP multicast = zwak lidmaatschapmanagement
Figuur 4.3: Groepscommunicatie 28
4. View Delivery: view = overzicht van een 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 kan geen enkel ander proces q 6= p v’(g) afleveren voor v(g) • Integriteit: als proces p view v(g) levert ⇒ p ∈ v(g) • Non-trivialiteit: als proces q groep toetreedt & wordt onbepaald bereikbaar vanaf proces p 6= q ⇒ q zit altijd in de 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)) • integriteit: als e correct proces bericht m stuurt → zal m niet 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 naar q & r → p crasht direct ⇒ q & r mogen niet 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 waarin nieuwe member zit, stuurt (stel oudste) RM de state door & stopt executie, ook alle andere RM’s stoppen executie tot 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, geen partities & individuele operaties (= geen transacties) • replica-service = correct als het blijft antwoorden ondanks fouten & als client geen onderscheid kan maken tussen deze service & service van 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 van een (enkele) correcte kopie van de objecten ⇒ resultaten v client operaties komen overeen met deze van de 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 niet doorgekomen → niet 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 naar backups → als primaire faalt, backup wordt primaire → FE moet primaire vinden na crash Fase 1 = request: FE stuurt request met unieke id naar primaire RM 29
Fase 2 = co¨ ordinatie: primaire bekijkt elke request atomisch, FIFO tov andere requests & checks id, als request met dat id al afgewerkt wordt antwoord herzonden Fase 3 = uitvoering: primaire voert request uit & slaat antwoord op Fase 4 = overeenkomst: als de request = update wordt (nieuwe staat + antwoord + id) naar alle backups gestuurd die een ACK trugsturen Fase 5 = antwoord: primaire antw naar FE die antw drstuurt naar client ⇒ lineariseerbr want: • primaire voert alle operaties op gedeelde objecten sequentieel uit • als primaire uitvalt: – bakcups krijgen view zonder primaire → berekenen wie volgende primaire wordt – nieuwe primaire registreert met naamservice – dmv view-synchrone communicatie kunnen de backups overeenkomen welke operaties al uitgevoerd werden v´o´or de primaire uitviel – als de FE geen antwoord krijgt stuurt hij request naar nieuwe primaire – nieuwe primaire hervat bij fase 2 = co¨ordinatie: kijken welke requests al werden afgehandeld & antw herzenden beide voorwaarden voor lineariseerbrh voldaan als primaire view-synchrone communicatie gebruikt naar backups toe Passieve replicatie: • als f processen crashen → f+1 RM’s nodig (kunnen niet overweg met arbitrary failures want clients kunnen geen antwoorden krijgen van backup RM’s) • lineariseerbrh door view-synchr-commun → overhead, meerdere berichten/multicast & na falen primaire delay door nieuwe groepsview leveren • variant waarbij clients v backup RM’s kunnen lezen → reduceert werk voor primaire & seq.consistentie maar geen lineariseerbaarheid • vb Sun NIS: zwakker (gn seq. cons) maar aangepast aan soort data, hoge bereikbrh & performantie, clients kunnen met master of slave communiceren & updates niet via RM’s mr direct op files in de master Actieve replicatie: • alle RM’s zelfde, beginnen initieel zelfde & voeren zelfde operaties in zelfde volgorde uit (vereist totally ordered betrouwbare multicast v FE naar alle RM’s) • als 1 RM crasht → geen effect op performantie • tolereert arbitrary (byzantijnse) fouten want FE kan verschillende antwoorden vergelijken • fasen: Fase 1 = Request: FE hangt uniek id aan request & gebruikt totally ordered betrouwbre multicast om ze te versturen naar 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: niet nodig want alle RM’s voeren zelfde uit in zelfde volgorde Fase 5 = Antwoord: FE’s ontvangen antwoorden van RM’s, kunnen 1 gebruiken (snelste, crash failures tolereren) of stemmen voor beste
30
• niet lineariseerbr want geen 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 antwoorden verzamelen in FE • performantie↑ door read-only requests enkel naar 1 RM te sturen 7. Zeer beschikbare services: geeft clients toegangt tot service met zovl mog redelijke antwtijden, ook als resultaten niet conform seq. cons (blijven ontvangen, inconsistenties later oplossen) • eager updates (vr fout-tolerante services): updates naar RM’s zo vlug mogelijk sturen & overeenkomen voordat antwoord naar client wordt gestuurd → voor hoge beschikbaarh: minimum # RM’s contacteren & minimum tijd nodig om overeen te komen • lazy updates (zwakkere consistentie): minder overeenkomst nodig & data meer beschikbr Vb - Gossip Architectuur: • data dicht bij clients gekopieerd • RM’s wisselen ‘gossip’ berichten uit met updates • 2 soorten operaties: queries = read-only & updates = staat aanpassen mr niet lezen • FE zend queries/updates naar 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 tussen replica’s → alle RM’s krijgen uiteindelijk alle updates • 5 fasen: Fase 1 = Request: FE’s gebruiken (nrml) zelfde RM & kan geblokkeerd zijn op bepaalde queries & update operaties keren terug naar client vanaf dat operatie doorgegeven is naar de FE → client kan verder doen, update in de achtergrond afhandelen door FE Fase 2 = Update antwoord: RM antw vanaf hij de update ontvangen heeft Fase 3 = Co¨ ordinatie: RM wacht met request uitvoeren tot de request voorkomt in de totale volgorde (er kunnen gossip berichten tussen zitten) Fase 4 = Uitvoering: RM voert request uit Fase 5 = Query antwoord: als request = query antwoord de RM Fase 6 = Overeenkomst: RM’s daten elkaar up door 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 wordt bij iedere query naar RM meegestuurd, nieuwe waarde new wordt bij antwoord teruggestuurd v RM samen met de gevraagde info (val ) cfr. figuur 4.4
31
Figuur 4.4: Gossip Architectuur • Gossip Replica Manager, cfr. figuur 4.5
Figuur 4.5: Gossip Replica Manager – value = waarde van de applicatiestaat in de RM – value timestamp = vectortijdstempel die alle updates weergeeft in de value, wordt upgedate iedere de value veranderd wordt (maw wanneer een update request binnenkomt) – update log: alle update operaties worden bijgehouden → bijhouden omdat update nog niet mag uitgevoerd worden want nog niet zijn beurt (unstable) & als uitgevoerd, ng geen bevestiging dat uitgevoerd bij andere RM’s – replica tijdstempel: geeft alle updates wr die door RM geaccepteerd zijn (dus in het log staan) ↔ 6= uitgevoerde updates! – uitgevoerde operaties tabel: vrkomt dat een operatie 2x wordt uitgevoerd (ontvangen v andere RM’s als v FE) – tijdstempel tabel: verz vectortijdstempels ontvangen v andere RM’s in gossipberichten → om te weten wanneer 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 door alle RM’s worden uitgevoerd – zijn replica tijdstempel samenvoegen met die ontvangen zodat dit overeenkomt met wat in het log wordt bijgevoegd
32
• niet nuttig voor real-time, niet voor bankaccounts, schaalbaar mr hoe meer RM’s hoe meer gossipberichten → als queries frequenter dan updates: read-only replicas gebruiken die enkel dmv gossipberichten upgedate worden & # updates per gossipbericht↑
4.5
Transacties met replicated data
1. transactie op replicated data moet voor client gebeuren zoals op gewone (enkele) data 2. bij nt-replicated data → transacties sequentieel, 1 per 1 in juiste volgorde, door serieel equivalente verweving v transacties v versch clients ⇒ effect op replicated data moet zelfde zijn alsof transacties 1 per 1 worden uitgevoerd op 1 set v objecten = one-copy serializability 3. Architecturale vragen: • Waar updates submitten? – update everywhere = update transacties op elke RM uitvoeren – 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 naar FE – lazy = update binnenkrijgen → antwoorden naar FE → update drsturen 4. Primary Copy Replication: alle requests (updates & queries) naar primaire RM Eager: • Primary copy = primaire RM: – request = read: lokaal lezen & antwoorden naar FE – request = write: lokaal schrijven, doorgeven naar backup RM’s & antwoorden naar FE – request = commit: controleren of alle RM’s de update doorgevoerd hebben – bij abort: abort & andere RM’s informeren over abort • Secondary Copy = backup RM: – – – –
request = read: lokaal lezen write v primaire: writes die elkaar 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 & antwoorden naar FE/gebruiker write: lokaal schrijven & antwoorden naar FE/gebruiker abort: lokaal stoppen commit: soms alle updates in 1 multicastbericht naar 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 33
– request = commit/abort v read-only: lokaal stoppen – opm: transactie mag data schrijven die niet replicated is OF wrvr deze RM primaire is • enkel lokale deadlocks mogelijk • systemen laten toe dat versch objecten versch primaire RM’s hebben ⇒ transactie die op 2 primairen wil schrijven = meestal niet toegestaan 5. Read-One/Write-All = ROWA = update everywhere Eager: • bij read: lokaal read-lock aanvragen, lokaal lezen & antwoorden naar FE/gebruiker • bij write v client: lokaal write-lock vragen, lokaal schrijven & write-request multicasten naar 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 antwoorden naar FE/gebruiker • bij commit request: controleren of alle RM’s de update doorgevoerd hebben • bij abort: aborten & andere RM’s informeren over abort • deadlock mogelijk Lazy: • bij read: lokaal lezen & antwoorden naar FE/gebruiker • bij write: lokaal schrijven & write-request multicasten naar andere RM’s • bij commit/abort: lokaal stoppen & soms na commit 1 multicastbericht sturen naar andere RM’s met gewijzigde objecten 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) • geen communicatie tussen RM’s binnen transactie antwoordtijd • mogelijks transactieverlies bij crash • optimalisaties voor update-forwarding mogelijk 7. Primary vs ROWA • simpeler gelijktijdigheidcontrole • minder co¨ ordinatie nodig & gemakkelijkere optimalisaties • nt-flexibel: clients moeten primaire RM kennen om te kunnen updaten & verschil tussen 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 tegen RM falingen • primaire houdt lijst U v alle beschikbare kopie¨en bij & polst bij nodes om falingen te detecteren • algoritme: Stap 1: in backup RM: haal U op van de primaire 34
Stap 2: lees een kopie, bij time-out lees een volgende Stap 3: submit lokale veranderingen in alle nodes in U Stap 4: commit bij alle nodes in U • RM die crashte & terug komt: – alle gemiste & lopende transacties ophalen bij de primaire – primaire kan sequentienummers toevoegen aan transacties → als RM transacties gemist gemakkelijker detecteren – alternatief: zend voor elk data-obj de laatste versie (enkel voor objecten wrv gecrashte RM minstens 1 update gemist heeft) • probleem: site die crashte & terugkomt kan 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 9. ROWA + Quorum Consensus Protocols tegen communicatiefalingen probleem: netwerk kan gescheiden zijn, berichten kunnen 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 wordt (vb quorum: meerderheid v replica’s in systeem) vb: elke read-operatie moet een read quorum v R stemmen verzamelen voor het kan lezen v gelijk welke up-to-date kopie & elke write-operateie moet e write quorum v W stemmen verzamelen voor het e update-operatie mag doorvoeren ⇒ R & W instellen voor groep RM’s zodat W > helft v totaal # stemmen & R+W > totaal # stemmen van een groep
KUTCURSUS
35
