[PATCH] bcache: implement PI controller for writeback rate

[PATCH] bcache: implement PI controller for writeback rate

[Michael Lyle]

bcache uses a control system to attempt to keep the amount of dirty data
in cache at a user-configured level, while not responding excessively to
transients and variations in write rate.  Previously, the system was a
PD controller; but the output from it was integrated, turning the
Proportional term into an Integral term, and turning the Derivative term
into a crude Proportional term.  Performance of the controller has been
uneven in production, and it has tended to respond slowly, oscillate,
and overshoot.

This patch set replaces the current control system with an explicit PI
controller and tuning that should be correct for most hardware.  By
default, it attempts to write at a rate that would retire 1/40th of the
current excess blocks per second.  An integral term in turn works to
remove steady state errors.

IMO, this yields benefits in simplicity (removing weighted average
filtering, etc) and system performance.

Another small change is a tunable parameter is introduced to allow the
user to specify a minimum rate at which dirty blocks are retired.
Ideally one would set this writeback_rate_minimum to a small percentage
of disk bandwidth, allowing the dirty data to be slowly cleaned out when
the system is inactive.  The old behavior would try and retire 1
sector/second, and the new default is 5 sectors/second.

Signed-off-by: Michael Lyle <mlyle@lyle.org>
---
 drivers/md/bcache/bcache.h    |  9 +++--
 drivers/md/bcache/sysfs.c     | 19 +++++-----
 drivers/md/bcache/writeback.c | 84 +++++++++++++++++++++++--------------------
 3 files changed, 60 insertions(+), 52 deletions(-)

diff --git a/drivers/md/bcache/bcache.h b/drivers/md/bcache/bcache.h
index dee542fff68e..f1cdf92e7399 100644
--- a/drivers/md/bcache/bcache.h
+++ b/drivers/md/bcache/bcache.h
@@ -265,9 +265,6 @@ struct bcache_device {
 	atomic_t		*stripe_sectors_dirty;
 	unsigned long		*full_dirty_stripes;
 
-	unsigned long		sectors_dirty_last;
-	long			sectors_dirty_derivative;
-
 	struct bio_set		*bio_split;
 
 	unsigned		data_csum:1;
@@ -361,12 +358,14 @@ struct cached_dev {
 
 	uint64_t		writeback_rate_target;
 	int64_t			writeback_rate_proportional;
-	int64_t			writeback_rate_derivative;
+	int64_t			writeback_rate_integral;
+	int64_t			writeback_rate_integral_scaled;
 	int64_t			writeback_rate_change;
 
 	unsigned		writeback_rate_update_seconds;
-	unsigned		writeback_rate_d_term;
+	unsigned		writeback_rate_i_term_inverse;
 	unsigned		writeback_rate_p_term_inverse;
+	unsigned		writeback_rate_minimum;
 };
 
 enum alloc_reserve {
diff --git a/drivers/md/bcache/sysfs.c b/drivers/md/bcache/sysfs.c
index f90f13616980..66a716d5f111 100644
--- a/drivers/md/bcache/sysfs.c
+++ b/drivers/md/bcache/sysfs.c
@@ -81,8 +81,9 @@ rw_attribute(writeback_delay);
 rw_attribute(writeback_rate);
 
 rw_attribute(writeback_rate_update_seconds);
-rw_attribute(writeback_rate_d_term);
+rw_attribute(writeback_rate_i_term_inverse);
 rw_attribute(writeback_rate_p_term_inverse);
+rw_attribute(writeback_rate_minimum);
 read_attribute(writeback_rate_debug);
 
 read_attribute(stripe_size);
@@ -130,15 +131,16 @@ SHOW(__bch_cached_dev)
 	sysfs_hprint(writeback_rate,	dc->writeback_rate.rate << 9);
 
 	var_print(writeback_rate_update_seconds);
-	var_print(writeback_rate_d_term);
+	var_print(writeback_rate_i_term_inverse);
 	var_print(writeback_rate_p_term_inverse);
+	var_print(writeback_rate_minimum);
 
 	if (attr == &sysfs_writeback_rate_debug) {
 		char rate[20];
 		char dirty[20];
 		char target[20];
 		char proportional[20];
-		char derivative[20];
+		char integral[20];
 		char change[20];
 		s64 next_io;
 
@@ -146,7 +148,7 @@ SHOW(__bch_cached_dev)
 		bch_hprint(dirty,	bcache_dev_sectors_dirty(&dc->disk) << 9);
 		bch_hprint(target,	dc->writeback_rate_target << 9);
 		bch_hprint(proportional,dc->writeback_rate_proportional << 9);
-		bch_hprint(derivative,	dc->writeback_rate_derivative << 9);
+		bch_hprint(integral,	dc->writeback_rate_integral_scaled << 9);
 		bch_hprint(change,	dc->writeback_rate_change << 9);
 
 		next_io = div64_s64(dc->writeback_rate.next - local_clock(),
@@ -157,11 +159,11 @@ SHOW(__bch_cached_dev)
 			       "dirty:\t\t%s\n"
 			       "target:\t\t%s\n"
 			       "proportional:\t%s\n"
-			       "derivative:\t%s\n"
+			       "integral:\t%s\n"
 			       "change:\t\t%s/sec\n"
 			       "next io:\t%llims\n",
 			       rate, dirty, target, proportional,
-			       derivative, change, next_io);
+			       integral, change, next_io);
 	}
 
 	sysfs_hprint(dirty_data,
@@ -213,7 +215,7 @@ STORE(__cached_dev)
 			    dc->writeback_rate.rate, 1, INT_MAX);
 
 	d_strtoul_nonzero(writeback_rate_update_seconds);
-	d_strtoul(writeback_rate_d_term);
+	d_strtoul(writeback_rate_i_term_inverse);
 	d_strtoul_nonzero(writeback_rate_p_term_inverse);
 
 	d_strtoi_h(sequential_cutoff);
@@ -319,8 +321,9 @@ static struct attribute *bch_cached_dev_files[] = {
 	&sysfs_writeback_percent,
 	&sysfs_writeback_rate,
 	&sysfs_writeback_rate_update_seconds,
-	&sysfs_writeback_rate_d_term,
+	&sysfs_writeback_rate_i_term_inverse,
 	&sysfs_writeback_rate_p_term_inverse,
+	&sysfs_writeback_rate_minimum,
 	&sysfs_writeback_rate_debug,
 	&sysfs_dirty_data,
 	&sysfs_stripe_size,
diff --git a/drivers/md/bcache/writeback.c b/drivers/md/bcache/writeback.c
index 42c66e76f05e..76e71e8ef356 100644
--- a/drivers/md/bcache/writeback.c
+++ b/drivers/md/bcache/writeback.c
@@ -24,48 +24,55 @@ static void __update_writeback_rate(struct cached_dev *dc)
 	uint64_t cache_sectors = c->nbuckets * c->sb.bucket_size;
 	uint64_t cache_dirty_target =
 		div_u64(cache_sectors * dc->writeback_percent, 100);
-
 	int64_t target = div64_u64(cache_dirty_target * bdev_sectors(dc->bdev),
 				   c->cached_dev_sectors);
 
-	/* PD controller */
-
+	/* PI controller:
+	 * Figures out the amount that should be written per second.
+	 *
+	 * First, the error (number of sectors that are dirty beyond our
+	 * target) is calculated.  The error is accumulated (numerically
+	 * integrated).
+	 *
+	 * Then, the proportional value and integral value are scaled
+	 * based on configured values.  These are stored as inverses to
+	 * avoid fixed point math and to make configuration easy-- e.g.
+	 * the default value of 100 for writeback_rate_p_term_inverse
+	 * attempts to write at a rate that would retire all the dirty
+	 * blocks in 100 seconds.
+	 */
 	int64_t dirty = bcache_dev_sectors_dirty(&dc->disk);
-	int64_t derivative = dirty - dc->disk.sectors_dirty_last;
-	int64_t proportional = dirty - target;
-	int64_t change;
-
-	dc->disk.sectors_dirty_last = dirty;
-
-	/* Scale to sectors per second */
-
-	proportional *= dc->writeback_rate_update_seconds;
-	proportional = div_s64(proportional, dc->writeback_rate_p_term_inverse);
-
-	derivative = div_s64(derivative, dc->writeback_rate_update_seconds);
-
-	derivative = ewma_add(dc->disk.sectors_dirty_derivative, derivative,
-			      (dc->writeback_rate_d_term /
-			       dc->writeback_rate_update_seconds) ?: 1, 0);
-
-	derivative *= dc->writeback_rate_d_term;
-	derivative = div_s64(derivative, dc->writeback_rate_p_term_inverse);
-
-	change = proportional + derivative;
+	int64_t error = dirty - target;
+	int64_t proportional_scaled =
+		div_s64(error, dc->writeback_rate_p_term_inverse);
+	int64_t integral_scaled, new_rate;
+
+	if ((error < 0 && dc->writeback_rate_integral > 0) ||
+	    (error > 0 && time_before64(local_clock(),
+			 dc->writeback_rate.next + NSEC_PER_MSEC))) {
+		/* Only decrease the integral term if it's more than
+		 * zero.  Only increase the integral term if the device
+		 * is keeping up.  (Don't wind up the integral
+		 * ineffectively in either case).
+		 *
+		 * It's necessary to scale this by
+		 * writeback_rate_update_seconds to keep the integral
+		 * term dimensioned properly.
+		 */
+		dc->writeback_rate_integral += error *
+			dc->writeback_rate_update_seconds;
+	}
 
-	/* Don't increase writeback rate if the device isn't keeping up */
-	if (change > 0 &&
-	    time_after64(local_clock(),
-			 dc->writeback_rate.next + NSEC_PER_MSEC))
-		change = 0;
+	integral_scaled = div_s64(dc->writeback_rate_integral,
+			dc->writeback_rate_i_term_inverse);
 
-	dc->writeback_rate.rate =
-		clamp_t(int64_t, (int64_t) dc->writeback_rate.rate + change,
-			1, NSEC_PER_MSEC);
+	new_rate = clamp_t(int64_t, (proportional_scaled + integral_scaled),
+			dc->writeback_rate_minimum, NSEC_PER_MSEC);
 
-	dc->writeback_rate_proportional = proportional;
-	dc->writeback_rate_derivative = derivative;
-	dc->writeback_rate_change = change;
+	dc->writeback_rate_proportional = proportional_scaled;
+	dc->writeback_rate_integral_scaled = integral_scaled;
+	dc->writeback_rate_change = new_rate - dc->writeback_rate.rate;
+	dc->writeback_rate.rate = new_rate;
 	dc->writeback_rate_target = target;
 }
 
@@ -491,8 +498,6 @@ void bch_sectors_dirty_init(struct cached_dev *dc)
 
 	bch_btree_map_keys(&op.op, dc->disk.c, &KEY(op.inode, 0, 0),
 			   sectors_dirty_init_fn, 0);
-
-	dc->disk.sectors_dirty_last = bcache_dev_sectors_dirty(&dc->disk);
 }
 
 void bch_cached_dev_writeback_init(struct cached_dev *dc)
@@ -506,10 +511,11 @@ void bch_cached_dev_writeback_init(struct cached_dev *dc)
 	dc->writeback_percent		= 10;
 	dc->writeback_delay		= 30;
 	dc->writeback_rate.rate		= 1024;
+	dc->writeback_rate_minimum	= 5;
 
 	dc->writeback_rate_update_seconds = 5;
-	dc->writeback_rate_d_term	= 30;
-	dc->writeback_rate_p_term_inverse = 6000;
+	dc->writeback_rate_p_term_inverse = 40;
+	dc->writeback_rate_i_term_inverse = 10000;
 
 	INIT_DELAYED_WORK(&dc->writeback_rate_update, update_writeback_rate);
 }
-- 
2.11.0

Re: [PATCH] bcache: implement PI controller for writeback rate

[Michael Lyle]

Hey everyone---

I'd appreciate any feedback you all can lend on this changeset.  I
know it's a bit of an awkward time with the opening of the merge
window to have a new functional change show up.  I also would
appreciate any comments on process / how to go about submitting work,
as I have not been active in the Linux kernel community in quite some
time.

This change makes a pretty substantial difference in the smoothness of
IO rates on my cached VM environment.  I see a couple of problems with
further review: I have an incorrect comment about the default p term
value, and there is a small bit of conflict with the patches that have
just gone out.  I can fix both of these quickly in a subsequent
revision.

It's also helpful for intermittent workloads to be able to write at a
somewhat higher rate out to disk.  Spending a few percent of disk
bandwidth on flushing dirty data-- to leave room to deal with new
bursts of workload-- is very helpful.

Thanks!

Mike


On Wed, Sep 6, 2017 at 12:56 AM, Michael Lyle <mlyle@lyle.org> wrote:
> bcache uses a control system to attempt to keep the amount of dirty data
> in cache at a user-configured level, while not responding excessively to
> transients and variations in write rate.  Previously, the system was a
> PD controller; but the output from it was integrated, turning the
> Proportional term into an Integral term, and turning the Derivative term
> into a crude Proportional term.  Performance of the controller has been
> uneven in production, and it has tended to respond slowly, oscillate,
> and overshoot.
>
> This patch set replaces the current control system with an explicit PI
> controller and tuning that should be correct for most hardware.  By
> default, it attempts to write at a rate that would retire 1/40th of the
> current excess blocks per second.  An integral term in turn works to
> remove steady state errors.
>
> IMO, this yields benefits in simplicity (removing weighted average
> filtering, etc) and system performance.
>
> Another small change is a tunable parameter is introduced to allow the
> user to specify a minimum rate at which dirty blocks are retired.
> Ideally one would set this writeback_rate_minimum to a small percentage
> of disk bandwidth, allowing the dirty data to be slowly cleaned out when
> the system is inactive.  The old behavior would try and retire 1
> sector/second, and the new default is 5 sectors/second.
>
> Signed-off-by: Michael Lyle <mlyle@lyle.org>
> ---
>  drivers/md/bcache/bcache.h    |  9 +++--
>  drivers/md/bcache/sysfs.c     | 19 +++++-----
>  drivers/md/bcache/writeback.c | 84 +++++++++++++++++++++++--------------------
>  3 files changed, 60 insertions(+), 52 deletions(-)
>
> diff --git a/drivers/md/bcache/bcache.h b/drivers/md/bcache/bcache.h
> index dee542fff68e..f1cdf92e7399 100644
> --- a/drivers/md/bcache/bcache.h
> +++ b/drivers/md/bcache/bcache.h
> @@ -265,9 +265,6 @@ struct bcache_device {
>         atomic_t                *stripe_sectors_dirty;
>         unsigned long           *full_dirty_stripes;
>
> -       unsigned long           sectors_dirty_last;
> -       long                    sectors_dirty_derivative;
> -
>         struct bio_set          *bio_split;
>
>         unsigned                data_csum:1;
> @@ -361,12 +358,14 @@ struct cached_dev {
>
>         uint64_t                writeback_rate_target;
>         int64_t                 writeback_rate_proportional;
> -       int64_t                 writeback_rate_derivative;
> +       int64_t                 writeback_rate_integral;
> +       int64_t                 writeback_rate_integral_scaled;
>         int64_t                 writeback_rate_change;
>
>         unsigned                writeback_rate_update_seconds;
> -       unsigned                writeback_rate_d_term;
> +       unsigned                writeback_rate_i_term_inverse;
>         unsigned                writeback_rate_p_term_inverse;
> +       unsigned                writeback_rate_minimum;
>  };
>
>  enum alloc_reserve {
> diff --git a/drivers/md/bcache/sysfs.c b/drivers/md/bcache/sysfs.c
> index f90f13616980..66a716d5f111 100644
> --- a/drivers/md/bcache/sysfs.c
> +++ b/drivers/md/bcache/sysfs.c
> @@ -81,8 +81,9 @@ rw_attribute(writeback_delay);
>  rw_attribute(writeback_rate);
>
>  rw_attribute(writeback_rate_update_seconds);
> -rw_attribute(writeback_rate_d_term);
> +rw_attribute(writeback_rate_i_term_inverse);
>  rw_attribute(writeback_rate_p_term_inverse);
> +rw_attribute(writeback_rate_minimum);
>  read_attribute(writeback_rate_debug);
>
>  read_attribute(stripe_size);
> @@ -130,15 +131,16 @@ SHOW(__bch_cached_dev)
>         sysfs_hprint(writeback_rate,    dc->writeback_rate.rate << 9);
>
>         var_print(writeback_rate_update_seconds);
> -       var_print(writeback_rate_d_term);
> +       var_print(writeback_rate_i_term_inverse);
>         var_print(writeback_rate_p_term_inverse);
> +       var_print(writeback_rate_minimum);
>
>         if (attr == &sysfs_writeback_rate_debug) {
>                 char rate[20];
>                 char dirty[20];
>                 char target[20];
>                 char proportional[20];
> -               char derivative[20];
> +               char integral[20];
>                 char change[20];
>                 s64 next_io;
>
> @@ -146,7 +148,7 @@ SHOW(__bch_cached_dev)
>                 bch_hprint(dirty,       bcache_dev_sectors_dirty(&dc->disk) << 9);
>                 bch_hprint(target,      dc->writeback_rate_target << 9);
>                 bch_hprint(proportional,dc->writeback_rate_proportional << 9);
> -               bch_hprint(derivative,  dc->writeback_rate_derivative << 9);
> +               bch_hprint(integral,    dc->writeback_rate_integral_scaled << 9);
>                 bch_hprint(change,      dc->writeback_rate_change << 9);
>
>                 next_io = div64_s64(dc->writeback_rate.next - local_clock(),
> @@ -157,11 +159,11 @@ SHOW(__bch_cached_dev)
>                                "dirty:\t\t%s\n"
>                                "target:\t\t%s\n"
>                                "proportional:\t%s\n"
> -                              "derivative:\t%s\n"
> +                              "integral:\t%s\n"
>                                "change:\t\t%s/sec\n"
>                                "next io:\t%llims\n",
>                                rate, dirty, target, proportional,
> -                              derivative, change, next_io);
> +                              integral, change, next_io);
>         }
>
>         sysfs_hprint(dirty_data,
> @@ -213,7 +215,7 @@ STORE(__cached_dev)
>                             dc->writeback_rate.rate, 1, INT_MAX);
>
>         d_strtoul_nonzero(writeback_rate_update_seconds);
> -       d_strtoul(writeback_rate_d_term);
> +       d_strtoul(writeback_rate_i_term_inverse);
>         d_strtoul_nonzero(writeback_rate_p_term_inverse);
>
>         d_strtoi_h(sequential_cutoff);
> @@ -319,8 +321,9 @@ static struct attribute *bch_cached_dev_files[] = {
>         &sysfs_writeback_percent,
>         &sysfs_writeback_rate,
>         &sysfs_writeback_rate_update_seconds,
> -       &sysfs_writeback_rate_d_term,
> +       &sysfs_writeback_rate_i_term_inverse,
>         &sysfs_writeback_rate_p_term_inverse,
> +       &sysfs_writeback_rate_minimum,
>         &sysfs_writeback_rate_debug,
>         &sysfs_dirty_data,
>         &sysfs_stripe_size,
> diff --git a/drivers/md/bcache/writeback.c b/drivers/md/bcache/writeback.c
> index 42c66e76f05e..76e71e8ef356 100644
> --- a/drivers/md/bcache/writeback.c
> +++ b/drivers/md/bcache/writeback.c
> @@ -24,48 +24,55 @@ static void __update_writeback_rate(struct cached_dev *dc)
>         uint64_t cache_sectors = c->nbuckets * c->sb.bucket_size;
>         uint64_t cache_dirty_target =
>                 div_u64(cache_sectors * dc->writeback_percent, 100);
> -
>         int64_t target = div64_u64(cache_dirty_target * bdev_sectors(dc->bdev),
>                                    c->cached_dev_sectors);
>
> -       /* PD controller */
> -
> +       /* PI controller:
> +        * Figures out the amount that should be written per second.
> +        *
> +        * First, the error (number of sectors that are dirty beyond our
> +        * target) is calculated.  The error is accumulated (numerically
> +        * integrated).
> +        *
> +        * Then, the proportional value and integral value are scaled
> +        * based on configured values.  These are stored as inverses to
> +        * avoid fixed point math and to make configuration easy-- e.g.
> +        * the default value of 100 for writeback_rate_p_term_inverse
> +        * attempts to write at a rate that would retire all the dirty
> +        * blocks in 100 seconds.
> +        */
>         int64_t dirty = bcache_dev_sectors_dirty(&dc->disk);
> -       int64_t derivative = dirty - dc->disk.sectors_dirty_last;
> -       int64_t proportional = dirty - target;
> -       int64_t change;
> -
> -       dc->disk.sectors_dirty_last = dirty;
> -
> -       /* Scale to sectors per second */
> -
> -       proportional *= dc->writeback_rate_update_seconds;
> -       proportional = div_s64(proportional, dc->writeback_rate_p_term_inverse);
> -
> -       derivative = div_s64(derivative, dc->writeback_rate_update_seconds);
> -
> -       derivative = ewma_add(dc->disk.sectors_dirty_derivative, derivative,
> -                             (dc->writeback_rate_d_term /
> -                              dc->writeback_rate_update_seconds) ?: 1, 0);
> -
> -       derivative *= dc->writeback_rate_d_term;
> -       derivative = div_s64(derivative, dc->writeback_rate_p_term_inverse);
> -
> -       change = proportional + derivative;
> +       int64_t error = dirty - target;
> +       int64_t proportional_scaled =
> +               div_s64(error, dc->writeback_rate_p_term_inverse);
> +       int64_t integral_scaled, new_rate;
> +
> +       if ((error < 0 && dc->writeback_rate_integral > 0) ||
> +           (error > 0 && time_before64(local_clock(),
> +                        dc->writeback_rate.next + NSEC_PER_MSEC))) {
> +               /* Only decrease the integral term if it's more than
> +                * zero.  Only increase the integral term if the device
> +                * is keeping up.  (Don't wind up the integral
> +                * ineffectively in either case).
> +                *
> +                * It's necessary to scale this by
> +                * writeback_rate_update_seconds to keep the integral
> +                * term dimensioned properly.
> +                */
> +               dc->writeback_rate_integral += error *
> +                       dc->writeback_rate_update_seconds;
> +       }
>
> -       /* Don't increase writeback rate if the device isn't keeping up */
> -       if (change > 0 &&
> -           time_after64(local_clock(),
> -                        dc->writeback_rate.next + NSEC_PER_MSEC))
> -               change = 0;
> +       integral_scaled = div_s64(dc->writeback_rate_integral,
> +                       dc->writeback_rate_i_term_inverse);
>
> -       dc->writeback_rate.rate =
> -               clamp_t(int64_t, (int64_t) dc->writeback_rate.rate + change,
> -                       1, NSEC_PER_MSEC);
> +       new_rate = clamp_t(int64_t, (proportional_scaled + integral_scaled),
> +                       dc->writeback_rate_minimum, NSEC_PER_MSEC);
>
> -       dc->writeback_rate_proportional = proportional;
> -       dc->writeback_rate_derivative = derivative;
> -       dc->writeback_rate_change = change;
> +       dc->writeback_rate_proportional = proportional_scaled;
> +       dc->writeback_rate_integral_scaled = integral_scaled;
> +       dc->writeback_rate_change = new_rate - dc->writeback_rate.rate;
> +       dc->writeback_rate.rate = new_rate;
>         dc->writeback_rate_target = target;
>  }
>
> @@ -491,8 +498,6 @@ void bch_sectors_dirty_init(struct cached_dev *dc)
>
>         bch_btree_map_keys(&op.op, dc->disk.c, &KEY(op.inode, 0, 0),
>                            sectors_dirty_init_fn, 0);
> -
> -       dc->disk.sectors_dirty_last = bcache_dev_sectors_dirty(&dc->disk);
>  }
>
>  void bch_cached_dev_writeback_init(struct cached_dev *dc)
> @@ -506,10 +511,11 @@ void bch_cached_dev_writeback_init(struct cached_dev *dc)
>         dc->writeback_percent           = 10;
>         dc->writeback_delay             = 30;
>         dc->writeback_rate.rate         = 1024;
> +       dc->writeback_rate_minimum      = 5;
>
>         dc->writeback_rate_update_seconds = 5;
> -       dc->writeback_rate_d_term       = 30;
> -       dc->writeback_rate_p_term_inverse = 6000;
> +       dc->writeback_rate_p_term_inverse = 40;
> +       dc->writeback_rate_i_term_inverse = 10000;
>
>         INIT_DELAYED_WORK(&dc->writeback_rate_update, update_writeback_rate);
>  }
> --
> 2.11.0
>

Re: [PATCH] bcache: implement PI controller for writeback rate

[Coly Li]

On 2017/9/7 上午9:54, Michael Lyle wrote:
> Hey everyone---
> 
> I'd appreciate any feedback you all can lend on this changeset.  I
> know it's a bit of an awkward time with the opening of the merge
> window to have a new functional change show up.  I also would
> appreciate any comments on process / how to go about submitting work,
> as I have not been active in the Linux kernel community in quite some
> time.
> 
> This change makes a pretty substantial difference in the smoothness of
> IO rates on my cached VM environment.  I see a couple of problems with
> further review: I have an incorrect comment about the default p term
> value, and there is a small bit of conflict with the patches that have
> just gone out.  I can fix both of these quickly in a subsequent
> revision.
> 
> It's also helpful for intermittent workloads to be able to write at a
> somewhat higher rate out to disk.  Spending a few percent of disk
> bandwidth on flushing dirty data-- to leave room to deal with new
> bursts of workload-- is very helpful.

Hi Michael,

One thing I care about is I/O latency of regular read/write requests.
For current PD controller, I observe the writeback rate can decrease
very fast to 1 sector/second to give almost all bandwidth to frond end
I/O requests. This behavior is good for data base users.

For this PI controller, I need to do more testing, and observe how it
works and behaves with different work loads. Before I am confident with
it for most of workloads I know, I am not able to response you very
fast. It will take time.

If you may provide more performance data (e.g. requests latency
distribution) comparing to current PD controller, that will be very
helpful for people to response this patch. For now, I need to understand
and test this patch.

Thanks.

Coly Li

> 
> 
> On Wed, Sep 6, 2017 at 12:56 AM, Michael Lyle <mlyle@lyle.org> wrote:
>> bcache uses a control system to attempt to keep the amount of dirty data
>> in cache at a user-configured level, while not responding excessively to
>> transients and variations in write rate.  Previously, the system was a
>> PD controller; but the output from it was integrated, turning the
>> Proportional term into an Integral term, and turning the Derivative term
>> into a crude Proportional term.  Performance of the controller has been
>> uneven in production, and it has tended to respond slowly, oscillate,
>> and overshoot.
>>
>> This patch set replaces the current control system with an explicit PI
>> controller and tuning that should be correct for most hardware.  By
>> default, it attempts to write at a rate that would retire 1/40th of the
>> current excess blocks per second.  An integral term in turn works to
>> remove steady state errors.
>>
>> IMO, this yields benefits in simplicity (removing weighted average
>> filtering, etc) and system performance.
>>
>> Another small change is a tunable parameter is introduced to allow the
>> user to specify a minimum rate at which dirty blocks are retired.
>> Ideally one would set this writeback_rate_minimum to a small percentage
>> of disk bandwidth, allowing the dirty data to be slowly cleaned out when
>> the system is inactive.  The old behavior would try and retire 1
>> sector/second, and the new default is 5 sectors/second.
>>
>> Signed-off-by: Michael Lyle <mlyle@lyle.org>
>> ---
>>  drivers/md/bcache/bcache.h    |  9 +++--
>>  drivers/md/bcache/sysfs.c     | 19 +++++-----
>>  drivers/md/bcache/writeback.c | 84 +++++++++++++++++++++++--------------------
>>  3 files changed, 60 insertions(+), 52 deletions(-)
>>
>> diff --git a/drivers/md/bcache/bcache.h b/drivers/md/bcache/bcache.h
>> index dee542fff68e..f1cdf92e7399 100644
>> --- a/drivers/md/bcache/bcache.h
>> +++ b/drivers/md/bcache/bcache.h
>> @@ -265,9 +265,6 @@ struct bcache_device {
>>         atomic_t                *stripe_sectors_dirty;
>>         unsigned long           *full_dirty_stripes;
>>
>> -       unsigned long           sectors_dirty_last;
>> -       long                    sectors_dirty_derivative;
>> -
>>         struct bio_set          *bio_split;
>>
>>         unsigned                data_csum:1;
>> @@ -361,12 +358,14 @@ struct cached_dev {
>>
>>         uint64_t                writeback_rate_target;
>>         int64_t                 writeback_rate_proportional;
>> -       int64_t                 writeback_rate_derivative;
>> +       int64_t                 writeback_rate_integral;
>> +       int64_t                 writeback_rate_integral_scaled;
>>         int64_t                 writeback_rate_change;
>>
>>         unsigned                writeback_rate_update_seconds;
>> -       unsigned                writeback_rate_d_term;
>> +       unsigned                writeback_rate_i_term_inverse;
>>         unsigned                writeback_rate_p_term_inverse;
>> +       unsigned                writeback_rate_minimum;
>>  };
>>
>>  enum alloc_reserve {
>> diff --git a/drivers/md/bcache/sysfs.c b/drivers/md/bcache/sysfs.c
>> index f90f13616980..66a716d5f111 100644
>> --- a/drivers/md/bcache/sysfs.c
>> +++ b/drivers/md/bcache/sysfs.c
>> @@ -81,8 +81,9 @@ rw_attribute(writeback_delay);
>>  rw_attribute(writeback_rate);
>>
>>  rw_attribute(writeback_rate_update_seconds);
>> -rw_attribute(writeback_rate_d_term);
>> +rw_attribute(writeback_rate_i_term_inverse);
>>  rw_attribute(writeback_rate_p_term_inverse);
>> +rw_attribute(writeback_rate_minimum);
>>  read_attribute(writeback_rate_debug);
>>
>>  read_attribute(stripe_size);
>> @@ -130,15 +131,16 @@ SHOW(__bch_cached_dev)
>>         sysfs_hprint(writeback_rate,    dc->writeback_rate.rate << 9);
>>
>>         var_print(writeback_rate_update_seconds);
>> -       var_print(writeback_rate_d_term);
>> +       var_print(writeback_rate_i_term_inverse);
>>         var_print(writeback_rate_p_term_inverse);
>> +       var_print(writeback_rate_minimum);
>>
>>         if (attr == &sysfs_writeback_rate_debug) {
>>                 char rate[20];
>>                 char dirty[20];
>>                 char target[20];
>>                 char proportional[20];
>> -               char derivative[20];
>> +               char integral[20];
>>                 char change[20];
>>                 s64 next_io;
>>
>> @@ -146,7 +148,7 @@ SHOW(__bch_cached_dev)
>>                 bch_hprint(dirty,       bcache_dev_sectors_dirty(&dc->disk) << 9);
>>                 bch_hprint(target,      dc->writeback_rate_target << 9);
>>                 bch_hprint(proportional,dc->writeback_rate_proportional << 9);
>> -               bch_hprint(derivative,  dc->writeback_rate_derivative << 9);
>> +               bch_hprint(integral,    dc->writeback_rate_integral_scaled << 9);
>>                 bch_hprint(change,      dc->writeback_rate_change << 9);
>>
>>                 next_io = div64_s64(dc->writeback_rate.next - local_clock(),
>> @@ -157,11 +159,11 @@ SHOW(__bch_cached_dev)
>>                                "dirty:\t\t%s\n"
>>                                "target:\t\t%s\n"
>>                                "proportional:\t%s\n"
>> -                              "derivative:\t%s\n"
>> +                              "integral:\t%s\n"
>>                                "change:\t\t%s/sec\n"
>>                                "next io:\t%llims\n",
>>                                rate, dirty, target, proportional,
>> -                              derivative, change, next_io);
>> +                              integral, change, next_io);
>>         }
>>
>>         sysfs_hprint(dirty_data,
>> @@ -213,7 +215,7 @@ STORE(__cached_dev)
>>                             dc->writeback_rate.rate, 1, INT_MAX);
>>
>>         d_strtoul_nonzero(writeback_rate_update_seconds);
>> -       d_strtoul(writeback_rate_d_term);
>> +       d_strtoul(writeback_rate_i_term_inverse);
>>         d_strtoul_nonzero(writeback_rate_p_term_inverse);
>>
>>         d_strtoi_h(sequential_cutoff);
>> @@ -319,8 +321,9 @@ static struct attribute *bch_cached_dev_files[] = {
>>         &sysfs_writeback_percent,
>>         &sysfs_writeback_rate,
>>         &sysfs_writeback_rate_update_seconds,
>> -       &sysfs_writeback_rate_d_term,
>> +       &sysfs_writeback_rate_i_term_inverse,
>>         &sysfs_writeback_rate_p_term_inverse,
>> +       &sysfs_writeback_rate_minimum,
>>         &sysfs_writeback_rate_debug,
>>         &sysfs_dirty_data,
>>         &sysfs_stripe_size,
>> diff --git a/drivers/md/bcache/writeback.c b/drivers/md/bcache/writeback.c
>> index 42c66e76f05e..76e71e8ef356 100644
>> --- a/drivers/md/bcache/writeback.c
>> +++ b/drivers/md/bcache/writeback.c
>> @@ -24,48 +24,55 @@ static void __update_writeback_rate(struct cached_dev *dc)
>>         uint64_t cache_sectors = c->nbuckets * c->sb.bucket_size;
>>         uint64_t cache_dirty_target =
>>                 div_u64(cache_sectors * dc->writeback_percent, 100);
>> -
>>         int64_t target = div64_u64(cache_dirty_target * bdev_sectors(dc->bdev),
>>                                    c->cached_dev_sectors);
>>
>> -       /* PD controller */
>> -
>> +       /* PI controller:
>> +        * Figures out the amount that should be written per second.
>> +        *
>> +        * First, the error (number of sectors that are dirty beyond our
>> +        * target) is calculated.  The error is accumulated (numerically
>> +        * integrated).
>> +        *
>> +        * Then, the proportional value and integral value are scaled
>> +        * based on configured values.  These are stored as inverses to
>> +        * avoid fixed point math and to make configuration easy-- e.g.
>> +        * the default value of 100 for writeback_rate_p_term_inverse
>> +        * attempts to write at a rate that would retire all the dirty
>> +        * blocks in 100 seconds.
>> +        */
>>         int64_t dirty = bcache_dev_sectors_dirty(&dc->disk);
>> -       int64_t derivative = dirty - dc->disk.sectors_dirty_last;
>> -       int64_t proportional = dirty - target;
>> -       int64_t change;
>> -
>> -       dc->disk.sectors_dirty_last = dirty;
>> -
>> -       /* Scale to sectors per second */
>> -
>> -       proportional *= dc->writeback_rate_update_seconds;
>> -       proportional = div_s64(proportional, dc->writeback_rate_p_term_inverse);
>> -
>> -       derivative = div_s64(derivative, dc->writeback_rate_update_seconds);
>> -
>> -       derivative = ewma_add(dc->disk.sectors_dirty_derivative, derivative,
>> -                             (dc->writeback_rate_d_term /
>> -                              dc->writeback_rate_update_seconds) ?: 1, 0);
>> -
>> -       derivative *= dc->writeback_rate_d_term;
>> -       derivative = div_s64(derivative, dc->writeback_rate_p_term_inverse);
>> -
>> -       change = proportional + derivative;
>> +       int64_t error = dirty - target;
>> +       int64_t proportional_scaled =
>> +               div_s64(error, dc->writeback_rate_p_term_inverse);
>> +       int64_t integral_scaled, new_rate;
>> +
>> +       if ((error < 0 && dc->writeback_rate_integral > 0) ||
>> +           (error > 0 && time_before64(local_clock(),
>> +                        dc->writeback_rate.next + NSEC_PER_MSEC))) {
>> +               /* Only decrease the integral term if it's more than
>> +                * zero.  Only increase the integral term if the device
>> +                * is keeping up.  (Don't wind up the integral
>> +                * ineffectively in either case).
>> +                *
>> +                * It's necessary to scale this by
>> +                * writeback_rate_update_seconds to keep the integral
>> +                * term dimensioned properly.
>> +                */
>> +               dc->writeback_rate_integral += error *
>> +                       dc->writeback_rate_update_seconds;
>> +       }
>>
>> -       /* Don't increase writeback rate if the device isn't keeping up */
>> -       if (change > 0 &&
>> -           time_after64(local_clock(),
>> -                        dc->writeback_rate.next + NSEC_PER_MSEC))
>> -               change = 0;
>> +       integral_scaled = div_s64(dc->writeback_rate_integral,
>> +                       dc->writeback_rate_i_term_inverse);
>>
>> -       dc->writeback_rate.rate =
>> -               clamp_t(int64_t, (int64_t) dc->writeback_rate.rate + change,
>> -                       1, NSEC_PER_MSEC);
>> +       new_rate = clamp_t(int64_t, (proportional_scaled + integral_scaled),
>> +                       dc->writeback_rate_minimum, NSEC_PER_MSEC);
>>
>> -       dc->writeback_rate_proportional = proportional;
>> -       dc->writeback_rate_derivative = derivative;
>> -       dc->writeback_rate_change = change;
>> +       dc->writeback_rate_proportional = proportional_scaled;
>> +       dc->writeback_rate_integral_scaled = integral_scaled;
>> +       dc->writeback_rate_change = new_rate - dc->writeback_rate.rate;
>> +       dc->writeback_rate.rate = new_rate;
>>         dc->writeback_rate_target = target;
>>  }
>>
>> @@ -491,8 +498,6 @@ void bch_sectors_dirty_init(struct cached_dev *dc)
>>
>>         bch_btree_map_keys(&op.op, dc->disk.c, &KEY(op.inode, 0, 0),
>>                            sectors_dirty_init_fn, 0);
>> -
>> -       dc->disk.sectors_dirty_last = bcache_dev_sectors_dirty(&dc->disk);
>>  }
>>
>>  void bch_cached_dev_writeback_init(struct cached_dev *dc)
>> @@ -506,10 +511,11 @@ void bch_cached_dev_writeback_init(struct cached_dev *dc)
>>         dc->writeback_percent           = 10;
>>         dc->writeback_delay             = 30;
>>         dc->writeback_rate.rate         = 1024;
>> +       dc->writeback_rate_minimum      = 5;
>>
>>         dc->writeback_rate_update_seconds = 5;
>> -       dc->writeback_rate_d_term       = 30;
>> -       dc->writeback_rate_p_term_inverse = 6000;
>> +       dc->writeback_rate_p_term_inverse = 40;
>> +       dc->writeback_rate_i_term_inverse = 10000;
>>
>>         INIT_DELAYED_WORK(&dc->writeback_rate_update, update_writeback_rate);
>>  }
>> --
>> 2.11.0
>>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-bcache" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 

Re: [PATCH] bcache: implement PI controller for writeback rate

[Michael Lyle]

Coly--

Sure.  I have some plots at http://jar.lyle.org/~mlyle/ctr/ -- they
show the response of the controller to a step (increase from 0 to 1000
sectors/second of IO), and to an impulse (a single unexpected 100,000
sectors of dirty data) showing up.

If anything, this controller is quicker to "turn off writes" and
remove workload from the backing disks than the previous one (though
how much it flushes when "idle" is configurable, now).  I would often
see the old controller continue writing back data long after the
workload was removed, or oscillate between writing large amounts and
doing very little.

It's important to note that the old controller claims to be a PD
controller, but it is actually a PI controller-- the output from the
PD controller was accumulated, which has the effect of numerically
integrating everything.  It is a very strange PI controller, too-- not
formulated in any of the "normal" ways that control systems are built.

Looking at the plots, there's a few different things to consider/look
at.  The first is how quickly the controller arrests a positive trend
after a step.  With default tuning, this is about 75 seconds.  Next,
is how well the value converges to the set point-- this is relatively
quick in both the step and impulse analyses.  Finally, the amount of
negative-going overshoot-- how much it writes "past" the setpoint is
important.  For an impulse, the current tuning overshoots about 10%--
if the system is at the target, and you dirty 100MB of the cache, it
will write back about 110MB.

The existing system writes **much further** past the setpoint because
it is only able to start really reducing the write rate when the
target amount of dirty data is reached.

Mike

On Wed, Sep 6, 2017 at 10:27 PM, Coly Li <i@coly.li> wrote:
> On 2017/9/7 上午9:54, Michael Lyle wrote:
>> Hey everyone---
>>
>> I'd appreciate any feedback you all can lend on this changeset.  I
>> know it's a bit of an awkward time with the opening of the merge
>> window to have a new functional change show up.  I also would
>> appreciate any comments on process / how to go about submitting work,
>> as I have not been active in the Linux kernel community in quite some
>> time.
>>
>> This change makes a pretty substantial difference in the smoothness of
>> IO rates on my cached VM environment.  I see a couple of problems with
>> further review: I have an incorrect comment about the default p term
>> value, and there is a small bit of conflict with the patches that have
>> just gone out.  I can fix both of these quickly in a subsequent
>> revision.
>>
>> It's also helpful for intermittent workloads to be able to write at a
>> somewhat higher rate out to disk.  Spending a few percent of disk
>> bandwidth on flushing dirty data-- to leave room to deal with new
>> bursts of workload-- is very helpful.
>
> Hi Michael,
>
> One thing I care about is I/O latency of regular read/write requests.
> For current PD controller, I observe the writeback rate can decrease
> very fast to 1 sector/second to give almost all bandwidth to frond end
> I/O requests. This behavior is good for data base users.
>
> For this PI controller, I need to do more testing, and observe how it
> works and behaves with different work loads. Before I am confident with
> it for most of workloads I know, I am not able to response you very
> fast. It will take time.
>
> If you may provide more performance data (e.g. requests latency
> distribution) comparing to current PD controller, that will be very
> helpful for people to response this patch. For now, I need to understand
> and test this patch.
>
> Thanks.
>
> Coly Li
>
>>
>>
>> On Wed, Sep 6, 2017 at 12:56 AM, Michael Lyle <mlyle@lyle.org> wrote:
>>> bcache uses a control system to attempt to keep the amount of dirty data
>>> in cache at a user-configured level, while not responding excessively to
>>> transients and variations in write rate.  Previously, the system was a
>>> PD controller; but the output from it was integrated, turning the
>>> Proportional term into an Integral term, and turning the Derivative term
>>> into a crude Proportional term.  Performance of the controller has been
>>> uneven in production, and it has tended to respond slowly, oscillate,
>>> and overshoot.
>>>
>>> This patch set replaces the current control system with an explicit PI
>>> controller and tuning that should be correct for most hardware.  By
>>> default, it attempts to write at a rate that would retire 1/40th of the
>>> current excess blocks per second.  An integral term in turn works to
>>> remove steady state errors.
>>>
>>> IMO, this yields benefits in simplicity (removing weighted average
>>> filtering, etc) and system performance.
>>>
>>> Another small change is a tunable parameter is introduced to allow the
>>> user to specify a minimum rate at which dirty blocks are retired.
>>> Ideally one would set this writeback_rate_minimum to a small percentage
>>> of disk bandwidth, allowing the dirty data to be slowly cleaned out when
>>> the system is inactive.  The old behavior would try and retire 1
>>> sector/second, and the new default is 5 sectors/second.
>>>
>>> Signed-off-by: Michael Lyle <mlyle@lyle.org>
>>> ---
>>>  drivers/md/bcache/bcache.h    |  9 +++--
>>>  drivers/md/bcache/sysfs.c     | 19 +++++-----
>>>  drivers/md/bcache/writeback.c | 84 +++++++++++++++++++++++--------------------
>>>  3 files changed, 60 insertions(+), 52 deletions(-)
>>>
>>> diff --git a/drivers/md/bcache/bcache.h b/drivers/md/bcache/bcache.h
>>> index dee542fff68e..f1cdf92e7399 100644
>>> --- a/drivers/md/bcache/bcache.h
>>> +++ b/drivers/md/bcache/bcache.h
>>> @@ -265,9 +265,6 @@ struct bcache_device {
>>>         atomic_t                *stripe_sectors_dirty;
>>>         unsigned long           *full_dirty_stripes;
>>>
>>> -       unsigned long           sectors_dirty_last;
>>> -       long                    sectors_dirty_derivative;
>>> -
>>>         struct bio_set          *bio_split;
>>>
>>>         unsigned                data_csum:1;
>>> @@ -361,12 +358,14 @@ struct cached_dev {
>>>
>>>         uint64_t                writeback_rate_target;
>>>         int64_t                 writeback_rate_proportional;
>>> -       int64_t                 writeback_rate_derivative;
>>> +       int64_t                 writeback_rate_integral;
>>> +       int64_t                 writeback_rate_integral_scaled;
>>>         int64_t                 writeback_rate_change;
>>>
>>>         unsigned                writeback_rate_update_seconds;
>>> -       unsigned                writeback_rate_d_term;
>>> +       unsigned                writeback_rate_i_term_inverse;
>>>         unsigned                writeback_rate_p_term_inverse;
>>> +       unsigned                writeback_rate_minimum;
>>>  };
>>>
>>>  enum alloc_reserve {
>>> diff --git a/drivers/md/bcache/sysfs.c b/drivers/md/bcache/sysfs.c
>>> index f90f13616980..66a716d5f111 100644
>>> --- a/drivers/md/bcache/sysfs.c
>>> +++ b/drivers/md/bcache/sysfs.c
>>> @@ -81,8 +81,9 @@ rw_attribute(writeback_delay);
>>>  rw_attribute(writeback_rate);
>>>
>>>  rw_attribute(writeback_rate_update_seconds);
>>> -rw_attribute(writeback_rate_d_term);
>>> +rw_attribute(writeback_rate_i_term_inverse);
>>>  rw_attribute(writeback_rate_p_term_inverse);
>>> +rw_attribute(writeback_rate_minimum);
>>>  read_attribute(writeback_rate_debug);
>>>
>>>  read_attribute(stripe_size);
>>> @@ -130,15 +131,16 @@ SHOW(__bch_cached_dev)
>>>         sysfs_hprint(writeback_rate,    dc->writeback_rate.rate << 9);
>>>
>>>         var_print(writeback_rate_update_seconds);
>>> -       var_print(writeback_rate_d_term);
>>> +       var_print(writeback_rate_i_term_inverse);
>>>         var_print(writeback_rate_p_term_inverse);
>>> +       var_print(writeback_rate_minimum);
>>>
>>>         if (attr == &sysfs_writeback_rate_debug) {
>>>                 char rate[20];
>>>                 char dirty[20];
>>>                 char target[20];
>>>                 char proportional[20];
>>> -               char derivative[20];
>>> +               char integral[20];
>>>                 char change[20];
>>>                 s64 next_io;
>>>
>>> @@ -146,7 +148,7 @@ SHOW(__bch_cached_dev)
>>>                 bch_hprint(dirty,       bcache_dev_sectors_dirty(&dc->disk) << 9);
>>>                 bch_hprint(target,      dc->writeback_rate_target << 9);
>>>                 bch_hprint(proportional,dc->writeback_rate_proportional << 9);
>>> -               bch_hprint(derivative,  dc->writeback_rate_derivative << 9);
>>> +               bch_hprint(integral,    dc->writeback_rate_integral_scaled << 9);
>>>                 bch_hprint(change,      dc->writeback_rate_change << 9);
>>>
>>>                 next_io = div64_s64(dc->writeback_rate.next - local_clock(),
>>> @@ -157,11 +159,11 @@ SHOW(__bch_cached_dev)
>>>                                "dirty:\t\t%s\n"
>>>                                "target:\t\t%s\n"
>>>                                "proportional:\t%s\n"
>>> -                              "derivative:\t%s\n"
>>> +                              "integral:\t%s\n"
>>>                                "change:\t\t%s/sec\n"
>>>                                "next io:\t%llims\n",
>>>                                rate, dirty, target, proportional,
>>> -                              derivative, change, next_io);
>>> +                              integral, change, next_io);
>>>         }
>>>
>>>         sysfs_hprint(dirty_data,
>>> @@ -213,7 +215,7 @@ STORE(__cached_dev)
>>>                             dc->writeback_rate.rate, 1, INT_MAX);
>>>
>>>         d_strtoul_nonzero(writeback_rate_update_seconds);
>>> -       d_strtoul(writeback_rate_d_term);
>>> +       d_strtoul(writeback_rate_i_term_inverse);
>>>         d_strtoul_nonzero(writeback_rate_p_term_inverse);
>>>
>>>         d_strtoi_h(sequential_cutoff);
>>> @@ -319,8 +321,9 @@ static struct attribute *bch_cached_dev_files[] = {
>>>         &sysfs_writeback_percent,
>>>         &sysfs_writeback_rate,
>>>         &sysfs_writeback_rate_update_seconds,
>>> -       &sysfs_writeback_rate_d_term,
>>> +       &sysfs_writeback_rate_i_term_inverse,
>>>         &sysfs_writeback_rate_p_term_inverse,
>>> +       &sysfs_writeback_rate_minimum,
>>>         &sysfs_writeback_rate_debug,
>>>         &sysfs_dirty_data,
>>>         &sysfs_stripe_size,
>>> diff --git a/drivers/md/bcache/writeback.c b/drivers/md/bcache/writeback.c
>>> index 42c66e76f05e..76e71e8ef356 100644
>>> --- a/drivers/md/bcache/writeback.c
>>> +++ b/drivers/md/bcache/writeback.c
>>> @@ -24,48 +24,55 @@ static void __update_writeback_rate(struct cached_dev *dc)
>>>         uint64_t cache_sectors = c->nbuckets * c->sb.bucket_size;
>>>         uint64_t cache_dirty_target =
>>>                 div_u64(cache_sectors * dc->writeback_percent, 100);
>>> -
>>>         int64_t target = div64_u64(cache_dirty_target * bdev_sectors(dc->bdev),
>>>                                    c->cached_dev_sectors);
>>>
>>> -       /* PD controller */
>>> -
>>> +       /* PI controller:
>>> +        * Figures out the amount that should be written per second.
>>> +        *
>>> +        * First, the error (number of sectors that are dirty beyond our
>>> +        * target) is calculated.  The error is accumulated (numerically
>>> +        * integrated).
>>> +        *
>>> +        * Then, the proportional value and integral value are scaled
>>> +        * based on configured values.  These are stored as inverses to
>>> +        * avoid fixed point math and to make configuration easy-- e.g.
>>> +        * the default value of 100 for writeback_rate_p_term_inverse
>>> +        * attempts to write at a rate that would retire all the dirty
>>> +        * blocks in 100 seconds.
>>> +        */
>>>         int64_t dirty = bcache_dev_sectors_dirty(&dc->disk);
>>> -       int64_t derivative = dirty - dc->disk.sectors_dirty_last;
>>> -       int64_t proportional = dirty - target;
>>> -       int64_t change;
>>> -
>>> -       dc->disk.sectors_dirty_last = dirty;
>>> -
>>> -       /* Scale to sectors per second */
>>> -
>>> -       proportional *= dc->writeback_rate_update_seconds;
>>> -       proportional = div_s64(proportional, dc->writeback_rate_p_term_inverse);
>>> -
>>> -       derivative = div_s64(derivative, dc->writeback_rate_update_seconds);
>>> -
>>> -       derivative = ewma_add(dc->disk.sectors_dirty_derivative, derivative,
>>> -                             (dc->writeback_rate_d_term /
>>> -                              dc->writeback_rate_update_seconds) ?: 1, 0);
>>> -
>>> -       derivative *= dc->writeback_rate_d_term;
>>> -       derivative = div_s64(derivative, dc->writeback_rate_p_term_inverse);
>>> -
>>> -       change = proportional + derivative;
>>> +       int64_t error = dirty - target;
>>> +       int64_t proportional_scaled =
>>> +               div_s64(error, dc->writeback_rate_p_term_inverse);
>>> +       int64_t integral_scaled, new_rate;
>>> +
>>> +       if ((error < 0 && dc->writeback_rate_integral > 0) ||
>>> +           (error > 0 && time_before64(local_clock(),
>>> +                        dc->writeback_rate.next + NSEC_PER_MSEC))) {
>>> +               /* Only decrease the integral term if it's more than
>>> +                * zero.  Only increase the integral term if the device
>>> +                * is keeping up.  (Don't wind up the integral
>>> +                * ineffectively in either case).
>>> +                *
>>> +                * It's necessary to scale this by
>>> +                * writeback_rate_update_seconds to keep the integral
>>> +                * term dimensioned properly.
>>> +                */
>>> +               dc->writeback_rate_integral += error *
>>> +                       dc->writeback_rate_update_seconds;
>>> +       }
>>>
>>> -       /* Don't increase writeback rate if the device isn't keeping up */
>>> -       if (change > 0 &&
>>> -           time_after64(local_clock(),
>>> -                        dc->writeback_rate.next + NSEC_PER_MSEC))
>>> -               change = 0;
>>> +       integral_scaled = div_s64(dc->writeback_rate_integral,
>>> +                       dc->writeback_rate_i_term_inverse);
>>>
>>> -       dc->writeback_rate.rate =
>>> -               clamp_t(int64_t, (int64_t) dc->writeback_rate.rate + change,
>>> -                       1, NSEC_PER_MSEC);
>>> +       new_rate = clamp_t(int64_t, (proportional_scaled + integral_scaled),
>>> +                       dc->writeback_rate_minimum, NSEC_PER_MSEC);
>>>
>>> -       dc->writeback_rate_proportional = proportional;
>>> -       dc->writeback_rate_derivative = derivative;
>>> -       dc->writeback_rate_change = change;
>>> +       dc->writeback_rate_proportional = proportional_scaled;
>>> +       dc->writeback_rate_integral_scaled = integral_scaled;
>>> +       dc->writeback_rate_change = new_rate - dc->writeback_rate.rate;
>>> +       dc->writeback_rate.rate = new_rate;
>>>         dc->writeback_rate_target = target;
>>>  }
>>>
>>> @@ -491,8 +498,6 @@ void bch_sectors_dirty_init(struct cached_dev *dc)
>>>
>>>         bch_btree_map_keys(&op.op, dc->disk.c, &KEY(op.inode, 0, 0),
>>>                            sectors_dirty_init_fn, 0);
>>> -
>>> -       dc->disk.sectors_dirty_last = bcache_dev_sectors_dirty(&dc->disk);
>>>  }
>>>
>>>  void bch_cached_dev_writeback_init(struct cached_dev *dc)
>>> @@ -506,10 +511,11 @@ void bch_cached_dev_writeback_init(struct cached_dev *dc)
>>>         dc->writeback_percent           = 10;
>>>         dc->writeback_delay             = 30;
>>>         dc->writeback_rate.rate         = 1024;
>>> +       dc->writeback_rate_minimum      = 5;
>>>
>>>         dc->writeback_rate_update_seconds = 5;
>>> -       dc->writeback_rate_d_term       = 30;
>>> -       dc->writeback_rate_p_term_inverse = 6000;
>>> +       dc->writeback_rate_p_term_inverse = 40;
>>> +       dc->writeback_rate_i_term_inverse = 10000;
>>>
>>>         INIT_DELAYED_WORK(&dc->writeback_rate_update, update_writeback_rate);
>>>  }
>>> --
>>> 2.11.0
>>>
>> --
>> To unsubscribe from this list: send the line "unsubscribe linux-bcache" in
>> the body of a message to majordomo@vger.kernel.org
>> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-bcache" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] bcache: implement PI controller for writeback rate

[Coly Li]

On 2017/9/7 下午11:29, Michael Lyle wrote:
> Coly--
> 
> Sure.  I have some plots at http://jar.lyle.org/~mlyle/ctr/ -- they
> show the response of the controller to a step (increase from 0 to 1000
> sectors/second of IO), and to an impulse (a single unexpected 100,000
> sectors of dirty data) showing up.
> 
> If anything, this controller is quicker to "turn off writes" and
> remove workload from the backing disks than the previous one (though
> how much it flushes when "idle" is configurable, now).  I would often
> see the old controller continue writing back data long after the
> workload was removed, or oscillate between writing large amounts and
> doing very little.
> 
> It's important to note that the old controller claims to be a PD
> controller, but it is actually a PI controller-- the output from the
> PD controller was accumulated, which has the effect of numerically
> integrating everything.  It is a very strange PI controller, too-- not
> formulated in any of the "normal" ways that control systems are built.
> 
> Looking at the plots, there's a few different things to consider/look
> at.  The first is how quickly the controller arrests a positive trend
> after a step.  With default tuning, this is about 75 seconds.  Next,
> is how well the value converges to the set point-- this is relatively
> quick in both the step and impulse analyses.  Finally, the amount of
> negative-going overshoot-- how much it writes "past" the setpoint is
> important.  For an impulse, the current tuning overshoots about 10%--
> if the system is at the target, and you dirty 100MB of the cache, it
> will write back about 110MB.
> 
> The existing system writes **much further** past the setpoint because
> it is only able to start really reducing the write rate when the
> target amount of dirty data is reached.
> 

Hi Mike,

Thank you for the informative reply. I add this patch to my for-test
patch pool. My submit for 4.14 is done, I hope we can try best to make
it in 4.15.

Coly Li

> 
> On Wed, Sep 6, 2017 at 10:27 PM, Coly Li <i@coly.li> wrote:
>> On 2017/9/7 上午9:54, Michael Lyle wrote:
>>> Hey everyone---
>>>
>>> I'd appreciate any feedback you all can lend on this changeset.  I
>>> know it's a bit of an awkward time with the opening of the merge
>>> window to have a new functional change show up.  I also would
>>> appreciate any comments on process / how to go about submitting work,
>>> as I have not been active in the Linux kernel community in quite some
>>> time.
>>>
>>> This change makes a pretty substantial difference in the smoothness of
>>> IO rates on my cached VM environment.  I see a couple of problems with
>>> further review: I have an incorrect comment about the default p term
>>> value, and there is a small bit of conflict with the patches that have
>>> just gone out.  I can fix both of these quickly in a subsequent
>>> revision.
>>>
>>> It's also helpful for intermittent workloads to be able to write at a
>>> somewhat higher rate out to disk.  Spending a few percent of disk
>>> bandwidth on flushing dirty data-- to leave room to deal with new
>>> bursts of workload-- is very helpful.
>>
>> Hi Michael,
>>
>> One thing I care about is I/O latency of regular read/write requests.
>> For current PD controller, I observe the writeback rate can decrease
>> very fast to 1 sector/second to give almost all bandwidth to frond end
>> I/O requests. This behavior is good for data base users.
>>
>> For this PI controller, I need to do more testing, and observe how it
>> works and behaves with different work loads. Before I am confident with
>> it for most of workloads I know, I am not able to response you very
>> fast. It will take time.
>>
>> If you may provide more performance data (e.g. requests latency
>> distribution) comparing to current PD controller, that will be very
>> helpful for people to response this patch. For now, I need to understand
>> and test this patch.
>>
>> Thanks.
>>
>> Coly Li
>>
>>>
>>>
>>> On Wed, Sep 6, 2017 at 12:56 AM, Michael Lyle <mlyle@lyle.org> wrote:
>>>> bcache uses a control system to attempt to keep the amount of dirty data
>>>> in cache at a user-configured level, while not responding excessively to
>>>> transients and variations in write rate.  Previously, the system was a
>>>> PD controller; but the output from it was integrated, turning the
>>>> Proportional term into an Integral term, and turning the Derivative term
>>>> into a crude Proportional term.  Performance of the controller has been
>>>> uneven in production, and it has tended to respond slowly, oscillate,
>>>> and overshoot.
>>>>
>>>> This patch set replaces the current control system with an explicit PI
>>>> controller and tuning that should be correct for most hardware.  By
>>>> default, it attempts to write at a rate that would retire 1/40th of the
>>>> current excess blocks per second.  An integral term in turn works to
>>>> remove steady state errors.
>>>>
>>>> IMO, this yields benefits in simplicity (removing weighted average
>>>> filtering, etc) and system performance.
>>>>
>>>> Another small change is a tunable parameter is introduced to allow the
>>>> user to specify a minimum rate at which dirty blocks are retired.
>>>> Ideally one would set this writeback_rate_minimum to a small percentage
>>>> of disk bandwidth, allowing the dirty data to be slowly cleaned out when
>>>> the system is inactive.  The old behavior would try and retire 1
>>>> sector/second, and the new default is 5 sectors/second.
>>>>
>>>> Signed-off-by: Michael Lyle <mlyle@lyle.org>
>>>> ---
>>>>  drivers/md/bcache/bcache.h    |  9 +++--
>>>>  drivers/md/bcache/sysfs.c     | 19 +++++-----
>>>>  drivers/md/bcache/writeback.c | 84 +++++++++++++++++++++++--------------------
>>>>  3 files changed, 60 insertions(+), 52 deletions(-)
>>>>
>>>> diff --git a/drivers/md/bcache/bcache.h b/drivers/md/bcache/bcache.h
>>>> index dee542fff68e..f1cdf92e7399 100644
>>>> --- a/drivers/md/bcache/bcache.h
>>>> +++ b/drivers/md/bcache/bcache.h
>>>> @@ -265,9 +265,6 @@ struct bcache_device {
>>>>         atomic_t                *stripe_sectors_dirty;
>>>>         unsigned long           *full_dirty_stripes;
>>>>
>>>> -       unsigned long           sectors_dirty_last;
>>>> -       long                    sectors_dirty_derivative;
>>>> -
>>>>         struct bio_set          *bio_split;
>>>>
>>>>         unsigned                data_csum:1;
>>>> @@ -361,12 +358,14 @@ struct cached_dev {
>>>>
>>>>         uint64_t                writeback_rate_target;
>>>>         int64_t                 writeback_rate_proportional;
>>>> -       int64_t                 writeback_rate_derivative;
>>>> +       int64_t                 writeback_rate_integral;
>>>> +       int64_t                 writeback_rate_integral_scaled;
>>>>         int64_t                 writeback_rate_change;
>>>>
>>>>         unsigned                writeback_rate_update_seconds;
>>>> -       unsigned                writeback_rate_d_term;
>>>> +       unsigned                writeback_rate_i_term_inverse;
>>>>         unsigned                writeback_rate_p_term_inverse;
>>>> +       unsigned                writeback_rate_minimum;
>>>>  };
>>>>
>>>>  enum alloc_reserve {
>>>> diff --git a/drivers/md/bcache/sysfs.c b/drivers/md/bcache/sysfs.c
>>>> index f90f13616980..66a716d5f111 100644
>>>> --- a/drivers/md/bcache/sysfs.c
>>>> +++ b/drivers/md/bcache/sysfs.c
>>>> @@ -81,8 +81,9 @@ rw_attribute(writeback_delay);
>>>>  rw_attribute(writeback_rate);
>>>>
>>>>  rw_attribute(writeback_rate_update_seconds);
>>>> -rw_attribute(writeback_rate_d_term);
>>>> +rw_attribute(writeback_rate_i_term_inverse);
>>>>  rw_attribute(writeback_rate_p_term_inverse);
>>>> +rw_attribute(writeback_rate_minimum);
>>>>  read_attribute(writeback_rate_debug);
>>>>
>>>>  read_attribute(stripe_size);
>>>> @@ -130,15 +131,16 @@ SHOW(__bch_cached_dev)
>>>>         sysfs_hprint(writeback_rate,    dc->writeback_rate.rate << 9);
>>>>
>>>>         var_print(writeback_rate_update_seconds);
>>>> -       var_print(writeback_rate_d_term);
>>>> +       var_print(writeback_rate_i_term_inverse);
>>>>         var_print(writeback_rate_p_term_inverse);
>>>> +       var_print(writeback_rate_minimum);
>>>>
>>>>         if (attr == &sysfs_writeback_rate_debug) {
>>>>                 char rate[20];
>>>>                 char dirty[20];
>>>>                 char target[20];
>>>>                 char proportional[20];
>>>> -               char derivative[20];
>>>> +               char integral[20];
>>>>                 char change[20];
>>>>                 s64 next_io;
>>>>
>>>> @@ -146,7 +148,7 @@ SHOW(__bch_cached_dev)
>>>>                 bch_hprint(dirty,       bcache_dev_sectors_dirty(&dc->disk) << 9);
>>>>                 bch_hprint(target,      dc->writeback_rate_target << 9);
>>>>                 bch_hprint(proportional,dc->writeback_rate_proportional << 9);
>>>> -               bch_hprint(derivative,  dc->writeback_rate_derivative << 9);
>>>> +               bch_hprint(integral,    dc->writeback_rate_integral_scaled << 9);
>>>>                 bch_hprint(change,      dc->writeback_rate_change << 9);
>>>>
>>>>                 next_io = div64_s64(dc->writeback_rate.next - local_clock(),
>>>> @@ -157,11 +159,11 @@ SHOW(__bch_cached_dev)
>>>>                                "dirty:\t\t%s\n"
>>>>                                "target:\t\t%s\n"
>>>>                                "proportional:\t%s\n"
>>>> -                              "derivative:\t%s\n"
>>>> +                              "integral:\t%s\n"
>>>>                                "change:\t\t%s/sec\n"
>>>>                                "next io:\t%llims\n",
>>>>                                rate, dirty, target, proportional,
>>>> -                              derivative, change, next_io);
>>>> +                              integral, change, next_io);
>>>>         }
>>>>
>>>>         sysfs_hprint(dirty_data,
>>>> @@ -213,7 +215,7 @@ STORE(__cached_dev)
>>>>                             dc->writeback_rate.rate, 1, INT_MAX);
>>>>
>>>>         d_strtoul_nonzero(writeback_rate_update_seconds);
>>>> -       d_strtoul(writeback_rate_d_term);
>>>> +       d_strtoul(writeback_rate_i_term_inverse);
>>>>         d_strtoul_nonzero(writeback_rate_p_term_inverse);
>>>>
>>>>         d_strtoi_h(sequential_cutoff);
>>>> @@ -319,8 +321,9 @@ static struct attribute *bch_cached_dev_files[] = {
>>>>         &sysfs_writeback_percent,
>>>>         &sysfs_writeback_rate,
>>>>         &sysfs_writeback_rate_update_seconds,
>>>> -       &sysfs_writeback_rate_d_term,
>>>> +       &sysfs_writeback_rate_i_term_inverse,
>>>>         &sysfs_writeback_rate_p_term_inverse,
>>>> +       &sysfs_writeback_rate_minimum,
>>>>         &sysfs_writeback_rate_debug,
>>>>         &sysfs_dirty_data,
>>>>         &sysfs_stripe_size,
>>>> diff --git a/drivers/md/bcache/writeback.c b/drivers/md/bcache/writeback.c
>>>> index 42c66e76f05e..76e71e8ef356 100644
>>>> --- a/drivers/md/bcache/writeback.c
>>>> +++ b/drivers/md/bcache/writeback.c
>>>> @@ -24,48 +24,55 @@ static void __update_writeback_rate(struct cached_dev *dc)
>>>>         uint64_t cache_sectors = c->nbuckets * c->sb.bucket_size;
>>>>         uint64_t cache_dirty_target =
>>>>                 div_u64(cache_sectors * dc->writeback_percent, 100);
>>>> -
>>>>         int64_t target = div64_u64(cache_dirty_target * bdev_sectors(dc->bdev),
>>>>                                    c->cached_dev_sectors);
>>>>
>>>> -       /* PD controller */
>>>> -
>>>> +       /* PI controller:
>>>> +        * Figures out the amount that should be written per second.
>>>> +        *
>>>> +        * First, the error (number of sectors that are dirty beyond our
>>>> +        * target) is calculated.  The error is accumulated (numerically
>>>> +        * integrated).
>>>> +        *
>>>> +        * Then, the proportional value and integral value are scaled
>>>> +        * based on configured values.  These are stored as inverses to
>>>> +        * avoid fixed point math and to make configuration easy-- e.g.
>>>> +        * the default value of 100 for writeback_rate_p_term_inverse
>>>> +        * attempts to write at a rate that would retire all the dirty
>>>> +        * blocks in 100 seconds.
>>>> +        */
>>>>         int64_t dirty = bcache_dev_sectors_dirty(&dc->disk);
>>>> -       int64_t derivative = dirty - dc->disk.sectors_dirty_last;
>>>> -       int64_t proportional = dirty - target;
>>>> -       int64_t change;
>>>> -
>>>> -       dc->disk.sectors_dirty_last = dirty;
>>>> -
>>>> -       /* Scale to sectors per second */
>>>> -
>>>> -       proportional *= dc->writeback_rate_update_seconds;
>>>> -       proportional = div_s64(proportional, dc->writeback_rate_p_term_inverse);
>>>> -
>>>> -       derivative = div_s64(derivative, dc->writeback_rate_update_seconds);
>>>> -
>>>> -       derivative = ewma_add(dc->disk.sectors_dirty_derivative, derivative,
>>>> -                             (dc->writeback_rate_d_term /
>>>> -                              dc->writeback_rate_update_seconds) ?: 1, 0);
>>>> -
>>>> -       derivative *= dc->writeback_rate_d_term;
>>>> -       derivative = div_s64(derivative, dc->writeback_rate_p_term_inverse);
>>>> -
>>>> -       change = proportional + derivative;
>>>> +       int64_t error = dirty - target;
>>>> +       int64_t proportional_scaled =
>>>> +               div_s64(error, dc->writeback_rate_p_term_inverse);
>>>> +       int64_t integral_scaled, new_rate;
>>>> +
>>>> +       if ((error < 0 && dc->writeback_rate_integral > 0) ||
>>>> +           (error > 0 && time_before64(local_clock(),
>>>> +                        dc->writeback_rate.next + NSEC_PER_MSEC))) {
>>>> +               /* Only decrease the integral term if it's more than
>>>> +                * zero.  Only increase the integral term if the device
>>>> +                * is keeping up.  (Don't wind up the integral
>>>> +                * ineffectively in either case).
>>>> +                *
>>>> +                * It's necessary to scale this by
>>>> +                * writeback_rate_update_seconds to keep the integral
>>>> +                * term dimensioned properly.
>>>> +                */
>>>> +               dc->writeback_rate_integral += error *
>>>> +                       dc->writeback_rate_update_seconds;
>>>> +       }
>>>>
>>>> -       /* Don't increase writeback rate if the device isn't keeping up */
>>>> -       if (change > 0 &&
>>>> -           time_after64(local_clock(),
>>>> -                        dc->writeback_rate.next + NSEC_PER_MSEC))
>>>> -               change = 0;
>>>> +       integral_scaled = div_s64(dc->writeback_rate_integral,
>>>> +                       dc->writeback_rate_i_term_inverse);
>>>>
>>>> -       dc->writeback_rate.rate =
>>>> -               clamp_t(int64_t, (int64_t) dc->writeback_rate.rate + change,
>>>> -                       1, NSEC_PER_MSEC);
>>>> +       new_rate = clamp_t(int64_t, (proportional_scaled + integral_scaled),
>>>> +                       dc->writeback_rate_minimum, NSEC_PER_MSEC);
>>>>
>>>> -       dc->writeback_rate_proportional = proportional;
>>>> -       dc->writeback_rate_derivative = derivative;
>>>> -       dc->writeback_rate_change = change;
>>>> +       dc->writeback_rate_proportional = proportional_scaled;
>>>> +       dc->writeback_rate_integral_scaled = integral_scaled;
>>>> +       dc->writeback_rate_change = new_rate - dc->writeback_rate.rate;
>>>> +       dc->writeback_rate.rate = new_rate;
>>>>         dc->writeback_rate_target = target;
>>>>  }
>>>>
>>>> @@ -491,8 +498,6 @@ void bch_sectors_dirty_init(struct cached_dev *dc)
>>>>
>>>>         bch_btree_map_keys(&op.op, dc->disk.c, &KEY(op.inode, 0, 0),
>>>>                            sectors_dirty_init_fn, 0);
>>>> -
>>>> -       dc->disk.sectors_dirty_last = bcache_dev_sectors_dirty(&dc->disk);
>>>>  }
>>>>
>>>>  void bch_cached_dev_writeback_init(struct cached_dev *dc)
>>>> @@ -506,10 +511,11 @@ void bch_cached_dev_writeback_init(struct cached_dev *dc)
>>>>         dc->writeback_percent           = 10;
>>>>         dc->writeback_delay             = 30;
>>>>         dc->writeback_rate.rate         = 1024;
>>>> +       dc->writeback_rate_minimum      = 5;
>>>>
>>>>         dc->writeback_rate_update_seconds = 5;
>>>> -       dc->writeback_rate_d_term       = 30;
>>>> -       dc->writeback_rate_p_term_inverse = 6000;
>>>> +       dc->writeback_rate_p_term_inverse = 40;
>>>> +       dc->writeback_rate_i_term_inverse = 10000;
>>>>
>>>>         INIT_DELAYED_WORK(&dc->writeback_rate_update, update_writeback_rate);
>>>>  }
>>>> --
>>>> 2.11.0
>>>>
>>> --
>>> To unsubscribe from this list: send the line "unsubscribe linux-bcache" in
>>> the body of a message to majordomo@vger.kernel.org
>>> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>>>
>> --
>> To unsubscribe from this list: send the line "unsubscribe linux-bcache" in
>> the body of a message to majordomo@vger.kernel.org
>> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> --
> To unsubscribe from this list: send the line "unsubscribe linux-bcache" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 

Re: [PATCH] bcache: implement PI controller for writeback rate

[Michael Lyle]

Coly--

That sounds great-- thanks for your help and advice. I'm about to send
an updated patch, adapted for the other 4.14 patches and with the
fixed comment.

I've run a few fio write-heavy scenarios with SATA and NVMe SSD in
front of a very slow USB disk--- the control system seems fairly
effective and gentle, e.g. http://i.imgur.com/RmWqnxg.png

Mike

On Thu, Sep 7, 2017 at 10:19 AM, Coly Li <i@coly.li> wrote:
> On 2017/9/7 下午11:29, Michael Lyle wrote:
>> Coly--
>>
>> Sure.  I have some plots at http://jar.lyle.org/~mlyle/ctr/ -- they
>> show the response of the controller to a step (increase from 0 to 1000
>> sectors/second of IO), and to an impulse (a single unexpected 100,000
>> sectors of dirty data) showing up.
>>
>> If anything, this controller is quicker to "turn off writes" and
>> remove workload from the backing disks than the previous one (though
>> how much it flushes when "idle" is configurable, now).  I would often
>> see the old controller continue writing back data long after the
>> workload was removed, or oscillate between writing large amounts and
>> doing very little.
>>
>> It's important to note that the old controller claims to be a PD
>> controller, but it is actually a PI controller-- the output from the
>> PD controller was accumulated, which has the effect of numerically
>> integrating everything.  It is a very strange PI controller, too-- not
>> formulated in any of the "normal" ways that control systems are built.
>>
>> Looking at the plots, there's a few different things to consider/look
>> at.  The first is how quickly the controller arrests a positive trend
>> after a step.  With default tuning, this is about 75 seconds.  Next,
>> is how well the value converges to the set point-- this is relatively
>> quick in both the step and impulse analyses.  Finally, the amount of
>> negative-going overshoot-- how much it writes "past" the setpoint is
>> important.  For an impulse, the current tuning overshoots about 10%--
>> if the system is at the target, and you dirty 100MB of the cache, it
>> will write back about 110MB.
>>
>> The existing system writes **much further** past the setpoint because
>> it is only able to start really reducing the write rate when the
>> target amount of dirty data is reached.
>>
>
> Hi Mike,
>
> Thank you for the informative reply. I add this patch to my for-test
> patch pool. My submit for 4.14 is done, I hope we can try best to make
> it in 4.15.
>
> Coly Li
>
>>
>> On Wed, Sep 6, 2017 at 10:27 PM, Coly Li <i@coly.li> wrote:
>>> On 2017/9/7 上午9:54, Michael Lyle wrote:
>>>> Hey everyone---
>>>>
>>>> I'd appreciate any feedback you all can lend on this changeset.  I
>>>> know it's a bit of an awkward time with the opening of the merge
>>>> window to have a new functional change show up.  I also would
>>>> appreciate any comments on process / how to go about submitting work,
>>>> as I have not been active in the Linux kernel community in quite some
>>>> time.
>>>>
>>>> This change makes a pretty substantial difference in the smoothness of
>>>> IO rates on my cached VM environment.  I see a couple of problems with
>>>> further review: I have an incorrect comment about the default p term
>>>> value, and there is a small bit of conflict with the patches that have
>>>> just gone out.  I can fix both of these quickly in a subsequent
>>>> revision.
>>>>
>>>> It's also helpful for intermittent workloads to be able to write at a
>>>> somewhat higher rate out to disk.  Spending a few percent of disk
>>>> bandwidth on flushing dirty data-- to leave room to deal with new
>>>> bursts of workload-- is very helpful.
>>>
>>> Hi Michael,
>>>
>>> One thing I care about is I/O latency of regular read/write requests.
>>> For current PD controller, I observe the writeback rate can decrease
>>> very fast to 1 sector/second to give almost all bandwidth to frond end
>>> I/O requests. This behavior is good for data base users.
>>>
>>> For this PI controller, I need to do more testing, and observe how it
>>> works and behaves with different work loads. Before I am confident with
>>> it for most of workloads I know, I am not able to response you very
>>> fast. It will take time.
>>>
>>> If you may provide more performance data (e.g. requests latency
>>> distribution) comparing to current PD controller, that will be very
>>> helpful for people to response this patch. For now, I need to understand
>>> and test this patch.
>>>
>>> Thanks.
>>>
>>> Coly Li
>>>
>>>>
>>>>
>>>> On Wed, Sep 6, 2017 at 12:56 AM, Michael Lyle <mlyle@lyle.org> wrote:
>>>>> bcache uses a control system to attempt to keep the amount of dirty data
>>>>> in cache at a user-configured level, while not responding excessively to
>>>>> transients and variations in write rate.  Previously, the system was a
>>>>> PD controller; but the output from it was integrated, turning the
>>>>> Proportional term into an Integral term, and turning the Derivative term
>>>>> into a crude Proportional term.  Performance of the controller has been
>>>>> uneven in production, and it has tended to respond slowly, oscillate,
>>>>> and overshoot.
>>>>>
>>>>> This patch set replaces the current control system with an explicit PI
>>>>> controller and tuning that should be correct for most hardware.  By
>>>>> default, it attempts to write at a rate that would retire 1/40th of the
>>>>> current excess blocks per second.  An integral term in turn works to
>>>>> remove steady state errors.
>>>>>
>>>>> IMO, this yields benefits in simplicity (removing weighted average
>>>>> filtering, etc) and system performance.
>>>>>
>>>>> Another small change is a tunable parameter is introduced to allow the
>>>>> user to specify a minimum rate at which dirty blocks are retired.
>>>>> Ideally one would set this writeback_rate_minimum to a small percentage
>>>>> of disk bandwidth, allowing the dirty data to be slowly cleaned out when
>>>>> the system is inactive.  The old behavior would try and retire 1
>>>>> sector/second, and the new default is 5 sectors/second.
>>>>>
>>>>> Signed-off-by: Michael Lyle <mlyle@lyle.org>
>>>>> ---
>>>>>  drivers/md/bcache/bcache.h    |  9 +++--
>>>>>  drivers/md/bcache/sysfs.c     | 19 +++++-----
>>>>>  drivers/md/bcache/writeback.c | 84 +++++++++++++++++++++++--------------------
>>>>>  3 files changed, 60 insertions(+), 52 deletions(-)
>>>>>
>>>>> diff --git a/drivers/md/bcache/bcache.h b/drivers/md/bcache/bcache.h
>>>>> index dee542fff68e..f1cdf92e7399 100644
>>>>> --- a/drivers/md/bcache/bcache.h
>>>>> +++ b/drivers/md/bcache/bcache.h
>>>>> @@ -265,9 +265,6 @@ struct bcache_device {
>>>>>         atomic_t                *stripe_sectors_dirty;
>>>>>         unsigned long           *full_dirty_stripes;
>>>>>
>>>>> -       unsigned long           sectors_dirty_last;
>>>>> -       long                    sectors_dirty_derivative;
>>>>> -
>>>>>         struct bio_set          *bio_split;
>>>>>
>>>>>         unsigned                data_csum:1;
>>>>> @@ -361,12 +358,14 @@ struct cached_dev {
>>>>>
>>>>>         uint64_t                writeback_rate_target;
>>>>>         int64_t                 writeback_rate_proportional;
>>>>> -       int64_t                 writeback_rate_derivative;
>>>>> +       int64_t                 writeback_rate_integral;
>>>>> +       int64_t                 writeback_rate_integral_scaled;
>>>>>         int64_t                 writeback_rate_change;
>>>>>
>>>>>         unsigned                writeback_rate_update_seconds;
>>>>> -       unsigned                writeback_rate_d_term;
>>>>> +       unsigned                writeback_rate_i_term_inverse;
>>>>>         unsigned                writeback_rate_p_term_inverse;
>>>>> +       unsigned                writeback_rate_minimum;
>>>>>  };
>>>>>
>>>>>  enum alloc_reserve {
>>>>> diff --git a/drivers/md/bcache/sysfs.c b/drivers/md/bcache/sysfs.c
>>>>> index f90f13616980..66a716d5f111 100644
>>>>> --- a/drivers/md/bcache/sysfs.c
>>>>> +++ b/drivers/md/bcache/sysfs.c
>>>>> @@ -81,8 +81,9 @@ rw_attribute(writeback_delay);
>>>>>  rw_attribute(writeback_rate);
>>>>>
>>>>>  rw_attribute(writeback_rate_update_seconds);
>>>>> -rw_attribute(writeback_rate_d_term);
>>>>> +rw_attribute(writeback_rate_i_term_inverse);
>>>>>  rw_attribute(writeback_rate_p_term_inverse);
>>>>> +rw_attribute(writeback_rate_minimum);
>>>>>  read_attribute(writeback_rate_debug);
>>>>>
>>>>>  read_attribute(stripe_size);
>>>>> @@ -130,15 +131,16 @@ SHOW(__bch_cached_dev)
>>>>>         sysfs_hprint(writeback_rate,    dc->writeback_rate.rate << 9);
>>>>>
>>>>>         var_print(writeback_rate_update_seconds);
>>>>> -       var_print(writeback_rate_d_term);
>>>>> +       var_print(writeback_rate_i_term_inverse);
>>>>>         var_print(writeback_rate_p_term_inverse);
>>>>> +       var_print(writeback_rate_minimum);
>>>>>
>>>>>         if (attr == &sysfs_writeback_rate_debug) {
>>>>>                 char rate[20];
>>>>>                 char dirty[20];
>>>>>                 char target[20];
>>>>>                 char proportional[20];
>>>>> -               char derivative[20];
>>>>> +               char integral[20];
>>>>>                 char change[20];
>>>>>                 s64 next_io;
>>>>>
>>>>> @@ -146,7 +148,7 @@ SHOW(__bch_cached_dev)
>>>>>                 bch_hprint(dirty,       bcache_dev_sectors_dirty(&dc->disk) << 9);
>>>>>                 bch_hprint(target,      dc->writeback_rate_target << 9);
>>>>>                 bch_hprint(proportional,dc->writeback_rate_proportional << 9);
>>>>> -               bch_hprint(derivative,  dc->writeback_rate_derivative << 9);
>>>>> +               bch_hprint(integral,    dc->writeback_rate_integral_scaled << 9);
>>>>>                 bch_hprint(change,      dc->writeback_rate_change << 9);
>>>>>
>>>>>                 next_io = div64_s64(dc->writeback_rate.next - local_clock(),
>>>>> @@ -157,11 +159,11 @@ SHOW(__bch_cached_dev)
>>>>>                                "dirty:\t\t%s\n"
>>>>>                                "target:\t\t%s\n"
>>>>>                                "proportional:\t%s\n"
>>>>> -                              "derivative:\t%s\n"
>>>>> +                              "integral:\t%s\n"
>>>>>                                "change:\t\t%s/sec\n"
>>>>>                                "next io:\t%llims\n",
>>>>>                                rate, dirty, target, proportional,
>>>>> -                              derivative, change, next_io);
>>>>> +                              integral, change, next_io);
>>>>>         }
>>>>>
>>>>>         sysfs_hprint(dirty_data,
>>>>> @@ -213,7 +215,7 @@ STORE(__cached_dev)
>>>>>                             dc->writeback_rate.rate, 1, INT_MAX);
>>>>>
>>>>>         d_strtoul_nonzero(writeback_rate_update_seconds);
>>>>> -       d_strtoul(writeback_rate_d_term);
>>>>> +       d_strtoul(writeback_rate_i_term_inverse);
>>>>>         d_strtoul_nonzero(writeback_rate_p_term_inverse);
>>>>>
>>>>>         d_strtoi_h(sequential_cutoff);
>>>>> @@ -319,8 +321,9 @@ static struct attribute *bch_cached_dev_files[] = {
>>>>>         &sysfs_writeback_percent,
>>>>>         &sysfs_writeback_rate,
>>>>>         &sysfs_writeback_rate_update_seconds,
>>>>> -       &sysfs_writeback_rate_d_term,
>>>>> +       &sysfs_writeback_rate_i_term_inverse,
>>>>>         &sysfs_writeback_rate_p_term_inverse,
>>>>> +       &sysfs_writeback_rate_minimum,
>>>>>         &sysfs_writeback_rate_debug,
>>>>>         &sysfs_dirty_data,
>>>>>         &sysfs_stripe_size,
>>>>> diff --git a/drivers/md/bcache/writeback.c b/drivers/md/bcache/writeback.c
>>>>> index 42c66e76f05e..76e71e8ef356 100644
>>>>> --- a/drivers/md/bcache/writeback.c
>>>>> +++ b/drivers/md/bcache/writeback.c
>>>>> @@ -24,48 +24,55 @@ static void __update_writeback_rate(struct cached_dev *dc)
>>>>>         uint64_t cache_sectors = c->nbuckets * c->sb.bucket_size;
>>>>>         uint64_t cache_dirty_target =
>>>>>                 div_u64(cache_sectors * dc->writeback_percent, 100);
>>>>> -
>>>>>         int64_t target = div64_u64(cache_dirty_target * bdev_sectors(dc->bdev),
>>>>>                                    c->cached_dev_sectors);
>>>>>
>>>>> -       /* PD controller */
>>>>> -
>>>>> +       /* PI controller:
>>>>> +        * Figures out the amount that should be written per second.
>>>>> +        *
>>>>> +        * First, the error (number of sectors that are dirty beyond our
>>>>> +        * target) is calculated.  The error is accumulated (numerically
>>>>> +        * integrated).
>>>>> +        *
>>>>> +        * Then, the proportional value and integral value are scaled
>>>>> +        * based on configured values.  These are stored as inverses to
>>>>> +        * avoid fixed point math and to make configuration easy-- e.g.
>>>>> +        * the default value of 100 for writeback_rate_p_term_inverse
>>>>> +        * attempts to write at a rate that would retire all the dirty
>>>>> +        * blocks in 100 seconds.
>>>>> +        */
>>>>>         int64_t dirty = bcache_dev_sectors_dirty(&dc->disk);
>>>>> -       int64_t derivative = dirty - dc->disk.sectors_dirty_last;
>>>>> -       int64_t proportional = dirty - target;
>>>>> -       int64_t change;
>>>>> -
>>>>> -       dc->disk.sectors_dirty_last = dirty;
>>>>> -
>>>>> -       /* Scale to sectors per second */
>>>>> -
>>>>> -       proportional *= dc->writeback_rate_update_seconds;
>>>>> -       proportional = div_s64(proportional, dc->writeback_rate_p_term_inverse);
>>>>> -
>>>>> -       derivative = div_s64(derivative, dc->writeback_rate_update_seconds);
>>>>> -
>>>>> -       derivative = ewma_add(dc->disk.sectors_dirty_derivative, derivative,
>>>>> -                             (dc->writeback_rate_d_term /
>>>>> -                              dc->writeback_rate_update_seconds) ?: 1, 0);
>>>>> -
>>>>> -       derivative *= dc->writeback_rate_d_term;
>>>>> -       derivative = div_s64(derivative, dc->writeback_rate_p_term_inverse);
>>>>> -
>>>>> -       change = proportional + derivative;
>>>>> +       int64_t error = dirty - target;
>>>>> +       int64_t proportional_scaled =
>>>>> +               div_s64(error, dc->writeback_rate_p_term_inverse);
>>>>> +       int64_t integral_scaled, new_rate;
>>>>> +
>>>>> +       if ((error < 0 && dc->writeback_rate_integral > 0) ||
>>>>> +           (error > 0 && time_before64(local_clock(),
>>>>> +                        dc->writeback_rate.next + NSEC_PER_MSEC))) {
>>>>> +               /* Only decrease the integral term if it's more than
>>>>> +                * zero.  Only increase the integral term if the device
>>>>> +                * is keeping up.  (Don't wind up the integral
>>>>> +                * ineffectively in either case).
>>>>> +                *
>>>>> +                * It's necessary to scale this by
>>>>> +                * writeback_rate_update_seconds to keep the integral
>>>>> +                * term dimensioned properly.
>>>>> +                */
>>>>> +               dc->writeback_rate_integral += error *
>>>>> +                       dc->writeback_rate_update_seconds;
>>>>> +       }
>>>>>
>>>>> -       /* Don't increase writeback rate if the device isn't keeping up */
>>>>> -       if (change > 0 &&
>>>>> -           time_after64(local_clock(),
>>>>> -                        dc->writeback_rate.next + NSEC_PER_MSEC))
>>>>> -               change = 0;
>>>>> +       integral_scaled = div_s64(dc->writeback_rate_integral,
>>>>> +                       dc->writeback_rate_i_term_inverse);
>>>>>
>>>>> -       dc->writeback_rate.rate =
>>>>> -               clamp_t(int64_t, (int64_t) dc->writeback_rate.rate + change,
>>>>> -                       1, NSEC_PER_MSEC);
>>>>> +       new_rate = clamp_t(int64_t, (proportional_scaled + integral_scaled),
>>>>> +                       dc->writeback_rate_minimum, NSEC_PER_MSEC);
>>>>>
>>>>> -       dc->writeback_rate_proportional = proportional;
>>>>> -       dc->writeback_rate_derivative = derivative;
>>>>> -       dc->writeback_rate_change = change;
>>>>> +       dc->writeback_rate_proportional = proportional_scaled;
>>>>> +       dc->writeback_rate_integral_scaled = integral_scaled;
>>>>> +       dc->writeback_rate_change = new_rate - dc->writeback_rate.rate;
>>>>> +       dc->writeback_rate.rate = new_rate;
>>>>>         dc->writeback_rate_target = target;
>>>>>  }
>>>>>
>>>>> @@ -491,8 +498,6 @@ void bch_sectors_dirty_init(struct cached_dev *dc)
>>>>>
>>>>>         bch_btree_map_keys(&op.op, dc->disk.c, &KEY(op.inode, 0, 0),
>>>>>                            sectors_dirty_init_fn, 0);
>>>>> -
>>>>> -       dc->disk.sectors_dirty_last = bcache_dev_sectors_dirty(&dc->disk);
>>>>>  }
>>>>>
>>>>>  void bch_cached_dev_writeback_init(struct cached_dev *dc)
>>>>> @@ -506,10 +511,11 @@ void bch_cached_dev_writeback_init(struct cached_dev *dc)
>>>>>         dc->writeback_percent           = 10;
>>>>>         dc->writeback_delay             = 30;
>>>>>         dc->writeback_rate.rate         = 1024;
>>>>> +       dc->writeback_rate_minimum      = 5;
>>>>>
>>>>>         dc->writeback_rate_update_seconds = 5;
>>>>> -       dc->writeback_rate_d_term       = 30;
>>>>> -       dc->writeback_rate_p_term_inverse = 6000;
>>>>> +       dc->writeback_rate_p_term_inverse = 40;
>>>>> +       dc->writeback_rate_i_term_inverse = 10000;
>>>>>
>>>>>         INIT_DELAYED_WORK(&dc->writeback_rate_update, update_writeback_rate);
>>>>>  }
>>>>> --
>>>>> 2.11.0
>>>>>
>>>> --
>>>> To unsubscribe from this list: send the line "unsubscribe linux-bcache" in
>>>> the body of a message to majordomo@vger.kernel.org
>>>> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>>>>
>>> --
>>> To unsubscribe from this list: send the line "unsubscribe linux-bcache" in
>>> the body of a message to majordomo@vger.kernel.org
>>> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>> --
>> To unsubscribe from this list: send the line "unsubscribe linux-bcache" in
>> the body of a message to majordomo@vger.kernel.org
>> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>>
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-bcache" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] bcache: implement PI controller for writeback rate

[Coly Li]

On 2017/9/8 上午11:01, Michael Lyle wrote:
> Coly--
> 
> That sounds great-- thanks for your help and advice. I'm about to send
> an updated patch, adapted for the other 4.14 patches and with the
> fixed comment.
> 
> I've run a few fio write-heavy scenarios with SATA and NVMe SSD in
> front of a very slow USB disk--- the control system seems fairly
> effective and gentle, e.g. http://i.imgur.com/RmWqnxg.png

Hi Mike,

This is not what I meant. A I/O latency distribution I want to look is
something like this,

- send out 10K read requests, measure response latency for each request
- gathering all the latency numbers, counting them with different
latency range, and get a statistic result.
- the result is, for each different latency range, how many read
requests hit the range. This is what I called latency distribution.

What I care about mostly is the latency distribution of regular frond
end I/O while background writeback I/O existing. This is a typical
information that database work load matters.

Thanks.

Coly Li


> On Thu, Sep 7, 2017 at 10:19 AM, Coly Li <i@coly.li> wrote:
>> On 2017/9/7 下午11:29, Michael Lyle wrote:
>>> Coly--
>>>
>>> Sure.  I have some plots at http://jar.lyle.org/~mlyle/ctr/ -- they
>>> show the response of the controller to a step (increase from 0 to 1000
>>> sectors/second of IO), and to an impulse (a single unexpected 100,000
>>> sectors of dirty data) showing up.
>>>
>>> If anything, this controller is quicker to "turn off writes" and
>>> remove workload from the backing disks than the previous one (though
>>> how much it flushes when "idle" is configurable, now).  I would often
>>> see the old controller continue writing back data long after the
>>> workload was removed, or oscillate between writing large amounts and
>>> doing very little.
>>>
>>> It's important to note that the old controller claims to be a PD
>>> controller, but it is actually a PI controller-- the output from the
>>> PD controller was accumulated, which has the effect of numerically
>>> integrating everything.  It is a very strange PI controller, too-- not
>>> formulated in any of the "normal" ways that control systems are built.
>>>
>>> Looking at the plots, there's a few different things to consider/look
>>> at.  The first is how quickly the controller arrests a positive trend
>>> after a step.  With default tuning, this is about 75 seconds.  Next,
>>> is how well the value converges to the set point-- this is relatively
>>> quick in both the step and impulse analyses.  Finally, the amount of
>>> negative-going overshoot-- how much it writes "past" the setpoint is
>>> important.  For an impulse, the current tuning overshoots about 10%--
>>> if the system is at the target, and you dirty 100MB of the cache, it
>>> will write back about 110MB.
>>>
>>> The existing system writes **much further** past the setpoint because
>>> it is only able to start really reducing the write rate when the
>>> target amount of dirty data is reached.
>>>
>>
>> Hi Mike,
>>
>> Thank you for the informative reply. I add this patch to my for-test
>> patch pool. My submit for 4.14 is done, I hope we can try best to make
>> it in 4.15.
>>
>> Coly Li
>>
>>>
>>> On Wed, Sep 6, 2017 at 10:27 PM, Coly Li <i@coly.li> wrote:
>>>> On 2017/9/7 上午9:54, Michael Lyle wrote:
>>>>> Hey everyone---
>>>>>
>>>>> I'd appreciate any feedback you all can lend on this changeset.  I
>>>>> know it's a bit of an awkward time with the opening of the merge
>>>>> window to have a new functional change show up.  I also would
>>>>> appreciate any comments on process / how to go about submitting work,
>>>>> as I have not been active in the Linux kernel community in quite some
>>>>> time.
>>>>>
>>>>> This change makes a pretty substantial difference in the smoothness of
>>>>> IO rates on my cached VM environment.  I see a couple of problems with
>>>>> further review: I have an incorrect comment about the default p term
>>>>> value, and there is a small bit of conflict with the patches that have
>>>>> just gone out.  I can fix both of these quickly in a subsequent
>>>>> revision.
>>>>>
>>>>> It's also helpful for intermittent workloads to be able to write at a
>>>>> somewhat higher rate out to disk.  Spending a few percent of disk
>>>>> bandwidth on flushing dirty data-- to leave room to deal with new
>>>>> bursts of workload-- is very helpful.
>>>>
>>>> Hi Michael,
>>>>
>>>> One thing I care about is I/O latency of regular read/write requests.
>>>> For current PD controller, I observe the writeback rate can decrease
>>>> very fast to 1 sector/second to give almost all bandwidth to frond end
>>>> I/O requests. This behavior is good for data base users.
>>>>
>>>> For this PI controller, I need to do more testing, and observe how it
>>>> works and behaves with different work loads. Before I am confident with
>>>> it for most of workloads I know, I am not able to response you very
>>>> fast. It will take time.
>>>>
>>>> If you may provide more performance data (e.g. requests latency
>>>> distribution) comparing to current PD controller, that will be very
>>>> helpful for people to response this patch. For now, I need to understand
>>>> and test this patch.
>>>>
>>>> Thanks.
>>>>
>>>> Coly Li
>>>>
>>>>>
>>>>>
>>>>> On Wed, Sep 6, 2017 at 12:56 AM, Michael Lyle <mlyle@lyle.org> wrote:
>>>>>> bcache uses a control system to attempt to keep the amount of dirty data
>>>>>> in cache at a user-configured level, while not responding excessively to
>>>>>> transients and variations in write rate.  Previously, the system was a
>>>>>> PD controller; but the output from it was integrated, turning the
>>>>>> Proportional term into an Integral term, and turning the Derivative term
>>>>>> into a crude Proportional term.  Performance of the controller has been
>>>>>> uneven in production, and it has tended to respond slowly, oscillate,
>>>>>> and overshoot.
>>>>>>
>>>>>> This patch set replaces the current control system with an explicit PI
>>>>>> controller and tuning that should be correct for most hardware.  By
>>>>>> default, it attempts to write at a rate that would retire 1/40th of the
>>>>>> current excess blocks per second.  An integral term in turn works to
>>>>>> remove steady state errors.
>>>>>>
>>>>>> IMO, this yields benefits in simplicity (removing weighted average
>>>>>> filtering, etc) and system performance.
>>>>>>
>>>>>> Another small change is a tunable parameter is introduced to allow the
>>>>>> user to specify a minimum rate at which dirty blocks are retired.
>>>>>> Ideally one would set this writeback_rate_minimum to a small percentage
>>>>>> of disk bandwidth, allowing the dirty data to be slowly cleaned out when
>>>>>> the system is inactive.  The old behavior would try and retire 1
>>>>>> sector/second, and the new default is 5 sectors/second.
>>>>>>
>>>>>> Signed-off-by: Michael Lyle <mlyle@lyle.org>
>>>>>> ---
>>>>>>  drivers/md/bcache/bcache.h    |  9 +++--
>>>>>>  drivers/md/bcache/sysfs.c     | 19 +++++-----
>>>>>>  drivers/md/bcache/writeback.c | 84 +++++++++++++++++++++++--------------------
>>>>>>  3 files changed, 60 insertions(+), 52 deletions(-)
>>>>>>
>>>>>> diff --git a/drivers/md/bcache/bcache.h b/drivers/md/bcache/bcache.h
>>>>>> index dee542fff68e..f1cdf92e7399 100644
>>>>>> --- a/drivers/md/bcache/bcache.h
>>>>>> +++ b/drivers/md/bcache/bcache.h
>>>>>> @@ -265,9 +265,6 @@ struct bcache_device {
>>>>>>         atomic_t                *stripe_sectors_dirty;
>>>>>>         unsigned long           *full_dirty_stripes;
>>>>>>
>>>>>> -       unsigned long           sectors_dirty_last;
>>>>>> -       long                    sectors_dirty_derivative;
>>>>>> -
>>>>>>         struct bio_set          *bio_split;
>>>>>>
>>>>>>         unsigned                data_csum:1;
>>>>>> @@ -361,12 +358,14 @@ struct cached_dev {
>>>>>>
>>>>>>         uint64_t                writeback_rate_target;
>>>>>>         int64_t                 writeback_rate_proportional;
>>>>>> -       int64_t                 writeback_rate_derivative;
>>>>>> +       int64_t                 writeback_rate_integral;
>>>>>> +       int64_t                 writeback_rate_integral_scaled;
>>>>>>         int64_t                 writeback_rate_change;
>>>>>>
>>>>>>         unsigned                writeback_rate_update_seconds;
>>>>>> -       unsigned                writeback_rate_d_term;
>>>>>> +       unsigned                writeback_rate_i_term_inverse;
>>>>>>         unsigned                writeback_rate_p_term_inverse;
>>>>>> +       unsigned                writeback_rate_minimum;
>>>>>>  };
>>>>>>
>>>>>>  enum alloc_reserve {
>>>>>> diff --git a/drivers/md/bcache/sysfs.c b/drivers/md/bcache/sysfs.c
>>>>>> index f90f13616980..66a716d5f111 100644
>>>>>> --- a/drivers/md/bcache/sysfs.c
>>>>>> +++ b/drivers/md/bcache/sysfs.c
>>>>>> @@ -81,8 +81,9 @@ rw_attribute(writeback_delay);
>>>>>>  rw_attribute(writeback_rate);
>>>>>>
>>>>>>  rw_attribute(writeback_rate_update_seconds);
>>>>>> -rw_attribute(writeback_rate_d_term);
>>>>>> +rw_attribute(writeback_rate_i_term_inverse);
>>>>>>  rw_attribute(writeback_rate_p_term_inverse);
>>>>>> +rw_attribute(writeback_rate_minimum);
>>>>>>  read_attribute(writeback_rate_debug);
>>>>>>
>>>>>>  read_attribute(stripe_size);
>>>>>> @@ -130,15 +131,16 @@ SHOW(__bch_cached_dev)
>>>>>>         sysfs_hprint(writeback_rate,    dc->writeback_rate.rate << 9);
>>>>>>
>>>>>>         var_print(writeback_rate_update_seconds);
>>>>>> -       var_print(writeback_rate_d_term);
>>>>>> +       var_print(writeback_rate_i_term_inverse);
>>>>>>         var_print(writeback_rate_p_term_inverse);
>>>>>> +       var_print(writeback_rate_minimum);
>>>>>>
>>>>>>         if (attr == &sysfs_writeback_rate_debug) {
>>>>>>                 char rate[20];
>>>>>>                 char dirty[20];
>>>>>>                 char target[20];
>>>>>>                 char proportional[20];
>>>>>> -               char derivative[20];
>>>>>> +               char integral[20];
>>>>>>                 char change[20];
>>>>>>                 s64 next_io;
>>>>>>
>>>>>> @@ -146,7 +148,7 @@ SHOW(__bch_cached_dev)
>>>>>>                 bch_hprint(dirty,       bcache_dev_sectors_dirty(&dc->disk) << 9);
>>>>>>                 bch_hprint(target,      dc->writeback_rate_target << 9);
>>>>>>                 bch_hprint(proportional,dc->writeback_rate_proportional << 9);
>>>>>> -               bch_hprint(derivative,  dc->writeback_rate_derivative << 9);
>>>>>> +               bch_hprint(integral,    dc->writeback_rate_integral_scaled << 9);
>>>>>>                 bch_hprint(change,      dc->writeback_rate_change << 9);
>>>>>>
>>>>>>                 next_io = div64_s64(dc->writeback_rate.next - local_clock(),
>>>>>> @@ -157,11 +159,11 @@ SHOW(__bch_cached_dev)
>>>>>>                                "dirty:\t\t%s\n"
>>>>>>                                "target:\t\t%s\n"
>>>>>>                                "proportional:\t%s\n"
>>>>>> -                              "derivative:\t%s\n"
>>>>>> +                              "integral:\t%s\n"
>>>>>>                                "change:\t\t%s/sec\n"
>>>>>>                                "next io:\t%llims\n",
>>>>>>                                rate, dirty, target, proportional,
>>>>>> -                              derivative, change, next_io);
>>>>>> +                              integral, change, next_io);
>>>>>>         }
>>>>>>
>>>>>>         sysfs_hprint(dirty_data,
>>>>>> @@ -213,7 +215,7 @@ STORE(__cached_dev)
>>>>>>                             dc->writeback_rate.rate, 1, INT_MAX);
>>>>>>
>>>>>>         d_strtoul_nonzero(writeback_rate_update_seconds);
>>>>>> -       d_strtoul(writeback_rate_d_term);
>>>>>> +       d_strtoul(writeback_rate_i_term_inverse);
>>>>>>         d_strtoul_nonzero(writeback_rate_p_term_inverse);
>>>>>>
>>>>>>         d_strtoi_h(sequential_cutoff);
>>>>>> @@ -319,8 +321,9 @@ static struct attribute *bch_cached_dev_files[] = {
>>>>>>         &sysfs_writeback_percent,
>>>>>>         &sysfs_writeback_rate,
>>>>>>         &sysfs_writeback_rate_update_seconds,
>>>>>> -       &sysfs_writeback_rate_d_term,
>>>>>> +       &sysfs_writeback_rate_i_term_inverse,
>>>>>>         &sysfs_writeback_rate_p_term_inverse,
>>>>>> +       &sysfs_writeback_rate_minimum,
>>>>>>         &sysfs_writeback_rate_debug,
>>>>>>         &sysfs_dirty_data,
>>>>>>         &sysfs_stripe_size,
>>>>>> diff --git a/drivers/md/bcache/writeback.c b/drivers/md/bcache/writeback.c
>>>>>> index 42c66e76f05e..76e71e8ef356 100644
>>>>>> --- a/drivers/md/bcache/writeback.c
>>>>>> +++ b/drivers/md/bcache/writeback.c
>>>>>> @@ -24,48 +24,55 @@ static void __update_writeback_rate(struct cached_dev *dc)
>>>>>>         uint64_t cache_sectors = c->nbuckets * c->sb.bucket_size;
>>>>>>         uint64_t cache_dirty_target =
>>>>>>                 div_u64(cache_sectors * dc->writeback_percent, 100);
>>>>>> -
>>>>>>         int64_t target = div64_u64(cache_dirty_target * bdev_sectors(dc->bdev),
>>>>>>                                    c->cached_dev_sectors);
>>>>>>
>>>>>> -       /* PD controller */
>>>>>> -
>>>>>> +       /* PI controller:
>>>>>> +        * Figures out the amount that should be written per second.
>>>>>> +        *
>>>>>> +        * First, the error (number of sectors that are dirty beyond our
>>>>>> +        * target) is calculated.  The error is accumulated (numerically
>>>>>> +        * integrated).
>>>>>> +        *
>>>>>> +        * Then, the proportional value and integral value are scaled
>>>>>> +        * based on configured values.  These are stored as inverses to
>>>>>> +        * avoid fixed point math and to make configuration easy-- e.g.
>>>>>> +        * the default value of 100 for writeback_rate_p_term_inverse
>>>>>> +        * attempts to write at a rate that would retire all the dirty
>>>>>> +        * blocks in 100 seconds.
>>>>>> +        */
>>>>>>         int64_t dirty = bcache_dev_sectors_dirty(&dc->disk);
>>>>>> -       int64_t derivative = dirty - dc->disk.sectors_dirty_last;
>>>>>> -       int64_t proportional = dirty - target;
>>>>>> -       int64_t change;
>>>>>> -
>>>>>> -       dc->disk.sectors_dirty_last = dirty;
>>>>>> -
>>>>>> -       /* Scale to sectors per second */
>>>>>> -
>>>>>> -       proportional *= dc->writeback_rate_update_seconds;
>>>>>> -       proportional = div_s64(proportional, dc->writeback_rate_p_term_inverse);
>>>>>> -
>>>>>> -       derivative = div_s64(derivative, dc->writeback_rate_update_seconds);
>>>>>> -
>>>>>> -       derivative = ewma_add(dc->disk.sectors_dirty_derivative, derivative,
>>>>>> -                             (dc->writeback_rate_d_term /
>>>>>> -                              dc->writeback_rate_update_seconds) ?: 1, 0);
>>>>>> -
>>>>>> -       derivative *= dc->writeback_rate_d_term;
>>>>>> -       derivative = div_s64(derivative, dc->writeback_rate_p_term_inverse);
>>>>>> -
>>>>>> -       change = proportional + derivative;
>>>>>> +       int64_t error = dirty - target;
>>>>>> +       int64_t proportional_scaled =
>>>>>> +               div_s64(error, dc->writeback_rate_p_term_inverse);
>>>>>> +       int64_t integral_scaled, new_rate;
>>>>>> +
>>>>>> +       if ((error < 0 && dc->writeback_rate_integral > 0) ||
>>>>>> +           (error > 0 && time_before64(local_clock(),
>>>>>> +                        dc->writeback_rate.next + NSEC_PER_MSEC))) {
>>>>>> +               /* Only decrease the integral term if it's more than
>>>>>> +                * zero.  Only increase the integral term if the device
>>>>>> +                * is keeping up.  (Don't wind up the integral
>>>>>> +                * ineffectively in either case).
>>>>>> +                *
>>>>>> +                * It's necessary to scale this by
>>>>>> +                * writeback_rate_update_seconds to keep the integral
>>>>>> +                * term dimensioned properly.
>>>>>> +                */
>>>>>> +               dc->writeback_rate_integral += error *
>>>>>> +                       dc->writeback_rate_update_seconds;
>>>>>> +       }
>>>>>>
>>>>>> -       /* Don't increase writeback rate if the device isn't keeping up */
>>>>>> -       if (change > 0 &&
>>>>>> -           time_after64(local_clock(),
>>>>>> -                        dc->writeback_rate.next + NSEC_PER_MSEC))
>>>>>> -               change = 0;
>>>>>> +       integral_scaled = div_s64(dc->writeback_rate_integral,
>>>>>> +                       dc->writeback_rate_i_term_inverse);
>>>>>>
>>>>>> -       dc->writeback_rate.rate =
>>>>>> -               clamp_t(int64_t, (int64_t) dc->writeback_rate.rate + change,
>>>>>> -                       1, NSEC_PER_MSEC);
>>>>>> +       new_rate = clamp_t(int64_t, (proportional_scaled + integral_scaled),
>>>>>> +                       dc->writeback_rate_minimum, NSEC_PER_MSEC);
>>>>>>
>>>>>> -       dc->writeback_rate_proportional = proportional;
>>>>>> -       dc->writeback_rate_derivative = derivative;
>>>>>> -       dc->writeback_rate_change = change;
>>>>>> +       dc->writeback_rate_proportional = proportional_scaled;
>>>>>> +       dc->writeback_rate_integral_scaled = integral_scaled;
>>>>>> +       dc->writeback_rate_change = new_rate - dc->writeback_rate.rate;
>>>>>> +       dc->writeback_rate.rate = new_rate;
>>>>>>         dc->writeback_rate_target = target;
>>>>>>  }
>>>>>>
>>>>>> @@ -491,8 +498,6 @@ void bch_sectors_dirty_init(struct cached_dev *dc)
>>>>>>
>>>>>>         bch_btree_map_keys(&op.op, dc->disk.c, &KEY(op.inode, 0, 0),
>>>>>>                            sectors_dirty_init_fn, 0);
>>>>>> -
>>>>>> -       dc->disk.sectors_dirty_last = bcache_dev_sectors_dirty(&dc->disk);
>>>>>>  }
>>>>>>
>>>>>>  void bch_cached_dev_writeback_init(struct cached_dev *dc)
>>>>>> @@ -506,10 +511,11 @@ void bch_cached_dev_writeback_init(struct cached_dev *dc)
>>>>>>         dc->writeback_percent           = 10;
>>>>>>         dc->writeback_delay             = 30;
>>>>>>         dc->writeback_rate.rate         = 1024;
>>>>>> +       dc->writeback_rate_minimum      = 5;
>>>>>>
>>>>>>         dc->writeback_rate_update_seconds = 5;
>>>>>> -       dc->writeback_rate_d_term       = 30;
>>>>>> -       dc->writeback_rate_p_term_inverse = 6000;
>>>>>> +       dc->writeback_rate_p_term_inverse = 40;
>>>>>> +       dc->writeback_rate_i_term_inverse = 10000;
>>>>>>
>>>>>>         INIT_DELAYED_WORK(&dc->writeback_rate_update, update_writeback_rate);
>>>>>>  }
>>>>>> --
>>>>>> 2.11.0
>>>>>>
>>>>> --
>>>>> To unsubscribe from this list: send the line "unsubscribe linux-bcache" in
>>>>> the body of a message to majordomo@vger.kernel.org
>>>>> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>>>>>
>>>> --
>>>> To unsubscribe from this list: send the line "unsubscribe linux-bcache" in
>>>> the body of a message to majordomo@vger.kernel.org
>>>> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>>> --
>>> To unsubscribe from this list: send the line "unsubscribe linux-bcache" in
>>> the body of a message to majordomo@vger.kernel.org
>>> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>>>
>>
>> --
>> To unsubscribe from this list: send the line "unsubscribe linux-bcache" in
>> the body of a message to majordomo@vger.kernel.org
>> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> --
> To unsubscribe from this list: send the line "unsubscribe linux-bcache" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 


-- 
Coly Li