Rules, Rules everywhere. One engine to rule them all

TravelTriangle is all about providing best booking experience to the travellers and catering to the requirements provided by them. To this end we rely heavily on making decisions based on conditions. For example, whether to activate a lead for a trip, where activation means forwarding the lead to agents on boarded on our platform. This decision involves analysing the data available in the lead, and whether it is sufficient for agents to provide suitable quotes to the traveler. Another example is checking the validity of a discount coupon on a trip. Our product is full of such conditional decisions across various flows, and until few months back, all conditions had to be coded in the system manually. Which meant even for small changes, our turnaround time was high, as there was direct dependency on development team. Product managers, and analytics team had to wait for couple of days before any changes could be pushed to production. Given the pace at which our product is evolving, such turnaround times were not tenable.

Hence, we decided to create a Rule Engine that can evaluate conditions at runtime and allow specification of these conditions declaratively without any code modifications. This article will focus on the architecture of this rule engine, it’s current capabilities/limitations, and the future roadmap.

Architecture

A Rule Engine essentially takes a set of conditions and input models representing core entities in the system (like User, RequestedTrip, Hotel, Quote), and based on these conditions provides a boolean output that can be used by the client invoking the rule engine to take further actions. Let’s take a deeper look into the architecture of rule engine. First we will describe what is a RULE.

ruleengine

Rule

A rule can be expressed grammatically as:

R -> A operator B: A,B R, I, V

where R are rules, I are input models and V are static values and operator can be either of <=, >=, >, <, ==, <>, +, -, *, /, %, ^, between, index, match, in, subset_intersect, subset_difference, array_include, key_value_compare, exists, size.

The rule_evaluator in rule engine is used to execute a rule which yields a boolean value and an action string. It depends on the client  of the  rule engine to  execute the action based on the result.

A sample rule can be

(A < B && C> D) || (E > (D – F)) || G <> H

This rule can be broken into individual conditions, where each condition is represented as

                                                         LHS Operator RHS

In the above rule there are four conditions:

  1. A < B
  2. C> D
  3. E > (D – F)
  4. G <>H

The rule_evaluator invokes condition_evaluator which generates a parse tree from the rule. Parse tree generated by condition evaluator for the aforementioned rule is represented below. After creation of the parse tree, rule is evaluated via a post order traversal of the tree.

tree

To represent the rules in our system we created our own DSL, which is covered in the next section.

Rule DSL

Rule DSL is a representation of a rule where it maps the data inputs to individual conditions. The DSL consists of following components:

  • priority : Priority defines the order in which rule will be executed
  • action : {success : s1, failure: f1}: Action is a string value which will be used by the rule engine client
  • condition: [Condition A, Condition B, Condition C]: Array of Rule conditions
  • operator: All the conditions are joined by a single operator namely, Conjunction(AND), Disjunction(OR) and Negation(NOT)

System supports two types of conditions:

  1. Simple Conditions :  A simple condition is defined as LHS operator RHS where LHS and RHS are constant values either supplied by input models or defined in the rule. A simple condition is expressed in DSL as   
    1. {field: {type: t1, val: v1}, operator: o1, value:{type: t2, val: v2}}
    2. An example simple condition is given below, which is checking if the departure city of a trip is an international location or not. 

“field”: {

“type”: “Trip”,

“attribute”: “from_location_type”,

“data_type”: “String”

},

“operator”: “!=”,

“value”: {

“type”: “String”,

“value”: “International”

}

  1. Complex Conditions : A complex condition is defined as LHS operator RHS where LHS is a constant value supplied by input models and RHS is a simple condition or a complex condition as well. A complex condition is expressed in DSL as
    1. {field: {type: t1, val: v1}, operator: o1, value:expression}
    2. An example of complex condition is given below. The condition is checking if the start date of a trip is 6 months from the date of lead creation. 

“field”: {

“type”: “Trip”,

“attribute”: “starting_date”,

“data_type”: “date”

},

“operator”: “>”,

“value”: {

“type”: “expression”,

“Value”: {

“field”: {

“type”: “Trip”,

“attribute”: “creation_date”,

“data_type”: “date”

},

“operator”: “+”,

“value”: {

“type”: “Integer”,

“value”: 180,

“Sub_type”: “day”

}

}

}

How do we use Rule Engine?

This engine is powering multiple use cases in the system including Activation Logic (covered below), checking coupon validity, calculating commissions applicable on a trip, computing payment schedules etc.

Activation Logic determines if a lead is hygienic and contains sufficient information to forward it to the agents. One of rules under Activation Logic, called Low Quality Lead rule, determines the quality of the lead. A simplified version of this rule is represented by the following expression:

Trip.fromLocationType != ‘International’ && Trip.stageOfTrip == ”Still a Looker”

 Below is the DSL for the above expression.  

{

 “composition”: “COMPLEX”,

 “action”: {

    “failure”: null,

    “success”: “Low quality lead”

 },

 “condition”: {

    “AND”: [

     {

       “type”: “Condition”,

       “field”: {

         “type”: “Trip”,

         “attribute”: “from_location_type”,

         “data_type”: “String”

       },

       “operator”: “!=”,

       “value”: {

         “type”: “String”,

         “value”: “International”

       }

     },

     {

       “type”: “Condition”,

       “field”: {

         “type”: “Trip”,

         “attribute”: “stage_of_trip”,

         “data_type”: “String”

       },

       “operator”: “==”,

       “value”: {

         “type”: “String”,

         “value”: “Still a Looker”

       }

     }

    ]

 }

}    

All the rules of the activation logic are defined in a similar manner. We also track the number of rule executions that happen in our system using our monitoring and metrics collection framework built using InfluxDb (which shall be covered in a later blog post). Below we can see the graph of the frequency at which our rule engine executes a single rule set.

 rule_stats

From performance perspective, we are able to execute thousands of rules within a minute, with no execution taking more than a few milliseconds, thus enabling our product to make critical decisions in run time. 

We have also created a navigation UI for the product and analytics team to define the rules easily. A glimpse of this rule engine UI is given below. The UI was created in AngularJs 1.4. You can see how our DSL condition is represented in GUI. On left hand side there is a field which represents the LHS of the equation. Field Type is a predefined set of Models available in our application, and attribute is the set of reflections of the Model we have selected. On right hand side there is value which represents the RHS of the equation. Here value type is predefined set of Models and various Data types like Array, String e.t.c.

rule_ui

Limitations and Future scope

Currently our rule engine does not have strict type checking or validation on the inputs and depends on the client, making the invocation, to provide valid data for processing the rules. Also, it can only consume static model information, i.e the attributes of a model on which rules are written and evaluated are predefined and cannot be loaded or changed at run time. This again limits the capabilities of our engine, since we cannot define rules on dynamic attributes such as user segments (which change over time), agent categories etc. To enable this, we will have to redesign the rule engine to execute as a multi pass evaluator instead of a single pass evaluator. We intend to make our rule engine self sufficient in terms validation of input, as well by loading data needed for rule evaluation dynamically at run time. 

Another shortcoming of our rule engine is that the rule grammar allows expression of only independent rules that are not dependent on each other. Also execution of one rule is not dependent on result of other thus making it unable to execute a whole decision tree. In future, we are planning to do away with this linear execution and go with full tree flow execution, thus giving more decisional powers to rule engine.    

We are constantly working on such challenging problems at TravelTriangle. If you are interested in working on similar problems, do reach out to us at career@traveltriangle.com.

Comments