Unwinding Uber’s Most Efficient Service
A few weeks ago, Uber posted an article detailing how they built their “highest query per second service using Go”. The article is fairly short and is required reading to understand the motivation for this post. I have been doing some geospatial work in Golang lately and I was hoping that Uber would present some insightful approaches to working with geo data in Go. What I found fell short of my expectations to say the least…
The post centered around how Uber built a service in Go to handle the problem of geofencing. The core of the geofencing problem is searching a set of boundaries to find which subset contains a query point. There’s a number of standard approaches to this problem and this is the route Uber chose.
Instead of indexing the geofences using R-tree or the complicated S2, we chose a simpler route based on the observation that Uber’s business model is city-centric; the business rules and the geofences used to define them are typically associated with a city. This allows us to organize the geofences into a two-level hierarchy where the first level is the city geofences (geofences defining city boundaries), and the second level is the geofences within each city.
If you asked someone to solve the geofencing problem who had never been exposed to spatial algorithms, this is probably what they would come up with. Color me disappointed that engineers at a company valued at $50b, whose core business revolves around finding things on Earth that are nearby, chose to ignore standard solutions without a concrete reason outside of “it’s too complicated”. It’s particularly disappointing considering Uber bought a portion of Bing Maps engineering based out of Colorado last summer. I used to work on the Bing Maps Streetside team that Uber acquired and I know for a fact that there are quite a few people that know a thing or two about spatial indexing on those teams. One of my interview questions was even how to find which geo-tagged Instagram pictures were of the Eiffel Tower.
