Fri, 26 Jun 2009
Consistent hashing and memcached, all you should know
Consistent hashing is a hash discipline to avoid some errors in traditional hashing - like modulus. Some memcached clients uses these techniques, perhaps libketama. With modulus hashing - key % n_servers - you may have problems when some server goes down. If you change the constant n_servers all of your keys will be mapped to other servers, this behavior can has disastrous consequences perhaps a lot of misses in a small fraction of time. Consistent hashing is trying to "address" this situation. Libketama implementation create one vector of integers where each integer is assigned to unique host. To matching some key to this vector you need convert this key in one integer and look up the most close integer host.
vector = [2 -> host a , 10 -> host b, 32 -> host a, 54 -> host b]
hash_key = f_hash("foo") <-- 7 perhaps
host = lookup(vector, hash_key) <-- host b
vector = [2 -> host a , 32 -> host a]
hash_key = f_hash("foo") <-- 7 perhaps
host = lookup(vector, hash_key) <-- host a
/*
host a has 2 Gb = 50% of keys
host b has 1 Gb = 25% of keys
host c has 1 GB = 25% of keys
*/
vector = [2 -> host a , 10 -> host b, 16 -> host c, 32 -> host a]
hash_key = f_hash("bar") <-- 7 perhaps
host = lookup(vector, hash_key) <-- host b
hash_key = f_hash("foo") <-- 12 perhaps
host = lookup(vector, hash_key) <-- host c
/*
host a has 2 Gb = 66% of keys
host c has 1 Gb = 33% of keys
*/
vector = [2 -> host a , 14 -> host a, 16 -> host c, 32 -> host a]
hash_key = f_hash("bar") <-- 7 perhaps
host = lookup(vector, hash_key) <-- host a
hash_key = f_hash("foo") <-- 12 perhaps
host = lookup(vector, hash_key) <-- host a
Posted at: 19:15 | category: /memcached | Comments (0)
Mon, 22 Jun 2009
Problemàtiques implícites de memcache i la seva arquitectura
Tornant a remenar una mica el tema de memcached, avui finalment he pogut muntar una prova de concepte sobre una de les problemàtiques que l'actual arquitectura de memcached que més mals de cap ens podria donar, l'obtenció d'un valor de la cache no vàlid. Cal tenir present primer de tot que memcached no és un sistema distribuït, això vol dir que les diferents instàncies del dimoni memcached que tenim al sistema no tenen constància de l'existència entre elles, per tan és problema del client - en aquest cas la implementació en C, python, php, pearl o altres - aconseguir el servidor cache on està allotjat un objecte en concret. Deixant per un altre dia les problemàtiques de l'ús de funcions hash no consistents, voldria concentrar-me amb un dels problemes derivats de la implementació del fail-over per part dels actuals clients. Moltes de les actuals implementacions - totes les que he vist - utilitzen el següent paradigma per tal de trobar el servidor on està allotjat un objecte/dada determinat.server = crc32(key) % n_servers
while( !connect(server, ...) && i < max_retries )
{
i++;
server++;
}
pfreixes@hidrogen:~$ memcached -m 128 -l 127.0.0.1 -p 11211 -vv
pfreixes@hidrogen:~$ memcached -m 128 -l 127.0.0.1 -p 11212 -vv
pfreixes@hidrogen:~$ memcached -m 128 -l 127.0.0.1 -p 11213 -vv
pfreixes@hidrogen:~/$ ./test set a 100
pfreixes@hidrogen:~/$ ./test get a
Value : 100
pfreixes@hidrogen:~/$ sudo iptables -D INPUT -p tcp --dport 11213 -j DROP
pfreixes@hidrogen:~/$ ./test set a 101
pfreixes@hidrogen:~/$ ./test get a
Value : 100
Posted at: 22:46 | category: /memcached | Comments (0)
Fri, 19 Jun 2009
Python-memcache errors en la selecció del servidor en cas de caiguda
Quan inspeccionava les problemàtiques intrínseques de memcached com a servidor de cache no bloquejant amb funcions de hash no consistents i les problemàtiques que això podia comportar - volia escriure un article al voltant d'això, vaig trobar-me que no podia reproduir alguns dels problemes que creien que es produirien mitjançant unes petites proves amb el modul de python-memcache. Primer vaig pensar, vaig errat segurament he confós l'arquitectura. Però tot i la nocturnitat dels fets vaig estirar el fil. De fet el codi de pyton-memcache es un sol arxiu i seguir el fil de les funcions no es excessivament problemàtic. La idea principal del joc de proves era veure com es podien produir inconsistències de cache per culpa de la reasignació de claus a un o altre servidor en cas de caiguda d'un d'aquests. i La prova en si hauria d'haver sigut d'allò més senzilla però per casualitats de la vida no funcionava. Mirant el codi actual de python-memcache vaig descobrir que utilitzava l'algoritme CRC32 per a calcular un hash "únic" a partir d'un string i que fent el mòdul d'aquest amb el número de servidors actuals s'obtenia a quin servidor connectar. Fins aquí tot correcte. El problema venia si aquell servidor no estava disponible, l'actual codi de python-memcache torna a calcular la hash concatenant un nou "digit" amb el valor de la iteració a la clau original. Per exemple, si la clau original es ABCDEF, el conjunt d'iteracions o claus provades seran ABCDEF1, ABCDEF12, ABCDEF123 i d'aquesta manera fins un màxim de 10 vegades - valor per defecte a Client._SERVER_RETRIES. Clar recordem que ha cada iteració es calcula el valor o hash d'ells. Que podria ser per exemple 100, 200, 300 i 400. Un cop es té aquest valor es fa servir el modul amb el numero de servidors, si en el nostre cas comptem amb dos servidors memcached tindrem 100 % 2, 200 % 2, 300 % 2, 400 % 2 que en tots els casos dona 0. Si portem aquests valors a la realitat el que esta passant es que la possibilitat de trobar un servidor es redueix a la possibilitat de calcular un número que estigui en el rang de projecció de la funció hash, si tenim dos servidors tenim un 50% de possibilitats de calcular un valor que caigui en el rang d'actuació del servidor x. Evidentment això es un problema, les ajudes de memcache ja diuen que si un servidor cau les claus associades a un servidor hauran de ser allotjades en un altre servidor - aquí rau un dels problemes de l'us de funcions hash no consitents. L'aproximació obvia que hauria d'haver efectuat el codi es la de la simple increment del valor inicial de la HASH. Per exemple començar per ABCDEF = 100, si falla 101 i d'aquesta manera fins arribar al nombre màxim de servidors disponibles. Mes tard vaig estar revisant el codi de l'antiga llibreria oficial de memcache i utilitzava el mecanisme descrit en el pàrraf anterior. Mare de deu quines coses que es veuen a les 4 de la matinada.Posted at: 04:41 | category: /memcached | Comments (0)
Python multiprocessing, threads go home
Recordo que una de les coses que va impactar-me més del disseny intern de Python era l'ús de GIL - Global Inter Lock - i els grans problemes que implicava en aplicacions multi thread on es feia ús intensiu de la CPU. Vaig pensar ingènuament que aquest handicap seria resolt per la comunitat tal com es faria més endavant en altres versions del llenguatge Python com ara la versió stackless. Però estava molt equivocat. A la versió 2.6 de Python - CPython - un nou modul anomenat multiprocessing ha agafat el protagonisme del paradigma de la multi concurrència. Multiprocessing proposa l'ús de processos com a entitats de processament en comptes d'utilitzar threads per tal de saltar-se - side stepping - la problemàtica de GIL vs. Trheads. He trobat una presentació força interessant feta pel mateix creador del PEP oficial - forma oficial de documentar i visualitzar informació en el projecte Python - que parla sobre el mòdul multiprocessing. Potser trobo a faltar una comparació entre la versió multiprocessing i multithreading de l'algoritme prime crunhing entre la versió de Cpython i stackless.Multiprocessing with python
La API de multiprocessing és quasi mimètica a la antiga - encara utilitzable - API del modul multithreading, per tan no hauria de ser molt problemàtic per a molts de "nosaltres" portar les nostres aplicacions a les noves tendències.
Però és aquesta tendència la solució a les problemàtiques endèmiques de Python en entorns de multi concurrència ? IMHO crec que no. Potser el mòdul de multiprocessing serà útil en una part de les necessitats però evidentment alguns dels problemes inherents de l'ús del procés com entitat principal de processament - temps de creació, compartir de forma explícita, .. - ens impedirà treure el màxim recurs a les noves plataformes hardware que tendeixen a inundar de cores les nostres plaques.
View more Microsoft Word documents from pvergain.
Posted at: 04:36 | category: /python | Comments (0)
Tue, 02 Jun 2009
Una primera aproximació tècnica sobre Google Wave
Ahir a la nit vaig tenir l'oportunitat de veure el vídeo de la presentació de Google Wave. Una hora i vint minuts llargs per presentar el que els germans Ransmussen diuen que seria el email si s'inventés a dia d'avui. A la xarxa ja hi ha alguns posts que fan un resum força interessant sobre el producte basats en la descripció funcional d'aquest i quines son les seves característiques més importants. Després d'acabar de visualitzar la presentació vaig quedar-me intranquil, una multitud de preguntes van començar a inquietar-me, entre elles dues de força interessants : quina era l'arquitectura de Google Wave ? i que significava posar a disposició del públic aquesta nova eina mitjançant alguna llicencia lliure ? Abans però de poder intentar respondre aquestes dues preguntes deixeu-me presentar el producte amb un paràgraf. Google wave intenta portar les actuals relacions humanes a la xarxa - email, blogs, microblogs, fotografies, wikis, etc - fins ara asíncrones - no simultànies - al món síncrona - que esdevé al mateix temps. Integrant al mateix temps totes elles en un mateix canal i format. Basant-se en l'actual protocol de missatgeria instantània però afegint a aquest tot un nou conjunt d'objectes que representen aquestes noves formes de relacions humanes a Internet. Quina és l'arquitectura de Google Wave? Google Wave té dues entitats diferenciades, una primera la forma el propi protocol de dades i un segon els actors que interactuen per a manejar aquest protocol. El protocol de Google Wave està discretament explicat a la pàgina oficial. Aquest està basat en l'actual implementació de XMPP i tal com comenten n'és una extensió per a poder donar suport a la comunicació en temps real entre wave servers per a intercanviar informació corresponent a la interacció en temps real de diferents persones. El format d'aquest protocol està composat basicament de dues tipologies de dades : les waves i les wavelets que anàlogament podríem descriure com la onada i la cresta de l'onada en un moment determinat del temps. Una wave és la unitat màxima d'informació i es iniciada per a algun servidor wave en un moment del temps, cada comunicació que es produeix en un moment del temps determinat relacionada amb un conjunt d'usuaris i un conjunt d'objectes se l'anomenat wavelet. Una wave pot tenir un número indeterminat de wavelets. L'actual especificació del protocol i implementació determina que qualsevol usuari que forma part d'una wavelet té permisos de lectura i escriptura de només aquella wavelet. Això implica que en un conjunt ampli de comunicacions - wavelets - que pertanyen a una mateix unitat - wave - certs usuaris tenen permisos diferents depenent exclusivament de si formen part o no de cada una de les wavelets. Al mateix moment una wavelet com a unitat mínima de relació d'informació entre persones i objectes està formada per un conjunt no determinat d'objectes que representen les diferents tipologies d'informacions que aquests s'intercanvien - missatges, fotografies, etc. Aquí és on arribem a un dels punts més importants del protocol, el sistema de transacció d'operacions. Al tractar-se d'un protocol en temps real i distribuït - multitud de persones prenen part en la comunicació - podem patir problemes d'inconsistència de dades. Semblant als problemes de transaccionalitat de bases de dades o bé de sistemes de versió distribuïts - git - el protocol de google wave també defineix la praxis que cal dur a terme en el seu model d'operacions El protocol descrit aquí necessita d'un conjunt d'actors per poder-lo dur a terme. L'arquitectura de google wave està basada primerament en l'anomenat wave server i el wave client. La federació de diferents wave servers ens permet la interacció de diferents grups d'usuaris que formen part d'una onada però que estan adscrits a diferents servidors. Cada wave server és propietari de les onades iniciades pels usuaris que formen part d'un servidor i s'intercanvien la informació de les diferents wavelets mitjançant el protocol i les operacions de transformació explicades anteriorment. Google Wave preveu ja de forma inicial dues formes d'ampliar de forma fàcil l'ús d'aquesta tecnologia. Les extensions i la incrustació - embed. Mitjançant les extensions - programes en python o java de moment - podem incorporar nous pluguins al wave server. Justament l'actual implementació interna de Google ja ens permet - mitjançant un compte d'usuari per desenvolupament - pujar les nostres pròpies extensions al seu servidor perquè aquestes puguin interactuar en les diferents comunicacions. L'exemple del traductor Roxy que es pot veure a la presentació n'és una prova empírica de la seva utilitat. Però si volem estendre o mes aviat obrir el ventall de possibilitats de l'usuari final disposem de la incrustació. A la presentació podem veure com el sistema de blogs de google - blogspot - esdevé un usuari més en les diferents comunicacions. Què i com serà lliure ? Aquesta pregunta vaig estar repetint-la dins meus fins a altes hores de la matinada. Que significava aquella frase que havia llegit en molts posts que aquesta infraestructura seria lliure. Alliberarien el servidor ? només el protocol ? I el client ? quina llicencia utilitzarien ? etc Finalment i després de passajar-me per el grup de discussió del protocol vaig poder llegir per part d'un desenvolupador de google la informació necessària per a poder començar a extreure conclusions : l'actual implementació té fortes dependències sobre L'arquitectura de google - bigtable, gfs ..- però esperem que a finals d'anys poguem alliberar una implementació del servidor que serveixi com a referència D'aquesta frase se'n extreu que si, que la comunitat disposarà d'una implementació lliure que podrà modificar, copiar o fer-ne el que vulgui. A Google li interessa que la comunitat pugui des d'un bon principi tenir un producte més o menys estable - el temps dirar - per a poder federar el màxim conjunt d'usuaris - empreses ? - a la seva xarxa mitjançant el nou protocol. Però, i les extensions del servidor ? Podrem disposar per exemple del traductor Roxy ? Crec i sóc de l'opinió que hi haurà tot un conjunt de eines que no seran alliberades per part de Google, aquestes seran en un futur les que definiran la qualitat d'un o altre producte. També caldrà saber que passa amb el client, si l'actual implementació - totalment depenent de html5 - serà alliberada o bé s'esperarà a que la comunitat tingui la capacitat de treure a la xarxa clients que suportin aquest nou paradigma. Crec sincerament que aquest no serà un element crític i no tardarem a veure els primers clients en format consola - ncurses - que donguin suport a la connexió de servidors wave. Pel que respectes a la llicència, haurem de veure si al final es decantant per GPL o bé quelcom més flexible - que no vol dir millor :) - com ara Apache Liscence.Posted at: 17:46 | category: /misc | Comments (1)