Our last article on Uber for Business (U4B) discussed implementing our ride profiles feature. Today, we want to share more insight into the kind of technical challenges we’re solving. Just because our mission is to improve businesses’ experiences doesn’t mean we’re writing COBOL and deploying once a year to our server setup from the 1990s. In fact, the Uber for Business team continually pushes the boundaries and has a track record of being the first adopters for our newer platform technologies. Let’s look at the example of what we call ride policies, our way of verifying rides in real time.

 

On the Company, Guaranteed

Imagine you’re running the travel department of your 100-person company. Your 40-strong sales team is constantly traveling all over the globe, going from airport to hotel, hotel to meeting, meeting to dinner, and dinner to the club. Wait, what? Employees often accidentally spend company money on personal errands—and now you’re left sifting through stacks of receipts, expense reports, and TPS reports, trying to figure out which ones to approve.

What if travel managers didn’t even need to look at expense reports to make sure their employees didn’t expense the wrong trip? What if employees didn’t have to worry about picking the right card, collecting receipts, and submitting reports? We hated doing those things ourselves, so we on U4B decided that it was time to simplify this across the board.

 

Enter U4B Policies

For customers using our centralized platform, we added ride policies. The account administrator creates a policy within our web app, and now their employees can only ride when the policy applies. We use this ourselves to offer employees a ride home if they’re leaving the office late, and it works brilliantly. Let’s take a look at how we built this feature.

Ride_Policies_Interface_2016

 

System Requirements

First, let’s figure out some of the U4B policy system requirements. From the customer’s perspective, we need a simple but powerful system that lets users express complex constraints without having to write any code or pseudocode. This is an interesting problem in and of itself, but for brevity’s sake let’s focus on the back-end requirements.

Consider this potential constraint, expressed in English:

“You can ride if it is after 9pm Wednesday–Friday and you are leaving the office.”

It is already evident that our system needs to handle some simple characteristics:

  • Inequality (time > 9pm)
  • Membership (day in [Wednesday, Thursday, Friday])
  • Boolean operands (time and day)

Yet it must also handle some more complex ones, like geospatial conditions (leaving the office). The first three need no explanation; the last we can rewrite to something that seems more familiar. The simplest way to check if someone is “at the office” is checking that the haversine distance between the user’s location and the office is below a given threshold. We can distill this process to two components: a function execution (haversine distance) and another inequality check (distance < threshold).

We also need to be able to evaluate these rules in real time; we don’t want the rider to have to wait while we’re checking if they’re within policy. This means that the upper bound for acceptable performance, even including outliers, is somewhere in the region of tens of milliseconds.

 

Execute Rules Like It’s 1999

Now that we know our requirements, we can start thinking about how to solve this problem. Many engineers will approach it in a broadly similar way:

  1. Define a grammar
  2. Write a parser
  3. Parse the rule into an abstract syntax tree (AST)
  4. Evaluate the AST

This tried-and-true solution can be seen all over the industry. The downside is that this cycle is executed repeatedly for every domain-specific problem. We wanted to push ourselves to do better and create something reusable in a small, clean, and simple way that ends this sadistic cycle. Here’s the challenge:

Using any number of existing tools, write a solution to the above problem in under 30 lines of code.

Before you go dredging up your old textbooks on formal grammars, it’d be wise to consider whether any tools and libraries out there have already solved this problem. The short answer is: there are many. If you’re familiar with projects like PegJS, which will generate a parser for you, you’re probably feeling pretty good knowing that you have just completely cut out step 2.

That’s a great optimization, but we can further save ourselves the trouble of writing code for any of the above steps by combining small, open source modules that already exist. What if, rather than writing our own domain-specific language, we used the subset of a very generic language for which these tools already exist. It’s 2016, so I am of course talking about JavaScript.

While ECMAScript defines how JavaScript should be interpreted, it doesn’t define a single way to parse JavaScript into a consistent format. Luckily, other engineers have defined this. A project to expose an API to the JS parser in SpiderMonkey gave us a lingua franca for JavaScript AST representations, and many tools have sprung up that use this format. This is an extremely powerful thing to have; many of the tools to which we entrust our code quality in the JavaScript ecosystem, such as linters and code coverage libraries, depend on this representation at a low level.

We now have our grammar (JavaScript), and the other two tools we need (the parser and the evaluator) already exist in the form of Esprima and static-eval. Esprima takes some valid JavaScript as input and then outputs an AST. When given a set of facts, static-eval traverses that AST and evaluates it in a safe way.

That leaves us with just a tiny little bit of glue code to complete our challenge:

There’s the basis of our extremely simple rule engine in just seven lines of code. We can now evaluate any valid JavaScript expression:

We are also able to expose functions in order to evaluate more complex rules. Something that would’ve required a change to the grammar, lexer, and parser is now a trivial change:

With a simple application of the haversine Node.js module, we can now implement our check for being at the office.

 

Modular and Extensible

While we were able to implement a simple rule evaluator in just a few lines of code, the real power of this system lies in its modularity and extensibility. In order to get from the user picking some options in the web app to an executable rule, we need to go through a few steps of transformation, separating these steps into layers:

Uber for Business (U4B) Rule Format Diagram

The above diagram broadly categorizes the system into four layers: input, domain, rule, and execution. Let’s consider how our original requirement (“you can ride if it is after 9 pm Wednesday–Friday and you are leaving the office”) traverses through these layers into the final product.

Input

The input layer describes how we allow the user to create the rule. We have already discussed allowing the user to select times from a dropdown menu, but we may wish to let engineers write rules directly in JavaScript or extend the interface to allow for natural language input. For our example, as the user selects options in the UI, we can create a JSON representation of those inputs:


Domain

The domain layer exists to coerce one or more inputs into rules that may be executed. For ride policies, we combine all atomic rules of the same type (e.g., time) with an `||` and rules of different types with an `&&`, but other systems may be different. For example, we may want to represent “6am–9am, or 8pm–1am” for available commute times. This lets us translate from a number of distinct components into a set of rules that must all pass in order for a ride to happen:

Remember that this is a valid JavaScript expression that we can then pass to the rule layer and on to the execution layer (both of which we have covered) at request time. Note that the modularity of the system is also beneficial at evaluation time. If we have a complex rule that requires sourcing a lot of data for facts from other distributed systems, we may wish to optimize the execution with a “lazy evaluator”. We can simply swap out the static-eval module with one that knows how to fetch data from other systems when needed and short-circuits if any of those conditions return false.

 

Request Time

We’ve shown that this system meets all of the rule evaluation requirements while still having a very simple and modular implementation, but does it perform well enough in order to run at request time? To ensure that the system performed well enough to insert into the request flow, the logic that executes when a rider requests a car, we benchmarked the rule evaluator with BenchmarkJS. The mean execution time was around 100 microseconds with a very small variance (0.0001 standard deviation), well within our limits.

This is just one example of the kind of technical challenges that the Uber for Business team solves every day. We have no shortage of them, so if you’re interested in helping us bring the joy of Uber to the world of business, browse through our engineering openings.

 

Will Demaine is a software engineer on Uber’s Business Infrastructure team who has extensively worked on Uber for Business features since U4B was launched in 2014.

Header Image: The interface for setting an U4B ride policy upon the feature’s debut in 2015.

Like what you’re reading? Sign up for our newsletter for updates from the Uber Engineering blog.

0 Comments