Optimization of OpenStreetMap background vector tile production for an on request service: Makina Maps
Implementation of a software stack for serving vector tiles on request. The approach is based on the optimization of OpenMapTiles and the extension of Kartotherian.
This article is an English translation of my own French article from Makina Corpus Blog.
Web and mobile map backgrounds based on data from OpenStreetMap, or alternatives, are distributed in the form of image tiles — called “rasters” — or data tiles — called “vector”. These tiles are the result of the map being divided into a grid. There is a grid for each level of scale (zoom) that we wish to represent.
Vector tiles offer more possibilities than raster. Among these advantages, interactivity or on-the-fly graphic style change directly on the client side (browser or mobile application). On the server side, this also means that the same vector tiles need to be sent to all users, regardless of the graphic style to be applied: the only concern is about serving data.
Makina Corpus wished to set up an on request vector tile service for the generation of OpenStreetMap backgrounds maps called “Makina Maps”.
State of the art
Vector tiles
In the case of online mapping solutions, vector tiles are available at URLs that follow the pattern {zoom}/{x}/{y}.<extentsion>. The extension is .mvt for Mapbox Vector Tiles, but can also be .pbf, the content remaining the same. These tiles are light in size — a few tens or hundreds kilobytes — and describe the geometries and attributes of objects.
The geometries included in the vector tiles are the result of cutting out the original geometries from the tile grid. This content is also filtered and simplified according to the zoom level, both on the geometry and on the attributes and their values, in order to keep the tiles light.
Production of vector tiles
These tiles are pre-calculated and stored to be served by the web server.
In the case of offline applications, these tiles are archived in MBTiles and embedded with the application. But the size, depending on the geographical area to be covered, are quickly huge.
Several software stacks exist to produce these tiles: among the free, and therefore open, solutions are OpenMapTiles and Kartotherian. Note that Mapbox also has its own in-house solution.
Tile production: a heavy industry
All these solutions are used to offer global coverage, they also have in common the fact that they pre-calculate the tiles for the whole world. To produce all the tiles 20 up to 30 days are needed with 8 CPUs to an OpenMapTiles instance. The alternative is to parallelize the calculation on a cluster of machines, to be able to process everything faster, even in one day.
The calculation time of a tile is variable according to the data it contains: it depends of the volume of data but especially of the complexity of the database query to obtain them. The simplest queries, for “empty” tiles of uniform terrain, in the middle of the ocean or the desert for example, take only a few milliseconds. In contrast, a tile at zoom level 14 — the most detailed level in OpenMapTiles — can take up to 15 seconds over complex terrain — while using an SSD database, which is faster read-write than HDD.
Updating OpenStreetMap Data
OpenStreetMap data changes daily and it is preferable to keep its background map updated. Updating is done by applying OpenStreetMap changes to the database (changes called “diff”). This process identifies tiles that contain data that have evolved and need to be regenerated.
Distribution of data
In the case of OpenMapTiles, the database contains three object types.
- First, objects selected in OpenStreetMap because they are desired in the vector tiles.
- These same objects are generalized: simplified, filtered or grouped for use in intermediate zoom levels that do not require the full detail of OpenStreetMap. This generalization is a pre-calculation to make the data lighter. The advantage is that vector tiles can then be produced more quickly.
- For the lowest zoom levels, other external data sources of OpenStreetMap are used. They are even simpler and therefore lighter and particularly suitable for these levels of detail. These include, for example, data from Natural Earth.
This distribution of data, especially with the help of pre-calculations, makes vector tiles faster to produce. The longest tiles to compute are those with the highest level of detail and the heavy in data: zoom 14. In contrast, raster tiles produced under the default OpenStreetMap mapping style — named OpenStreetMap Carto — do not use a generalization step.
Pre-calculation strategy and on request rendering of raster tiles
The strategy for raster tiles is to pre-calculate the low zoom level from 0 up to 13 for example. This is the most time-consuming step, as it involves large volumes of data and simplification calculations. The other zoom levels from 14 up to 20 are calculated and rendered on the fly as image tiles from the database.
Note that where it is mandatory to compute on the server side all zoom levels from 0 up to 20 for raster tiles, vector tiles only go to zoom level 14, which already contains all the details for the following scales. Vector tiles of level 14 should therefore extract and contain more data volume than their raster equivalents.
Statement on strategies and constraints
Low-detail tiles require pre-calculations from generalization in the database or during tile extraction, as they cover large portions of the territory using detailed data in OpenStreetMap. On the other hand, raster solutions can compute tiles for detailed levels on request. Unfortunately, this strategy is not available with vector tiles, because the most detailed level, zoom 14, is heavy.
It would therefore be useful to be able to take advantage of the benefits of rendering on request in software stacks for vector tile generation. The on request service first of all significantly reduces the computing power required. This eliminates the need for the pre-generation stage of all tiles, which, for the whole world, takes weeks or a lot of hardware resources. The other advantage is that the time between updating the data in OpenStreetMap and their availability in the vector map can be reduced.
Bottleneck identification
First of all, an analysis of the performance of vector tile production by OpenMapTiles allows to understand which zoom levels are the slowest.
7.6 tiles/s at z0, 1 tiles in 0:00:00.1
14.4 tiles/s at z1, 1 tiles in 0:00:00.1
3.1 tiles/s at z2, 1 tiles in 0:00:00.3
11.8 tiles/s at z3, 1 tiles in 0:00:00.1
5.5 tiles/s at z4, 1 tiles in 0:00:00.1
3.4 tiles/s at z5, 2 tiles in 0:00:00.5
2.3 tiles/s at z6, 2 tiles in 0:00:00.8
4.6 tiles/s at z7, 2 tiles in 0:00:00.4
3.1 tiles/s at z8, 2 tiles in 0:00:00.6
1.7 tiles/s at z9, 2 tiles in 0:00:01.1
3.8 tiles/s at z10, 4 tiles in 0:00:01.1
4.8 tiles/s at z11, 9 tiles in 0:00:01.8
2.0 tiles/s at z12, 20 tiles in 0:00:09.7
7.0 tiles/s at z13, 80 tiles in 0:00:11.3
0.9 tiles/s at z14, 252 tiles in 0:04:40.0Performance of generation of zoom levels of all tiles in urban areas — Paris area — in tiles per second.
Performance analysis shows that zoom level 14 is clearly below the others.
Given the pre-calculation of generalization and the use of simplified data, the most detailed zoom levels are indeed the slowest. Note that this slowness on the most detailed zoom tiles is magnified exponentially by the fact that each zoom level contains four times as many tiles as the previous one.
The tiles are composed of thematic layers of data. Each layer is the result of a database query. These queries are limited to the geographical extent of the tile but can be more or less complex depending on the thematic and zoom level. It is interesting to look at the tile generation performances for each of these layers.
1,653.2 tiles/s water 252 tiles in 0:00:00.1
5,191.9 tiles/s waterway 252 tiles in 0:00:00.0
253.0 tiles/s landcover 252 tiles in 0:00:00.9
313.6 tiles/s landuse 252 tiles in 0:00:00.7
28,975.5 tiles/s mountain_peak 252 tiles in 0:00:00.0
12,825.7 tiles/s park 252 tiles in 0:00:00.0
905.4 tiles/s boundary 252 tiles in 0:00:00.2
10,076.8 tiles/s aeroway 252 tiles in 0:00:00.0
37.1 tiles/s transportation 252 tiles in 0:00:06.7
1.0 tiles/s building 252 tiles in 0:04:05.2
7,096.4 tiles/s water_name 252 tiles in 0:00:00.0
84.6 tiles/s transportation_name 252 tiles in 0:00:02.9
971.5 tiles/s place 252 tiles in 0:00:00.2
46.8 tiles/s housenumber 252 tiles in 0:00:05.3
52.2 tiles/s poi 252 tiles in 0:00:04.7
15,672.6 tiles/s aerodrome_label 252 tiles in 0:00:00.0Layer generation performance of zoom level 14, in tiles per second.
The buildings layer is by far the most time consuming to produce, with an average extraction time from the database of one second — 1.04 s — per tile. It takes 95% of the total extraction time. It is therefore the prime bottleneck that makes this generation of tiles impracticable for an on request service.
Optimization
OpenMapTiles uses several SQL tables to store buildings according to their attributes or natures in OpenStreetMap. Reducing this number of tables combined with a restructuring of SQL queries makes the database lighter and improves performance.
1.5 tiles/s at layer building, 252 tiles in 0:02:49.6Than the extraction time of the buildings per tile takes only 0.7 seconds. This is a significant gain of about 30%, but is still insufficient for interactive use.
Change of strategy for buildings
Reduction of the multitude
Buildings are a problem because they are numerous, ubiquitous in the city and with a detailed geometry. This “problem” is particularly true in area where buildings was imported in OpenStreetMap — like in France. On a tile of level 14 in a dense urban area, in median value 25,000 buildings are found, the largest tiles have up to 100,000. All these buildings have to be stored, but also indexed and retrieved from the database.
In light of this problem, the first idea could be to use the grouping function — also called clustering CLUSTER of the database. It allows to group together on disk data that will be requested simultaneously from the database. Simultaneous access to the data is based here on the criterion of geographical proximity. Note that this grouping of data in the database can be done during the creation of the database or on demand, but its state is not preserved during updates.
The application of the CLUSTER strategy addresses the problem of data access, but not the one of the volume of objects stored and indexed. This idea of grouping building could be taken up at a topological level. A group — aka cluster — is defined by “close” elements. In the above case the proximity is spatial, but it can also be semantic or visual. A group of close buildings match with the concept city. A small cutting unit is necessary. The lower level on the scale of proximity of buildings is the block.
Even though the PostGIS spatial data extension of the PostgreSQL database has several functions for grouping spatial data — including ST_ClusterIntersecting, which allows to group objects that touch each other — the idea, in terms of computation, is to keep it as simple and fast as possible: group buildings according to an arbitrary grid.
The interest is to no longer store and retrieve individual buildings, but groups of contiguous buildings. If in a rural or sparsely populated urban area this will only make little changes, in a dense urban environment the number of objects processed will be considerably reduced. Nevertheless, a cluster does not merge objects. When creating the vector tiles, the clusters are ungrouped and each building get back its independence. Thus, nothing changes in the content of the produced vector tiles, but the generation performance is significantly improved.
4.4 tiles/s at layer building, 252 tiles in 0:00:56.7This new strategy makes it possible to extract the buildings on average of 225 ms. This is now an acceptable delay for an on request service, even if it is at the upper limit for this use.
Pre-calculation, the dark side
The grouping techniques described can significantly reduce the response time, but a pre-calculation step remains unavoidable. It consists of processing all buildings in an initial calculation to assign them to a cluster. As the number of buildings is large, this calculation duration is not negligible. These clusters must also be stored, which duplicates one of the most important data layers. However, the weight of the clusters table is reduced by half compared to the original table.
When updating data from OpenStreetMap the original table of buildings is modified. The cluster table has to be derived from it again. Unfortunately, this calculation is long: 5 hours for a clustering of all buildings of Europe.
Differential cluster update
Since the full calculation time for groupings is too long, only buildings that have actually changed during updates should be considered. The strategy is to track the changes made in the main table of buildings using observation mechanisms — database trigger — that will keep an history of the changes. This history is then used to reproduce the grouping calculation only on the clusters in which buildings have been changed: only these clusters are ungrouped to update the buildings that have evolved, and then recalculated.
On request vector tile software stack: “Makina Maps”
The two main open source software stacks for pre-calculating vector tiles are OpenMapTiles and Kartotherian. They are made of a set of free softwares that can be composed or interchanged.
In order to distribute vector tiles on request, a web server is necessary but also one or more styles to display them. Other solutions such as TileServer GL — by the developers of OpenMapTiles — are made to serve pre-calculated tiles and styles.
However for an on request service, we need to have all these components: from the database to production of the tiles and styles web service. We also need tiles caching to improve performance and data update from OpenStreetMap. The update should involve invalidation of the tiles cache when the data contained therein has changed.
For the design of Makina Maps, the choice was made to assemble OpenMapTiles for the tiles schema and the database, Kartotherian for the tiles extraction and server. Modules to serve styles have been added to Kartotherian. The whole is exposed through a NGINX web server which also be a tiles cache.
This new free software stack is available on Github, it is light compared to a pre-generation solution. For example, tiles can be used for:
- a French region in 10 min, instead of 1 hour;
- the whole of Europe in 15 hours, instead of a week.
This solution contains everything you need to quickly and simply serve vector tiles and styles from scratch.
Conclusion
The improved performance of OpenMapTiles makes it possible to provide vector tiles on request. By chaining all server components into a single software stack, OpenStreetMap based background vector tiles are more accessible and easy to deploy.
The OpenMapTiles improvements detailed here are proposed for integration into the project source code.
The new Makina Maps software stack is free software available on Github and open for contribution.
