2

I understand Uber (or any other cab service) server receives the user coordinates through apps. Say I book the cab at 10am. How does Uber know which cab is vacant and nearest to the user coordinate, then notifies that driver?

Say I am at location X of city New York. How does the Uber server know what are the cabs near to location X? Do all cabs send their coordinates to the server at a regular interval of time which the server maintains somewhere in memory and then when a user request comes, it selects the cab which is nearest or is it an altogether different algorithm?

I believe Uber uses spherical geometry services. But I am not sure how it helps in above?

Glorfindel
  • 3,137
  • 6
  • 25
  • 33
user3198603
  • 1,896
  • 2
  • 16
  • 21

3 Answers3

3

Push model

We can have a publisher/subscriber model based Notification Service that broadcasts the current location of drivers to all the interested customers. The server side maintains a list of customers (subscribers) interested in knowing the location of a driver and, whenever there is an update within the region of interest for that driver, the Notification Service sends notifications on the current location of the driver to all subscribed customers.

Pull model

This is as you described, clients send their current location, and the server will find all the nearby drivers from the region of interest to return them to the client. Upon receiving this information, the client can update their view to reflect the current positions of the drivers. Clients can query every five seconds to limit the number of roundtrips to the server.

Pull model is preferred because otherwise an update on subscriber/publisher is complicated. And with pull model, either PostGIS or ElasticSearch supports query from a range of geo locations, so only a region of interest around the client is returned, thus reducing the memory usage.

lennon310
  • 3,132
  • 6
  • 16
  • 33
Jasmine W
  • 45
  • 6
2

Each diver has its status in the central database. To get the nearest one probably they're using approximation so they are taking latitude / longitude of the user, calculate rectangular area on the map and pick the cars within it. Then, after filtering they're able to calculate real distance using road map, which is much more resource consuming.

That's why there's probably at least one or several stages of filtering before real calculation is taking place.

Slawek
  • 2,884
  • 16
  • 16
  • `Each diver has its status in the central databas` .Actually my question is on this part only. Say Uber has 1 million cabs . Does each cab can sends its location after some seconds which uber(or any other large scale cab service) keeps in memory ? If yes i believe they must be caching the data cache clusters something like memcache based on longitude and latitude. Now as soon as book request comes up, it will pick right cache node based on longitude and latitude and then send the push notification to right cab ? – user3198603 Jun 29 '17 at 02:48
1

Each cab has a device which sends its location and driver availablity to a central server.

This allows the central server to work out the closest driver, but also make a decision based on driver rating and other commercial factors.

Ewan
  • 70,664
  • 5
  • 76
  • 161
  • `Each cab has a device which sends its location and driver availablity to a central server.` Actually my question is on this part. Say Uber has 1 million cabs . Does each cab can sends its location after some seconds which uber(or any other large scale cab service) keeps in memory ? If yes i believe they must be caching the data cache clusters something like memcache based on longitude and latitude. Now as soon as book request comes up, it will pick right cache node based on longitude and latitude and then send the push notification to right cab ? – user3198603 Jun 29 '17 at 02:47
  • doing a spherical surface distance calc on a million database rows isn't a particularly expensive operation. Finding the nearest cab is the easy part – Ewan Jun 29 '17 at 07:07
  • But still keeping in memory will be much faster than db . An disadvantage you see apart from cost ? – user3198603 Jun 29 '17 at 14:16
  • its a common misconception that memory is faster than a db. – Ewan Jun 29 '17 at 16:18
  • 1
    can you please why it is misconception ? Generally it is said reading from memory is approx 100x faster than reading from DB . Reason is IO/OS call call where read has to happen from disk platter. That's why real time applications like facebook/whatsapp serves the data from memory instead of DB – user3198603 Jul 01 '17 at 03:14
  • 2
    a: because a db will cache results to memory in any case and b: because indexing means you will read less data – Ewan Jul 01 '17 at 07:15