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 :-) 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%. 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 :-). > 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". 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
signature.asc
Description: OpenPGP digital signature
_______________________________________________ Python-es mailing list Python-es@python.org https://mail.python.org/mailman/listinfo/python-es
