Blog

EdgeWorkers Use Case: Store Locator

September 8, 2020 · by Josh Johnson and Javier Garza ·
Categories:

Many websites provide a search function to help users find nearby locations such as retail stores. Typically, a store locator service is implemented on-premise or at the cloud origin, searching a database to find physical locations near the user. You can improve the performance of this search by executing it in a serverless function at the Edge with EdgeWorkers.

Finding the nearest store requires three key pieces of information:

  1. User location expressed as latitude and longitude

  2. Store locations, including latitude and longitude

  3. A function to find the closest locations to the user

The first two items are relatively simple. However, writing an efficient function to find the closest locations to the user is deceptively complex. While it sounds easy to calculate the distance of each location from the user and return those with the shortest distance, iterating through hundreds of locations and recalculating distances on every user request is not an efficient use of computing resources.

Instead of determining the distance from every user to every store, you can use spatial indexing to arrange location data into a structure that supports efficient searching. While it’s possible to write your own spatial search algorithms, the process is time-consuming and requires an in-depth understanding of the underlying data structures. 

Fortunately, you don’t need to reinvent the wheel. There is a large library of open-source JavaScript modules available through npm. Dependencies are then packaged into the EdgeWorker module with rollup. In this article, we will show you how to use npm and rollup to include geokdbush and kdbush, two JavaScript libraries that power fast spatial indexing, and search.

Quick start

The result of this tutorial is available on GitHub in the Akamai EdgeWorkers Examples Repository. To view the sample EdgeWorkers project and build the bundle, follow these steps:

  1. Install Git and Node.js, if not already installed

  2. Using Git, clone the source code from the Akamai EdgeWorkers Examples Repository with the command:

git clone https://github.com/akamai/edgeworkers-examples.git

  1. Change the directory into the store locator path and install dependencies from the npm:
    cd storelocator
    npm install

  2. Build the EdgeWorker with npm:
    npm run build

  3. The resulting bundle will be located at “dist/storelocator.tgz”

Learn how to create the store locator service from beginning to end. You can see a demo at: http://edgeworkers.akamaideveloper.com/storelocator. Just enter the latitude and longitude values using the “lat” and “lon” query-string parameters to find out the closest store to the location of your choice. For example, you can use http://edgeworkers.akamaideveloper.com/storelocator?lat=42.262&lon=-84.416 to see the closest stores to Jackson, Michigan. 

User location

To locate stores that are close to the site visitor, we need to know where the user is located. The browser’s geolocation API provides a precise location if the user accepts permissions to access it. For consumers who do not, IP-based geolocation can approximate their location, as described in the Geo-Based Redirect EdgeWorkers Use Case.

Store locations

The next set of information required is a list of store locations. Each location must include the latitude, longitude, and any other data necessary for the store locator service to deliver accurate results. The data can be encoded in a JSON object and deployed with the EdgeWorkers code.

For this example, we will query data from the OpenStreetMap Overpass API to generate a list of locations. Using Overpass Turbo, we search Walmart stores in the U.S. with the query: 

[out:json][timeout:2500];

{{geocodeArea:United States of America}}->.searchArea;

(

  node[brand="Walmart"](area.searchArea);

);

out body;

>;

out skel qt;

When this article was written, this query returned 808 locations. This data is for example purposes only — OpenStreetMap data is not complete, may not contain every store location, and, in some cases, shows multiple nodes for the same store.

mapcode blockcode block

Finding the closest stores

Once we know the locations of the user and stores, the final step is to find the closest stores. As mentioned earlier, looping through every store and calculating the distance to each is not going to be fast. 

Instead, using a spatial index to arrange location data into a structure that supports efficient searching will speed results. To avoid the time and effort of writing the spatial indexing and search logic, we will use geokdbush. Geokdbush is an open source JavaScript library that indexes geographic data in a k-d tree and implements a fast nearest-neighbor search. For more details on spatial indexing and search algorithms, visit https://en.wikipedia.org/wiki/R-tree.

Managing dependencies

As part of the solution, we will use both geokdbush and kdbush. Both libraries are available as npm packages. To start, we will need to create an npm project by executing “npm init” in an empty directory and answering the questions. Be sure to change the entry point to “main.js”. After running “npm init”, a “package.json” file is created that contains project metadata.

$ npm init

This utility will walk you through creating a package.json file.

It only covers the most common items, and tries to guess sensible defaults.

 

See `npm help json` for definitive documentation on these fields

and exactly what they do.

 

Use `npm install <pkg>` afterwards to install a package and

save it as a dependency in the package.json file.

 

Press ^C at any time to quit.

package name: (storelocator) 

version: (1.0.0) 

description: Example store locator service using Akamai EdgeWorkers

entry point: (index.js) main.js

test command: 

git repository: 

keywords: 

author: josjohns@akamai.com

license: (ISC) Apache-2.0

About to write to /Users/josjohns/projects/gss/temp/storelocator/package.json:

 

{

  "name": "storelocator",

  "version": "1.0.0",

  "description": "Example store locator service using Akamai EdgeWorkers",

  "main": "main.js",

  "scripts": {

    "test": "echo \"Error: no test specified\" && exit 1"

  },

  "author": "josjohns@akamai.com",

  "license": "Apache-2.0"

}


 

Is this OK? (yes)

Once the npm project is created, we can install dependency modules. These commands download the kdbush and geokdbush modules into the “node_modules” directory and update the dependencies in the “package. Json” file.:

$ npm install --save kdbush

$ npm install --save geokdbush

Adding location data

Next, we will save our data to a JSON file. In this example, we store the data in “data/locations.json” to save the results from the Overpass search described above. Later, we will use rollup to package this data into an ES module. A small fragment of the location data is shown below — the full file is available on GitHub:

{

  "version": 0.6,

  "generator": "Overpass API 0.7.56.1002 b121d216",

  "osm3s": {

    "timestamp_osm_base": "2020-04-18T20:41:02Z",

    "timestamp_areas_base": "2020-03-06T11:03:01Z",

    "copyright": "The data included in this document is from www.openstreetmap.org. The data is made available under ODbL."

  },

  "elements": [

 

{

  "type": "node",

  "id": 207731972,

  "lat": 34.8850980,

  "lon": -92.1125500,

  "tags": {

    "addr:city": "Jacksonville",

    "addr:country": "US",

    "addr:full": "2000 John Harden Dr",

    "addr:housenumber": "2000",

    "addr:postcode": "72076",

    "addr:state": "AR",

    "addr:street": "John Harden Drive",

    "brand": "Walmart",

    "brand:wikidata": "Q483551",

    "brand:wikipedia": "en:Walmart",

    "name": "Walmart Supercenter",

    "opening_hours": "24/7",

    "operator": "Walmart",

    "phone": "+1-501-985-8731",

    "ref:walmart": "24",

    "shop": "supermarket",

    "website": "https://www.walmart.com/store/24/jacksonville-ar/whats-new"

  }

},

{

  "type": "node",

  "id": 309761248,

  "lat": 28.5361908,

  "lon": -81.2091148,

  "tags": {

    "addr:city": "Orlando",

    "addr:country": "US",

    "addr:full": "600 S Alafaya Trl",

    "addr:housenumber": "600",

    "addr:postcode": "32828",

    "addr:state": "FL",

    "addr:street": "South Alafaya Trl",

    "brand": "Walmart",

    "name": "Walmart Neighborhood Market",

    "opening_hours": "Mo-Su 06:00-24:00",

    "operator": "Walmart",

    "phone": "+1-407-380-0384",

    "ref": "3617",

    "ref:walmart": "3617",

    "shop": "supermarket",

    "website": "https://www.walmart.com/store/3617/orlando-fl/whats-new"

  }

}

  ]

}

EdgeWorker code

Let’s write the code that ties everything together. The code will index the location data upon initialization of the EdgeWorker module. On each HTTP request, we need to read the latitude and longitude from incoming query string parameters, search the indexed data for the nearest two stores, and respond with the result as a JSON object:

import URLSearchParams from 'url-search-params';

 

import KDBush from 'kdbush';

import geokdbush from 'geokdbush';

 

import locations from './data/locations.json'

 

// Initialize index of locations

const indexedLocations = new KDBush(locations.elements, (p) => p.lon, (p) => p.lat);

 

export function onClientRequest(request) {

 

  //Extract longitude and latitude from query string

  const params = new URLSearchParams(request.query);

  const lat = Number(params.get('lat'));

  const lon = Number(params.get('lon'));

 

  // Respond with an error if lat or lon are not passed in.

  if(!lon || !lat){

    request.respondWith(

        400,

        {'Content-Type':['application/json;charset=utf-8']},

        JSON.stringify({error:'lat and lon parameters must be provided'})

      );

      return;

  }

  //var nearest = geokdbush.around(indexedLocations, -83.259, 42.292, 2);

 

  // Find 2 closest locations

  let nearest = geokdbush.around(indexedLocations, lon, lat, 2);

 

  if (!nearest) {

    request.respondWith(

        400,

        {'Content-Type':['application/json;charset=utf-8']},

        JSON.stringify({error:'Error locating nearby locations. lat:${lat}, lon:${lon}'})

      );

      return;

  }

 

  let result = [];

  for (var i = 0; i < nearest.length; i++) {

    let location = nearest[i];

    // calulate distance and convert to miles

    let distance = geokdbush.distance(lon, lat, location.lon, location.lat) / 1.609;

    // add distance and location to the result

    result.push ({distance: distance, location: location})

  }

 

  // Respond with json result containing nearest locations

  request.respondWith(

      200,

      {'Content-Type':['application/json;charset=utf-8']},

      JSON.stringify(result, null, 2));

}

 

To deploy an EdgeWorker, we also need a “bundle.json file” — a manifest that contains the version and description of the EdgeWorker:

 

{

    "edgeworker-version": "0.1",

    "description" : "Returns the closest store locations to the provided latitude and longitude"

}

Bundling the module

With all of the dependencies, data, and code now in the project, we can use rollup to bundle the code into an ES module. The following command installs rollup into the project as a development dependency:

$ npm install rollup --save-dev

We also need a few rollup plug-in modules installed:

# Allow referencing json data file as an ES module

$ npm install --save-dev rollup-plugin-json

# Provide the ability for rollup to resolve node modules

$ npm install --save-dev @rollup/plugin-node-resolve

# Wrap commonjs modules into an ES module

$ npm install --save-dev @rollup/plugin-commonjs

# copy additional asset files

$ npm install --save-dev rollup-plugin-copy-assets

Once the rollup and associated plug-ins are installed, we’ll create the “rollup.config.js” file that contains configuration options for rollup. With this file in place, we can simply execute “rollup -c” from the command line to bundle the EdgeWorker module and associated files into the “dist/work” directory as shown below:

import resolve from '@rollup/plugin-node-resolve';

import commonjs from '@rollup/plugin-commonjs';

import copy from "rollup-plugin-copy-assets";

import json from 'rollup-plugin-json';

 

export default {

// Specify main file for EdgeWorker

input: 'main.js',

 

//Define external modules, which will be provided by the EdgeWorker platform

external: ['url-search-params'],

 

// Define output format as an ES module and specify the output directory

output: {

format: 'es',

dir: "dist/work"

},

 

// Bundle all modules into a single output module

preserveModules: false,

plugins: [

 

// Convert CommonJS modules to ES6

commonjs(),

 

// Resolve modules from node_modules

resolve(),

 

// Copy bundle.json to the output directory

copy({

assets: [

"bundle.json",

]

}),

 

// Package json data as an ES6 module

json()

]

};

To integrate with npm, and complete the packaging process, let’s add a build script in the “package.json” file to execute rollup and build the “.tgz” file:

...,

"scripts": {

    "build": "rollup -c && cd dist/work && tar -czvf ../storelocator.tgz *"    

},
...

Now we can build the EdgeWorker bundle with a single command:

$ npm run build

 

> storelocator@1.0.0 build /Users/josjohns/projects/gss/temp/storelocator

> rollup -c && cd dist/work && tar -czvf ../storelocator.tgz *


 

main.js → dist/work...

created dist/work in 459ms

a bundle.json

a main.js

Adding the EdgeWorker to the Akamai platform

Activating the EdgeWorker on the Akamai platform is a simple process: 

  1. Login to “control.akamai.com” and navigate to “Edge functions”

  2. Create a new EdgeWorker ID, and provide a name and group

  3. Click on the newly created EdgeWorker, create a new version, and upload the EdgeWorker bundle (the “storelocator.tgz” file created in the previous step)

  4. Activate the version to the Akamai staging and production networks

To associate the EdgeWorker with the Akamai property:

  1. Create a new blank rule in Property Manager

  2. Add the “EdgeWorkers” behavior to the rule, selecting the identifier corresponding to the EdgeWorker that you created in the previous step

  3. Add a match condition to execute the EdgeWorker on the “/storelocator” path

  4. Save and activate the new property version

Criteria

The result

Once the EdgeWorkers and properties are deployed, all logic for locating the stores and building the response is performed at the Edge of the Internet, delivering fast performance regardless of where your users reside.

A live demo is available at http://edgeworkers.akamaideveloper.com/ by adding “/storelocator” and sending the latitude and longitude as query string parameters. As an example, you can find the closest stores to Jackson, Michigan by navigating to http://edgeworkers.akamaideveloper.com/storelocator?lat=42.262&lon=-84.416:

The output will looks like this

[

  {

    "distance": 1.2659788494625828,

    "location": {

      "type": "node",

      "id": 4216260835,

      "lat": 42.2499,

      "lon": -84.4345826,

      "tags": {

        "addr:city": "Jackson",

        "addr:country": "US",

        "addr:housenumber": "1700",

        "addr:postcode": "49202",

        "addr:state": "MI",

        "addr:street": "West Michigan Avenue",

        "brand": "Walmart",

        "brand:wikidata": "Q483551",

        "brand:wikipedia": "en:Walmart",

        "name": "Walmart Supercenter",

        "opening_hours": "24/7",

        "operator": "Walmart",

        "operator:wikidata": "Q483551",

        "operator:wikipedia": "en:Walmart",

        "phone": "+1-517-817-0326",

        "ref:walmart": "5160",

        "shop": "supermarket",

        "website": "https://www.walmart.com/store/5160/jackson-mi/whats-new"

      }

    }

  },

  {

    "distance": 32.22093282523531,

    "location": {

      "type": "node",

      "id": 6977481145,

      "lat": 42.7281982,

      "lon": -84.4075709,

      "tags": {

        "brand": "Walmart",

        "brand:wikidata": "Q483551",

        "brand:wikipedia": "en:Walmart",

        "name": "Walmart Garden Center",

        "shop": "garden_centre"

      }

    }

  }

]

 

We hope you enjoyed learning more about how EdgeWorkers can help you refine your location filters! For more information on EdgeWorkers, visit our page. 

About the authors

 

 

Josh

Josh Johnson is an Enterprise Architect at Akamai Technologies where he consults with enterprise customers, enabling development teams to design web applications for performance, security, and reliability. As a DevOps advocate, Josh helps organizations improve quality and efficiency through automation. His experience ranges from small startups to large multi-national corporations. Outside of work, he has mentored competitive and educational robotics teams with students from Kindergarten through 12th grade.

 

Javier

Javier Garza is a developer evangelist at Akamai Technologies where he helps the largest companies on the internet run fast and secure apps by leveraging web performance, security, and DevOps best practices. Javier has written many articles on HTTP/2 and web performance, and is the co-author of the O’Reilly Book, Learning HTTP/2. In 2018, Javier spoke at more than 20 developer-related events around the world, including well-known conferences like Velocity, AWS Re:Invent, and PerfMatters. His life’s motto is: share what you learn, and learn what you don’t. In his free time he enjoys challenging workouts and volunteering for non-profits that support children and education.