Different alerts storage

[abyrd]

Every edge has a pointer to a list of alerts. The reason alerts are not just in an edge->alert map is that they can have an effect on routing (e.g. station closures). We need to do a survey of all ways an alert can affect routing, and see if there are better ways to represent those than in these lists. That will eliminate one whole field from every edge.
Related to #1527

[JordenVerwer]

As far as I know, I implemented this in commit 17b46d5. Alerts no longer affect routing, because the GTFS-RT reference never specified that they do so in the first place.

[buma]

I think they should affect routing. For example: No service stations can't be used in routing.
Same with no service routes or trips.

[JordenVerwer]

The problem is threefold:

1. Most types of alerts are far too vague to be used in routing. What is OTP supposed to do with ill-defined effects like reduced service and significant delays?
2. Even for the effects that could potentially be used, there is presently no well-defined meaning. If a stop is closed, what happens to trips that were supposed to visit it? Do they get canceled? Are they split in two? Do they just skip the closed stop? If so, how does it affect the rest of the timetable? All these things would have to be formalized first.
3. There already is a solution to this very problem in the form of GTFS-RT trip updates. Alerts should not double as both user-facing information and routing directions.

If you want to continue this discussion you can do so on the GTFS-RT mailing list. I believe the subject was brought up recently, because apparently some agencies (not including TriMet) want this functionality. However, no one has formalized the proposed effects of GTFS-RT alerts yet, as required per item 2. Therefore, I conclude that all implementations that currently exist are probably agency-specific and informally-specified. This certainly includes the implementation that used to be in OTP, which was poorly documented and just generally unpleasant to look at.

[abyrd]

On Tue, Sep 16, 2014, at 18:04, JordenVerwer wrote:

1. Even for the effects that could potentially be used, there is
   presently no well-defined meaning. If a stop is closed, what happens to
   trips that were supposed to visit it? Do they get canceled? Are they
   split in two? Do they just skip the closed stop? If so, how does it
   affect the rest of the timetable? All these things would have to be
   formalized first.

The opinion I got from TriMet was in fact that Alerts should not
affect routing, an opinion which I believe influenced your choice to
make this change.

But given the fact that most small agencies aren't going to write
sophisticated software to generate GTFS-RT and are attaching alerts to
objects "by hand" one by one, there does need to be some mechanism for
saying vehicles don't stop at a stop, people shouldn't get on or off
there etc. Those could be more RT messages or stricter definitions of
the Alert effects or some other thing, but as you say it's not defined
yet.

So yes, this should really be resolved on the RT mailing list.

-Andrew

[abyrd]

@JordenVerwer thanks for pointing out your previous change. There are in fact no Alerts on edges in the general sense, but PlainStreetEdge still has: Set of Alerts for notes, Set of Alerts for wheelchairNotes, and every single edge even has a List of TurnRestriction.

Even when you don't build the graph with elevation data, every edge has a pointer to an ElevationProfileSegment, which then has a bunch of other fields. I think we could easily cut the size of these objects in half.

[laurentg]

For info, the alerts list in PlainStreetEdge do not have any effect on routing, they are generated for some roads (unpaved / muddy surface, caution area, toll roads during driving...) and simply displayed to the user. Also the list of alerts are kept in the state during plan, we could remove this and simply scan the alerts once the itinerary is found (however toll roads alerts are generated on the fly).

[JordenVerwer]

So, basically you could duplicate the approach I used for GTFS-RT Alerts, without having to worry about thread-safety, because these alerts do not change after the graph is built anyway.

[laurentg]

Some notes are added for temporary (splitter) edges, so we have to take care of synchronization issues. I plan to remove the note set in state and apply notes during plan generation phase, using a more generic matching process (for wheelchair notes and drive tolls), each note having a matcher that accept the note depending on the edge and the state.

[JordenVerwer]

But temporary edges are only supposed to be visible in a single routing context, aren't they?

[laurentg]

@JordenVerwer Sure, but since we want to remove the note/wheelchair notes in the edge itself, we use a graph-wide "street note index service" to handle the edge->note index. So any add/removal in this index need to be synchronized, as temporary edges will add/remove notes on the fly in multi-threaded context.

[JordenVerwer]

It doesn't sound like the most obvious approach to use a global (and otherwise immutable) map to store inherently thread-local objects. Is there any reason the notes (that can really apply only to four edges, or six if the parent edges also require special treatment) can't be added to the routing context?

Or do you mean that adding a note to a temporary edge changes its parent edge for all other routing contexts as well? If so, that would imply that searches aren't fully isolated from each other, which would be bad.

[laurentg]

We could index the note in two separate places (global immutable street note index for immutable notes and routing context for temporary edges), but this would duplicate code. I think it's easier to handle edge->note indexing in the same place, allowing adding/removal for temporary edges. Anyway we do not have any performance issues here: the index is read only when the itinerary is found, once for each edge in the trip plan, and accessed only for splitted temporary edges with notes (which is not that often, notes are few).

[JordenVerwer]

I suppose you might be able to reuse the code I wrote for GTFS-RT Alerts, so if that's the case the next paragraph doesn't apply.

However, I originally I assumed that a new map would be created for the notes on PlainStreetEdges. If we make that map immutable (after graph building), it's no longer necessary to synchronize it, and a Multimap implementation can probably be used directly (without any kind of wrapper). Then the notes on PartialPlainStreetEdges can either be stored in the RoutingContext or on the PartialPlainStreetEdges themselves. I do not consider that code duplication, given that you'd have to add synchronization code otherwise. On the whole it may lead to slightly more code, but it will definitely be less complex.

To illustrate this added complexity: if you do add notes on temporary edges to the global map, you'll have to worry about memory leaks, etc. It's not as simple as it would seem at first.

[laurentg]

Indeed I did not thought about using PartialPlainStreetEdge. If we are certain that they are all temporary, we could store notes either in them or in the routing context. However honestly the synchronization issue are not that important (we wrap the multimap in a synchronized version) and that has a negligible impact on performance, as we do not look up for notes during route planning anymore: we just duplicate notes when splitting an edge, and one get() for each edge in the final itinerary when generated. Concerning preventing memory leak it could be safer indeed to not rely on ad-hoc code for removing notes on temporary edges removal (currently I need a line of code in a not-so proper place).

[JordenVerwer]

The problem I have with the Multimaps.synchronizedMultiMap wrapper (I assume that's the one you were referring to) is that it leaks: you can still perform non-synchronized accesses through the collection views it returns. Therefore I consider it safer to handle the synchronization myself in accessor and mutator methods, as I did for GTFS-RT Alerts. But if synchronization can be avoided altogether, that's even better.

I agree that performance is not really an issue here, but code complexity is. Sometimes concurrency issues simply can't be avoided, but here they can be, which is what I would prefer.

[hannesj]

It would still be nice to have a mechanism to change/remove alerts after the graph is built.

Currently we are using a graph updater to fetch information about ongoing roadworks and other obstructions for pedestrians/cyclists from an API provided by the city public works department nightly and adding those to the graph. With #1540 it is still possible to add alerts, but not change/remove those anymore.

[laurentg]

@hannesj Does a graph.streetNoteIndex.addNote(Edge, Alert, NoteMatcher) and ...removeNote(Edge) would be enough?
And btw with #1540 you can't add notes in a multi-threaded context anymore (but it should simple to add, we just need to synchronize the index).

[hannesj]

@laurentg It would be nicer to have something like removeNote(Edge, Alert) or even removeNote(Edge, java.util.regex.Pattern), as we prefix our notes in order to show them differently in the front-end. If we would just use removeNote(Edge) it could remove notes that we don't want to remove (eg about unpaved surface or wheelchair usage).

[hannesj]

Maybe it would be good to add the source in Alert in order to be able to remove all notes from specific source at once?

[laurentg]

The most flexible approach is probably a removeNote(Edge, Alert), since the amount of notes per edge is low it's simpler for the client to filter out alerts by looping in all alerts for an edge.

Currently the index does not index on alert, but it could be nice to be able to remove an alert for all edges, ie: removeNote(Alert).

Thinking about it, I think we could have a better architecture by having a list of StreetNoteProvider, with the current index being a StaticNoteProvider implementation, each provider having simply to define a getNotes(State). That way multiple dynamic providers could be created and handle their notes the way they best see fit.

[hannesj]

I like the idea about being able to have muptiple StreetNoteProviders, who independently take care of their own indexes. By doing that, we could just build a new index on when updating the information and replace the old index with the new one atomically.

[JordenVerwer]

I agree that allowing for multiple StreetNoteProviders is a good idea. People that want to be able to update notes dynamically are then free to write their own implementation. I would be against having too many hooks inside mainline OTP for code that isn't part of mainline OTP, though. Just extracting an interface from the current implementation would probably be enough for now.

Yeah, I know we'd be back at the "interface with a single implementation" point, but in this case there's a concrete example of why that would be useful. On the other hand, there's not really a reason why these changes would have to be made in mainline OTP in the first place.

[hannesj]

@JordenVerwer I'm not against pushing our implementation to OTP. However, it is probably of little use to others, since it is made to consume data provided by the city. As the data is provided as a WFS service, it could be rewritten as a configurable WFSStreetNoteUpdater which could be mainlined?

[JordenVerwer]

I'm not familiar with WFS, but if this is used more widely, it might be worth the effort.