Evaluate the possibility of switching to libcirclhist

[htuch]

Envoy uses https://github.com/circonus-labs/libcircllhist, the original design discussion was in https://github.com/envoyproxy/envoy/issues/1965.

In the interest of minimizing total dependencies, we should answer "is there a strong reason to be using HDR histogram vs. this log-linear library?". This library may have already been considered, if we can articulate our rationale in this issue we can have some design history.

[oschaaf]

So reading up, what may be for hdrhistogram is improved accuracy. But seeing is believing, I feel it's worth doing some tests for comparison. On a side-note: one fairly recent observation is that the merge we with perform after the test run to compute the aggregated latencies with HdrHistogram massively slows down when using lots of workers (80 on a 40 cpu (HT-enabled) system with 128GB of ram). I didn't look into that, but it seems very reproducible, so I am making note of it here so I don't forget when getting back to this.

[htuch]

Also worth evaluating is the project health of the various options, some might have more active communities and contributions than others.

[HeinrichHartmann]

Hi @htuch, the qualitiative differences to HDR Histograms are as follows:

• circllhist mandates all bin and range choices. This means two circllhists from different sources are always mergable. But also you have to live with 2 digit decimal precision (usually not a big issue).

• circllhist is generally more optimized (since it does less). In particular the C implementation is highly performant when it comes to insertion (ns-range) and merge (us-range) operations.

• HDR-Histogram uses base-2 arithmetic behind the scenes, circllhist uses base 10. So you get precise counts at "human readable" float numbers like 0.24, 120, 1800, as opposed to 0.09375=0.00011 base-2.

I ran some superficial benchmarks for a recent conference talk: https://nbviewer.jupyter.org/github/HeinrichHartmann/Statistics-for-Engineers/blob/master/2019-10-02-SRECon-Dublin/2.4%20Mergeable%20Percentile%20Aggregation%20Comparison.ipynb

Here is the summary table:

In this benchmark we inserted ~800K samples. The reported time is the time for the insertion of the complete dataset.

[oschaaf]

That is an awesome analysis. Based on that, I'd lean towards switching NH to libcirclhist, because:

• It looks faster for our use-case both in inserts and merge, at what looks like an acceptable loss in accuracy
• We could piggy back on Envoy for this, I think. Which would mean that we could completely drop our own statistics infrastructure

@htuch what do you think?

[htuch]

Yep, SGTM, I think the original choice of HDR histogram is we wanted a precise and efficient (memory or serialization wise) histogram for dealing with potentially large ranges, as you typically encounter when measuring latency. This seemed to be a popular algorithm and implementation. I think if we gain via unification and the precision tradeoffs are within reason, i.e. multiple decimal digits when dealing with microseconds, we're good.