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

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

Kasper Tidemann
September 17, 2017

Distribuerede systemer på CBS, 18. september 2017 - transaktioner, del 2

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

Kasper Tidemann

September 17, 2017
Tweet

More Decks by Kasper Tidemann

Other Decks in Education

Transcript

  1. 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
  2. Problemet opstår jo hvis det her fx sker samtidig. SELECT

    * FROM students WHERE year = 2016; UPDATE students SET .. WHERE year = 2016;
  3. … eller det her. UPDATE students SET .. WHERE year

    = 2016; UPDATE students SET .. WHERE year = 2016;
  4. Husk på atomicitet, der sikrer at transaktioner enten lykkes eller

    ikke. Det nytter ikke at I kun får 50 kr. på kontoen, hvis I forsøger at sætte 100 kr. ind.
  5. Hvilket programmeringssprog skal man vælge? En håndfuld af jer kom

    og spurgte mig igen efter sidste forelæsning.
  6. Det handler om at være god til at udtrykke noget

    med en computer. Derfor kan JavaScript, HTML og CSS være en god start, fordi det kombinerer koden med det visuelle.
  7. At starte med JavaScript, HTML og CSS er en glimrende

    vej til at arbejde med backend også. Hvilket fx kunne være Go eller Ruby (on Rails) eller Python (Django).
  8. Det er svært at afgøre hvem man kan stole på

    i et distribueret system. Servere er jo bare servere, når dagen er omme.
  9. Mange sikkerhedsbrister skyldes at nogen udgiver sig for at være

    nogle andre. Tænk fx på tampering af beskeder og så fremdeles.
  10. Et velfungerende (distribueret) system bygger først og fremmest på tillid.

    Vi stoler fx på at optællingen af stemmer ved et folketingsvalg er korrekt.
  11. Byzantine Generals’ Problem er en teori om generaler, angreb og

    forrædere. Det er for så vidt en god metafor, selvom den er noget krigerisk.
  12. Ifølge Leslie Lamport, så skal alle loyale generaler være enige

    om en slagplan. Forrædere må ikke kunne spolere planen. Ready, set, war!
  13. Det svarer jo til at vi har nogle servere, som

    skal være enige om hvad de gør. Fx at opdatere hver deres information om jeres konto, når I hæver 100 kr. i banken.
  14. Sidste gang blev jeg spurgt om hvad der sker, hvis

    man befinder sig i en situation med halvtreds-halvtreds. For nu at bruge talesprog om det.
  15. Et citat fra Leslie Lamports artikel som svar på spørgsmålet.

    A small number of traitors can affect the decision only if the loyal generals were almost equally divided between the two possibilities.
  16. Det kaldes også et trust scheme, når vi laver regler

    for hvem vi kan stole på. Det nytter ikke hvis en general (server) sender samtlige beskeder til alle andre uden videre, for beskederne kan jo forfalskes på vejen. Derfor er hovedreglen: for hver besked fra en loyal general (anerkendt server), der skal alle andre loyale generaler bruge samme besked.
  17. … og hvad er en consensus vector så? Interactive consistency

    er når hver proces har sin egen værdi, og når alle processer kommunikerer med hinanden for at afgøre hvilken værdi, der er den korrekte. Der er tale om en række private værdier, der udveksles mellem processer (servere) for at finde en offentlig værdi i den givne consensus vector.
  18. majority(v1 , .., vn-1 ) En majoritetsalgoritme er et generelt

    begreb, der dækker over at afgøre hvilken værdi, der er korrekt.
  19. Ofte implementeres majority-algoritmer med udgangspunkt i antallet af ens forekomster.

    Forekomster Valg af den forekomst af en værdi, der optræder flest af. Sandsynlighed Valg af den værdi, der forekommer mest sandsynlig. Tillid Valg af den værdi, der optræder hos flest, der er tillid til. Type Valg af den værdi, som passer med den type, der er valgt.
  20. Kan man bruge en majority-algoritme i det tilfælde? Hvad hvis

    vi har ti servere, der alle mener at I har noget forskelligt stående på jeres bankkonto?
  21. Politiske debatter går i høj grad ud på at nogen

    mener at nogle andre mener noget, som de ikke gør. Prøv at tænke på hvor ofte det her gør sig gældende i det virkelige liv.
  22. Hvis der ingen forrædere er, så kører det jo bare.

    – Er I klar? – Yes! – Så pyt da.
  23. Prøv at udskifte generalen med master og løjtnant med slave,

    og I har et typisk database-setup. Hvis der ingen forrædere er, så sender generalen sin besked til alle løjtnanter, som læser beskeden og handler derefter. Hvis en løjtnant ingen besked modtager, så falder hun tilbage og angriber ikke (fallback policy).
  24. Når der er forrædere, så er tilliden i systemet begrænset.

    Hvis der er forrædere, så sender generalen sin besked til alle løjtnanter, som sender beskeden til hinanden. Hvis v er den oprindelige besked og v1 = v2 = v, men v3 = x, så er majority(v, v, x) = v.
  25. Det kan være simple sets med tal, der udgør en

    signatur. Endelig har vi signed messages, der kan afsløre når noget ikke stemmer overens.
  26. Den sidste general er forvirret, for han får to beskeder.

    angrib : 0 angrib : 0 fald tilbage : 0 : 1 angrib : 0 : 1 – Øh?
  27. Prøv at sammenligne det med at give en besked videre

    i en telefonkæde. Der er tale om signering via v : i : j og så fremdeles, som afslører hvem der snyder hvem.
  28. Hvis en server bare fejler, så stopper den. Hvis fejlen

    er byzantinsk, så stopper serveren ikke nødvendigvis. Generelt siger man at fejl i et distribueret system kan være fail-stops eller byzantine.
  29. Det er dyrt både i tid og ressourcer at sende

    alle de beskeder. Achieving reliability in the face of arbitrary malfunctioning is a difficult problem, and its solutions seems to be inherently expensive.
  30. Teorien siger altså at der ingen vej er udenom, hvis

    det skal være tæt på perfekt. The only way to reduce the cost is to make assumptions about the type of failure that may occur. However, when extremely high reliability is required, such assumptions cannot be made, and the full expense of a Byzantine Generals solution is required.
  31. Det kommer ikke uden sin pris, når det bliver implementeret.

    Det betyder at konsensus i et distribueret system er dyrt, tager tid og kræver mange ressourcer.
  32. Tid til at se på en anden artikel. Vi skal

    tilbage til transaktioner og navnlig dem, der er meget tilgængelige.
  33. Det er nemlig rigtigt - det kan ikke opnås. Indeed,

    serializable transactions—the gold standard of traditional ACID databases—are not achievable with high availability in the presence of network partitions.
  34. Og typisk gemmer vi jo ikke det, vi har i

    hukommelsen, på samme måde på harddisken. Det betyder at den er udtrykt på en form, som kan gemmes på en harddisk.
  35. Godt spørgsmål. Hvis man skal lave transaktioner, der er meget

    tilgængelige, hvad ligger man så under for?
  36. Lysets hastighed kan vi altså ikke rigtig gøre hurtigere. Fundamentally,

    the speed at which two servers can communicate is (according to modern physics) bounded by the speed of light. In the best case, two servers on opposite sides of the Earth— communicating via a hypothetical link through the planet’s core—require a minimum 85.1ms round-trip time (RTT; 133.7ms if sent at surface level).
  37. Enten er noget meget tilgængeligt eller meget rigtigt. Når man

    designer en database, så skal man vælge mellem høj tilgængelighed eller stærk semantik. Man kan ikke få begge dele.
  38. Og nu kommer der et gyldent citat… Hvis I skulle

    skrive dagbog over alle de små ting, som der sker i løbet af jeres dag, så ville det jo være uoverkommeligt.
  39. Det skal I huske på når I bliver bedt om

    at lave fyldestgørende dokumentation. Man kan ikke beskrive et system til fulde uden at lave det.
  40. Nøgleordene her er en af dem. Meget tilgængelige transaktioner er

    baseret på idéen om at servere ikke behøver koordinere med hinanden før en af dem besvarer en forespørgsel.
  41. Dem skal vi selvfølgelig lige gennemgå. Der nævnes to interessante

    koncepter, henholdsvis last-write-wins (LLW) og dirty reads/writes.
  42. Her er jeg gået ind på Learn for at opdatere

    denne forelæsnings beskrivelse.
  43. Det giver lidt sig selv. Men det er jo ikke

    sikkert at det, der sidst er ankommet, er det rigtige. Det sidste, der bliver sendt til en server og gemt i en database, er det som der bruges.
  44. Når der er forrædere, så er tilliden i systemet begrænset.

    Tænk på mit eksempel fra sidst, hvor jeg nævnte to personer, der arbejder i det samme dokument. Den ene person sætter sig på et fly og arbejder videre uden at være forbundet til Internettet. Den anden sletter dokumentet i mellemtiden. Den ene person lander igen og prøver at gemme dokumentet i deres fælles database. Hov!
  45. Det vil sige når en transaktion kan læse noget, som

    ikke er gemt på harddisken endnu. A dirty read (uncommitted dependency) occurs when a transaction is allowed to read data from a row that has been modified by another running transaction and not yet committed.
  46. Det tager tid for alle servere at blive enige om

    en værdi, og det kan man ikke vente på. I et meget tilgængeligt system er consistency begrænset - det kan ikke garanteres.
  47. Igen: hvis der nu er 8 servere, der mener at

    en værdi er 1, og 2 servere, der mener at værdien er 2… I et meget tilgængeligt system konvergerer alle værdier mod den samme værdi.
  48. Det er fordi de fleste distribuerede systemer er databaser. Hvorfor

    har vi om alle de her tunge koncepter, der drejer sig om databaser?
  49. Det er jo det, som vi lige har talt om.

    Distribuerede systemer er når to eller flere sandheder bevæger sig - eller konvergerer - mod den samme sandhed.
  50. Som jo er når to computere ikke taler direkte til

    hinanden, men gennem en tredje. Vi har talt om indirekte kommunikation.
  51. Enten udvider vi med mere CPU og RAM eller også

    tilføjer vi flere servere i et cluster. Vi har talt om horisontal og vertikal skalering.
  52. Eller: om at få det til at fungere når flere

    forskellige vil behandle de samme data på samme tid. Vi har talt om transaktioner.
  53. Og er herunder blevet enige om at distribuerede systemer i

    praksis er en afvejning. … og så har vi talt om de grundlæggende elementer i teorien bag det hele.