iv_an_ru (iv_an_ru) wrote,
iv_an_ru
iv_an_ru

Category:

Обработка больших временных рядов в современных СУБД

Просили писать про базы данных всё подряд, не только хохмочки? Получайте.

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

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

== Round-Robin Database ==

Если последние данные намного интереснее старых, то возникает соблазн сэкономить ресурсы и хранить не один временной ряд, а набор векторов данных "с убывающей точностью". Скажем, 10000 последних событий, поминутную статистику последних нескольких часов, понедельную статистику последних лет и.т.п. При поступлении запроса компилятор выбирает самый точный из тех векторов, которые охватывают нужный интервал, и при необходимости интерполирует данные, то есть правдоподобно врёт. Основанные на этой идее хранилища называют round-robin, поскольку данные записываются в кольцевые буферы, каждая новая запись происходит поверх самой старой из ещё не забытых записей. Если для параметра хочется хранить среднее или среднеквадратичное отклонение, то хранят число отсчётов параметра и сумму значений (или дополнительно ещё и сумму квадратов значений), тогда поступление каждого нового отсчёта сопровождается только операциями сложения и не приводит к накоплению ошибок умножения-деления при переносе данных из вектора более частых отсчётов в вектор более редких. Кроме того, если есть, скажем суточный вектор почасовых статистик, то можно очень просто накапливать среднесуточную гистограмму: достаточно для очередного часа не перезаписывать значение в векторе, а прибавлять новое к старому. Можно добавить возможность вычислять положение в векторе не как простой модуль от времени по длине вектора, а как более сложную функцию. Скажем, можно разбить вектор на 12 частей из 24 значений и заполнять почасовыми статистиками каждую часть вектора в течение соответствующего месяца --- образуется набор гистограмм, среднесуточных для каждого месяца. Реализация такого хранилища не представляет больших проблем, и самой известной реализацией является, безусловно, RRDtool.

Узким местом любой такой системы является неизбежная потеря точности старых данных и ограничения в последующей их обработке. Например, значение функции от статистик может сильно отличаться от статистики значений функции. Простейший пример такой функции --- произведение. Пусть у вас есть большой красивый завод, на нём центральное отопление и поминутные отсчёты температур приточной и обратной воды, а также объёма прошедшей воды. Потреблённое тепло считается как произведение объёма на теплоёмкость воды и на разность приточной и обратной температур. Но если у нас полдня не поступало тепло, потому что по трубе лилась холодная вода, а ещё полдня тепло не поступало, потому что совсем не было напора, то согласно кривому теплосчётчику в среднем за день у нас была более-менее тёплая вода с половинным напором, и произведение этих средних внезапно оказалось больше нуля. Вы возмущаетесь, и идёте в суд. Таким образом, в round-robin хранилище надо бы запоминать не только данные датчиков, но и мгновенную мощность --- и разработчику более удачного теплосчетчика повезло, он знает, что нам понадобится именно эта, а не другая функция.

Если данные собраны правильно и имеются статистики, привязанные к существенным параметрам, в том числе статистики суточных/недельных/годовых циклов, то интерполяция будет достаточной для получения весьма правдоподобных результатов. Тем не менее, интерполяция даст особо крупный сбой при попытке подсчитать число туристов в Пекине в августе 2008-го. Интерполяция не знает про Олимпиаду. Если заранее известно про возможность Олимпиады, или, скажем, про возможность некоторого аварийного или специального состояния, то можно копить разные статистики для "обычного" и "необычного" времени. Например, телеметрия с борта самолёта сопровождается битом "тревога", исключающим данные из обычного накопления статистики и битом "шасси внизу", в соответствии с которым формируются два раздельных статнабора. Если возможны слишком разнообразные особые случаи, то имеет смысл отдельно для каждого случая сохранять наборы более точных данных и усложнить компилятор, чтобы он мог брать данные не из одного вектора, а из нескольких, либо вообще отказаться от идеи хранить данные в виде регулярных векторов. Это означает, что приходится окончательно распрощаться с простыми round-robin и начать использовать более сложные

== Time-Series Data Base ==

Round-Robin Database стирает самое старое значение, чтобы записать новое. "Настоящая" TSDB (Time-Series Data Base) не только не стирает старые данные по мере поступления новых, она может и вовсе не иметь операции удаления. Вместо этого она хранит временной ряд как две колонки одинаковой длины: в одной перечислены моменты времени, в другой значения параметра, соответствующие этим моментам. Если несколько параметров измеряются синхронно, то каждый параметр попадает в свою колонку, но они совместно используют колонку моментов. Хранилище умеет быстро искать значения параметров и их моменты по порядковому номеру отсчёта в ряду и быстро сформировать "вырезку" из временного ряда, ограниченную временем начала и временем конца либо ограниченную временем конца и имеющую длину не больше заданной. Поиск значения параметра по моменту времени состоит из получения вырезки длины 1 и взятия в этой вырезки значения номер ноль. Для этого сгодилась бы любая СУБД с поколоночным хранением, если бы не два обстоятельства. Во-первых, TSDB должна поддерживать очень быструю вставку данных, например, сто миллионов отсчётов в секунду на кластере из шестнадцати или даже четырёх не очень дорогих машин. Во-вторых, TSDB должна быстро выполнять несколько специфических наборов операций, самые важные из которых --- GDIAR и приблизительные джойны.

=== GDIAR ===

GDIAR --- это порядок подготовки временных рядов к выполнению "логической" части запроса. Прежде чем принимать какие-то решения на основании данных, или даже просто показывать данные пользователю, их надо "причесать", то есть избавить от излишних подробностей и несущественных ошибок. Буквы показывают порядок выполнения отдельных операций:
--- Grouping
--- Downsampling
--- Interpolation
--- Aggregation
--- Rate calculation

Grouping. Очень часто система получает от разных датчиков частичные данные, и сохраняет их в отдельные временные ряды. Скажем, покупатели случайным образом проходят через разные кассы магазина, а аналитика интересует суммарный поток покупателей через магазин. Группировка представит несколько временных рядов как один более плотный. В более сложном случае возможна группировка по мета-данным о рядах, чтобы получить, например, временной ряд покупателей с тележками и отдельно ряд покупателей через кассы "только с корзинками".

Downsampling. Если у нас есть посекундные отсчёты значения, а пользователь хочет посмотреть суточный график, то разумно построить временной ряд пореже, сгруппировав близкие по времени значения и взяв подходящую статистику для каждой группки.

Interpolation. Если данные реже, чем надо, то их можно пополнить, если они загрязнены высокочастотным шумом, то их можно сгладить. Комбинации интерполяции с прореживанием могут давать интересные результаты. Пусть у нас для каждой кассы есть временной ряд сумм чеков, пробитых этой кассой. Тогда проредив каждый ряд с интервалом 10 минут и оператором count, му получим набор рядов для числа покупателей в минуту, а интерполировав получившиеся ряды с оператором avg, мы получим среднее число покупателей, которые за 10 минут проходят через одну _работающую_ кассу. Если бы мы просто считали все чеки и поделили на постоянное число касс в магазине, результат был бы, очевидно, иным.

Aggregation. С этим этапом всё понятно. Если нам не хватило агрегатных функций на более ранних этапах, самое время позвать ещё одну. Скажем, суточные максимум и минимум среднего числа покупателей, которые за 10 минут проходили через одну работающую кассу. Хотя чаще это прозаическая сумма или максимум по всем значениям из интервала запроса.

Rate calculation. Если у нас есть монотонно растущий счётчик событий, то rate calculation строит регулярный ряд, значениями которого являются количества событий в единицу времени. Это выглядит очень простой операцией, если бы не два обстоятельства. Во-первых, счётчик событий может иметь недостаточную разрядность и переполняться. У оператора есть cпециальная опция, которая позволяет корректно обработать переполнение. Во-вторых, счётчик может быть сброшен на ноль некоей "перезагрузкой" источника данных. Ещё одна опция оператора позволяет с большой надёжностью распознать и такую ситуацию. Добавление этих двух опций делает rate calculation буквально незаменимой операцией.

В случае обычной СУБД, все перечисленные операции могут быть выполнены хранимыми процедурами. Разница "всего лишь" в скорости. В хорошей TSDB на языке низкого уровня пишутся не только все используемые в "причёсывании" операции и аггрегатные функции, но и все их популярные комбинации, а оптимизатор знает подробности семантики выражений и способы упрощения тех или иных выражений для конкретных типов рядов. Кроме того, оптимизатор может использовать аналог "materialized persistent view" для часто повторяющихся выражений над рядом.

Итак, мы получили "причёсанные" временные ряды. Не слишком длинные, не слишком короткие, без артефактов вроде высокочастотного шума и переполненных счётчиков. Остаток вычислений происходит примерно так же, как и в любом XQuery- или SQL-процессоре (В зависимости от того, на что похож язык запросов используемой TSDB --- на XQuery или на SQL). Есть таблицы, для них есть реляционные операции, всё как обычно. Единственная разновидность операторов, которых нет в обычной реляционной алгебре, это

=== Приблизительные джойны ===

Вернёмся к примеру про теплосчётчик: два градусника и расход в кубометрах. Хорошо, если у нас есть одна общая колонка времен отсчётов, используемая и рядами для градусников и рядом для расхода. Хуже, если измерения поступали по независимым каналам, и теперь у нас есть две или даже три колонки времён. С общими временами отсчётов задача сводилась к поэлементному произведению вектора расхода на поэлементную разность векторов температур. С разными временами для каждой операции необходимо устранить расхождения по времени, а для этого задать три параметра:
--- допуск, в пределах которого отсчёты считаются достаточно одновременными для данной задачи,
--- метод, которым будет выполняться согласование данных во времени (выбор самого подходящего отчёта, интерполяция, некоторое усреднение и т.п.),
--- что делать, если общий отсчёт получить невозможно.
Казалось бы, это всё можно сделать операциями "причёсывания", обработав три исходных временных ряда как одну группу, но это не так. Если бы мы собрали их в группу, то на выходе получили бы временной ряд, в котором все значения параметров были бы записаны вперемешку, без указаний, какие числа соответствуют температуре, а какие --- давлению. Причёсывание было бы полезным, если бы мы могли слегка пожертвовать точностью вычислений. Можно построить прореживанием три регулярных временных ряда с одинаковыми интервалами, и этим свести задачу к случаю общих времён отсчётов.

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

== Функциональность традиционных TSDB не покрывает растущие потребности разработчиков. ==

Интерполяция внутри приблизительного джойна, как и любая другая, может выдать правдоподобную фантазию, особенно если временной ряд описывает параметр, имеющий смысл не непрерывно, а только в некоторые моменты времени. Решением может быть использование "двувременных" рядов, в которых для каждого значения дополнительно хранится конец временного интервала, в котором оно сохраняло валидность. Достоинство --- исчезает всякая двусмысленность. Недостаток --- дополнительная колонка требует ресурсов и дополнительной логики в оптимизаторе запросов, но хуже всего --- дополнительной логики на этапе GDIAR. Большая часть операций "причёсывания" будет отбрасывать данные о концах интервалов, для остальных придётся писать дополнительный код.

Что ещё хуже, при использовании двувременных рядов сохраняется риск логической ошибки, связанной с задержками в получении информации. Аналитик может задать, например, такой вопрос: 1-го октября зиц-председатель конторы "Рога и Копыта" сбежал со всей кассой, так почему же 2-го октября мы выдали им кредит? Вопрос останется без ответа, если у нас нет третьей колонки, в которой было бы записано, что сообщение об исчезновении председателя поступило в базу только 3-го октября. А если сообщения могут опровергаться, то понадобится ещё и четвёртая колонка.

Четырёхвременные ряды? Тогда уж проще взять традиционную СУБД.

Именно так. Надо взять традиционную СУБД, и добавить в неё специальные средства записи во временные ряды, специальные индексы для их хранения и все операторы, описанные ранее. Иначе тупик.
Правда, если добавить именно в традиционную СУБД, то тоже тупик.

== Эволюция большой схемы РСУБД стоит слишком дорого ==

Чем больше система и чем дольше она живёт, тем сильнее меняется со временем. Если оборудование меняется в среднем раз в пять лет, то описывающая его схема за десять лет поменяется не на 200%, а на 200% плюс некоторый квадратичный от размера системы вклад тех данных, которые описывают взаимодействия агрегатов. Если складывать сырые данные в реляционные таблицы, то админинстрирование схемы и обновление приложений вслед за схемой становится дорогим удовольствием. Для TSDB цена изменчивости данных ниже, потому что в приложения можно заранее заложить нужную гибкость. В TSDB запрос может обращаться не к конкретному временному ряду, а, например, к группе всех рядов, имя которых соответствует некоторому регулярному выражению, или которые имеют какие-то заданные тэги из списка. Первая операция "причёсывания" --- grouping, она представит эту группу как один объединённый ряд. SQL такой возможности лишён: SQL-запрос содержит явные константные списки таблиц и колонок.

Менее заметна эволюция статистик. Поведение системы может радикально измениться за время накопления информации во временном ряду. Давным-давно у интернет-магазина были сто мелких поставщиков и единицы клиентов в сутки, сейчас один большой поставщик и сотни клиентов в сутки. SQL-запрос, который был бы оптимален для среднестатистических 50 поставщиков и 50 клиентов, не адекватен ни для одной из частей реальных рядов. Для TSDB это не является проблемой по очень простой причине --- там невозможно написать сложные запросы, а порядок джойнов задаётся разработчиком.

== SPARQL, schema-less, schema-last ==

Если мы не можем администировать классическую реляционную схему и использовать SQL, почему бы не перейти на SPARQL? Пусть каждый набор временных рядов, имеющий общую колонку моментов времени, будет представлен отдельным виртуальным RDF-графом, в котором моменты времени будут субъектами, имена рядов --- именами предикатов, а значения --- объектами. Тогда почти все операции с этими рядами можно будет очень удобно представить в виде выражений SPARQL, достаточно встроить дополнительные операторы. На это можно возразить, что в RDF субъектами могут быть только вершины, а не литералы, в т.ч. не литералы типа xsd:dateTime. Тем не менее, в SPARQL субъекты могут быть и литералами тоже. Для экспорта-импорта отметку времени 2014-10-07T10:45 вполне можно преобразовать во что-то вроде http://example.com/2014-10-07T10:45 . Метаданные о графах можно просто хранить в "соседних" графах. Обращения к метаданным будут примерно на треть дороже, чем если бы метаданных хранились в некоторых специальных таблицах, это называется "налог на RDF", но удобство перевешивает.

Если используется "толстая" СУБД, то разумно сложить в неё не только временные ряды и метаданные о них, но и все остальные сведения об описываемой системе. Практичными оказываются два варианта.

Schema-less хранение. Все эти сведения хранятся в виде классического RDF. Этот способ не требует от СУБД никакой функциональности сверх той, что уже понадобилась для работы с временными рядами, но приложение будет платить "налог на RDF".

Schema-last хранение. СУБД сама ищет повторяющиеся "реляционные" шаблоны в поступающих данных, и сама создаёт таблицы для более эффективного хранения "типовых" данных именно в этих таблицах, а не в RDF. "Необычная" часть данных продолжает храниться в стандартном RDF. Приложение всего этого не видит --- процесс преобразования данных полностью скрыт в ядре СУБД. Приложение отправляет SPARQL-запросы, а как прочитаются данные --- дело SPARQL-процессора. Этот способ требует от разработчиков СУБД изрядной хитрости, зато "налог на RDF" платится только на те "необычные" данные, которые ни в один шаблон не влезли.

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

== Если SPARQL "с расширениями" даёт большие возможности, вымрут ли классические TSDB? ==

Не вымрут. Мало того, что специализированные TSDB выполняют простые запросы быстрее, чем это в обозримом будущем сможет делать SPARQL-процессор, так они ещё и выполняют их за гарантированное время. Получив запрос, TSDB обрабатывает данные, относящиеся к очень маленькому промежутку времени, готовит маленький кусочек ответа, переходит к следующему маленькому промежутку. Быстро и предсказуемо. Некоторые TSDB могут даже непрерывно сообщать новые ответы по мере поступления новых данных. Уменьшая размеры кэшей, TSDB с небольшим объёмом данных можно запихать в довольно слабую аппаратуру. Производительный SPARQL-процессор так не сможет, потому что он будет обрабатывать ряды отрезками в десятки или сотни тысяч значений. Такая векторизация позволяет эффективно использовать память в десятки гигабайт и строить производительные кластеры, но по воробьям из этой пушки стреляется плохо. Вероятнее всего, в простых функциональных модулях ещё долго будет использоваться round-robin, в управлении агрегатами --- TSDB, и только на самом верхнем уровне будет встречаться SPARQL. С другой стороны, этот самый "верхний уровень" по мере развития аппаратуры распространяется из датацентров в карманы с сотовыми телефонами. Скажем, в проектируемом сейчас японцами частном космодроме отсутствует центр управления полётами --- все операции контролируются с одного ноутбука. Изучение "экзотики для богатых" сейчас --- надёжный способ остаться с "массовыми" заказами завтра.
Tags: rdbms, конспекты
Subscribe

  • Пора устраивать идиотоцид под видом демократии.

    Афиняне могли совершенно демократическим путём приговорить город, который им не сделал ничего плохого, к убийству всех тамошних мужчин и обращению в…

  • (no subject)

    Почему я не ношу зимой шапку: 1. Шапка не гарантирует 100% защиты от мороза 2. Я не доверяю российским шапкам 3. Шапки плохо протестированы 4.…

  • Как я из пионера-ленинца стал антикоммунистом. Часть 2/2.

    Когда в Новосибирской области открылось областное отделение РИКО Госплана, оно осело не в облсовете или ещё где в центре города, а в нашей "деревне…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 9 comments