[cpif] La paginación y algoritmos asociados

[Jesus Cea]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Por paginación, nos referimos al dividir un hilo o un subforo en
páginas. Por ejemplo, si un hilo tiene 100 mensajes, y cada página lista
15 mensajes, habrá 7 páginas, la última parcial.

La complejidad del asunto es poder ir directamente a una página
intermedia, sin que el cpif tenga que revisarse todos los mensajes
intermedios.

A continuación muestro un log que puede ser relevante. Se trata de una
conversación en la sala Jabber/XMPP python at conf.jabberes.org. Espero que
Heimy no tenga problema ocn publicar este log :)

Opiniones y propuestas bienvenidas:

>>>>>

14:16,26 <jcea> yo habia pensado tener un btree
14:16,35 <jcea> pero en vez de que la clave sean mensajes
14:16,38 <jcea> la clave serian paginas
14:16,44 <jcea> y el contenido sería un array con los mensajes de esa pagina
14:16,54 <jcea> que sería cortito (digamos, 25 mensajes por pagina)
14:17,01 <jcea> el problema es el de siempre
14:17,05 <jcea> si insertas un elemento en medio
14:17,10 <jcea> hayq eu recalcularlo todo
[...]
14:22,13 <jcea> si, es un btree de libro :)
14:22,47 <jcea> se hace así para poder tener btrees INMENSOS
14:22,59 <jcea> una posibilidad en cpif es pasar un poco de los btrees
14:23,09 <jcea> ya que un hilo no va a tener cientos de miles de mensjaes
14:23,18 <jcea> ni va a haber millones de hilos
14:23,26 <jcea> y trabajar con arrays persistentes
14:23,37 <jcea> que son O(N) (por ejemplo, una insercion)
14:23,41 <jcea> pero con una constante muy baja
14:24,38 <Heimy> hombre, lo de cientos de miles... es darle tiempo
14:24,46 <Heimy> CPI tiene casi 30000 mensajes en uno de los subforos
14:25,12 <Heimy> si sumas todos pasa de los 50000
14:25,19 <jcea> no importa el numeor total de mensajes
14:25,23 <jcea> sino el numero de mensajes por hilo
14:25,27 <Heimy> ah, bueno
14:25,30 <Heimy> por hilo no, claro
14:25,36 <jcea> hay hilos muy cafres
14:25,38 <Heimy> el más largo debe tener unos 500, como mucohj
14:25,39 <jcea> como el de presentaciones
14:25,42 <jcea> qeu son ya 100 paginas
14:25,46 <Heimy> mh
14:25,47 <Heimy> perdón
14:25,50 <Heimy> 250
14:25,55 <jcea> ¿cuantos mensajes se muestran por pagina?
14:25,57 <Heimy> que el límite está en 25 mensajes por página, creo
14:26,07 <Heimy> uh
14:26,09 <Heimy> 2500 entonces
14:26,10 <Heimy> que diga
14:26,10 <Heimy> :]
14:26,12 <jcea> pues hay ya algun hilo rozando los 3000 mensajes
14:26,16 <jcea> pero es un caso atípico
14:26,42 <jcea> la media puede andar por las 3-5 paginas
14:26,50 <jcea> que son unos 100 mensajes
14:27,06 <jcea> Segun eso, igual compensa pasar de los btrees
14:27,35 <jcea> Pero me preocupa tirar por una opcion con puntos debiles
14:27,43 <jcea> en plan que si un foro concreto empieza a tener hilos largos
14:27,48 <jcea> el rendimeitno sea una mierda
14:27,53 <jcea> No todo es cpi en este mundo :)
14:28,17 <Heimy> luego están los topics
14:28,28 <Heimy> el subforo más largo que tenemos ahora mismo también
roza los 2000 topics
14:28,29 <Heimy> pero vamos
14:28,48 <Heimy> independientemente de todo eso, los moderadores también
se supone que tienen función de jardineros
14:28,56 <Heimy> el hilo de presentaciones debería ser histórico ya
14:28,59 <jcea> si te fijas
14:29,07 <jcea> todos estos problemas son debidos a una "feature"
14:29,10 <jcea> que es la paginacion
14:29,19 <jcea> osea
14:29,22 <jcea> con los btrees
14:29,28 <jcea> puedo ir directametn a un hilo
14:29,36 <jcea> ir directo al primero y al ultimo
14:29,43 <jcea> o dado un hilo determinado
14:29,48 <jcea> ir facilmente al siguiente o al anterior
14:29,57 <jcea> peeero
14:30,03 <jcea> el problema es ir "al primero de la pagina 7"
14:30,23 <Heimy> el problema es que la paginación es esencial
14:30,28 <jcea> si
14:30,28 <Heimy> aunque sea hecha en memoria
14:30,34 <jcea> llevo toda la noche pensando cómo pulirmela
14:30,40 <jcea> y no hay manera
14:30,45 <Heimy> en disco, olvídala
14:30,52 <Heimy> yo preferiría hacerla en memoria
14:30,57 <jcea> si, esa es una opcion que estoy considerando
14:31,05 <Heimy> de hecho, hay que hacerla en memoria
14:31,16 <Heimy> no se almacenan las páginas
14:31,25 <Heimy> porque entra un topic nuevo (o un mensaje nuevo) y te
cambia
14:32,14 <jcea> si trabajas en memroia y no haces caché
14:32,14 <jcea> hundes el rendimeinto
14:32,15 <jcea> osea, un hilo de 94 paginas
14:32,18 <jcea> que vas al ultimo
14:32,39 <jcea> supone recorrerte los 92*25 mensajes
14:32,41 <Heimy> nah, la caché dala por sentada
14:32,42 <jcea> 94*25
14:32,53 <Heimy> pregunta tonta
14:32,53 <jcea> para ver cual es el primero de la pagina 94
14:33,17 <jcea> tampoco es una opcion
14:33,19 <Heimy> bueno, no
14:33,24 <Heimy> ya me se la respuesta
14:33,26 <Heimy> jum...
14:33,29 <jcea> no grabarlo en disco
14:33,41 <jcea> porque si cada tio que entra tienes que recalcular, vas
jodido
14:33,50 <jcea> combiene mas grabar a disco
14:33,57 <jcea> y purgar esa info cuando entra un mensaje nuevo
14:34,05 <jcea> asi recalculas una vez por mensaje nuevo
14:34,12 <jcea> no una vez por vista
14:34,29 <jcea> "conviene"
14:34,30 <jcea> :p
14:34,54 <jcea> ejemplo, la lista (ordenada) de hilos de un subforo
14:35,01 <jcea> que consta de 150.000 hilos
14:35,20 <jcea> solo hay que reordenarla cuando entra un mensaje nuevo
14:35,23 <jcea> no una vez por vista
14:35,31 <jcea> y con suerte el grueso de los cambios
14:35,38 <jcea> se concentre en un numero pequeño de indices
14:35,47 <jcea> (los hilos más recientes)
14:35,57 <jcea> y no tienes que reescribir en disco el ordende los 150.000
14:36,10 <jcea> Si entra un mensaje nuevo en el hilo 17
14:36,15 <jcea> solo tiene squ emoverlo a la posicion 1
14:36,22 <jcea> y correr el 1-16 un puesto
14:36,31 <jcea> el resto del arbol no lo tocas
14:36,58 <jcea> pero el programa debe ser capaz de tolerarlo
razonablemente bien
14:37,04 <jcea> (que se edite el hilo más viejo del foro...)
14:37,24 <jcea> nuevamente el problema e sla paginacion
14:37,28 <jcea> porque si no hubiera paginacion
14:37,37 <jcea> bastaría con que la clave del btree de hilos
14:37,46 <jcea> fuera el índice del mensaje más reciente en cada hilo
14:37,58 <jcea> cuando se añade un mensaje nuevo en el hilo 718 que está
en la mitad del btree
14:38,16 <jcea> simplemente se borra de ahi (está indexado por el
antiguo ultimo mensaje del btree)
14:38,21 <jcea> (del foro, digo)
14:38,31 <jcea> y se inserta exclsuivamente ese hilo en la posicion correcta
14:38,34 <jcea> osea
14:38,47 <jcea> sin paginacion, el trabajo es O(logx(N))
14:39,08 <Heimy> ya
14:39,14 <jcea> se me esta ocurriendo una idea...
14:39,19 <Heimy> pero lo de "sin paginación" no podemos ni siquiera
plantearlo
14:39,22 <Heimy> (para la interfaz web)
14:39,32 <jcea> imagina que tienes dos btress
14:39,38 <Heimy> a menos que nos inventemos una nueva manera de ver un
foro por web :P
14:39,45 <jcea> heimy, estaria bien :)
14:39,50 <jcea> supon dos btress
14:39,56 <Heimy> los supongo
14:40,01 <jcea> en la "pantalla" de hilos de un subforo
14:40,22 <jcea> uno de ellos la clave es el numero de mensaje ultimo en
el foro X, y su valor es el foro "x"
14:40,35 <jcea> con ese btree puedes tener la lista ordenada de hilos
14:40,38 <jcea> foro=hilo
14:40,45 <jcea> el otro btree esta indexado por pagina
14:40,56 <jcea> y simplemente te dice cual es el primer foro de la pagina X
14:41,25 <jcea> cuando un foro del medio
14:41,31 <jcea> pasa a ser el primero porque hay una entrad anueva en él
14:41,40 <jcea> el btree ordenado por antiguedad
14:41,50 <jcea> elimina el hilo en su posicion actual y lo inserta en la
posicion nueva
14:42,01 <jcea> esta operacion es proporcional al logaritmo del numero
de hilos. Osea, rapida
14:42,08 <jcea> ahora hay qeu actualizar el otro btree
14:42,20 <jcea> y se me ha courrido una forma "buena" de hacerlo
14:42,49 <jcea> dependiendo de donde estuviera el hilo original
14:42,51 <jcea> todas las paginas
14:42,58 <jcea> a) empiezan en elmismo hilo que antes
14:43,05 <jcea> b) empiezan en el anterior hilo que antes
14:43,10 <jcea> o c) empiezan en el hilo siguiente
14:43,15 <jcea> no hay más opciones
14:43,20 <jcea> por ejemplo
14:43,25 <jcea> si el hilo actualizado estaba en la pagina 7
14:43,36 <jcea> la pagina 2 empieza e el hilo anterior
14:43,41 <jcea> (que antes)
14:43,43 <jcea> la 3 igual
14:43,47 <jcea> hasta la 6
14:44,09 <jcea> y las paginas de la 8 en adelante empiezan exactamente
donde antes
14:44,36 <jcea> el tiempo de recalculo sigue siendo proporcional al
numero de foros
14:44,40 <jcea> pero ahora el tiempo es 25 veces más rapido
14:44,47 <jcea> porque solo examinas un hilo por pagina
14:44,48 <jcea> no todos
14:44,54 <Heimy> aquí arriba...
14:44,55 <jcea> (para ver cual era el anterior)
14:44,59 <Heimy> [01:41:58 PM] jcea: elimina el hilo en su posicion
actual y lo inserta en la posicion nueva
14:45,03 <Heimy> básicamente estás describiendo una cola
14:45,07 <Heimy> que es lo preferible
14:45,22 <jcea> una cola "normal" no puedes quitar un elemento del medio :)
14:45,27 <Heimy> ya O:)
14:45,40 <jcea> si el btree lo indexo por "ultimo mensaje escrito en ese
hilo"
14:45,42 <jcea> tengo el efecto de cola
14:45,48 <jcea> pero puedo acceder al interior
14:45,54 <jcea> fácilmente
14:46,09 <jcea> supongamos que tenemos 150.000 hilos en subforo
14:46,18 <jcea> si hay 50 hilos por pagina
14:46,29 <jcea> son 3000 paginas
14:46,42 <jcea> si hay un mensaje nuevo en el hilo más antiguo
14:46,53 <jcea> no tengo que revisar 150.000 hilos para reordenarlos
14:46,59 <jcea> sino solo unos 3000
14:47,16 <jcea> sigue siendo lineal, pero con una constante 25 veces menor
14:47,37 <jcea> si el foro editado es reciente
14:47,43 <jcea> el tiempo es rpoporcional al numero de hilos más
recientes que el
14:47,48 <jcea> no al numero de hilos en total
14:47,50 <jcea> uhm
14:47,53 <jcea> parece bastante razonable...
14:48,22 <jcea> ¿Cómo lo ves?
14:48,47 <jcea> ahora el problema
14:49,00 <jcea> es saber en qué pagina estaba el hilo que acabamos de editar
14:49,44 <Heimy> hehe
14:49,47 <jcea> una opcion es marcar los hilos
14:49,55 <jcea> cabecera de pagina (osea, el primero de cada pagina)
14:49,59 <jcea> cuando editamos un hilo
14:50,05 <jcea> retrocedemos en el btree (es rapido)
14:50,12 <jcea> hasta encontrar un hilo marcado como "cabecera"
14:50,22 <jcea> y así sabemos en qué pagina estabamos
14:50,55 <jcea> estoy viendo un problema
14:51,09 <jcea> y es cuando se mete un hilo nuevo, que NO es un hilo
antiguo modificado
14:51,23 <jcea> En este caso, los 150.000 hilos viejos se tienen que
correr un puesto
14:51,33 <jcea> y todas las paginas empiezan en el hilo anterior
14:52,17 <jcea> hay que recorrerse los 3000 elementos del indice, ir al
hilo anterior de 3000 hilos diferentes, marcarlos como cabecera, etc
14:52,22 <jcea> puta paginacion!!!!!!!!!!!
14:52,23 <jcea> :p
14:57,57 <jcea> se podria modificar la implementacion de los btrees
14:58,00 <jcea> de forma que cada nodo interno
14:58,07 <jcea> tuviese un contador por cada hijo
14:58,13 <jcea> que dijese cuántos hijos tiene debajo
14:58,22 <jcea> pero una insercion o borrado
14:58,26 <jcea> modificaría varios nodos
14:58,36 <jcea> en vez de uno (en la mayoría de los casos), como ocurre
ahora
14:58,55 <jcea> pero en este caso podría ser una opcion a considerar
14:59,05 <jcea> definir una clase "btree2" nueva
14:59,18 <jcea> que herede de "btree" e implemente los contadores
15:01,35 <jcea> una modificacion en un btree con 150.000 elementos
15:02,00 <jcea> supondría modificar unos 5 nodos nada mas
15:02,28 <jcea> (fan out : 16-32 nodos hijos por cada padre)
15:07,30 <jcea> otra posibilidad
15:07,47 <jcea> el btree ese con ordenado por fecha de modificacion
15:08,01 <jcea> pero "algunos" (digamos, uno de cada 50 hilos)
15:08,29 <jcea> contiene un puntero a un hilo anterior/posterior, y
tiene apuntado tambien su distancia
15:08,48 <jcea> no todos los foros tienen esa información, solo algunos
15:09,00 <jcea> cuando quieres moverte rapido por el los hilos
15:09,17 <jcea> puedes seguir esos enlaces, que te saltan de 50 en 50
hilos, o de 100 en 100
15:09,39 <jcea> cuando hay un ainsercion, borrado
15:09,48 <jcea> solo tienes que actualizar el enlace anterior/siguiente
15:10,03 <jcea> cuando te quieres mover a saco
15:10,06 <jcea> sigues las cadenas
15:10,08 <jcea> uhmmmm
15:10,52 <jcea> de hehco puedes tener metaforos
15:11,00 <jcea> con enlaces a varias distancias
15:13,39 <jcea> cuanto te quieres mover a la pagina 7
15:13,50 <jcea> tienes que localizar el hilo 7*50 = 350
15:13,56 <jcea> recorres las cadenas
15:13,59 <jcea> y vas sumando distancia
15:14,09 <jcea> el hilo 1 tiene un puntero al hilo 73
15:14,28 <jcea> te vas al 73 (directamente), qeu tiene un puntero al 110
15:14,33 <jcea> yu sigues la cadena
15:14,46 <jcea> hasta llegar al hilo 311, que tiene un puntero al 401
15:15,09 <jcea> puedes estar en el 311 y contar 350-311 hilos hacia adelante
15:15,23 <jcea> (iterar hacia adelante y hacia atras es eficiente)
15:15,29 <jcea> o ir al 401 e iterar hacia atras
15:26,20 <jcea> Igual había que sacar el tema en cpi
15:26,26 <jcea> "duda algoritmo" :p
15:26,38 <jcea> tal vez a alguien se le ocurriría algo :)
15:31,44 <jcea> Heimy: ¿no conocerás algun blog/lista de correo/foro/lo
que sea sobre algoritmos?
15:36,09 <jcea>
http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtree.html
15:36,11 * jcea leyendo
15:38,03 <jcea> ah, es como mi version de "btree2" :)
15:41,02 <jcea> una implementacion btree2 tendría un "len()" muy rápido :p
15:41,18 <jcea> le daré una pensada y lo sugeriré en durus

<<<<<

Tiempo después:

>>>>>

17:42,30 * jcea escribiendo mensjae a la lista de durus sobre los
counted btress
17:42,42 <jcea> hay un problema serio con ellos, y son los conflictos
17:42,57 <jcea> Dado que cualquier cambio en el cbtree altera todos los
nodos en la ruta desde el nodo objetivo hasta la raiz
17:43,12 <jcea> cualquier cambio en cualquier parte del arbol implica
cambiar el nodo raiz
17:43,20 <jcea> asi que cualquier transaccion en curso... conflicto
17:43,26 <jcea> osea
17:43,30 <jcea> con los btrees normales
17:43,35 <jcea> si tengo 1000 transacciones que simultaneamente
17:43,41 <jcea> alteran un btree GRANDE
17:43,54 <jcea> tengo buenas posihbilidades de que cada una altere un
trozo distinto
17:43,58 <jcea> y el commit tenga exito en todas
17:44,06 <jcea> En cambio con los cbtree, todos los cambios
17:44,09 <jcea> alteran la raiz
17:44,16 <jcea> asi que todas las transacciones se solapan
17:44,26 <jcea> y solo va a ganar la primera transaccion
17:44,36 <jcea> las otras 999 tendrán un conflicto y deberán reintentarlo

<<<<<

- --
Jesus Cea Avion                         _/_/      _/_/_/        _/_/_/
jcea at argo.es http://www.argo.es/~jcea/ _/_/    _/_/  _/_/    _/_/  _/_/
jabber / xmpp:jcea at 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
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iQCVAwUBRjuSwJlgi5GaxT1NAQINWgP/d6YXt8n16vIKbLxzXfPTaDB6a0OxVsP4
ZG8Hz+X1uPKVnNgRXeEpsO6Q1VQURvsM0kHwlt1CGwC/Ukh8Q5D2i0fy/akaQbkI
piSmvO+5cBygh3D1bVxYfMwTATwuBOvUaV1PLDFlnEjjA6YzP0qHJIO8biUW2eui
8/aFoboAYXw=
=rudj
-----END PGP SIGNATURE-----