Backend

Location-Based Publish-Subscribe with MySQL

Location-Based Publish-Subscribe

Many location-based mobile apps such as a taxicab app, have two populations of users:

  • 1. Publishers - publish a location-based request - passenger : "get me a taxi at 153 East 53rd Street"
  • 2. Subscribers - subscribe o request at their proximity - taxi driver: "can pick within 5 miles of 350 5th Avenue"

Major classes of such apps include crowdsourcing apps, personal services, personal assistants, errands, pop-up shops and mobile vendors.

Continuous Location Update

Subscribers constantly move, so their subscription changes continuously. This continuous change clearly distinguishes such apps from yellow pages apps, where subscribers, such as restaurants, have a fixed location.

Location update by subscribers is effected in the mobile app by periodically transmitting to the server, via an API call, the current location as obtained from the GPS of a mobile device.

Time-Bounds

Both publication and subscription have a time-bound. No passenger is waiting for a taxi for more than an hour at a location. Work breaks and intermittent cellular coverage may delay location updates, making a subscription to a proximity stale.

MySQL

A location-based publish-subscribe is implemented by basic means using MySQL:

  • 1. MySQL has built-in spatial data points including points, e.g. POINT(15 20)
  • 2. MySQL has built-in UNIX timestamp support as TIMESTAMP data type

Location-Based Database

Publishers:


CREATE TABLE publisher 
(  
    id INT NOT NULL AUTO_INCREMENT,
    user_id INTEGER, 
    user_name VARCHAR(30), 
    request_type VARCHAR(30), 
    location POINT,
    time_created TIMESTAMP DEFAULT CURRENT_TIMESTAMP 
) 

Subscribers:


CREATE TABLE subscriber 
(
  id INT NOT NULL AUTO_INCREMENT,
  user_id INTEGER, 
  user_name VARCHAR(30), 
  subscription_type VARCHAR(30), 
  location POINT,
  time_created TIMESTAMP DEFAULT CURRENT_TIMESTAMP 
) 

Match Publishers with Subscribers

Matching publishers with subscribers is an inner join on distance of locations between publshers and subscribers.

We match subscribers to publishers periodically with the MySQL event scheduler. Once a match is discovered, it is inserted into the matches table.

The built-in DISTANCE function is not accurate, so we need to define a MySQL Geo Distance that computes whether the publisher is within a spherical rectangle of given size:


CREATE FUNCTION MySQLGeoDistance (subscriber POINT, publisher POINT, distance_km FLOAT)
RETURNS BOOLEAN DETERMINISTIC 
RETURNS 

    MBRContains(

        LINESTRING(

            POINT(Y(subscriber) + distance_km / ( 111.1 / 
            	COS(RADIANS(X(subscriber)))), 
            	X(subscriber) +  distance_km / 111.1),

            POINT(Y(subscriber) -  distance_km / ( 111.1 / 
            	COS(RADIANS(X(subscriber)))), 
            	X(subscriber) -  distance_km / 111.1) 

        ),

        publisher

    );

For brevity, we cannot elaborate here on the accuracy of the formula, and on defining the spatial indexes that would improve the performance of the match query.

We run the matching query every minute (or whatever period you want) with the MySQL event scheduler:


CREATE EVENT matched
ON SCHEDULE EVERY 1 MINUTE
DO
BEGIN

   INSERT INTO matches
   SELECT  s.user_id  AS sub_user_id,  s.user_name  AS sub_user_name, s.location, 
   		p.user_id AS pub_user_id, p.user_name AS pub_user_name
   FROM subscriber AS s INNER JOIN publisher AS p
   ON p.request_type = s.subscription_type AND    
         DISTANCE(s.location, p.location, 5)
END;

Matches:


CREATE TABLE matches ( 
  sub_user_id INTEGER, 
  sub_user_name VARCHAR(30), 
  location POINT,
  pub_user_id INTEGER, 
  pub_user_name VARCHAR(30)
) 

Notify Subscribers

We send push notifications to subscribers on each match. To do this we run a cron job that dumps the matches table into a file. Then we scan the file and send push notification to subscribers with all details.

Cron Job

The commands are simple.


sudo crontab -e

Add this line to run every minute:


* * * * * /use/local/push_matches.sh

To run every 5 minutes:


0-59/5  * * * * /use/local/extract_and_push_matches.sh

Bash Script

The script extract_and_push_matches.sh will dump the matches table into a file, then scan the file and send a push notification to the subscriber.

The script is basic bash:


# parameters are set here (omitted for brevity)

# dump into /tmp/matches.txt as a tab separated file
mysqldump -h 127.0.0.1 -P $port -u $username -p $password  \
	--tab=/tmp/matches.txt  --tables=matches lbs_db

# scan the file
cat /tmp/matches.txt | while read line
do

# send push notification with content of line
# elaborated below

done

# delete all matches DELETE FROM matches
mysql -h 127.0.0.1 -P $port -u $username -p $password lbs_db < delete_matches.sql

Push Notifications

Most apps today need to support both iOS and Android. Uniqush is an interoperable push notification server with an HTTP interface tat is easy to set up.

The script will send HTTP requests to the server with curl.

Other open source servers are available, such as the Instagram server for Android.

Handling Matches that Become Real-World Encounters

We assume an API call for the subscriber that notifies the server that an encounter with the publisher did indeed occur. This call will delete the corresponding rows from the publisher and subscriber tables. Similarly, in some apps, a publisher may notify the server that an encounter has occurred. We omit these queries here for brevity.

Bounding Time

Location-based requests have a limited duration, people do not wait for a taxi for a day in the same location, so we need to delete stale published requests with the MySQL event scheduler.

Here we delete requests that are more than 30 minutes old:


CREATE EVENT matched_del_sub
ON SCHEDULE EVERY 5 MINUTE
DO

    DELETE FROM publisher
    WHERE time_created  < (UNIX_TIMESTAMP() - 1800);         # 30 * 60

And a similar event for subscribers.

Match on Arrival

To provide better response time for publishers we can define a trigger on insert to the publisher table that will run the match query:


CREATE TRIGGER publisher_insert AFTER INSERT ON publisher

FOR EACH ROW
BEGIN

   # match query     

END;

Yoram Kornatzky

Yoram Kornatzky