Policy Engine 的前世今生

作为一个 video streaming service，TubiTV 很重要的一项功能是保证影视剧按照合约上的要求在规定的时间（窗口期），规定的平台，以及规定的国家发布。比如 Terminator，合约上规定 7/1 ~ 10/30（我瞎编的窗口），在美国可以上线，只允许 appletv，iphone，roku，web 访问，那么，如果我们不能正确处理，让加拿大的观众通过正常渠道访问到，或者过了窗口期，美国的观众也能访问，那么就是违约行为，可能导致严重的后果。这是 video stream service 普遍存在的需求。

一部电影的窗口期有时候会很复杂，有可能同时存在多个窗口，瞎编一个栗子：

• 美国用户一季度可以在 roku，xbox 上访问
• 美国用户三季度可以在 web，iphone，ipad，android 上访问
• 加拿大用户 3-4 月可以在 appletv 上访问
• 英国用户 12/1 - 12/15 日可以在 firetv 上访问

Rule Engine：此情可待成追忆

为这样的数据建模，并提供快速的决策并非易事，简单起见可以做一个 rule engine，把一条条窗口的信息转化成一条条 rule，然后从上到下匹配，匹配到就立即返回。

这么做对于小规模的数据，以及简单的规则还好，如果规则复杂起来，影视剧的规模上一个层次，就会立即遇到瓶颈。假设我们一次要验证 500 部电影是否在现在的时刻，在美国加州，使用 iphone 允许访问，假定平均的规则数是 5，每验证 3/5 的规则才能确定是否允许播放，那么我们需要执行 300 次规则才能完成验证。再假设每秒有 200 个来自用户的请求，在没有命中缓存的情况下，最坏的情况 1s 我们要验证 60k 次规则。

显然，这样的解决方案无法满足人民群众日益增长的物质文化需求，我们需要另辟蹊跷。

2016年以来，在 TubiTV，越来越复杂的规则，越来越丰富的内容，越来越多的用户，使得我们的目录服务越来越慢，在大致 6 月前后，我们的规则系统开始不堪重负，到了更新换代的时候。

Rule parser：曾经沧海难为水

权衡各种利弊之后，我们最终选择了用 BNF 表述规则。想法很简单，在数据库里，我们维护一个描述规则的表达式，还以上面的例子为例：

((country = "US") and 
 (platform in ["roku", "xbox"]) and 
 (01/01/2016 < date < 03/31/2016))
 or ((country = "US") and 
     (platform in ["web", "iphone"]) and
     (07/01/2016 < date < 09/30/2016))
...

这样的话，我们把匹配规则的工作变成了表达式执行的操作，效率一下子高了一个数量级。不过表达式执行的难点在于，如何用合适的工具将其转化成语法树，使之可以执行。我们知道，在 C 的领域，有 flex / bison（大学期间编译原理使用的 lex / yacc 的升级版），由于我们的系统是 nodejs 构建的，直接用有诸多不便，所以我们选用了 jison —— javascript 下的 bison。

用 jison 描述 BNF（严格说，是 EBNF）很容易，定义好 lex 后，就可以定义 grammar 了。关于这个主题，我之前写过文章，见：如何愉快地写个小parser。在这里就不详述了。

jison 会把 EBNF 编译成 javascript 文件，然后我们包装一个简单的接口（主要考虑易用性），就可以让系统的其他部分调用了。它的效率很高，很好地支撑起了我们的服务。

然而 javascript 毕竟还是一个解释型的语言，生成的文件很复杂，效率不高，而且需要解释执行（我知道 js 有 JIT），和 bison 生成 C 代码并编译，效率低了很多。因为 policy expression 存储在数据库中，每次当我们通过一个 id 要确定这个内容是否在指定的环境允许播放时，还需要读取数据库（或者 redis 缓存）。

最要命的时候随着 TubiTV 的发展，我们的内容成倍增长，我们的用户和流量好几倍增长，我们支持的平台越来越多，新的基于表达式的 policy engine 也开始不堪重负 —— 我们通过增加缓存，减少首次调用处理的内容数量等等手段，勉力维持这系统的正常运作。

可是，时不时的，我们还是会收到 slow API 的报警 —— 在有些小众国家，policy engine 处理了数千次内容才勉强获得可供用户播放的内容 —— 由于这样的国家访客很少，缓存往往是不在线的，因此一切都是按照最低效的方式处理：读取数据库，一个个 evaluate policy expression，写缓存，等等等等。

2017年已至，现有的 policy engine 眼看着又不能满足人民群众日益增长的物质文化需求了。。。

Policy Engine：花自飘零水自流

昨晚在火车上，我一口气收到了很多系统的报警，除了其他问题外，不少都指向 policy engine。我一边用 elixir 写着代码，一遍思索着如何解决这个问题。

突然间，我一闪念：何不用找找 elixir 撰写的 BNF 工具，在 elixir 下面解析出语法树，然后利用 macro 生成适合 pattern matching engine 优化的代码？

这样我可以把整个 database 里的 id 和 policy 生成成千上万个处理函数，由 erlang VM 来做 optimized binary search tree？

人类一思考，上帝就发笑，序员一思考，上帝想上吊。回到家，草草扒拉两口饭，就迫不及待研究 elixir 下面类似 bison 的工具，找来找去没有找到合适的，只觉得一个 ABNF 的似乎还看着不错，于是便甩开膀子研究起来。ABNF 的语法比较别扭，tokenization 还需要显式地声明空白字符，不像 EBNF 直接写一句所有空白字符都 skip 就可以不必关心了。当然，这不是什么大问题，更大的问题是 ABNF 不支持递归。突然间让我把一个由递归写就的 EBNF 转换成 ABNF，我很不适应，边翻 RFC5234 学习边写。一路折腾到 12 点多，还没折腾利索，一看表，在这么折腾下去，第二天没法上班，就依依不舍睡去了。

睡觉也睡不踏实。脑子里全是没有解决完的问题的思考。嘴里数着羊，大脑卡了一个线程复盘解决方案，一个线程无理由地播放《美丽心灵》。就这么半睡半醒到四点，脑袋里突然一闪念：为啥我守着一个支持 quote / unquote 的语言，却要用 BNF 去实现表达式？BNF 是给没有 metaprogramming 能力的语言提供的工具，我完全可以把现有的 expression 转换成 elixir 能够认识的表达式，然后 Code.string_to_quoted 不就可以了么？

那厢小贝饿了在呼唤她娘，我干脆也放弃假寐数羊，一个鲤鱼打挺冲出去，写下了这么几行：

def parse(policy) do
  policy    
    |> format_date    
    |> format_not_in    
    |> format_not_equal    
    |> format_equal    
    |> Code.string_to_quoted # string => compiled expr
end

测试一下：

iex(1)> PolicyEngine.Parser.parse("country in [\"US\", \"CA\"] and platform not in [\"web\", \"appletv\"]")
{:ok,
 {:and, [line: 1],
  [{:in, [line: 1], [{:country, [line: 1], nil}, ["US", "CA"]]},
   {:<~>, [line: 1], [{:platform, [line: 1], nil}, ["web", "appletv"]]}]}}

hin好！所谓念念不忘，必有回响！五小时徒劳无功，十分钟便推翻了一切。

接下来就是生成海量（100k）的函数，让 erlang VM 的 pattern matching 接管替我做 binary search tree：

这段代码从数据库里读取所有视频数据，然后生成 parse 函数。VM 会把它们优化成 binary search tree，高效访问。访问数据库只是在 compile time 发生，runtime 完全脱离了数据库。你可以将它想象成一个 cache，只不过不是 data cache，是 code cache。

主体的代码就这么两段，非常简单易懂。使用 benchfella benchmark 一下，每次 policy match 只需要 20us：

$ mix bench
Settings:
  duration:      1.0 s

## BasicBench
[20:43:52] 1/1: policy check

Finished in 2.41 seconds

## BasicBench
benchmark nam iterations   average time
policy check      100000   21.12 µs/op

写了两个测试例和线上的环境对比一下，500 个 policy，在完全没 cache 的情况下，nodejs 的基于 JISON 的 rule parser 要几百毫秒，新的 policy engine 只需要几十毫秒，数量级的差别。这里我还没有使用 GenServer 和 Poolboy 做 concurrent check，估计这样做下来效率会再上一个台阶。

当然凡是有得必有失。runtime 的高效是以 compile time 的低效为代价的。在我的高配 mbp 上，compile 一次 10 分钟。这里面有很多优化的空间，比如说可以用 Experimental.Flow 替换 Enum 使之能够 partition 到多个 process 下执行。

当 policy 变更，或者新增内容时，我们需要 recompile，并且更新线上系统。好在 erlang VM 对 hot reload 支持完美，这不是个事。关键还是把 compile time 优化到分钟级，十分钟太长。

同时，需要提供 rest 或者 gRPC 的 API 供 nodejs 下的其他系统使用。添加 rest API 额外会带来 50-100ms 的消耗，但依旧比之前的系统好很多。

今天中午本来打算跟 team 分享如何用 elixir 实现 activity stream 的，临时换了主题，改成了讲 Policy Engine。晚上回家的火车上还意犹未尽，又写了这篇文章。回到家和老婆分享了这事，老婆说，你这买卖做得划算啊，写了 200 行代码，先是在公司臭屁一番，然后又跑公众号上臭屁一番，回到家还继续臭屁，一石三鸟。