Realtime added patterns for a trip persist with DIFFERENTIAL updates even after a new update

[optionsome]

Expected behavior

Realtime added trip pattern for a trip (that usually happen with SKIPPED stops) should be removed when a new update arrives for the trip.

Observed behavior

Realtime added trip pattern added persists in a broken state when a new update that doesn't contain SKIPPED stops arrives.

Version of OTP used (exact commit hash or JAR name)

2.4

Data sets in use (links to GTFS and OSM PBF files)

Can be requested

Steps to reproduce the problem

Load a DIFFERENTIAL gtfs realtime trip update that contains SKIPPED stops for a trip and afterwards in a separate update an update to the trip that doesn't contain SKIPPED stops.

[abyrd]

To facilitate review of the corresponding PR as well as understanding for future refactors, can you give a bit more detail on what happens?

The "expected behavior" section says "trip pattern ... should be removed when a new update arrives for the trip" but it seems like there might be something more going on. The "observed behavior" section says that "added trip pattern added persists in a broken state". So if I understand right the problem is not just that the patterns persist (which is arguably a sort of slow memory leak) but that there is something else wrong with them. What exactly is the "broken state"?

If the patterns persist but are reused by any subsequent update that has exactly the same pattern, this is not necessarily a bad outcome. But if another update comes in and the pattern is reused, and this somehow causes routing errors (or is otherwise "broken") then of course it needs to be fixed.

[optionsome]

The issue is that the TimetableSnapshot's realtimeAddedTripPattern index contains the realtime added trip pattern for the trip even after there is an update to the trip which uses the original trip pattern again. This causes some API calls to return the "old" version of the timetable which is in a deleted state (and all of the stops are shown as canceled). This does not seem to affect routing.

[abyrd]

When a trip is realtime-modified to use a particular stop, then realtime-modified again to skip that stop, arguably we want to retain the information about the canceled trip in case a passenger already made plans around that fact (e.g. is walking to the stop to board the trip), and now needs to see that the event they were planning on did in fact exist but is canceled. In that case it makes perfect sense to display a trip visiting the stop but marked "canceled".

The problem arises when the second (revised) realtime update changes the trip's behavior at only some stops in its pattern, and subsequently the trip is present in both a canceled and un-canceled form at all the other stops on different TripPatterns. Then an API call about a single stop might encounter the same trip twice, once canceled and once non-canceled. This is clearly confusing. Any non-canceled version needs to mask the canceled version, and that can be done in several ways. For example:

• The API call can filter out duplicate trip IDs across different patterns, favoring the un-canceled instances;
• The realtime-affected trips passing through stops can be indexed directly instead of indexing their patterns, with non-canceled instances favored over canceled ones in those indexes.

To expand on the second option: the indexes used to assemble API responses currently seem to be pattern-oriented (realtimeAddedTripPattern and patternsForStop in TimetableSnapshot), but patterns are relevant only to routing algorithms and not to passenger-facing representations. For passengers, multiple patterns are often grouped together under a single simplified commercial name (as a single route or branch of a route). At any given moment, within a single consistent snapshot, for any one tripId and stopId there should only be one set of StopTime (or "call") information that is non-canceled / non-deleted. In other words it should be possible to unambiguously select which instance of the trip to report as the currently passenger-relevant one at any specific stop. It seems possible to index directly from stop to passenger-relevant trip, rather than from stop to pattern(s), leading transitively to multiple clashing versions of trips.

It's an internal detail that the API-oriented code is iterating over TripPatterns to discover all the relevant trips visiting a stop. That internal detail probably shouldn't be exposed in any way, even as a grouping mechanism for the trips. And maybe that internal detail doesn't even need to exist in indexes outside routable data structures.

Whatever the approach, for a given realtime-affected tripId N, we need to be able to show that trip as canceled at some stops, but un-canceled at some other stops.

[optionsome]

There are different levels of realtime added trip patterns. With modified/added trips, the pattern can be completely different. At some point, that realtime added trip pattern becomes relevant to the passengers as well, as grouping it to an existing pattern might not make sense. However in this case, the realtime added trip pattern just changes the dropoff/pickup status on stops and "merging" it with the "planned" pattern (derived from the static data) makes sense and we don't need to expose the trips under different pattern to users, at least in most cases.

What is the benefit of keeping a realtime added pattern with only deleted timetables if we don't even want to expose the existence of the realtime added trip pattern to the users? I feel like it just complicates our code as we need to filter those out somehow in all API calls. Also, we seemingly only persist the realtime added trip pattern when using DIFFERENTIAL updates, and even then, only one realtime added trip pattern for a trip. It's possible that a trip could have multiple different versions of a realtime added trip pattern over time if different stops are skipped, for instance.

I do agree with you @abyrd that maybe the way we index things for API calls might not be ideal.

[abyrd]

However in this case, the realtime added trip pattern just changes the dropoff/pickup status on stops and "merging" it with the "planned" pattern (derived from the static data) makes sense and we don't need to expose the trips under different pattern to users, at least in most cases.

We can't just mix trips with different pickup/dropoff patterns under the same TripPattern. This would break invariants or definitions the routing algorithm depends on. Do you mean genuinely merging the trip into a different TripPattern, or just dynamically merging its representation as it goes out in the API response? That is, do you mean merging the primary data structure or merging the derived representation just before serialization?

What is the benefit of keeping a realtime added pattern with only deleted timetables if we don't even want to expose the existence of the realtime added trip pattern to the users?

The usefulness of patterns and their exact definition can't be judged in the context of non-routing API responses alone. The definition of a pattern comes from routing algorithms, and routing won't work properly if a pattern includes trips that don't meet that definition. If the definition of what trips are included in a pattern is altered to make non-routing API output more pleasant or convenient, then the two kinds of pattern (API and routing) diverge in meaning, and must be maintained separately. That is, the routable data will no longer be a simple derivative of these TripPatterns, and we have to apply separate logic (API and routing) every time data gets grouped/inserted/updated in patterns.

For this reason I'd be very wary of changing the criteria for associating a trip with a pattern. Unless of course the change can be taken to the extreme, and trips are not associated with patterns at all in the non-routing API context, with patterns kept only for routing purposes. I haven't fully verified whether this is feasible.

Currently: Every trip belongs to a pattern, and the instance representing that trip is (only?) reachable via the instance representing its enclosing pattern. This clean hierarchy (driven by routing needs) carries over to the code where other non-routing API responses are generated. There is probably no reason TripPatterns have to hierarchically group trips in all contexts. Trips can be grouped into TripPatterns for routing purposes, and grouped differently (into Routes for example) or not grouped at all and indexed individually for the purposes of other non-routing API responses.

The backstory is that we originally (like 10+ years ago) grouped and stored trips in TripPatterns as a routing optimization (on Graph edges, then for Raptor. That grouping is still relevant to this day for routing. The "index API" was only built later, on top of that primarily routing-oriented data structure. In places where a set of trips was needed for a non-routing API response, but no relevant individual-trip-level index existed, the needed set of trips was built up dynamically from patterns.

These days the routing may seem to be happening elsewhere on different data structures, but if I'm not mistaken these TripPatterns that are examined in the non-routing-oriented API responses are still fundamental in maintaining the proper grouping of trips for raptor routing.

(edit: I now realize that in the above text, I used the term "pattern" somewhat indiscriminately to mean both TripPattern and the StopPattern serving as a key for a TripPattern in OTP.)

[optionsome]

We can't just mix trips with different pickup/dropoff patterns under the same TripPattern. This would break invariants or definitions the routing algorithm depends on. Do you mean genuinely merging the trip into a different TripPattern, or just dynamically merging its representation as it goes out in the API response? That is, do you mean merging the primary data structure or merging the derived representation just before serialization?

Sorry, I originally meant to quote part of your original message but left it out and my writing was a ambiguous. I meant exposing through the APIs. For routing, these differences are crucial as you stated.

The usefulness of patterns and their exact definition can't be judged in the context of non-routing API responses alone. The definition of a pattern comes from routing algorithms, and routing won't work properly if a pattern includes trips that don't meet that definition. If the definition of what trips are included in a pattern is altered to make non-routing API output more pleasant or convenient, then the two kinds of pattern (API and routing) diverge in meaning, and must be maintained separately. That is, the routable data will no longer be a simple derivative of these TripPatterns, and we have to apply separate logic (API and routing) every time data gets grouped/inserted/updated in patterns.

For this reason I'd be very wary of changing the criteria for associating a trip with a pattern. Unless of course the change can be taken to the extreme, and trips are not associated with patterns at all in the non-routing API context, with patterns kept only for routing purposes. I haven't fully verified whether this is feasible.

Currently: Every trip belongs to a pattern, and the instance representing that trip is (only?) reachable via the instance representing its enclosing pattern. This clean hierarchy (driven by routing needs) carries over to the code where other non-routing API responses are generated. There is probably no reason TripPatterns have to hierarchically group trips in all contexts. Trips can be grouped into TripPatterns for routing purposes, and grouped differently (into Routes for example) or not grouped at all and indexed individually for the purposes of other non-routing API responses.

The backstory is that we originally (like 10+ years ago) grouped and stored trips in TripPatterns as a routing optimization (on Graph edges, then for Raptor. That grouping is still relevant to this day for routing. The "index API" was only built later, on top of that primarily routing-oriented data structure. In places where a set of trips was needed for a non-routing API response, but no relevant individual-trip-level index existed, the needed set of trips was built up dynamically from patterns.

These days the routing may seem to be happening elsewhere on different data structures, but if I'm not mistaken these TripPatterns that are examined in the non-routing-oriented API responses are still fundamental in maintaining the proper grouping of trips for raptor routing.

(edit: I now realize that in the above text, I used the term "pattern" somewhat indiscriminately to mean both TripPattern and the StopPattern serving as a key for a TripPattern in OTP.)

I think the discussion about how the TripPatterns should be modeled for routing/API is an interesting one but this issue is about an edge case where we have a TripPattern that we don't use for routing nor do we want to expose it or any of its contents through APIs because all TripTimes that it contains in its Timetable, have StopRealTimeState DELETED. I think the filtering for Raptor happens in https://github.com/opentripplanner/OpenTripPlanner/blob/dev-2.x/src/main/java/org/opentripplanner/routing/algorithm/raptoradapter/transit/mappers/TripPatternForDateMapper.java#L84-L112 and https://github.com/opentripplanner/OpenTripPlanner/blob/dev-2.x/src/main/java/org/opentripplanner/routing/algorithm/raptoradapter/transit/mappers/TransitLayerMapper.java#L140-L151 but the filtering in TransitService for the API responses is lackluster.

[abyrd]

I think the discussion about how the TripPatterns should be modeled for routing/API is an interesting one but this issue is about an edge case where we have a TripPattern that we don't use for routing nor do we want to expose it or any of its contents through APIs because all TripTimes that it contains in its Timetable, have StopRealTimeState DELETED.

I think I understand: this is about seeing those realtime-added patterns as a kind of memory leak and cleaning them up. But what's still making this ambiguous for me is that in #5726 (comment) you mentioned "@t2gran argued that to have consistency between updates we need to keep the deleted entities." What kind of consistency are we talking about? If it's from the end-user perspective (showing end user an update about trip X visiting stop Y, then later continuing to show that same trip X at stop Y but with information that it's canceled) we do need to retain the canceled trips (in the current system), or change the indexing or other aspects of the representation in a case-specific way.

BTW sorry my commentary is getting split across the issue and PR - it wasn't clear at first how much we were discussing the general problem (the issue) versus the proposed solution (on the PR). I'll try to confine any commentary to a single place from now on.

[t2gran]

Trips exposed through the API can not be removed - just simply because someone bought a ticket and to fetch the information in the ticket again the trip must be accessible in the API. So, I think the DELETE is a bad idea. You can cancel stops/trips and add a note to say that this trip should never been planed - it was a mistake - but it should not disappear - one exposed to the end user. Deleting a RT-instance of a trip witch is replaced with new information about the trip is ok. This is what I ment by "consistency".

[abyrd]

Discussed in call today: agreed upon next step is to arrange a separate thread of work/discussion calls on the topic of realtime updates together with @t2gran. Once that is scheduled, I will more formally map out the space of realtime handling functionality and situate this problem within that space, so that in PRs like this one we can make a clear decision about what we are and are not covering, and what remains to be addressed down the road.