Sub-millisecond Timezone Resolution
--
Mothership is modernizing the freight industry, which means we have to consider geography in many areas of our platform. We’ve relied heavily on the Google Maps Platform to build out our product, but have been shifting to open source or in-house solutions as we grow.
While this may sound crazy on the surface, there are a number of reasons to move these services in-house:
- Costs as we grow
- Fine-tune results to fit our business needs
- De-risk the business (We can scale location services to meet our needs and not worry about negotiating rate limits, etc.)
- Build in-house expertise
Today we’ll be looking at how we replaced Google’s Time Zone API in our stack.
The Setup
Much like replacing the parts of an airplane while it’s in flight, we need to be confident in the accuracy and performance of any homegrown solutions before we cut traffic away from Google. At the same time, we still want to centralize all of our time zone lookups across our services, giving us a single point to strangle away our calls upstream.
The first step was to design a simplified interface that worked for all of our existing time zone lookups. While Google’s Time Zone API isn’t a huge surface area, it does cover more than we need, like historical lookups. Since we don’t deal with dates in the past, our interface really just needs to return the current time zone identifier — such as America/Los_Angeles or America/Chicago—provided a pair of coordinates.
This turned out to be an embarrassingly simple API: a single POST endpoint that takes in coordinates and returns a timezoneId. Consider this example where we wish to resolve the time zone of coordinates for the town of Random Lake, Wisconsin.
POST /timezone
{
"coordinates": {
"latitude": "43.5554306",
"longitude": "-87.9656231"
}
}
200 OK
{
"timezoneId": "America/Chicago"
}The next step was to build a new service to satisfy this interface where we proxied these requests upstream. Instead of each service calling Google’s APIs directly, we would proxy the request through this new service, where we could collect performance and accuracy metrics. This in-cluster proxy would add very little overhead to the overall latency, and we could be confident that we didn’t lose any accuracy as the data was still coming from Google.
Once we had all time zone lookups running through our new API, we could start experimenting with in-house solutions. While we would continue to use Google’s API for the response we returned to the caller, we could also call our own solution(s) in parallel and collect metrics. Before we could comfortably switch away from Google, we wanted to know that our average latency, error rate (failed lookups), and accuracy rate (did our result match theirs?) were within acceptable levels.
The Strategy
While we were in the design phase, we stumbled upon the open-source project timezone-boundary-builder. This project provides GeoJSON files of the current time zone boundaries from OpenStreetMap data.
The dataset was just a collection of GeoJSON “Features” that identified each time zone. Features are just JSON objects with some metadata (properties) tied to some geometry like points, lines, polygons and more. For example:
{
"type": "Feature",
"geometry": {
"type": "Point",
"coordinates": [125.6, 10.1]
},
"properties": {
"name": "Dinagat Islands"
}
}Armed with a dataset and a dream, we began building out some methods for resolving a time zone from some coordinates.
The First Attempt
Since the dataset is packaged as an array of polygons, the simplest approach would have us iterate over the array and perform a point-in-polygon check on each time zone until we found one that contained our coordinates.
Since point-in-polygon is an O(N) operation with regards to the number of points, we knew this could get expensive fast. The time zone polygons are complex shapes (the Los Angeles time zone polygon contains 28,265 points), so we opted to first check whether or not the point was in the polygon’s bounding box. This turned it into an O(4) constant-time bounds check before running the more expensive point-in-polygon check.
We suspected this approach might yield “good enough” performance, as most time zones would get rejected with the cheaper bounds check.
The performance metrics showed that we were faster than Google’s Time Zone API on average, though we know that’s a result of network latency. Given an upper bound of ~150 ms for round-trip time and lower bound of ~10ms (ping from within our cluster), it seems reasonable to believe most of that 57.5ms average is spent on the network. While serviceable, our first approach was slower than expected and we knew we could do better.
A New Challenger Approaches
Our next attempt incorporated a type of data structure called a quadtree. There are a few flavors/variations, but in general a quadtree’s nodes each have exactly four children or no children at all. We’ve used a region quadtree, which when applied to a two-dimensional space, each node in the tree represents a region of space, with the child nodes representing sub-divisions, i.e. the north-west, north-east, south-west and south-east quadrants.
When you look at a map of the world, it becomes apparent that we could divide it into four quadrants and guide our search by only checking polygons that fall into the same region as our point. If we repeat the subdivision process a few times, it could filter out most polygons that we’d have to check.
Quadtrees are commonly used with points, but our dataset contains polygons. To get them into the tree, we check if the polygon can fit entirely within the region covered by the node. If the polygon crosses a node’s boundary, we leave the polygon in the parent node. Once a node collects enough polygons, we attempt to split it into four children and redistribute the polygons amongst them.
Here’s what our tree looks like when rendered over our time zone data set:
As we learned previously, polygons are complicated shapes and expensive to work with, so our tree uses the polygon’s bounding box for the indexing. This also helps with search performance as checking if a point is inside of a rectangle is much faster than checking if a point is inside of a polygon.
Searching the tree starts at the root and identifies which child node contains our point. We then visit that quadrant (node) and repeat the process until we’re at a leaf node that contains our point (think depth-first search). At the leaf node, we check each stored polygon to see if our point is contained within its bounding box. If not, we work our way back up the tree and check the polygons stored in the parent nodes along the way.
Here’s that process visualized when resolving the time zone for Louisville, Kentucky:
The quadtree approach let us rule out a lot of the time zone boundaries up front. For example, when searching for a location in Los Angeles, the brute force approach had to check 131 boundaries, where the quadtree only checked 13 bounding boxes and 1 polygon.
The performance of our quadtree ended up being better than we expected, and more than sufficient for our needs. At an average of 1.3ms, with the max around 5ms, we were in the territory of being better than Google’s Time Zone API.
Is There A Better Tree?
This isn’t quite the end of the story as we also explored a different kind of tree structure — the R-tree. Our dataset is mostly large polygons which limits our ability to redistribute them across child nodes in our tree. In effect, this creates a very top-heavy tree. We hypothesized that since R-trees are balanced, we’d see faster/more consistent search times.
Performance was similar to using a quadtree, but the R-tree didn’t seem to perform any better on average. We suspect this is because our bounds checks are cheaper than tree traversal, and the number of polygons in the dataset isn’t large enough to allow for the balancing to really help. The details of an R-tree aren’t the focus of this post, but if you’d like to read more here’s a good article on the topic.
In the end, we opted to use the quadtree implementation in production. However, we wouldn’t have known it was the most suitable solution for us if we hadn’t measured the performance. When we get some more time, we’d like to explore what would happen if we broke up the dataset into smaller polygons to confirm our suspicions.
On Accuracy
We discussed performance metrics as we explored the various implementations we tested, but we didn’t touch on accuracy and error metrics. The accuracy and error metrics allowed us to validate the dataset we found, but had little bearing on the approach we used to resolve the time zone. For example, both the quadtree and brute force approach return the same result from our dataset — the latter just being slower than the former.
That said, we did notice some differences between our dataset and the results from Google. Theirs seemed to be fairly accurate, and in the worst case defaulted to the legally observed time zone. For our purposes though, we’re interested in the time zone used by humans in the region, legality be damned.
As it happens, Phenix, Alabama falls within the geographic bounds of the Central time zone but observes Eastern time. Google reports Phenix as observing Central time, and the dataset we use has Phenix recorded as within the Eastern time zone. On the other hand, the towns of Mountain City, Jackpot, Jarbidge, and Owyhee in Nevada are legally in the Pacific time zone but observe Mountain time. Google reports this correctly, but our dataset has these cities in the Pacific zone.
While some of these towns are very sparsely populated (Mountain City is even considered a ghost town) and not likely going to cause an issue for us, we added the ability to adjust our results to more accurately reflect the locally observed time zones should the need arise.
It’s also worth mentioning that we operate primarily in the contiguous United States, so our accuracy results are not likely representative of the entirety of either dataset. Similarly, the differences we detected do not mean Google’s data is wrong or that our dataset is any more or less accurate, we just thought these were fun edge cases worth calling out.
We’re Hiring!
We mentioned we’re building our in-house expertise so we can implement new usages of location services in our product. We also want to tailor these services to better fit the needs of the trucking industry — services as common as navigation have different considerations for truckers than they do consumer vehicles.
There’s a lot more work to be done in this area. Some of the projects we’d like to tackle in the next year
- Using historical shipment and driver density to better predict demand and preemptively direct carriers to areas with more opportunity
- Bring navigation/direction services in-house and improve estimated travel time calculations
- Address geocoding and autocompletion services
- Add more geofenced features to our carrier mobile app
- Improve our machine learning powered shipment dispatching and route optimization processes
We could use all the help we can get. If you think quadtrees were the wrong choice and you could do better, you believe you could help us build any of the aforementioned features, or you just want to build things and write blog posts about them, come work with us.
