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

Question

У меня есть данные полевой шины, которые отправляются в пакетах и ​​содержат данные (например, число с плавающей точкой) из источника.

=> Я получаю метки времени с идентификатором источника и значением.

Теперь я хочу создать небольшую программу (фактически, ведущий журнал в C ++, который предлагает интерфейс запросов через HTTP для отображения данных в виде диаграммы), где пользователь может выбрать несколько источников и интересующий диапазон времени и затем получает данные. Этот демон будет работать под управлением встроенной системы на основе Linux.

Итак, мой вопрос: какова наиболее эффективная схема хранения данных (производительность запросов и потребление памяти) для этих данных?

---

Приложение № 1:

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

• Скорость передачи данных, как правило, составляет 3 пакета в секунду (обычно используются пакеты до 30 / с)
• Интересные данные могут быть старше месяца (чем больше, тем лучше; алгоритм может использовать иерархию, которая обеспечивает сверхбыстрый поиск за последний день, быстрый поиск за последнюю неделю и приемлемый поиск для более старых данных)
• Идентификаторы (на данный момент) 32-битные.
• Используется всего 1000 идентификаторов, но заранее неизвестно, какой пользователь может использовать дополнительный идентификатор в любое время
• Сохраненные значения будут иметь разные типы данных (логические, целые, с плавающей точкой - возможны даже строки шириной 14 байт)

немного математики:

• Предполагая, что 32-битная временная метка + 32-битный ID + 32-битные значения в среднем создадут данные для хранения 12 байтов
• Это будет в течение месяца. 12 * 3 * 60 * 60 * 24 * 30 = около 100 МБ данных для фильтрации (в режиме реального времени с 500-МГц процессором Geode)
• Показ графика за последний день отфильтрует 1/30 данных - для фильтрации останется 3 МБ.
• Эти 3 МБ будут уменьшены до 1/1000-й (= 3 КБ), показывая только соответствующий идентификатор.

---

Приложение № 2:

Эта проблема в основном спрашивает, как мне перенести 2D-набор данных (время и ID - размеры) в память (и оттуда сериализовать его в файл). И ограничение состоит в том, что оба измерения будут отфильтрованы.

Предлагаемый отсортированный по времени массив является очевидным решением для измерения времени. (Чтобы повысить производительность запросов, можно использовать индекс на основе дерева. Сам бинарный поиск не так прост, поскольку каждая запись может иметь разный размер - но дерево индексов охватывает это красиво и в основном имеет одну и ту же основную идею).

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

Answer 1

Вы можете просто сохранить свои данные в SQLite и заставить ваш веб-сервер выполнять SQL-запросы к ним.Используя существующие инструменты, вы можете быстро создавать прототипы и видеть, насколько хорошо он масштабируется для ваших целей.

Answer 2

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

struct Page
{
    int id;
    int timestamp0, timestamp1;
    int bytes_used;
};

На каждой странице есть события только дляконкретный идентификатор и все страницы имеют одинаковый размер (например, 4K).Когда вы получаете событие, вы добавляете его на определенную страницу, если оно подходит, в противном случае назначаете новую страницу для этого идентификатора события.

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

Псевдокод для добавления события:

1. найти последнюю страницу для идентификатора x
2. если событие не помещается на странице, выделите новую свежую страницу
3. сохраните событие и обновите индексную запись для страницы

для выполнения поиска:

1. для каждой записи в индексе
2. , если запись касается идентификатора, который вам не нужен, затем перейдите к следующему
3. , если (page.timestamp0 >= tsmax || page.timestamp1 < tsmin), то страница не отображается.не содержит ни одного интересного события, перейдите к следующему
4. эта страница содержит хотя бы соответствующее событие;загрузите страницу и обработайте события, которые содержатся в интересующем вас периоде tsmin ... tsmax.

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

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

Answer 3

наиболее эффективно (производительность запросов и потребление памяти)

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

Самым простым и, возможно, достаточным решением будет использование IMO в виде простого массива, поскольку это наиболее сжатая несжатая форма, в которой можно хранить данные. Таким образом, каждый элемент массива содержит timestamp, id and value.

Когда вы запрашиваете данные с двумя отметками времени begin и end, вы определяете расположение отметок времени в массиве, используя binary search. Затем вы пересекаете все элементы и выбираете только те, которые имеют идентификаторы источников данных, которые вас интересуют. Элементы массива, конечно, должны быть упорядочены по временным меткам.

• Данные занимают O (n) памяти, где количество записей журнала равно n.
• Данные вставляются в O (1)
• Извлечение данных должно быть примерно таким: O (2 * log (n) + n * m), где n - количество элементов. Если у вас есть больше источников данных, которые вы хотите включить в запрос, вы можете сохранить идентификаторы источника данных в наборе, поэтому сложность будет O (2 * log (n) + n * log (m)).

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

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

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