Lezione n - Dipartimento di Informaticaricci/17-04-13-Distributed-Storage.pdf · Lezione n.14 P2P...

1Laura Ricci

P2P in DataCenters: DynamoDipartimento di InformaticaUniversità degli Studi di Pisa

Lezione n.14P2P IN DATACENTERS:

AMAZON DYNAMO

Laura Ricci17/4/2013

Università degli Studi di PisaDipartimento di Informatica

2Laura Ricci


DHT: APPLICAZIONI● DHT utilizzate in diverse applicazioni/sistemi commerciali

● rete KAD/ Trackerless Bittorrent

● recentemente le tecnologie P2P sono state utilizzate per la realizzazione di storage systems su larga scale

● questi sistemi sistemi si differenziano dai sistemi P2P “puri” per:● maggior affidabilità delle macchine● maggior raggiungibilità (no NAT)● minor livello di dinamicità

● Esempi:Dynamo: Amazon

Cassandra: Facebook Voldemort: LinkedIN Big Table: Google

3Laura Ricci


ACID: DA WIKIPEDIA● Transazione = singola operazione logica, termine utilizzato nel contesto dei

database tradizionali

● Esempio:● il trasferimento di fondi da un conto ad un altro che coinvolge un insieme

di modifiche, come un addebito ed un accredito

● ACID (Atomicity, Consistency, Isolation, Durability): insieme di proprietà che garantiscono che le transazioni vengono elaborate in modo affidabile

● Proprietà definite da Jim Gray nel 1970, che propose un insieme di tecnologie per verificarle.

● ACID: termine coniato nel 1983, ripreso recentemente....● garantire tali proprietà in large scale storage system nel caso di “big

data” (Facebook, Google, Amazon) risulta molto complesso....

4Laura Ricci


ACID: ATOMICITY● Atomicity: transazione “tutto o nulla”, se una parte della transazione

fallisce, l'intera transazione fallisce e lo stato dei dati rimane invariato. La proprietà deve essere garantita anche in presenza di guasti, errori,...

● Esempio: ● un database con due campi, A e B● vincolo di integrità: somma di A e B uguale a 100

CREATE TABLE acidtest (A Integer, B Integer Check (A + B = 100));

● transazione valida: sottrai 10 ad A ed aggiungi 10 a B.

● violazione di atomicity: dopo aver sottratto 10 da A, la transazione non è

in grado di modificare B.

5Laura Ricci


ACID: CONSISTENCY

● Consistency: tutti i vincoli definiti sui dati devono essere rispettati dalle

transazioni definite

● Esempio:

● un database con due campi, A e B

● vincolo di integrità: somma di A e B uguale a 100

CREATE TABLE acidtest (A Integer, B Integer Check (A + B = 100));● Una transazione che sottrae 10 da A, ma non lo sottrae a B può essere

atomica, ma non rispetta il vincolo di integrità. L'intera transazione deve

essere cancellata ed il sistema riportato ad uno stato consistente

6Laura Ricci


ACID: ISOLATION● Isolation: l'esecuzione concorrente di un insieme di transazioni restituisce

lo stesso stato dei dati che si sarebbe ottenuto eseguendo le transazioni sequenzialmente

● riguarda il controllo dell'esecuzione concorrente delle transazioni

● Esempi:

7Laura Ricci


ACID: DURABILITYIsolation: Il risultato di una transazione deve essere memorizzato su una memoria non volatile prima del commit della transazione

● Esempio: ● un database con due campi, A e B● vincolo di integrità: somma di A e B uguale a 100

CREATE TABLE acidtest (A Integer, B Integer Check (A + B = 100));

● una transazione atomica trasferisce 10 da A a B. ● a questo punto viene inviato un messaggio di “successo” all'utente. ● le modifiche, tuttavia, sono ancora memorizzate in un buffer in attesa di

essere memorizzate su disco. ● se c'è un fault e la memorizzazione non avviene, viene ad essere invalidata

la durability

8Laura Ricci


ACID E LARGE SCALE STORAGES

● Molto difficile garantire proprietà ACID per applicazioni web-based● “Big Data”, “Big Users”● alti tassi di letture/scritture● dati non strutturati (no schema)

● SQL-based database non scalano

● necessarie soluzioni più flessibili

9Laura Ricci


ACID E LARGE SCALE STORAGES

● Molto difficile garantire queste proprietà per applicazioni web-based● “Big Data”, “Big Users”● alti tassi di letture/scritture● dati non strutturati (no schema)● RDBMS non scalabili....

● soluzioni possibili● replication● sharding

10Laura Ricci


AUMENTARE LA SCALABILITA'

● Soluzione: replicazione dell'intero database, vertical scaling

● Architettura scalabile

● Aumenta la scalabilità delle operazioni

di lettura

● Sincronizzazione di letture

11Laura Ricci


AUMENTARE LA SCALABILITA'

● Soluzione: sharding, horizontal scaling

● partizionare il database tra diversi host

● Aumenta la scalabilità sia delle operazioni di lettura che di quelle di scrittura

● Non possibili transazioni tra shard diverse

● Soluzione iniziale adottata da ● Facebook, ● YouTube, ● Yahoo

12Laura Ricci


EFFICIENZA CONTRO COSTO

13Laura Ricci


RIPENSARE L'ARCHITETTURA

14Laura Ricci


NOSQL: NUOVE ARCHITETTURE

● Una applicazione sociale non è una banca....richiesti livelli inferiori di ACID

● Distributed Data Storage:rilasciano una o più delle proprietà ACID

15Laura Ricci


CONSISTENCY MODELS

● Strong Consistency: dopo il completamento di un aggiornamento, tutti gli accessi successivi fanno riferimento al dato aggiornato

● Eventual Consistency: il sistema non garantisce la restituzione del valore aggiornato

● finestra di incostistenza● in seguito, tutti gli accessi restituiscono il solito valore

16Laura Ricci


DYNAMO: LE SFIDE

● High available key-value store

● Sfida: reliability/availability at maasive scale

● decine di milioni di clienti

● decine di migliaia di nodi

17Laura Ricci


● NOSQL storage systems utilizzato da Amazon (insieme ad altri, S3 Simple Stotage System,....)

● influenza su architettura di diversi altri storage systems

● Caratteristiche:● “highly decentralized, loosely coupled, service oriented architecture”● infrastruttura: decine di migliaia di server geograficamente dislocati

sul globo● commodity hardware● “standard mode of operation”: nodi soggetti a fallimento

DYNAMO: CARATTERISTICHE GENERALI

18Laura Ricci


DYNAMO: CARATTERISTICHE GENERALI

● Obiettivi:● rinunciare alla strong consistency in favore di

● availability● scalability

● service-level agreement● scalabilità● semplicità

● architettura peer to peer like: ogni nodo con le stesse responsabilità● eterogeneità dei nodi

19Laura Ricci


● Key-value storage

● get(key): restituisce una lista di oggetti ed un contesto● può restituire un insieme di diversi oggetti associati alla chiave se

esistono più versioni dello stesso dato in conflitto. ● contesto: insieme di metadati, utilizzato per l'implementazione del

versioning

● put(key, object, context): non restituisce alcun valore● contesto: come sopra

● key, object:● non interpretati da Dynamo● considerati come vettori di bytes● key ottenuta mediante l'applicazione dell'algoritmo MD5

DYNAMO API

20Laura Ricci


DYNAMO: SCELTE DI PROGETTO

● Data Partitioning

● Replication

● Data Versioning

● Esecuzione put e get

● Membership

● Gestione dei Fallimenti

21Laura Ricci


DATA PARTITIONING

● Partitioning dei dati basato su consistent hashing● mapping dei dati “alla Chord”● 1-hop routing

22Laura Ricci


DATA PARTITIONING: 1-HOP DHT● Ogni peer memorizza nella propria routing table tutti gli altri peer

dell'overlay

● Fully meshed overlay● routing semplificato ed efficiente● aumenta dimensione routing table● overhead per la gestione delle routing table: ogni nodo deve essere

informato di ogni cambiamento nell'overlay● alta richiesta di banda per la diffusione degli aggiornamenti

● 1-hop DHT● enterprise DHT: maggiore capacità computazionale e richiesta di

banda● maggiore stabilità dell'overlay● alto numero di query /secondo molto alto● scalabilità fino ad alcune centinaia di migliaia di nodi.

● ragionevole per una enterprise DHT

●

23Laura Ricci


CONSISTENT HASHING: DISTRIBUZIONI

● Analisi della distribuzione dei dati

● Parametri4,096 nodiSpazio degli indirizzi di m=22 bitsNumero massimo di documenti e/onodi = 222=4.194.304

Più simulazioni, le chiavi per nodi e documenti generate in modo random, in media 500,000 documenti Ottimo = ~122 documenti per nodoGrafico: mostra quanti nodi (asse y) memorizzano un certo numero di documenti (asse x)

Distribuzione Ottima dei Documenti sui Nodi del

Sistema

24Laura Ricci


DYNAMO: CAUSE DI SBILANCIAMENTO

●

Distribuzione deinodi non perfettamenteuniforme

Distribuzione deidati non perfettamente uniforme

Hot Spots Eterogeneità dei nodi

25Laura Ricci


DYNAMO: VIRTUAL SERVERS

● per ogni nodo più identificatori logici● ogni identificatore rappresenta un virtual server (VS)

● ogni nodo esegue più VS● responsabile per più regioni non contigue● numero di VS proporzionali alle risorse di calcolo del nodo

Virtual Server (regioni) stesso colore sono gestiti dallo stesso nodo

26Laura Ricci


DYNAMO: ARCHITETTURA

27Laura Ricci


DYNAMO: REPLICAZIONE● “the standard mode of operation” di Dynamo prevede i crash delle macchine

● per assicurare l'availability dei dati, i dati vengono replicati

● ogni dato replicato sugli n-1 successori del nodo su cui è mappato sull'anello (n parametro configurabile, tipicamente 3)

● Preference List= Lista di nodi che contengono le repliche del dato

● replicazione aumenta anche la performance● richieste read-only possono essere

distribuite a qualsiasi replica● “copie multiple”: necessari meccanismi per la consistenza delle copie replicate

28Laura Ricci


REPLICAZIONE E VIRTUAL SERVERS

● Mapping Virtual Node-nodi fisici: ● evitare che repliche dello stesso VN appartengano allo stesso nodo fisico● se più repliche mappate sullo stesso nodo fisico, considerare nodi fisici

successivi

29Laura Ricci


DYNAMO: JOIN● nodi aggiunti e rimossi esplicitamente dall'amministratore

● sistema deve fornire servizi anche durante le operazioni di join/leave

● inserzione/eliminazione di nodi: redistribuzione dei dati e delle repliche

● Membership management

● Tutti i nodi devono essere informati di una modifica all'overlay (1-hop

DHT)● Algoritmi di gossip per propagare le modifiche all'overlay

30Laura Ricci


DYNAMO: JOIN● Il nuovo nodo annuncia sua presenza● gli immediati vicini (a destra e sinistra) modificano la ownership delle chiavi e

delle repliche: operazione sincrona● il nuovo nodo a copia i dati dai vicini: operazione asincrona● aggiornamenti inviati via gossip agli altri nodi: operazione asincrona

Il nodo X si unisce al sistema

31Laura Ricci


DYNAMO: JOINAggiornamento asincrono delle viste: un nodo che non possiede una vista aggiornata può inoltrare le richiesta ● ad un vicino n del nuovo nodo x che non possiede più l'informazione

● n inoltra l'informazione ad x● ad x che non possiede ancora il nuovo dato

● utilizzati i vector clock per determinare la validità dei dati

Il nodo X si unisce al sistema

32Laura Ricci


DYNAMO: LEAVE

● Verifica periodica della presenza dei nodi effettuata durante i cicli gossip del protocollo epidemico

● I vicini del nodo caduto aggiornano i range e si scambiano dati, in modo da avere un numero consistente di repliche

33Laura Ricci


DYNAMO E DHT CLASSICHE: DIFFERENZE

● Le tecniche viste nei lucidi precedenti sono simili a quelle utilizzate nelle DHT

“classiche”

● ma....Dynamo utilizza la DHT per memorizzare dati applicativi

● Problema principale

● versioning: gestione di diverse versioni dello stesso dato

● sincronizzazione sulle write alle diverse versioni

● tecniche utilizzate:

● vector clocks

● quorum

34Laura Ricci


DATA VERSIONING

● una operazione di put può terminare prima che il nuovo valore sia stato propagato a tutte le copie

● una successiva get() può restituire dati non contenenti ultimi aggionamenti

● high availability, ma eventual consistency

● Alcune applicazioni di Amazon possono tollerare questo modello di consistenza:

● shopping carts● operazione “add to cart”, deve essere sempre eseguita

● make money!● se la copia locale non è la più recente

● eseguire comunque l'operazione● riconciliare successivamente versioni “divergenti”

35Laura Ricci


SHOPPING CART EXAMPLE

Shopping cart: contiene i libri acquistati, replicata su più nodi(A,B)

Client: effettua operazioni sulla propria shopping cart

Aggiornamenti eseguiti su nodi diversi della DHT

Quorum: insieme di nodi aggiornati dalla prima put

“write sempre eseguita”, ma inconsistenza finale

36Laura Ricci


DATA VERSIONING● Approccio: scrivere sempre, riconciliare versioni contrastanti al momento

della lettura

● “riconciliazione sintattica”● la nuova versione “ingloba le vecchie versioni “● conflitto rilevato in modo automatico

● “riconciliazione semantica”● quando non è possibile una riconciliazione “automatica”● fallimenti/ aggiornamenti concorrenti● riconciliazione effettuata dal client:

● collassa in una unica versione più “rami” corrispondenti a “storie diverse di aggiornamento”.

● Per entrambe: utilizzo di vector clocks

37Laura Ricci


VECTOR CLOCKS: DEFINIZIONI● Ogni nodo mantiene un clock logico: contatore incrementato ogni volta che si

esegue un aggiornamento

● Vector Clock: lista di coppie <nodo, contatore>● un contatore per ogni nodo che ha aggiornato il documento

● definiscono relazioni di causalità tra le versioni

● ordinamento parziale tra vector clocks:● v

1 ≤ v

2, sei contatori in v

1 sono tutti minori di quelli corrispondenti in v

2

● se v1 ≤ v

2, la versione corrispondente a v

2 è più aggiornata ed ingloba quella

associata a v1, la versione associata a v

1 può essere scartata

● altrimenti le due versioni non sono correlate● aggiornamenti paralleli o presenza di faults● necessaria riconcialiazione semantica da parte della applicazione (ad

esempio, merge)

38Laura Ricci


MODIFICHE SU DATI REPLICATI

39Laura Ricci


VECTOR CLOCKS

40Laura Ricci



41Laura Ricci



42Laura Ricci



43Laura Ricci



44Laura Ricci


RISOLUZIONE DEI CONFLITTI● Dato replicato su 3 nodi A, B, C

● Un client C1 crea un nuovo

oggetto e lo memorizza● memorizzazione eseguita

dal nodo A● A crea un vector clock che

individua la versione D1

dell'oggetto

● Successivamente D1 verrà

propagata a B ed a C

45Laura Ricci


RISOLUZIONE DEI CONFLITTI

● Dato replicato su A, B, C

● Il client C1 effettua un aggiornamento del dato, l'aggiornamento è gestito dal nodo A

● Nel sistema ora esistono le versioni D

1 e D

2 dell'oggetto, ma

● D2 “incorpora” D

1

● D1 può essere eliminata

● Politica “always write”: gli altri nodi non vengono a conoscenza immediantamente di D

2

46Laura Ricci



● il client C1 effettua un nuovo

aggiornamento sullo stesso dato● utilizza la versione D

2, che già

possedeva perchè la aveva aggiornata in precedenza

● l'aggiornamento viene gestito dal nodo B

● il client C2

● legge la versione D2 dal nodo A

● la aggiorna● l'aggiornamento è gestito dal

nodo C

47Laura Ricci



● un client C3 legge le versioni D3, e

D4 e rileva un conflitto

● necessaria riconciliazione

● La riconciliazione è effettuata dal nodo A

48Laura Ricci



● A gestisce il nuovo aggiornamento

● Il read context è un “riassunto”

dei vector clock di D3 e D4.

● “riconcilia” le versioni

● Versione D5: riconciliata e scritta

da A

49Laura Ricci


RISOLUZIONE DEI CONFLITTI● Dato replicato su 3 nodi A, B, C

● Un client C1 crea un nuovo

oggetto e lo memorizza

● memorizzazione eseguita

dal nodo A

● A crea un vector clock che

individua la versione D1

dell'oggetto

● Successivamente D1 verrà

propagata a B ed a C

50Laura Ricci


RISOLUZIONE DEI CONFLITTI● Dato replicato su A, B, C

● Il client C1 effettua un aggiornamento del dato, l'aggiornamento è gestito dal nodo A

● Nel sistema ora esistono le versioni D

1 e D

2 dell'oggetto, ma

● D2 “incorpora” D

1

● D1 può essere eliminata

● Politica “always write”: gli altri nodi non vengono a conoscenza immediantamente di D

2

51Laura Ricci



● Il dato viene modificato e la

modifica viene gestita dal nodo B

● B non ha ancora ricevuto

l'aggiornamento da A

● Nel sistema esistono due versioni,

quella di A e quella di B

52Laura Ricci



● Un client legge le due versioni da A

e da B

● D4 inglobata da D

3

● La versione D4

può essere scartata

automaticamente

● Il sistema mantiene la versione D5

53Laura Ricci


QUORUM MODELN, W, R: quorum model● N repliche● W numero repliche aggiornate in modo sincrono (non tutte le N repliche)● R numero di repliche lette da una operazione di get()

● Per ottenere strong consistency W + R > N

54Laura Ricci


QUORUM MODELN, W, R: quorum model:

● N repliche● W numero repliche aggiornate in modo sincrono (non tutte le N repliche)● R numero di repliche lette da una operazione di get()

● tipica configurazione per Dynamo

● (N,R,W) == (3,2,2)

● Se si accettano inconsistenze

● high performance read: R==1, W==N

● valori bassi di R e W portano ad un numero maggiore di inconsistenze

55Laura Ricci


ESECUZIONE PUT( ) E GET( )● PUT( )

● il coordinatore genera un nuovo vector clock (a partire dalla versione letta) e lo memorizza localmente

● invia il dato modificato, insieme al vector clock, alle N repliche● attende la risposta da W-1 nodi● la put termina quando almeno W-1 nodi hanno riportato successo

● GET( )● invio la richiesta ad N nodi, aspetto R risposte● scarta versioni inglobate da altre: “riconcialiazione sintattica”● restituisce versioni che pensa non essere correlate● il client effettua la “riconciliazione semantica”● il dato modificato viene riscritto

56Laura Ricci


ESECUZIONE PUT( ) E GET( )● I client possono inviare le loro richieste

● al nodo responsabile del dato (coordinatore)● minore latenza, put(), get() inserite direttamente nel codice del client

● ad un load balancer● aumenta la latenza

● PUT( )● il coordinatore genera un nuovo vector clock e lo memorizza localmente● invia il vettore alle N repliche● attende la risposta da W-1 nodi

● GET( )● invio la richiesta ad N nodi, aspetto R risposte● scarta versioni inglobate da altre, restituisce versioni non correlate● “riconciliazione” e riscrittura versioni non correlate● se R+W<N

57Laura Ricci


READ REPAIR

58Laura Ricci


READ REPAIR

59Laura Ricci


READ REPAIR

60Laura Ricci


READ REPAIR

61Laura Ricci



62Laura Ricci



63Laura Ricci


DYNAMO: TRANSIENT FAILURES

● A causa di irraggiungibilità temporanea di nodi il quorum di scritture può non essere raggiunto

● Sloppy quorum = quorum approssimativo

● Creazione di copie transienti: hinted handoff

● Riconciliazione successiva

● A irraggiungibile● PUT inviata a D● Successivamente quando D riesce raggiungere A

● invia replica ad A ● rimuove la replica

64Laura Ricci


DYNAMO: PERMANENT FAILURES

● Versioning non garantisce la consistenza● se non è richiesto un quorum di maggioranza, ● se si verificano fallimenti

● occorre comunque verificare periodicamente che le copie non siano in conflitto

● utilizzo di Merkel trees● anti-entropia

65Laura Ricci


DYNAMO: ANTI ENTROPIAMerkel Tree:● Foglie: hash dei valori● Nodi interni: composizioni di hash delle foglie

● Ogni nodo mantiene un Merkel tree per ogni range di chiavi da lui gestito

● Anti entropia: scambiare parti di Merkle tree

● Protocollo “divide and conquer”:● contatta un altro nodo sull'anello scelto in modo uniforme● se i due nodi gestiscono una replica dello stesso range, scambio delle root

dei Merkel tree● se le root coincidono, stop● se non coincidono, ripetere ricorsivamente i controlli sui figli

● Merkel tree ricalcolato per ogni join/leave

●

66Laura Ricci


DYNAMO: CONCLUSIONI● CAP

● Strong Consistency:NO● Tutti i nodi vedono lo stesso dato nello stesso tempo

● Availability:SI● Partition Tolerance:SI

● Il sistema continua ad operare nonostante perdite di messaggi o fallimento di alcune sue parti

● KEY/Value Storage: put e get● Data Partitioning: consistent hashing● Load balancing: virtual servers● Replication: preference list, successor nodes● Data Versioning: vector clocks, conflitti risolti al momento della lettura

dalla applicazione● Membership: join/leave gestiti dall'amministratore, gossip-based update

delle viste● Gestione fallimenti transienti: hinted hand-off● Gestione fallimenti permanenti: Merkle trees

67Laura Ricci


CAP THEOREM

● Consistency: grado di consistenza di un sistema dopo l'esecuzione di un aggiornamento

● Availability: possibilità di scrivere/leggere un dato in ogni istante

● Tolleranza ai partizionamenti: capacità del sistema di lavorare in presenza di partizione delle rete

● CAP Theorem: un sistema può soddisfare al massimo 2 delle proprietà CAP

● in generale, scegliere tra C e A● database tradizionali: preferenza a C● Web applications: preferenza A

68Laura Ricci


CAP: CLASSIFICAZIONE DEI SISTEMI

Lezione n - Dipartimento di Informaticaricci/17-04-13-Distributed-Storage.pdf · Lezione n.14 P2P...

Documents

Transcript of Lezione n - Dipartimento di Informaticaricci/17-04-13-Distributed-Storage.pdf · Lezione n.14 P2P...