Cursus — tree_nity pendiente
«treenity — Message Queue System»: un sistema de colas de mensajes con
topics, productores y consumidores, comunicados por IPC entre procesos, con un
hashmap hecho a mano y filtrado por prefijo. Proyecto de 42next, rank 05.
De dónde viene — En cuanto un sistema tiene varias piezas, no
todas van al mismo ritmo: el registro de un usuario genera un evento, la analítica lo procesa
más tarde y la facturación cuando puede. Una cola de mensajes es el pasillo
donde esos mensajes esperan, de modo que quien los produce no tiene que esperar a quien los
consume. El modelo de este proyecto, con topics, mensajes clave-valor numerados con
un offset y consumidores que recuerdan por dónde iban, es el de Apache
Kafka, creado en LinkedIn en 2011. El preámbulo del enunciado juega con el nombre:
cita a Franz Kafka y sus protagonistas perdidos entre intermediarios y mensajes que llegan
tarde o nunca. La diferencia con Kafka es que aquí todo ocurre en una sola máquina, entre
procesos, usando los mecanismos de comunicación entre procesos (IPC) clásicos de Unix. El
nombre del proyecto apunta a la otra mitad: los árboles con los que se filtra por prefijo.
Qué pide
Rank: 05Lenguaje: C++ (C++17 o posterior) o GoModalidad: grupo (no lo dice el enunciado; los repos vistos son de 2–3 personas)Versión: 2.0
- Dos programas,
server y client, con un Makefile con
all, clean, re y test. En lenguajes
interpretados o de JVM se generarían scripts con shebang, aunque los lenguajes admitidos son
solo C++ y Go.
- El servidor crea un punto de entrada IPC, acepta varios clientes, guarda en memoria los
mensajes de cada topic y los envía a los consumidores.
- El cliente tiene tres papeles: gestión (crear y listar topics, consultar los
datos de un cliente), productor (enviar mensajes a un topic, en texto o binario) y
consumidor (suscribirse a un topic, filtrar por prefijo de clave, empezar en un
offset concreto y conservar su posición entre reconexiones).
- Varios servidores pueden correr a la vez sin interferir; el PID del servidor sirve de
identificador único.
- Se entregan dos binarios de prueba,
ft_aquarium (un consumidor que dibuja
los mensajes como peces) y ft_fish (un productor de peces aleatorios), que
también se usan en la evaluación junto a otros tests automáticos.
01Topics, mensajes y offsets
Un topic es un canal con nombre que guarda mensajes. Cada mensaje tiene una
clave, un valor (datos arbitrarios del cliente; clave más valor como mucho 1024 bytes) y un
offset, un entero de 32 bits que asigna el servidor de forma creciente. Un consumidor
nuevo empieza en el offset 0; al recibir un mensaje lo confirma devolviendo el
offset al servidor, y si vuelve más tarde continúa donde lo dejó, salvo que pida otro offset
para releer o saltar mensajes.
La convención importa: el offset guardado es siempre el siguiente que el cliente
quiere leer, no el último recibido. Tras procesar el mensaje N se confirma N + 1.
Qué te obliga a aprender — La idea de log de solo
añadir: los mensajes no se borran al leerse, como en una cola clásica, sino que se quedan
numerados y cada consumidor lleva su propio cursor. Eso permite que varios consumidores lean
el mismo topic a ritmos distintos, que uno se caiga y retome, o que alguien vuelva a procesar
el pasado. También introduce el concepto de acknowledgement: un mensaje enviado no
cuenta como entregado hasta que el receptor lo confirma.
02IPC: la elección del transporte
Hay que elegir uno de tres mecanismos, y defender la elección en la evaluación:
- Colas de mensajes System V (
msgget, msgsnd…).
- Colas de mensajes POSIX (
mq_open, mq_send…).
- Tuberías con nombre (FIFO,
mkfifo).
El punto de entrada principal sirve para la gestión y el registro de clientes; cada
consumidor suscrito tiene su propio canal para recibir mensajes. Como estos mecanismos
suelen ser de un solo sentido, el enunciado pide diseñar cómo devolver las respuestas. No se
permiten librerías externas de IPC.
Qué te obliga a aprender — Los mecanismos de IPC de Unix y sus
diferencias. Las FIFO (que ya asoman en pipex o minitalk en el camino antiguo) son un fichero
especial por el que fluyen bytes sin fronteras de mensaje. Las colas System V vienen del Unix
de AT&T de los 80 y se identifican con claves numéricas que sobreviven al proceso si nadie
las borra; las POSIX son su versión más moderna, con nombres tipo ruta y notificaciones.
Elegir uno condiciona cómo delimitas los mensajes, cómo se crea un canal de vuelta y qué hay
que limpiar al terminar.
03Concurrencia y apagado limpio
- Al menos un hilo o goroutine por topic para procesar sus mensajes; el
procesamiento dentro de un topic puede ser síncrono o asíncrono.
- Acceso seguro a estructuras compartidas: en C++,
std::thread,
std::mutex, std::condition_variable y, si interesa,
std::shared_mutex; en Go, goroutines, canales y sync.RWMutex.
- Orden garantizado solo dentro de un mismo productor; entre productores distintos, no.
Los consumidores reciben en orden de offset.
- Con
SIGINT o SIGTERM, ambos programas terminan limpiamente:
liberan recursos, esperan a que los clientes confirmen y, pasados 5 segundos, salen
igualmente. El servidor debe borrar todos sus recursos IPC y conseguir que cada consumidor
suscrito salga con código 0 en vez de quedarse colgado; el método es libre y se explica en
la evaluación.
Qué te obliga a aprender — Patrones de concurrencia de verdad:
productor-consumidor, lectores-escritores, variables de condición. Y una lección de sistemas
que suele pillar desprevenido: cerrar tu extremo de un canal de un solo sentido no despierta
necesariamente al proceso que está bloqueado leyendo el otro, así que «apagar» requiere
avisar activamente. Los recursos IPC, además, no siempre desaparecen al morir el proceso: si
no los limpias, quedan en el sistema (ipcs los muestra).
04Hashmap y búsqueda por prefijo
Los datos de cada cliente (ID, topic, offset, prefijo opcional y ruta de su canal) se
indexan en un hashmap implementado a mano, con resolución de colisiones explícita
(encadenamiento o direccionamiento abierto). Los mapas de la librería estándar no valen para
esta parte.
Para el filtrado, cada topic mantiene una estructura eficiente de consumidores indexados
por prefijo; la elección es libre (AVL, rojo-negro, trie, tabla hash con lógica de
prefijos…) y se discute en la evaluación. Las reglas: user casa con
user y con user.login pero no con admin; el prefijo
vacío casa con todo, y esos consumidores se añaden directamente a la lista de entrega sin
recorrer la estructura. Varios consumidores pueden compartir prefijo.
Qué te obliga a aprender — Cómo funciona por dentro una tabla
hash (función de hash, cubetas, colisiones, factor de carga, redimensionado), justo la
estructura que en Python o Go das por hecha. Y por qué existe el trie o
árbol de prefijos (Fredkin, 1960): dada la clave de un mensaje, recorrer sus caracteres en un
trie da en un solo paso todos los prefijos que la cubren, en lugar de comparar con cada
consumidor uno a uno.
05La interfaz exacta
Los tests automáticos dependen de que los argumentos, la salida estándar y los códigos de
salida sean exactamente los del enunciado. Las formas de uso son:
./server
./client <ipc> create <topic>
./client <ipc> list
./client <ipc> produce <topic> [--raw]
./client <ipc> subscribe <topic> <nombre> [--prefix <p>] [--offset <n>] [--raw]
./client <ipc> info <nombre>
- El servidor imprime su identificador IPC (en el ejemplo,
/tmp/operator.server.1337).
- En texto, el productor lee líneas
clave:valor por stdin y el consumidor
las escribe igual. Con --raw los registros son binarios: tamaños de 32 bits en
little-endian seguidos de los bytes, sin separadores; el consumidor antepone el
offset.
info devuelve un JSON con cliente, topic, offset, prefijo y canal.
- Códigos de salida: 0 éxito, 1 error general, 2 error de topic o cliente, 3 error de
comunicación IPC, con precedencia 1 > 3 > 2 si se dan varios. Lo evaluable va por
stdout; logs y errores, por stderr.
- IDs de cliente y nombres de topic:
^[a-zA-Z0-9_.-]{1,32}$. Dos
suscriptores con el mismo nombre no pueden estar activos a la vez.
Qué te obliga a aprender — A diseñar un formato binario y a
leerlo de un flujo: con --raw no hay saltos de línea que marquen el final, así
que es el campo de tamaño el que dice cuántos bytes leer, y un registro cortado al final es un
error. El endianness (el orden de los bytes de un entero en memoria) deja de ser una
curiosidad en cuanto dos programas tienen que entenderse.
06Git, tests y README
- Se aplica entero un documento aparte, Git Workflow Guidelines: commits con
Conventional Commits
(
feat(broker): …, fix(consumer): …), un cambio lógico por commit,
una rama por funcionalidad con nombres del tipo feat/…, nada de
squash, y en main solo arreglos menores. Se comprueba con la
herramienta gitinette; no respetarlo es un 0.
- Tests unitarios completos del filtrado por prefijo, con Google Test en C++ o el
paquete
testing en Go, lanzados con make test.
- README en inglés con las secciones Architecture, IPC Choice, Data Structures y
Testing, además de las comunes.
Puntos delicados
- La convención del offset (se guarda N + 1) es fácil de implementar al revés y los
tests lo notarán en la salida de
info.
- El apagado: consumidores bloqueados que no se enteran de que el servidor se ha
ido, y recursos IPC que se quedan huérfanos en el sistema.
- El canal de vuelta: con mecanismos de un solo sentido hay que diseñar cómo
responde el servidor a cada cliente sin mezclar respuestas.
- Detectar un topic inexistente al producir: el productor debe salir con código 2
en vez de aceptar mensajes en silencio.
- El historial de Git cuenta desde el primer commit: conviene leer las guías antes
de empezar.
- Las librerías externas se toleran para estructuras de datos o para leer
argumentos si se justifican, pero nunca para el hashmap de clientes ni para el IPC.