Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Distribuerede systemer på CBS, 14. september 20...

Kasper Tidemann
September 12, 2017

Distribuerede systemer på CBS, 14. september 2017 - transaktioner, del 1

Slides til undervisningen i distribuerede systemer på CBS d. 14. september 2017 omhandlende transaktioner.

Kasper Tidemann

September 12, 2017
Tweet

More Decks by Kasper Tidemann

Other Decks in Education

Transcript

  1. Hvordan fungerer git og GitHub? Det blev jeg spurgt om

    sidst - og det er et godt spørgsmål.
  2. En transaktion er en behandling af informationer, der enten lykkes

    eller ikke lykkes. Den generelle definition inden for IT.
  3. Det kunne fx skabe kaos, hvis der ikke blev anvendt

    transaktioner i banken… Transaktioner er en måde at skabe et forløb på, så behandlinger af data ikke foregår kaotisk.
  4. Her læser vi en kontos anløbende og lægger 10% til.

    Tidspunkt Handling Resultat 12:00 beløb = kontoA.læsBeløb() 1.000 kr. 12:01 kontoA.sætInd(beløb * 1.1) 1.100 kr.
  5. Her gør vi det samme igen på samme tid fra

    en anden maskine. Tidspunkt Handling Resultat 12:00 beløb = kontoA.læsBeløb() 1.000 kr. 12:01 kontoA.sætInd(beløb * 1.1) 1.100 kr. 12:00 beløb = kontoA.læsBeløb() 1.000 kr. 12:01 kontoA.sætInd(beløb * 1.1) 1.100 kr.
  6. For at citere DS-bogen for en gangs skyld. Det er

    det, der hedder the lost update problem.
  7. Rækkefølgen på to transaktioner må altså ikke være afgørende. We

    say two operations performed by different processes on the same resource conflict if the resulting state depends on the order in which they are executed.
  8. En-efter-en versus samtidig afvikling. We say that an interleaving of

    two blocks is serially equivalent, if the result is equivalent to an execution in which one block was executed entirely before the other.
  9. Jeg nævnte det jo sidste gang. Lad os bringe det

    på banen igen. Vi skal tale om atomicitet igen.
  10. Et lille tip: flyv direkte. Det kan man jo nu.

    Du vil gerne til San Francisco. Du beder et rejsebureau om at arrangere din tur. De fortæller at du skal over Chicago. De booker først en billet til Chicago, og finder så ud af at der ikke er flere pladser i flyet derfra til San Francisco - og du ærgrer dig.
  11. Drako var en græsk politiker med nogle meget stramme love.

    Det kunne undgås med en transaktion, der på drakonisk vis enten ville lykkes eller slet ikke.
  12. Konflikter kan opstå når der er afhængigheder i rækkefølgen. Operationer

    i to transaktioner Konflikt Årsag læs læs Nej Effekten af to læse-operationer er ikke afhængig af deres rækkefølge læs skriv Ja Effekten af en læs- og skriv- operationer er afhængig af deres rækkefølge skriv skriv Ja Effekten af en skriv- og skriv- operation er afhængig af deres rækkefølge
  13. Microsoft Access er et eksempel på en database som har

    streng afvikling af instruktioner.
  14. Tænk MySQL, PostgreSQL, Oracle og så videre. ACID er et

    begreb inden for databaser, som står for Atomicity, Consistency, Isolation og Durability.
  15. ACID er et stærkt koncept fra den gamle skole inden

    for databaser. Atomicity Enten virker hele molevitten eller også bliver det droppet. Consistency Sørger for at data er korrekte, fx at en ny række har en primærnøgle. Isolation Sætter lighedstegn mellem samtidig og seriel kørsel af transaktioner. Durability Hvis nu serveren eksploderer, så skal transaktioner kunne overleve - typisk ved at være gemt på disken.
  16. At bruge locks og locking er meget udbredt i databaser.

    Man kan sikre seriel ækvivalens ved fx at låse værdier eller ved at lave wait-for-grafer.
  17. Om hvordan det forholder sig med læse- og skrive-låse. Læse-operation

    Skrive-operation Hvis der ikke er nogen lås OK OK Hvis læse-lås på værdien OK Vent Hvis skrive-lås på værdien Vent Vent
  18. Her er der skabt en deadlock-situation. Transaktion 1 Transaktion 2

    Operationer Låse Operationer Låse kontoA.sætInd(200) skrive-lås på konto A kontoB.sætInd(200) skrive-lås på konto B kontoB.læsBeløb() (venter på skrive-låsen på konto B) kontoA.læsBeløb() (venter på skrive-låsen på konto A)
  19. Det er essensen af two-phase locking. Hvis en værdi ikke

    allerede er låst, så lås den. Hvis værdien har en lås i forvejen, der er i konflikt med operationen, så vent til låsen fjernes. Hvis værdien har en lås i forvejen, der ikke er i konflikt, så fortsæt som planlagt. Hvis værdien allerede er låst i samme transaktion, så forfrem den eventuelt og fortsæt som planlagt.
  20. En måde at styre samtidig afvikling på, så det ikke

    går rabundus. Locking er en form for concurrency control.
  21. Det kan skabe bedre performance at være optimistisk. Optimistic concurrency

    control er en antagelse om at flere forskellige transaktioner kan gennemføres uden at påvirke hinanden. Når en transaktion bliver kørt, så foregår det uden brug af locking. Når resultatet af en transaktion bliver gemt, så undersøges hvorvidt de data, den har brug, er blevet ændret i mellemtiden. Hvis ja, så forsøges transaktionen gentaget på ny.
  22. Altså: adgang til værdier styres af tidsstempler. Timestamp ordering har

    som regel at en transaktion ikke må gemme en værdi, der er blevet læst på et senere tidspunkt af en anden transaktion. En transaktion må ikke gemme en værdi, der er blevet gemt på et senere tidspunkt af en anden transaktion. En transaktion må ikke læse en værdi, der er blevet gemt på et senere tidspunkt af en anden transaktion.
  23. Det har at gøre med Leslie Lamport. Ham vender vi

    tilbage til. Et tidsstempel kan være et tidspunkt eller blot en værdi som stiger.
  24. Endnu et citat fra bogen. Transactions all limit to some

    extent the potential for concurrent operation.
  25. Fx når en transaktion læser værdier fra et cluster af

    database-servere. Transaktioner er distribuerede når de anvender værdier fra flere forskellige steder.
  26. Nu kommer vi til noget af det, som er virkelig

    interessant. Med distribuerede transaktioner har vi flere forskellige aktører, og hvem styrer så hvad?
  27. Two Generals’ Problem hvor sendebude bliver sendt ud og hjem

    - og nogen bliver slået ihjel undervejs.
  28. Det handler om at lede og fordele ansvar. Der skal

    være en, der styrer slagets gang. Det skal ikke være den samme altid - turen skal gå på skift. Det kaldes blandt andet for en coordinator role, en log leader eller generelt set log election. Husk at transaktioner skal gemmes og kunne genskabes - det gøres via en log over hvad der er sket.
  29. Det er jo nødvendigt at koordinere hændelser i et distribueret

    system. For at koordinere har vi skabt det, der hedder en two-phase commit protocol.
  30. Sådan ser en atomic commit protocol ud. – Er I

    klar? – Ja, mand! – På hvad? – Næ!
  31. Atomic commit protocol, forklaret. Hvis alle melder tilbage med grønt

    lys, så bliver transaktionen gennemført (commit). Hvis ikke alle melder positivt tilbage, så bliver transaktionen afbrudt (abort/rollback). Hvis en deltager har meldt positivt tilbage og ikke hører mere fra lederen, så er deltageren i en uncertain state.
  32. Konsensus vender vi tilbage til senere. Den form for koordinering

    er et eksempel på konsensus i et distribueret system.
  33. Stjålet direkte fra Wikipedia. A fundamental problem in distributed computing

    is to achieve overall system reliability in the presence of a number of faulty processes. This often requires processes to agree on some data value that is needed during computation. Examples of applications of consensus include whether to commit a transaction to a database, agreeing on the identity of a leader, state machine replication, and atomic broadcasts.
  34. Og når vi stemmer, så er det fordi vi skal

    opnå konsensus. Demokrati er en form for konsensus i den virkelige verden.
  35. Altså hvis en server crasher, fx. Hvad sker der så

    hvis det hele går op i hat og briller?
  36. Evnen til at håndtere og udbedre fejl er essentiel. Transaktioner

    skal som udgangspunkt være persisteret, altså gemt et sted, så de kan genskabes om nødvendigt. Hvis en server ikke svarer, så kan der anvendes en timeout, som opgiver at få svar efter noget tid. Ergo: et distribueret system skal som minimum kunne håndtere forsinkelser (latency) og nedbrud (failures).
  37. Som i livet generelt er det ofte flertallet som bestemmer.

    Et quorum er et udtryk for et givent flertal, der skal til for at et distribueret system kan overleve nedbrud. Et quorum på to tredjedele betyder at et system med alle noder intakte kan overleve at en tredjedel af dem dør på grund af systemfejl eller lignende. Et quorum kan samtidig anvendes til at løse konflikter omkring data i systemer, der er eventually consistent.
  38. Det er humlen i det. Bitcoin har en block chain,

    som er en stor log over alt det, der er sket.
  39. Hvis ja, hvorfor? Hvad forventer I at få ud af

    det? Er der nogen af jer, som har købt Bitcoin?
  40. En beskrivelse af Ethereum. Ethereum is a decentralized platform that

    runs smart contracts: applications that run exactly as programmed without any possibility of downtime, censorship, fraud or third party interference. These apps run on a custom-built blockchain, an enormously powerful shared global infrastructure that can move value around and represent the ownership of property. This enables developers to create markets, store registries of debts or promises, move funds in accordance with instructions given long in the past.
  41. En tidlig definition af kausalitetsbegrebet. Leslie Lamport fremsætter i juli

    1978 idéen om begivenheder, der er indtruffet før hinanden. a → b
  42. Et simpelt koncept, egentlig. Han omtaler clocks som en logisk

    konstruktion, der tæller når en værdi bliver ændret. hvis a → b, så C(a) < C(b)
  43. Også det her. Brugen af clocks gør det muligt at

    opstille en samlet rækkefølge over begivenheder i et distribueret system. a 㱺 b eller Ci(a) < Cj(b) eller Ci(a) = Cj(b) og Pi ≺ Pj
  44. Sidstnævnte er en vigtig pointe. Når der er opstillet en

    samlet rækkefølge for begivenheder i et distribueret system, så kan hver node vedligeholde en liste over hvilke ressourcer, der er ledige hvornår - og sørge for at sende forespørgsler på ressourcer når der er behov for det. Det kræver dog at alle noder kender til hinanden i det distribuerede system.
  45. Yes. En node kan få adgang til en ressource når

    den har en forespørgsel på en ressource i sin liste, og den forespørgsel kommer før andre forespørgsler i henhold til den samlede rækkefølge. a 㱺 b
  46. Så måske er det en god idé at anvende rigtige

    ure i stedet for tilnærmede. Problemet er at en begivenhed kan være vigtig, men hvis den ankommer for sent, så honoreres den reelle rækkefølge ikke.
  47. Altså: rigtige ure. I stedet for en værdi, der stiger

    løbende, så kan der anvendes rigtige ure til at afgøre den reelle rækkefølge af begivenheder i et distribueret system. Det skal selvfølgelig forstås som ure i en computer - og ikke det armbåndsur, du har på armen.
  48. Strong clock condition optræder når forsinkelser ikke ændrer i en

    faktisk rækkefølge. One of the mysteries of the universe is that it is possible to construct a system of physical clocks which, running quite independently of one another, will satisfy the Strong Clock Condition.