Support out of order ingestion for native histograms

[beorn7]

This feature will be released soon for normal float samples, and it would be really weird if we did not support it for histogram samples.

Update 14th June 2023: @krajorama and @jesusvazquez are starting to work on this issue.

[krajorama]

Overall task list from discussion:
Scope: everything is in the tsdb package: db.go, head_append.go, ooo_*.

Write path: start from headAppender.Append function
Need ooo_head.go OOOChunk.InsertHistogram, OOOChunk.ToHistogramChunk, modify writing ooo head to disk to account for different encodings.
Need head.go insertHistogram - keep it simple for now, no handling of counter reset, just use the 32 sample OOOchunks.

@jesusvazquez notes:
ooo_head.go

• Creeate new InsertHistogram() method
• Create new ToHistogramFloatHistogram() ToHistogram()

head_append.go

• Modify AppendHistogram() with ooo logic
• Modify appendableHistogram() with ooo logic
• Create insertHistogram()
• Modify mmapCurrentOOOHeadChunk() with new chunk encoding logic. The method currently works with ooo chunks as if they always were XOR chunks.

[beorn7]

Also assigning to @zenador and @krajorama to mark all the collaborators on this issue.

[zenador]

Testing to see if this grants permission to assign

[krajorama]

From IRL discussion: we've decided that we do not need to support the of mixing different sample types (float/integer histogram/float histogram) in the OOO headchunk. This should make testing a bit simpler.

[krajorama]

From IRL discussion:
@carrieedwards @fionaliao @jesusvazquez (cc @zenador )

Immediate goals in priority order for the code:

• add native histograms to existing unit test happy paths
• add tests around counter reset/multiple chunk handling
• tests for float <-> native histogram series transitions

[krajorama]

Counter reset between chunks test case discussion:

It is theoretically possible to write such sequence of histogram samples:

• append and commit a recent histogram sample to initialize the normal in order head/WAL
• append and commit opts.OutOfOrderCapMax number of out of order histogram samples without counter reset
• append and commit 2 x opts.OutOfOrderCapMax more histograms that are out of order, don't have counter reset between them and later then the previous out of order samples AND the first sample in this batch has lower (bucket) counters than the last sample in the previous batch

When we query the samples back, something should detect that now the samples have a counter reset - I'm not sure if this should happen on chunk / chunk iterator level or simply somewhere in the PromQL engine (cc @beorn7 )

[beorn7]

The PromQL engine simply looks at the CounterResetHint as returned from the query to TSDB. If you want the PromQL engine to do the (expensive) traditional counter reset detection, just set the CounterResetHint in the returned histogram to UnknownCounterReset.

[beorn7]

Generally, it would be cool if we never end up with (counter) histogram chunks that have counter resets in the middle. (We have ruled that out so far, assuming that a histogram will change its bucket layout a lot after a reset so that handling that all in the same chunk is more expensive than cutting a new chunk. I'm not completely sure if it is even technically possible to encode a chunk with a counter reset in the middle. We definitely have created a lot of code around the invariant that there is never a counter reset within the same chunk. So keeping it that way would definitely be much much preferred.)

But if all of the above is just about returning histogram samples from a state where things haven't been consolidated into one chunk, and they come from overlapping chunks or buffers, you could indeed simply return a CounterResetHint as UnknownCounterReset whenever you want PromQL to detect the counter reset itself.

[beorn7]

Closing this as the code is merged, but note that this is a huge undertaking and it is quite likely that we will find bugs in the implementation. But those should be tracked in specific issues.

Thanks everyone for all the work here.