пятница, 8 апреля 2016 г.

[prog] Несколько ссылок на тему topic matching algorithm

Столкнулся тут с необходимостью рассовывать MQTT-шные сообщения по подписчикам. И, поскольку подписки могут создаваться с использованием wildcard-ов (в MQTT это "+" и "#"), то важно делать это эффективно, а не за счет полного перебора подписок.

В процессе поиска информации в Интернетах наткнулся вот на эти ссылки, которые рассказывают, как это можно делать:

Две записи в блоге разработчиков RabbitMQ о том, как они решали эту проблему в 2010-ом году: Very fast and scalable topic routing – part 1 и Very fast and scalable topic routing – part 2.

Статья "High-speed message matching" с сайта ZeroMQ. И еще один вариант этого же материала, но на сайте OpenAMQ.

Небольшая заметка Optimizing Subscriptions in nanomsg от автора ZeroMQ и nanomsg.

Любопытная и большая статья Breaking and Entering: Lose the Lock While Embracing Concurrency с упором на lock-free реализацию и ссылкой на github с исходниками на Go.

Статья Fast Topic Matching Algorithm Implementation for WOS2 Message Broker. Как я понял, описанный в этой статье подход требует перестройки внутренних структур данных как при появлении новых подписок, так и при появлении новых топиков. Есть подозрение, что пара индусов довольно коряво пересказали часть ранее упомянутой статьи High-speed message matching.

Если нарою еще что-нибудь интересное, добавлю сюда. Хотя, простые решения на основе деревьев, в принципе-то, очевидны. И, как показал опыт RabbitMQ, еще и весьма эффективны.

Комментариев нет: