Компилятор бизнес-правил на основе деревьев выражений

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

TL; DR

Для тех, кто предпочитает читать код — ссылка на репозиторий GitHub с кодом из статьи.

Обо мне

Меня зовут Даниэль, я старший разработчик в компании Arcadia. Мой опыт в основном сосредоточен в сфере финансов: крупный банк, биржевой брокер и финансовая консалтинговая компания.

О проекте и задаче 

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

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

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

Для того чтобы решение было наиболее гибким (мы должны полагаться только на схему данных) и эффективным (не перегружать мощности серверов какой-то сложной обработкой), мы решили написать компилятор, который из определения самого правила, полученного в формате JSON, создаст функцию, принимающую нужные аргументы и возвращающую булев результат: true — мы должны отправить уведомление, false — уведомление отправлять не нужно. Данный компилятор был написан на С# c использованием деревьев выражений.

Ещё немного вступления 

Немного расскажу о самой технологии деревьев выражений в .NET. Чтобы мой рассказ не был простым копированием текста из документации, я буду говорить о том, под каким углом лично я рассматриваю эту технологию применительно к этой конкретной задаче.

Начну, пожалуй, с простого документа в Microsoft Excel. Это приложение господствует в корпоративном секторе отчасти благодаря своему богатому функционалу. Меня на данный момент больше всего интересуют пользовательские функции (User Defined Functions, UDFs). С помощью этих функций мы можем создать некоторые расчёты в нашем документе, связать между собой полученные на более ранних этапах результаты и на их основе произвести другие вычисления или анализ. Таким образом мы можем декомпозировать сложные вычисления на несколько простых, что само по себе даёт большой простор для творчества.

Небольшое демо того, на что примерно я ориентируюсь. В этом документе я пытаюсь отобразить форматированное сообщение ‘ALERT’, если изменение цены превысило 20%.

Четыре столбца: PREVIOUS (предыдущая цена) — CURRENT (текущая цена) — % (изменение в процентах) — Результат, наличие или отсутствие уведомления (ALERT).

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

Существует парадигма программирования, которая представляет программу как набор таких графов, называется она «программирование на основе потоков данных» (dataflow programming). На основе этой парадигмы и связанных с ней идей появились множество трендов и технологий в разработке: TensorFlow, модель акторов, реактивное программирование.

Возьмём простой граф:

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

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

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

Решение 

Я создам набор простых правил, которые буду использовать как пример и на основе которых опишу сам процесс обработки данных.

Минимальная цена на продажу алюминия на Лондонской бирже металлов (LME) превысила определённое значение.

price.Symbol == "LME-AL" && price.Ask > 20 

Средняя цена на медь или золото на Лондонской бирже металлов (LME) упала ниже определённого значения.

(price.Symbol == "LME-CO" || price.Symbol == "LME-GO") && price.Mid < 14 

Цены на некоторые металлы изменились на Чикагской товарной бирже.

price.Symbol == "CME-CO" || price.Symbol == "CME-ZN"
  || price.Symbol == "CME-AL"|| price.Symbol == "CME-NI" 

(Названия символов взяты из головы и к реальности отношения не имеют.)

Теперь можно описать, как примерно будет выглядеть простое выражение, которое мы хотим получить в результате, чтобы нагляднее представлять конечную цель.

// ... price.Symbol == "LME-AL" && price.Ask > 20 
System.Linq.Expressions.BinaryExpression binaryExpression 
     = System.Linq.Expressions.Expression.MakeBinary( 
         System.Linq.Expressions.ExpressionType.And, 
         System.Linq.Expressions.Expression.MakeBinary( 
             System.Linq.Expressions.ExpressionType.Equal, 
             System.Linq.Expressions.Expression.Constant({price.Symbol}), 
             System.Linq.Expressions.Expression.Constant("LME-AL")), 
         System.Linq.Expressions.Expression.MakeBinary( 
             System.Linq.Expressions.ExpressionType.GreaterThan, 
             System.Linq.Expressions.Expression.Constant({price.Ask}), 
             System.Linq.Expressions.Expression.Constant("20"))); 

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

{ 
//... metadata 
      "condition" : { 
          "operator" : "And", 
          "conditions" : [ 
             { 
                 "fact" : "Symbol", 
                 "operator" : "EQ", 
                 "value" : "LME-AL" 
             }, 
             { 
                 "fact" : "Ask", 
                 "operator" : "GT", 
                 "value" : "20" 
             } 
         ] 
     } 
} 

{ 
//... metadata 
      "condition" : { 
          "operator" : "And", 
          "conditions" : [ 
             { 
                  "operator" : "OR", 
                  "conditions" : [ 
                     { 
                          "fact" : "Symbol", 
                          "operator" : "EQ", 
                          "value" : "LME-CO" 
                     }, 
                     { 
                          "fact" : "Symbol", 
                          "operator" : "EQ", 
                          "value" : "LME-GO" 
                     } 
                  ] 
             }, 
             { 
                 "fact" : "Mid", 
                 "operator" : "LT", 
                 "value" : "14" 
             } 
         ] 
     } 
}

{ 
//... metadata 
      "condition" : { 
          "operator" : "OR", 
          "conditions" : [ 
             { 
                 "fact" : "Symbol", 
                 "operator" : "EQ", 
                 "value" : "CME-CO" 
             }, 
             { 
                 "fact" : "Symbol", 
                 "operator" : "EQ", 
                 "value" : "CME-ZN" 
             }, 
             { 
                 "fact" : "Symbol", 
                 "operator" : "EQ", 
                 "value" : "CME-AL" 
             }, 
             { 
                 "fact" : "Symbol", 
                 "operator" : "EQ", 
                 "value" : "CME-NI" 
             } 
         ] 
     } 
} 

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

Такое разделение кода возможно с паттерном «Посетитель», который мы применим в этой задаче.

Начнём с самого простого: определим базовый тип и подтипы для наших правил (выражений), основанных на стандартных классах Expression и ExpressionType из пространства имён System.Linq.Expressions. 

public abstract class Condition
{
  public ExpressionType Operator { get; set; }
  public abstract Expression Accept(IConditionExpressionVisitor visitor);
}

// ...
public sealed class BinaryCondition : Condition
{
	public string Fact { get; set; }
  public string Value { get; set; }
  public override Expression Accept(IConditionExpressionVisitor visitor)
  {
  	return visitor.Visit(this);
  }
} 
 
// ... 
public sealed class CompositeCondition : Condition
{
	public IEnumerable<Condition> Conditions { get; set; }
  public override Expression Accept(IConditionExpressionVisitor visitor)
  {
  	return visitor.Visit(this);
  }
} 

Теперь можно посмотреть на сам процесс компиляции. Мне нравится использовать в коде метафоры, которые могут отражать нечто связанное с реальностью. К примеру, в этом случае мне очень симпатична идея создания компилятора, напоминающего реальный компилятор существующего языка программирования. Разумеется, он будет упрощён, в этом и суть метафоры.

Я разобью процесс компиляции на два: 1. Трансляция; 2. Компиляция.

Трансляция, как первый шаг в этом упрощенном алгоритме, будет реализована с помощью паттерна «Посетитель»: 

public interface IConditionExpressionVisitor
{
  Expression Visit(CompositeCondition condition);
  Expression Visit(BinaryCondition condition);
}

internal partial class ConditionTranslator : IConditionExpressionVisitor
{
	private readonly BinaryConditionTranslator _binaryTranslator;
  private readonly CompositeConditionTranslator _compositeTranslator;
  
  internal ConditionTranslator(Type modelType, ParameterExpression parameter)
  {
  	_binaryTranslator = new BinaryConditionTranslator(modelType, parameter);
    _compositeTranslator = new CompositeConditionTranslator(this);
  }
  
  internal Expression Translate(Condition condition)
  {
  	return condition.Accept(this);
  }
  
  Expression IConditionExpressionVisitor.Visit(CompositeCondition condition)
  	=> _compositeTranslator.Translate(condition);
  
  Expression IConditionExpressionVisitor.Visit(BinaryCondition condition)
  	=> _binaryTranslator.Translate(condition);
} 

internal partial class ConditionTranslator
{
  private class BinaryConditionTranslator
  {
    private readonly Type _modelType;
    private readonly ParameterExpression _parameter;
    
    internal BinaryConditionTranslator(Type modelType, ParameterExpression parameter)
    {
      _modelType = modelType;
      _parameter = parameter;
    }
    
    internal Expression Translate(BinaryCondition condition)
    {
      if (string.IsNullOrWhiteSpace(condition.Fact))
      {
        throw new ArgumentException($"'{nameof(BinaryCondition)}.{nameof(condition.Fact)}' can not be null or empty.");
      }
      
      if (condition.Value == null)
      {
        throw new ArgumentException($"'{nameof(BinaryCondition)}.{nameof(condition.Value)}' can not be null.");
      }
      
      if (!FactIsPresented())
      {
        throw new ArgumentException($"Fact '{condition.Fact}' is not available.");
      }
      
      return TranslateToBinary();
      
      bool FactIsPresented() => _modelType.GetProperty(condition.Fact) != null;
      
      Expression TranslateToBinary()
      {
        try
        {
          PropertyInfo property = _modelType.GetProperty(condition.Fact);
          MemberExpression left = Expression.Property(_parameter, condition.Fact);
          
          Expression right = property.PropertyType.GetGenericArguments().Any()
            ? (Expression)Expression.Convert(Expression.Constant(
            	Convert.ChangeType(
                condition.Value, 
                property.PropertyType.GetGenericArguments().First(),
                CultureInfo.InvariantCulture)), property.PropertyType)
            : Expression.Constant(
              Convert.ChangeType(
                condition.Value,
                property.PropertyType,
                CultureInfo.InvariantCulture));
          
          return Expression.MakeBinary(condition.Operator, left, right);
        }
        catch (Exception ex)
        {
          throw new InvalidOperationException("Rule compilation exception", ex);
        }
      }
    }
  }
}

internal partial class ConditionTranslator
{
  private class CompositeConditionTranslator
  {
    private readonly ConditionTranslator _parent;
    
    internal CompositeConditionTranslator(ConditionTranslator translator)
    {
      _parent = translator;
    }
    
    internal Expression Translate(CompositeCondition condition)
    {
      List<Exception> exceptions = new List<Exception>();
      Expression[] translated = condition.Conditions.Select(child => Translate(child)).ToArray();
      
      if (exceptions.Any())
      {
        throw new InvalidOperationException("Rule compilation exception", new AggregateException(exceptions));
      }
      
      return translated.Aggregate((left, right) => Expression.MakeBinary(condition.Operator, left, right));
      
      Expression Translate(Condition condition)
      {
        try
        {
          return _parent.Translate(condition);
        }
        catch (AggregateException ex)
        {
          foreach (Exception innerEx in ex.InnerExceptions)
          {
            exceptions.Add(innerEx);
          }
          
          return Expression.Empty();
        }
        catch (Exception ex)
        {
          exceptions.Add(ex);
          return Expression.Empty();
        }
      }
   	}
  }
} 

За счёт этого интерфейс компилятора будет сильно упрощён.

public interface IConditionCompiler<TModel>
{
	Func<TModel, bool> Compile(Condition condition);
} 

А вот и сам компилятор.

public class ConditionCompiler<TModel> : IConditionCompiler<TModel>
{
	private readonly Type _modelType;
  private readonly ParameterExpression _parameter;
  private readonly ConditionTranslator _translator;
  
  public ConditionCompiler()
  {
  	_modelType = typeof(TModel);
    _parameter = Expression.Parameter(_modelType);
    _translator = new ConditionTranslator(_modelType, _parameter);
  }
  
  public Func<TModel, bool> Compile(Condition condition)
  	=> Expression.Lambda<Func<TModel, bool>>(
        _translator.Translate(condition),
        _parameter)
      .Compile();
}

Что, собственно, тут происходит? Если вкратце, то мы создаём компилятор, параметризованный типом модели, которую будем использовать. Далее мы получаем наше выражение и рекурсивно обходим каждый блок, проверяя, сможем ли мы его скомпилировать. Также мы проверяем тип и поля модели на соответствия.

Небольшой пример того, как может быть протестирован данный код:

var condition = new CompositeCondition
{
	Operator = ExpressionType.And,
  Conditions = new Condition[]
  {
  	new BinaryCondition
    {
    	Operator = ExpressionType.Equal,
      Fact = "Symbol",
      Value = "LME-AL"
    },
    new BinaryCondition
    {
    	Operator = ExpressionType.GreaterThan,
      Fact = "Ask",
      Value = "20"
    },
  }
};

Func<PriceModel, bool> rule = _priceRuleCompiler.Compile(condition); 

var incomingPriceUpdate = new PriceModel { Symbol = "LME-AL", Ask = 42 };
var shouldNotify = rule(incomingPriceUpdate);
if (shouldNotify)
{
  Console.WriteLine("PASSED. Notification is sent");
}

incomingPriceUpdate = new PriceModel { Symbol = "CME-AL", Ask = 42 };
var shouldNotNotify = rule(incomingPriceUpdate) is false;
if (shouldNotNotify)
{
  Console.WriteLine("PASSED. Notification has not been sent");
} 

Немного статистики.

Время компиляции и исполнения одного правила в миллисекундах (Intel i7-8550U, 16GB RAM).

Немного о расширяемости кода.

Кроме простых булевых операций можно добавить вызовы методов классов, валидацию компилятора на основе отражений (system reflection), к примеру запретить компилировать некоторые булевы операции для определённых типов полей, или же, что более реалистично, запретить компилировать вызовы некоторых функций. Все расширения могут быть добавлены зависимостями в конструктор класса или метаданными в модель.

Стек технологий и использование в проде 

Мы активно используем платформу Azure. Наш компилятор интегрирован в сервис и развёрнут в кластере Service Fabric. Для того чтобы хранить пользовательские конфигурации бизнес-правил, мы используем Cosmos DB, сам же механизм отправки реализован через очередь в Service Bus.

Упрощённая схема работы выглядит так: мы имеем две очереди, к которым подключён сервис, и коллекцию, в которой мы храним правила. Одна для получения обновлений из источников данных, вторая для отправки уведомлений. Мы разделили фазы компиляции и исполнения наших правил, чтобы получить некоторый прирост производительности. При старте сервис запрашивает все правила из хранилища, компилирует их и сохраняет во внутренний кэш. Как только пользователь изменяет правило или добавляет новое, мы получаем обновления через Cosmos DB Change Feed и меняем значение в кэше. Таким образом мы всегда имеем актуальное состояние кэша и гарантируем отправку уведомления пользователю. Каждый раз, когда мы получаем уведомление из очереди, мы просматриваем кэш, исполняя каждое правило; в зависимости от результата мы либо отправляем уведомление в очередь уведомлений, либо идём дальше по циклу.

Наше приложение не является высоконагруженным — мы имеем до 100,000 активных пользователей, поэтому простого кэширования скомпилированных правил нам хватает с избытком. Но я уверен, что даже в случае высокой нагрузки данное решение будет уместным. К примеру, мы можем воспользоваться шардированием (sharding), добавив больше нод для нашего сервиса и сохранять в каждой ноде лишь часть общих правил. С помощью топиков в Azure ServiceBus мы можем маршрутизировать обновления из наших источников на конкретную ноду. Мы также можем воспользоваться вертикальным масштабированием — увеличить количество потоков, чтобы получить прирост производительности не только на этапе исполнения правил, но и на этапе их компиляции.

Заключение 

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

На этом у меня всё. Спасибо!