Существует ли хорошо установленный инкрементный алгоритм для сохранения истории значений с накоплением за определенные промежутки времени?

Question

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

Моя система (которую я собираюсь использовать в OpenSource) имеет поток данных NetFlow. Вместо того, чтобы хранить в базе данных и использовать функции SQL, я предпочитаю иметь систему без базы данных и поддерживать набор статистики, обновляемый для каждого нового потока и прокручиваемый в секунду (или выше).

Мое решение включает в себя один массив uint для эффективного создания зубчатого массива размеров [60, 59, 23, 6, ...], представляющего секунды, минуты, часы, дни, недели и т. Д.

Каждый слот содержит общее количество байтов за это время. Таким образом, через 60 секунд статистика за одну минуту создается в виде Avg(секунд). Это, конечно, продолжается относительно времени.

Вместо того, чтобы просто иметь тысячи секундных приращений, это связано с:

1. Ограничения памяти и возможность иметь больше статистических узлов; А ТАКЖЕ
2. Идеальная презентация для пользователей

... что я свернуть шкалы времени.

Учитывая, что поток может применяться к нескольким узлам в иерархии статистики (WAN Link, IP Address, Destination Address, SourcePort-DestinationPort), я вычисляю дельту один раз (GenerateDelta), а затем просто применяю к каждому узлу, который является одновременно активным и который соответствует метаданным потока.

Статистика по данному узлу будет "прокручиваться" в следующих потенциальных случаях:

1. При чтении / отображении (через HTTP\JSON AJAX-запрос)
2. Когда дельта применяется (из-за соответствующего потока)
3. Просто каждые n-секунд (n обычно 1)

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

• GenerateDelta - маловероятно, поскольку это характерно для разбивки и усреднения потока с длительностью по слотам в массиве статистики.
• Прокрутка - если бы были только секунды, то это, конечно, было бы просто, однако мое решение требует, чтобы 60 секунд были объединены в новое общее количество минут каждые 60 секунд, и так далее.

Я не хочу, чтобы респонденты предлагали какие-либо собственные алгоритмы, я уже (почти) выполнил все свои собственные без проблем и со многими соображениями производительности. И другие, вероятно, смогут взглянуть на мой алгоритм, когда я закончу и опубликую его как Open Source.

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

Спасибо!

Answer 1

Благодаря комментарию @rici я обнаружил, что домен "Статистика потока" - это то, что требуется. Существуют системы управления потоками данных (DSMS) для работы со статистикой потоков. В то время как системы SQL RDBMS могут хранить данные со статистикой, сгенерированной SQL-запросом, системы управления потоком данных позволяют обрабатывать непрерывный поток данных по одному или нескольким запросам.

Эта статья описывает DSMS как:

1. Возможность пожертвовать качеством для качественного использования
2. Будучи за один проход, потому что данные огромны
3. Наличие запросов, рассматривающих данные как последовательности, а не множества И многое другое...

На этом изображена схема такой DSMS, ссылается на проблемную область анализа сетевого трафика,

В этой статье описывается StreamSQL, SQL-подобный синтаксис для определения непрерывных запросов.

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

На этой вики-странице можно найти несколько продуктов / прототипов DSMS, в частности, представляет интерес Odysseus, основанный на Java и с открытым исходным кодом.