GTFS-RT trip updates without enough memory for full message

Hello,

To elaborate on previous comments: There are multiple issues at play here. What Stefan is referring to (in the linked ticket) is a discussion on the "incrementality" field in GTFS-RT. The spec still says it's unsupported and its behavior undefined, but in practice people have been using it for about ten years in a fairly standardized way.

## Incremental Message Reception

The incrementality field allows for some other options. There are three aspects to this as I've seen it used in practice:

a)  Differential vs. full-dataset: The incrementality field can take on two values: differential and full_dataset. In full-dataset mode, you'll get one big FeedMessage containing every update for every trip or vehicle. In differential mode, you'll receive updates for each trip or vehicle as they stream in, either individually or in small blocks. This may include a guarantee that an update will be provided on every entity at least once every n minutes, or alternatively the producer sending the full dataset when you first connect, then sending only changes. Once you're in differential mode, this opens up possibilities b and c.

b) Poll vs. Push: In practice differential messages are usually distributed individually or in small blocks via a message queue. This means the notifications are pushed by the message queueing system as soon as they arrive, rather than pulled by the consumer via occasional polling. It would in principle also be possible to provide differential updates by polling (like full-dataset updates), with the producer tracking the last time each consumer polled, but I don't know of any such implementations. Combining differential+push means that you can receive vehicle positions and trip updates immediately after the vehicles report their position. In some places vehicles provide updates every few seconds, so their position is genuinely known in real time. For example, a system like this: https://junaan.fi/Helsinki (which I think is consuming a different data format, but from a system that communicates internally using differential streaming GTFS-RT).

c) Filtering: Message queue systems often allow filtering by topic. A continuous stream of immediate small messages provided by (b) is already an improvement over full dataset fetching, but if you only care about one route (for an arrival time display panel for example) you don't want to continuously receive and parse thousands of messages per second looking for the relevant ones. So rather than a "firehose" of every message, you subscribe to a topic that includes only messages for that one route. You then receive a single message every few seconds with the latest predictions for the routes you care about.

The advantages of a system like this are evident, and at least in cases I've seen, differential message passing systems are often considered the only reasonable option when a large (national/metropolitan) realtime passenger information system goes through an intentional and thorough design process.

So: if your data producer provides streaming, filtered differential messages or is planning to, this seems perfect for your use case. In fact it is designed with your use case in mind, with similar needs to arrival displays, bus tracking apps, and journey planner routing instances.

If they do *not* provide streaming filtered differential messages (which is the norm), then you will indeed need to periodically download the entire full-dataset feed, parse the entire thing and scan through it until you find the single message you need :)

## Incremental Parsing

I believe all automatically generated parsers I've seen for protobuf messages are intended to parse an entire message and return a full in-memory representation of that message. In the case of GTFS-RT, the top-level FeedMessage will generally contain the entire dataset as a repeating FeedEntity, so the entire deserialized dataset has to fit into memory (which is the problem you were originally asking about).

Rather than modifying the function that parses FeedEntity, you'd probably want to modify the function that parses FeedMessage (which contains the repeating FeedEntity field) so it doesn't allocate a giant empty array of FeedEntity in advance. In that function's loop handling the list, after calling the FeedEntity parser function, it would call your callback then free the returned FeedEntity [1]. This seems like a good option on the surface, but the generated protobuf parsers I looked at don't actually generate full parser functions for each message type. They reuse some generic code for every message type, such that it might be hard to get it to behave in this special way for only repeating FeedEntity instances without making the parsers for all other message types into event-driven parsers. Though that wouldn't necessarily be a bad thing...

The alternative is then to write the parser yourself. Depending on your background or interests, you might find this fairly straightforward. There are tons of references on recursive descent parsers, and the protobuf wire format is well documented. One tricky part is variable-width integer encoding. What I'd probably recommend is generating a parser from the protobuf definition, then reusing all its basic number decoding functions and constants, but calling them from hand-written versions of some or all of the actual parsing functions.

The other trick is going to be keeping the size of the input buffer bounded. I think what you want there might be a circular buffer, with network packets going in and the event-driven parser reading out of it.

I hope this gives you some ideas! It was also a good opportunity for me to think through some upcoming documentation for differential mode GTFS-RT. Anyone please correct me if I made any mistakes in there!

Andrew

I just realized Stefan might be suggesting that if your producer does not do differential data, you could run the new differential system being built for the Netherlands, have it occasionally ingest a full dataset feed from your provider and create your own differential message broker. Then your embedded system can subscribe to only a limited amount of messages from your own broker. 

-Andrew 

In retrospect, what I've written so far is an attempt at writing my own parser like you said. With shoddy pattern recognition functions and help of a mini protobuf library , I made progress on reading in 500 bytes at a time and fully parsing out the updates I'm after for an entire message. (i.e. 2 or 3 routes of interest for a LED arrival board using this SBC by maker called Adafruit).  But it's not reliable. I believe I ran into variable-width issues exactly as you describe, which without a deeper understanding of the format makes finding the boundaries of the recursive message structure a hassle. And one mistake throws off the chain of parsing fixed-size buffers for the remainder of the FeedMessage, as the trimmings (the start or subsequent message) get handed off to the next iteration. What is a good resource for better understanding how to detect those boundaries when cycling through arbitrary size chunks? Are there any existing libraries or reference that are good to dig into? Do I need to venture out of Python? Also curious if this sounds impractical or not a good path to pursue! I have to admit I am somewhat out of depth on aspects of all this, low- and high-level.