Ordered optimisations for chunks, indexes

[Mike-Dax]

We have a reader that often wants truly random access to messages. Our non-MCAP based persistence engine utilises a BTree ordered by time for this purpose, resulting in very fast 'seek' times.

We have a writer that persists our data into an MCAP file, pulling from these persistence engines. The output is totally ordered by time, and therefore we can guarantee that the resulting MCAP file's on disk representation is also totally ordered by time.

My reading of the MCAP spec and implementation is that the order of chunks, message indices and chunk indexes are all unordered.
I understand that often writers can't guarantee their message ordering. However, sometimes they are totally ordered.

I would like to suggest the ability to add user-defined metadata to chunks and indexes.

My hope is this would be possible to do in a non-breaking fashion, by appending a map to the end of the Chunk, Message Index and Chunk Index records? Readers currently written would not read the additional fields, but ones in the future would be able to check if there's length designated for them? (I'm unsure if this would work in practice) Alternatively, a new Opcode could contain data about these other records. (I would hope this would more certainly work in practice)

Our writer could then maintain an is_totally_ordered piece of state while writing, then write that metadata per chunk / message index / chunk index. Our reader could then read that state, and use an optimised path where these records can be binary searched.

I'd like the metadata to be unspecified, so that within the confines of the spec, we would be free to try other optimisation strategies. Arbitrary metadata should be able to fulfil this purpose.

We have 'tagged' messages, that have the same topic, but may have some facet / row that distinguishes one from another. For example, a 'light intensity' topic, but tagged with additional 'position' information. Arbitrary metadata would let us define our own 'index' within the metadata that specifies the ranges covered by each position. The messages could be laid out by (position, time), and again we can optimise our queries to take advantage of this information. Since the spec is that the ordering is unspecified, any other readers without understanding of this information would just read them as unordered, sort them, and move on. (Cardinality issues prevent us from having separate topics for each facet.)

Other potential optimisations to explore would be laying out the ordering as an Van Emde Boas Tree / other implicit tree structure that allows for efficient searching.

Per topic size statistics would also be possible to store in these regions.

There's prior discussion about user-defined statistics here

I didn't want to write up an RFC without some level of interest, hence this relatively low effort discussion post. Does this approach seem reasonable / useful?

[wkalt]

@Mike-Dax I think this is a great request, and one we have thought about previously. I wonder if you saw this idea:
#723

I think the idea for recording whether a chunk is ordered could be expressed as a custom "chunk-level" statistic. We could also handle this by extending the "chunk index" record as you suggest, but I think the MCAP model extends more cleanly through addition of new records when possible.

This isn't something that has drawn enough interest for us to implement yet, but what do you think? You would also be able to leverage this for min/max statistics and various other things that could be helpful for your searching, depending on what you are doing.

[wkalt]

Oh, I'm sorry - got ahead of myself and didn't read the end of your message. I think an RFC for this would be appreciated, either extending on that custom statistics one or if it doesn't fit the bill, whatever features you need. We would definitely take it under consideration and it's great to see the user interest.

[defunctzombie]

One item I'll throw in here related to faster reading is that even without the guarantees around chunk ordering or message index ordering you can do get some "reasonably" fast insights from the chunk indexes and message indexes on whether the file is ordered and optimize some reading paths. That is the approach taken in this recent improvement for the typescript library: #1036