Any Advice to Shorten Traffic Update Interval

[wangyoucao577]

Thanks for the https://github.com/Project-OSRM/osrm-backend/wiki/Traffic, we have succeed to integrate our traffic data into OSRM.

Current Situation:

• Now we can update traffic per 20 minutes for North America based on kubernetes rolling update strategy. But it's too long for us.
• After analyse below log, we found that osrm-customize costs about 10 minutes and osrm-routed costs about 2.5 minutes. (AWS r5.2xlarge, i.e. 8 cpus, 64GB memory). It makes sense since both of them process the whole North America data.

Improve Target:

• Is it possible to let osrm-customize only processes necessary part instead of the whole data, e.g. several cells? We can provide delta traffic data(maybe only 1% per 2-3 minutes), if it's possible we think the osrm-customize can achieve a significant improvement.
• We hope we can shorten the traffic update interval to 2-3 minutes. Any other advice?

Many thanks in advance!

[2019-07-26T20:21:47 UTC] + /osrm-build/osrm-customize map.osrm --segment-speed-file traffic.csv -l DEBUG
[2019-07-26T20:22:46 UTC] [info] Loaded traffic.csv with 76208175values
[2019-07-26T20:22:51 UTC] [info] In total loaded 1 file(s) with a total of 76208175 unique values
[2019-07-26T20:23:10 UTC] [info] Used 535602493 speeds from LUA profile or input map
[2019-07-26T20:23:10 UTC] [info] Used 76202107 speeds from traffic.csv
[2019-07-26T20:23:10 UTC] [warn] Speed values were used to update 76202107 segments for 'routability' profile
[2019-07-26T20:23:13 UTC] [info] Updating segment data took 19415.8ms.
[2019-07-26T20:23:13 UTC] [info] In total loaded 0 file(s) with a total of 0 unique values
[2019-07-26T20:23:31 UTC] [info] Done reading edges in 102861ms.
[2019-07-26T20:24:35 UTC] [info] Loaded edge based graph: 314601014 edges, 77352770 nodes
[2019-07-26T20:24:36 UTC] [info] Loading partition data took 167.905 seconds
[2019-07-26T20:30:56 UTC] [info] Cells customization took 379.771 seconds
[2019-07-26T20:30:56 UTC] [info] Cells statistics per level
[2019-07-26T20:30:57 UTC] [info] Level 1 #cells 364987 #boundary nodes 8661846, sources: avg. 15, destinations: avg. 22, entries: 187827795 (1502622360 bytes)
[2019-07-26T20:30:57 UTC] [info] Level 2 #cells 28984 #boundary nodes 1551129, sources: avg. 36, destinations: avg. 50, entries: 74111441 (592891528 bytes)
[2019-07-26T20:30:57 UTC] [info] Level 3 #cells 1820 #boundary nodes 226793, sources: avg. 84, destinations: avg. 114, entries: 25507158 (204057264 bytes)
[2019-07-26T20:30:57 UTC] [info] Level 4 #cells 61 #boundary nodes 15416, sources: avg. 169, destinations: avg. 225, entries: 3635860 (29086880 bytes)
[2019-07-26T20:30:57 UTC] [info] Unreachable nodes statistics per level
[2019-07-26T20:30:57 UTC] [warn] Level 1 unreachable boundary nodes per cell: 0.00175623 sources, 0.00190966 destinations
[2019-07-26T20:30:57 UTC] [warn] Level 2 unreachable boundary nodes per cell: 0.00814242 sources, 0.00621032 destinations
[2019-07-26T20:30:57 UTC] [warn] Level 3 unreachable boundary nodes per cell: 0.039011 sources, 0.028022 destinations
[2019-07-26T20:30:57 UTC] [warn] Level 4 unreachable boundary nodes per cell: 0.278689 sources, 0.278689 destinations
[2019-07-26T20:30:57 UTC] [info] Unreachable nodes statistics per level
[2019-07-26T20:30:57 UTC] [warn] Level 1 unreachable boundary nodes per cell: 0.0155896 sources, 0.016565 destinations
[2019-07-26T20:30:58 UTC] [warn] Level 2 unreachable boundary nodes per cell: 0.109371 sources, 0.108336 destinations
[2019-07-26T20:30:58 UTC] [warn] Level 3 unreachable boundary nodes per cell: 0.573077 sources, 0.566483 destinations
[2019-07-26T20:30:58 UTC] [warn] Level 4 unreachable boundary nodes per cell: 1.45902 sources, 1.54098 destinations
[2019-07-26T20:30:58 UTC] [info] Unreachable nodes statistics per level
[2019-07-26T20:30:58 UTC] [warn] Level 1 unreachable boundary nodes per cell: 0.121481 sources, 0.112409 destinations
[2019-07-26T20:30:58 UTC] [warn] Level 2 unreachable boundary nodes per cell: 0.77629 sources, 0.699351 destinations
[2019-07-26T20:30:58 UTC] [warn] Level 3 unreachable boundary nodes per cell: 3.21978 sources, 2.91593 destinations
[2019-07-26T20:30:58 UTC] [warn] Level 4 unreachable boundary nodes per cell: 10.4098 sources, 9.4918 destinations
[2019-07-26T20:30:58 UTC] [info] Unreachable nodes statistics per level
[2019-07-26T20:30:58 UTC] [warn] Level 1 unreachable boundary nodes per cell: 0.00241652 sources, 0.00300559 destinations
[2019-07-26T20:30:58 UTC] [warn] Level 2 unreachable boundary nodes per cell: 0.0141112 sources, 0.0143527 destinations
[2019-07-26T20:30:58 UTC] [warn] Level 3 unreachable boundary nodes per cell: 0.0901099 sources, 0.0923077 destinations
[2019-07-26T20:30:58 UTC] [warn] Level 4 unreachable boundary nodes per cell: 0.557377 sources, 0.590164 destinations
[2019-07-26T20:31:35 UTC] [info] MLD customization writing took 36.2444 seconds
[2019-07-26T20:31:48 UTC] [info] Graph writing took 13.3386 seconds
[2019-07-26T20:31:49 UTC] [info] RAM: peak bytes used: 37227970560
[2019-07-26T20:31:49 UTC] + child=133
[2019-07-26T20:31:49 UTC] + wait 133
[2019-07-26T20:31:49 UTC] + /osrm-build/osrm-routed map.osrm -a MLD --max-table-size 8000
[2019-07-26T20:31:49 UTC] [info] starting up engines, v5.22.0
[2019-07-26T20:31:49 UTC] [info] Threads: 8
[2019-07-26T20:31:49 UTC] [info] IP address: 0.0.0.0
[2019-07-26T20:31:49 UTC] [info] IP port: 5000
[2019-07-26T20:34:03 UTC] [info] http 1.1 compression handled by zlib version 1.2.8
[2019-07-26T20:34:03 UTC] [info] Listening on: 0.0.0.0:5000
[2019-07-26T20:34:03 UTC] [info] running and waiting for requests

[wangyoucao577]

From previous issues, the #4449 (comment) might be a solution to achieve real time for some cases, e.g. not a extremely long route.

[wangyoucao577]

One more question: what's the traffic update interval of the demo site(http://map.project-osrm.org)?

[danpat]

Most of the numbers you've posted look reasonably normal, except this one:

[2019-07-26T20:30:56 UTC] [info] Cells customization took 379.771 seconds

The cell customization step is highly parallelizable, you can speed this bit up by providing more CPUs (e.g. 16 or 32 cores, if you have them available).

You can also speed up the boot of osrm-routed by using the osrm-routed --mmap file.osrm flag - this avoids loading the data into RAM. Assuming your box has sufficient RAM that all the datafiles will be in the filesystem cache from the osrm-customize step, you should see fast startup and fast queries. If files aren't in the filesystem cache, some queries may be slow until the filesystem cache is warmed up.

Other than that - this is about how fast OSRM is. It's certainly possible to design a system that will ingest traffic faster, but the price you will pay is in query performance. If you need faster turnaround times, I'd suggest you split your dataset into smaller pieces (regions), and run them all in parallel. This assumes you don't need support for long-distance queries that may cross a partition.

[wangyoucao577]

@danpat Thanks very much for the very quick reply.

For the customize part, I'll have a try when I have 16 or 32 cores machine. But if my traffic data input can be very small, is it possible to let osrm-customize only process necessary part? In another word, if there's no new traffic.csv passed in, the osrm-customize can return immediately at second call.

The --mmap suggestion looks good, I'll have a try.

[CodeBear801]

@danpat and @daniel-j-h Do you think its reasonable to do customization based on delta traffic from previous version?

Current OSRM-Customize strategy is:

• Load csv data into a sorted array
• Iterate from/to pairs in OSRM data to update segment cost
• Execute customize::customize, which will re-calculate cost for boundary nodes of all cells, level by level.

For each cell, re-calculate all boundary nodes' cost is needed as long as there is cost change inside, but for cells with no cost change, theoretically we don't need to touch them.

Based on traffic data from professional sources, about 30% of segments in the graph have traffic coverage but only very small part of them will update minute to minute. If we could add an additional command line option which deal with delta traffic it could dramatically decrease customization time.

We will do some profile to see the cell influence ratio based on delta traffic first.

[wangyoucao577]

Below logs were generated when start up osrm-routed with --mmap. Compared with previous log, osrm-routed initialization time reduced from 130s to 57s, totally 73 seconds saved.

[2019-08-02T21:28:59 UTC] + /osrm-build/osrm-customize map.osrm --segment-speed-file traffic.csv -l DEBUG
[2019-08-02T21:29:49 UTC] [info] Loaded traffic.csv with 76208175values
[2019-08-02T21:29:54 UTC] [info] In total loaded 1 file(s) with a total of 76208175 unique values
[2019-08-02T21:30:12 UTC] [info] Used 535602493 speeds from LUA profile or input map
[2019-08-02T21:30:12 UTC] [info] Used 76202107 speeds from traffic.csv
[2019-08-02T21:30:12 UTC] [warn] Speed values were used to update 76202107 segments for 'routability' profile
[2019-08-02T21:30:15 UTC] [info] Updating segment data took 18170.4ms.
[2019-08-02T21:30:15 UTC] [info] In total loaded 0 file(s) with a total of 0 unique values
[2019-08-02T21:30:33 UTC] [info] Done reading edges in 94133.6ms.
[2019-08-02T21:31:35 UTC] [info] Loaded edge based graph: 314601014 edges, 77352770 nodes
[2019-08-02T21:31:36 UTC] [info] Loading partition data took 156.536 seconds
[2019-08-02T21:37:54 UTC] [info] Cells customization took 377.949 seconds
[2019-08-02T21:37:54 UTC] [info] Cells statistics per level
[2019-08-02T21:37:55 UTC] [info] Level 1 #cells 365014 #boundary nodes 8660415, sources: avg. 15, destinations: avg. 22, entries: 187754785 (1502038280 bytes)
[2019-08-02T21:37:55 UTC] [info] Level 2 #cells 28909 #boundary nodes 1547423, sources: avg. 36, destinations: avg. 50, entries: 73984124 (591872992 bytes)
[2019-08-02T21:37:55 UTC] [info] Level 3 #cells 1822 #boundary nodes 228172, sources: avg. 84, destinations: avg. 115, entries: 25856388 (206851104 bytes)
[2019-08-02T21:37:55 UTC] [info] Level 4 #cells 60 #boundary nodes 15566, sources: avg. 173, destinations: avg. 230, entries: 3726667 (29813336 bytes)
[2019-08-02T21:37:55 UTC] [info] Unreachable nodes statistics per level
[2019-08-02T21:37:55 UTC] [warn] Level 1 unreachable boundary nodes per cell: 0.00179445 sources, 0.00194787 destinations
[2019-08-02T21:37:55 UTC] [warn] Level 2 unreachable boundary nodes per cell: 0.00861323 sources, 0.00664153 destinations
[2019-08-02T21:37:55 UTC] [warn] Level 3 unreachable boundary nodes per cell: 0.0444566 sources, 0.0290889 destinations
[2019-08-02T21:37:55 UTC] [warn] Level 4 unreachable boundary nodes per cell: 0.316667 sources, 0.283333 destinations
[2019-08-02T21:37:55 UTC] [info] Unreachable nodes statistics per level
[2019-08-02T21:37:56 UTC] [warn] Level 1 unreachable boundary nodes per cell: 0.0157199 sources, 0.0167172 destinations
[2019-08-02T21:37:56 UTC] [warn] Level 2 unreachable boundary nodes per cell: 0.110104 sources, 0.109481 destinations
[2019-08-02T21:37:56 UTC] [warn] Level 3 unreachable boundary nodes per cell: 0.586718 sources, 0.572997 destinations
[2019-08-02T21:37:56 UTC] [warn] Level 4 unreachable boundary nodes per cell: 1.51667 sources, 1.5 destinations
[2019-08-02T21:37:56 UTC] [info] Unreachable nodes statistics per level
[2019-08-02T21:37:56 UTC] [warn] Level 1 unreachable boundary nodes per cell: 0.121524 sources, 0.11242 destinations
[2019-08-02T21:37:56 UTC] [warn] Level 2 unreachable boundary nodes per cell: 0.777924 sources, 0.701685 destinations
[2019-08-02T21:37:56 UTC] [warn] Level 3 unreachable boundary nodes per cell: 3.21515 sources, 2.90999 destinations
[2019-08-02T21:37:56 UTC] [warn] Level 4 unreachable boundary nodes per cell: 10.8667 sources, 9.8 destinations
[2019-08-02T21:37:56 UTC] [info] Unreachable nodes statistics per level
[2019-08-02T21:37:56 UTC] [warn] Level 1 unreachable boundary nodes per cell: 0.00245744 sources, 0.00307385 destinations
[2019-08-02T21:37:56 UTC] [warn] Level 2 unreachable boundary nodes per cell: 0.0143208 sources, 0.0148051 destinations
[2019-08-02T21:37:56 UTC] [warn] Level 3 unreachable boundary nodes per cell: 0.0938529 sources, 0.0944018 destinations
[2019-08-02T21:37:56 UTC] [warn] Level 4 unreachable boundary nodes per cell: 0.7 sources, 0.733333 destinations
[2019-08-02T21:38:32 UTC] [info] MLD customization writing took 35.1301 seconds
[2019-08-02T21:38:46 UTC] [info] Graph writing took 14.6054 seconds
[2019-08-02T21:38:47 UTC] [info] RAM: peak bytes used: 37251137536
[2019-08-02T21:38:47 UTC] + child=133
[2019-08-02T21:38:47 UTC] + wait 133
[2019-08-02T21:38:47 UTC] + /osrm-build/osrm-routed map.osrm --mmap -a MLD --max-table-size 8000
[2019-08-02T21:38:47 UTC] [info] starting up engines, v5.22.0
[2019-08-02T21:38:47 UTC] [info] Threads: 8
[2019-08-02T21:38:47 UTC] [info] IP address: 0.0.0.0
[2019-08-02T21:38:47 UTC] [info] IP port: 5000
[2019-08-02T21:39:44 UTC] [info] http 1.1 compression handled by zlib version 1.2.8
[2019-08-02T21:39:44 UTC] [info] Listening on: 0.0.0.0:5000
[2019-08-02T21:39:44 UTC] [info] running and waiting for requests

[danpat]

totally 73 seconds saved.

Just be aware - using --mmap causes data to be read from files on-the-fly when queries start to happen, instead of all the disk reading being front-loaded when osrm-routed is used in its default mode.

If the files are already in the operating system's page cache, then performance should be very close to having the data in RAM already. If the files are not in the page cache, or you have other processes on the system that are causing your routing data to be evicted from the page cache, then query performance can be affected.

The ideal setup is one where you:

a) have no swap enabled
b) have no other active processes on the machine
c) download the already-processed files from a remote server

If you do all three of the above, then all file contents should be in the page cache when you start osrm-routed, and startup should be fast, and query performance should be good.

One other thing to watch out for, especially in a potentially shared hosting environment, is filesystem cache evection - if you're using Docker, other containers on the same host may evict critical pages from the cache, leading to poor query performance when those pages are needed for a routing query.

[danpat]

@CodeBear801 Yes - you should be able to skip re-customization of the lowest-level cells if no data has changed (these are the most numerous, and avoiding recalc would save the most time). It's been a while since I've looked at this part of the code, so I'm not sure how much change would be needed to re-read the existing cells into this part of the code.

As a minor segue - depending on how ambitious you are, another approach to save a bunch of time would be to make osrm-customize a persistent process - if you look at the timing logs, significant time is spent just loading data on each iteration. One idea I had a while back was to make osrm-customize a daemon process that you would send signals to to re-process, avoiding the cost of re-loading data each time. Never got the time to implement it though.

[CodeBear801]

@danpat Agree. Make osrm-customize a stand along daemon process could save loading time for frequent customization.

Based on the profile, for each round of osrm-customize will take 10 minutes: 1 minute to load speed.csv, 3 minutes to load osrm data and 6 minutes to do customization. We plan to use OSRM to enable both live traffic + personalized information, I think quick turn around is needed for traffic accident and personalized metric. Our target is making live traffic to be ready as soon as possible, at seconds or around one minute level.

• Using demon process could save the part of "3 minutes to load osrm data". This will make sure file contents in the page cache and could also save time for routed. Will do different experiments with @wangyoucao577
• "1 minute to load speed.csv" is due to there are too many contents to be updated:76 million lines and 2.6GB file in physical size for speed.csv. We also think using compact file format or use more complex logic to separate file loading and content transformation, but that won't help much since so many contents exists there. Decrease the content to be updated would be a obvious way to optimize here.
• "6 minutes to do customization" is a big part. We will carefully working on this part and start with profiling. In my opinion, if we want routing algorithm to represent liveness as quick as possible, then customization should be very fast and routed(query) could always based on fresh upraded graph. Current customization already using TBB to parallel execution on different cells and pre-allocation space for metric holds value for source and destination pair of each cell, based on our code analysis here, here and here. To speed up this part avoid touching unchanged cells would be our first experiment.

[danpat]

A simpler alternative might be to use a smaller map - have you considered slicing up North America into 1/4-sized chunks with decent overlap?

Realtime traffic is generally irrelevant for long-distance routing, so if you have a fallback for long routes that doesn't update frequently, it likely doesn't matter too much.

[wangyoucao577]

@danpat For #5503 (comment) and #5503 (comment), my understanding is that whatever the data in cache or not, the osrm-routed loading should be very fast once I start it by --mmap, right? So my question is why there's still 1 minute cost by loading? I think we may have to read code to see what possibly happened.

[2019-08-02T21:38:47 UTC] [info] IP port: 5000
[2019-08-02T21:39:44 UTC] [info] http 1.1 compression handled by zlib version 1.2.8

I agree that a clean server is necessary for ideally --mmap setup, but it's not easy to get since I deployed it based on docker in kubernetes cluster. I can disable swap and make sure no other user process, but kubernetes related processes are not controllable. We also have some other containers have to run in same cluster/server for monitoring. All these kubernetes processes/containers may possible to influence query performance but incontrollable.
So I think we should do some benchmark for query performance to see whether the falloff can be acceptable for now. We can enable it until getting better solution done if it's acceptable.

One more question: what do you mean for "c) download the already-processed files from a remote server"?

[wangyoucao577]

@danpat For #5503 (comment), a long-distance route mostly can be split to 3 parts:
a) origin->highway entrance
b) highway entrance -> highway exit
c) highway exit -> destination

Only part b) may irrelevant with realtime traffic. Both a) and c) require realtime traffic for better route. Even for part b), we still possible to get better highway entrance and exit with realtime traffic.

[danpat]

One more question: what do you mean for "c) download the already-processed files from a remote server"?

Here, I meant don't run osrm-extract/partition/customize on the same server you run osrm-routed on. These tools need memory for temporary tasks, and may evict some of the pages you want from the page cache. By downloading already processed files from somewhere else, you can be sure that the entire fileset is in the page cache (the act of downloading and writing to disk will populate those pages). I only mention it to be sure you've considered all the implications of using --mmap.

As for the 1-minute startup time - it's possible not all of the datafiles are being mmap()-ed - it's been a while since I've reviewed the entire pipeline. I suspect the .ramIndex file may not be mmapped, but you'd have to read the code to be sure.

[danpat]

Only part b) may irrelevant with realtime traffic. Both a) and c) require realtime traffic for better route. Even for part b), we still possible to get better highway entrance and exit with realtime traffic.

Remember that by the time the traveller arrives at part (c), the traffic data used to calculate the route is probably very stale, particularly for long routes. Generally, what you want is to consider realtime traffic for the first, say, 15-30 minutes of a route, then fade back to historical average conditions - error in travel times mean it becomes very uncertain when the driver will actually be performing the more distant parts of the route. Currently, OSRM does not support doing this, although we have plenty of historical discussion about it:

• Time-dependent routing #4449
• Support for time-dependent ETAs #2695

[CodeBear801]

@danpat, thanks for your suggestion, let me confirm my understanding.

• Without modify customization part's code, the easiest way is partition data into several over-lapped parts and apply customization separately.
  When handling user's request, there should be a router in the front, depend on orig/destination point's location send to different routing server. And for each routing server could do customization separately. Because the scale of data will be lower then there should be smaller customization time.
  May be I could also set up a routing server with full region data to handle long distance route but with lower update frequency. Very few people really drive for over 10 hours so calculating long route might mainly for trip planning purpose.
  The potential issue could be mis-match between partition map matrix and full map matrix and there might be multiple route due to overlap of data. But as long as we could manage a clear user story this strategy should not annoying much.
  If upper understanding is correct, its very helpful, we will discuss our product stories to evaluate this strategy.

• Thanks for sharing previous' discussion about time dependent routing. I read comments in those discussions and paper from Ben Strasser.
  The paper suggest to define several time windows(eg rush hour and none rush hour), compute several time independent route candidate in each time window, generate a sub graph contains only edges in those route result, then compute a time dependent route based on the sub graph.
  When mapping to OSRM, it means we could have several cost metric and each of them mapping to a specific time window(8pm ~ 6am, 6am ~ 10am, 10am ~ 4pm, 4pm ~ 8pm), and additional live traffic could stay in a map. Based on each matrix we could calculate alternative route separately, then based on all these route candidates we apply live traffic calculate time dependent route, like first 15~30 minutes consider live traffic and following mainly consider historic speed and accident. This idea could build on top of MLD and CH, to calculate time independent alternative route candidate. The challenge would be, how to bound the algorithm(like adjust Λmax and Λmin or some strategy to help user to adjust them based on different data) and total resource cost.

[wangyoucao577]

Only part b) may irrelevant with realtime traffic. Both a) and c) require realtime traffic for better route. Even for part b), we still possible to get better highway entrance and exit with realtime traffic.

Remember that by the time the traveller arrives at part (c), the traffic data used to calculate the route is probably very stale, particularly for long routes. Generally, what you want is to consider realtime traffic for the first, say, 15-30 minutes of a route, then fade back to historical average conditions - error in travel times mean it becomes very uncertain when the driver will actually be performing the more distant parts of the route. Currently, OSRM does not support doing this, although we have plenty of historical discussion about it:

• Time-dependent routing #4449
• Support for time-dependent ETAs #2695

@danpat You're right, part c) is also irrelevant with real time traffic. Real time traffic is important only for part a), i.e. mostly first 15 ~ 30 minutes, or maybe 2 ~ 3 hours at most. The proposal "slicing up North America into 1/4-sized chunks with decent overlap" should work for most of short/middle routes. The problem is that we may have to setup maybe a dozen of services based on these slicings, it costs resources but should work!

Another problem is that we still hope to improve the part a) of a long route by real time traffic. As I metioned here(#4449 (comment)), is it possible to let OSRM support query on subgraph restricted by some segements?

Moreover, thanks very much for the sharing, the paper(https://arxiv.org/pdf/1606.06636.pdf) is really interesting and looks good for rush hours. In OSRM there might be a simple way to inject it for MLD, i.e. import the historical speeds by customize for different time window, no need to generate multiple base graph by extract/partition. Then the problem will be same as #4449 (comment), i.e. how to construct the subgraph for further time-dependent query.