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 行代码,先是在公司臭屁一番,然后又跑公众号上臭屁一番,回到家还继续臭屁,一石三鸟。

原文发布于微信公众号 - 程序人生(programmer_life)

原文发表时间:2017-01-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

HTML5对APP开发最终用户的三大优势

一、大幅降低使用门槛   为什么流媒体会替代下载视频成为主流?为什么页游会如此火爆?只因用户太“懒”。让用户更方便的满足需求,有时效果好于更多的满足需求。  用...

38360
来自专栏FreeBuf

浅析大规模生产网络的纵深防御架构

纵深防御这个在安全行业被用的很烂的词,乙方的顾问写方案时信手捏来,我想大家的理解可能并不一致。其实我比较赞同lake2用的“河防”以及数字公司用的“塔防”的概念...

39350
来自专栏黑白安全

51Job百万条用户信息外泄?暗网售价12个比特币

记者发现,前程无忧51Job.com(Nasdaq:JOBS)用户信息在暗网上被公开销售,黑客甚至展示了部分样本数据,包括邮箱、密码、真实姓名、身份证号码、电话...

9530
来自专栏Linyb极客之路

杂谈设计模式与系统阶段的关系

12340
来自专栏FreeBuf

解读NSA对APT组织的透视

近日,CrySyS实验室和Ukatemi联合发布了一份安全报告。研究人员基于“影子经纪人”泄漏的NSA数据,发现了代号为“领土争端”(Terditorial D...

17430
来自专栏非著名程序员

编程不息,Bug 不止

今天不想聊别的,就想聊点 Bug,是不是感觉我有点傲娇呢?昨天大家的留言我都一一仔细看完了,看完之后,就想到了一句话:生命不息,坎坷不止。2016年大家真的是被...

18290
来自专栏小文博客

腾讯云年中大促,低至三折优惠

站长朋友们注意啦,最近腾讯云活动不断,新出活动腾讯云年中大促,部分热销商品限时5折,更有年付三折优惠,现在购买服务器再合适不过了。已有腾讯云服务器的站长朋友也不...

55240
来自专栏程序人生

Botwall - Bot Firewall??

Mountain View的El Camino Real和Castro交界的地方,有一栋大楼,地址是:800 W El Camino Real,里面入驻了不少创...

38070
来自专栏程序员互动联盟

如何成为一个黑客?

很多人要成为高大上的黑客需要学习哪些基本功? 能盗取账号,能攻击服务器? 再牛的黑客起码是一个合格的程序员 所以说想成为黑客先成为合格的程序再说,说别的就是空谈...

52170
来自专栏华章科技

关于反爬虫,看这一篇就够了

本文来自携程酒店研发部研发经理崔广宇在第三期【携程技术微分享】上的分享,以下为整理的内容概要。墙裂建议点击下方视频,“现场”围观段子手攻城狮大崔,如何高智商&高...

17320

扫码关注云+社区

领取腾讯云代金券