как бы вы решали такую задачу?
На сервер льется телеметрия в формате "индекс"-"тип"-"значение". Она приходит пакетами. Записи внутри пакета и сами пакеты не упорядочены по индексу.
Задача: максимально оперативно выдавать упорядоченные по индексу непрерывные куски заданной длительности. Кусок должен содержать все "типы".
Здравствуйте, pva, Вы писали:
pva>как бы вы решали такую задачу?
Я бы сделал скользящее reordering window с фиксированным количеством слотов. Каждый приходящий пакет сначала вставлял бы на свое место, а потом "выдвигал" бы из окна столько записей, сколько собраных накопилось. Ну и сдвигал бы границы окна.
Ну и если очередной новый пакет в окно не помещается, потому, что старые недособраные записи не дают окну сдвинуться, значит, сдвигаем принудительно, выбрасывая старые недособраные пакеты (это в любом случае надо делать, иначе пропавший куда-то случайно фаргмент записи заблокирует эту конструкцию навечно).
Здравствуйте, pva, Вы писали:
pva>Привет,
pva>как бы вы решали такую задачу? pva>На сервер льется телеметрия в формате "индекс"-"тип"-"значение". Она приходит пакетами. Записи внутри пакета и сами пакеты не упорядочены по индексу. pva>Задача: максимально оперативно выдавать упорядоченные по индексу непрерывные куски заданной длительности. Кусок должен содержать все "типы".
pva>Например при заданной длительности 2: pva>Входящие pva>
не, чуток не то. Исторические данные могут прийти и несколько дней спустя. Свежие данные имеют приоритет, но при этом обрабатывать исторические данные тоже нужно.
Пока я остановился на таком варианте:
— сортирую и сливаю в непрерывные сегменты пришедший пакет
— затем новые сегменты вливаю в кеш, который содержит разреженные данные и заодно оставляю себе те сегменты, которые после слияния длиннее лимита
— затем пробегаюсь по остальным каналам в кеше, проверяя содержат ли они те же данные что и отобранные сегменты
— при совпадении — выдаю обнаруженные куски, заодно удаляя их из кеша
недостатком такого метода является фрагментация кеша. Например, для примера выше, приход индексов 4 и 5 (с пропуском 3) сгенерировал бы сегмент "45" и пришедшая позже "3" зависла бы в воздухе навсегда.
В качестве альтернативы можно установить дискретный шаг, размером с лимит. Но тогда, например, ".4" + "5." останутся "выпавшими".
Здравствуйте, BlackEric, Вы писали:
BE>Возможно я не понял задачу, но я бы всё это сложил в ClickHouse, построил индексы и забирал упорядоченные данные из него SQL запросом.
Боюсь, что это чересчур энтерпрайзно.
Во-первых, это решает только проблему сортировки и слияния, но никоим образом не решает вопросов определения "готовности" данных (наличие непрерывного сегмента данных во всех "типах").
Во-вторых, я уже проходил подобное пару раз ))) оверхед при использовании СУБД настолько огромный, что ни в сказке сказать, ни пером описать.
Здравствуйте, pva, Вы писали:
pva>Здравствуйте, BlackEric, Вы писали:
BE>>Возможно я не понял задачу, но я бы всё это сложил в ClickHouse, построил индексы и забирал упорядоченные данные из него SQL запросом. pva>Боюсь, что это чересчур энтерпрайзно. pva>Во-первых, это решает только проблему сортировки и слияния, но никоим образом не решает вопросов определения "готовности" данных (наличие непрерывного сегмента данных во всех "типах"). pva>Во-вторых, я уже проходил подобное пару раз ))) оверхед при использовании СУБД настолько огромный, что ни в сказке сказать, ни пером описать.
Если у вас данные идут с задержкой в несколько дней, то что вы используете в качестве кеша?
Наличие непрерывности тоже в принципе можно через sql проверять.
1. Сохранять поступающие элементы в dict/hash
2. При сохранении поддерживать количество для каждого индекса/типа (+1 для пришедшего элемента)
3. Как только наберется нужно количество (пришло каждого по два), доставать серию из п.1
Здравствуйте, BlackEric, Вы писали:
BE>Если у вас данные идут с задержкой в несколько дней, то что вы используете в качестве кеша?
redis. Но я в нем храню только списки границ непрерывных сегментов. Например, "1-4" "6-7"... Сами данные хранятся в другом месте.
BE>Наличие непрерывности тоже в принципе можно через sql проверять.
Даже боюсь себе представить. Не только с точки зрения sql, но и с точки зрения необходимых ресурсов.
Лет эдак 8 назад законтрактили меня на один проект "посмотреть одним глазом". Там чуваки использовали mssql для телеметрии, вида time-value. По таблице на канал. Ну и там еще много смешного было.
Пара таких серверов с трудом тянула чуть больше десятка "клиентов", жрала под $10k на AWS и помирала каждую ночь при выгрузке суточных данных.
Здравствуйте, pva, Вы писали:
pva>как бы вы решали такую задачу?
Непонятно условие выдавания значений наружу.
Что значит "все типы"? Есть какой-то словарь "всех типов", существующий отдельно? Тогда чему он равен для приведённого примера? [1,2]? Тогда почему в третьей строчке ничего не вывели? Что такое "длительность" в данном случае?
Здравствуйте, Dair, Вы писали:
D>Непонятно условие выдавания значений наружу. D>Что значит "все типы"? Есть какой-то словарь "всех типов", существующий отдельно? Тогда чему он равен для приведённого примера? [1,2]?
"все типы" для данного примера — это [1,2] как вы и указали. Да, словарь типов фиксированный. Иначе мы не могли бы определить условие — содержать все "типы".
D>Тогда почему в третьей строчке ничего не вывели?
Потому что в третьей строчке тип "1" "готов" — содержит непрерывный сегмент размером 2 семпла, а тип "2" в третьей строчке получил только свой первый семпл — не соответствует условию достаточной "длительности".
D>Что такое "длительность" в данном случае?
Размер непрерывного сегмента в семплах.
Здравствуйте, pva, Вы писали:
pva>"все типы" для данного примера — это [1,2] как вы и указали. Да, словарь типов фиксированный. Иначе мы не могли бы определить условие — содержать все "типы".
Ага.
D>>Тогда почему в третьей строчке ничего не вывели? pva>Потому что в третьей строчке тип "1" "готов" — содержит непрерывный сегмент размером 2 семпла, а тип "2" в третьей строчке получил только свой первый семпл — не соответствует условию достаточной "длительности".
А, то есть, в искомой нам последовательности должно быть по "длительности" каждого "типа", то есть, минимальный фиксированный размер выдаваемого пакета "длительность"*кол-во-"типов", да?
D>>Что такое "длительность" в данном случае? pva>Размер непрерывного сегмента в семплах.
А вот вопрос — что будет если в пятой строчке приведённого примера придёт, например, "0"-"1"-"Г"? "ААГБВ"?
А, нет, сам себя поправляю — длительность заданная, а не минимальная. Тогда я не знаю правильного ответа, что надо вывести?
Здравствуйте, Dair, Вы писали:
D>А, то есть, в искомой нам последовательности должно быть по "длительности" каждого "типа", то есть, минимальный фиксированный размер выдаваемого пакета "длительность"*кол-во-"типов", да?
Да, именно так. Не просто по длительности каждого типа, а они должны быть тех же самых индексов. То есть, если у нас тип "1":[0, 1], а тип "2":[1, 2] то это не "наш пациент".
И "длительность" задает минимальное ограничение на размер. Тоесть, нет проблем если при лимите 2 мы получим из "1.3" + "2" = "123" (по индексам).
D>А вот вопрос — что будет если в пятой строчке приведённого примера придёт, например, "0"-"1"-"Г"? "ААГБВ"?
Такое прийти не может — индекс является автоинкрементом на клиенте. Но из-за зашумленности сети пакеты могут теряться и для потеряшек повтор будет только через какой-то промежуток времени с тем же индексом.
D>А, нет, сам себя поправляю — длительность заданная, а не минимальная. Тогда я не знаю правильного ответа, что надо вывести?
Если у нас только два типа [1, 2], то что бы ни пришло пятой строчкой — оно будет частью нового сегмента, поскольку в примере выше предыдущие четыре строчки уже сформировали законченный сегмент и больше не участвуют в игре.
Здравствуйте, pva, Вы писали:
pva>Да, именно так. Не просто по длительности каждого типа, а они должны быть тех же самых индексов. То есть, если у нас тип "1":[0, 1], а тип "2":[1, 2] то это не "наш пациент".
Тут я потерялся. Исходно ты говорил про индекс и тип как отдельные друг от друга сущности.
А тут ты накладываешь уже ограничения на индекс тоже, то есть, их надо воспринимать совместно?..
Я уже думал что я почти всё понял, а вот нет!
Накидай ещё примеров, пожалуйста.
Вот, например, если в исходном примере индексы поменять на 1234 вместо 1001 — что поменяется?
Здравствуйте, Dair, Вы писали:
D>Тут я потерялся. Исходно ты говорил про индекс и тип как отдельные друг от друга сущности.
Спасибо что пытаешься разобраться. Исходно я писал
Задача: максимально оперативно выдавать упорядоченные по индексу непрерывные куски заданной длительности. Кусок должен содержать все "типы".
Тоесть, здесь присутствуют ограничения:
1) непрерывность
2) для выбранного куска — суть, заданной последовательности индексов [a..b] — присутсвие во всех типах.
То есть, выход есть только в случае когда у нас [a..b] существует для всех типов.
D>Вот, например, если в исходном примере индексы поменять на 1234 вместо 1001 — что поменяется? D>
Здравствуйте, pva, Вы писали: pva>Задача: максимально оперативно выдавать упорядоченные по индексу непрерывные куски заданной длительности. Кусок должен содержать все "типы".
Куски могут(должны) перекрываться?
Ну, то есть если у нас ровно один тип, то что должно выдаваться при таком входе для длительности 2?
0-0-A
1-0-B -> AB
2-0-C -> BC или ""?
3-0-D -> CD
В целом, задача выглядит достаточно прямолинейно.
Берём любую отсортированную структуру queue, например B-дерево. Ключ сортировки — (индекс, тип).
Параллельно с ней заводим структуру message фиксированным размером L*N, где L — длительность, N — количество типов.
Заводим lsn — текущий номер индекса, и readyCount — количество готовых к отправке отсчётов. Оба инициализируются нулём.
При поступлении каждого сэмпла
1. Если индекс — в диапазоне [lsn, lsn+L), и в message пришедшего отсчёта ещё нет, то
1.1. Кладём отсчёт в message
2.2. Увеличиваем readyCount. Если он равен L*N, то
1.2.3. "выдаём" содержимое message
1.2.3. Сдвигаем lsn: в зависимости от ответа на мой вопрос вначале, либо на L, либо на 1.
1.2.4. Правим message: в зависимости от ответа на мой вопрос вначале, либо очищаем, либо "сдвигаем" на N, освобождая новую строку.
1.2.5. Правим readyCount: в зависимости от ответа на мой вопрос вначале, либо обнуляем, либо уменьшаем на N.
1.2.5. Заполняем освободившееся место в message из queue
1.2.6. Выбрасываем из queue все данные с ключом меньше lsn
2. Иначе (индекс >= lsn+L) — кладём отсчёт в queue.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
pva>>Задача: максимально оперативно выдавать упорядоченные по индексу непрерывные куски заданной длительности. Кусок должен содержать все "типы". S>Куски могут(должны) перекрываться? S>Ну, то есть если у нас ровно один тип, то что должно выдаваться при таком входе для длительности 2? S>
S>0-0-A
S>1-0-B -> AB
S>2-0-C -> BC или ""?
S>3-0-D -> CD
После выдачи AB индексы 01 больше не участвуют. Тоесть для 2-0-C -> ""
S>В целом, задача выглядит достаточно прямолинейно.
Насколько я понял алгоритм, то он реализует дискрeтный шаг наблюдения.
В таком случае мы можем просто разбить весь диаппазон на "окна" размера N и хранить только счетчики для каждого окна при условии что во входящем потоке нет дубликатов.
По входящему индексу просто определяем какому окну принадлежит и увеличиваем там счетчик. По достижению N — выдаем результат.
Давайте увеличу лимит до 4, чтобы показать некоторые примеры
Текущее состояние "кеша"
Тип 1: 1 2 3 4 5 6 7 8 . . . 12
Тип 2: . 2 3 4 . . 7 8 9 . . 12
Входящий
Тип 1: 9
Тип 2: 10
Новое состояние
Тип 1: 1 2 3 4 5 6 7 8 9 . . 12
Тип 2: . 2 3 4 . . 7 8 9 10 . 12
Результат: [] - потому что нет в обоих типах последовательности длины 4+
Входящий
Тип 2: 5 6
Новое состояние (промежуточное)
Тип 1: 1 2 3 4 5 6 7 8 9 . . 12
Тип 2: . 2 3 4 5 6 7 8 9 10 . 12
Новое состояние
Тип 1: 1 . . 12
Тип 2: . 10 . 12
Результат: [ 2 3 4 5 6 7 8 9 ] - непрерывная последовательность длины 4+ в обоих типах
Здравствуйте, pva, Вы писали:
pva>В таком случае мы можем просто разбить весь диаппазон на "окна" размера N и хранить только счетчики для каждого окна при условии что во входящем потоке нет дубликатов. pva>По входящему индексу просто определяем какому окну принадлежит и увеличиваем там счетчик. По достижению N — выдаем результат.
Да. Гарантия отсутствия дубликатов упрощает алгоритм.
Update: Нужно быть аккуратным, и всё же держать очередь окон. Иначе есть риск первым собрать полный комплект не от "текущего" окна, а от "следующего" — тогда наивный алгоритм отправит сначала "следуюшее" окно, а уже потом — предыдущее.
В остальном, всё остаётся вполне простым.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Update: Нужно быть аккуратным, и всё же держать очередь окон. Иначе есть риск первым собрать полный комплект не от "текущего" окна, а от "следующего" — тогда наивный алгоритм отправит сначала "следуюшее" окно, а уже потом — предыдущее.
Нет ограничения на порядок отправки, равно как и требования фиксированного шага. Выше я уже показал как для размера 4 получить кусок, размером 8 не по границе "окна".
Впрочем, я уже реализовал через диаппазоны. Не очень оптимально по скорости, но коротко и читаемо. Следующий этап — добавить "заполненность", чтобы допустимо было выдавать куски заполненные не на 100%.
Здравствуйте, pva, Вы писали: pva>Нет ограничения на порядок отправки, равно как и требования фиксированного шага. Выше я уже показал как для размера 4 получить кусок, размером 8 не по границе "окна". pva>Впрочем, я уже реализовал через диаппазоны. Не очень оптимально по скорости, но коротко и читаемо. Следующий этап — добавить "заполненность", чтобы допустимо было выдавать куски заполненные не на 100%.
По-видимому, я неверно понял задачу.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
