Distribuerede systemer på CBS, 28. september 2016 - transaktioner

Slides til undervisningen i distribuerede systemer på CBS d. 28. september 2016 omhandlende transaktioner.

Transcript

1. Velkommen til min undervisning. Distribuerede systemer på CBS, september 2016, mere Leslie Lamport
2. kt@tdmn.co. Skriv til mig, hvis I har brug for hjælp.
3. newsletter.tdmn.co Tilmeld jer hvis I vil vide mere om iværksætteri, investeringer og så videre.
4. En hurtig opfølgning fra sidst. Det tager vi lige.
5. 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
6. Problemet opstår jo hvis det her fx sker samtidig. SELECT * FROM students WHERE year = 2016; UPDATE students SET .. WHERE year = 2016;
7. … eller det her. UPDATE students SET .. WHERE year = 2016; UPDATE students SET .. WHERE year = 2016;
8. Hvilket programmeringssprog skal man vælge? Det var der en del af jer, der spurgte mig om sidst.
9. 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.
10. Her kan man se et billede af mig og hvordan det ser ud i DOM’en.
11. 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).
12. Vi starter med Leslie Lamport igen. Og hans berømte artikel, The Byzantine Generals’ Problem.
13. 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.
14. Mange sikkerhedsbrister skyldes at nogen udgiver sig for at være nogle andre. Tænk fx på tampering af beskeder og så fremdeles.
15. 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.
16. Har I nogensinde tænkt over hvorfor Uber virker så godt i USA?
17. 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.
18. En gruppe generaler med en eller flere forrædere i geledderne.
19. 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!
20. 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.
21. 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.
22. 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.
23. Det var det, som vi talte om sidst: et beslutningsdygtigt flertal. 2/3.
24. 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.
25. … 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.
26. majority(v1 , .., vn-1 ) En majoritetsalgoritme er et generelt begreb, der dækker over at afgøre hvilken værdi, der er korrekt.
27. 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.
28. 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?
29. 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.
30. Et lille filosofisk indspark. Mennesker bygger systemer, der minder om dem selv.
31. Microsoft Dynamics CRM.
32. Hvis der ingen forrædere er, så kører det jo bare. – Er I klar? – Yes! – Så pyt da.
33. 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).
34. 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.
35. Ham til højre har ikke rent mel i posen. v v v x
36. 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.
37. Den sidste general er forvirret, for han får to beskeder. angrib : 0 angrib : 0 fald tilbage : 0 : 1 angrib : 0 : 1 – Øh?
38. 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.
39. 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.
40. 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.
41. 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.
42. 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.
43. Pause.
44. Tid til at se på en anden artikel. Vi skal tilbage til transaktioner og navnlig dem, der er meget tilgængelige.
45. 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.
46. Kom gerne med et bud. Hvad betyder det at en transaktion er serialized?
47. 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.
48. Et eksempel på et JSON-objekt i Chromes konsol.
49. Her har jeg serialized JSON-objektet, som gør det til en simpel tekststreng.
50. Godt spørgsmål. Hvis man skal lave transaktioner, der er meget tilgængelige, hvad ligger man så under for?
51. 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).
52. 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.
53. Et herligt spørgsmål sådan en navnløs onsdag. Hvordan fungerer jeres hjerner?
54. 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.
55. 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.
56. 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.
57. Dem skal vi selvfølgelig lige gennemgå. Der nævnes to interessante koncepter, henholdsvis last-write-wins (LLW) og dirty reads/writes.
58. Her er jeg gået ind på Learn for at opdatere denne forelæsnings beskrivelse.
59. 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.
60. 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!
61. 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.
62. 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.
63. 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.
64. Det er fordi de fleste distribuerede systemer er databaser. Hvorfor har vi om alle de her tunge koncepter, der drejer sig om databaser?
65. Det første begreb. Consistency.
66. Det andet begreb. Eventual consistency.
67. Det tredje begreb. Availability.
68. Det fjerde begreb. Consensus.
69. Det femte begreb. Convergence.
70. Det sjette begreb. Partitioning.
71. Det syvende begreb. Fault-tolerance.
72. Det ottende begreb. Replication.
73. Lad os lige tage det her på halvvejen. Midtvejsopsummering.
74. Den praktiske definition. Distribuerede systemer er når to eller flere computere opfører sig som en.
75. 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.
76. Som jo er når to computere ikke taler direkte til hinanden, men gennem en tredje. Vi har talt om indirekte kommunikation.
77. Væsentlige bestanddele i ethvert distribueret system. Vi har talt om kerner og operativsystemer.
78. 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.
79. 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.
80. 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.
81. Jeg glæder mig til at se jer næste gang. Tak for i dag!