Масштабируемый алгоритм обнаружения устаревших данных

Вот в чем проблема:

"агенты", установленные на многих различных серверах, посылают сигналы" сердцебиения " на центральный сервер каждые 5 секунд. Как я могу найти тех, кто пропустил свое сердцебиение более чем на 10 секунд, и поднять тревогу?

Проблема проста, если вы не думаете о масштабируемости. В простейшей форме вы можете записать метку времени последнего пульса, полученного от каждого агента в таблице базы данных, и выполнить регулярный запрос, чтобы найти те, что старше. чем порог.

Однако это решение не масштабируется на миллионы агентов.

Я ищу алгоритмы или технологии, которые делают это возможным.

3 2
monitoring algorithm

3 ответа:

  1. используйте карту: AgentId --> LastHearbeatTime
  2. Используйте 11 наборов (при условии, что достаточно разрешения в 1 секунду), каждый из которых содержит идентификаторы агентов, о которых сообщается в 1-секундном окне.

Каждый раз, когда агент сообщает о биении сердца: 1. Найди его на карте 2. Удалите его из соответствующего набора 3. Обновить информацию на карте 4. Добавьте его в соответствующий набор

Определите поток: один раз в секунду истекает самый старый набор. Она должна быть пуста. Если это не так-он содержит идентификаторы агентов, которые не сообщили. После истечения срока действия набора его можно повторно использовать (циклический массив наборов).

Я считаю, что это может быть реализовано без блокировок (возможно, Вам понадобится 12 наборов).

2

Без знания языка и платформы довольно сложно дать вам совет по детальной реализации, однако мой совет в чем-то похож на совет Лиора Когана. На мой взгляд, однако, вам нужно только два набора, и никакая карта не участвует:

Предположим, что у вас есть две переменные, представляющие наборы, A и B.

Каждый удар сердца удаляет идентификатор агента из набора A. Каждые 5 секунд другой поток создает предупреждение для каждого идентификатора агента в B, затем устанавливает B = A и, наконец, создает набор с все идентификаторы агентов и наборы A равны этому (если число идентификаторов агентов действительно велико, вы можете подготовить новый набор между одной проверкой и другой и только спать в течение оставшегося времени). Блокировка будет необходима только при изменении переменных, указывающих на каждый набор, при условии, что вы используете коллекцию наборов без блокировки. Производительность будет в значительной степени зависеть от алгоритмической сложности указанной реализации, и если вы пойдете по этому пути, вы должны отдать предпочтение тому, у кого лучшая производительность (не обязательно лучше всего big-O, например, если задержка wost-case имеет для вас значение) для удаления.

В качестве дополнительного замечания, если память не является проблемой или сбоев относительно мало, когда вы проверяете, нужно ли вам поднимать оповещения и делать это, вы можете сделать это в потоке самостоятельно и получить, возможно, интересные ускорения производительности (опять же, платформа и время выполнения имеют значение, ибо в erlang это было бы ветерком, но в Windows стоимость создания полномасштабного нового потока может превысить преимущество производительности, если сбоев немного) ценой сохранения старого набора B в памяти.

1

MongoDB отлично подходит для этого типа использования. Хотя это не совсем алгоритм, он подходит для фундаментальной технологии, которая необходима для создания этого сервиса. Мы используем его здесь, в CopperEgg, для нашего продуктаRevealCloud , чтобы делать именно то, что вы говорите - мы посылаем предупреждение, когда система ушла на некоторое время - выборка каждые 5 секунд. Я хотел бы услышать больше о ваших мыслях и прецедентах. Можете ли вы предоставить более подробную информацию?

-1