Re: [PATCH 3/4] libmultipath: path latency: simplify getprio()

Re: [PATCH 3/4] libmultipath: path latency: simplify getprio()

[Guan Junxiong]

Hi Martin，

Thanks for your clarification. I agree with you now in this thread.

Regards,
Guan


On 2017/11/20 10:10, Martin wrote:
> 
> 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
> 

--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel

Re: [PATCH 3/4] libmultipath: path latency: simplify getprio()

[Martin Wilck]

On Thu, 2017-11-23 at 10:20 +0800, Guan Junxiong wrote:
> Hi Martin，
> 
> Thanks for your clarification. I agree with you now in this thread.

Thank you. I'd be grateful if you could give these patches a test in
your environment, I believe you have better testing equipment for this
stuff than I do. 

Just in case I made a silly mistake.

Martin

-- 
Dr. Martin Wilck <mwilck@suse.com>, Tel. +49 (0)911 74053 2107
SUSE Linux GmbH, GF: Felix Imendörffer, Jane Smithard, Graham Norton
HRB 21284 (AG Nürnberg)

--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel

[PATCH 0/4] path latency prio fixes

[Martin Wilck]

Hi Christophe and Guan,

I was hoping to get down to the review before Christophe committed
your your patch "calculate standard deviation on a logarithmic scale for
prioritizer path_latency". I failed to do this in timely manner, sorry.

But I still have some issues with the patch. Please check these fixes.
I also have remaining issues with the "intermittent IO accounting"
patch, will send these later.

Martin Wilck (4):
  libmultipath: path latency: fix default base num
  libmultipath: path latency: log threshold with p2
  libmultipath: path latency: simplify getprio()
  libmultipath: path latency: remove warnings

 libmultipath/prioritizers/path_latency.c | 112 ++++++++++---------------------
 1 file changed, 34 insertions(+), 78 deletions(-)

-- 
2.15.0

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

[Martin Wilck]

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(-)

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;
 }
-- 
2.15.0

Re: [PATCH 3/4] libmultipath: path latency: simplify getprio()

[Guan Junxiong]

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;
>  }
> 

Re: [PATCH 3/4] libmultipath: path latency: simplify getprio()

[Martin Wilck]

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

-- 
Dr. Martin Wilck <mwilck@suse.com>, Tel. +49 (0)911 74053 2107
SUSE Linux GmbH, GF: Felix Imendörffer, Jane Smithard, Graham Norton
HRB 21284 (AG Nürnberg)

--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel

Re: [PATCH 3/4] libmultipath: path latency: simplify getprio()

[Guan Junxiong]

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

Re: [PATCH 3/4] libmultipath: path latency: simplify getprio()

[Martin Wilck]

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

-- 
Dr. Martin Wilck <mwilck@suse.com>, Tel. +49 (0)911 74053 2107
SUSE Linux GmbH, GF: Felix Imendörffer, Jane Smithard, Graham Norton
HRB 21284 (AG Nürnberg)

--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel