News for hackers. Stuff that matters.
Re:How we built Uber Engineering's highest query-per-second ... by dang on Thursday November 14, 2019 @02:29PM (#21538524)
This comment is unacceptable on Hacker News, and I'd like to explain in detail why. Please don't think I'm picking on you personally; we all react like this sometimes. Rather, I want to drive this point home to the community. It's important for discussion quality here!

-----

Please omit swipes like "Really, just poor quality work" and "anyone with even a basic understanding" from your posts to HN. It's great to add relevant information, such as an applicable data structure and a link to a good article on the same topic. But it's not great to put others and their work down, and HN has at least two guidelines that ask you not to:

When disagreeing, please reply to the argument instead of calling names. "That is idiotic; 1 + 1 is 2, not 3" can be shortened to "1 + 1 is 2, not 3."

Please don't post shallow dismissals, especially of other people's work. A good critical comment teaches us something.

Actually, a third guideline is relevant too:

Please respond to the strongest plausible interpretation of what someone says, not a weaker one that's easier to criticize.

The strongest plausible interpretation is not that the engineers lacked a basic understanding of relevant CS—or, for that matter, how to use a search engine, since R-trees would pop up nearly any place you searched about this stuff. The strongest plausible interpretation is that they had some other reason for choosing the implementation they did. For example, perhaps it was efficient enough and they were smartly choosing not to build something more complicated than needed.

https://news.ycombinator.com/newsguidelines.html

Edit: and it turns out that the article explains why they didn't use R-trees.

Re:How we built Uber Engineering's highest query-per-second ... by deminature on Thursday November 14, 2019 @02:57PM (#21538784)
It's disappointing to see a highly-upvoted comment from someone that didn't read the article. The article discusses explicitly why R-trees were not used:

>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.

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
Re:How we built Uber Engineering's highest query-per-second ... by woeirua on Thursday November 14, 2019 @05:29PM (#21540193)
Just about every modern language has a well established R-tree library...
Re:How we built Uber Engineering's highest query-per-second ... by icholy on Thursday November 14, 2019 @11:43PM (#21542253)
I mean why stop there? Let's remove the database indexes too. Hell, why use a hashtable when you have lists amirite?