[3/4] libmultipath: path latency: simplify getprio()
diff mbox

Message ID 20171118001134.26622-4-mwilck@suse.com
State Not Applicable, archived
Delegated to: christophe varoqui
Headers show

Commit Message

Martin Wilck Nov. 18, 2017, 12:11 a.m. UTC
The log standard deviation can be calculated much more simply
by realizing

   sum_n (x_i - avg(x))^2 == sum_n x_i^2 - n * avg(x)^2

Also, use timespecsub rather than the custom timeval_to_usec,
and avoid taking log(0).

Signed-off-by: Martin Wilck <mwilck@suse.com>
---
 libmultipath/prioritizers/path_latency.c | 71 ++++++++++++++------------------
 1 file changed, 30 insertions(+), 41 deletions(-)

Comments

guanjunxiong 00401709 Nov. 19, 2017, 2:52 a.m. UTC | #1
On 2017/11/18 8:11, Martin Wilck wrote:
> The log standard deviation can be calculated much more simply
> by realizing
> 
>    sum_n (x_i - avg(x))^2 == sum_n x_i^2 - n * avg(x)^2
> 

I derive the equation:
 sum_n {(x_i - avg(x))^2} = sum_n{x_i^2 -2*x_i*avg(x) + avg(x)^2}
                          = sum_n{x_i^2} - 2*avg(x)*sum_n{x_i} + sum_n{avg(x)^2}
                          = sum_n{x_i^2} - 2*avg(x)*avg(x) + n*avg(x)^2
                          =  sum_n{x_i^2} + (n-2)*avg(x)^2

> Also, use timespecsub rather than the custom timeval_to_usec,
> and avoid taking log(0).
> 

Great.


> +	pp_pl_log(3, "%s: latency avg=%.2e uncertainty=%.1f prio=%d\n",

latency avg -> latency geometric avg ? Because in most cases,
avg means arithmetic avg , but in this case, it means geometric avg.


> +		  pp->dev, exp(lg_avglatency * lg_base),
> +		  exp(standard_deviation * lg_base), rc);

How can you get the uncertainty of Log-normal distribution
is the exp(standard_deviation * lg_base) ?

Thanks.
Regards
Guan

.

> +
>  	return rc;
>  }
> 

--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel
Martin Wilck Nov. 20, 2017, 8:46 a.m. UTC | #2
Hello Guan,

> On 2017/11/18 8:11, Martin Wilck wrote:
> > The log standard deviation can be calculated much more simply
> > by realizing
> > 
> >    sum_n (x_i - avg(x))^2 == sum_n x_i^2 - n * avg(x)^2
> > 
> 
> I derive the equation:
>  sum_n {(x_i - avg(x))^2} = sum_n{x_i^2 -2*x_i*avg(x) + avg(x)^2}
>                           = sum_n{x_i^2} - 2*avg(x)*sum_n{x_i} +
> sum_n{avg(x)^2}
>                           = sum_n{x_i^2} - 2*avg(x)*avg(x) +
> n*avg(x)^2
>                           =  sum_n{x_i^2} + (n-2)*avg(x)^2

No, that's wrong:

    avg(x) = (1/n) * sum_n(x_i)
=>  sum_n(x_i) = n * avg(x)

Thus the 2nd term in the line before the last in your derivation
is not "- 2*avg(x)*avg(x)", but "- 2*n*avg(x)*avg(x)", and the end
result becomes sum_n(x_i^2) - n*avg(x)^2.

> 
> > Also, use timespecsub rather than the custom timeval_to_usec,
> > and avoid taking log(0).
> > 
> 
> Great.
> 
> 
> > +	pp_pl_log(3, "%s: latency avg=%.2e uncertainty=%.1f
> > prio=%d\n",
> 
> latency avg -> latency geometric avg ? Because in most cases,
> avg means arithmetic avg , but in this case, it means geometric avg.

Yes, I meant the geometric average. I don't think we should bother the
user with these subtleties. Well, maybe it would feel better if we'd
use "geometric mean" rather than "avg" in the log message, alhough that
might again irritate some people who don't know the term ... I really
don't care much.

> > +		  pp->dev, exp(lg_avglatency * lg_base),
> > +		  exp(standard_deviation * lg_base), rc);
> 
> How can you get the uncertainty of Log-normal distribution
> is the exp(standard_deviation * lg_base) ?

The "width" of the normal distribution is measured in terms of the
standard deviation, sigma. In your patch, you correctly accounted for
the confidence levels of the 2*sigma environment 
(https://en.wikipedia.org/wiki/68%E2%80%9395%E2%80%9399.7_rule).

Here, we're assuming a log-normal distribution for the latency (it's a
practical assumption, not a statistical assertion - in reality the
latency probably rather follows an exponential or Poisson distribution
but we don't need to go into that detail). That means we're assuming
that log(latency) can be described by a normal distribution with a
certain standard deviation sigma around the log of the geometric mean.
Again, sigma is the "width" of that normal distribution. Thus with ~68%
probability, the log of the the latency is in the 1-sigma interval
around the average. Translating that back into "real" latency, with 68%
likelyhood it will be in the interval [(1/F) * gm, F*gm], where gm is
the geometric mean and F=exp(sigma). Therefore, F (which is
exp(standard_deviation * lg_base)) can be used as an estimate of the
"uncertainty factor" for the latency.

Agreed?

Regards
Martin
guanjunxiong 00401709 Dec. 7, 2017, 4:26 a.m. UTC | #3
Hi Martin,

I have tested this patch and found something needed to be correct. My comments inline.


On 2017/11/18 8:11, Martin Wilck wrote:
> The log standard deviation can be calculated much more simply
> by realizing
> 
>    sum_n (x_i - avg(x))^2 == sum_n x_i^2 - n * avg(x)^2
> 


> @@ -340,8 +323,14 @@ int getprio(struct path *pp, char *args, unsigned int timeout)
>  			  ".It is recommend to be set larger",
>  			  pp->dev, base_num);
>  
> +	standard_deviation = sqrt((sum_squares - lg_toldelay * lg_toldelay)
> +				  / (io_num -1));
>  
This assignment is wrong. It gets a "NAN" for standard_deviation.
It should be the following equation according to sum_n (x_i - avg(x))^2 == sum_n x_i^2 - n * avg(x)^2

standard_deviation = sqrt((sum_squares - io_num* lg_avglatency* lg_avglatency)/ (io_num -1));
                   = sqrt((sum_squares -  lg_toldelay* lg_avglatency)/ (io_num -1));


>  	rc = calcPrio(lg_avglatency, lg_maxavglatency, lg_minavglatency);
>  
> +	pp_pl_log(3, "%s: latency avg=%.2e uncertainty=%.1f prio=%d\n",
> +		  pp->dev, exp(lg_avglatency * lg_base),
> +		  exp(standard_deviation * lg_base), rc);
> +

I still have the doubt about the computation of the "uncertainty" item.
Because I have observed that the uncertainty is in the range of 1.3 ~ 1.6 whenever
the base_num varies from 1.1 to 10.

Do you mean the uncertainty as the "Error function" of (log) normal distribution?
Here is the definition of https://en.wikipedia.org/wiki/Error_function

I prefer to using  "Error function" that describes accumulated probability of  how  prio
locates in the (-inf, prio-1) and (prio+1, +inf).

Thanks
Guan

--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel
Martin Wilck Dec. 7, 2017, 3:56 p.m. UTC | #4
On Thu, 2017-12-07 at 12:26 +0800, Guan Junxiong wrote:
> Hi Martin,
> 
> I have tested this patch and found something needed to be correct. My
> comments inline.
> 
> 
> > @@ -340,8 +323,14 @@ int getprio(struct path *pp, char *args,
> > unsigned int timeout)
> >  			  ".It is recommend to be set larger",
> >  			  pp->dev, base_num);
> >  
> > +	standard_deviation = sqrt((sum_squares - lg_toldelay *
> > lg_toldelay)
> > +				  / (io_num -1));
> >  
> 
> This assignment is wrong. It gets a "NAN" for standard_deviation.
> It should be the following equation according to sum_n (x_i -
> avg(x))^2 == sum_n x_i^2 - n * avg(x)^2
> standard_deviation = sqrt((sum_squares - io_num* lg_avglatency*
> lg_avglatency)/ (io_num -1));
>                    = sqrt((sum_squares -  lg_toldelay*
> lg_avglatency)/ (io_num -1));

That's of course correct. I'll submit an update asap.

> I still have the doubt about the computation of the "uncertainty"
> item.
> Because I have observed that the uncertainty is in the range of 1.3 ~
> 1.6 whenever
> the base_num varies from 1.1 to 10.

> Do you mean the uncertainty as the "Error function" of (log) normal
> distribution?

> Here is the definition of
> https://en.wikipedia.org/wiki/Error_function
> 
> I prefer to using  "Error function" that describes accumulated
> probability of  how  prio
> locates in the (-inf, prio-1) and (prio+1, +inf).

There's a misunderstanding here.

My "uncertainty factor" describes the width of the distribution of the
*measured* latencies. It roughly represents the accuracy of the
measurement (indicating that 68%, or error_function (sqrt(1/2)), of the
measured values lie in the interval [avg/F, avg*F]). IOW, it tells you
how stable your latencies for a certain path are.

It has nothing to do with the artificial prio "bins" that the latency
prioritizer sets up. Therefore it *has to be independent* of base_num.
It just gives an indication how large base_num should be. 

I hope this makes it clear.

Martin

Patch
diff mbox

diff --git a/libmultipath/prioritizers/path_latency.c b/libmultipath/prioritizers/path_latency.c
index ce5c95dd7075..44472b77dd86 100644
--- a/libmultipath/prioritizers/path_latency.c
+++ b/libmultipath/prioritizers/path_latency.c
@@ -34,6 +34,7 @@ 
 #include "prio.h"
 #include "structs.h"
 #include "util.h"
+#include "time-util.h"
 
 #define pp_pl_log(prio, fmt, args...) condlog(prio, "path_latency prio: " fmt, ##args)
 
@@ -56,14 +57,6 @@ 
 
 #define DEF_BLK_SIZE		4096
 
-static double lg_path_latency[MAX_IO_NUM];
-
-static inline long long timeval_to_us(const struct timespec *tv)
-{
-	return ((long long)tv->tv_sec * USEC_PER_SEC) +
-	    (tv->tv_nsec / NSEC_PER_USEC);
-}
-
 static int prepare_directio_read(int fd, int *blksz, char **pbuf,
 		int *restore_flags)
 {
@@ -199,22 +192,6 @@  out:
 	return 0;
 }
 
-double calc_standard_deviation(double *lg_path_latency, int size,
-				  double lg_avglatency)
-{
-	int index;
-	double sum = 0;
-
-	for (index = 0; index < size; index++) {
-		sum += (lg_path_latency[index] - lg_avglatency) *
-			(lg_path_latency[index] - lg_avglatency);
-	}
-
-	sum /= (size - 1);
-
-	return sqrt(sum);
-}
-
 /*
  * Do not scale the prioriy in a certain range such as [0, 1024]
  * because scaling will eliminate the effect of base_num.
@@ -234,20 +211,16 @@  int calcPrio(double lg_avglatency, double lg_maxavglatency,
 int getprio(struct path *pp, char *args, unsigned int timeout)
 {
 	int rc, temp;
-	int index = 0;
 	int io_num = 0;
 	double base_num = 0;
 	double lg_avglatency, lg_maxavglatency, lg_minavglatency;
 	double standard_deviation;
 	double lg_toldelay = 0;
-	long long before, after;
-	struct timespec tv;
 	int blksize;
 	char *buf;
 	int restore_flags = 0;
 	double lg_base;
-	long long sum_latency = 0;
-	long long arith_mean_lat;
+	double sum_squares = 0;
 
 	if (pp->fd < 0)
 		return -1;
@@ -260,7 +233,6 @@  int getprio(struct path *pp, char *args, unsigned int timeout)
 				pp->dev, io_num, base_num);
 	}
 
-	memset(lg_path_latency, 0, sizeof(lg_path_latency));
 	lg_base = log(base_num);
 	lg_maxavglatency = log(MAX_AVG_LATENCY) / lg_base;
 	lg_minavglatency = log(MIN_AVG_LATENCY) / lg_base;
@@ -269,8 +241,10 @@  int getprio(struct path *pp, char *args, unsigned int timeout)
 
 	temp = io_num;
 	while (temp-- > 0) {
-		(void)clock_gettime(CLOCK_MONOTONIC, &tv);
-		before = timeval_to_us(&tv);
+		struct timespec tv_before, tv_after, tv_diff;
+		double diff, reldiff;
+
+		(void)clock_gettime(CLOCK_MONOTONIC, &tv_before);
 
 		if (do_directio_read(pp->fd, timeout, buf, blksize)) {
 			pp_pl_log(0, "%s: path down", pp->dev);
@@ -278,25 +252,34 @@  int getprio(struct path *pp, char *args, unsigned int timeout)
 			return -1;
 		}
 
-		(void)clock_gettime(CLOCK_MONOTONIC, &tv);
-		after = timeval_to_us(&tv);
+		(void)clock_gettime(CLOCK_MONOTONIC, &tv_after);
+
+		timespecsub(&tv_after, &tv_before, &tv_diff);
+		diff = tv_diff.tv_sec * 1000 * 1000 + tv_diff.tv_nsec / 1000;
+
+		if (diff == 0)
+			/*
+			 * Avoid taking log(0).
+			 * This unlikely case is treated as minimum -
+			 * the sums don't increase
+			 */
+			continue;
+
+		/* we scale by lg_base here */
+		reldiff = log(diff) / lg_base;
+
 		/*
 		 * We assume that the latency complies with Log-normal
 		 * distribution. The logarithm of latency is in normal
 		 * distribution.
 		 */
-		lg_path_latency[index] = log(after - before) / lg_base;
-		lg_toldelay += lg_path_latency[index++];
-		sum_latency += after - before;
+		lg_toldelay += reldiff;
+		sum_squares += reldiff * reldiff;
 	}
 
 	cleanup_directio_read(pp->fd, buf, restore_flags);
 
 	lg_avglatency = lg_toldelay / (long long)io_num;
-	arith_mean_lat = sum_latency / (long long)io_num;
-	pp_pl_log(4, "%s: arithmetic mean latency is (%lld us), geometric mean latency is (%lld us)",
-			pp->dev, arith_mean_lat,
-			(long long)pow(base_num, lg_avglatency));
 
 	if (lg_avglatency > lg_maxavglatency) {
 		pp_pl_log(2,
@@ -340,8 +323,14 @@  int getprio(struct path *pp, char *args, unsigned int timeout)
 			  ".It is recommend to be set larger",
 			  pp->dev, base_num);
 
+	standard_deviation = sqrt((sum_squares - lg_toldelay * lg_toldelay)
+				  / (io_num -1));
 
 	rc = calcPrio(lg_avglatency, lg_maxavglatency, lg_minavglatency);
 
+	pp_pl_log(3, "%s: latency avg=%.2e uncertainty=%.1f prio=%d\n",
+		  pp->dev, exp(lg_avglatency * lg_base),
+		  exp(standard_deviation * lg_base), rc);
+
 	return rc;
 }