2017-11-27 23:37 GMT+01:00 Jesus Cea <j...@jcea.es>: > On 27/11/17 21:38, Francesc Alted wrote: > > De todas maneras, lo que intentaba era hacer ver > > que una ordenación siempre suele aumentar el ratio de compresión. > > Aquí > > hay un ejemplo mejor de lo que quería decir: > > > > In [40]: b = np.random.randint(2**63, size=1000*1000) > > Estás usando 63 bits, no 64, pero vale :-) >
Bueno, la verdad es que confieso que mientras estaba intentando los 64 me encontré con: In [8]: b = np.random.randint(2**64, size=1000*1000) --------------------------------------------------------------------------- ValueError Traceback (most recent call last) <ipython-input-8-43513dff6db1> in <module>() ----> 1 b = np.random.randint(2**64, size=1000*1000) mtrand.pyx in mtrand.RandomState.randint (numpy/random/mtrand/mtrand.c:16123)() ValueError: high is out of bounds for int64 y me dije "bah, probablemente Jesús me va a perdonar 1 bit" :) > > Ordenar mejora la compresión porque estamos reduciendo la entropía de > los datos. En mi caso, si tengo 256000 valores diferentes, podrían > ordenarse de 256000! maneras, un número de 1.4 millones de dígitos. Si > de todas esas posibilidades me quedo exclusivamente con la versión > ordenada numéricamente, me ahorro (por entropía) unos 4229911 bits > (aproximación de Stirling del factorial). Es decir, un compresor > perfecto comprimiría mis 8192000 bytes perfectamente aleatorios a > 7663261 bytes. Una compresión teórica máxima del 6.45%. Si los datos son > verdaderamente aleatorios y la única estructura que tenemos es que están > ordenados, no podemos comprimir más que un 6.45%. Salvo error matemático > por mi parte. (considerando 256000 valores de 256 bits aleatorios). > > Por tanto, insisto nuevamente, me centraría en buscar una estructura de > datos que acceda al mínimo posible de páginas de RAM, no en comprimir, > porque por la parte de compresión estoy limitado al 6.45% de un > compresor ideal que no existe. > > Usemos la fórmula para analizar tu ejemplo. Un millón de valores son > 1e6! de combinaciones de ordenación. Si me quedo solo con la variedad > ordenada numéricamente, un compresor IDEAL podría ahorrar 18488874 bits. > Tus datos ocupan 63 bits cada uno (no 64), así que en total suman > 63000000 bits. Con la compresión IDEAL salen 44511126 o 5563891 bytes. > Como tú partes de 64 bits de mentirijillas y no 63 bits reales (jeje, te > doy ventaja), el nivel de compresión máximo teórico cogiendo esos 64 > bits por elemento sería del 30.5%. > Buena estimación. Para ver que pasa con 64 bits he hecho la prueba fetén: In [25]: b = np.random.randint(2**64, size=1000*1000, dtype=np.uint64) In [26]: b.sort() In [27]: %time len(blosc.compress(b)) CPU times: user 26.3 ms, sys: 0 ns, total: 26.3 ms Wall time: 6.9 ms Out[27]: 6324530 Lo cual nos deja la compresión en un 21% (no 23% de 63 bits). Usando el codec más potente en blosc, el ztsd: In [28]: %time len(blosc.compress(b, cname="zstd")) CPU times: user 1.09 s, sys: 0 ns, total: 1.09 s Wall time: 290 ms Out[28]: 6050011 que representa el 25% de compresión (supongo que muy cerca del límite teórico). > > La compresión que muestra blosc en ese mismo ejemplo es del 23%. > Confieso que es una hazaña reseñable e inesperada y que mientras hacía > las cuentas estaba nervioso por que la "práctica" contradijese la > "teoría" matemática inviolable. A fin de cuentas yo soy ingeniero, no > matemático :-). > Bueno, mientras no se supere el límite teórico no hay ninguna 'hazaña' reseñable ;) > > > Probablemente ya lo habrás estudiado, pero con cosas como Cassandra o > > HBase no podrías atacar estos problemas? Si éstos te parecen demasiado > > 'pesados', a lo mejor un filesystem distribuido como Gluster > > (https://en.wikipedia.org/wiki/Gluster) ayudaría. Y si quieres más bajo > > nivel todavía, qué tal un simple almacén de objetos? Hay un interesante > > artículo sobre esto en: > > https://www.digitalocean.com/community/tutorials/object- > storage-vs-block-storage-services > > (a mí me gusta la aproximación de Ceph en particular). > > La clave del asunto es que los nodos de almacenaje no corren ningún > código especial. Imagina montar un sistema así con nodos tontos, simples > almacenes de datos sin capacidad para ejecutar ningún tipo de código. > Sus únicas operaciones son: escribir un objeto, leer un objeto y listar > los objetos que almacena (de forma muy lenta, por cierto). Supón que tus > nodos de almacenamiento son cosas como Google Drive o Dropbox, con una > latencia estratosférica e incapacidad total para ejecutar ningún código > más alla de GET, PUT, REMOVE o LIST. > > Los almacenes están completamente descoordinados y son TONTOS. Lo que yo > tengo montado es la inteligencia que hay por encima que permite > localizar y operar con los objetos A PESAR de que el almacenaje final no > coopera. También la replicación y la verificación de la integridad de > todo el sistema. > > Este proyecto tiene unos objetivos muy concretos. No pretende competir > con sistemas de almacenamiento distribuidos donde tienes el lujo de > ejecutar código en la máquina que te da el almacenamiento. En mi caso yo > no puedo ni siquiera confiar en que el almacenamiento no me mienta > descaradamente, como para entregarle alguna responsabilidad en la > gestión del sistema... > > Mi sistema lleva funcionando años con una excelente trayectoria. A > medida que crece el espacio de almacenaje hay que evolucionar los > algoritmos. No por un tema específicamente de velocidad, que es buena > ahora mismo cuando no paginas, sino porque a medida que los índices > crecen y ocupan más, acabas paginando. El cambio a "cuckoo hashes" > reduciría mis necesidades de memoria respecto a la versión actual del > sistema a un tercio, aproximadamente. Es decir, con los recursos > actuales, puedo triplicar mi tamaño hasta volver a tropezarme con el > problema que empiezo a rozar ahora: paginar. > > Ahora mismo estoy empezando a paginar en algunos momentos. Durante esos > "eventos", el rendimiento del sistema se va al garete y el problema > persiste durante dos o tres minutos por "evento". Reduciendo mis > necesidades de memoria a un tercio, puedo triplicar mi tamaño hasta que > vuelva a encontrarme en el mismo punto que estoy ahora, donde la > paginación "está empezando a molestar" (pero aún no es grave y supone > solo molestias esporádicas). > > Con mi ritmo de crecimiento de los últimos años, esto me da unos dos o > tres años de vida, tiempo suficiente para un cambio tecnológico, para > que el proyecto se vuelva irrelevante o para una rearquitectura. > > En realidad, hay muchas vías de escape, estoy lejos de tropezarme con un > muro insalvable. Un "cuckoo hash" es un proyecto de dos tardes a cambio > de dos o tres años de relax. Lo que estoy intentando es ver si algún > compañero conoce un algoritmo mejor para invertir en él cinco tardes a > cambio de la salvación eterna :-p > > Conozco Celph. De hecho uno de los nodos de almacenamiento de los que > hablo corre Celph por debajo, pero no puedo permitirme el lujo de > aprovecharme de ello. Ahora dime también cuánta memoria necesitas en el > directorio CELPH para mapear cien millones de objetos. No me cabe en mi > Raspberry PI con un gigabyte de RAM compartida con otros demonios :). > > Esta discusión está siendo muy interesante, Francesc. Sigamos :-). > > Centrémonos en la parte de acceso mínimo a páginas, ya que la parte de > compresión es un dead-end en este caso concreto. Tengo blosc en mi > arsenal para otros proyectos, puedes estar seguro de ello. > > Situación actual: con un cuckoo hash solo necesito el acceso a dos > páginas de memoria en el peor de los casos, por cada "lookup". El tiempo > de generación de los cuckoo hash es bastante irrelevante y se hace > offline, no en cada escritura de objetos. Me da igual que tarde 15 > horas. Básicamente el terabyte de objetos más recientes se gestiona de > otra manera diferente, que no describo en estos emails, el cuckoo hash > es solo para los petabytes "fríos". > Vale, ahora ya veo tu caso de uso con más claridad. La verdad es que me interesa mucho tu proyecto; si lo tienes en abierto nos podrías decir dónde está? Me gustaría 'jugar' un poco :) Francesc > > El objetivo es batir esas dos páginas de memoria por "lookup". ¿Ideas?. > > -- > Jesús Cea Avión _/_/ _/_/_/ _/_/_/ > j...@jcea.es - http://www.jcea.es/ _/_/ _/_/ _/_/ _/_/ _/_/ > Twitter: @jcea _/_/ _/_/ _/_/_/_/_/ > jabber / xmpp:j...@jabber.org _/_/ _/_/ _/_/ _/_/ _/_/ > "Things are not so easy" _/_/ _/_/ _/_/ _/_/ _/_/ _/_/ > "My name is Dump, Core Dump" _/_/_/ _/_/_/ _/_/ _/_/ > "El amor es poner tu felicidad en la felicidad de otro" - Leibniz > > > _______________________________________________ > Python-es mailing list > Python-es@python.org > https://mail.python.org/mailman/listinfo/python-es > > -- Francesc Alted
_______________________________________________ Python-es mailing list Python-es@python.org https://mail.python.org/mailman/listinfo/python-es
