Add functions for histogram standard deviation

[Wing924]

Standard deviation is as important metrics as φ-quantiles.
We can calc quantiles from histogram using histogram_quantile(φ float, b instant-vector), but we can't calc the standard deviation.
I suggest to add histogram_stddev(avg float, b instant-vector) and histogram_stdvar(avg float, b instant-vector) functions.

Ref. How to get the standard deviation of a given histogram

[brian-brazil]

How accurate would such a result be on something with only 10 buckets with greatly different sizes?

[Wing924]

@brian-brazil
I did a test to check the accuracy.

data source

# response time of a static contents server
count: 367,201
min:         0.000 [ms]
max:    31,298.796 [ms]
avg:         5.624 [ms]
stddev:    129.513 [ms]

# response time of an API server
count: 435,913
min:         0.000 [ms]
max:     4,090.126 [ms]
avg:        93.569 [ms]
stddev:    212.479 [ms]

histogram

count of buckets: 30
buckets width: exponential scale

# static contents server
unit [ms] | count  | histogram bar
1.001     : [198   ] *
1.001     : [189   ] *
1.003     : [372   ] *
1.006     : [572   ] **
1.012     : [870   ] ***
1.022     : [1754  ] *******
1.040     : [3017  ] ************
1.072     : [5153  ] ********************
1.130     : [9063  ] ***********************************
1.235     : [14481 ] ********************************************************
1.423     : [21066 ] **********************************************************************************
1.762     : [26831 ] ********************************************************************************************************
2.372     : [30387 ] **********************************************************************************************************************
3.470     : [30995 ] ************************************************************************************************************************
5.446     : [30317 ] *********************************************************************************************************************
9.003     : [21303 ] **********************************************************************************
15.406    : [19431 ] ***************************************************************************
26.931    : [17419 ] *******************************************************************
47.677    : [2310  ] *********
85.019    : [1149  ] ****
152.235   : [737   ] ***
273.224   : [355   ] *
491.003   : [139   ] *
883.006   : [48    ]
1588.611  : [46    ]
2858.700  : [23    ]
5144.861  : [18    ]
9259.950  : [8     ]
16667.111 : [6     ]
+Inf      : [7     ]

# API server
unit [ms] | count  | histogram bar
1.001     : [0     ]
1.001     : [1     ]
1.003     : [2     ]
1.006     : [3     ]
1.012     : [10    ]
1.022     : [24    ]
1.040     : [44    ]
1.072     : [123   ]
1.130     : [588   ] *
1.235     : [3150  ] *****
1.423     : [5656  ] *********
1.762     : [18862 ] ********************************
2.372     : [22248 ] *************************************
3.470     : [5381  ] *********
5.446     : [28928 ] ************************************************
9.003     : [34902 ] ***********************************************************
15.406    : [61929 ] ********************************************************************************************************
26.931    : [30020 ] **************************************************
47.677    : [20980 ] ***********************************
85.019    : [63840 ] ***********************************************************************************************************
152.235   : [71583 ] ************************************************************************************************************************
273.224   : [26923 ] *********************************************
491.003   : [2968  ] *****
883.006   : [812   ] *
1588.611  : [18160 ] ******************************
2858.700  : [69    ]
5144.861  : [4     ]
9259.950  : [0     ]
16667.111 : [0     ]
+Inf      : [0     ]

Result

# static contents server
q 50% real:      1.40 [ms] hist:     1.86 [ms] (err = -33%)
q 60% real:      1.89 [ms] hist:     2.33 [ms] (err = -23%)
q 70% real:      2.79 [ms] hist:     3.16 [ms] (err = -13%)
q 80% real:      4.60 [ms] hist:     4.89 [ms] (err = -6%)
q 90% real:     11.67 [ms] hist:     8.72 [ms] (err = 25%)
q 95% real:     17.41 [ms] hist:    12.81 [ms] (err = 26%)
q 99% real:     32.35 [ms] hist:    29.70 [ms] (err =  8%)
stddev real:   129.51 [ms] hist:   111.25 [ms] (err = 14%)

# API server
q 50%  real:    19.46 [ms] hist:    14.71 [ms] (err = 24%)
q 60%  real:    51.81 [ms] hist:    32.61 [ms] (err = 37%)
q 70%  real:    76.23 [ms] hist:    46.17 [ms] (err = 39%)
q 80%  real:   110.25 [ms] hist:    67.02 [ms] (err = 39%)
q 90%  real:   160.00 [ms] hist:   103.03 [ms] (err = 36%)
q 95%  real:   278.89 [ms] hist:   199.22 [ms] (err = 29%)
q 99%  real:  1058.89 [ms] hist:   794.52 [ms] (err = 25%)
stddev real:   212.48 [ms] hist:   180.94 [ms] (err = 15%)

Conclusion

The accuracy of histogram stddev is no more than that of histogram quantiles.

[brian-brazil]

You're algorithm isn't producing a correct answer, it should be +Inf for the static server as there is at least one point in the +Inf bucket.

More generally in any sufficiently loaded system there will always be some proportion of events in the +Inf bucket so I don't think this is workable in general.

[Wing924]

it should be +Inf for the static server as there is at least one point in the +Inf bucket.

I don't know why you think at least one point should be in the +Inf bucket. I think you confused general histogram (my graph) and cumulative histogram (prometheus histogram). Because cumulative histogram is good for calc but not for human understanding, I plotted general histogram.

This is the same data but use cumulative histogram:

# static contents server
1.000       : [128937  ] ******************************************
1.001       : [129135  ] ******************************************
1.001       : [129324  ] ******************************************
1.003       : [129696  ] ******************************************
1.006       : [130268  ] *******************************************
1.012       : [131138  ] *******************************************
1.022       : [132892  ] *******************************************
1.040       : [135909  ] ********************************************
1.072       : [141062  ] **********************************************
1.130       : [150125  ] *************************************************
1.235       : [164606  ] ******************************************************
1.423       : [185672  ] *************************************************************
1.762       : [212503  ] *********************************************************************
2.372       : [242890  ] *******************************************************************************
3.470       : [273885  ] ******************************************************************************************
5.446       : [304202  ] ***************************************************************************************************
9.003       : [325505  ] **********************************************************************************************************
15.406      : [344936  ] *****************************************************************************************************************
26.931      : [362355  ] **********************************************************************************************************************
47.677      : [364665  ] ***********************************************************************************************************************
85.019      : [365814  ] ************************************************************************************************************************
152.235     : [366551  ] ************************************************************************************************************************
273.224     : [366906  ] ************************************************************************************************************************
491.003     : [367045  ] ************************************************************************************************************************
883.006     : [367093  ] ************************************************************************************************************************
1588.611    : [367139  ] ************************************************************************************************************************
2858.700    : [367162  ] ************************************************************************************************************************
5144.861    : [367180  ] ************************************************************************************************************************
9259.950    : [367188  ] ************************************************************************************************************************
16667.111   : [367194  ] ************************************************************************************************************************
+Inf        : [367201  ] ************************************************************************************************************************

# API server
1.000       : [18703   ] *****
1.001       : [18703   ] *****
1.001       : [18704   ] *****
1.003       : [18706   ] *****
1.006       : [18709   ] *****
1.012       : [18719   ] *****
1.022       : [18743   ] *****
1.040       : [18787   ] *****
1.072       : [18910   ] *****
1.130       : [19498   ] *****
1.235       : [22648   ] ******
1.423       : [28304   ] ********
1.762       : [47166   ] *************
2.372       : [69414   ] *******************
3.470       : [74795   ] *********************
5.446       : [103723  ] *****************************
9.003       : [138625  ] **************************************
15.406      : [200554  ] *******************************************************
26.931      : [230574  ] ***************************************************************
47.677      : [251554  ] *********************************************************************
85.019      : [315394  ] ***************************************************************************************
152.235     : [386977  ] ***********************************************************************************************************
273.224     : [413900  ] ******************************************************************************************************************
491.003     : [416868  ] *******************************************************************************************************************
883.006     : [417680  ] *******************************************************************************************************************
1588.611    : [435840  ] ************************************************************************************************************************
2858.700    : [435909  ] ************************************************************************************************************************
5144.861    : [435913  ] ************************************************************************************************************************
9259.950    : [435913  ] ************************************************************************************************************************
16667.111   : [435913  ] ************************************************************************************************************************
+Inf        : [435913  ] ************************************************************************************************************************

[brian-brazil]

I did not misunderstand the data, my point stands.

[Wing924]

Can you point me where's wrong? The input data is strange?

[brian-brazil]

The input looks reasonable, the output of your function is not given that data.

[Wing924]

You're algorithm isn't producing a correct answer, it should be +Inf for the static server as there is at least one point in the +Inf bucket.

I think you're talking about the +Inf bucket. The problem is how to treat +Inf. If we take account the +Inf bucket and treat mean of that bucket as +Inf, the stddev is +Inf, which is no meaning; if we just ignore +Inf bucket, we can get reasonable stddev. +Inf bucket only occur if you have really irregular data. If +Inf bucket is big, the histogram design is wrong.

[brian-brazil]

+Inf is the correct answer, you can't just throw away data because you don't like it. Histograms are designed this way for quantiles so the user will know that their buckets are off, which means that this doesn't work for standard deviation.

[lock]

This thread has been automatically locked since there has not been any recent activity after it was closed. Please open a new issue for related bugs.