Distribuïnt...

SOAP fail

noreply@blogger.com (Marc) — Sun, 08 Nov 2009 12:17:00 +0000

Estic veient una tendència a la xarxa?

"XML-RPC, SOAP, and other XML based protocols are hardly even worth mentioning. They are unnecessarily verbose and complex. XML is not convertible to a simple unambiguous data structure in any language I’ve ever used. I’ve wasted too many hours of my life clumsily extracting data from XML files to feel anything but animosity towards the format."

Un altre, blog que es lamenta dels SOAP's.

Del paper sobre Thrift (by Facebook): Thrift és un RPC que han fet els de Facebook per ús intern, al paper on n'expliquen les bases fan una comparació amb altres frameworks i dónen els motius pels quals no els han utilitzat, en cas de SOAP, simplement:

"SOAP. XML-based. Designed for web services via HTTP, excessive XML parsing overhead."

Estic convençut d'haver llegit més històries recentment, però vaig ser massa mandrós per anar-les apuntant.

En definitiva. No utilitzeu SOAP Web Services. Algun dia explicaré perquè els hi tinc tanta mania.

Spring killed the Java star.

noreply@blogger.com (Marc) — Thu, 29 Oct 2009 22:09:00 +0000

Un títol suggerent no ?

Els que em coneixen sabran que mai he sigut un fan ni de Spring ni d'altres frameworks ni convencions de programació. No sé, sempre he sigut de la vella escola.

Anem en compte. Són uns grans frameworks i realment ajuden en el desenvolupament, sobretot d'aplicacions d'un nivell avançat i complicat. I tot i que els utilitzo poc, els utilitzo.

Actualment a last.fm estem buscant gent, tenim dues posicions obertes:

Enginyer de Dades: Necessitem un enginyer que es manegui bé treballant amb moltes dades (Terabytes) i Java.
Enginyer de Catàleg: Hauria de tenir un nivell avançat de Java + SQL + Postgres.

Que ho sapigueu.

Bé, estem fent entrevistes de feina i tenim alguns problemes. Bàsicament tenim moltes aplicacions de gent que sap Hibernate, però no domina SQL i sap Spring, però no domina Java. Fatal.

Per què? doncs per els següents motius:

Bases de dades: Hibernate es una solució meravellosa. Un cop tens tota la història configurada et permet accedir a la base de dades de forma còmoda, sense històries i sense SQL. Meravellós oi? doncs sí. Ara bé! què passa quan hi ha una urgència i s'han de fer queries complicades a la base de dades des d'un terminal per ssh. Ja l'hem liada. Doncs no pot ser.
Java: Aquest tema és més general. Molta gent que sap Spring té clares com fer les coses, però moltes vegades no sap perquè es fan d'aquesta manera. Si t'estàs enfrontant amb un projecte clàssic, com és tenir una base de dades amb un nivell de domini ben definit, un nivell amb els controladors i el nivell de vistes el que t'importa és fer les coses el més bé i el més còmodament possible, en aquest cas Spring (o qualsevol altre framework) és una solució idònia. Quan estàs en una situació estranya què s'ha de fer? doncs tirar de l'API de Java. I si és una situació estranya cal dominar-la.

El cas de last.fm és bastant peculiar. El meu equip treballa amb moltes quantitats de dades, és per això que entre d'altres eines utilitzem Hadoop. Però no sempre es soluciona tot amb Map Reduce.

Amb un volum d'entrada de dades normals, l'elecció entre un HashMap o un TreeMap (lògicament per alguna tasca auxiliar i no guardar les dades!) pot sembla anecdòtica. La diferència serà de microsegons. Ara bé, si l'entrada és de Terabytes de dades la diferència pot arribar a ser d'hores en quan a velocitat, apart de que podem rebentar el límit de memòria de la màquina virtual. Per tant, en el nostre cas, són coses que s'han de saber.

Lògicament són coses que s'aprenen amb experiència, però estic veient que aquests tipus de coneixements, els coneixements sobre com funciona un llenguatge o un compilador a fons manquen cada vegada més i més. Aquest tipus de frameworks estan apartant coneixements bàsics d'informàtica que sempre s'haurien de tenir en compte.

Bé, això són tant sols unes reflexions personals. Cal saber de tot i aquests frameworks són importants, ara bé, com tot, s'ha de saber quan s'han d'utilitzar i quan no.

Technical documentation guidelines.

noreply@blogger.com (Marc) — Wed, 29 Jul 2009 23:43:00 +0000

After some years of working as a developer I've realized the lack of standard guidelines when it comes to writing technical documentation. Not user manuals. Technical documentation, the one you should write when you develop a system, or the one you should get when you start maintaining a system somebody developed.

So, no standard guidelines around ? (at least that i liked), no problem, open source, open world. I made my own.

I started researching, getting technical documentations from different projects, getting the opinions from lots of good professional developers and using lots of common sense (my common sense, well, and sometimes other people's common sense) and this is what i came to:

Ok, I tried, I promise, I tried. I cannot format the document in Blogspot. I've created a static html page. You can find the article: HERE

Hive

noreply@blogger.com (Marc) — Sat, 11 Jul 2009 19:52:00 +0000

Aquest post parlo de Hive, una eina que han fet a Facebook que converteix un llenguatge d'accés a dades semblant SQL a treballs map-reduce per fer consultes als directoris guardats en el DFS de Hadoop.

Un dels problemes que tenim els usuaris de Hadoop és que estem treballant amb uns volums de dades considerables. En cas contrari seria millor utilitzar Python o Erlang o una base de dades relacional (insisteixo una vegada més, Hadoop si i només si s'ha de treballar amb moltes dades). Com ja he explicat en altres posts un dels sub-projectes de Hadoop és el sistema de fitxers, fet a inspiració del Google File System (GFS). És un sistema redundant i distribuït, per tant cada fitxer està fragmentat per la xarxa i n'hi ha diverses còpies. Això implica que sigui molt difícil perdre un fitxer (ja que n'hi ha 3 còpies diferents), però al mateix moment es fa més complicat poder accedir a aquest fitxer, ja que qualsevol manipulació que se li vulgui aplicar (sense un treball map/reduce de Hadoop) força que s'hagi de baixar del clúster, i aquests fitxers poden arribar a ser molt grans (molt molt grans).

Això a efectes pràctics significa que no es pot fer de forma senzilla un 'grep' per buscar continguts. El fitxer està repartit pel clúster per tant, s'ha de fer un treball map-reduce per fer el grep. El codi de hadoop ja porta implementada aquesta utilitat, però igualment és incòmode i poc potent.

En principi no hauria de ser un problema, ja que normalment interessa processar una entrada i un cop tenim la sortida a punt la baixem tota del clúster per servir-la a la pàgina web, per inserir-la a la base de dades o el que sigui. El problema ve quan necessites saber (urgentment) una certa línia d'un fitxer de 200 Gb que està fragmentat dins el clúster.

Potser això és una mica difícil d'entendre, un exemple:

Com sabeu fa poc es va morir Michael Jackson, doncs bé, quan la noticia es va escampar la gent va començar a escoltar la seva música. A last.fm vam començar a rebre scrobbles de Michael Jackson, aquests scrobbles, que basicament hi ha l'identificador d'usuari i la cançó que aquest ha escoltat es guarden al sistema de fitxers distribuït per a ser processats per Hadoop. No ens volíem esperar a que fos al vespre per saber quanta gent de més havia escoltat al difunt rei del pop. La solució era fer un programa (en Java o bé en Dumbo) per agafar aquestes dades i fer un grep per veure quants usuaris era, una cosa que utilitzant bash senzillament seria:


bash $> grep michaeljackonid fitxer_scrobbles | sort -k columna_usuari -u | wc -l

és en Java molt més pesat i complicat d'escriure.

Els de l'equip de dades ja havíem tingut diverses peticions d'aquestes anteriorment, i ja tenim una sèrie de programes (mal fets, a base de copy and paste, ràpids) per fer consultes. El principal problema és que d'aquesta manera s'acaba tinguent una bateria d'scripts de consulta que són impossibles de reutilitzar, totalment específics i que serveixen tant sols una vegada.

Però aquesta vegada va ser diferent, perquè des de feia uns dies estàvem jugant amb Hive!

Segons la seva pàgina, Hive és una infraestructura de 'warehouse' (magatzem de dades) que corre sobre Hadoop i permet la consulta de dades. Per tant, és en certa manera. Una infraestructura per córrer SQL sobre directoris de DFS.

Convé tenir en consideració els següent punt, molt important:

Hive no és una base de dades.

El que fa Hive és tenir en uns fitxers propis del DFS de Hadoop una sèrie de dades que en certa manera descriuen les estructures de directoris dels directoris normals del DFS. Un cop tenim això, la línia de comandaments de Hive permet fer consultes amb SQL. S'ha elegit aquest llenguatge de consulta perquè (desgraciadament?) és el que sap tothom i realment no fa falta crear-ne cap altre.

Aquesta consulta SQL és convertida per Hive en diversos passos, com podem veure en el document d'arquitectura en una sèrie de tasques Map Reduce que corren de forma normal al clúster.

Aquestes tasques senzillament agrupen les dades i les filtren tal com hem dit a la consulta, i en cas que sigui necessari les ordenen (order by), treuen duplicats (distinct)...

Per tant, amb Hive podem córrer una consulta sobre totes les dades del sistema de fitxers distribuït, de forma senzilla i sense haver de carregar totes les dades en una base de dades relacional.

A mi personalment, m'estalviarà moltes hores, ah, i per cert, l'augment d'oients de Michael Jackson el podeu trobar aquí.

Nosql

noreply@blogger.com (Marc) — Tue, 16 Jun 2009 22:27:00 +0000

Tot just la setmana passada es va celebrar la primera trobada Nosql a San Francisco, sobre bases de dades distribuïdes i no relacionals. Coincidint amb el Hadoop Summit 2009.

Bàsicament va ser una trobada dels principals desenvolupador / usuaris de bases de dades no relacionals (basades en Google BigTable i Amazon Dynamo), on cada desenvolupador va explicar les característiques del seu sistema.

Aquí us deixo un link del blog de'n Johan Oskarsson que hi va assistir amb els links a totes les transparències utilitzades així com els videos. Espero que us sigui de servei!

Hadoop, the definitive guide.

noreply@blogger.com (Marc) — Mon, 15 Jun 2009 17:17:00 +0000

S'acaba de publicar a O'Reilly 'Hadoop, the Definitive Guide'. Un llibre sobre Hadoop (lògicament) que ha escrit Tom White i en el qual he contribuït en un capítol d'experiències.

pd.- Lògicament sóc el culpable de la imatge de la pàgina 413.

Dynamo

noreply@blogger.com (Marc) — Sun, 17 May 2009 16:50:00 +0000

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.

Bigtable

noreply@blogger.com (Marc) — Fri, 08 May 2009 06:25:00 +0000

Bé, avui toca parlar del primer article de la sèrie de noves bases de dades. BigTable, de Google.

El que trobareu aquí és un resum de l'article Bigtable: A distributed storage system for structured data que va aparèixer a la conferència OSDI al 2006.

Primerament, BigTable és el nom del producte que van programar internament a google, és bàsicament un sistema d'emmagatzemament distribuït per guardar dades estructurades i està pensat perquè sigui molt escalable. A més, un detall important, és que els enginyers de google el van dissenyar per còrrer en moltes màquines genèriques, no calen grans servidors ni discs durs especials, simplement, màquines com les que podem tenir ara mateix al davant. Google utilitza aquest servei per guardar moltes de les seves dades, per exemple índexs web, o imatges de Google Earth, per tant, no és una idea, és una implementació existent i està en producció<

Com ja havia introduït en el post anterior, Bigtable no utilitza ni dona suport a un model de dades relacional, al contrari, facilita un model de dades molt senzill que permet un control dinàmic sobre l'estructura dels continguts i del seu format. Les dades són indexades mitjançant columnes i files, els noms de les quals són cadenes de texte, els continguts d'aquestes són cadenes de texte també, per tant, la base de dades no sap (ni li interessa) el format dels continguts, això és problema de l'aplicació.

Model de Dades

Atenció amb la definició: Bigtable és un mapa ordenat, multidimensional, distribuït, persistent i dispers (aplaudiments i furor general!). Aquest mapa està indexat per:

Clau de la fila
Clau de la columna
Instant de temps (!)

Per tant té aquest format:


(row:string, column:string, time:int64) --> string

Anem a explicar una mica cada factor d'indexació:

Fila

Les clau de cada fila són strings, de fins a 64Kb, cada lectura i escriptura a una fila es considera atòmica. Un detall important és que per a cada taula es particiona dinàmicament el número de files que té una tablet, que és la unitat de distribució i balancejament de dades de Bigtable (més explicació sobre això una mica més endavant).

Familia de Columnes

Les claus de les columnes estan agrupades en families de columnes, que són els elements més bàsics d'accés a control a la taula. Aquestes no haurien de canviar de forma dinàmica, per tant, una taula té un número fixe de families de columnes durant l'execució, ara bé, dins de cada familia de columnes hi pot haver un número indeterminat de columnes, que poden aparèixer i desaparèixer en temps d'execució. Per tant, una familia de columnes de Bigtable equival a una columna d'una base de dades de model relacional, i a més aquesta columna podria tenir columnes a dins, i a més dinàmiques!

Instant de temps

La idea és ben senzilla, es tracta que una taula tingui un històric dels valors que hi havia en les columnes/files. Lògicament això és un valor configurable i a més, Bigtable té un garbage collector, semblant al Java que va netejant valors a mesura que es fan més vells del que ens interessa.

API

Una altre gran diferència entre les bases de dades relacionals i Bigtable és que mentres que les RDB interactuen amb l'exterior mitjançant SQL, Bigtable ho fa mitjançant una API, per tant, en aquest punt s'aproxima més al Hashmap distribuït. Apart d'això, els usuaris poden crear scripts amb un llenguatge de query de google anomenat Sawzall per fer consultes més complexes.

Parts de l'arquitectura de Bigtable

Hem de tenir en compte que els enginyers de google no van crear Bigtable del res, es van basar i lògicament van utilitzar coses que ja estaven fetes dins de Google:

Google File System, un sistema de fitxers distribuït.
Google SSTable, un format de fitxers binari. Bàsicament és una taula de hash de clau->valor ordenats.
Chubby, un servei de locks distribuit i persistent. Bàsicament es tracta d'un servei que és capaç de mantenir semàfors i altres tipus de locks de concurrència de forma distribuïda.

Casi res :D, mare meva que animals que són aquests de can google...

Implementació de Bigtable

Ja aviso que a partir d'aquí la cosa es complica una mica, si no us interessa la implementació d'aquest petit monstre us recomano que passeu directament a Coses que han aprés a can Google. De totes maneres, l'article no és molt detallat en quant a l'implementació, ja que és una implementació propietària i tancada i jo bàsicament n'he fet un resum per destacar-ne els detalls més importants.

Per la resta de valents... Bigtable està format per 3 components:

Un llibreria que usa l'aplicació client.
Un servidor master
Molts servidors de tablets, que poden ser afegits o trets de forma dinàmica del cluster per suplir necessitats de càrrega.

El master és l'encarregat d'assignar les tablets als servidors de tablets, detectar canvis en les màquines (afegim o treiem servidors de tablets), fer el balanceig de càrrega, neteja de files (temes temporals) i finalment manegar els canvis d'esquema de la base de dades, com són la creació de taules i de families de columnes.

Cal tenir en compte que tot i tenir un servidor master, les dades dels clients no hi passen a través, per sino que es comuniquen directament amb els servidors de tablets per fer les escriptures/lectures, i important, no utilitzen el servidor master per localitzar les tablets!, per tant, a efectes pràctics el màster està bastant descarregat.

Localització de les tablets

Tema important, com s'ho fa un client per localitzar el tablet que té les files que l'interessen?, però abans d'això és important saber que aquesta informació està guardada en una estructura de dades de 3 nivells, semblant a un arbre B+, i el primer nivell de l'estructura està en un fitxer guardat a Chubby, per tant, el client el primer que fa és preguntar a Chubby a on és aquest fitxer,i amb un màxim de 3 salts tenim el tablet que té l'informació que necessitem.

Assignació de les tablets

Següent pregunta: a on són els tablets? i per què hi són?
Lògicament cada tablet està assignat només a un servidor de en cada moment, el servidor màster manté una llista dels servidors de tablets que estan actius a cada moment, els tablets que ténen assignats cadascun i també els tablets que no estan assignats a cap servidor (i que per tant estan guardats al GFS). Aquesta llista només canvia quan:

Una taula és creada.
Una taula és destruïda
Dos tablets s'han fet tant petits que el màster decideix ajuntar-los en un sol tablet.
Un tablet s'ha fet tant gran que el màster decideix partir-lo en dos.

Altres detalls interessants

El paper dóna bastants més detalls d'implementació, però realment això pretén ser una introducció al model de dades de Bigtable, per tant els he ignorat, ara bé vull destacar:

Grups de localitat: Els clients poden agrupar diversos grups de families en el que són els grups de localitat, cosa que permet garantir que estaran al mateix servidor de tablets.
Compressió: Lògicament es permet compressió a l'hora de guardar els valors. S'han triat un conjunt d'algorismes de compressió ràpids (comprimeixen a 100-200Mb/s i descomprimeixen a 400-1000Mb/s en una bona màquina) i també poden descomprimir el fitxer per parts, sense haver de descomprimir-lo tot, molt pràctic en cas de que volguem llegir només una part petita del fitxer.
Bloom Filters: No saps què són els bloom filters? (wikipedia) Per evitar fer molts d'accessos a disc Bigtable utilitza Bloom Filters per veure si un fitxer en format SSTable conté les dades per un clau/valor en concret.
Caching: les lectures estan en una cache per una lectura més ràpida.

Coses que han aprés a can Google

L'article original té tot un apartat de les lliçons apreses en l'implementació, evaluació i ús de Bigtable internament a google, voldria destacar les dues següents:

La majoria d'aplicacions només necessiten transaccions d'una sola columna.
És important mantenir un, atenció aquí: DISSENY SENZILL, perquè més endavant sigui senzill de modificar, segons les necessitats reals, que normalment són diferents a les inicials.

I això és bàsicament un resum del que és Bigtable. És recomanable llegir el paper original, ja que dóna molts més detalls sobre implementació i decisions de disseny. Cal tenir en compte que és un paper bastant important i que ha sigut molt influent en les noves bases de dades que s'estan utilitzant i implementant actualment. Sobretot perquè va ser de les primers en trencar amb el model de dades relacional i es va posar en producció (i va funcionar)

Hadoop, la guia definitiva.

noreply@blogger.com (Marc) — Thu, 07 May 2009 14:06:00 +0000

Avui he rebut la noticia que està a punt de ser publicat, 'Hadoop, the definitive guide' un llibre que ha escrit Tom White i en el qual he pogut participar escriguent part d'un capítol d'experiències.

Podeu trobar més informació al següent post (anglés).

Nous models de bases de dades

noreply@blogger.com (Marc) — Mon, 27 Apr 2009 22:12:00 +0000

Aquest post és una introducció a una sèrie d'escrits que aniré fent relacionats amb els nous models de bases de dades que estan apareguent, i que estan tinguent una bona acceptació en diversos sectors del món empreserial relacionat amb informàtica (el perquè d'això mereix un post per si sól)

Primer de tot, aquests nous models s'allunyen bastant del model relacional de bases de dades al que suposo que tots estàvem més que acostumats. Sí, això vol dir tenir una base de dades sense SQL. Estrany oi?

El model relacional funciona molt bé per algunes aplicacions, però no és una solució universal que serveixi per tot. Fins fa poc era ben normal trobar aplicactius o arquitectures que tenien instal·lada una RDB tipus MySql o Postgres i que tant sols era utilitzada com a magatzem de dades. Amb això vull dir que no s'utilitzaven les propietats ACID d'una base de dades relacional, per tant, SELECTS senzills i UPDATES.

Fins aquí tot bé i cap problema, s'està infrautilitzant una eina molt potent, però no és res greu i si funciona doncs perfecte. Ara bé, pot ser que arribin els problemes en forma de:

Escalabilitat: La base de dades s'ha fet molt gran i la màquina, o bé la base de dades no pot suportar els continguts que ha de guardar o bé la càrrega de les diverses aplicacions que l'usten. Què cal fer? cal passar-se a una base de dades més potent o intentem repartir la càrrega de la base de dades entre altres màquines?
Disponibilitat: Què passa si la màquina de té la base de dades no està disponible? es queda tot aturat? És fàcil fer backups i restaurar-los en cas de que sigui necessari?. Serà un drama?

Qualsevol administrador de bases de dades sabrà que els dos punts anteriors són importants i els dos són, lògicament, solucionables utilitzant qualsevol motor de base de dades decent, fins a cert punt.

Ara bé, si tenim en compte empreses del nivell de Google, Amazon, Linkedin, Yahoo... que maneguen cada dia unes quantitats de dades MOLT grans hem de pensar que les seves bases de dades han de ser inmenses i lògicament els seus administradors han hagut de tenir en compte els dos problemes anteriors. Com s'ho han fet? doncs bàsicament han abandonat el model de bases de dades relacionals (i les seves implementacions) i han passat a uns models nous, fets a mida (lògicament només pels usos que no requerien una base de dades relacionals!).

Hem de tenir en compte que aquestes empreses tenen molts de recursos i que també ténen unes necessitats bastant específiques, probablement per moltes de les seves aplicacions el model relacional els ajudi ben poc. En molts casos el que necessiten és tant sols "una taula de hash monstruosament gran i monstruosament ràpida". Aquest concepte, conegut com DHT (Distributed Hash Table) no és nou, en l'àmbit de recerca ja és ben conegut i fins i tot hi ha diverses implementacions disponibles, cadascuna enfocada a solucionar problemes lleugerament diferents:

Aquests projectes són els que van posar les bases del que després acabaria apareguent. Si aneu a les pàgines d'aquests projectes veureu que tot i que ténen implementacions estables no són utilitzades en entorns de producció empresarial (que jo sàpiga o hagi sapigut trobar, si estic equivocat sisplau feu-m'ho saber). Una part molt interessant d'aquests projectes és l'apartat d'articles, on s'expliquen les diverses decisions de disseny, diferents problemes que s'ha hagut de solucionar així com diferents algorismes molt importants en el món de la informàtica distribuïda i sobre els quals tinc pensat fer algun post properament.

Les DHT no són trivials ni de dissenyar ni d'implementar, el seu concepte és senzill, una taula de hash distribuïda, però no ens hem de deixar enganyar. Ténen molta tela.

Google i Amazon es van posar en marxa i cadascuna va implementar-se la seva pròpia base de dades especificament pels seus usos, un cop les van tenir implementades, provades i en producció van publicar cadascuna un article, que en certa manera són els articles que van començar amb la "moda" de les noves bases de dades:

De part de Google. Bigtable: A Distributed Storage System for Structured Data.
De part d'Amazon. Dynamo: Amazon's Highly Available Key-value Store.

A partir de llavors han aparegut moltes bases de dades basades en aquests papers, gens sorprenentment algunes basant-se amb el model Bigtable i d'altres que més que bases de dades s'anomenen Key-Value Stores i que, lògicament, es basen en Dynamo.

Els articles són realment molt interessants i de lectura obligada per qualsevol persona interessada en escalabilitat, bases de dades i noves tecnologies.

En el pròxim post resumiré el paper de la Bigtable de google, i en el següent la Dynamo d'Amazon, per veure'n bé les diferències, tant de disseny com d'ús pràctic. I més endavant, i depenent del meu temps descriuré les meves experiències reals amb diverses implementacions, de moment tinc pensades:

CouchDB, de la qual ja n'he parlat en aquest blog.
Voldemort, que és la Key-Value Store que han implementat a LinkedIn.

Volunteer Computing i BOINC

noreply@blogger.com (Marc) — Mon, 06 Apr 2009 23:07:00 +0000

Aquest post va del Volunteer Computing, amb la seva implementació més famosa, BOINC.

El Volunteer Computing ve d'una idea bastant senzilla. Molta gent té ordinadors, i molta d'aquesta gent no els hi treu tot el suc que podria, per tant, estaria molt bé aprofitar tota aquesta potència restant oi ? doncs es tracta d'això.

BOINC és un software molt senzill que s'instal·la en un ordinador, hi ha versions per Windows, GNU/Linux, BSD's, etc. Un cop el software està instal·lat l'usuari s'autentifica i s'apunta a un o diversos projectes. Ja està.

El que passa llavors és que aquest software contacta amb els servidors de BOINC i demana feina. Els servidors li enviaran uns "paquets" amb un o diversos treballs de computació, un cop rebuts aquests l'ordinador començarà a processar-los. Una vegada s'hagi calculat el resultat, aquest s'enviarà de nou als servidors i demanarà més treballs. Tot això de forma totalment transparent a l'usuari i sense que aquest ho noti.

Boinc prové de SETI@Home , un programa que bàsicament va crear aquest esquema per analitzar ones de ràdio provinents de l'espai per intentar trobar vida extra terrestre. Més tard va aparèixer Folding@Home un programa de caire més... biològic per processar plegaments de mol·lècules per l'investigació de malalties i fàrmacs. El problema és que cada projecte utilitzava el seu propi client, i a mesura que anaven sortint més projectes s'havia d'anar instal·lant els seus clients. Finalment es va decidir unificar el format i tenir un sol programa a on et podies apuntar a diferents projectes, així és com va nèixer BOINC.

Passos ràpids per habilitar una conta

La manera més fàcil d'entendre com funciona (en general) és veure-ho funcionant. El software es pot descarregar des de la pàgina de BOINC, o en cas de Linux del gestor de paquets.

El següent cas és triar els projectes en els quals volem participar. N'hi ha molts, aquí podeu trobar-ne una llista, n'hi ha per tots els gustos; problemes matemàtics, de salut, de recerca de vida alienígena...

Per cada projecte al que volem participar ens hi n'hem de donar d'alta a la seva pàgina, llavors ens donaran un nom d'usuari i una clau d'identificació que haurem d'introduir al programa (BOINC). De totes maneres, per fer-nos la vida més senzilla hi ha "paquets" o managers. Aquests són projectes com el World Community Grid, que és una iniciativa d'IBM que agrupa els projectes de BOINC que ténen a veure amb investigació mèdica i mediambiental. Si ens donem d'alta al WCG ens donem d'alta amb un sol identificador a una sèrie de projectes de BOINC, per tant és una forma bastant agradable de simplificar.

Per tant si algú li fa gràcia i vol provar-ho el més senzill és:

Baixar-se el BOINC i instal·lar-lo.

Donar-se d'alta al WCG

Entrar l'identificador del WCG + la clau al BOINC.

Un cop a dins pots entrar a formar part d'equips. Es tracta de fer una competició sana de veure quin equip aconsegueix processar més paquets. Jo formo part de l'equip 'Catalunya', per tant, si voleu contribuir hi sereu molt benvinguts ;)

Com funciona

Cal tenir clares les diferències entre Volunteer Computing i altres tipus de supercomputació o computació distrbuïda, com el Grid Computing. El poder del primer es basa en tenir moltes màquines, de diverses categories de forma totalment descontrolada. Aquestes màquines no són teves, no tens el control sobre elles, no saps ni et pots fiar de que l'endemà continuaran funcionant o que estaran connectades a Internet, cosa que com més endavant veurem comporta unes particularitats en el disseny del sistema.

Bàsicament un projecte de Boinc funciona independentment de qualsevol altre. Cada projecte té el seu servidor, i cada servidor està format per una sèrie de programes, els quals funcionen tinguent com a nucli una base de dades relacional. Aquests subprogrames s'encarreguen de:

Servidor de Fitxers. Cada servidor té una sèrie de fitxers que són les feines que ha de fer cada màquina. Lògicament aquests fitxers estan guardats en el servidor i són enviats quan toca a cada màquina que ha de processar-lo. Un cop el paquet s'ha processat és enviat de nou cap al servidor. El servidor, a més d'emmagatzemament té diverses funcions addicionals:

Comprovació d'integritat: Quan es rep un resultat és necessari comprobar que el fitxer no sigui corrupte, per causa malintencionada o bé per error de transferència.

Comprovació de correcció: En parlaré en pocs paràgrafs però cada tasca es processa més d'una vegada en més d'una màquina. Així doncs es rep el mateix resultat (o el que hauria de ser exactament el mateix resultat) en diverses ocasions. Per tant, si hem enviat una feina a processar a 5 màquines diferents hauriem de rebre 5 vegades el mateix resultat. En cas de que rebem resultats diferents cal descartar aquest resultat i tornar a calcular-lo.

Organitzador (normalment s'utilitza el nom anglés, scheduler) Aquesta és el procés que decideix quina feina s'envia a quina màquina. Per tant, aquest és el procés que decideix quantes vegades rebrem un resultat. Aquesta redundància es per diversos motius:

Seguretat: Podria ser que per qualsevol motiu un usuari volgués boicotejar un projecte (coses més estranyes s'han vist) i que per tant intentés enviar resultats incorrectes. Cal sempre comparar el resultat amb diverses màquines, mai ens en podem fiar d'una sola.

Evitar colls de botella. És un punt molt relacionat amb l'anterior, pot ser que tinguem dependències entre tasques, i que per tant tinguessim una tasca molt important i sense el resultat d'aquesta no poguéssim continuar. El que no es pot fer en un entorn com aquest (Volunteer Computing) és fiar-nos de que una màquina enviarà el resultat del paquet que hem enviat. No controlem aquella màquina, i per tant, no ens podem fiar. És per això que sempre enviem el paquet més vegades de les que és necessari, i com més important és la tasca, més vegades l'enviem.

Programar la teva pròpia apliació

Una de les gràcies de Boinc és que pots programar la teva pròpia aplicació perquè corri en diverses màquines alhora, ja siguin dins la pròpia empresa o fins i tot en una xarxa més casolana. En principi no és senzill, ja que estem parlant d'una aplicació que ha de ser paral·lelitzable i que pugui còrrer en diverses plataformes, ja siguin Microsoft Windows, Mac o bé GNU/Linux.

La pàgina de Boinc posa a l'avast de qualsevol persona que ho vulgui fer una sèrie d'ajudes i tutorials per configurar l'entorn de desenvolupament així com programes d'ajuda.

No tinc experiència personal amb això, però realment m'agradaria sentir noticies d'algú que ho hagi intentat.

Diversos Usos

Lògicament tota aquesta tecnologia es pot aplicar en altres camps, a la mateixa pàgina de BOINC ens dónen unes petites explicacions de com configurar una xarxa de màquines amb BOINC pels nostres propis projectes. En cas de tenir una empresa amb moltes màquines potser no cal invertir grans sumes en servidors d'aplicacions o bé d'utilitzar serveis externs com els Amazon WS, ja que ens podem muntar el nostre "super computador virtual" amb BOINC:

Per empreses.

Per Campus Universitaris.

Per tant crec que puc concloure dient que el BOINC és informàtica distribuïda popular!, va vinga no sigueu garrepes, feu-vos una compta i a cremar cicles de CPU!!

Hadoop

noreply@blogger.com (Marc) — Wed, 25 Mar 2009 23:42:00 +0000

Els que estigueu posats en el món de l'informàtica distribuïda o bé d'alt rendiment o bé, simplement que esteu una mica a l'aguait de les novetats informàtiques potser us sonarà Hadoop.

Hadoop és una plataforma de software que bàsicament permet escriure programes que processin unes grans quantitats de dades. Grans grans. El projecte ja té diversos anys i alguns dels seus components s'han separat en subprojectes:

Hadoop Core: Plataforma de Map Reduce + Sistema de fitxers distribuit.
HBase: Una base de dades distribuïda i escalable.
Pig: Nivell d'alt llenguatge per aplicacions que utilitzen Hadoop-core.
ZooKeeper: Sistema de coordinació per Hadoop.
Hive: Una espècie de SQL fer queries a les dades emmagatzemades en Hadoop (moltes dades, moltes moltes)

És un projecte Open Source utilitzat en producció (molt important) en diverses empreses, tal com podeu veure aquí. A més, té una comunitat d'usuaris / desenvolupadors molt activa tal com podreu veure si doneu un tomb pel seu tracker

En aquest post parlaré exclusivament del projecte principal, Hadoop Core.

Les característiques que ells destaquen en la seva pàgina són les següents:

Escalabilitat: Pot manejar grans quantitats de dades (petabytes) i té escalabilitat horitzontal, és a dir, si necessites més potència o més espai, simplement afegeixes màquines.
Econòmic: És Open Source (llicència Apache) i treballa amb qualsevol tipus de màquines, no és necessari que siguin servidors d'alta gamma. A més, és una plataforma de software que suposa que els errors de hardware són usuals i per tant, sap reaccionar. També cal destacar que està preparat per còrrer al Amazon EC2
Segur: Sempre es mantenen diverses còpies de les dades repartides en diverses màquines, així ens estalviem desgràcies quan una màquina decideix morir sense avisar.

Hadoop és capaç de processar grans quantitats de dades perquè utilitza Map Reduce. Map Reduce és un model de programació pensat, o més bé, readaptat, per procés de moltes dades. Amb això voldria aclarar que de fet, només serveix per això. Sembla ser que hi ha certa moda en utilitzar Map Reduce en alguna de les seves implementacions per moltes coses. Si no es té una entrada de com a mínim gigues de dades probablement no sigui el que es necessita.

Bé, els causants de tota aquesta febre MR (Map Reduce) van ser Google quan van publicar un article on explicaven què era, com es programava i com ho utilitzaven en producció a diari en els seus clústers. A partir d'aquí van començar a aparèixer implementacions d'aquest model de programació en diversos llenguatges, una de les més importants, si no és la que més és sens dubte Hadoop.

En resum, MR i per tant Hadoop treballen de la següent manera (molt per sobre):

Tenim les dades al sistema de fitxers distribuit que comparteixen totes les màquines que conformen el nostre clúster. Tenim un programa que implementa MR mitjançant Hadoop, això bàsicament vol dir que hem programat un programa semblant a aquesta, el qual té una classe Mapper, amb un mètode map i una classe Reducer amb un mètode reduce.

Hadoop parteix el clúster en mappers i reducers, una màquina pot ser mapper i reducer a l'hora, això es pot definir en la configuració del sistema. Les màquines que fan de mappers agafen les dades del sistema de fitxers distribuit i li apliquen la funció map. Així de bon principi ja tenim tot de màquines que estan llegint les dades d'entrada de forma paral·lela.

MR té uns requeriments per les dades. Bàsicament han d'esser de la forma. Clau -> Valor, on la clau i el valor poden ser qualsevol cosa. Per tant, un cas típic seria un log d'apache:


127.0.0.1 - - [31/Jul/2008:00:37:04 +0100] "GET /~marc/images/imatge1.jpg HTTP/1.1" 200 16624
127.0.0.2 - - [31/Jul/2008:00:37:05 +0100] "GET /~marc/images/imatge2.jpg HTTP/1.1" 200 16624
127.0.0.3 - - [31/Jul/2008:00:37:06 +0100] "GET /~marc/images/imatge3.jpg HTTP/1.1" 200 16624
127.0.0.1 - - [31/Jul/2008:00:37:04 +0100] "GET /~marc/images/imatge3.jpg HTTP/1.1" 200 16624

Per exemple en aquest programa ens interessa saber quines IPs han agafat quines imatges. Per tant podriem dir-li al mapper que la clau de sortida sigui la imatge, i que el valor de la clau sigui la IP:


Clau   Valor
imatge1.jpg  127.0.0.1 
imatge2.jpg 127.0.0.2 
imatge3.jpg 127.0.0.3 
imatge3.jpg 127.0.0.1

Ok, per cada Clau/Valor que el mapa troba l'envia a un reducer. És important notar que no associa res de res, en aquest cas enviarà una clau/valor per cada linia de fitxer. Aquesta és una part molt interessant ja que el mètode map simplement invoca una funció amb la clau i el valor com a paràmetres i se n'oblida. Aquests valors són emmagatzemats "màgicament" al sistema de fitxers distribuit de forma totalment transparent fins que tots els mappers han acabat. Això vol dir que els reducers no comencen a processar les dades fins que els mappers estiguin (en veritat si que comencen en certa manera, però no és important ara). Hadoop té un particionador de manera que, atenció que això és important, cada reducer (cada instància d'un reducer) rep una i només una clau amb una llista dels valors: Això és una mica espinós per entendre, exemple:


Clau 1 / Valor A
 Clau 2 / Valor B
 Clau 3 / Valor A
 Clau 2 / Valor A
 Clau 3 / Valor C

I el reducer rebrà:


Reducer1 : Clau 1 amb una llista que contindrà: Valor A
Reducer2 : Clau 2 amb una llista que contindrà: Valor B, Valor A
Reducer3 : Clau 3 amb una llista que contindrà: Valor A, Valor C

Per tant hi haurà tants reducers com claus tingui la sortida el mapper. En l'exemple anterior es tradueix a:


imatge1.jpg 127.0.0.1
imatge2.jpg 127.0.0.2
imatge3.jpg 127.0.0.3, 127.0.0.1

Llavors lògicament el reducer pot fer el que vulgui amb aquestes dades. L'exemple aquest és extremadament senzill, però pensem que un map i un reduce complex poden fer les mil i una bestieses i si estem parlant d'un fitxer de log complert d'apache d'alguna pàgina important pot ser molt i molt gros.

Un cop el reduce està també escriu els resultats en forma clau valor. Aquests resultats són guardats al sistema de fitxers distribuit.

Podeu trobar molta més informació sobre Map/Reduce + Hadoop al tutorial de hadoop.

Bé, en pròxims articles entraré més en detalls sobre Hadoop i probablement publicaré snippets de codi, amb problemes que em vaig trobant al dia a dia i alguns números.

CouchDB i Key-Value Stores.

noreply@blogger.com (Marc) — Fri, 20 Mar 2009 21:53:00 +0000

Avui he estat a una presentació de Jan Lehnard sobre CouchDB. Podeu trobar les slides aquí.

CouchDB és una key-value store, i aquest és justament el primer post sobre aquest tema. En vindran molts més ja que és un tema molt extens i molt interessant, si més no per mi. Bàsicament podriem dir que una key-value store és una base de dades molt senzilla distribuïda per la xarxa, també hi ha qui ho enten com una taula de hash gegantina distribuïda en diversos ordinadors. I molt més pensada per a l'eficiència dels gets/sets que a per la complexitat que poden tenir altres bases de dades com Postgres o Mysql.

Una de les coses que m'ha fet pensar més de la xerrada és la quantitat de key-value stores que hi ha actualment. La majoria són bastant noves i tot i que totes serveixen pel mateix, emmagatzemar i obtenir certs valors, els seus dissenys són totalment diferents i fan que cadascuna tingui la seva sortida de mercat.

Aquí podeu trobar un post molt complert i interessant sobre key-value que va fer l'RJ (CTO de last.fm)

Unes pinzellades per a qui li faci mandra llegir-se tot l'article o li faci cosa perquè està en anglés:

Les principals diferències de disseny de les key-value stores que convé mirar abans d'adoptar-ne una, o bé que s'han de tenir en compte són:

Tolerància a fallades: Les key-value stores normalment estan en màquines dedicades, i més d'una màquina, per tant diem que tenim 5 màquines servint l'informació. Què passa si una de les màquines s'espatlla de cop?. Depenent de la tolerància a fallades de la key-value store pot ser que no passi res, o que tinguem un problema gros. Entre els tipus de tolerància a fallades que són més normals destacaria:
- Replicació: Tant senzill com tenir més d'una còpia de cada valor que es serveix. Si cau una màquina no passa res perquè hi haurà alguna altre màquina que també té aquest valor. Lògicament gastem més espai del necessari, però és el preu a pagar.
- Particionat: No és una tècnica en si sola, sino que és una millora del mètode anterior, si els valors són grans (fitxers, mp3, imatges) podem partir el fitxer en diversos trossos i repartir-los (amb redundància o replicació) per diverses màquines.
Persistència: Normalment aquests mecanismes tenen totes les dades a memòria RAM. Amb això ens estalviem tot el temps d'I/O a disc. Lògicament fa que quedi poca RAM per altres coses, però és el preu de la velocitat. Ara bé, de nou, què passa si hem d'apagar la màquina?. N'hi ha que guarden els valors en una base de dades relacional, ja sigui Mysql, Berkeley, etc. Així, al engegar agafen tota la informació de la base de dades i la posen a memòria. Treballen en memòria i finalment, quan s'apaga la màquina es guarda de nou a la base de dades. N'hi ha d'altres que ho serialitzen utilitzant llibreries natives dels llenguatges de programació en que estan implementades i fins i tot n'hi ha que _no_ guarden res. Quan s'apaguen es perd tot!, normalment són utlitzades com a caches.

Accés: Molt bé, tenim molta informació, però com hi accedim?. N'hi ha que porten les seves pròpies llibreries en diversos llenguatges, n'hi ha que utilitzen HTTP (sempre REST, mai SOAP) i n'hi ha d'altres que ofereixen interficies de thrift o protocol buffers (hi haurà tot un post sobre aquests dos, no patiu, són mecanismes de serialització / RPC, el primer fet a facebook i el segon fet a google).

Eficiència: Lògicament, s'ha de parlar d'eficiència. Tant en temps d'accés a les dades (quan tardes en fer un GET, quan tardes en fer un PUT?) com en l'eficiència d'ús de recursos que utilitzen les màquines per servir l'informació.

En pròxims posts entraré una mica més en detall en implementacions concretes i en les key-values stores que considero més interessants.

Bittorrent

noreply@blogger.com (Marc) — Wed, 04 Mar 2009 21:22:00 +0000

Començo el nou blog amb un post sobre protocols, avui Bittorrent!

Suposo que tothom, més o menys coneix el Bittorrent, aquest "programa per descarregar pel·lícules". Doncs bé, bittorrent és el nom del protocol, també de l'empresa que el va fer i d'un programa que utilitza aquest protocol. Sí, realment poca imaginació.

Bàsicament és un protocol per distribuir fitxers, fa temps s'usa de forma popular, però últimament ha tingut bastant resó mediàtic pel judici que ha tingut lloc a Suècia contra la pàgina d'emmagatzemament de .torrents The Pirate Bay. Al final sembla ser que poca cosa han pogut fer perquè tal pàgina tant sols guardava els fitxers .torrent i només actuava de tracker, i això no és delicte oi ?, ara probablement algú es preguntarà què és un .torrent? què és un tracker ? ara anem a això!

Protocol

El gran avantate que té el bittorrent sobre l'HTTP clàssic és que quan hi ha diverses baixades del mateix fitxer de forma concurrent (diverses persones volen baixar-se el mateix fitxer alhora), aquests usuaris s'envien trossos del fitxer entre ells. Per tant, com més persones hi hagi baixant un fitxer millor.

Com funciona.

El funcionament de cara l'usuari és ben senzill.

Un usuari es baixa un fitxer amb extensió .torrent, és un fitxer petit, menys de 60ks. Tot seguit s'obre amb el client de bittorrent i el fitxer es comença a descarregar. Pim pam.

En resum i explicat d'una forma planera el que passa és el següent:

Quan l'usuari obre el fitxer .torrent amb el seu client, aquest contacta amb el tracker (la direcció del tracker està dins el fitxer .torrent) que és un programa instal·lat en un servidor d'internet, i s'identifica com un usuari que es vol baixar aquell fitxer en concret. Tot seguit el tracker contesta amb les IP's dels diferents peers (altres usuaris) que s'estan baixant el fitxer, i que per tant, en ténen trossos. Seguidament el client contacta amb aquesta llista d'usuaris i els hi comença a demanar trossos, més endavant aquest client també compartirà els trossos que ja té.

De tant en tant contactaran amb el tracker de nou per refrescar la llista d'usuaris connectats que comparteixen aquest fitxer.

Fitxer Torrent

El fitxer .torrent és un fitxer binari. Bàsicament és un diccionari amb els següents camps i valors:

announce: La URL del tracker.
info: És un altre diccionari que conté:

name: Nom suggerit per guardar el fitxer o el directori.
pieces length: Mida dels trossos en que es parteix el fitxer (o fitxers) en bytes. El protocol parteix el fitxer en trossos del mateix tamany, amb la única possible excepció de l'últim tros. Els trossos normalment són de 256Ks tot i que es veu que en versions del protocol anteriors els trossos eren de 1Mb.
pieces: És un string, la mida del qual és múltiple de 20. Cada 20 caràcters representa el hashing SHA1 del tros que representa, per tant hi haurà tants subtrossos de 20 com trossos tingui el fitxer, i a cada posició 20*i , sient 0 <= i < #trossos hi ha el hashing per a aquell tros en concret.
length/files: O bé hi ha length o bé hi ha files, però estrictament un (i només un) dels dos. En cas de que sigui length, significa que el que s'està baixant és un sol fitxer i en length és el tamany total d'aquest en bytes. En cas de que sigui files representa un conjunt de fitxers dins d'una estructura de directori.

path: Una llista d'strings que corresponen a noms de subdirectoris, en cas de que existeixin.

Tracker

El tracker és el software que comunica els usuaris amb altres usuaris, hi ha diverses implementacions, una de les més famoses és opentrack er, que és la que utilitzen entre d'altres The Pirate Bay i la Wikipedia. A destacar la seva llicència, beerware.

Quan un client fa un GET (demana informació) a un tracker, la comanda HTTP té els següents valors:

info_hash: És un string de 20 bytes amb el hash SHA1 de l'apartat info del fitxer de metainfomració (aka .torrent)
peer_id: Id de l'usuari que es vol baixar el fitxer, aquest id és totalment aleatori i és generat pel client cada vegada que comença a baixar-se un fitxer de nou.
ip: (Paràmetre opcional) IP del client.
port: És el port al qual escolta el client, normalment és el 6881, en cas de que estigui ocupat és el 6882 i anar pujant fins al 6889.
uploaded: Els bytes que s'han pujat d'aquest fitxer. Això són els bytes que aquest client en particular ha enviat a altres peers.
downloaded: Bytes que s'han baixat fins aquest moment.
left: Número de bytes que falten per completar la transferència del fitxer. Cal notar que no té perquè ser el mateix que el resultat de la mida del fitxer - downloaded, ja que pot ser que hi hagi hagut una corrupció de dades o problemes de transferència, i que per tant algun tros de fitxer s'hagi de tornar a baixar.
event: És l'estat del client, pot ser started, quan s'està començant a baixar des del començament, completed un cop té tot el fitxer o stopped, un cop es para de baixar.

La resposta del tracker al client també són diccionaris en binari. Pot ser que el tracker contesti amb una entrada de failure, amb un contingut que és un string llegible amb el missatge d'error. En cas de que tot hagi anat bé el diccionari conté dues claus, la primera interval, que són el número de segons en que el client hauria de tornar a fer una petició d'informació al tracker. La següent entrada serà peers, que conté una llista de id's, ips i ports dels peers que s'estan baixant el fitxer. En cas de que hi hagi algun aconteixement especial un client pot fer una requesta d'informació al tracker encara que no hagi passat el temps indicat per aquest.

Comunicació entre peers

La comunicació entre peers és simètrica. Els missatges que s'envien d'un peer a l'altre són del mateix format i les dades (del fitxer que s'està compartint) poden anar també en els dos sentits.

Els peers es refereixen als diferents trossos del fitxer compartit amb indexs, que són exactament els mateixos indexs que hi ha al fitxer de metainformació. Un cop un client s'ha baixat un tros del fitxer i n'ha comprovat l'integritat amb el mapa SHA1 ho comunica a la resta de peers.

Les connexions entre peer i peer contenen dos bits d'estat. El primer, choked (tapat), si o no, i el segon, interessat, si o no. El bit the choked indica que el client està tapat, això vol dir que no enviarà més informació fins que sigui "destapat".

Una transferència de dades entre dos peers té lloc quan un dels dos està interessat i l'altre no està tapat. En cas de que un client no estigui interessat en res que tingui un altre client (sempre que aquest últim estigui destapat) aquest ho ha de fer constar amb el bit de interessat a fals.

El protocol recomana que quan s'està enviant dades, els clients haurien de tenir encuades a memòria diverses peticions de trossos per tenir una bona rendiment TCP, per altra banda quan s'està enviant dades a un altre peer també haurien de tenir els trossos a enviar a memòria, i en cas de que s'anul·li per qualsevol motiu la transferència, probablement el client quedi tapat. aquests trossos es poden borrar fàcilment. Això com ja he dit són recomanacions del protocol, caldria mirar exactament com s'implementa en cada client.

Per tant, quan dos clients s'envien missatges tenim bàsicament que comencen amb un handshake seguit per un fluxe d'informació de mida prefixada.

El handshake comença amb el número 19 en decimal seguit de l'string 'BitTorrent protocol'. A partir d'aquí, tots els números seran enters codficats en 4 bytes en big-endian. Seguidament venen els 20 bytes de hash SHA1 de la taula info_value del fitxer de metainformació, en cas de que els dos clients no donguin exactament el mateix hash, es talla la comunicació entre ells. En cas de que tot vagi bé s'envien 20 bytes més amb l'identificació del clients, en cas de que aquesta informació (l'id del client amb qui s'està comunicant) no aparegui a la informació sobre clients que havia donat el tracker, es talla la comunicació.

Tot seguit tenim el que és la comunicació en si entre peers, els missatges amb mida de cos cero són pings per fer saber i mantenir l'estat dels peers i s'envien cada dos minuts. En cas de que el cos del missatge tingui més d'un byte llavors cal mirar quin tipus de missatge es tracte:

0 - Choke
1 - Unchoke
2 - Interested
3 - Not Interested
4 - Have: És un número que indica que s'ha acabat de transferir i comprovat la integritat d'un nou tros.
5 - Bitfield: És un mapa de bits on cadascun indica quins trossos de fitxer s'ha enviat.
6 - request: Bàsicament és una petició perquè li enviin un tros. De paràmetre té un index.
7 - piece: Les dades en si del fitxer.
8 - cancel: Demana per cancel·lar una transmissió.

A l'hora de baixar els trossos normalment els clients trien els trossos de forma aleatori, així s'aconsegueix que estranyament es donguin situacions d'inanició que són les quals en que hi ha alguns trossos del fitxer que només estiguin en un o poc clients, cosa que faria que en el cas que aquests paressin de pujar fitxers ningú podria tenir el fitxer complert. Això forma part del protocol oficial de Bittorrent, tot i que algunes implementacions intenten millorar aquest aspecte fent que els trossos menys continguts en global entre els clients siguin els que tenen més prioritat per ser enviats.

i bàsicament... és això :)

Jerga

Vinga va, una mica de paraulotes relacionades amb el tema:

p2p: Peer 2 Peer, d'un a l'altre, d'un punt a l'altre, d'una persona a una altre, bla bla bla
peer: Un punt (ordinador, màquina, persona...) que participa en una comunicació P2P
seed: En el món bittorrent seeder és una persona que permet que d'altres puguin obtenir el fitxer un cop ell/a ja el té. Per tant, que no borra el fitxer una vegada l'ha baixat, sinó que el continua compartint.
leecher: justament al revés que el seeder, una persona que no comparteix el fitxer, tant sols el baixa.

Links

Especificació del protocol. Bastant ben explicat i bastant planera.
Wikipedia Hi ha un gràfic molt interessant. Pago una cervesa a qui l'entengui!

Primer post i presentació.

noreply@blogger.com (Marc) — Wed, 04 Mar 2009 00:41:00 +0000

Bé, començo el nou blog sobre informàtica distribuïda.

Com suposo ja sabreu n'hi ha molts de blogs d'aquesta temàtica per la xarxa. El que passa és que la majoria són en anglés.

Per tant m'he decidit en obrir-ne un en català.

Aquí aniré traduint els diversos articles i posts d'altres blogs que em semblin interessants i aniré fent-ne de propis, lògicament.

Bàsicament parlaré de protocols de comunicació, mecanismes de RPC, de serialització, de diverses eines i dissenys per arquitectures i sistemes distribuïts.

apa doncs.