Меня зовут Сигида Алексей, я старший архитектор по развитию технологий CVM (Customer Value Management) в компании Мегафон. Много лет решения о том, что показать клиенту, у нас принимал Teradata RTIM (Real-Time Interaction Manager) - движок real-time маркетинга. Если вы когда-нибудь получали смс-сообщение от Мегафон или открывали личный кабинет, то с большой долей вероятности предложение было подобрано этой системой. Вы заходите на сайт или в приложение, и за миллисекунды решается, какое предложение показать.

Логика выбора описывается деревьями принятия решений: запрос проходит по веткам дерева, а условия переходов в узлах - критерии - определяют, к какому сегменту отнести клиента и какое предложение ему подобрать.

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

Переписать логику оркестрации - задача понятная. Но внутри системы жили тысячи правил (критериев отбора аудитории), написанных на собственном языке выражений Teradata. Вот с ними всё оказалось интереснее. Эта статья о том, как AST помог перенести их без ручного переписывания в нашу новую систему MegaRITM.

Что такое критерии в RTIM

Критерий - это условие, которым дерево принятий решений проверяет клиента: выполнилось - запрос идет по одной ветке, не выполнилось - по другой. Результат вычисления критерия - всегда true или false. Писались они на том самом языке выражений Teradata: синтаксис Java-подобный, есть операторы &&, ||, функции вроде get(), filter(), count(), set(). Выглядит это примерно так:

set("filteredCart", filter(get("Account.cart"), "item", "soda")) &&
count(filteredCart) > 0 &&
set("chips", filter(get("Account.cart"), "item", "chips")) &&
value(get(filteredCart, 0, "price")) - value(get(filteredCart, 0, "discount")) >
value(get(chips, 0, "price")) - value(get(chips, 0, "discount"))

Это пример из документации Teradata RTIM: клиент подходит под акцию на газировку, если газировка в корзине стоит дороже чипсов (с учетом скидки). В продакшне выражения бывали куда сложнее: несколько вложенных filter, цепочки set, паттерны по регулярным выражениям. Критериев у нас было несколько тысяч, и почти все они содержали такие выражения.

Три способа это решить

Для начала один важный факт, без которого сравнение вариантов не имеет смысла. Парсер текстовых выражений нужен не только для разовой миграции архива. Бизнес-пользователи и после переезда продолжают писать критерии тем же текстовым синтаксисом. Компонент “текст -> <вариант реализации ниже>” - это часть постоянной архитектуры новой системы, а миграция тысяч старых критериев - просто первый прогон этого компонента по накопленным данным. Кроме того, в новой системе нам в любом случае нужно было реализовать все функции, которые используются в критериях.

Осознав это, мы поняли: мы выбираем не скрипт для одноразового переезда, а «сердце» нового движка, которому предстоит работать годами. Любое решение должно было учитывать, что бизнес-пользователи вносят правки десятки раз в день. Итак, задача звучала так: взять выражения-критерии на языке Teradata и научить систему на лету проходить по дереву принятия решений, выполняя проверки. Как к этому подступиться? У нас было три пути.

Ручной перевод. Берешь каждое выражение, читаешь, пишешь эквивалентное выражение на Go, компилируешь. На выходе получаем сервис, который очень быстро работает. Но что делать, когда структура дерева или сами критерии будут меняться? Снова писать код? А ведь в бизнесе это происходит несколько раз в день.

Поиск и замена через регулярные выражения или шаблоны. А что если, при каждом изменении дерева или критериев динамически генерировать код по шаблонам или с использованием регулярок? Кажется, задача достаточно сложная. Да, мы решим проблему с частыми ручными правками, но пересборка сервиса все равно нужна. И проблема не в самом процессе CI/CD, а в том, что каждая сборка занимает время. При высокой частоте изменений от бизнеса может сформироваться очередь из сборок, из-за чего пострадает time-to-market.

Разбор через AST. Распарсить выражение критерия в дерево, обойти дерево и собрать структуру в нашем формате. Больше кода на старте, зато надежно и предсказуемо. Мы выбрали этот путь, - тем более что реализация функций, как сказано выше, требовалась в любом случае. Таким образом, мы можем хранить структуру деревьев принятия решений и AST в памяти, а при изменении просто их подменять. При каждом новом вызове дерева у нас всегда будут актуальные данные. Получается, что критерии и в старой, и в новой системе - это не скомпилированный код, а данные. В нашем случае Go-код - это интерпретатор, который при каждом запросе обходит JSON-дерево критерия и вычисляет результат.

“А почему не взять готовое решение?” - закономерный вопрос. И у него два ответа.

Во-первых, готовые движки выражений (CEL, expr, JSONLogic) решают задачу целиком, но только если вы вольны выбрать синтаксис. Мы - не вольны: синтаксис навязан Teradata, на нём написаны тысячи существующих критериев, и бизнес-пользователи продолжают писать на нём новые. Переучивать людей ради удобства инструмента значило бы поменять местами цель и средство.

Во-вторых, есть генераторы парсеров вроде ANTLR: описываешь грамматику, получаешь парсер. Для языка из пары десятков функций и нескольких операторов это почти паритет с ручным рекурсивным спуском. Генератор экономит день-два на старте, но приносит зависимость, дополнительный шаг кодогенерации в сборке и типовые сообщения об ошибках, на которые сложно влиять. А ведь наши ошибки читают не разработчики, и внятное “что и где не так” нам важнее (к этому ещё вернёмся). Рукописный рекурсивный спуск для грамматики такого размера - не велосипедостроение. Будь в языке полсотни конструкций, выбор был бы другим.

Почему именно AST

AST (Abstract Syntax Tree, абстрактное синтаксическое дерево) - это не экзотика из учебника по компиляторам. Это стандартный способ работы с любым структурированным языком: браузер строит DOM из HTML, интерпретатор Python строит AST из исходника перед выполнением, линтеры анализируют код именно через дерево.

Идея простая: текст выражения - это последовательность символов, в которой скрыта структура. AST делает эту структуру явной. Вместо строки a && b > 2 у вас узел “логическое И” с двумя дочерними узлами: “переменная a” и “сравнение b > 2”. С деревом работать несравнимо проще, чем со строкой.

Главное преимущество - корректность по построению. Регулярное выражение не знает, внутри ли оно скобок или снаружи. Дерево знает всегда: каждый узел знает своих потомков, и обход дерева всегда корректен с точки зрения приоритетов операций и вложенности. Второе преимущество - расширяемость. Когда бизнес приходит с новой функцией, нужно добавить один обработчик узла, а не переписывать набор регулярок или шаблонов. Третье - тестируемость. Можно написать тест на каждый тип узла отдельно, не прогоняя сквозные тесты через весь парсер.

Как выглядит наше дерево

Мы намеренно сделали структуру узла минимальной:

{
  "type": "function",
  "value": "filter",
  "args": [
    {
      "type": "function",
      "value": "get",
      "args": [
        { "type": "string", "value": "Account.cart", "args": [] }
      ]
    },
    { "type": "string", "value": "item", "args": [] },
    { "type": "string", "value": "soda", "args": [] }
  ]
}

Всего три поля: тип узла, значение и список дочерних узлов. Типов пять: function, num, string, logical, arithmetic. Этого оказалось достаточно, чтобы представить весь язык RTIM.

Дочерних узлов может быть сколько угодно, от нуля до N. У литерала список пуст, у функции их столько, сколько аргументов, а цепочка a && b && c - это один узел && с тремя потомками, а не лесенка вложенных пар. Плоские цепочки удобнее и для интерпретатора (один узел вместо каскада), и для глаз при отладке JSON. В Go этому JSON соответствует одна плоская структура:

type Node struct {
    Type  string `json:"type"`
    Value string `json:"value"`
    Args  []Node `json:"args"`
}

Никакой иерархии типов, никаких интерфейсов на каждый вид узла - один struct на всё дерево, а обработка веток по типу - это switch на Type внутри обходчика. Цена такого упрощения в том, что компилятор Go не проверит за нас структурные правила: например, что у сравнения > ровно два потомка, а у num их нет вовсе. Эти проверки берёт на себя валидатор на входе (о нём ниже) и тесты по каждому типу узла.

Минимальность - это ещё и про рантайм: дерево обходится на каждом запросе, и чем дешевле обработка одного узла, тем быстрее вычисление критерия. Разделение типов не случайное. Логические logical (&&, ||, >, <, ==) - возвращают булевое значение. Арифметические arithmetic (+, -, *, /) - возвращают число. Интерпретатор использует это при проверке типов в рантайме. Список допустимых функций фиксированный и известен заранее. Если парсер встретил вызов функции, которой нет в списке, он сразу выдаст ошибка. Голый идентификатор без скобок - это переменная, объявленная через set(), как filteredCart в примере выше.

Как это работает на практике

Весь процесс состоит из трех шагов.

Шаг 1: парсинг. Берем строку с выражением Teradata, прогоняем через токенизатор (разбивает строку на токены: ключевые слова, операторы, литералы), потом через парсер (строит дерево по грамматике).

Парсер живёт не в Go-сервисе, а в Python-бэкенде, где бизнес-пользователи создают и редактируют критерии: Go только интерпретирует готовые деревья. Сам парсер - рекурсивный нисходящий. Каждая функция соответствует правилу грамматики: parse_logical_or, parse_comparison, parse_term. Рекурсия, естественно, отражает вложенность выражений, а приоритет операторов задаётся самой цепочкой вызовов: чем ниже приоритет оператора, тем выше в цепочке функция, которая его разбирает.

# Узел дерева - словарь {'type', 'value', 'args'}, как в JSON выше.
# Каждая функция получает индекс текущего токена в списке tokens и возвращает
# пару (узел, индекс первого неразобранного токена).
# Пример упрощён для наглядности: в реальном парсере больше проверок
# синтаксиса и уровней приоритета.

FUNC_LIST = {'get', 'set', 'filter', 'count', 'value'}

# точка входа - уровень оператора с самым низким приоритетом
def parse_expression(index: int) -> tuple[dict, int]:
    return parse_logical_or(index)

# каждый уровень приоритета устроен одинаково: разобрать операнд уровнем ниже
# и, пока идёт один и тот же оператор, собирать операнды в args одного узла.
# a && b && c - это один узел logical с тремя детьми,
# а вот a - b + c при смене оператора распадётся на два узла: (a - b) + c
def parse_args(index, ops, node_type, parse_next):
    left, index = parse_next(index)
    while index < len(tokens) and tokens[index] in ops:
        op = tokens[index]
        args = [left]
        while index < len(tokens) and tokens[index] == op:
            arg, index = parse_next(index + 1)
            args.append(arg)
        left = {'type': node_type, 'value': op, 'args': args}
    return left, index

# || - самый низкий приоритет, поэтому разбирается первым
def parse_logical_or(index):
    return parse_args(index, {'or'}, 'logical', parse_logical_and)

def parse_logical_and(index):
    return parse_args(index, {'and'}, 'logical', parse_comparison)

def parse_comparison(index):
    return parse_args(index, {'>', '<', '=='}, 'logical', parse_add_sub)

def parse_add_sub(index):
    return parse_args(index, {'+', '-'}, 'arithmetic', parse_mul_div)

# * и / - самый высокий приоритет среди операторов
def parse_mul_div(index):
    return parse_args(index, {'*', '/'}, 'arithmetic', parse_term)

# дно цепочки: скобки, вызовы функций, литералы, переменные
def parse_term(index: int) -> tuple[dict, int]:
    token = tokens[index]

    if token == '(':  # скобки запускают цепочку приоритетов заново
        node, index = parse_expression(index + 1)
        return node, index + 1  # пропускаем ')'

    if token in FUNC_LIST:  # вызов функции: имя '(' аргументы через ',' ')'
        args = []
        index += 2  # пропускаем имя функции и '('
        while tokens[index] != ')':
            arg, index = parse_expression(index)
            args.append(arg)
            if tokens[index] == ',':
                index += 1
        return {'type': 'function', 'value': token, 'args': args}, index + 1

    if token == '-':  # унарный минус: -5 -> число со знаком
        return {'type': 'num', 'value': '-' + tokens[index + 1], 'args': []}, index + 2

    if token.isdigit():
        return {'type': 'num', 'value': token, 'args': []}, index + 1

    if token.startswith('"'):  # строковый литерал, кавычки оставил токенизатор
        return {'type': 'string', 'value': token.strip('"'), 'args': []}, index + 1

    # голый идентификатор - переменная из set(), отдельного типа узла нет:
    # интерпретатор найдёт её значение в контексте вычисления
    return {'type': 'string', 'value': token, 'args': []}, index + 1

На выражении count(filteredCart) > 0 парсер выдаст ровно то дерево, что описано выше:

tokens = ['count', '(', 'filteredCart', ')', '>', '0']
tree, _ = parse_expression(0)
# {'type': 'logical', 'value': '>', 'args': [
#     {'type': 'function', 'value': 'count',
#      'args': [{'type': 'string', 'value': 'filteredCart', 'args': []}]},
#     {'type': 'num', 'value': '0', 'args': []}]}

Обратите внимание на три вещи. Внутренний цикл parse_args собирает всю цепочку одного оператора в один узел - так &&-цепочка из примера в начале статьи станет одним узлом с четырьмя детьми, а не лесенкой пар. Скобки и аргументы функций в parse_term рекурсивно вызывают parse_expression: цепочка приоритетов запускается заново, поэтому произвольная вложенность не требует никакой отдельной обработки. И, наконец, неизвестный идентификатор перед ( в реальном парсере – вызовет ошибку разбора, а не будет молчаливо пропущен (так как список функций фиксирован.

Шаг 2: Валидация на входе. Синтаксис проверяет сам парсер: несбалансированные скобки или неизвестная функция отлавливаются ещё на этапе разбора. Но есть проверки, которые грамматика не выражает: обязательные аргументы у функций, ровно два операнда у оператора сравнения, минимум два - у && и ||. Их выполняет валидатор поверх готового дерева до того, как выражение попадёт в хранилище.

Шаг 3: Сравнительное тестирование. Финальная проверка корректности миграции проходило на реальных продакшн-данных. Одни и те же запросы прогонялись через старую систему на Teradata и через новую, а решения по каждому критерию сравнивались на сходимость. Расхождения были в основном из-за семантических различий в рантайме, которые не видны в синтаксисе. Например, filter() в RTIM при пустом результате возвращает пустой список, а наш интерпретатор в ряде случаев возвращал nil. Каждое расхождение разбирали вручную и либо фиксили интерпретатор, либо фиксировали осознанное отличие поведения.

Обновление правил без перезапуска

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

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

С чем столкнулись

Реверс-инжиниринг. Teradata RTIM - типичный «черный ящик» с очень скудной документацией . Перед разработкой пришлось потратить заметное время на анализ тысяч уже написанных выражений: какие аргументы принимает каждая функция, какие типы данных возвращает. Всё это выяснялось через отладку и тестирование.

Приоритеты операторов. В Java-подобных языках && имеет меньший приоритет, чем >, и большинство выражений на этом и держится. Но несколько критериев были написаны с явными скобками в неожиданных местах. Пришлось внимательно проверить, что парсер правильно обрабатывает все комбинации, - обычная граничная задача при написании парсеров, ничего экзотического.

Проверка типов. Тип атрибута (вроде Account.cart) задается не в выражении, а в метаданных профиля, которые резолвятся только во время выполнения запроса. Значит, проверить типы на этапе трансформации в принципе нельзя - мы еще не знаем, что фактически лежит по этому пути. Мы реализовали неявное приведение типов в интерпретаторе, чтобы сгладить большинство несовпадений, но это компромисс, а не решенная проблема. Часть ошибок в критериях проявится только тогда, когда конкретный запрос дойдет до конкретной ветки дерева в продакшне. Сравнительное тестирование снижает этот риск, но не убирает полностью.

Итог

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

Зато дальше всё работало предсказуемо. Когда в процессе миграции обнаруживался новый паттерн выражения, добавление поддержки занимало часы, а не дни. Не было ни одного случая в духе “регулярка не то захватила” или “пробел в неожиданном месте всё сломал”. Если вы мигрируете систему с собственным языком выражений - формульным, фильтрующим, любым - и этих выражений больше нескольких сотен, AST окупается. Порог входа невысокий: рекурсивный нисходящий парсер для подобных языков помещается в пятьсот строк кода, и надежность и возможность тестировать каждый слой отдельно стоят того. В нашем случае это была даже не инвестиция ради одной миграции: пока бизнес пишет критерии текстом, парсер и интерпретатор нужны системе постоянно.

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