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

В статье я опишу идею хранения в достаточно известной колоночной базе данных 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 (historical 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]

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

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 вам поможет