News for hackers. Stuff that matters.
Re:How we built Uber Engineering's highest query-per-second ... by woeirua on Thursday November 14, 2019 @09:52AM (#21535773)
This is a very inefficient implementation. Really, just poor quality work overall, as anyone with even a basic understanding of spatial indexing would know that an R-tree would be many times faster, as illustrated here: https://medium.com/@buckhx/unwinding-uber-s-most-efficient-s...
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?
Re:How we built Uber Engineering's highest query-per-second ... by paggle on Thursday November 14, 2019 @03:18PM (#21538980)
If you follow American football, your comment reads quite a bit like "Tom Brady has terrible throwing mechanics." Ultimately, it might be right, in some purely academic sense, but in a more relevant sense, good throwing mechanics are those that win you games, and good software implementations are those that meet the business requirements.
Re:How we built Uber Engineering's highest query-per-second ... by buckhx on Thursday November 14, 2019 @11:50AM (#21536930)
Thanks for the shout out. If anyone has questions or comments feel free to reach out.

Also I'm looking for work so if anyone is interested snag my email from my profile.

Re:How we built Uber Engineering's highest query-per-second ... by jorblumesea on Thursday November 14, 2019 @12:11PM (#21537138)
It's funny because had you tried to brute force any of their interview questions (spatial or not) it would have been instant rejection. Often feels like algo analysis is an exercise to get a job and not something engineers actually do, even when required.
Re:How we built Uber Engineering's highest query-per-second ... by woeirua on Thursday November 14, 2019 @12:28PM (#21537334)
The entire line of argument would have been immediately rejected in a phone screening or an on-site interview at any of the major companies, and even many lesser companies that deal with spatial data. Anyone doing spatial queries and not using existing spatial data structures had better have a really good reason for not doing so.
Re:How we built Uber Engineering's highest query-per-second ... by winrid on Thursday November 14, 2019 @11:59AM (#21536995)
I've used RTrees for this too (In Java) and they're great.

Hundreds of thousands of queries a second per cpu core on millions of data points.

Re:How we built Uber Engineering's highest query-per-second ... by _virtu on Thursday November 14, 2019 @11:54AM (#21536956)
I'm currently implementing an rtree in elm. Does anyone have good references about rtrees that they like?
Re:How we built Uber Engineering's highest query-per-second ... by mateo411 on Thursday November 14, 2019 @12:46PM (#21537527)
I think this is the first paper on R Trees.

http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf

[dead]
Re:How we built Uber Engineering's highest query-per-second ... by benburleson on Thursday November 14, 2019 @12:04PM (#21537051)
For future internet-searchers that stumble upon this, it might be helpful to point out that better solutions exist..
Re:How we built Uber Engineering's highest query-per-second ... by rutenspitz on Thursday November 14, 2019 @02:37PM (#21538594)
It would be even more helpful to point out that the article talked about all of this.
Re:How we built Uber Engineering's highest query-per-second ... by jzoch on Thursday November 14, 2019 @12:02PM (#21537036)
While he was a bit rude I wouldnt assume he hasn't built something at this sort of scale.
Re:How we built Uber Engineering's highest query-per-second ... by pc86 on Thursday November 14, 2019 @12:50PM (#21537579)
The vast majority of programmers haven't built something at this sort of scale, so while it's very possible that he has, odds are that he hasn't.
[dead]
Re:How we built Uber Engineering's highest query-per-second ... by woeirua on Thursday November 14, 2019 @12:33PM (#21537391)
Let's just ignore the fact that in this case scale has nothing to do with the actual efficiency of the algorithm they implemented. As the link I posted mentioned, had they used a more efficient algorithm they could have used far fewer resources, or used the same resources to scale up further, with much faster response times overall.
Re:How we built Uber Engineering's highest query-per-second ... by forgottenpass on Thursday November 14, 2019 @01:32PM (#21537969)
99% of people building at "scale" are borrowing bragging rights from a large company they happen to be employed by and/or tools they use while doing zero novel work unique to the size of their deployment.

To say that these paper tigers are above the bikeshedding of all the plebs is quintessential software echochamber.

Re:How we built Uber Engineering's highest query-per-second ... by dang on Thursday November 14, 2019 @02:39PM (#21538615)
"Don't be snarky."

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

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

We've had to ask you to stop doing precisely this in the past:

https://news.ycombinator.com/item?id=19884138

https://news.ycombinator.com/item?id=13587522

Unfortunately, you've continued to post like this frequently. If you keep doing that we're going to have to ban you, so could you please review the guidelines and fix this?