Distribuerede systemer, CBS, 5. oktober 2015

Slides til forelæsningen om transaktioner i distribuerede systemer på CBS d. 5. oktober 2015 kl. 08:00.

Transcript

1. Transaktioner Distribuerede systemer på CBS, oktober 2015 DS-bogen, kapitel 16 og 17
2. speakerdeck.com/kaspertidemann Mine slides til undervisningen ligger på Speaker Deck.
3. Vi starter med gennemgang af nogle spørgsmål fra sidst. Et par spørgsmål fra sidste gang.
4. Windows PowerShell Brug Get-Process eller aliaserne ps eller gps.
5. Vi begynder med kapitel 16 i DS-bogen. DS.kapitel( ); 16
6. Hvad er en transaktion? Vi kender dem fra stort set alle sammenhænge, men hvad er de?
7. At slå op i ordbogen er altid godt. Ifølge Dansk Sprognævn
8. En generel definition indenfor IT. Behandling af informationer i operationer, der enten lykkes eller ikke.
9. Et eksempel på “the lost update problem”. Ændringer kan gå tabt 1) beløb = kontoA.læsBeløb(); ! 2) kontoA.sætInd(beløb * 1.1); 1.000 kr. ! 1.100 kr. 1) beløb = kontoA.læsBeløb(); ! 2) kontoA.sætInd(beløb * 1.1); 1.000 kr. ! 1.100 kr.
10. “The inconsistent retrievals problem” ved flytning af beløb mellem konti. … og læsninger kan være forkerte. 1) kontoA.hævBeløb(500); 1.000 kr. -> 500 kr. 1) kontoAogB.læsBeløb(); 1.500 kr. 1) kontoB.sætInd(500); 1.000 kr. -> 1.500 kr. (Bemærk: vi er ved at flytte penge mellem to konti. Derfor forsvinder de 500 kr. jo ikke bare - de er ved at blive flyttet.)
11. Sig hej til seriel ækvivalens. Når to transaktioners operationer giver samme resultat.
12. Altså en-efter-en versus samtidig afvikling af operationer. Om interleaving 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.
13. Et eksempel på løsningen af “the lost update problem”. Eksemplet fra før 1) beløb = kontoA.læsBeløb(); ! 2) kontoB.sætInd(beløb * 1.1); 1.000 kr. ! 1.100 kr. 3) beløb = kontoA.læsBeløb(); ! 4) kontoC.sætInd(beløb * 1.1); 1.100 kr. ! 1.210 kr.
14. Vi skal tale om atomicitet igen. Det talte vi jo også om sidst - lad os få det på banen igen.
15. Et lille tip: flyv direkte. Det kan man jo nu. Bestilling af flybilletter 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.
16. Det kunne undgås med en transaktion, der på drakoniansk vis enten ville lykkes helt eller slet ikke. Drako var en græsk politiker med nogle meget stramme love.
17. Konflikter kan opstå når der er afhængigheder i rækkefølgen. Årsag til konflikter 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
18. Et eksempel på afvikling under streng hensyntagen til rækkefølgen. Microsoft Access
19. ACID er Atomicity, Consistency, Isolation og Durability. Tænk MySQL, PostgreSQL, Oracle og så videre.
20. ACID er et stærkt koncept fra den gamle skole indenfor databaser. ACID i en database 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.
21. Locks på værdier, deadlocks og wait-for-grafer. En måde at sørge for seriel ækvivalens er ved at anvende locks.
22. Om hvordan det forholder sig med læse- og skrive-låse. En opklarende tabel 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
23. læsBeløb(); på kontoA og kontoB skaber en deadlock-situation. Deadlocking er ikke godt Transaktion 1 Transaktion 2 Operationer Låse Operationer Låse kontoA.sætInd(100); skrive-lås på kontoA kontoB.sætInd(200); skrive-lås på kontoB kontoB.læsBeløb(); (venter på skrive- låsen på kontoB) kontoA.læsBeløb(); (venter på skrive- låsen på kontoA)
24. Det er essensen af two-phase locking i en transaktion. 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.
25. Locking er en form for concurrency control. En måde at styre samtidig afvikling på, så det ikke går rabundus.
26. Vi har alle prøvet at gemme et Excel-ark, som en anden har åbent. Locking i dagligdagen
27. Den form for optimisme kan skabe bedre performance. Optimistic concurrency control Det 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 en transaktion committes, så undersøges hvorvidt de data, den har læst, er blevet ændret i mellemtiden. Hvis ja, så forsøges transaktionen gentaget.
28. Altså: adgang til værdier styres af tidsstempler. Timestamp ordering En transaktion må ikke 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.
29. Et tidsstempel kan være et tidspunkt eller blot en værdi som stiger. Det har at gøre med Leslie Lamport. Ham vender vi tilbage til.
30. Om concurrency control; det skal man være opmærksom på. Et citat fra bogen They all limit to some extent the potential for concurrent operation.
31. Pause
32. Vi fortsætter med kapitel 17 i DS-bogen. Yes! DS.kapitel( ); 17
33. Transaktioner er distribuerede når de anvender værdier fra flere forskellige steder. Fx når en transaktion læser en værdi fra et cluster af database-noder.
34. Når en transaktion bliver implicit distribueret. Noder i et cluster curl -X GET http://1.1.1.1:8098/users/1
35. Når flere forskellige maskiner samarbejder om en opgave. Kort om clusters og CPR-registre
36. Spørgsmålet er så: hvem styrer hvad? Nu kommer vi til noget af det, der er virkelig interessant.
37. Sendebude bliver sendt ud og hjem, men nogle bliver slået ihjel undervejs. Two Generals’ Problem
38. Det er IT-verdenens svar på “du er den!”. Udpegelse af en leder 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 persisteres og kunne genskabes - det gøres via en log over hvad der er sket.
39. Sådan ser en atomic commitment protocol ud. Two-phase commit protocol - Er I klar? - Ja, mand! - På hvad? - Møz!
40. Atomic commitment protocol, forklaret. Two-phase commit protocol 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.
41. Den form for koordinering er et eksempel på konsensus i et distribueret system. Konsensus vender vi tilbage til senere.
42. Stjålet direkte fra Wikipedia. Som en chef. Kort definition 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.
43. Demokrati er en form for konsensus i den virkelige verden. Begrebet anvendes ikke kun indenfor IT - bestemt ikke.
44. Men igen: hvad sker der hvis en deltager går rabundus? Altså hvis en server crasher, fx.
45. Evnen til at håndtere - og udbedre! - fejl, der opstår løbende, er essentiel. Hvis det hele går sydpå 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 indføres 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).
46. Beslutningsdygtigt flertal. 2/3.
47. Som i livet generelt er det ofte flertallet som bestemmer. Flertallet 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.
48. Det har noget at gøre med de papers, som vi gennemgår til næste forelæsning. Vi går i dybden med byzantinske tilstande mv. næste gang.
49. Navnesammenfaldet omkring “bit” er en tilfældighed. To eksempler
50. I den ene ende af skalaen har vi BitTorrents klientfokuserede udbedring. BitTorrent Forbinder til andre klienter via et distribueret hash table, en slags kort der kan slås op i. En torrent indeholder et hash af de data, som den består af. Når klumper af data er downloadet, så sammenlignes de med hash-værdierne - og hvis de ikke stemmer overens, så smides data ud igen.
51. I den anden ende af skalaen har vi Bitcoins transaktionsbaserede form. Bitcoin Består af en block chain, der indeholder alle transaktioner som er foretaget i netværket. Information om block chain’en bliver sendt ud til alle noder via flooding, som vi talte om til sidste forelæsning. Block chain’en har en Genesis Block, og derfra følger en lang række blocks, der indeholder alle handler - dermed kan hele Bitcoin-forløbet genskabes fra start tilslut.
52. Transaktioner anvendes mange andre steder, fx i filsystemet på jeres computer. Det kaldes også et journaliseret filsystem.
53. Min Mac kører med journaliseret HFS+. Diskværktøj
54. I tilfældet NTFS. … og fra Windows’ hjemmeside
55. Pause
56. Nu starter den rigtige teori om distribuerede systemer! papers( ); Leslie Lamport
57. Først en betragtning omkring det at læse papers. Og navnlig definitionerne og det sprog, der kommer ud af dem.
58. Tænk lemmaer, sigmaer og andre matematiske symboler. En lille bid tekst
59. Grand old man indenfor distribuerede systemer. Leslie Lamport
60. En tidlig definition af kausalitetsbegrebet. Happened before Leslie Lamport fremsætter i juli 1978 idéen om begivenheder, der er indtruffet før hinanden. a → b
61. Et simpelt koncept, egentlig. Clocks Der behøver ikke være tale om et rigtigt ur, men alene om en logisk konstruktion, der sørger for at ændre en værdi fortløbende. hvis a → b, så C(a) < C(b)
62. Pludselig kan vi se den samlede rækkefølge. Total ordering Brugen af clocks gør det muligt at opstille en samlet rækkefølge over begivenheder i et distribueret system. a 㱺 b Ci(a) < Cj(b) eller Ci(a) = Cj(b) og Pi ≺ Pj hvis
63. Sidstnævnte er en vigtig pointe. Resource scheduling 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.)
64. Yes. Eller sagt på en anden måde En node kan få adgang til en ressource når den har en forespørgsmål 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
65. Problemet er at en begivenhed kan være vigtig, men hvis den fx ankommer for sent, så honoreres den reelle rækkefølge ikke. Ergo: der kan anvendes rigtige ure i stedet for tilnærmede.
66. Tænk på dit gode, gamle armbåndsur. Løsningen er at bruge tid Altså rigtig tid. 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.
67. Et af universets mysterier? Ja, jo, okay så. Og endelig: et kryptisk citat One of the mysteries of the universe is that it is possible to construct a system of physical clocks which, running quite indepedently of one another, will satisfy the Strong Clock Condition.
68. Opsummering. For god ordens skyld.
69. Tak for i dag! For spørgsmål, skriv til mig på kt@tdmn.co.