Histograms

A Histogram measures the distribution of values in a stream of data

直方图描述数据流中的数据分布情况。

直方图不仅仅能提供最大，最小，平均值，而且可以提供median（中位线）或者99th线。

计算直方图的基本方法：排序。但是对吞吐量大，低延迟要求的系统，不适用。下面介绍下常用的方法。

dropwizard

一个开源的Metrics库，https://metrics.dropwizard.io/3.2.3/manual/core.html#exponentially-decaying-reservoirs。采用了下面的方法来统计Histogram。

reservoir sampling （蓄水池采样）

在一个给定长度的数组中随机等概率抽取一个数据很容易，但如果面对的是长度未知的海量数据流呢？蓄水池采样(Reservoir Sampling)算法就是来解决这个问题的, 它在分析一些大数据集的时候非常有用。

先把读到的前k个对象放入“水库”，对于第k+1个对象开始，以k/(k+1)的概率选择该对象，以k/(k+2)的概率选择第k+2个对象，以此类推，以k/m的概率选择第m个对象（m>k）。如果m被选中，则随机替换水库中的一个对象。最终每个对象被选中的概率均为k/n，证明如下

第m个对象被选中的概率=选择m的概率 x（其后元素不被选择的概率+其后元素被选择的概率 x 不替换第m个对象的概率），即

• Uniform Reservoirs

  统计全量数据，通过 Vitter’s R算法，来随机选取数据。用于长时间的测量。

• Exponentially Decaying Reservoirs

  只看最后5分钟的数据，通过使用 forward-decaying priority reservoir来对新数据进行指数加权。不像Uniform Reservoirs，它只展示最近的数据，可以让你尽早的发现数据的变化

• Sliding Window Reservoirs

  只关注最后N个

• Sliding Time Window Reservoirs

  只关注最后N秒内

SlidingTimeWindowReservoirs 因为它是无界的，如果被用在一个大吞吐量的系统，会造成大量的内存浪费，因为它记录每一个measurement，所以也是最慢的。

但是看到了这篇文章：https://medium.com/hotels-com-technology/your-latency-metrics-could-be-misleading-you-how-hdrhistogram-can-help-9d545b598374

Dropwizard内部默认使用Exponentially decaying Reservoirs （EDR）

但是有以下缺点：

• EDR设计有损;它们不存储每个样本（它们具有统计学上的代表性）。
• 默认情况下，EDR存储静态1028个样本，并且样本在过去5分钟内被加权。
• EDR中样本衰减的速率受直方图更新频率的影响。

这些缺点加起来意味着您报告的指标可能会产生误导，要么是由于丢弃的样本导致的不准确，要么是通过包含可能更旧的样本来计算的。虽然提供代替方案，但都不适合实时报告。

HdrHistogram（高动态范围直方图）是一种无损直方图实现，具有可配置的值精度，可解决EDR的缺点。

HdrHistogram

//TODO

---