Интерпретатор байт-кода регулярных выражений: поиск иголок в стогах сена сеанса
Здесь, в Badoo, каждый день происходит 17 миллиардов событий, миллионы пользовательских сессий и огромное количество виртуальных свиданий. Каждое событие тщательно анонимизируется и сохраняется в реляционных базах данных для последующего анализа с использованием SQL и языков, подобных SQL.
Современные распределенные базы данных, содержащие десятки терабайт данных, - настоящее чудо инженерного гения. Однако SQL как отражение реляционной алгебры в большинстве своих стандартных версий еще не позволяет формулировать запросы в терминах упорядоченных кортежей.
В этой заключительной части цикла статей о виртуальных машинах (Часть 1: Собственные интерпретаторы байт-кода; Часть 2: Оптимизация интерпретаторов байт-кода) я собираюсь изучить альтернативный подход к поиску интересующих сеансов, а именно механизм регулярных выражений (Сопоставление поросят), определяемый последовательностями событий.
Виртуальная машина, байт-код и компилятор предоставляются бесплатно!
О мероприятиях и сессиях
Допустим, у нас есть хранилище данных, позволяющее быстро извлекать события, составляющие пользовательские сеансы.
Мы хотим найти сеансы на основе следующих запросов:
- «Подсчитать общее количество сеансов, в которых есть указанная подпоследовательность событий»;
- «Найти части сеанса, описанные указанным шаблоном»;
- «Вернуть ту часть сеанса, которая произошла после указанного шаблона»;
- или «посчитайте, сколько сеансов достигло определенных частей шаблона».
Это полезно для всех видов анализа: поиска подозрительных сессий, анализа воронки и т. Д.
Желаемые подпоследовательности нужно как-то описать. В самом простом виде эта задача аналогична поиску подстроки в тексте; но более мощный инструмент, а именно регулярные выражения, предпочтительнее. Современные реализации обработчиков регулярных выражений в основном используют (да, вы уже догадались!) Виртуальные машины.
Создание небольших виртуальных машин, которые сопоставляют пользовательские сеансы с регулярными выражениями, - это то, что мы собираемся сделать ниже. Но давайте начнем с уточнения некоторых определений.
Событие состоит из типа события, времени, контекста и набора атрибутов, специфичных для каждого из соответствующих типов событий.
Тип и контекст каждого события - целые числа из заранее определенных списков. Если с типом события все ясно, то контекстом будет, например, номер экрана, на котором произошло указанное событие.
атрибут события также является целым числом, значение которого определяется типом события. У данного события может не быть каких-либо атрибутов вовсе или их может быть несколько.
Сеанс - это последовательность событий, отсортированная по времени.
Хорошо, давай продолжим! На западном фронте все тихо, так что давайте действовать.
Базовое сравнение последовательности событий
Эту виртуальную машину отличает то, что она пассивна в отношении входящих событий. Мы не хотим сохранять в памяти весь сеанс и позволять виртуальной машине самостоятельно переходить от одного события к другому. Вместо этого мы собираемся отправлять события из сеанса на виртуальную машину одно за другим.
Давайте сначала напишем функции интерфейса:
matcher *matcher_create(uint8_t *bytecode); match_result matcher_accept(matcher *m, uint32_t event); void matcher_destroy(matcher *matcher);
Если с функциями matcher_create и matcher_destroy все понятно, то стоит прокомментировать matcher_accept. Функция matcher_accept получает экземпляр виртуальной машины и следующее событие (32-битное: 16-битное для типа события и 16-битное для контекста) и возвращает код, который определяет, что код пользователя должен делать дальше:
typedef enum match_result {
// request the next event
MATCH_NEXT,
// regex matched, done with the session
MATCH_OK,
// regex did not match, done with the sessionне подавать
MATCH_FAIL,
// internal error
MATCH_ERROR,
} match_result;
Коды операций для виртуальной машины:
typedef enum matcher_opcode {
//zero opcode, stops execution with an error
OP_ABORT,
// check current event’s type (arg — the type to check)
OP_NAME,
// check current event context (arg — the context to check)
OP_SCREEN,
// request a next event
OP_NEXT,
// successfully matched the session
OP_MATCH,
} matcher_opcode;
Основной цикл виртуальной машины:
match_result matcher_accept(matcher *m, uint32_t next_event)
{
#define NEXT_OP() \
(*m->ip++)
#define NEXT_ARG() \
((void)(m->ip += 2), (m->ip[-2] << 8) + m->ip[-1])
for (;;) {
uint8_t instruction = NEXT_OP();
switch (instruction) {
case OP_ABORT:{
return MATCH_ERROR;
}
case OP_NAME:{
uint16_t name = NEXT_ARG();
if (event_name(next_event) != name)
return MATCH_FAIL;
break;
}
case OP_SCREEN:{
uint16_t screen = NEXT_ARG();
if (event_screen(next_event) != screen)
return MATCH_FAIL;
break;
}
case OP_NEXT:{
return MATCH_NEXT;
}
case OP_MATCH:{
return MATCH_OK;
}
default:{
return MATCH_ERROR;
}
}
}
#undef NEXT_OP
#undef NEXT_ARG
}
В этой простой версии наша виртуальная машина последовательно сравнивает шаблон, описанный байт-кодом, с входящими событиями. В этой форме это просто довольно длинное сравнение префиксов, относящихся к двум строкам: желаемому шаблону и входящей строке.
Префиксы - это одно, но нам нужно уметь идентифицировать желаемые шаблоны не только в начале, но и в любой момент сеанса. Наивным решением было бы повторно запускать сравнения для каждого события сеанса. Однако это будет означать, что каждое событие будет просматриваться несколько раз, а также потребуется огромное количество алгоритмических вычислений.
Пример из первой статьи этой серии использует отслеживание с возвратом для имитации повторных сравнений. Код в примере, конечно, выглядит лучше, чем приведенный здесь, но это не означает, что проблема исчезла: каждое событие нужно проверять несколько раз.
И это не то, с чем можно жить.
Я, я и я снова
Давайте вернемся к тому, что мы пытаемся сделать: нам нужно сравнить шаблон с входящими событиями, начиная новое сравнение для каждого из событий. Так почему бы не сделать именно это? Позвольте виртуальной машине проходить входящие события в несколько потоков!
В конце концов, это то, что нам нужно для создания новой сущности: поток. Каждый поток хранит единственный указатель на текущую инструкцию:
typedef struct matcher_thread {
uint8_t *ip;
} matcher_thread;
Естественно, мы не собираемся хранить явный указатель внутри самой виртуальной машины. Его заменят два списка тем (подробнее об этом чуть позже):
typedef struct matcher {
uint8_t *bytecode;
/* Threads to be processed using the current event */
matcher_thread current_threads[MAX_THREAD_NUM];
uint8_t current_thread_num;
/* Threads to be processed using the event to follow */
matcher_thread next_threads[MAX_THREAD_NUM];
uint8_t next_thread_num;
} matcher;
Вот обновленный основной цикл:
match_result matcher_accept(matcher *m, uint32_t next_event)
{
#define NEXT_OP(thread) \
(*(thread).ip++)
#define NEXT_ARG(thread) \
((void)((thread).ip += 2), ((thread).ip[-2] << 8) + (thread).ip[-1])
/* Every new event launches a new thread from the first bytecode instruction */
add_current_thread(m, initial_thread(m));
// On every event we check every thread
for (size_t thread_i = 0; thread_i < m->current_thread_num; thread_i++ ) {
matcher_thread current_thread = m->current_threads[thread_i];
bool thread_done = false;
while (!thread_done) {
uint8_t instruction = NEXT_OP(current_thread);
switch (instruction) {
case OP_ABORT:{
return MATCH_ERROR;
}
case OP_NAME:{
uint16_t name = NEXT_ARG(current_thread);
// if the current event does not correspond to a template described by the thread, the thread will just not make into the next_threads list
if (event_name(next_event) != name)
thread_done = true;
break;
}
case OP_SCREEN:{
uint16_t screen = NEXT_ARG(current_thread);
if (event_screen(next_event) != screen)
thread_done = true;
break;
}
case OP_NEXT:{
// a thread requested the next event, i.e. it must make it to the next_threads list
// next_threads
add_next_thread(m, current_thread);
thread_done = true;
break;
}
case OP_MATCH:{
return MATCH_OK;
}
default:{
return MATCH_ERROR;
}
}
}
}
/* Swap the current and next thread lists */
swap_current_and_next(m);
return MATCH_NEXT;
#undef NEXT_OP
#undef NEXT_ARG
}
Для каждого полученного события мы сначала добавляем новый поток в список current_threads, который проверяет шаблон с самого начала. Затем мы начинаем работать со списком current_threads, выполняя инструкции, следующие за указателем для каждого из потоков.
Если мы сталкиваемся с инструкцией NEXT, то поток перемещается в список next_threads, то есть ожидает получения следующего события.
Если шаблон потока не соответствует полученному событию, то рассматриваемый поток просто не добавляется в список next_threads.
Инструкция MATCH немедленно завершает работу функции, отправляя уведомление посредством кода возврата о том, что шаблон соответствует сеансу.
Пройдя наш путь через список потоков, списки текущих и следующих потоков меняются местами.
Вот и все. Можно сказать, что мы буквально делаем то, что хотели: мы одновременно проверяем несколько шаблонов, запускаем один новый процесс сравнения для каждого из событий сеанса.
Несколько личностей и ветвление в шаблонах
Конечно, полезно искать шаблон, который описывает линейную последовательность событий, но мы стремимся получить полноценные регулярные выражения. И потоки, которые мы создали на предыдущем этапе, нам и здесь пригодятся.
Допустим, мы хотим получить последовательность из двух или трех интересующих событий, что-то вроде регулярного выражения, основанного на строках: «a? Bc». В этой последовательности символ «а» не обязателен.
Как это можно выразить в байт-коде? Легкий! Мы можем запустить два потока: по одному для каждого случая, то есть один с символом «a» и один без него. Для этого мы вводим дополнительную инструкцию (в форме SPLIT addr1, addr2), которая запускает два потока с заданных адресов. Помимо SPLIT нам также понадобится JUMP, который просто продолжает выполнение инструкции, указанной в прямом аргументе:
typedef enum matcher_opcode {
OP_ABORT,
OP_NAME,
OP_SCREEN,
OP_NEXT,
// jump to an address specified
OP_JUMP,
// launch 2 new threads from both given addresses
OP_SPLIT,
OP_MATCH,
// not an op
OP_NUMBER_OF_OPS,
} matcher_opcode;
Сам цикл и другие инструкции не меняются, мы просто вводим два новых обработчика:
// ...
case OP_JUMP:{
uint16_t offset = NEXT_ARG(current_thread);
add_current_thread(m, create_thread(m, offset));
break;
}
case OP_SPLIT:{
uint16_t left_offset = NEXT_ARG(current_thread);
uint16_t right_offset = NEXT_ARG(current_thread);
add_current_thread(m, create_thread(m, left_offset));
add_current_thread(m, create_thread(m, right_offset));
break;
}
// ...
Обратите внимание, что инструкции добавляют потоки в текущий список, то есть продолжают свою работу в контексте текущего события. Поток, в зависимости от того, какое ветвление произошло, не добавляется в список последующих потоков.
Самым удивительным в этой виртуальной машине для регулярных выражений является тот факт, что наших потоков и этой пары инструкций достаточно для выражения почти всех общепринятых конструкций при сравнении строк.
Регулярные выражения, определенные для событий
Теперь, когда у нас есть подходящая виртуальная машина и инструменты для нее, мы можем обратиться к фактическому синтаксису наших регулярных выражений.
Написание кодов операций для более серьезных программ вручную быстро утомляет. В прошлый раз я не делал полноценного парсера, но пользователь true-grue на примере мини-языка PigletC продемонстрировал возможности своей библиотеки raddsl. Я был настолько впечатлен краткостью этого кода, что с помощью raddsl я написал небольшой, 100–200 строк кода, компилятор регулярных выражений на Python. Компилятор и инструкция по его использованию доступны на GitHub. Результат работы компилятора на языке ассемблера понимает утилита, которая читает два файла (программу для виртуальной машины и список событий сеанса для целей тестирования).
Для начала ограничимся типом и контекстом события. Мы обозначаем тип события одной цифрой: если нам нужно указать контекст, мы делаем это с помощью двоеточия. Вот очень простой пример:
> python regexp/regexp.py “13” # event type 13 NEXT NAME 13 MATCH
А теперь пример с контекстом:
python regexp/regexp.py “13:12” # event type 13, context 12 NEXT NAME 13 SCREEN 12 MATCH
Последующие события необходимо каким-то образом разделить (например, пробелами):
> python regexp/regexp.py “13 11 10:9” 08:40:52 NEXT NAME 13 NEXT NAME 11 NEXT NAME 10 SCREEN 9 MATCH
Более интересный шаблон:
> python regexp/regexp.py “12|13” SPLIT L0 L1 L0: NEXT NAME 12 JUMP L2 L1: NEXT NAME 13 L2: MATCH
Обратите внимание на строки, заканчивающиеся двоеточием. Это ярлыки. Инструкция SPLIT создает два потока, которые продолжают выполняться с меток L0 и L1, в то время как инструкция JUMP в конце первой выполняемой ветви просто перемещается в конец ветвления.
Вы можете переключаться между более длинными цепочками выражений, группируя подпоследовательности вместе в скобках:
> python regexp/regexp.py “(1 2 3)|4” SPLIT L0 L1 L0: NEXT NAME 1 NEXT NAME 2 NEXT NAME 3 JUMP L2 L1: NEXT NAME 4 L2: MATCH
Неуказанное событие отмечено точкой:
> python regexp/regexp.py “. 1” NEXT NEXT NAME 1 MATCH
Если мы хотим указать, что подпоследовательность необязательна, мы ставим за ней вопросительный знак:
> python regexp/regexp.py “1 2 3? 4” NEXT NAME 1 NEXT NAME 2 SPLIT L0 L1 L0: NEXT NAME 3 L1: NEXT NAME 4 MATCH
Само собой разумеется, что также поддерживаются обычные многократные повторения в регулярных выражениях (плюс или звездочка):
> python regexp/regexp.py “1+ 2” L0: NEXT NAME 1 SPLIT L0 L1 L1: NEXT NAME 2 MATCH
В этом случае мы просто запускаем инструкцию SPLIT несколько раз, запуская новые потоки для каждой итерации.
Аналогично и со звездочкой:
> python regexp/regexp.py “1* 2” L0: SPLIT L1 L2 L1: NEXT NAME 1 JUMP L0 L2: NEXT NAME 2 MATCH
Будущие перспективы
Другие описанные расширения виртуальной машины также могут оказаться полезными.
Например, его можно легко расширить с помощью теста атрибута события. В случае реальной системы я предполагаю использовать синтаксис типа «1: 2 {3: 4, 5:› 3} », что означает следующее: событие 1 в контексте 2 с атрибутом 3 значения 4 и атрибутом значение 5 больше 3. В этом случае атрибуты можно просто отправить в функцию matcher_accept с помощью массива.
Если мы также отправим временной интервал между событиями в matcher_accept, тогда мы можем добавить синтаксис к языку, который позволяет время проходить между событиями: «1 mindelta (120) 2» - что будет означать следующее: событие 1, затем минимальный интервал 120 секунд, затем событие 2. В сочетании с сохранением подпоследовательностей это позволяет нам собирать информацию о поведении пользователя между двумя подпоследовательностями событий.
Другие полезные вещи, которые относительно легко добавить: сохранение подпоследовательностей регулярных выражений, различие между жадными и обычными операторами, звездочкой и плюсом и т. Д. Теоретически наша виртуальная машина представляет собой недетерминированный конечный автомат, т.е. реализовать.
Заключение
Наша система разрабатывается для быстрых пользовательских интерфейсов, поэтому движок для хранения сессий был написан самостоятельно и оптимизирован, в частности, с целью прочесывания всех сессий. Все миллиарды событий, разбитые на сеансы, проверяются на соответствие шаблонам в течение нескольких секунд на одном сервере.
Если в вашем случае скорость менее критична, вы можете настроить аналогичную систему в виде расширения какой-либо более стандартной системы для хранения данных по образцу традиционной реляционной базы данных или распределенной файловой системы.
По этому поводу в последних версиях стандарта SQL уже есть возможность, аналогичная описанной в статье, а в некоторых базах данных (Oracle и Vertica) она уже реализована. В свою очередь Яндекс ClickHouse реализует собственный SQL-подобный язык, а также имеет похожие возможности.
Отвлекаясь от темы событий и регулярных выражений, хочу повторить, что у виртуальных машин приложение гораздо шире, чем может показаться на первый взгляд. Этот метод подходит и широко применяется во всех случаях, когда необходимо четко разделить примитивы, которые понимает системный движок, и подсистему, ориентированную на пользователя, например, какой-то DSL или язык программирования.
На этом завершается эта серия статей, посвященных различным приложениям, интерпретаторам байт-кода и виртуальным машинам. Я надеюсь, что вам понравилось читать статьи, и, разумеется, я буду рад ответить на любые ваши вопросы по теме.
Неофициальная библиография
Интерпретаторы байт-кода для языков программирования представляют особый интерес, и литературы по этой теме не так много. Лично мне понравился Иэн Крейг под названием «Виртуальные машины», хотя он не столько описывает реализацию интерпретаторов, сколько описывает абстрактные машины, математические модели, лежащие в основе различных языков программирования.
Для более широкой перспективы существует еще одна книга о виртуальных машинах под названием Виртуальные машины: универсальные платформы для систем и процессов Джеймса Смита. Это введение в различные области применения виртуализации, включая виртуализацию языков, процессов и общей компьютерной архитектуры.
Практические аспекты разработки движков для регулярных выражений редко обсуждаются в популярной литературе по компиляторам. Piglet Matcher и пример из первой статьи основаны на идеях из замечательной серии статей Расса Кокса, одного из разработчиков движка Google RE2.
Теория регулярных выражений изложена во всех академических учебниках по компиляторам. Принято ссылаться на знаменитую Книгу дракона, но я бы рекомендовал начать со ссылок, приведенных выше.
Работая над этой статьей, я впервые использовал интересную систему под названием raddsl для быстрой разработки компиляторов на Python. Его написал пользователь true-grue (спасибо, Петр!). На него стоит взглянуть, если вы хотите создать язык прототипов или быстро разработать DSL.
