DoorDash recently published an article on how it is solving scaling challenges with content discovery using Elasticsearch and H3, a geospatial indexing system that partitions the world into hexagonal cells.
DoorDash realized that in dense locations at peak times, a single content discovery request would fan out thousands of calls to their internal systems, causing load issues, unsustainable need for horizontal scalability, and unreasonable resource usage. They modified their system to store required content by geographical hexagons instead of keeping data for individual stores. They replaced their content retrieval systems with Elasticsearch to filter out the results by geographical hashes and other attributes.
Image source: Taming Content Discovery Scaling Challenges with Hexagons and Elasticsearch
When a consumer opens the DoorDash app, the backend services fetch a set of stores in the consumer address's deliverable radius, considering the logistical and geographical constraints.
Next, the Discovery Platform calls the Campaign Service to get a list of stores eligible, available, and relevant for the context. The Campaign Service fetches campaigns per store from the database.
A single request would generate thousands of calls in densely populated areas.
Although DoorDash could theoretically scale its system horizontally to handle this load, it wasn't the best use of resources and wasn't sustainable.
At first, they tried to solve this problem by batching the calls instead of getting data for all stores at once. After performance testing, they decided on the optimal batch size. However, this approach didn't support their "ever-growing expansion, selection, and content discovery".
Finally, they decided to reduce the cardinality of the fan-outs by grouping the stores by their geographical location. They looked at existing solutions and finally decided to use H3, a hexagonal hierarchical geospatial indexing system.
H3 is an open-source project. It provides APIs that are suitable for DoorDash needs. Since H3 uses hexagonal areas, it is easier to use it to approximate a circle, which is closer to what DoorDash uses for calculating delivery radii.
Using H3, the team grouped the stores by geo hexagons that helped them condense the data to be retrieved. Instead of retrieving campaigns per store, the discovery platform now could call the campaigns by hex, reducing the number of calls.
The team decided on the optimal H3 resolution level by running the benchmarking tests on what size hexagon they should use. As quoted in the article - "We found that we reached the empirical optimal balance between computational complexity and approximation effectiveness at H3 resolution level of 9."
Once the team finalized using geo hashes for geographical filtering, they also decided to optimize the data fetching. Since they were using Cassandra, they were fetching all data and then doing in-memory filtering. The team realized Cassandra is fast for lookups but cannot handle multiple key filtering.
Based on the existing technologies at DoorDash, they decided to use Elasticsearch to optimize the filtering. They created an Elasticsearch index containing campaign data and could filter efficiently on geohash, start/end date, and time of day.
This led to cost reductions while maintaining high quality and reliability. Particularly, they saved about 50% cost on Cassandra and Redis clusters and around 75% on Kubernetes application hosting.