Sé lo que estás mirando
Aquí el va el primer problema de algunos que iré proponiendo. Yo publicaré mi solución en unos días (4… o 5), dejando así un tiempo prudente ;]
/* si sois hábiles, no debería llevaros más que unos pocos minutos; pero en cualquier caso la velocidad no significa nada, lo importante es llegar a una buena solución; -es sobre todo un ejercicio mental, de diseño – */
Es muy sencillo pero, como nota, os diré que cuando vi la implementación de esto mismo en un proyecto grande… casi me echo a llorar.
***
Fue una de las primeras cosas que tuve que resolver hace algunos años para LoG85. Se trata de diseñar un fragmento del esquema de una base de datos para guardar, para cada usuario, qué publicaciones ha visitado y cuáles no. Las publicaciones pueden ser fotos, entradas, comentarios… lo que queráis, es lo de menos.
De partida tenemos una tabla usuarios y otra publicaciones, con los campos y restricciones que queráis; tenéis que conseguir que en la base de datos se guarden qué publicaciones han sido visitadas por qué usuarios. Tenéis libertad absoluta para crear o reformar tablas, escribir código, diseñar cachés… la película que queráis. Lo importante es que el sistema tiene que ser elegante (sencillo, claro, eficiente) y escalable (el número de usuarios y de publicaciones, así como su relación, puede crecer ad infinitum). Y por supuesto en todo momento la bd ha de encontrarse en un estado coherente; manteniendo la integridad referencial.
Si dais la solución en prosa, aseguraos de que todo está bien especificado 😉
*** SOLUCIÓN ***
¡Gracias a todos los que habéis participado! Bien vía comentarios, bien vía email o teléfono. Comento un poco las respuestas:
Todas las soluciones se han centrado en crear una tabla que representa la relación entre publicaciones y usuarios; las entradas de esta tabla nueva guardan qué usuarios han visitado qué publicación. Han habido diferentes versiones en las que se guardaban fechas, número de visitas, etc. Pero en cualquier caso, la versión básica de esta tabla, que sólo contendría dos claves ajenas a las primarias de las tablas usuarios y publicaciones, valdría (la primaria de la nueva tabla sería una composición de las dos ajenas).
Esta es la solución “trivial” que funciona. Pero no cumple uno de los objetivos del enunciado; no es escalable.
Primero, hablaremos de volumen; en un proyecto mediano que tenga unos 20.000 usuarios, es fácil que en pocos meses esos usuarios hayan visto una media de 1.000 publicaciones (fotos, tweets, entradas… lo que sea). Esto significa que nuestra tabla auxiliar tendrá 20.000.000 de filas. Y lo que es peor, crece geométricamente conforme aumenta el número de publicaciones y usuarios; a n*m. En pocos años tendremos una tabla con varios cientos de millones de filas, sólo para almacenar quién ha visto qué.
Aunque SGBD’s grandes tipo MySQL, MariaDB, Oracle… se comportan relativamente bien con tablas grandes, también tenemos que contemplar la posibilidad de que nuestra aplicación pueda correr sobre sistemas de gestión de bases de datos más modestos como SQLite. No sólo eso, para tener una velocidad aceptable es imprescindible tener los segmentos de las tablas más utilizados cacheados en RAM; con tablas tan grandes estamos invalidando la caché casi en cada consulta; llegado cierto punto límite en el que la tabla no quepa en memoria el rendimiento bajará de golpe varios órdenes de magnitud. Un diseño como este puede ser la diferencia entre que una aplicación vaya como un rayo en un hosting compartido o requiera un servidor dedicado entero para medio-funcionar. Y por supuesto, no podríamos ni plantearnos usar un sistema de instancias virtuales tipo Amazon, donde pagamos por consumo de memoria y ciclos de CPU.
La información mínima:
Este problema es peligroso porque es trivial encontrar una solución que “funciona”. Es fácil comformarse. Funciona en un “programa juguete” de estar por casa; pero muere en un entorno real. Tampoco hay una solución directa, dado que la información que tenemos que almacenar es esta y aparentemente no podemos reducirla más.
¿No podemos?
En realidad sí, y aquí está la magia.
Mi solución es usar una tabla “views” para las relaciones de esta forma:
| id_user | secuence_start | secuence_end |
|---|---|---|
| 34 | 5 | 5 |
| 34 | 7 | 10 |
| 34 | 12 | 12 |
| 36 | 20 | 28 |
| 785 | 5 | 5 |
La idea es la siguiente: lo más probable que es un usuario visualice muchas publicaciones con ids consecutivos (fotos de un album, respuestas de una entrada, entradas consecutivas, etc). Aún en el caso de que por la naturaleza de nuestra aplicación esta estadística no fuera cierta, más adelante veremos como forzar a que así sea.
Sabiendo esto, podemos explotar esta característica para almacenar segmentos de ids visitados, con un inicio y un final. Es decir, guardamos cosas como “el usuario 34 ha visitado todas las publicaciones de la 7 a la 10”.
A esto, añadimos un pequeño algoritmo de inserción, el consumo de CPU en la inserción es despreciable frente al consumo de CPU que supone consultas en una tabla cargada; además la inserción será una operación poco habitual.
Consulta para saber si una publicación ha sido visitada:
select true from views where id_user=$id_user and
secuence_start<=$id_post and secuence_end>=$id_post;
Algoritmo de inserción:
1) Comprobar si la publicación ya ha sido leída con la consulta anterior. Si es así, terminamos aquí.
2) Ejecutar:
update views set secuence_start=$id_post where
id_user=$id_user and secuence_start=$id_post+1;
Es decir, si queremos insertar como vista la publicación 6, y tenemos un segmento que empieza en la 7 para ese usuario, simplemente cambiamos el 7 por un 6.
El driver nos devuelve el número de filas cambiadas después de la operación, si es uno (se ha encontrado un segmento que cambiar), vamos al paso 2A. Si es cero, saltamos al 3.
2A) Comprobamos si el nuevo inicio de segmento es inmediatamente posterior a un final de segmento. Esto implica fusionar y desfragmentar segmentos que deben ser uno solo.
select secuence_start from views where id_user=$id_user
and secuence_end=$id_post-1;
Guardamos el resultado en una variable $tmp. Si $tmp tiene valor (hay resultado), actualizamos el segmento siguiente y eliminamos el que quedará con información redundante:
update views set secuence_start=$tmp where id_user=$id_user and secuence_start=$id_post; delete from views where id_user=$id_user and secuence_start=$tmp and secuence_end=$id_post-1;
Hemos terminado nuestra inserción y fusión 🙂
3) Ejecutar:
update views set secuence_end=$id_post where
id_user=$id_user and secuence_end=$id_post-1;
Es lo mismo que la operación anterior, pero para los finales de segmento. Preguntamos al driver el número de filas modificadas. Si es uno, pasamos a 3A, si no a 4.
3A) Repetimos las operaciones en 2A por el mismo motivo, adaptadas a una inserción de final de segmento.
select secuence_end from views where id_user=$id_user and secuence_start=$id_post+1; --guardado en variable tmp update views set secuence_end=$tmp where id_user=$id_user and secuence_end=$id_post; delete from views where id_user=$id_user and secuence_start=$id_post+1 and secuence_end=$tmp;
Terminada la inserción y fusión.
4) Llegados a este punto, no hay ningún segmento para el que nuestra entrada vaya a formar parte.
Ejecutamos:
insert into views values($id_user,$id_post,$id_post);
Y fin.
En cuanto pueda os pondré números reales de lo que supone realmente este algoritmo en rendimiento y reducción de tablas; basándome en la bd de log85 😉
¿Cómo llegué a esta solución?
Esto es lo más importante; la verdadera lección de este problema. A menudo tenemos que trabajar con cantidades enormes de información que no podemos comprimir en base a su grado de entropía usando métodos tradicionales.
Pero, como mentes inteligentes y cumbres del pensamiento abstracto que somos (nos queremos), debemos aprovechar nuestra condición humana para encontrar patrones y características que vuelvan a esa información vulnerable. Ya no en almacenamiento; en procesamiento cualquier “información sobre la información” que nos restrinja de una entrada de palabras aleatorias puede marcar la diferencia entre encontrar un algoritmo que se ejecute en 100ms, o tener que usar otro “default” que necesitará, literalmente, varios cientos años para darnos una respuesta.
Esta es sólo una idea. Puede mejorarse sobre la misma base y forzar la estadística para que los ids de lo que ven los usuarios sean más secuenciales. Por ejemplo; las entradas pueden tener ids como 100, 200, 300, 400… y los comentarios a las entradas como unidades sumadas a la id de la entrada: 101, 102, 103… así al ver entradas y comentarios tenemos un buen segmento asegurado. Esto no significa un límite de 100 comentarios por entradas. Cuando nos quedemos sin ids para la secuencia podremos romperla… al fin y al cabo, lo único importante de un id es que sea único (no necesariamente secuencial). Podéis jugar con esto para reducir la fragmentación entre ids de lo que realmente se ve.
Si lo probáis, veréis como la mejora con esta solución es espectacular. Espero que os haya gustado 🙂
Si te gusta esta entrada... compártela! 😉
0
0
0
0
0
010 Comentarios
Sí, parece trivial. Pero no lo es tanto…
A ver, es cierto, lo veo trivial, así que supongo que estaré errado pero por participar …
Crearía una tercera tabla Visita con dos claves ajenas apuntando cada una de ellas a las claves primarias de las otras dos tablas. La clave primaria de esta tabla Visita sería la combinación de ambas claves ajenas.
Cuando un usuario visita una publicación se añade una fila con el identificador del usuario y la de la publicación. Si se necesita guardar cuantas veces visita la publicación se puede añadir un atributo entero a esta tercera tabla fuera de la clave primaria.
Tu respuesta fallaría, pues un mismo usuario no podría acceder a un mismo contenido, más de una vez 🙂
No es un fallo realmente. Sólo hay que guardar qué se ha visitado ya y qué no. Podrías leer si ya está la combinación que quieres insertar antes de probar a insertarla; o controlar los fallos mediante excepciones 😉
Pues según he leído, no se trata de un problema demasiado complejo, aunque si bien es cierto, que yo he visto aproximaciones horrendas (con hacks incluidos) en proyectos medianos y grandes, que también me han provocado lágrimas de rabia.
Propongo una solición, escalable, eficiente, rápida, de fácil lectura y fácilmente comprensible.
Dado que se puede diseñar por especificación del enunciado, haré el ejemplo usando mi amado PostgreSQL (aunque con algunas modificaciones, podría ser migrado a otros sistemas relacionales), por comodidad mía, pondré nombres de campos en inglés.
CREATE TABLE users (
userID BIGSERIAL, — o SERIAL, depende de la cantidad
… (demás campos importantes de usuarios)
PRIMARY KEY (userID)
);
CREATE TABLE publicationsBase (
publicationID BIGSERIAL,
(…)
PRIMARY KEY (publicationID)
);
Llegados a este punto, y dado que PostgreSQL permite herencia entre tablas, me parece más correcto, realizar subtablas, dependiendo de la publicación, que hereden de la base con los datos comunes, por ejemplo una imagen quedaría:
CREATE TABLE publication_images (
img_src VARCHAR NOT NULL,
mime_type VARCHAR NOT NULL,
size INTEGER NOT NULL, — Bytes
PRIMARY KEY (publicationID)
) INHERITS (publicationsBase);
Siguiendo este modelo, tenemos un sistema bastante limpio, organizado, y clasificado en tipos y subtipos, facilmente ampliable y totalmente escalable y funcional.
Pero la parte sensible, que, precisamente es la que responde a la pregunta en sí, y para mantener la integridad referencial y el funcionamiento que se especifica, dado que sería una relación varios a varios.
Nota sobre PostgreSQL: El campo timestamp tiene una granularidad de 1 microsegundo, con lo que se puede dar por supuesto que es materialmente imposible que el mismo usuario acceda al mismo contenido, en el mismo microsegundo más de una vez.
Con esto dicho, propongo la solución como la siguiente:
CREATE TABLE user_visits (
userID BIGINT,
publicationID BIGINT,
visitDate TIMESTAMP DEFAULT NOW(),
PRIMARY KEY (userID,publicationID,visitDate),
FOREIGN KEY (userID) REFERENCES users(userID) ON DELETE CASCADE ON UPDATE CASCADE,
FOREIGN KEY (publicationID) REFERENCES publications(publicationID) ON DELETE CASCADE ON UPDATE CASCADE
);
NOTAS: Con la triple clave primaria, se cumplen las especificaciones del enunciado, manteniendo el modelo escalable, rápido (pues una primary key se indexa), y simple, ya que no se implementan cosas que rocen el estándar.
NOTA2: Debido a una limitación en PostgreSQL con las herencias y las claves foráneas, en la práctica, sería necesaria una tabla adicional para almacenar los IDs de las publicaciones, enlazar en esa nueva tabla las foreign keys a dichos IDs, y mantenerla actualizada vía triggers, pero dado que es un modelo teórico, para simplificar, no he incluido dicho proceso.
NOTA3: Me he olvidado de comentar que, se podría combinar esta solución con cachés del tipo memcached de forma trivial, y sin afectar, en nada, al diseño de la base de datos, manteniendo el mismo funcionamiento y almacenando, solamente, estadísticas de conteo de visitas la segunda vez que se haga un count sobre lo mismo, y borrando la cache de visitas cuando se almacene una nueva visita usuario/contenido, para forzar la SQL COUNT a ejecutarse nuevamente. Por ejemplo.
NOTA4: Lo que no se ha visitado, obviamente, no estará y un COUNT(*)>0 devolvería false.
Siguiendo esto, en caso de descubrir que el rendimiento de los que no se han visitado fuese un impacto importante (que lo dudo), la solución sería tan fácil como crear una tabla:
CREATE TABLE not_visited_publication (
userID BIGINT,
publicationID BIGINT,
PRIMARY KEY (userID,publicationID),
FOREIGN KEY (userID) ….
FOREIGN KEY (publicationID) …
);
Y mantenerla actualizada con:
– Trigger AFTER INSERT en la tabla publicationsBase
– Trigger BEFORE INSERT en la tabla user_visits para que borre la row correspondiente de not_visited_publication
Como se ve, esta tabla externa, no modifica en nada el diseño base de la base de datos, queda consistente, y se utilizaría a modo de cache, aunque, dada la facilidad de implementarla a posteriori y la improbabilidad de que sea poco óptima, no sería estrictamente necesaria.
Tal como se ha comentado hasta ahora usaría tres tablas y una de ellas (llamada visitas) sería la q contendría las claves ajenas a las otras dos (usuarios y publicaciones). En principio el problema no especifica q debamos almacenar fecha de la visita o si se ha visitado más de una vez una publicación por el mismo usuario, por tanto, la tabla visitas se compondría de 3 campos: el campo usuario que apunta a la clave primaria de usuarios, el campo publicación q apunta a la clave primaria de publicaciones y un tercer campo que sería la clave primaria consistente en un numérico autoincremental, de esta forma podemos repetir tantas veces como queramos usuarios con publicaciones.
Para mantener la integridad referencial habría q establecer una norma del tipo “on delete cascade”.
Muy buena la solución ¡bravo!, muy interesado en ver el estudio del impacto en el espacio en el mundo real. Por intentar llevarme al menos la chapa del botellín de la cerveza al concursante más preguntón y por alargar la vida del post, preguntar que pasa en el caso de que haya muchos grupos de una sola publicación.
En esos casos entiendo que es innecesario mantener uno de los dos datos ya que es mera repetición del otro, si se deja a null uno de los dos datos, ¿el SGBD reserva sitio de todas maneras para el dato?
Si se diera este caso y el número de grupos de una sola publicación fuera suficientemente significativo estudiaría la posibilidad de tener ambas tablas disminuyendo el espacio utilizado.
¿Disminuiría mucho el rendimiento?
Es una buena pregunta! En mi diseño original el dato final estaba a Null. Pero lo cambié en seguida porque repetir el principio y el final simplificaba mucho las consultas y además era más coherente conceptualmente con el significado “cabeza” y “cola” de segmento.
Cada SGDB por poder, podrá hacer lo que quiera. Pero realmente lo único que tiene sentido es que en tipos de datos básicos el valor NULL ocupe lo mismo que el tipo base (es imprescindible para que el acceso sea directo y rápido que todas las filas ocupen lo mismo). En tipos de longitud variable lo que realmente se almacena es un puntero a un archivo en el sistema de ficheros; de nuevo, el puntero de longitud fija.
En el peor caso el número de filas sería igual al de la solución trivial (de donde partimos); con la ventaja de que realmente, el peor caso es casi imposible que se dé en la práctica.
Por estadística, cuanto más se use el sistema más segmentos se crearán desde ids únicos (salvo que el número de publicaciones sea mucho mayor que el número de visitas, en cuyo caso tienes un problema, pero de otro tipo ;)) El rendimiento caería poco a poco conforme te acercas al peor caso. No lo separaría en varias tablas porque tienes que estar preparado para crear un segmento en cualquier momento, y trabajar entre tablas es mucho peor que trabajar en una (a menudo el SGDB hará el producto cartesiano de los campos seleccionados de las dos tablas antes de filtrar (esta es otra poderosa razón por la que reducir el número de filas es muy importante; las tablas grandes en seguida se vuelven inmanejables en consultas cruzadas)).
Tarde o temprano, y aunque lo tengas todo muy mal organizado (que no deberías), el tamaño medio del segmento sólo puede hacer una cosa: crecer 🙂