v1: require message index entries be sorted?

[wkalt]

This enables a reader to do a binary search over the message index. Insertion sort can be used to sort the section in place performantly, under the assumption it is already mostly ordered.

[defunctzombie]

The downside is that if your logTime does go out of order, you now need to do more work to keep this sorted array. Work that the robot maybe doesn't need to do and its easy for a reader to do.

[jameskuszmaul-brt]

On a per-topic basis, I'd expect that most writers could probably enforce ordering? I.e., a message sent at t=1s in topic /foo can probably be guaranteed to be logged before a message sent at t=2s also on /foo. But a message sent at t=2s on /bar may be present before any /foo messages in the log.

I've also seen logfiles specs that state that messages, even across topics, will not be out of order by more than a certain amount of time, which allows the reader to only have to read ahead by a certain amount to sort.

[wkalt]

well, to be clear this concerns the order of the entries in the index, not in the file itself.

The file can have out of order messages, though it could potentially violate some expectations of consuming applications. I agree they will generally be ordered or almost totally ordered.

The question here is whether the array of <timestamp, uint64> tuples in the Message Index record should be sorted.

An array already has to be maintained for these, so it's just a question of whether the array is sorted before being written out to disk.