search

rinigus / osmscout-server

Maps server providing tiles, geocoder, and router
https://rinigus.github.io/osmscout-server
GNU General Public License v3.0
164 stars 28 forks source link

Valhalla integration: discussion #132

Closed rinigus closed 7 years ago

rinigus commented 7 years ago

@otsaloma, @M4rtinK:

I would like to start a discussion regarding porting of Valhalla into SFOS and its integration with the OSM Scout Server. Reasons behind it are related to support of routing between multiple countries (https://github.com/rinigus/osmscout-server/issues/65) and, if my first testing is correct, fast route calculation. We would also get access to a well developed routing engine, surely a bonus.

There are few technical issues to be resolved, such as partitioning planet import into the country packages and maybe porting few additional libraries, but, assuming that its all possible, how we would like to interface Valhalla?

I am considering two options:

  1. add Valhalla as a library and let you interface it via OSM Scout Server protocol
  2. add Valhalla as a separate communication stream with a separate port and Valhalla's own protocol

I think that the both options would allow to package it all together with OSM Scout Server (or, as an alternative in the second case separately) and, on OSM Scout Server side, make it rather transparent for the user (just select a routing engine). Here are the advantages that I could come up with regarding the both approaches:

  1. Valhalla as a library

    • transparent for GUI developers - you would have to support only one protocol. As a result, in future, if we want to make or adjust some QtLocation plugin that would be easier.
    • for users, only one setting to change - select routing engine in OSM Scout Server. When compared with the solution 2, if we want to have simple integration for users, we would have to figure out how to communicate the choice of the routing engine between the server and the client. I guess its a complication

  2. Valhalla as a separate protocol

    • you could get immediate support for all Valhalla's features. When used as a library, I would have to implement the features that you want.

From the server point of view, I guess that the work is similar for the cases 1 and 2, maybe a bit less in the case 1. For the case 1, I would have to incorporate an existing Valhalla's code as one of the modules and expand it a bit. For case 2, I would have to port ZeroMQ, CZMQ, and the prime_server to SFOS. Valhalla itself, without daemons, is already running on SFOS.

From RAM usage and overall efficiency, I suspect that solution 1 would be better. Valhalla's daemons are written to provide routing for many and we maybe able to get slightly better efficiency without JSON serialization that occurs while valhalla's internal servers communicate between each other.

Would be great to get your opinion on these matters as you are the ones who would be directly involved with it.

otsaloma commented 7 years ago

This is not a big deal for me either way, whichever you think is best should be fine. Just some things for you to consider:

  1. for users, only one setting to change - select routing engine in OSM Scout Server

I really think you should not provide users with more than one routing engine -- nor geocoder or map rasterizer either! Once Jolla 1 and BTRFS are gone, maybe just forget about space issues, pick the best ones and support those? You do the evaluation, then make it simple for users. (Poor Maps has the same problem, but there the multitude exists mainly because many of the providers are unreliable, and fallbacks are needed.)

  1. Valhalla as a separate protocol: you could get immediate support for all Valhalla's features.

For routing, I don't really need much more than endpoint coordinates and travel mode (foot, bicycle, car), so it doesn't really matter. But, I could imagine some app authors finding distance matrices, map matching or some other features useful. Especially map matching is a very cool thing to use for GPS traces.

So, it doesn't really matter for my use. I don't demand much features and can fairly easily adapt to changes. I can understand the benefit of being able to replace Valhalla, but how likely is that? And could you not just have OSM Scout Server act as a reverse proxy for the Valhalla server? Then, if you need to replace Valhalla, just bump the API version to v2 and transform v1 calls to v2 syntax supporting only the main parameters?

Valhalla's daemons ...

Do you really mean daemons? Would that be allowed in Harbour?

rinigus commented 7 years ago

@otsaloma , thank you very much for the advice!

Re single geocoder/routing/rendering: I'll have to think about it and discuss it as well. It would surely make it easier to use and to develop. However, maybe its actually a question of the best defaults and not asking too many questions from users? If they wish they can change it ...

As for the space issue - I presume the problem is with the devices that don't have any external SD card. And we would probably have a few of those for a while (ported devices without SD card slot, for example).

I will look into polishing the server as soon as the full functionality is there.

Re routing: thanks for pointing out the other important features of Valhalla.

As for replacing Valhalla - no, that wasn't really a plan. Its mainly about ability to swap between libosmscout and valhalla in a transparent manner. [if deemed necessary]

Re proxy: that is surely one way to do that. Except Valhalla would require additional geocoding resolution of end-points. If I would go for Valhalla's protocol, it would be better to keep OSM Scout Server handling out of the way as much as possible.

Valhalla's daemons: you can (and usually do) run Valhalla as services. For SFOS, I would have to make a wrapper application that would run it (or incorporate it into OSM Scout Server). Internally, different processes within Valhalla are communicating as daemons via ZeroMQ. That allows to split them on big iron, but maybe is a bit of an overhead in our case. If I use Valhalla as library, I would be able to communicate between routines without extra transformations of variables (to / from JSON)

As for Harbour - I''ll find the way to make it all compatible

@otsaloma - thank you again. As usual, discussion with you is though provoking.

M4rtinK commented 7 years ago

I mostly concur with @otsaloma - I think it's important to have well working default option, as that what most users will probably use. Ideally, the default option would be good enough that alternatives would not be needed (and would not have to be maintained, etc.).

I think it would make sense to make a table of the currently available & possible routing, geocoding and map rendering options to summarize what are the actual differences, strengths and weeknesses of the different solutions. This might include not just features and performance, but also resource consumption, the project having an active upstream, how hard it is to make it (and keep it) running on Sailfish OS, etc.

The table it might very well show up one solution already ticks all (or an overwhelming majority of) the boxes, so it could be used as the default and other solutions deprioritized/deprecated.

As for the Valhalla integration options I guess I'm kinda gravitating to option 1 as I'm a bit afraid of the performance of running an actual Valhalla zero-mq based "cluster" (even though it would certainly be cool, even just for bragging right ! :) ).

Also I wonder if it might be possible to start with Valhalla as a library and then migrate to separate service later if we find good reasons for that, as I guess OSM Scout Server could just transparently call the Valhalla API to provide it's routing API.

BTW, is the data output somehow limited in priciple by using Valhalla as a library ? Asking mostly because apparently Valhalla can outright generate routing instructions - which can of course be also done on the GUI application side, but the routing engine is in much better position to do that by having much more data to work with than the GUI application. So that's something that I think could be immediately useful & possibly rather plug-and-play (eq. use directions directly from Valhalla if available).

Or is is the issue just that the currens JSON fields can't hold all the data Valhalla can provide ? In such case I can imagine something like add_valhalla_data=true in the query & an extra valhalla_data dictionary in the response. Like that GUI apps could support routing reagardles of backend, with the option to use the additional data if available. Also I guess it might not be needed to export all the data Valhalla can provide like this immediately - just a selected useful subset that could be extended as needed as GUI apps make use of the data.

M4rtinK commented 7 years ago

Also - I really have to add this - thanks a lot for working on all of this, much appreciated! 👍 :)

rinigus commented 7 years ago

Just a short update with the proper reply coming later.

Since I am looking into reducing required Boost version to 1.51, I had to port ZMQ/CZMQ/prime_server anyway and run full Valhalla on the phone. It works quite nicely, with the RSS RAM requirements towards 125MB (concurrency 1, aka only one of each subservers in the cluster). That is when serving Sweden + Denmark. So, from the resources point of view, it seems to be modest.

I will make the table or at least a summary on what we have. And write down what would option 1 and 2 mean for us.

In addition, reading and digging into the code yesterday left an impression that going for option 1 (keeping OSM Scout Server routing protocol and using Valhalla as the brains) would require significant work that maybe is better spent on other things. But let me write the summaries of the options and possible technical solutions. I'll try to do it tonight.

rinigus commented 7 years ago

Let me try to reply regarding current and default options. Unfortunately, the list became rather long. I am sorry for this long reply. In the end, I address Valhalla's integration issue again and propose the solution.

Background

Whole work started by using libosmscout. That library was selected for a simple reason - it offers all-in-one solution to map rendering, search, and routing. While doing so, it manages to keep the databases in a small sizes. However, there are several shortcomings that I had to address leading to the use of specialized backends. With the addition of Valhalla, I would personally use Mapnik/geocoder-nlp&libpostal/Valhalla since that provides the seamless integration between maps as well as great results.

Its possible that in future libosmscout will considerably catch up. But if we want as good solution for SFOS now, we have to look into alternatives.

Overall

RAM

At considered configurations, I think that RAM usage is reasonable. I would expect that libosmscout VS Mapnik/geocoder-nlp&libpostal/Valhalla would use similar amount of RAM (in RSS).

Storage

Storage was found on the basis of the supported planet import. Note that some regions are imported multiple times to support country sub-regions (like Germany)

libosmscout: planet import leads to 31GB - roughly 1/1 ratio with corresponding PBF. That's a strength of this option.

mapnik: 50 GB for planet geocoder-nlp and libpostal: 6GB valhalla: 40GB

Maintenance

All libraries are established and maintained by several people, with the exception of geocoder-nlp that's maintained and developed just by me. When initial porting is done, it should be reasonably simple to maintain the ports, unless the library moves to a newer compiler. Newer compilers would be required by Mapnik, but we could probably use the current version for a while.

Maintenance is greatly simplified if we keep our API (C++ or HTTP) as close as possible to the original library/service, hence this discussion. When adaptation is needed, I am trying to push it upstream to simplify the maintenance.

Rendering

libosmscout rendering is not the best. It has issues with positioning labels on each other, rendering multiple maps is basically done by rendering them one-by-one into the same image (not data layers one-by-one). At current version, libosmscout does not render its maps on world coastlines. All these issues are addressed, but resolving takes time. Mapnik, as a base, solves all these issues.

The both rendering options allow configuration via styles. At present, libosmscout supports day/night styles. Mapnik has a daylight style included, nightlight style has not been developed. Regarding Mapnik styles, probably they have to be developed further, but I am not expert in it.

Geocoding

libosmscout search is rather difficult to use, you have to hit the "correct" query to find something. geocored-nlp is using libpostal and the results seem to be quite good. The only shortcoming of geocoder-nlp is the absence of POI search ("nearby search"), but it should not be too hard to add since I have SQLite database already designed with that in mind. Although, the database will increase due to the indexing by coordinate.

Routing

libosmscout is quite capable, with the limitations of routing only in one region. While libosmscout is faster than OsmAnd (according to a user report), its slower than MoNav and Valhalla, for example. User base of libosmscout routing functionality is also probably limited to SFOS users. As far as I understood, OSM Scout Server was the first major user of it. Hence the bugs that we saw in the beginning of the use.

Valhalla is giving us an ability to merge countries/territories on device. Its also developed professionally and has a large user base. As mentioned above, RAM usage even with the full valhalla routing service seems to be moderate.

As for timing, together with location resolution by geocoder-nlp, routing from Stockholm to Malmö took 10 seconds to compute by libosmscout vs 3 seconds by Valhalla. I suspect that geocoder may take a large chunk of the time in Valhalla's case.

Valhalla integration

Service vs library

I realized that the main issue for me with the Valhalla's integration is that its full HTTP API service. Its written in a way that its not possible to just copy a relevant part and get the route with the instructions. Instead, it has already well-developed HTTP API and it feels wrong to start disassembling it and re-constructing into inferior API that I designed for use by OSM Scout Server.

From maintenance point of view, its the best to have as close to the "plain" Valhalla as possible. That would immediately make it simple to deploy server and allow to develop client programs by following Valhalla's API documentation.

Suggestion: Since you both suggest to focus on a single option, I would go along @otsaloma suggestions and bump HTTP API to v2 for routing and use Valhalla's API over there. The server will use reverse proxy technique and forward the calls over to valhalla and return its replies. That way we can keep the same HTTP port for communication.

Long term and Transition

Assuming that Valhalla's deployment will be success (which I expect), I would suggest:

In long-term, if there will be interested users, we could look into changing libosmscout-based router API into supporting Valhalla's API in some limited form. Alternatively, we can retire it if there are no users using it.

Geocoding and routing

Valhalla does not support geocoding. So, before calling routing one has to resolve the names. I would suggest to call OSM Scout Server geocoder before routing call. So, when taking Poor Maps implementation, to replace https://github.com/otsaloma/poor-maps/blob/master/routers/mapzen.py#L78 by "osmscout" call in OSM Scout Server routing module.

Deployment issues

There are some issues with how to deploy valhalla on devices. Ideally, I would add executable valhalla_route_service and call it as a process from the server. This is not allowed in Harbour. Alternative, is to incorporate valhalla's service into main server as its threads. Not too difficult, but has few drawbacks. I'll raise the issue on sailfish devel list and let's see if Harbour rules can be modified.

otsaloma commented 7 years ago

Sounds good.

Out of curiosity: did you look into OSRM? Is it bigger or more complicated than Valhalla?

rinigus commented 7 years ago

@otsaloma, great!

OSRM: I did not look very much into it. Valhalla was fitting due to the use of tiles which, according to Valhalla's authors. is the big difference with the other options. But I must say that I haven't studied it too closely. Please let me know if I missed something important that you know...

otsaloma commented 7 years ago

My experience is limited to using the APIs and I've found both OSRM and Valhalla to be result-wise good. OSRM is perhaps a bit faster, but its output is quite complicated and difficult to parse.

Valhalla's tiled routing probably does make a lot of sense in this context (not that I quite understand how it works).

rinigus commented 7 years ago

Re tiles: what I learned was that you have to convert a planet in one go leading to a folder full of tiles. Tile names are related to the coordinates. So, later you could just have on the device the tiles that are of interest. But basically, you are working on the same database that can just be split. Now the tricky part is to perform such split. This code I have to write.

rinigus commented 7 years ago

Just to give an overview of the current state:

Missing parts on server's side:

I expect (hope) that I can write the missing part in a week, just to give rough timeline on availability. Then it should be possible to distribute the new version and start working on the clients. Poor Maps is trivial to get supported (it supports Valhalla's protocol already), I would have to look later into modRana as well. I think it is reasonable to have a gap while clients catch up and be a bit relaxed about it.

rinigus commented 7 years ago

Valhalla integration is now implemented with the tile distribution as well. I am closing this issue, thank you very much for your feedback! As soon as the new release is out, we could work on making the clients adjusted to the new protocol.