The Life and Times of a Policy Engine

As a video streaming service, one of TubiTV’s most important jobs is to ensure that films and TV shows are released according to the terms of their contracts—within the specified time window, on the specified platforms, and in the specified countries. Take Terminator: suppose the contract specifies a window of 7/1 to 10/30 (I’m making this up), available in the US, and restricted to appletv, iphone, roku, and web. If we fail to handle this correctly—letting a Canadian viewer reach it through normal channels, or letting a US viewer access it after the window has closed—that’s a breach of contract and could lead to serious consequences. This is a need that every video streaming service shares.

A film’s window can sometimes be quite complex, with multiple windows coexisting at once. Here’s a made-up example:

• US users can access it on roku and xbox in Q1
• US users can access it on web, iphone, ipad, and android in Q3
• Canadian users can access it on appletv from March to April
• UK users can access it on firetv from 12/1 to 12/15

Rule Engine: Such Feeling Could Only Become a Memory

Modeling this kind of data and delivering fast decisions is no trivial task. As a simple approach, one could build a rule engine that turns each window into an individual rule, then match top-down and return as soon as something matches.

That works fine for small datasets and simple rules, but once the rules grow complex and the catalog scales up a notch, you hit a bottleneck at once. Suppose we need to verify all at once whether 500 films are allowed to play right now, in California, on an iphone. Assume the average number of rules is 5, and that on average you must check 3 of those 5 rules to decide whether playback is allowed—then you need 300 rule executions to finish the check. Now suppose there are 200 requests per second from users; with no cache hit, the worst case means 60k rule evaluations per second.

Clearly, this solution cannot satisfy the people’s ever-growing material and cultural needs—we need to find another path.

Since 2016 at TubiTV, with ever more complex rules, ever richer content, and ever more users, our catalog service has grown slower and slower. Around June, our rule system began to buckle under the load; it was time for a generational upgrade.

Rule Parser: Once the Ocean Is Seen, No Other Water Will Do

After weighing the trade-offs, we ultimately chose to express rules in BNF. The idea is simple: we maintain an expression in the database that describes the rules. Take the earlier example once more:

((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))
...

This turns the work of rule matching into expression evaluation, and efficiency jumps by an order of magnitude at once. The hard part of expression evaluation, though, is turning the expression into a syntax tree with the right tool so that it can be executed. In the C world, of course, there is flex / bison (the upgraded lex / yacc I once used in my compiler course at university), but since our system is built on nodejs, using them directly is inconvenient. So we chose jison—the bison of JavaScript.

Describing BNF (strictly speaking, EBNF) with jison is easy: once the lex is defined, you can define the grammar. I’ve written about this topic before—see the earlier article. I won’t go into detail here.

jison compiles EBNF into a JavaScript file, and then we wrap a simple interface around it (mainly for ease of use) so that other parts of the system can call it. It’s quite efficient and supported our service well.

Yet JavaScript is, after all, an interpreted language; the generated file is complex and not very efficient, and it must be interpreted (yes, I know js has a JIT). Compared with bison generating C code that is then compiled, it’s far slower. And because policy expressions live in the database, every time we want to determine, by id, whether a piece of content may play in a given environment, we also have to read the database (or the redis cache).

Most critically, as TubiTV grew—our content multiplied, our users and traffic grew several-fold, and we supported more and more platforms—the new expression-based policy engine began to buckle under the load as well. We kept it running through sheer effort: adding caches, reducing the amount of content processed on the first call, and so on.

But every so often we’d still get slow API alerts—in some niche countries, the policy engine had to process thousands of titles just to scrape together enough playable content. Because visitors from such countries are few, the cache is usually cold, so everything went through the least efficient path: reading the database, evaluating policy expressions one by one, writing to the cache, and on and on.

Now 2017 has arrived, and the existing policy engine is once again visibly failing to satisfy the people’s ever-growing material and cultural needs…

Policy Engine: Petals Drift and Waters Flow of Their Own Accord

Last night on the train, I got a burst of system alerts. Besides the other issues, quite a few pointed at the policy engine. As I wrote Elixir code, I kept mulling over how to solve the problem.

Suddenly a thought flashed through my mind: why not look for a BNF tool written in Elixir, parse the expression into a syntax tree there, and then use macros to generate code that the pattern-matching engine can optimize?

That way I could generate thousands upon thousands of functions from the ids and policies in the whole database, letting the Erlang VM build an optimized binary search tree?

When humans think, God laughs; when a programmer thinks, the whole family suffers. Back home, I wolfed down a couple of bites and couldn’t wait to dig into bison-like tools for Elixir. I searched high and low without finding anything suitable; only an ABNF one looked halfway decent, so I rolled up my sleeves and dove in. ABNF’s syntax is rather awkward—tokenization requires declaring whitespace explicitly, unlike EBNF where a single line skipping all whitespace lets you ignore the issue. That wasn’t a big deal, though; the bigger problem was that ABNF doesn’t support recursion. Being suddenly forced to convert a recursion-built EBNF into ABNF was very uncomfortable for me; I wrote while flipping through RFC5234 to learn. I struggled until past midnight and still hadn’t gotten it clean. A glance at the clock told me that at this rate I wouldn’t be able to work the next day, so I reluctantly went to sleep.

Even sleep wasn’t sound. My mind was full of thoughts about the unsolved problem. Counting sheep, one thread of my brain replayed the solution while another played A Beautiful Mind for no reason at all. Half-asleep like this until four in the morning, a thought suddenly flashed: why am I clinging to BNF to implement expressions when I have a language that supports quote / unquote? BNF is a tool provided for languages without metaprogramming; I could simply translate the existing expression into an expression Elixir understands, and then Code.string_to_quoted would do the trick.

Over there little Bei, hungry, was calling for her mother, so I gave up my feigned sleep and sheep-counting, leapt up like a carp, and wrote these few lines:

def parse(policy) do
  policy
    |> format_date       # match and convert dates
    |> format_not_in     # replace " not in " with " <~> ", then overload the operator
    |> format_not_equal  # replace " <> " with " != ", which elixir accepts
    |> format_equal      # replace " = " with " == ", since elixir "=" is pattern match
    |> Code.string_to_quoted # string => compiled expr
end

Let’s test it:

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"]]}]}}

Excellent! As the saying goes, hold something in mind and it will echo back. Five hours wasted in vain, overturned in ten minutes.

Next: generate a massive number (100k) of functions and let the Erlang VM’s pattern matching take over and build the binary search tree for me:

This code reads all the video data from the database and then generates parse functions. The VM optimizes them into a binary search tree for efficient access. The database is accessed only at compile time; at runtime we are completely detached from it. You can think of it as a cache—except it’s not a data cache, it’s a code cache.

The core code is just these two snippets, very simple and easy to understand. Benchmarking with benchfella, each policy match takes only 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

I wrote two test cases to compare against the production environment: with 500 policies and no cache at all, the nodejs JISON-based rule parser takes several hundred milliseconds, while the new policy engine takes only tens of milliseconds—a difference of an order of magnitude. I haven’t yet used GenServer and Poolboy for concurrent checks; I expect that doing so will push efficiency up another notch.

Of course, every gain comes with a loss. Runtime efficiency comes at the cost of compile-time inefficiency. On my high-spec mbp, one compile takes 10 minutes. There’s plenty of room for optimization here—for instance, replacing Enum with Experimental.Flow so the work can be partitioned across multiple processes.

When policies change or new content is added, we need to recompile and update the live system. Fortunately, the Erlang VM supports hot reload perfectly, so this is no big deal. The key is still to bring compile time down to the minute level—ten minutes is too long.

At the same time, we need to expose a rest or gRPC API for other systems under nodejs to use. Adding a rest API brings 50-100ms of overhead, but it’s still far better than the previous system.

At noon today I’d originally planned to share with the team how to implement an activity stream in Elixir, but I switched the topic at the last minute to the Policy Engine. On the train home in the evening I was still not satisfied, so I wrote this article. Back home I shared it with my wife, who said: “What a bargain this deal of yours is—you wrote 200 lines of code, first showed off at the company, then went and showed off on your WeChat public account, and now you’re still showing off at home. Three birds with one stone.”

True. But over the past 24 hours I’ve only closed my eyes for 3 hours, and even then I was half-awake mulling over the problem. Is it easy being me?