事务布景

运力资源是货拉拉事务的中心要素之一，但是跟着事务量的添加，运力资源呈现了供需失衡的现象，有些专业商场的运力供给紧缺，而有些专业商场的运力供给饱和。面临供需失衡的现象，需求依据数据剖析和确诊去制定专业商场的促销战略，以到达平衡供需联系的意图。但仅依赖BI人员经过线下零散报表和暂时跑数等工具来辅佐人工进行确诊、复盘、优化的手段，无法掩盖全国性运力资源的调理。而且BI人员需将数据在多个体系之间导入导出，导致数据链路冗长、效率低下。

因而，货拉拉大数据团队依据供需失衡的场景，构建一套线上实时动态运力资源调理的体系，经过目标因子结合规矩引擎进行调理，以到达运力资源的供需平衡，然后促进司机、用户、渠道三方共赢的效果。

项目架构

货拉拉大数据基于规则引擎构建运力资源供需调节系统

运力调理体系，在项目架构维度上，从上到下可分为：应用层、服务层、引擎层、数据存储层。本文首要介绍从应用层的战略装备到引擎层中的使命核算层这部分内容在规矩引擎及K8s方面上的实践。

战略组

战略形式

运力的供需平衡调理，总体上可分为三个战略：

  • 确诊战略：BI/算法人员经过多个目标因子，制定确诊战略，由确诊战略中的规矩挑选出需求进行供需调理的OD（Origin Grid，起点网格。Destination Grid，结尾网格。OD：指起点网格与结尾网格）。针对挑选出的OD进行供需调理，并上线。如添加/减少优惠券发放数量，添加/减少司机或用户的补助额度等等。
  • 复盘战略：经过每日的复盘战略，对OD打上标签，调查经过确诊战略进行供需调理后OD的供需情况。当满意复盘战略的规矩时，则履行结束或继续履行优化战略。
  • 优化战略：优化战略是依据复盘战略的成果进行的继续不断的优化，使得终究供需情况得到收敛。

货拉拉大数据基于规则引擎构建运力资源供需调节系统

规矩

  • 规矩：是挑选OD的最小“原子”单位，规矩的构成如下：
左值 联系运算符 右值
变量（首要是目标变量） >=, <=, >, <, ==, !=, is, contains…… 详细数值/文本

比方：预付呼应单量 >= 100

左值 联系运算符 右值
预付呼应单量 >= 100

规矩组：

  • 单一规矩无法挑选出契合要求的OD，此刻需求结合逻辑运算符AND、OR，构成相对复杂的逻辑表达式。格局如：规矩A && ( 规矩B || 规矩C )…

货拉拉大数据基于规则引擎构建运力资源供需调节系统

规矩互斥性校验：

  • 规矩互斥性校验的意图：确保规矩组挑选出来的OD调集间不存在交集，也便是：规矩A ∩ 规矩B = ∅。如下图，在全集U中，规矩A与规矩B扫描出来的OD是不存在交集的，然后防止多个供需战略调理包作用于一个OD，导致OD的供需调理呈现不可预知的差错。

货拉拉大数据基于规则引擎构建运力资源供需调节系统

怎么经过算法确保规矩间互斥性呢，一种比较直观的办法：运用每个规矩，从数据库挑选出OD调集，然后对调集求交集，但这种直观的办法却存在以下几个缺点：

  • 不可信：调集求交集有必要依赖源数据，而源数据是继续改变的，也就意味着规矩的互斥性在不一起刻下，可能是不一样的。
  • 功能低下：每一次的互斥性校验都有必要依据全集U下去进行扫描，意味着对数据库的全表扫描，导致功能低下
  • 后置性感知：感知是依据数据库有数据才干履行下一步校验。

因而，这里经过数学办法来校验，做到不依赖源数据进行互斥性校验。其来自数学上的一个定理：任何一个逻辑函数表达式都能展开成一个“与或”表达式，也即称为：析取范式。（Disjunctive Normal Form，简称：DNF）

  • 关于每一个规矩组，可用如下图的数据结构表明

    • 第一层节点存储：逻辑运算符or
    • 第二层节点存储：逻辑运算符and
    • 叶子节点：存储联系表达式

货拉拉大数据基于规则引擎构建运力资源供需调节系统

  • 关于没有逻辑运算符的单一规矩，为确保归一性，也可用如下图的数据结构表明：

货拉拉大数据基于规则引擎构建运力资源供需调节系统

互斥性校验算法：

关于每条析取范式的规矩，其就演变成求：规矩A与规矩B的Object（参阅上图）是否存在交集。而关于Object的比较，遵循如下算法原理：

  • 当且仅当每个Object内的一切变量都存在交集时，则证明整个Object所表明的规矩存在交集，也便是不互斥。假如两两比照的Object中不存在相同变量，则运用补足变量的办法，而且该变量占用全集。如：a > 1 与 b > 1比照，选用补足变量的办法，则变成：( a > 1 and -∞ < b < +∞ )与 ( -∞ < a < +∞ and b > 1)。很明显，a > 1 跟 -∞ < a < +∞ 存在交集，-∞ < b < +∞ 跟 b > 1存在交集。因而，a > 1 与 b > 1是存在交集的，也便是不互斥。
  • 当任意一个两两比较的Object存在交集时，则整个规矩组存在交集，也便是不互斥。

规矩引擎实践

BI/算法人员每天都会产出许多战略，每个战略都包含规矩。

一般的项目中没有引用规矩引擎之前，一般的做法都是运用一个接口进行事务工作。首先要传进去参数，经过if…else或其他办法进行事务逻辑判别，其非必须获取到接口履行结束后的成果。每次规矩的改变，都需求修改写死在代码中的if…else代码，然后进行发版。这种每一次规矩改变都需求发版的操作，毫无疑问将导致效率低下，一起也容易引发线上事故。但运用规矩引擎后就截然不同了，原有的if…else不复存在，代替它们的是规矩引擎脚本，经过规矩引擎完结可动态改变的“if …else”。

  • 下面临几种常见的规矩引擎进行比照
Drools IKExpression Aviator
简介 Drools（JBoss Rules ）是一个开源事务规矩办理体系解决方案 (BRMS)，提供中心事务规矩引擎 (BRE)、Web 创作和规矩办理应用程序 (Drools Workbench)。契合业内标准，速度快、效率高 IK Expression是一个开源的（OpenSource)，可扩展的（Extensible），依据java语言开发的一个超轻量级（Super lightweight）的公式化语言解析履行工具包。 Aviator是一个高功能、轻量级的java语言完结的规矩引擎，首要用于各种表达式或逻辑表达式的动态求值。
学习本钱 高 低 低
功能 运用Rete算法快速匹配，功能高。尤其是对处理一个有成百上千特色的复杂目标时的快速匹配规矩时速度快。 依托解释履行来完结表达式的履行，和 Aviator，Groovy 这种编译履行的引擎相比，功能较差。 经过将逻辑表达式编译成Java字节码，交给JVM去履行。相比其它解释性的规矩引擎而言，具有轻量级，高功能的特色。
功能 功能丰厚 功能有限的解析引擎 功能相比IKExpression丰厚，但逊色于Drools

供需调理的规矩并不像风控体系那般复杂，供需调理的中心是从存储海量OD的数据库中找出契合装备规矩的特定OD，并对该OD进行如优惠券，补助等促销手段的调理。可抽象为以下两个方面：

  • 判定OD的详细目标的值是否满意规矩表达式，其返回的是一个布尔变量。
  • 因为规矩的多变性，因而无法运用写死if…else代码，需经过规矩引擎完结可动态改变的“if …else”。

因而，在综合考虑上述各个引擎的学习本钱、功能、功能与事务场景的匹配性之后，技能团队选型运用了Aviator作为本项意图规矩引擎框架。

货拉拉大数据基于规则引擎构建运力资源供需调节系统

  1. XXL-Job每5分钟守时扫描装备上线的OD战略，依据该战略装备的规矩，生成字符串格局的逻辑表达式，并存储于Mysql中。
  2. 当需求扫描OD进行规矩匹配时，则从Mysql中加载对应的逻辑表达式，运用 aviator进行compile后缓存。
  3. 将OD的目标的值作为compiledExp的newEnv的值，进行规矩装备。
  4. 假如满意规矩，则履行事务逻辑；否则，履行另一种事务逻辑。
// 从数据库取得规矩，此处以字面常量展现
String expression = "(a > 50 && b > 200) || c > 10";
Expression compiledExp = 
    AviatorEvaluator
    .compile(md5Hash(md5Hash(expression)), expression, true);
// 查询OD，将OD的目标作为newEnv的args。
Boolean matched =
        (Boolean) compiledExp
        .execute(compiledExp.newEnv("a", 300, "b", 450, "c", 700));
if (matched) {
    // 供需战略包......
} else {
   //  其它供需战略调整......
}

功能优化实践

在供需调理体系上，对OD的调理，可以简化为如下的数据链路模型：从数据库查询OD，将查询到的OD经过规矩引擎匹配，终究射中对应的供需战略调理包。所以，在功能优化上，首要从以下两方面切入：怎么从数据库中快速查询很多的OD？规矩的匹配怎么优化？下面将从OD查询与规矩匹配两方面做的功能提高进行介绍。

货拉拉大数据基于规则引擎构建运力资源供需调节系统

OD查询功能优化办法

虽然在OD的规矩匹配过程中，运用了aviator进行规矩匹配。但因为OD的数据量大，特别是遇到单个批次数据量大的时候，在查询OD时，即使射中了索引，也时常呈现了超时现象。因而，这里引入了一个“批次兼并切分”的概念，结合K8s完结分布式多进程与多线程一起协作，从此对读写功能进行了提高。

  • 学习贪心算法的思想，对批次中OD数量少的兼并下一个批次，对批次中OD数据大的切分红多个子批次。
  • 经过使命切分模块，核算得到需求K8s一起启动的的Job数量以及每个Job内并发的Task数。

货拉拉大数据基于规则引擎构建运力资源供需调节系统

货拉拉大数据基于规则引擎构建运力资源供需调节系统

规矩匹配功能优化办法

  • 缓存热门OD：因为OD的运力调整是继续不断的迭代直至收敛，也就意味着在屡次迭代的过程中，会复用到之前的规矩，然后导致同一个OD被同一个规矩屡次扫描到，因而经过运用LRU算法，对热门OD进行缓存。关于现已经过规矩匹配的OD，不用运用Aviator进行规矩匹配，直接复用前次规矩匹配的成果值。
// 从数据库取得规矩，此处以常量展现
String expression = "(a > 50 && b > 200) || c > 10";
String expressionKey = md5Hash(md5Hash(expression));
OdMatchStatus odMatchStatus = lruCacheMap.get(expressionKey);
if (odMatchStatus != null) {
    // 射中热门OD缓存，则不再运用AviatorEvaluator进行规矩的匹配判定。
} else {
    // 运用AviatorEvaluator匹配。并记载匹配次数，
    // 当其到达热门OD数据的最低门槛时, 将其加入热门OD的缓存中
}
  • 运用Aviator默认的运行期优化优先的运行形式。
  • 运用编译成果缓存形式，复用编译成果，传入不同变量履行。一起缓存Key运用两次md5哈希算法对表达式进行哈希，防止缓存Key存在哈希磕碰。
AviatorEvaluator.getInstance()
     .setOption(Options.OPTIMIZE_LEVEL, AviatorEvaluator.EVAL);
Expression compiledExp = 
    AviatorEvaluator
    .compile(md5Hash(md5Hash(expression)), expression, true);
  • 外部变量传入，优先运用编译成果的 Expression#newEnv(..args) 办法创建外部 env，将会启用符号化，降低变量拜访开销。

结束语：

本文首要介绍规矩的互斥性校验原理，规矩引擎在运力调理场景下的应用，一起扼要介绍在功能优化上的实践。运力调理是一个巨大的工程，本文无法面面俱到，后续将经过其它文章进行介绍。期望读者能从本文中有所收成。

作者介绍：陈佳超｜高级大数据工程师。曾任职于华为，现任职于货拉拉大数据部门，首要负责定价体系、营销一体化-AB、A/B实验渠道与A/B SDK项目。在大数据应用架构规划、落地、开发、存储与功能优化提高方面有较丰厚的实战经验。