Reëvaluate histogram bins

Note: I'm just trying to get some thoughts written down after chatting with @david-crespo. This is more of a discussion than a feature request.

Oximeter uses histograms for distribution metrics, like request latencies or disk write sizes. We divide values into bins and store counts of events per bin. This is cheaper than storing every relevant event in the database, but more useful than storing summary statistics over all events.

The problem is that choosing the sizes of the bins is hard. We want to balance precision (which means small bins) with space-efficiency (which means large bins), and relatedly, we want to choose bins that provide good coverage over the distribution of observed values. This can be hard to do a priori, and distributions could even vary across racks or customer sites, which makes calibration even more challenging.

We currently use log-linear bins for histogram metrics, such that we divide values first by power of ten, then linearly within each log value: ten evenly spaced bins from 1 microsecond to 10 microseconds, ten more evenly spaced bins from 10 microseconds to 100 microseconds, all the way up to ten bins from 100s to 1000s. This can lead to many empty bins at the low and high end of the range, since there aren't many http requests that finish in less than single-digit microseconds, and hopefully also very few that take more than 10s. We also don't get great precision, because we don't have a large number of buckets for the part of the distribution where most values fall. Here's an example from grafana showing distributions of latencies for the system_timeseries_query endpoint:

I'm thinking about this today because @david-crespo raised the issue of identifying very slow responses (>30s), which we also can't do with our current bins. But in general, I think we can probably improve precision without using more space in the database. Some options:

• Continue using log-linear bins, but tune them better. We probably don't need coverage in the microsecond range, and @david-crespo might appreciate better coverage of very slow responses. If we can drop bins at the lower end, we would also be able to use more linear bins per exponent without increasing the size of data on disk. These bins could also be user-configurable, although I would be cautious there, since tuning histogram buckets is notoriously difficult, which is why we're talking about it in the first place.
• Use a more efficient bucketing strategy. Log-linear bins require us to know things about our distribution a priori, and are hard to adjust after the fact (for example, if we change bins, we can't necessarily merge old and new observations). Instead, we could use a bucketing strategy that's more precise and efficient, and requires less configuration. The idea that comes to mind here is Prometheus native histograms, which are sparse, exponential histograms that are tuned by desired precision and maximum number of buckets, not on the specific buckets themselves. In other words, we can write something like "give me a resolution factor of 1.1 (each bucket 10% wider than the next-smallest one), and downsample if we see more than 100 buckets". Related strategies like hdrhistogram and ddsketch exist, but they're less well supported in the telemetry ecosystem, so I wouldn't go down that path unless we really have to.
• Use a separate slow-query log for very slow queries. Requests that take >30s are hopefully extremely rare, and might be worth emitting as logs, rather than trying to tune histogram bins to capture them.

Over the long term, I think a bucketing strategy with minimal configuration, like Prometheus's sparse exponential histograms, will work best: it's hard to pick ideal buckets in advance, and that choice will be potentially different for each service (or even each endpoint). But it's a fairly involved change, and probably not a priority—even on the topic of histograms, there are probably more urgent changes, like supporting alignment and aggregation (I'll file a ticket about this later!).

Shorter term, it might be worth thinking about adding one more exponent at the high end of the range to address @david-crespo's concern, or a slow query log for the same reason. I also wouldn't mind adding more linear buckets within each power of ten to get a better sense of the actual distribution of latencies, to inform future decisions. For reference, histograms actually represent a small fraction of clickhouse storage at the moment, probably because we don't have many of them, and because sparse arrays should compress well in clickhouse:

SELECT
    `table`,
    sum(rows) AS total_rows,
    formatReadableSize(sum(data_compressed_bytes)) AS compressed,
    formatReadableSize(sum(data_uncompressed_bytes)) AS uncompressed
FROM system.parts
WHERE (`table` LIKE 'measurements_%') AND active
GROUP BY `table`
ORDER BY total_rows DESC

Query id: d8bc5e60-d78a-45dc-bd34-17c848f553a5

   ┌─table──────────────────────┬─total_rows─┬─compressed─┬─uncompressed─┐
1. │ measurements_f32           │ 9222192997 │ 72.89 GiB  │ 425.05 GiB   │
2. │ measurements_cumulativeu64 │ 6698341540 │ 62.60 GiB  │ 395.76 GiB   │
3. │ measurements_u64           │  486546486 │ 3.02 GiB   │ 28.69 GiB    │
4. │ measurements_cumulativei64 │  432089310 │ 3.47 GiB   │ 24.67 GiB    │
5. │ measurements_histogramu64  │  265060230 │ 4.90 GiB   │ 351.82 GiB   │
6. │ measurements_bool          │   27524496 │ 215.08 MiB │ 1.29 GiB     │
7. │ measurements_f64           │     205062 │ 3.18 MiB   │ 11.92 MiB    │
8. │ measurements_i64           │      39096 │ 316.13 KiB │ 2.32 MiB     │
   └────────────────────────────┴────────────┴────────────┴──────────────┘

No implementation file, test, or entry point is named. Start by locating the current log-linear histogram bucket definition and reviewing the ClickHouse storage context described here. Compare the proposed binning and slow-query-log options, then document a chosen direction and its precision, storage, and compatibility trade-offs.