Graphhopper: Potential Improvement: Introduce max Request Time in the Backend

[boldtrn]

Hi,

I just came up with a potential improvement. We have a timeout parameter in the js file. How about adding a timeout to each request in java?

The timeout could be configureable.

Not sure if this makes sense?

Best,
Robin

[karussell]

This is already done on the jetty side (we can configure it somewhere I think). Also we should do this within GraphHopper itself: #473
The current solution via maximum weight is already working but not suitable if the weighting is not seconds nor meters.

Also see potential performance improvements if not using CH #506

[boldtrn]

I guess a nice solution would monitor all requests and check if one request ran longer than allowed. This could keep the performance overhead rather small.

The default seems to have no time out set.

[karussell]

But limiting the request duration should be possible with jetty, not sure if it kills the thread then but if this is available from jetty I woud not want to implement this. Of course making this easily configurable should be our aim

[boldtrn]

Thanks, you are right. I misunderstood your last post. I did a quick research but could not come up with an easy solution. The best I found was:

Include the setMaxIdleTime in the GHServer and make it configureable in the config file. But I am not sure if this setting is doing the trick.

[karussell]

Yes, this looks good.

But I am not sure if this setting is doing the trick.

Why not try it ;) ? They say in the docs that this is highly likely delegated to the JVM via setSoTimeout

BTW: another param was also requested and we can make it configurable as well: connector0.setAcceptQueueSize();

[boldtrn]

Why not try it ;)

I might some day, but not today. BTW: I guess this would be a good first issue ;).

[boldtrn]

I just tried setting setMaxIdleTime (also soLingerTime and stopTimeout) but none worked as expected. I will keep you updated if I find a good solution.

[karussell]

Will maxVisitedNode not work for your use case?

[boldtrn]

No I introduced an endless loop for some rare scenarios (which is already fixed). Due to this I revisited this issue.

[karussell]

But once the endless loop is fixed the maxVisitedNodes can be used? Or why can't you use it?

[boldtrn]

Yes. I was just looking for a prevention. This created some headaches for me in the last days including several GraphHopper restarts. So i figured, something like that would be nice.

[karussell]

@boldtrn maybe you try something like connector0.setIdleTimeout(args.getInt("jetty.idle_timeout", 30) * 1000); where did you find setMaxIdleTime? Or was this for jetty 8?

[karussell]

Hmmh setIdleTimeout does not seem to work

[karussell]

It is not possible on the jetty level according to this mailing list thread https://dev.eclipse.org/mhonarc/lists/jetty-users/msg06601.html

[boldtrn]

Seems to be true :(. I also created a StackExchange Thread some weeks ago. http://stackoverflow.com/questions/36642801/embeded-jetty-kill-request-after-a-given-time

The only answer is about writing it myself using Future. Not sure if we should close this one? Were there any problems corresponding to this issue?

[karussell]

Ups, I just created a SO question as well ... looks like there is no definite answer so will keep it open, as I cannot believe there is no access to the socket settings directly.

Were there any problems corresponding to this issue?

Well I would like to have a simple control mechanism for the GH user for non-CH routes so that they can make sure their user requests do not overload too much their systems. Although this is controllable with maxVisitedNodes now ... hmmh, not sure what to do.

[karussell]

According to the new answers on my question we could only solve this manually, but as we have the maxVisitedNodes in place I would close for now, only if there are still problems for this. Maybe we should set maxVisitedNodes to some limited value already in the config? This won't affect CH but keeps non-CH safer.

Also this low resource filter is interesting: https://www.eclipse.org/jetty/documentation/current/limit-load.html

[boldtrn]

Maybe we should set maxVisitedNodes

Makes sense. We should set it probably quite high. To theoretically allow non-ch calculations across Europe, that way most people do not have to modify it, but still you sever won't hang up forever, but just (5min?).

[arminus]

Maybe we should set maxVisitedNodes to some limited value already in the config? This won't affect CH but keeps non-CH safer.

So how can potential DOS situations be avoided with CH enabled? I take it the Jetty path of controlling this is a dead end after reading through all of the above...

[boldtrn]

@arminus

DOS situations be avoided with CH enabled

Well maxVisitedNodes is not used with CH enabled. You have to enable the flexibility mode for that. If you do so, you should be aware of the problems and how to handle them.
Also IMHO, you should check DOS before actually calling your API. There are lot's of ways to do that, e.g. Cloudflare, API Gateways (e.g. Amazon API Gateway), you name it.

I take it the Jetty path of controlling this is a dead end after reading through all of the above...

Yes, one might implement something like this after jetty and before actually calling GH. See: http://stackoverflow.com/a/36643495/1548788

[arminus]

Also IMHO, you should check DOS before actually calling your API.

Actually, I began to do that by calculating line of sight distances between route points and not passing them on to GH if a max distance threshold is passed...

Cloudflare, API Gateways...

For a commercial solution maybe, not for what I do on a small/non-funded scale. Actually, I'm not worried about an intentional DOS attempt but more about users just clicking "somewhere on the map" (e.g. from Hamburg to Naples) which would result in high loads

http://stackoverflow.com/a/36643495/1548788

I understood this approach was dropped above?

[boldtrn]

Actually, I began to do that by calculating line of sight distances between route points and not passing them on to GH if a max distance threshold is passed...

Sounds like a reasonable approach. Please add it as a PR once it's done. I think this could be beneficial for GraphHopper as well.

intentional DOS attempt but more about users just clicking

Ah ok that is something different.

I understood this approach was dropped above?

Yes because it would be an extra overhead, that is mostly unnecessary.

[arminus]

Please add it as a PR once it's done.

So far I use GH out-of-the-box, so I do this in JS on the client side... (see an example on https://www.xctrails.org/ferrata)

[karussell]

Actually, I began to do that by calculating line of sight distances between route
points and not passing them on to GH if a max distance threshold is passed...

You still should limit max visited nodes to something as otherwise you can still get intended or unintended bad requests

[arminus]

You still should limit max visited nodes to something

as in "somewhere in the GH code"?

[karussell]

No, via a config, see #473

[arminus]

But this is for non-CH only?

[boldtrn]

But this is for non-CH only?

Yes, you might end up in an endless loop if you don't define them. (Only for non-ch)

[karussell]

Yes, you might end up in an endless loop if you don't define them. (Only for non-ch)

It is not an endless loop but a really large one ;)

Maybe we should also include an additional distance protector. E.g. routing from paris to nyc can be excluded up-front and should not trigger a search even if limited to 1mio nodes.

[arminus]

Well, I have CH enabled and still need to protect the server against paris to nyc like routing attempts

[karussell]

Well, I have CH enabled and still need to protect the server against paris to nyc like routing attempts

This should not be a problem with CH although you can still protect it but the benefit would be a lot lower

[arminus]

This should not be a problem with CH

My "blackbox-observation" doesn't quite confirm this... I just ran a test using a rather powerful server with a GH database covering D/A/CH/I, with

graph.flagEncoders=car,foot|blockFords=false,mtb|blockFords=false 
graph.dataaccess=MMAP_STORE_SYNC 
prepare.chWeightings=shortest
prepare.minOnewayNetworkSize=100

->
2016-06-06 15:23:43,486 [qtp131682780-17] INFO com.graphhopper.http.GHBaseServlet - vehicle=foot&weighting=shortest&point=53.56641415275043,10.01953125&point=38.75408327579141,16.5234375&instructions=true&type=json&key=undefined 127.0.0.1 de_DE Mozilla/5.0 (Windows NT 6.1; WOW64; rv:46.0) Gecko/20100101 Firefox/46.0 [53.56641415275043,10.01953125, 38.75408327579141,16.5234375], took:169.19841, , shortest, foot, alternatives: 1, distance0: 2039668.5970157352, time0: 24675min, points0: 27934, debugInfo: idLookup:4.2552485s; , algoInit:0.06761164s, dijkstrabiCH-routing:129.13196s, extract time:36.1786;, algoInit:0.06761164s, dijkstrabiCH-routing:129.13196s, extract time:36.1786, simplify (39272->27934)

took:169.19841 is a lot less as to what I actually observed for the entire request and all the while, GH sucked up some considerable CPU - which to me is a clear indicator that I have to worry about this, especially on a smaller server.

Of course an AJAX request would time out long before, but the calculation on the server is still continuing (and possibly heaping up, since a user might click again and again...)

So I still think a maxVisitedNodes threshold parameter would also make sense for CH routing, i.e. stop and throw a respective exception rather than continuing long after a client timeout.

[karussell]

You are using MMAP and have probably only a few available RAM (?). Then yes, you would also need such a protection. I meant the defaults (RAM+CH=true)

So I still think a maxVisitedNodes threshold parameter would also make sense for CH routing

The current maxVisitedNodes should influence CH too, if not raise an issue as this would be a bug

[karussell]

BTW: If you have a powerful server, then do NOT use MMAP!

[arminus]

You are using MMAP and have probably only a few available RAM (?).

on the production server, yes

The current maxVisitedNodes should influence CH too

Your last comment On April 29 indicated otherwise, but ok, I just reran the test, with

routing.maxVisitedNodes=2000

Just restarted the server, didn't rebuild the DB, though, do I need to? (that'll take some 24hours...)

->

2016-06-06 15:51:43,633 [qtp131682780-16] INFO com.graphhopper.http.GHBaseServlet - vehicle=foot&weighting=shortest&point=53.56641415275043,9.931640625&point=38.85682013474361,16.6552734375&instructions=true&type=json&key=undefined 127.0.0.1 de_DE Mozilla/5.0 (Windows NT 6.1; WOW64; rv:46.0) Gecko/20100101 Firefox/46.0 [53.56641415275043,9.931640625, 38.85682013474361,16.6552734375], took:2.7777863, , shortest, foot, alternatives: 1, distance0: 2048202.6742501908, time0: 24777min, points0: 28002, debugInfo: idLookup:0.7286473s; , algoInit:0.017141698s, dijkstrabiCH-routing:1.1349596s, extract time:0.56115097;, algoInit:0.017141698s, dijkstrabiCH-routing:1.1349596s, extract time:0.56115097, simplify (39533->28002)

much faster now (?!), but according to the simplify info, maxVisitedNodes wasn't taken into account?

BTW: If you have a powerful server, then do NOT use MMAP!

Understood, I only run the tests on the server where I build the GH database, not on the smaller server where I deploy it...

[arminus]

BTW: I'm on GH 0.6

[karussell]

much faster now (?!), but according to the simplify info, maxVisitedNodes wasn't taken into account?

Should work on 0.6 I think but not 100% sure. Maybe you go to the master and use routing.max_visited_nodes? You'll see an exception if the setting protects you...

Maybe we should set maxVisitedNodes to some limited value already in the config?
This won't affect CH but keeps non-CH safer.

Here I meant that one default setting like 1mio would not make CH safer at the same time as there you have just a few K nodes.

[arminus]

routing.max_visited_nodes on 0.6 doesn't have any effect either - I'll try with the master later. Can it load the 0.6 DB?

[karussell]

routing.max_visited_nodes on 0.6

on 0.6 it should be routing.maxVisitedNodes. Also have a look into the json response, there you see how many visited nodes you have and can just use a bit lower value (restart necessary) to see if it throws an exception.

[arminus]

Ok, this does work in the master branch (java.lang.IllegalArgumentException: No path found due to maximum nodes exceeded...) with routing.max_visited_nodes but I get no such exception when setting routing.maxVisitedNodes in 0.6

[karussell]

Strange. Still we won't have the time to fix this in 0.6 as 0.7 will be out next week ...

[arminus]

That's fine, I also spent almost half the day yesterday to prevent routing in case line of sight dist > some max value on the client side (which will not be entirely in vain once I have 0.7 since it also now properly cancels waypoint drags etc.)

[karussell]

Regarding the "dist > some max value" I've created a new issue: #734

[INRIX-Trang-Nguyen]

We have been running into memory and performance issues related to this issue.
At scale, we set a large value for maxVisitedNodes to enable routing against sparse data set.

Are there any improvements planned to map matching to detect cyclical graph traversal and prevent infinite loop without having to rely on maxVisitedNodes? It seems that an edge should not be traversed more than once or have a way to configure the number of re-traversals allowed.