APDN code swarm
June 21, 2008 – 12:24 amPlease do not sleep in a middle of a video and wait for second part of video. You think the Christmas days are for sleep and eat and not for work
El problema de la multi concurrència amb Python
June 8, 2008 – 2:16 pmDes de fa ja uns quants anys s'estan imposant les arquitectures multi core en els ordinadors de consum. Aquest fet està ajudant a que molts dels desenvolupadors es preocupin per conceptes com la multi concurrència.
Mitjançant aquesta suport a la multi concurrència, dotada pels propis nuclis dels processadors, el programa pot efectuar tasques en paral.lel. Existeixen diverses metodologies de procediment algorítmic per a aconseguir aquesta multi concurrència, però totes elles es basen en el concepte de procés lleuger o thread.
Un procés pot estar format per varis threads. Tots els threads d'un mateix procés comparteixen espai d'adreces i tenen un segment de pila independent.
Els sistemes multi core actuals tenen la capacitat d'executar diferents fils d'un mateix procés en un moment determinat mitjançant l'assignació de diferents CPUs a cada un dels fils. És responsabilitat del programador però poveïr els mecanismes adequats per evitar accessos simultanis a segments de dades que aquests comparteixen.
Python, com molts altres llenguatges, dona accés a la possibilitat de crear i manejar threads mitjançant el modul threading. Aquest mòdul és una capa d'abstracció del built-in threading del propi cpython i que utilitza la implementació nativa del sistema operatiu. En cas de Python sobre Sistemes Operatius gust Linux aquest mòdul està implementat mitjançant les llibreries pthread.
El codi següent mostra com mitjançant el mòdul threading podem crear dos fils en un mateix procés Python.
#!/usr/bin/python import thread import time NUM_THREADS = 2 def foo(arg): print "I'm a thread %d" % thread.get_ident() if __name__ == "__main__": for i in range(0, NUM_THREADS): thread.start_new_thread(foo, (None,)) # join thread hardcode time.sleep(2)
Python implementa internament el que s'anomena Global Internal Lock, GIL, per a poder donar suport a múltiples fils sobre un mateix procés. Aquest mecanisme actua de forma semblant a un semàfor global davant de múltiples fils d'un mateix procés. Què significa això ? fem una ullada al següent codi:
#!/usr/bin/python import thread import time NUM_THREADS = 2 def foo(arg): del(arg[0]) print "I'm a thread %d" % thread.get_ident() if __name__ == "__main__": a = [ "hellow", "world" ] for i in range(0, NUM_THREADS): thread.start_new_thread(foo, (a,)) # join thread hardcode time.sleep(2)
Aquesta nova versió del programar modifica els paràmetres que es transmeten des del programa principal a la funció foo i com els threads els reben. Ara cada thread obtindrà momentàniament una referència a la llista [ "hellow", "world" ] per eliminar-la posteriorment amb la funció del. El recolector de brosa utilitza les referencies a objectes com un mecanisme de traçabilitat per eliminar objecte de la memòria.
Mitjançant el GIL Python pot prevenir que dos fils intentin efectuar una operació atómica sobre un mateix objecte a la vegada. En l'exemple que presetem el GIL evita que els dos threads que utilitzen la funció del decrementin simultàniament les referències a la llista [ "hellow", "world" ]. Aquest mecanisme però, no evita que el propi programador eludeixi la responsabilitat de crear les zones d'exclusió mútua pertinents.
El gran problema d'aquest mecanisme és la problemàtica que es genera en entorns multi core, en el següent gràfic podem observar aquesta problemàtica:
Aquest gràfic mostra com el GIL impedeix que les dues CPUs puguin executar de forma simultània dos threads que pertanyen a un mateix procés de Python. Cada un d'ells bloqueja l'altre mitjançant l'adquisició del GIL. Aquest serà el comportament habitual entre threads d'un mateix procés python i no podran explotar les múltiples CPUs d'un sistema.
Python però implementa diferents mecanismes a la seva màquina virtual per evitar l'starvation de la CPU, on un sol thread acapari de forma permanent la CPU. Un dels mecanismes utilitzats es la auto cessió de la CPU per part d'un fil cada n instruccions bytecode.
Existeixen implementacions lliures que ja eviten aquest comportament tan desagradable, pero desconec de moment quines són les prespectives per a les noves versions de Python
[APDN] Impacte de l’arquitectura del node
May 25, 2008 – 2:35 amSi recordeu algun dels meus últims posts sobre el meu projecte final de carrera, recordareu que us havia parlat de APDN, App Python Distributed Network. Doncs bé si tot va bé d'aquí a tres de setmanes presentaré davant del tribunal el projecte de forma definitiva. Finalment ha arribat el moment de començar a fer les proves de rendiment.
APDN és un middleware i com a tal s'interposa com una capa transparent entre el l'usuari i els nodes on s'executen tasques en segon pla. A cada node s'utilitza un programa anomenat apdnn, aquest s'encarrega d'executar les instàncies python, de seguir-les i finalment tancar-les.
El programa del node utilitza un model preforking per a realitzar el llançament de tasques, i utilitza un conjunt d'estructures de dades, un seguit de pipes i altres mecanismes IPC per a comunicar-se amb processos en espais d'adreces diferents.
Avui he he mesurat l'impacte de la infraestructura en el node. Aquesta tasca intenta mesurar quin overhead, si n'hi ha, provoca la pròpia infraestructura de programari de apdnn sobre el procés python. Normalment estructures, mecanismes de sincronització o altres com els comentats que formen part de apdnn poden provocar una penalització de CPU.
Un cop superats certs problemes amb el model d'atenció de peticions de xarxa sobre el servidor*, he pogut fer les proves que m'interessaven. Cal dir que ja m'esperava un impacte relativament baix, el propi programari apdnn no és molt intrusiu pels processos en segon pla un cop aquests s'estan executant.
En la prova que he fet he intentat demostrar que els processos python en un entorn amb APDN activat no tenen una penalització d'ús de la CPU versus un entorn no APDN. El resultat dels experiments l'he pogut reflectir amb el següent gràfic.
Aquest gràfic mostra quin és el nombre mig de claus md5 generades en un temps determinat per un conjunt de processos que incrementen de forma quadràtica. Lògicament si anem augmentant el nombre de processos aquests rivalitzen per la CPU i el nombre de claus md5 cau estrepitosament. Es interessant veure com l'arquitectura APDN no penalitza el procés batch amb menys CPU.
EL programa APDN per a fer aquesta demo es diu md5challenge, i té la següent pinta :
#!/usr/bin/python # # Example of app python code for app envelope # Pau Freixes, pfreixes@milnou.net # 2008-05-23 import signal import md5 _nrdigest = 0 _const_b = 20 _f = None _signal = False def handler_alrm(signum, frame): global _signal global _nrdigest global _f _signal = True def try_me(): global _nrdigest global _f global _signal _f = open("/dev/urandom","r") while _signal is not True: buff = _f.read(_const_b) md5.md5(buff).hexdigest() _nrdigest = _nrdigest + 1 if _f is not None : _f.close() # Define entry point with one input variable # req is a instance of Request object, usefull members of this object are: # req.input is a dictionary with input.xml variables # req.constants is a dictionary with constants defined into signature.xml # req.output is void dictionary for full with output variables # req.config is a dictionary with config values take from namespace # req.apdn_pid is a pid of aplication def main( req ): global _nrdigest signal.signal(signal.SIGALRM, handler_alrm) signal.alarm(req.input['time']) try_me() req.output['count'] = _nrdigest return req.OK if __name__ == "__main__": # test code class test_req: pass req = test_req() req.input = { 'time' : 10 } req.output = { 'ret' : 0, 'count' : 0 } req.OK = 1 main(req) print "Reached %d digests" % req.output['count']
Com podeu veure està preparat per córrer en standalone o bé sobre l'arquitectura APDN. Si ho fa en standalone un petit truc de python ens permet recrear un objecte del tipus Request i assignar-li en temps real els diccionaris necessaris perquè funcioni l'aplicació. En un entorn APDN la funció main ja rep de forma automàtica l'objecte Request. Aquest model d'execució és molt semplant al de mod_python.
*El model de xarxa ha canviat de working threads a un mix de working threads + dinamic temp threads. També s'ha afegit un model de cues per atenció de paquets de xarxa que fa el servidor una mica més equitatiu i evita el starvation de clients sobre nodes.
About google infraestructure and new human relationships
May 16, 2008 – 5:45 pmSome very geek Guy talking with other very geek guy
Guy 1 : Whath's your google cluster number ?
Guy 2 : I don't know but I'm sure the same of you, think about locality data problem
Una mica més de llenya al foc, openssl bug
May 14, 2008 – 8:29 pmAvui i veient que l'últim bug anunciat a debian security estava en boca de tothom, i tothom es preguntava fins a quin punt això podia afectar al status quo de la seguretat de les comunicacions segures, he decidit fer-li una ullada a tot plegat.
No és que sigui d'efectes retardats, sincerament a vegades les coses no en soc capaç de veure'n la dimensió fins que les tinc davant del tot. Respecte al tema puc resumir-ho com : certs programadors de debian han actuat de forma inconscient - per no ésser groller i tenint en compte la immensa feina - posant en perill durant els últims dos anys les suposades comunicacions segures dels nostres sistemes.
Ens podem fer unes quantes preguntes de tot el que envolta a aquest misteriós i increïble problema.
Primer de tot, Qui i com ha pogut fer això? Un mantainer de Debian va decidir al seu moment que cert codi havia de ser remogut - comentat en el cas del patch - perque no passava alguns dels testos d'un analitzador de memoria molt conegut. I no es va preguntar potser que aquesta línia era allà per una qüestió més important que la de sumar línies de codi ? Doncs es veu que no.
Segon, el raonament tècnic ? No sóc ni molt menys una autoritat en el tema i exiteixen bons llocs per informar-se del tema, en tot cas en faig una pinzellada tècnica del perquè de la inseguretat.
L'error es basa en la capacitat de predicció dels nombre aleatoris, que aquests són utilitzats directament per molts algoritmes de criptografia per a gener claus o d'altres eines necessaries per a securitzar protocols, medis o altres entorns. En el cas que ens ocupa, fent una ullada al substrat del problema aquest es troba localitzat a la funció ssleay_rand_add, utilizada per a generar buffers pseudo aleatoris, que al seu torn seran utilizats per a generar nombres aleatoris.
Recordem que la aleatorietat esta intrínsecament lligada a l'entropia de la informació, per tant es important ofuscar de forma eficient les dades que han sigut utilizades per a calcular aquests buffers pseudo aleatoris, el comentari introduït al codi redueix l'aleatorietat i augmenta l'entropia implicita, permetent fer atacs de força bruta.
Tercer, quins programes i paquets es veuen afectats ? Qualsevol que utilitzi openssl modificat per Debian de forma explícita - compilat estaticament - o bé de forma implicita - amb enllaç dinàmic. És el cas més comentat el de openssh. I altres programaris com MySql no es veuen afectats per utilitzar altres llibreries criptogràfiques.
Quart, nivell de risc ? Certament és complicat respondre aquesta pregunta i dependria molt del propi programa que utilitza les funcions afectades de openssl. Tal i com ja es mostrava en un missatge de farà alguns anys - els humans tenim la capacitat d'evolucionar al entrebancar-se a una mateixa pedra dues vegades - l'ús reiterat de la funció errònia mitigaria l'error per ella mateixa, gràcies a l'augment de l'aleatorietat. Aixó vol dir que si cridem 2N vegades la funció reduïm l'entropia i augmentem l'aleatorietat. Ara bé en el cas més habitual, com el de openssh, cal anar amb molt de compte.
Si ens concentrem estrictament en un paquet openssh, el risc és elevat - quasi catastròfic -, tal i com es comenta en aquest article l'espai de claus rsa o dsa generables és de només 32,768 valors diferents. És possible atacar una comunicació xifrada en temps real amb un maquinari normal i corrent.
Algunes distribucions només - debian stable entre d'altres - només proposen ugpradar el mateix paquet afectat openssl i no derivats com openssh i les claus ja generades - i dèbils - no es tornen a generar. Per superar aquest error podem eliminar les claus antigues i tornar a configurar el paquet openssh-server
root@hidrogen:/etc/ssh# rm ssh_host_dsa_key* ssh_host_rsa_key*
root@hidrogen:/etc/ssh# dpkg-reconfigure openssh-server
Creating SSH2 RSA key; this may take some time ...
Creating SSH2 DSA key; this may take some time ...
* Restarting OpenBSD Secure Shell server sshd
Feu una ullada a Barrapunto, a Slashdot a alguns dels blogs per ampliar aquesta informació, o bé a aquest magnífic article tècnic
Yahoo Hadoop !
May 2, 2008 – 12:28 pmJa fa 2 anys quasi que Yahoo va implantar els primers nodes Hadoop, no se si l'actual xifra de 2000 nodes ha augmentat significativament. Tampoc se si yahoo té intenció en un futur de migrar tota la seva arquitectura - per cert desconeguda - a Hadoop, pero m'entusiama la frase "it's not hard to imagine a time when Hadoop and Hadoop-powered infrastructure is as common as the LAMP"
En tot cas esperem que Microsoft falli estrepitosament en la seva intentona de comprar bèlicament a Yahoo. Ballmer es com un nen mal criat i Yahoo seria com una joguina nova, ja m'enteneu
Què és realment MapReduce ?
April 30, 2008 – 4:58 pmDes de fa uns anys paraules com ara MapReduce, BigTable, GoogleFileSystem o Google Batch Queue estan prenent protagonisme. Aquestes representen un nou paradigma tecnològic del qual podriem dir-ne que Google n'es el principal creador.
Totes aquestes tecnologies s'ha anat pensant, modelant i portant a la pràctica en una arquitectura hardware anomenada Commodity PC, formada per desenes de milers de nodes repartits per diferents data centers. Google ha sabut exprimir aquest concepte i ha sapigut aplicar una política de desenvolupament tremendament senzilla, basada en la màxima de Divide and conquer.
Algunes d'aquestes tecnologies ja s'estan projectant en el mon del programari lliure, aquest és el cas de Hadoop com a port de MapReduce. Però què és MapReduce exactament ?
Existeix un paper molt bo i no gaire dens escrit pels seus creadors i que en recomano la seva lectura, jo faré una petita aproximació tècnica i didàctica d'aquesta tecnologia.
MapReduce és una eina per tractar grans quantitats d'informació de forma automàtica amb un conjunt de nodes, on aquest conjunt pot anar de les poques desenes als diversos centenars de nodes. Per a poder processar de forma parl.lela la informació en diversos nodes MapReduce utiliza un parell de funcions anomenades Mapping i Reduce proveides per a l'usuari.
La funció Maping agafa com a paràmetre un valor, normalment una de les parts de l'entrada, realitza la lògica algorítmica i emet un un conjunt de parells clau, valor.
La funció Reduce agafa com a paràmetre una clau i el conjunt de valors possibles per aquella clau processats per la funció Mapping.
Anem a veure un exemple. Imaginem el problema de realitzar la cerca i comptatge d'un patró determinat en un arxiu. Un model bàsic seria força semblant al següent programa :
def grep(file_name, pattern): count = 0 fd = fopen(file_name, "r") for line in fd.readlines(): if ( re.search(pattern, line) ) count = count + 1 return count
MapReduce ens permet atacar aquest tipus de problemes d'una forma diferent, mitjançant la reducció del conjunt d'elements d'entrada.
Si haguessim de reescriure l'aplicació anterior a un format de MapReduce probablement tindriem quelcom semblant a això :
def map(part_file): for line in part_file.readlines(): if ( re.search(pattern, line) ): emit(pattern, "1") def reduce(key, list_values): count = 0 for value in list_value: count = count + 1 return count
Com podem observer ara tenim dues funcions, la funció map que agafa com a paràmetre una porció de l'arxiu d'entrada i la funció reduce que agafa com a paràmetre una clau i un conjunt de valors associats a aquesta clau.
Per poder respondre el perquè dels paràmetres i de les funcions el més útil es que veiem pas per pas que passa en una arquitectura MapReduce davant del problema i les funcions que s'han donat.
- MapReduce separa en N sub arxius l'arxiu orIginal. En el cas de MapReduce de Google això ja no serà necessari per la propia arqutiectura de Google File System.
- Cada sub arxiu o pedaç de buffer es passat a la funció definida per nosaltres i anomenada map, aquesta es podrà estar executant en qualsevol node de la infraestructura comodity PC. De fet tindrem múltiples intàncies d'aquesta funció executant-se en desenes de nodes.
- Cada una de les instàncies emet un conjunt de parells clau, valor. En el cas que presentem la funció map només emetrà valors del tipus pattern, 1
- A mida que les instàncies de les funcions map es van acabant, un conjunt d'instancies de les funcions reduce agafen les sortides amb el format clau, llista de valors
- Cada instància de reduce pot agafar una clau idèntica amb una llista de valors diferents, en el cas que ens ocupa les nostres instàncies de la funció reduce només reben la clau pattern, amb una llista de "1" que signifiquen comptatges del patró de les sortides de les funcions map
Aquesta és, simplificada, la metodologia de treball de MapReduce. La finalitat de MapReduce és doncs dividir el conjunt d'entrades per separar el seu processament en un cluster de nodes, aplicant la política de Divide and conquer
Existeixen múltiples problemes on aquesta solució és realment interessant, i en molts casos els problemes originals poden ser re escrits per aprofitar aquesta arquitectura. Análisis de logs, creació d'arxius invertits de frequenecies de paraules, treball sobre grafs, etc
Podeu trobar aquesta informació més ampliada al següent paper.
Libertat Franki
April 28, 2008 – 1:40 pmMentres els suposats progressites alçen les veus contra la Xina, on aquests giraven el cap davant de la provada i condemanda ratzia policial contra l'independentisme català l'any 92. Els suposats garants de la democràcia, aquí anomenats Mossos d'Esquadra, han empresonat a en Franki.
Llibetat Franki.
Una mica més de propaganda de Google
April 23, 2008 – 9:45 pmAvui m'he trobat aquesta presentació d'un dels enginyers de Google sobre algunes de les peculiaritats dels diferents sistemes que s'utilitzen actualment per a manejar alguns centenars de peta bytes de dades o desenes de milers d'usuaris simultanis a Google.
No parla de res de nou, BigTable, MapReduce, GoogleFileSystem i poca cosa més, però potser és la presentació més completa a nivell informatiu que he pogut veure.
Si teniu una estoneta feu.li una ullada.
plotting your svn commits
April 22, 2008 – 4:43 pmI have hat a small problem for give to my PFC director one time graph about order and time performance of my Apdn project. Because the first graph and the reality it's quite different.
I'm turn the problem and I decided explain only the true, this is my svn comit histogram about apdn project.
When x axes is a number of week project and y-axis is a sizeof(commit), i merge into weeks because split this histogram into several days is too big
You can create this histogram with this program and execute this into you workcopy subversion directory
pfreixes@hidrogen:~/myprojects/apdn$ ./svntrack.py > weeks.dat
pfreixes@hidrogen:~/myprojects/apdn$ gnuplot
gnuplot> set style data histograms
gnuplot> set output "apdn_hist_commit.png"
gnuplot> set terminal png
gnuplot> plot "weeks.dat" using 2:xticlabels(1)