Open-sourcing our Node.js S2 library

Location context is at the center of what we do at Radar. Developers use Radar’s four context types (Geofences, Places, Regions, and Insights) to build amazing location-based app experiences.

Radar’s engineering team has scaled this real-time context infrastructure to over 100M devices and 10,000 qps using caching techniques built in-part on Google’s classic S2 algorithm.

That’s why we’re happy to announce that we’re open-sourcing our Node.js TypeScript bindings for Google’s S2 library to bring the power of S2 to the Node.js developer ecosystem.

Converting a (latitude, longitude) point and a region to S2 cells.

What is it?

The S2 Geometry home page gives a great high-level overview of the library. At its core, S2 is a set of mathematical functions used to map (latitude, longitude) points or regions into S2 cell IDs. This simplifies geospatial indexing and retrieval by converting (double, double) tuples into a single highly cacheable 64-bit integer ID lookups.

Google’s original implementation is written in C++, and official ports exist for Go and Java. Today, we’re thrilled to open-source our TypeScript bindings for the official Google C++ implementation.

Why did we do this?

At Radar, our mission is to make every app on every device contextually aware. To achieve this, we need to build core technologies that allow us to power location context at scale. We needed a solution that would allow us to index and retrieve location data extremely efficiently.

While we knew that S2 was a natural choice to solve this problem, current S2 libraries for JavaScript didn’t fit our needs. For example, we found that some libraries implemented their own custom ID space and used JavaScript strings instead of integers. We found other libraries that did provide JavaScript bindings for the original C++ library, but that did not properly handle the 64-bit integer data type that S2 uses, and had not been maintained for several years. Finally, we couldn’t find any libraries that exposed TypeScript bindings. This was important, as our server is written in TypeScript.

This led us to build our own TypeScript bindings on top of the latest C++ implementation of S2 using N-API and BigInt. Next, we’ll describe how we did it.

How did we do it?

1. Build on N-API

The Node N-API framework is the modern way to build portable native extensions in Node.js with Application Binary Interface (ABI) stability, meaning that libraries built on N-API are compatible with multiple Node versions without any extra code or flags.

Since we were writing our wrapper library in C++, we made use of the node-addon-api header library in order to simplify the usage of the N-API in C++, rather than write C-like code the way that the N-API is used out of the box.

An example of exposing a C++ S2 class in JavaScript is shown below:

/* 
 * s2cellid.cc 
 * 
 * Usage in JavaScript:
 *   const s2 = require('@radarlabs/s2');
 *   const ll = new s2.LatLng(48.8584, 2.2945);
 *   ll.toString();  // "48.8584,2.2945"
 */

#include <napi.h>
#include "s2/s2latlng.h"

Napi::FunctionReference LatLng::constructor;

Napi::Object LatLng::Init(Napi::Env env, Napi::Object exports) {
  Napi::HandleScope scope(env);

  Napi::Function func = DefineClass(env, "LatLng", {
    InstanceMethod("toString", &LatLng::ToString)
  });

  constructor = Napi::Persistent(func);
  constructor.SuppressDestruct();

  exports.Set("LatLng", func);
  return exports;
}

LatLng::LatLng(const Napi::CallbackInfo& info) : Napi::ObjectWrap<LatLng>(info) {
  Napi::Env env = info.Env();
  Napi::HandleScope scope(env);

  int length = info.Length();
  if (length <= 0 || !info[0].IsNumber() || !info[1].IsNumber()) {
    Napi::TypeError::New(env, "(lat: number, lng: number) expected.").ThrowAsJavaScriptException();
    return;
  }

  Napi::Number lat = info[0].As<Napi::Number>();
  Napi::Number lng = info[1].As<Napi::Number>();

  this->s2latlng = S2LatLng::FromDegrees(
    lat.DoubleValue(),
    lng.DoubleValue()
  );
}

Napi::Value LatLng::ToString(const Napi::CallbackInfo& info) {
  return Napi::String::New(info.Env(), this->s2latlng.ToStringInDegrees());
}

The node-addon-api library makes it simple to implement JavaScript classes and functions in C++ without the significant plumbing of worrying about V8 or raw N-API calls.

2. Use BigInt for 64-bit integers

While the JavaScript Number type doesn’t support 64-bit integers (only 53-bit integers or 64-bit floats), the BigInt type introduced in Node 10 allows for arbitrarily large integers. BigInts are declared like Numbers, but have a trailing n on the end of the declaration. For example, you can now do this on Node 10 or above:

// a Number
console.log(Number.MAX_SAFE_INTEGER)  // -> 9007199254740991

// a BigInt
console.log(9007199254740991n * 100n) // -> 900719925474099100n

BigInt allows us to represent S2 cell IDs as a 64-bit uint in an elegant, performant way without having to resort to string serialization.

In the S2 library N-API code, we can expose a BigInt like this:

Napi::Value CellId::Id(const Napi::CallbackInfo &info) { 
  return Napi::BigInt::New(info.Env(), (uint64_t) s2cellid.id()); 
}

Which then allows a JavaScript developer on our engineering team to write a simple call:

const s2 = require('@radarlabs/s2');

// a point in NYC
const nyc = new s2.LatLng(40.7033, -73.98810);
const cell = new s2.CellId(nyc);
console.log(cell.id()); // -> 9926595707078672139n

3. Provide TypeScript bindings

We reaped a number of benefits by introducing TypeScript and static typing in our server codebase: catching various classes of type and null errors, improving developer velocity via autocomplete, static verification and implicit documentation from types, and improving third-party library usage. Given that, it was natural for us to release the library with TypeScript bindings.

You can see the full type bindings of our S2 library here.

Ultimately, we wanted to use technology to help improve our sense of place and make the day-to-day experience better for mobile users everywhere. By open-sourcing the S2 library, we hope to give back to the developer community and nurture the great ideas that aim to improve this everyday experience.

Have any features you’d like to see? Feel free to open an issue on our GitHub repository.

Interested in making apps smarter or working on location tech? We’re hiring!