Geospatial queries, reinvented
Location aware applications have undoubtedly become a part of our day-to-day routines, ranging from fitness trackers to directions services and much more. As such an application, Beat has integrated several spatial technologies in its stack, in order to provide the best possible experience to both passengers and drivers.
In this article, we will go through the details of how Beat managed to achieve lightning fast queries during the driver dispatching process; getting the nearest driver to a passenger.
Lots of theoretical stuff coming up, so bear with me.
Spatial Indexing
In a nutshell, spatial indexing refers to a rather broad set of techniques that enable fast and efficient indexing of spatial objects in software applications. Spatial objects can represent points on a plane, polygons of arbitrary shapes, lines and pretty much every geometry. It is supported by several mainstream databases, some of which offering very sophisticated and highly scalable APIs, such as PostgreSQL with PostGIS extension.
Typical applications of such database indexes include, among other, the following:
- Spatial Range Queries: Given a query object, a dataset and a specified threshold, the query returns a subset of the dataset including objects whose distance from the query object is at most equal to the threshold.
- Spatial Joins: Given a dataset, and a query object, the query returns a subset of objects from the dataset that spatially interact with the query object (i.e. intersection, containment, etc).
What all this has to do with Beat
Right from the very first day, Beat had to solve a two-fold puzzle.
First, we have to figure out how many drivers are located around a passenger, and make sure we always dispatch the nearest driver to the passenger, the moment they request for a new ride.
At the same time, we have to keep the drivers’ positions up-to-date and do it fast and cost-effectively. Keep in mind that the driver mobile client sends a position update, based on the device’s GPS tracker data, several times per minute.
On top of that, the above has to scale to several thousands of drivers and passengers that might be connected to Beat in a city every single moment during high demand hours.
The Initial Approach
When Beat started — it’s been 8 years already! — the team was rushing into creating new features and setting up the platform. Apparently, there was no need for performance optimization back then.
Based on that, we decided to use MongoDB. This is a general purpose, document-based database providing full spatial indexing support (with so-called 2dsphere indexes), it’s quite easy to set up and it’s scalable. Furthermore, there are Mongo client libraries for all major programming languages, so we didn’t have to re-invent the wheel, it was just plug-and-play. Happy days, right?
Well, here are some of the reasons why Mongo failed our expectations:
- 2dsphere indexes do not support sharding, so you cannot have a single collection with all drivers’ position split into multiple shards. As a result, the database can only scale vertically, meaning we kept pouring more and more resources into our MongoDB instances in order to maintain the desired performance.
- Spatial indexing with MongoDB turns out be quite expensive in terms of resources, namely high CPU usage during index updates.
- Due to misconfiguration, our PHP Mongo client (yes, we did use PHP for everything back then) did not support connection pooling, so we would run out of connections in the server quite often.
All of the above resulted in slow responses to passengers’ requests, even platform outages, so we ended up looking for a more efficient solution.
Disclaimer: this article is not about how bad MongoDB is (actually, it’s not!). It took several years before the load in our platform was such that MongoDB’s performance was inadequate .
Boosting Our Queries
Searching for an alternative that would work smoothly and support increased throughput took a lot of research.
We could have just picked another off-the-shelf database with spatial indexing support and migrate all our data. Instead, we preferred to move towards a custom solution in order to have full control of update/search operations and be able to apply optimizations, custom-made filters and so on.
The result: A custom database based on Google’s S2 Geometry and Hashicorp’s Go-MemDB.
Google S2 Geometry
S2 Geometry is a framework for decomposing the unit sphere into a hierarchy of cells. It enables fast data representation on a 3D sphere with very low distortion, compared to 2D geometries.
There are 31 hierarchy levels, ranging from zero — 6 “face” cells covering 85 million km² each — all the way up to 30 whose “leaf” cells (there’s 6*4³⁰ of them) each cover an area of just .74 cm². Each cell has 4 descendant cells, except for “leaf” cells. Using cells from different levels, the S2 geometry defines robust constructive (unions, intersections) & boolean predicate (containment) operations, as well as fast area covering (cell unions).
Indexing of S2 cells is done using Hilbert Curves, which is very interesting, but quite out of scope for this article. In our case, the most important part — which also actually makes search so fast — is the fact that the IDs of an S2 cell and its descendants have the same prefix. As a result, you can index cells using structures such as prefix trees (more on this in the next section) and get very fast lookup operations.
Full support for S2 Geometry features is provided for C++, but there are also partial ports for Java, Go and Python, out of which the Go port is the most complete (about 40%). This is more than enough for our purpose.
Hashicorp’s Go MemDB
This is a simple in-memory database, built on immutable radix trees (compact prefix trees). It provides Atomicity, Consistency and Isolation from the ACID set of database properties. Durability is not supported due to its in-memory nature, but you can always backup your data as frequently as you want.
There is full transaction support and, according to the documentation, there is a wide variety of indexing options, ranging from single field indexes to more advanced compound field indexes (that’s actual objects being used as indexes).
Thanks to its underlying immutable data structures, the database provides Multi-Version Concurrency Control (MVCC), which essentially allows for multiple readers, while one writer can perform a transaction on a copy of the data. The data is replaced in the tree after each transaction is completed.
A Search Example
Here is an example demonstrating how to search for objects that are indexed using S2 cells in a Go MemDB. Combining S2 with Go MemDB we have effectively turned spatial indexing into a set of simple prefix tree operations.
Upon insert, every user object is indexed under the right leaf cell ID, based on the user’s latitude and longitude. The cell ID is obtained via the S2 library API.
Using the RegionCoverer class of the S2 library we can identify which cells best cover the are around a specified point. This operation returns a so-called CellUnion.
A CellUnion is guaranteed to not contain overlapping cells, so users within cell and its descendants are retrieved without duplicates, instantly. Great stuff!
Performance Gain
Let me give you some stats about how this setup boosted Beat’s dispatching service performance in production compared to MongoDB.
MongoDB driver position updates have an average 300ms latency, reaching a maximum of ~600ms in one of our biggest production environments. Search queries take an average of 150ms with a maximum of ~400ms.
At the same time, Go MemDB implementation search operations max out at ~20ms latency, with an average of 5ms, which is mind-blowing! Update operations have a very similar latency.
The MemDB database has a very high write throughput — up to ~15K writes/sec have been observed and we are pretty confident it can go way above that.
Our driver search service — which is just an extended version of the code posted above — is deployed on Kubernetes and its setup consists of 3 pods (think VMs, but much lighter), which almost never exceed 200Mb of RAM usage and 100 goroutines each, at any given time.
Tradeoffs
The solution described above has allowed us to substantially speed up the dispatching process. But all this comes at some cost.
Consistency Across Multiple Instances
Production grade services usually require more than one running instances of the same codebase. Having used a memory-backed storage, we had to find a way to keep all instances in sync. Sending users’ location updates over Kafka messages did the trick for us. This solution is both fast and scalable. Every instance of the dispatching app consumes all messages of the position topic, so their databases stay in sync.
Warm Up Time
Beat’s dispatching service is deployed with high availability autoscaling enabled. This means that when resource consumption in pods exceeds a specified limit, new pods are automatically spawned. Each instance of the app takes about 10 seconds to catch up with online users’ positions that arrive through Kafka. The service itself should not accept any requests before that time.
Effort
Last but not least, one should keep in mind that the current setup of Beat’s dispatching service — regardless of how cool it might look — required significant effort for system design and load/performance testing. Not every location-aware app has to be that sophisticated, unless it is critical for its performance.
Interested in discovering the magic behind spatial queries, too? Apply for a role in the Beat Engineering Team.
Fotis Papadopoulos is a Backend Engineer and a member of the Dispatching team at Beat, focusing on software best practices and performance. A DevOps culture advocate with a passion about impactful & disruptive projects.
