Redis Commands: Geography Edition

Geo commands are implemented as modular Redis commands for Dynamic Redis.

Dynamic Redis is a simple set of patches on top of regular Redis allowing new commands to load using shared libraries (no need to patch and recompile Redis to add new commands!).

The geo module is distributed as part of Redis Module ToolKit.

Location is important. Everything exists somewhere. Knowing where things are is more and more important in the world. Every mobile phone is a complex location tracking device these days, but how are we using all the data we have access to now?

Location information presents a very basic problem. Location information is inherently four dimesional: (latitude, longitude, elevation) at a given time. For ease of data processing, we tend to ignore elevation and time when presenting location data and only focus on latitude/longitude grid coordinates.

Things exist

Things exist at a location (a latitude and a longitude). We ignore elevation for now. Discovering if one (latitude, longitude) pair is near another requires a two dimensional index. Two dimensional indexing is largely a solved problem, but not as widely implemented as very simple one-dimensional indexing using range searches.

What we need is a way to represent a two dimensional space in only one dimension. For integers, we can use simple space filling curves. We can represent a pair of integer (x,y) coordinates in only one integer, but geographic data isn’t only integers.

In 2008, a public domain implementation for encoding latitude/longitude pairs down to one dimension showed up as geohash. Now we can easily encode our geographic information (minus elevation and time) into one range-searchable entity.

The Geohash

A Geohash is traditionally represented as a base-32 encoded string so locations can be easily shared with a short, easy to type string. Most databases have a way of running range searches over strings, so you can get a rough ability to search based on location, but because it uses a string encoding, each character represents between 1 and 5 bits. It’s not an efficient or accurate encoding for doing range searches.

The Improved Geohash

Nothing about using a Geohash requires you encode it as an ASCII string. And, actually, using the Geohash in raw binary form is much more accurate and precise than a base-32 conversion.

The accuracy of a Geohash depends on its length. A 32-bit Geohash represents an area with an average error of about 600 meters. A 64-bit geohash represents an area with an average error of 18 centimeters. A 128-bit geohash represents an area with an average error of the width of a strand of DNA.

Obviously a 128-bit Geohash is overkill. We don’t need to target DNA with femtodrones (yet). But, going up the scale, a 32-bit Geohash isn’t nearly accurage enough. A 42-bit Geohash gives us an accuracy error of 20 meters. That’s better, but still not great—there would be too much ancillary damage when targeting a person in a 20 meter radius.

A happy a compromise is a 52-bit Geohash. 52-bits gives us accuracy down to 0.6 m (2 ft), which, unless you’re on crowded public transport or at a concert, is about the amount of space a human-sized person takes up in the world.

Geohash Implementation

Ardb, an extended Redis clone written in C++, recently released their integer-only Geohash implementation used in their 2D Spatial Index.

Upon seeing the brilliant non-text-Geohash, I just had to port Geo Indexing back to Redis. (Cross polination of open source projects is great, isn’t it?)

So, I forked their Geohash implementation, bikesheded the heck out of it (formatting fixes, coding convention fixes, friendiler interfaces, some logic improvements) and built Redis Geo Commands around my heavily modified 52-bit Geohash implementation originally provided by Ardb.

Why 52-bits?

Redis stores all scores of sorted set (zset) as type double. Doubles are 64-bit floating point representations—but—they have a special property: 52-bit integers are perfectly represented with no loss of accuracy (as seen in double precision floats have direct representations for 52-bit integers).

By using 52-bit integers for our Geohash, we can attach a two dimensional location to every zset member.

The Geohash encoding guarantees, within known bounds, a range search between a lower range Geohash and a higher range Geohash will include all coordinates between. We get free two dimensional indexing with a simple range search. Awesome.

(Yes, we also cover the 8 + 1 (neighbors + center) search scenarios too.)

Investigate Geohash Storage in Redis

When using georadius or georadiusbymember, you can request the underlying Geohash too by adding withhash to your command.

You can use zset commands directly to investigate the structure of your geoset too:

127.0.0.1:6379> zrange nyc 0 -1 withscores
 1) "wtc one"
 2) "1791873972053020"
 3) "union square"
 4) "1791875485187452"
 5) "central park n/q/r"
 6) "1791875761332224"
 7) "4545"
 8) "1791875796750882"
 9) "lic market"
10) "1791875804419201"
11) "q4"
12) "1791875830079666"
13) "jfk"
14) "1791895905559723"

You could even implement GEOADD yourself by encoding your coordinates with GEOENCODE then using the returned Geohash as the score in a ZADD _zset_ _score_ _member_, but GEOADD provides a nicer interface, and GEOADD enables the special use case of our next section.

Big data real time streaming microservices. (Billion dollars nao, plz.)

Everything is real time. Imagine you have users pushing high frequency location updates. Maybe they are on a train and updating their location once a second. How do you show their location updates in a live view?

Thanks to the magic of Geo Commands combined with Redis PubSub, you can get notified of every location update by subscribing to a geo-themed Redis PubSub channel.

Redis Geo PubSub Channel

All values set by GEOADD generate a Redis PUBLISH event on channel __geo:[geoset]:[member].

Track ALL THE THINGS

Subscribe to all location updates: PSUBSCRIBE __geo:*

Subscribe to location updates for a specific geoset: PSUBSCRIBE __geo:[geoset]:*

Subscribe to location updates for a specific (geoset, member): SUBSCRIBE __geo:[geoset]:[member]

(Usage note: PSUBSCRIBE is “pattern subscribe” and matches anything after * — SUBSCRIBE matches only the exact channel you specify.)

Trivial Use Case

You can imagine a scenario where one user is tracking another in real-time by SUBSCRIBE __geo:members:5331 to track user 5531 in the members geoset.

Bulk PubSub Location Tracking Example

Let’s do a bulk GEOADD while also being subscribed to all geoset PubSub channels in another terminal.

Our performance is pretty good. There is room for improvement in a few areas, but geo commands are perfectly usable for high performance applications today.

This is a series of benchmarks as of the first public geo commands release (0.3).

All benchmarks were run on my 2013 i7 OS X laptop (which is typically faster than my 2008 i7 server). There’s also a good chance these commands were run with redis-server being simultaneously executed by a debugger and introspected by a memory leak checker. Your performance will be better on a non-laptop.

You can easily increase your performance by running multiple redis-server processes on one multi-core server (or on multiple servers). If your server has 8 cores, you can fully utilize it by running 6 to 10 redis-server processes (depending on your workload).