Re:How we built Uber Engineering's highest query-per-second ...
by woeirua on Thursday November 14, 2019 @05:27PM
(#21540183)
I did read the article before posting. They don’t actually explain why they opted to not use an R-tree except to say that they think this organizational structure makes sense intuitively. Unfortunately, intuition here is wrong, and the link I posted specifically benchmarks their solution and shows that if they had done even basic benchmarking they would have seen this.
Now there might be a valid argument for this approach if the geofences are changing constantly and reindexing the R-trees would take too long, but in the end they synchronize everything anyways, and the R-tree could easily be generated on another node, serialized and then unserialized asynchronously before swapping to an updated tree.
Re:How we built Uber Engineering's highest query-per-second ...
by icholy on Thursday November 14, 2019 @03:07PM
(#21538881)
R-tree will easily outperform that approach.
Re:How we built Uber Engineering's highest query-per-second ...
by xtomus on Thursday November 14, 2019 @04:45PM
(#21539812)
You can either ship a 2 dimensional linear search approach today or ship an R tree based approach in 2 weeks time. I know which one in choosing if they both meet all of the requirements
>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.