KDB

кдвп


Привет, Хабр !


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


Зачем?

Хранение Time Series


Если у вас есть ежесекундные колебания курса валют на последние 20 лет, то реляционная база данных будет не самым быстрым и эффективным решением по хранению и обработке накопленного (т.е. чуть больше чем 120×10^9 строк для 200 валют). В этом случае логичнее всего использовать шуструю колоночную базу данных, а значит KDB нам поможет.


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


Вычисления


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


Production ready


Решив все прямые технические задачи, у вас встанут следующие:


  • Backup
  • Репликация (+ active-active работа сервисов)
  • Шардинг
  • Поддержка основных технологий и языков программирования (Java, .Net, R и тд)


Как оно работает на одном сервере?

Физические данные в KDB хранятся с минимальными издержками. Так, колонка с целыми числами — это просто последовательность целых чисел, которая хранится в одном файле на диске.


Физическое хранение


Как уже говорилось выше, KDB — колоночная база данных, т.е. каждая колонка хранится отдельно. В реальности, колонка — это просто отдельный файл, не более чем. То есть таблица t с колонками a, b, c и d будет представлять на диске просто папку «t», в которой есть четыре файла — a, b, c и d. И плюс небольшой файл с метаданными. Если надо скопировать таблицу — вы можете просто скопировать файлы (и заставить сгенерить метаданные). Если надо перенести часть данных на новый сервер — просто скопируйте файлы.


Как любой читатель понимает, хранить миллионы объектов в одном файле крайне неэффективно. В этом случае даже задача пересортировки будет решаться уже сложно и дорого (ведь нельзя всё взять в память — её столько нет). Отсюда в KDB (как и в каждой приличной колоночной базой данных) вся таблица изначально делится на разделы (partitions), см. документацию. Разделы назначаются на всю базу данных и чаще всего являются просто датой.


Последнее уже чуть усложняет файловую структуру. Если у вас две таблицы (t1 и t2), и у них есть колонка date (по ней будем разделять данные по папкам) то на диске будет следующая структура:


 \ 2017.01.01
    \ t1
    \ t2
 \ 2017.01.02
    \ t1
    \ t2


То есть в папке с датой находятся папки с таблицами, в них находятся файлы с колонками.


На диске данные всегда хранятся без возможности изменения или удаления. Вы можете только дописать еще данных. Т.е. если вам надо таки обновить или выкинуть данные для даты d — забираете их все в память (select from t where date = d), делаете все необходимые операции, сохраняете за дату d1, а потом меняете имена папок на диске.


После того, как мы научились разделять файлы на диске, можно еще оптимизировать их хранение с помощью сжатия (например, gzip или google snappy). Эффективная колоночная база обязана уметь делать это самостоятельно, ибо иначе сжимать придется или файловой системой (т.е. хранить несжатые данные в кеше оперативной памяти), или не сжимать данные вообще (и увеличить IO) или сжимать данные уже в слое приложения (и потерять возможность сжатия соседних строк).


Кроме эффективного хранения данных, KDB дает возможность быстро читать данные в память. Для этого таблица должна быть упорядоченная, то есть одно на выбор:


  • Данные в каждом разделе хранятся нетронутыми. То есть, если у нас есть таблица t с колонками date (partition), а также с b, c и d, то для выполнения запроса select v from t where date=2017.01.01 and k=12 придется загрузить в память вcе данные из колонок k и v за определенную дату. Или, говоря языком реляционных баз данных, придется сделать index scan.
  • Одна из колонок будет отсортированной. Если продолжить пример выше и отсортировать данные по колонке k, то запрос select v from t where date=2017.01.01 and k=12 будет работать уже намного быстрее — KDB загрузит только часть данных в память, найдет он их за логарифм. Что важно — от этого атрибута таблица не разрастется на диске, т.е. никаких дополнительных данных хранить не потребуется.
  • Одна из колонок будет уникальной. В этом случае KDB дополнительно создаст хеш-таблицу для значений, что позволит сделать index seek в примере select v from t where date=2017.01.01 and k=12. Очевидно, в этом случае хеш таблица хранится рядом и отнимает драгоценное место.
  • Несколько колонок сгруппированы. По сути это примерно то же самое, что и primary key index в реляционных базах данных. В такой таблице кортеж из одинаковых значений колонок хранится вместе, более того — отдельно хранится хеш таблица, по которой можно сразу обратиться к нужным значением. То есть, для запросов вида select v from t where date=2017.01.01 and k=12 будет происходить index seek, и KDB мгновенно будет прыгать в нужное значение на диске. Однако запросы вида select v from t where date=2017.01.01 and k<12 and k > 10 будут делать index scan, так как хеш таблица не будет сортировать данные. Однако задача с легкостью решается с помощью дополнительной таблицы и отсортированной колонкой.


RDB и HDB


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


  • Все исторические данные хранятся в HDB (hisrotical DB). Они хранятся сжато и упорядоченно на диске, их можно быстро вычитывать в память и анализировать.
  • Все данные за последний день хранятся в RDB (realtime DB), задача которой — как можно быстрее забрать данные у приложения. В этом случае числа могут храниться в оперативной памяти (последний день из 20 лет вряд ли займет много места), что позволит быстро к ним обращаться даже при условии, что они не отсортированы. Если же поток данных достаточно большой, естественно можно убирать числа из оперативной памяти в момент их сброса на диск.


Если совсем поверхностно, то алгоритм работы RDB следующий:


  1. Забираем данные из приложения
  2. Раз в N секунд/минут — сбрасываем данные на диск и вызываем пользовательскую функцию, в которую передаем сброшенное. Она:
    2.1. Или дописывает свежепришедшие данные к объекту в памяти (фильтруя, агрегируя, что угодно)
    2.2. Не делает ничего (ведь далеко не всегда нам нужен текущий день для анализа истории)
  3. В конце дня — забираем все накопленные в RDB данные, сортируем/группируем их и сбрасываем в HDB


Q

Рассказывая про KDB нельзя не упомянуть про язык Q, на котором строятся все запросы (и все функции) в KDB. Если с функциями выборки более менее всё ясно (см. пример выше — select v from t where date=2017.01.01 and k=12), то вот остальные вещи выглядят несколько необычнее.


Идею Q можно ассоциировать с пословицей краткость — сестра таланта.


Итак, создаем новую переменную:


tv: select v from t where date=2017.01.01 and k=12;


Упростим запрос — нам не нужен and для перечисления условий:


tv: select v from t where date=2017.01.01,k=12;


Добавим группировку и агрегацию:


tv: select count by v from t where date=2017.01.01,k=12;


переименуем колонку:


tv: select c: count by v from t where date=2017.01.01,k=12;


Вернемся к первому запросу


tv: select v from t where date=2017.01.01,k=12;


И переименуем колонку


tv: select v from t where date=2017.01.01,k=12;
tv: `v1 xcol tv;


Отсортируем колонку:


tv: select v from t where date=2017.01.01,k=12;
tv: `v1 xcol tv;
tv: `v1 xasc tv;


Или, что удобнее — объединим запрос в более привычную одну строчку:


tv: `v1 xasc `v1 xcol select v from t where date=2017.01.01,k=12;


Обернем наш запрос в функцию (символ ':' в начале выражения означает return, а не присваивание, как было в примерах выше):


f: {[]
    tv: `v1 xasc `v1 xcol select v from t where date=2017.01.01,k=12;
    :tv;
}


Добавим параметры:


f: {[i_d, i_k]
    tv: `v1 xasc `v1 xcol select v from t where date=i_d,k=i_k;
    :tv;
}


И вызовем функцию (в конце не будем писать »;» — это даст нам вывод на консоль, как полезный side effect):


f: {[i_d, i_k]
    tv: `v1 xasc `v1 xcol select v from t where date=i_d,k=i_k;
    :tv;
};

f[2017.01.01, 12]


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


f: {[d]
    i_d: d[`date];
    i_k: d[`key];

    : `v1 xasc `v1 xcol select v from t where date=i_d,k=i_k;
};

f[(`date`key)!(2017.01.01;12)]


В последнем примере мы сделали сразу нескольких вещей:


  1. Объявили словарь с помощью выражения (`date`key)!(2017.01.01;12)
  2. Передали словарь в функцию
  3. Прочитали переменные из словаря i_d: d[`date];


Дальше — добавим бросание ошибки для случая, когда данных нет:


f: {[d]
    i_d: d[`date];
    i_k: d[`key];

    r: `v1 xasc `v1 xcol select v from t where date=i_d,k=i_k;

    $[0 = count r;'`no_data;:r];
};

f[(`date`key)!(2017.01.01;12)]


Итак, сейчас наша функция бросит исключение со словами «no_data» для случая, когда в таблице нет данных по нашему запросу.
Конструкция $[1=0;`true;`false] — условный переход, в котором сначала идет условие, потом выражение, которое следует выполнить, если условие истинно. В конце — блок else. Однако в реальности это скорее pattern matching, чем if, ибо допустима и следующая конструкция: $[a=0;`0; a=1;`2; `unknown]. То есть на всех нечетных позициях (кроме последней) стоят условия, на всех четных — то, что надо выполнить. И в конце — блок else.


Как видно в примерах, язык логичный (хоть и лаконичный). В Q есть:


  • Лямбды
  • Условные переходы
  • Циклы
  • Специальные инструкции для объединения таблиц (в том числе сложные join’ы, pivot таблицы)
  • Возможность добавления модулей (например — чтобы заодно посчитать на GPU аналитику)


И в заключении

  • Если у вас идет работа с большим объемом данных — KDB вам поможет
  • Если у вас есть задачи по анализу time series — KDB вам поможет
  • Если у вас есть задача по быстрой записи (и последующему анализу) большого потока данных — KDB вам поможет

© Habrahabr.ru