[Python-es] ¿Propuesta de algoritmo o estructura de datos para conjuntos aleatorios con pocos cambios?

[Jesus Cea]

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                         _/_/      _/_/_/        _/_/_/
jcea en jcea.es - http://www.jcea.es/     _/_/    _/_/  _/_/    _/_/  _/_/
Twitter: @jcea                        _/_/    _/_/          _/_/_/_/_/
jabber / xmpp:jcea en 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

------------ próxima parte ------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 473 bytes
Desc: OpenPGP digital signature
URL: <http://mail.python.org/pipermail/python-es/attachments/20171127/bd770087/attachment.sig>