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

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:

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

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>
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

Puntos delicados

Fuente