Avui toca comentar el segon article sobre nous models de bases de dades. Per tant, nens i nenes,
Dynamo. Per cert, un dels autors del paper és
Werner Vogels, CTO d'Amazon, i realment recomano molt el seu blog,
All things distributed. Vinga va, comencem...
Dynamo és una key-value store que és utilitzada ( i dissenyada i programada ) a Amazon. Suposo que tots sabeu a què es dedica Amazon i també podeu tenir una idea de com és la pàgina web. Per tant, no és una sorpresa quan veiem que dos dels principals objectius de Dynamo son:
- Escalabilitat.
- Alta disponibilitat.
Igual que la Google va dissenyar i programar la seva pròpia solució al emmagatzemament de dades, ja que no va trobar cap producte que pogués utilitzar, per tant Dynamo es va fer a mida. Hi ha molts serveis interns d'Amazon que només necessiten accés simple a un valor segons un clau. Per tant, una taula de hash.
Dynamo utilitza una barreja de tècniques ben conegudes dins de l'àmbit de sistemes distribuïts per aconseguir escalabilitat i disponibilitat, entre les quals hi ha la partició i replicació de dades entre els diferents nodes i versionat d'objectes. Ara bé, quan tenim objectes replicats i repartits a través de la xarxa apareixen problemes. Com ho fem per assegurar que totes les còpies dels objectes són la mateixa ? com ho fem perquè quan un usuari afegeixi un CD al seu carro de la compra, totes les còpies s'actualitzin? En aquest cas Dynamo utilitza una tècnica, semblant a un quòrum i un protocol descentralitzat de sincronització de rèpliques (
sona guai eh?, tranquils que ja explicaré una mica més endavant què és), a més, té un detector de fallades mitjançant un
protocol de gossip (hi haurà un article aviat només d'aquests protocols, no patiu). Tot això fa que els nodes d'emmagatzemament puguin ésser afegits i trets de la xarxa sense cap tipus de partionament o redistribució manual. Tot és automàtic.
Aquesta key-value store està en producció i ha estat provada repetides vegades, el seu primer gran repte va ser suportar tota la càrrega addicional del període nadalenc. Simplement va funcionar i va escalar el que va fer falta sense que ningú hi fes res (si més no, és el que diuen, jo no hi era :P).
Consideracions de disseny
Amazon al principi utilitzava RDBMS per tots els seus sistemes. Molts d'aquests sistemes guardaven la informaci i la consultaven per la clau primària, això vol dir que realment no utilitzaven totes les possibilitats d'aquests sistemes. A més, les funcionalitats de rèplica que ofereixen aquestes tecnologies trien la
consistència en comptes de
disponibilitat. Això en paraules planes vol dir que si la base de dades troba que un valor que està replicat (té "còpies de seguretat") té valors diferents entre les còpies, prefereix solucionar el problema en comptes de retornar el resultat, causant retards.
Per tant, els requeriments que tenia l'equip d'enginyers d'Amazon eren:
- Model de consulta: Operacions de lectura i escriptura a un element que simplement està identificat per una clau. No hi ha operacions que realitzin consultes a diferents elements a l'hora, simplement no hi ha necessitat de cap esquema relacional.
- Propietats ACID: Les bases de dades que implementen les 4 lletres tendeixen a tenir poca disponibilitat en casos extrems, per tant, es va decidir rebaixar la 'C' (Consistència), cosa que implica una millora en la disponibilitat.
- Eficiència: El sistema havia de funcionar (igual que Google/BigTable) en hardware senzill i barat, i tots les mètriques de latència estan preses en el 99.9 percentil de la distribució. Cosa que vol dir que SEMPRE ha d'anar molt ràpid.
- Altres: Dynamo funciona dins d'Amazon, per tant s'entén que és un entorn no hostil, per tant, no hi ha requeriments de seguretat, ergo, no hi ha ni autenticació i autorització.
Un cop tenim clars els requeriments passem al disseny de Dynamo.
En entorns de bases de dades distribuïdes és important el tema de la consistència entre rèpliques (com ja s'ha comentat abans). Normalment s'utilitza una coordinació síncrona de rèpliques per poder tenir una consistència fiable. Això implica que la disponibilitat del sistema és menor en alguns escenaris de fallada, ja que el motor de la base de dades marca les dades com no disponibles fins que està totalment segur que tot és correcte.
Dynamo ho fa diferent, utilitza tècniques de replicació optimista, que vol dir que els canvis es propaguen passi el que passi i que es permet continuar treballant amb normalitat tot i que hi hagi casos de desconnexió. Aquesta aproximació pot portar a casos on es poden trobar conflictes, lògicament aquests conflictes s'han de descobrir i arreglar. Ara bé:
- Qui ho resol?
- Quan ho resol?
Atenció amb la següent frase que té tela (i la poso en negreta perquè almenys jo, la primera vegada que la vaig llegir vaig caure de culs a terra): Dynamo està dissenyat per ser una data store que tard o d'hora serà consistent, cosa que vol dir que tots els canvis tard o d'hora arriben a tots els nodes. Que xulos que són.
Ara bé, perquè
tard o d'hora les dades siguin consistents s'han de resoldre les dues preguntes anteriors. La de
quan es resol vol dir si es fa durant les lectures de les dades o les escriptures. Normalment les resolucions es fan en les escriptures per mantenir les lectures senzilles. En el cas de Dynamo ho han fet diferent. I una altre vegada, al ser una base de dades per a Amazon, van considerar que era millor que les escriptures fossin més senzilles i ràpides, no és d'estranyar, perquè en el seu cas una escriptura implica que un usuari afegeix un producte al carro de la compra. Per tant, és important que l'operació d'afegir sempre funcioni.
La pròxima pregunta,
qui resol els problemes, les opcions són o bé que ho faci Dynamo o bé que ho faci el programa que està utilitzant Dynamo. Dynamo permet les dues dues, en cas de que sigui la mateixa key-value store que ho faci poca cosa hi pot fer, tant sols pot utilitzar polítiques ben senzilles com ara "l'últim d'escriure guanya". D'altre banda, en cas de que sigui l'aplicació que arregli els conflictes, al tenir tota la informació de què són les dades i d'entendre la lògica del sistema pot fer qualsevol cosa que sigui necessària.
Altres detalls tingut en compte en el disseny:
- Escalabilitat incremental
- Simetria: Cada de node que participa a Dynamo ha de tenir les mateixes responsabilitats que la resta. No hi ha rols especials (això ho converteix en un P2P).
- Descentralització
- Heterogeneïtat: Les màquines que formaran els nodes de Dynamo no seran iguals, i no seran super màquines, per tant, és necessari que el sistema tingui en compte el tipus de màquina que és cada node i que la seva càrrega sigui proporcional a les seves capacitats.
Arquitectura
L'arquitectura de Dynamo, recordem, ha de tenir maneres escalables i robustes de:
- Poder balancejar la càrrega.
- Detectar fallades.
- Recuperar-se de fallades.
- Sincronitzar les rèpliques.
- Detectar i reaccionar a sobrecarrega.
- Ésser capaç de treballar amb concurrència de tasques.
- Distribuir tasques.
- Agrupar requestes.
- Monitoritzar el sistema.
- Disparar alarmes en cas d'errors o de situacions estranyes.
- Configurar-se.
- Fer massatges als programadors (aquesta la he afegit jo, però crec que no ve d'aquí, francament).
Si heu llegit el post anterior, el de
BigTable recordareu que no es parlava en tant detall de l'arquitectura del sistema. Això és perquè l'equip de BigTable va poder aprofitar molts components que altres equips d'enginyers de Google ja havien implementat i que en part, solucionaven la majoria d'aquests problemes, d'altre banda, l'equip d'Amazon ho va haver d'implementar tot de dalt a baix.
Algunes de les tècniques clàssiques que utilitza Dynamo per tractar alguns dels problemes citats anteriorment (s'expliquen en més detall a continuació):
Problema |
Tècnica |
Avantatge |
|---|
Partionament de dades |
Hashing |
Té bona escalabilitat |
Bona disponibilitat per les escriptures. |
Rellotges vectorials amb reconciliació. |
La mida de la versió es deslliga de les tasses de renovació. |
Tractament de fallades temporals. |
Quòrum reduït |
Té bona disponibilitat i garantia de durabilitat quan algunes de les rèpliques no estan disponibles. |
Recuperació de fallades permanents. |
Anti-entropia utilitzant arbres de Merkle |
Sincronitza rèpliques divergents en segon terme. |
Detecció de fallades i de membres. |
Gossip protocols i de detecció de fallades. |
Manté la simetria i evita tenir un registre centralitzat per guardar la llista de membres i el seus estats. |
Interfície del sistema
Dynamo guarda els objectes amb les seves claus mitjançant una interfície simple. Ofereix dos mètodes,
get() i
put(). El mètode get localitza les rèpliques de l'objecte associat amb la clau al sistema d'emmagatzemament i retorna un sòl objecte en cas de que no hi hagi conflicte, o bé una llista amb els objectes amb conflictes amb un
context.
D'altre banda, el mètode put determina on les rèpliques de l'objecte haurien d'estar guardades i les hi escriu a disc. El context codifica meta-data (dades sobre dades), com per exemple la versió de l'objecte. Aquesta informació és guardada amb l'objecte de tal manera que el sistema en pot verificar la validesa.
Dynamo tracta tant la clau com l'objecte com un vector de bytes. L'algorisme de hashing per generar l'identificador de la clau és MD5, i genera un id de 128 bits.
Algorisme de partionat
Un dels requeriments de Dynamo és que pugui escalar. Això implica que té un mecanisme per partionar
dinàmicament les dades a través dels nodes. La sortida d'aquest algorisme de partionat és tractada com un espai circular o "anella". A cada node del sistema se l'hi assigna un valor aleatori en l'espai, cosa que representa la seva "posició" dins de l'anella.
Cada element de dades és identificat per un clau, la qual és assignada a un node aplicant-li la funció de hash, que ens retorna la seva posició en l'anella. Tot seguit seguim l'anella en sentit anti-horari fins que trobem el primer node amb una posició més gran que la posició teòrica de la clau. Per tant, cada node passa a ésser responsable d'una regió de l'anella. Per tant, una arribada o sortida d'un node dins el conjunt de nodes que usen Dynamo tant sols afecta als seus dos veïns.
El fet de que el mètode de hashing sigui uniforme planteja alguns problemes amb heterogeneïtat de les màquines que conformen l'anella, cosa que porta a un malt balanceig del sistema. Per tant, el que es fa és en comptes de assignar a cada node un sòl punt en el cercle, cada node és assignat diversos punts. Per tant, cada node passa a tenir "servidors virtuals", i cadascun d'aquests servidors és responsable per una posició de l'anella. Utilitzar nodes virtuals comporta entre d'altres els següents avantatges:
- Si un node cau, la càrrega que tenia aquest node és dispersada en la resta de nodes.
- Quan el node torna a estar de nou disponible, aquest accepta més o menys una quantitat equivalent de dades de la resta de nodes.
- El número de nodes virtuals que un node real té està decidit per les característiques del node.
Replicació
Dynamo replica les dades. Cada clau, k és assignada a un node
coordinador, aquest node serà el responsable de la replicació dels elements de dades. Per tant, a més de ser el responsable d'assegurar que els valors es llegeixin i s'escriguin a disc també serà el responsable de replicar aquestes dades en els anteriors N-1 nodes (en sentit antihorari) de l'anella. Per tant, cada node és responsable d'ell mateix i de les rèpliques en els seus N predecessors, preferiblement nodes reals, no virtuals.
Versionat de dades
El fet de que Dynamo ofereixi consistència tard o d'hora permet que les actualitzacions puguin ser propagades a totes les rèpliques de forma asíncrona. A efectes pràctics vol dir que una operació de put() contestarà al client abans de que s'hagin actualitzat totes les rèpliques, cosa que implica que puguin existir escenaris en que el següent get() retorni un objecte al qual li manquin actualitzacions.
Per assegurar la consistència, el que fa Dynamo tracte el resultat de cada actualització com una nova versió de les dades, i permet que en alguns moments existeixin diverses versions d'un mateix objecte en el mateix moment. Lògicament en la majoria de vegades les versions més actuals substitueixen a les més velles, de totes maneres de vegades apareixen "branques", resultant en versions amb conflictes entre elles. En aquests casos el client és encarregat de fer la "reconciliació" d'aquestes branques per convertir-les de nou en una sola. Per detectar els conflictes i perquè s'han produït Dynamo utilitza rellotges vectorials.
Els vectors clocks és un sistema que va ser inventat per
Leslie Lamport. Són molt utilitzats en informàtica distribuïda i tenen molta tela. Aviat hi haurà tot un article que parli de vectors clocks, ara mateix deixem-ho estar en que serveixen per detectar col·lisions temporals com la que acabem de veure.
Execució de les operacions de lectura i escriptura
Les operacions de lectura i escriptura són invocades a través de l'API de Dynamo, mitjançant HTTP, els clients poden triar dues maneres:
- Dirigir la petició a través d'un balancejador de càrrega que triarà un node basant-se en l'informació de càrrega.
- Utilitzar una llibreria específica per redirigir la petició directament al node coordinador de la clau.
Com hem vist anteriorment cada clau ha de ésser rebuda pel seu node coordinador, en el segon cas, el node que rep la petició és sempre el coordinador, en el primer cas però, la petició pot anar a parar a qualsevol node, el que fa llavors aquest node és enrutar-la cap al node que toca, que serà el coordinador de la clau.
Tractament de fallades
En el cas de Dynamo utilitzés un sistema de quòrum típic faria que el sistema no estigués disponible en casos en que algun o alguns nodes tinguessin problemes, per tant el sistema utilitzat per Dynamo no força un quòrum complert, sinó que utilitza un quòrum relaxat. Per tant, no tots els nodes que formen part de la rèplica han d'estar disponibles a l'hora de fer una actualització, cosa que implica que l'operació serà més ràpida, però cosa que implica que poden donar-se inconsistències al sistema, i és per això que tenim els vector clocks per arreglar-les.
Detecció de membres
Tots els nodes saben l'estat i la llista de nodes que hi ha al sistema formant part de l'anella. Per propagar els canvis també s'utilitza un protocol de gossip. Per tant, sempre cada node sabrà qui és el node coordinador de qualsevol clau.
Lògicament les deteccions de fallades són relativament senzilles, si un node intentat contactar amb un altre node (ja sigui per demanar que faci de coordinador o bé per replicar alguna dada) i aquest no contesta, ràpidament el node s'encarrega de fer saber a la resta que aquell node no està disponible i que cal reaccionar rebalancejant les dades.
Afegint i traient nodes
Quan un nou node apareix al sistema, se li assigna un número de tokens que estan aleatòriament repartits dins de l'anella. Fins llavors altres nodes estaven encarregades de mantenir aquelles dades, per tant el node nou contacta amb aquestes màquines, els fa saber que ha aparegut i demana que l'hi enviïn les claus emmagatzemades més les dades.
Implementació
Amazon ha implementat Dynamo amb Java, i cada node pot emmagatzemar les dades mitjançant un connector a bases de dades. Per tant, cada node té a sota una base de dades per guardar les dades a disc, depenent del tipus de dades s'utilitza un producte o un altre.
