Handling of non monotonic timestamps

[XN137]

The first commit shows a problem when reading files with non monotonic timestamps: some histograms get silently skipped when using nextIntervalHistogram(double, double) (but not when using nextIntervalHistogram()). Note: This also wont happen when the file contains a StartTime or BaseTime comment.

The skipping of intervals in such cases is because of these code parts: https://github.com/HdrHistogram/HdrHistogram/blob/c410c5c2699b69ce0eb026ff954fefc4045ec363/src/main/java/org/HdrHistogram/HistogramLogReader.java#L233-L249 https://github.com/HdrHistogram/HdrHistogram/blob/c410c5c2699b69ce0eb026ff954fefc4045ec363/src/main/java/org/HdrHistogram/HistogramLogReader.java#L257-L261 because offsetStartTimeStampSec can become negative and thus will be < 0.

The first commit is more of a question: is it an invalid file format if timestamps are non-monotonic?

If the answer is yes, which i assumed due to: https://github.com/HdrHistogram/HdrHistogram/blob/c410c5c2699b69ce0eb026ff954fefc4045ec363/src/main/java/org/HdrHistogram/HistogramLogReader.java#L155-L157 and the given file is an invalid file format, then the 2nd commit fails hard when trying to read/write such files (because imho failing hard is better than silently dropping parts of the data, had to spend quite a while debugging this).

if no and the example file is valid, we will need to discuss how a real fix should look like.

[marshallpierce]

I took a pretty different implementation approach in the Rust implementation in part because I couldn't figure out a good way to explain to a prospective user exactly what this logic was doing. This is the first time I've heard of such odd logs in the wild, but no doubt there are more out there.

[giltene]

The current log parsing logic definitely makes an assumption about monotonicity of timestamps. Doing things like reporting on a given time range without that assumption would be "much harder". Can you describe some of the use cases you are seeing that are showing out-of-order timestamps within a log? Maybe we can come up with something weaker than "must be monotonic" which would be practical.

When looking at stream consumption use cases, for example, a time-window filtering thing that identifies items in a window of interest before aggregating them seems to be a common pattern these days (e.g. in real time pricing use cases that process events arriving lazily in a stream, and may often show up out of sequence). I'd love to find a logical and well-defined semantics that would allow for such window-based aggregation without requiring monotonicity in event arrival. The big question seems to be around "termination", as in "how far (in time or space) do you go before you stop looking for items that fall in the time window?".

[nitsanw]

I think the current API does not report errors clearly and conflates error/warning conditions (which is a preference/requirements issue). I can argue for real use cases where histograms, particularly histograms for different tags, arrive out of order. I would at least like to be able to disable the "monotony" requirement in the reader. I think the time range can be met on a best effort basis, such that for a range [X,Y] the log is read from the first histogram after X until the first histogram which is after Y. If there are histograms in between that are out of range/order, report them, don't drop them. I would suggest a callback mechanism for the error handling.

[nitsanw]

See recent work on #142 which allows a workaround the monotonic TS requirement without breaking existing behavior. Would you consider this is still an issue given the new implementation (i.e. if you were to use the new HistogramLogScanner class)?