Распределенное вычисление предикатов в потоке событий

Question

Мой вопрос на самом деле представляет собой запрос на статьи, статьи, тексты или книги по проблеме, которую я пытаюсь решить в своей работе.

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

Например, предположим, что существует объект A который имеет атрибут под названием name и считать, что существует предикат P что верно, когда объект name равно Jhon.Каждое событие в потоке имеет метку времени и значение имени атрибута.Итак, рассмотрим следующую последовательность событий:

e1 = { name: Jhon, timestamp: 1 }
e2 = { name: Jhon, timestamp: 2 }
e3 = { name: Peter, timestamp: 3 }
e4 = { name: Doug, timestamp: 4 }
e5 = { name: Jhon, timestamp: 5 }

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

Теперь события не обязательно отображаются в потоке в правильном порядке согласно его временной метке.Каждое событие уникально благодаря своей временной метке, поэтому для одного и того же объекта не существует двух или более событий с одинаковой временной меткой.Кроме того, временные метки не обязательно образуют последовательность, которая всегда увеличивается на единицу:если мы увидим e1 с отметкой времени 1 и e3 с отметкой времени 3, это не означает существования e2 с отметкой времени 2.Нет никакой гарантии, что все события будут получены или когда они будут получены.Это часть проблемы, что мы знаем только о существовании событий, которые видим в потоке.

Реальный сценарий еще хуже:существует несколько компьютеров, параллельно обрабатывающих этот поток событий.Однако для простоты я пойду дальше в этом примере, рассматривая только один компьютер.

Если события поступают и обрабатываются в порядке, описанном выше, то отправляемые уведомления должны быть:

P(A) = true when e1 arrives
P(A) = false when e3 arrives
P(A) = true when e5 arrives.

Это правильная последовательность уведомлений, поскольку она учитывает порядок отметок времени.Теперь представьте, что компьютер получает события в следующем порядке:

e1, e5, e2, e4, e3

Наивный алгоритм, который не учитывает временную метку события, отправит неверную последовательность уведомлений:

P(A) = true when e1 arrives
P(A) = false when e4 arrives

Алгоритм, над которым я работаю, учитывает временные метки и определяет, когда уведомление должно было быть отправлено, но не было отправлено.Так когда e3 прибудет, он заметит, что уведомление P(A) = true для e5 не был отправлен.Это немного похоже на изобретение велосипеда, хотя мне не известно, чтобы кто-нибудь читал об этой проблеме.Мне бы хотелось получить ссылки на эту проблему или на что-то подобное, например, на некоторые статьи, посвященные такого рода проблемам.

Реальная проблема гораздо сложнее, поскольку она предполагает сохранение предиката $ imes$ состояние объекта в базе данных, которое работает как общее состояние между компьютерами, обрабатывающими поток, и я говорю о тысячах событий, поступающих в секунду, поэтому невозможно хранить все события в какой-либо базе данных.

Есть ли какая-нибудь литература по описанной мною проблеме?если да, не могли бы вы дать мне ссылки на него?

Я хотел бы увидеть статью или текст, объясняющий алгоритм, решающий эту проблему, и было бы еще лучше, если бы в такой статье были представлены доказательства алгоритма (например,правильность).

Если такой статьи не существует (я действительно так думаю), я бы принял ответ, который описывает алгоритм и предоставляет аргумент или доказательство его правильности.

Чтобы этот алгоритм был корректным, он всегда должен отправлять правильную последовательность уведомлений независимо от порядка поступления событий.И алгоритм не должен хранить все полученные события в памяти, потому что реальная проблема заключается в том, что слишком много событий невозможно сохранить в памяти или в БД.Было бы разумно хранить в памяти некоторые события, желательно фиксированное количество.

Answer 1

Результат невозможности №1:удаленные события

Проблема не может быть решена вообще;нет никакого способа гарантировать, что ваши требования будут выполнены, если некоторые события будут удалены (т. е. не получены).Рассмотрим сначала этот поток:

e1 = { name: Jhon, timestamp: 1 }
e2 = { name: Jhon, timestamp: 4 }

где алгоритм видит оба события.Далее рассмотрим этот поток:

e1' = { name: Jhon, timestamp: 1 }
e2' = { name: Pete, timestamp: 2 }
e3' = { name: Jhon, timestamp: 3 }
e4' = { name: Jhon, timestamp: 4 }

где алгоритм видит только события e1',e4' (остальные события потеряны и никогда не получены).Вы могли заметить, что то, что видит алгоритм в обоих случаях, идентично, поэтому его выходные данные будут идентичными в обоих случаях.Однако правильный ответ в этих двух случаях различается, поэтому нет никакой надежды на алгоритм, который всегда будет давать правильный результат.(Правильный ответ в первом случае — не выдавать уведомлений;правильный ответ во втором случае — создать два уведомления, одно из которых укажет, что предикат является ложным после получения e2', и один, чтобы указать, что предикат истинен после получения e3'.)

Неясно, как адаптировать требования к этой ситуации.Единственное правдоподобное решение, которое я вижу, — это сказать, что создаваемые уведомления должны зависеть только от полученных событий, а не от отправленных событий.Это эквивалентно указанию того, что события нельзя удалять.

Результат невозможности №2:переупорядочение событий

Вы заявляете, что должны иметь возможность обрабатывать переупорядоченные события без сохранения всех событий в памяти и с произвольным переупорядочением.Однако эти требования несовместимы:этого невозможно достичь.Рассмотрим длинную последовательность событий с временными метками 2,4,6,8,10,12,...Если в конце длинной последовательности событий приходит событие с нечетной временной меткой, единственный способ быть уверенным, что вы сможете его правильно обработать, — это сохранить всю историю прошлых событий (или прошлых состояний объекта).

Таким образом, вам также придется ослабить требование о повторном заказе.Возможно, вы готовы навсегда сохранить все события в памяти.(Если да, то у вас есть решение.) Возможно, вы готовы установить ограничение на повторный заказ, например, ни одно событие не будет задерживаться более чем на 10 минут.(Если да, то вам нужно хранить историю только за последние 10 минут, а все более старое можно удалить.) Возможно, в вашей конкретной ситуации имеет смысл что-то другое.

Но единственное, что нельзя, — это налагать все строгие требования, изложенные в вашем вопросе, и требовать всегда правильного алгоритма.

---

Мне не известна какая-либо литература по этому вопросу, и я не вижу особых оснований ожидать, что она будет.Это очень специфический набор требований, и мне кажется, что возникающая задача либо тривиальна, либо неразрешима.Обычно это не те проблемы, которые обычно изучаются в литературе.Возможно, вас заинтересует постоянные структуры данных, но это всего лишь причудливый способ хранения всей истории событий, который, как вы сказали, вы хотите сделать;и вам не нужна сложная структура данных, чтобы сделать это в вашей конкретной ситуации.