domenica 15 novembre 2015

Using redis as a base for a spatial model

Recently I've been working with on a server application that could maintain the spatial location of its clients and make them query their neighbours. Following are listed some of the design choices for this project and we discuss how redis is perfect as a base for the spatial computing model.

Design

The system we want to build is a key component for the spatial computing system, its task is to mediate interactions between neighbours and maintain a consistent representation of the network of devices.

As shown in the picture, this system is made up of three exential logical parts.
The connector, is the component of the system that enables network communications between server and devices.
A resource is an object with a type, associated data, relationships to other resources, and a set of methods that operate on it. It models an important concept of the system that can be accessed remotely with standard methods like HTTP GET, POST and PUT.
The model must support a consistent representation of the device network and enables spatial query to be made considering the position of each node. Given the nature of the system, further consideration must be made on the model; data must be fresh and an outdated information must expire after a given time, querying the model should be fast and thread safe and must perform well even with large quantity of data.

In sight of simplicity and the fact that the server should be able to manage as much as requests as possible we decided to build a system that is based on the ReST model.
Using ReST architecture means using a simple client-server request/response protocol for communication, moreover it enables the designer to think about the concept of resource and its representation. Next we define what resources are made of and how they behave in relation to HTTP methods GET, PUT, POST, etc.

Redis Introduction

Redis is an open-source, in-memory data structure storage that is build to work with large quantity of data. It’s simple to use and with a well-made documentation, regardless it offers the following features that makes it perfect of our applicative scenario:

Redis has it’s own set of action that can be performed on data structures, the full set of commands includes:
  • SET and GET to store and fetch information using a key string.
  • SADD and ZADD to add items to a set or sorted set.
  • SREM and ZREM to remove an item from a set or sorted set.
  • GEOADD to add an item with longitude and latitude to a geo index.
  • GEORADIUS to get items from a geo index inside a radius of given meters from a point.

Redis Implementation

Information of one node should be indexed by the network id of our model and the node id itself, this means that we can use these two types of data structure for storing our model:
  • a simple string indexed with a combination of the netId and nodeId for saving all information about a note state (using for example json formalism).
    • that can be made expirable after a given amount of seconds.
  • a geospatial index (geolist) indexed by the netId containing all nodes at a given latitude and longitude.
    • that can be used for neighbourhood search.


The reason we don’t simply use the geospatial index is that redis can’t mark as expirable elements of the geospatial index as well for elements of sets and lists. This means that consistency between the geolist and active nodes in a network should be given by the application, this could be done every time we fetch nodes from a network in four simple steps:

  1. Get the list of node ids from the geolist
  2. For every id in the list fetch the respective string representation from the db
    1. if the string is null mark the node id for deletion.
    2. otherwise parse the string and save the node into a list.
  3. Remove all marked node ids from the geolist in a single redis call.
  4. Return the list of parsed nodes.

Of course because interleaving of these operation can occur, case in which a node is removed from the geospatial index even if it was just added to the network exists. However we consider the price of using synchronism too high to pay since in our scenario we have to deal with devices that continuously update their state and losing track of a device for a given time is expected.

For communicating with redis lettuce was used as a client api, no authentication mechanism was implemented, all needed informations are redis machine ip number and port location.

Redis Error Measurement

Quoting redis.io webpages on distance measurement from two geopoints: “The distance is computed assuming that the Earth is a perfect sphere, so errors up to 0.5% are possible in edge cases.”
We want to test some cases to assert the quality of the measurement for our applicative scenario.

We take some distinctive points in Cesena (Italy):

// Piazza del popolo 44.137199, 12.241922
LatLonPosition piazza = new LatLonPosition(44.137199, 12.241922);
String idPiazza = addNewNode(44.137199, 12.241922);
// Piazza (pappa reale) 44.137560, 12.241320
addNewNode(44.137560, 12.241320);
// Rocca 44.135996, 12.240365.
addNewNode(44.135996, 12.240365);
// via chiaramonti (biblioteca) 44.140027, 12.242564
addNewNode(44.140027, 12.242564);
// via sacchi 3 (facoltà) 44.139623, 12.243427
addNewNode(44.139623, 12.243427);

And we check near places in a range of 100m from Piazza del popolo using the provided range search of redis implemented in the system.

NBR:[
idPappaReale
[pos: [lat:44.13756,lon:12.24132], values: {}, sensors: {}]
Distance: 62.60068090367517
idPiazza
[pos: [lat:44.137199,lon:12.241922], values: {}, sensors: {}]
Distance: 0.0
]

As expected the system shows two nodes, one being the center of the range search. More tests confirms that the georadius function of redis returns the expected values, but since we want to study the quality of these results we check possible error in measuring the distance from two points because that could result in obtaining more or less points from georadius.

Using Google Maps to obtain the “real” distance between two points, we test and see error given by redis.

Real distance
Redis distance
Error
62.45 m
62.60 m
0,15 m
183.67 m
185.13 m
1,46
315.23 m
318.52 m
3,29
295.96 m
274.38 m
21,58
1.07 km
1.07 km
< 0.01 km
669.89 km
670.07 km
0,18 km
642.52 km
642.71 km
0,19 km

Data shows that redis measurement have an error in meters that increases based on the range used for the range search. However since in our scenario we are interested in short distance range search between 5m and 200m at least, the error provided by the application is marginal.

Repository