IO-less dirty throttling v8

mm/page-writeback.c +15 -0

+static unsigned long bdi_position_ratio(struct backing_dev_info *bdi,
+                                       unsigned long thresh,
+                                       unsigned long dirty,
+                                       unsigned long bdi_thresh,
+                                       unsigned long bdi_dirty)
+{
+       unsigned long limit = hard_dirty_limit(thresh);
+       unsigned long origin;
+       unsigned long goal;
+       unsigned long long span;
+       unsigned long long pos_ratio;   /* for scaling up/down the rate limit */
+
+       if (unlikely(dirty >= limit))
+               return 0;
+

Quoted 19 lines · Wu Fengguang

(quoted diff) +19 -0

+static unsigned long bdi_position_ratio(struct backing_dev_info *bdi,
+                                       unsigned long thresh,
+                                       unsigned long dirty,
+                                       unsigned long bdi_thresh,
+                                       unsigned long bdi_dirty)
+{
+       unsigned long limit = hard_dirty_limit(thresh);
+       unsigned long origin;
+       unsigned long goal;
+       unsigned long long span;
+       unsigned long long pos_ratio;   /* for scaling up/down the rate limit */
+
+       if (unlikely(dirty >= limit))
+               return 0;
+
+       /*
+        * global setpoint
+        */
+       goal = thresh - thresh / DIRTY_SCOPE;

Review

Quoted 6 lines

(quoted diff) +6 -0

+       origin = 4 * thresh;
+
+       if (unlikely(origin < limit && dirty > (goal + origin) / 2)) {
+               origin = limit;                 /* auxiliary control line */
+               goal = (goal + origin) / 2;
+               pos_ratio >>= 1; 

use before init?

It's actually dead code because (origin < limit) should never happen. I feel so good being able to drop 5 more lines of code :)

Quoted 2 lines · Wu Fengguang

It's actually dead code because (origin < limit) should never happen. I feel so good being able to drop 5 more lines of code :)

OK, but that leaves me trying to figure out what origin is, and why its 4 * thresh.

I'm having a horrible time understanding this stuff.

origin is where the control line crosses the X axis (in both the global/bdi setpoint cases).

Quoted 2 lines · Wu Fengguang

origin is where the control line crosses the X axis (in both the global/bdi setpoint cases).

Ah, that's normally called zero, root or or x-intercept:

http://en.wikipedia.org/wiki/X-intercept

Quoted 4 lines · Wu Fengguang

(quoted diff) +0 -0

@@ -538,11 +538,6 @@ static unsigned long bdi_position_ratio(
        goal = thresh - thresh / DIRTY_SCOPE;
        origin = 4 * thresh;
 

Review static unsigned long bdi_position_ratio( · line 543

Quoted 8 lines

(quoted diff) +0 -5

-       if (unlikely(origin < limit && dirty > (goal + origin) / 2)) {
-               origin = limit;                 /* auxiliary control line */
-               goal = (goal + origin) / 2;
-               pos_ratio >>= 1;
-       }
        pos_ratio = origin - dirty;
        pos_ratio <<= BANDWIDTH_CALC_SHIFT;
        do_div(pos_ratio, origin - goal + 1); 

So basically, pos_ratio = (4t - d) / (25/8)t, which if I'm not mistaken comes out at 32/25 - 8d/25t. Which simply doesn't make sense at all.

This is the more meaningful view :)

origin - dirty
pos_ratio = --------------
origin - goal

which comes from the below [*] control line, so that when (dirty == goal), pos_ratio == 1.0:

+ *  When the number of dirty pages go higher/lower than the setpoint, the dirty
+ *  position ratio (and hence dirty rate limit) will be decreased/increased to
+ *  bring the dirty pages back to the setpoint.

Quoted 6 lines

origin - dirty
pos_ratio = --------------
origin - goal

which comes from the below [*] control line, so that when (dirty == goal), pos_ratio == 1.0:

OK, so basically you want a linear function for which:

f(goal) = 1 and has a root somewhere > goal.

(that one line is much more informative than all your graphs put together, one can start from there and derive your function)

That does indeed get you the above function, now what does it mean?

Quoted 14 lines · Peter Zijlstra

Quoted 6 lines

origin - dirty
pos_ratio = --------------
origin - goal

which comes from the below [*] control line, so that when (dirty == goal), pos_ratio == 1.0:

OK, so basically you want a linear function for which:

f(goal) = 1 and has a root somewhere > goal.

(that one line is much more informative than all your graphs put together, one can start from there and derive your function)

Quoted 1 line

That does indeed get you the above function, now what does it mean?

So going by:

write_bw
ref_bw = dirty_ratelimit * pos_ratio * --------
dirty_bw

pos_ratio seems to be the feedback on the deviation of the dirty pages around its setpoint. So we adjust the reference bw (or rather ratelimit) to take account of the shift in output vs input capacity as well as the shift in dirty pages around its setpoint.

From that we derive the condition that:

pos_ratio(setpoint) := 1

Now in order to create a linear function we need one more condition. We get one from the fact that once we hit the limit we should hard throttle our writers. We get that by setting the ratelimit to 0, because, after all, pause = nr_dirtied / ratelimit would yield inf. in that case. Thus:

pos_ratio(limit) := 0

Using these two conditions we can solve the equations and get your:

limit - dirty
pos_ratio(dirty) = ----------------
limit - setpoint

Now, for some reason you chose not to use limit, but something like min(limit, 4*thresh) something to do with the slope affecting the rate of adjustment. This wants a comment someplace.

Now all of the above would seem to suggest:

dirty_ratelimit := ref_bw

However for that you use:

if (pos_bw < dirty_ratelimit && ref_bw < dirty_ratelimit)

	dirty_ratelimit = max(ref_bw, pos_bw);

if (pos_bw > dirty_ratelimit && ref_bw > dirty_ratelimit)

	dirty_ratelimit = min(ref_bw, pos_bw);

You have:

pos_bw = dirty_ratelimit * pos_ratio

Which is ref_bw without the write_bw/dirty_bw factor, this confuses me.. why are you ignoring the shift in output vs input rate there?

Quoted 15 lines · Peter Zijlstra

Quoted 14 lines · Peter Zijlstra

Quoted 6 lines

origin - dirty
pos_ratio = --------------
origin - goal

which comes from the below [*] control line, so that when (dirty == goal), pos_ratio == 1.0:

OK, so basically you want a linear function for which:

f(goal) = 1 and has a root somewhere > goal.

(that one line is much more informative than all your graphs put together, one can start from there and derive your function)

Quoted 7 lines

Quoted 1 line

That does indeed get you the above function, now what does it mean?

So going by:

write_bw
ref_bw = dirty_ratelimit * pos_ratio * --------
dirty_bw

Actually, thinking about these formulas, why do we even bother with
computing all these factors like write_bw, dirty_bw, pos_ratio, ... Couldn't we just have a feedback loop (probably similar to the one computing pos_ratio) which will maintain single value - ratelimit? When we are getting close to dirty limit, we will scale ratelimit down, when we will be getting significantly below dirty limit, we will scale the ratelimit up. Because looking at the formulas it seems to me that the net effect is the same - pos_ratio basically overrules everything...

Quoted 24 lines · Jan Kara

Quoted 15 lines · Peter Zijlstra

Quoted 14 lines · Peter Zijlstra

Quoted 6 lines

origin - dirty
pos_ratio = --------------
origin - goal

which comes from the below [*] control line, so that when (dirty == goal), pos_ratio == 1.0:

OK, so basically you want a linear function for which:

f(goal) = 1 and has a root somewhere > goal.

(that one line is much more informative than all your graphs put together, one can start from there and derive your function)

Quoted 7 lines

Quoted 1 line

That does indeed get you the above function, now what does it mean?

So going by:

write_bw
ref_bw = dirty_ratelimit * pos_ratio * --------
dirty_bw

Quoted 8 lines

Actually, thinking about these formulas, why do we even bother with
computing all these factors like write_bw, dirty_bw, pos_ratio, ... Couldn't we just have a feedback loop (probably similar to the one computing pos_ratio) which will maintain single value - ratelimit? When we are getting close to dirty limit, we will scale ratelimit down, when we will be getting significantly below dirty limit, we will scale the ratelimit up. Because looking at the formulas it seems to me that the net effect is the same - pos_ratio basically overrules everything...

Good question. That is actually one of the early approaches I tried. It somehow worked, however the resulted ratelimit is not only slow responding, but also oscillating all the time.

This is due to the imperfections

1) pos_ratio at best only provides a "direction" for adjusting the ratelimit. There is only vague clues that if pos_ratio is small, the errors in ratelimit should be small.

2) Due to time-lag, the assumptions in (1) about "direction" and "error size" can be wrong. The ratelimit may already be over-adjusted when the dirty pages take time to approach the setpoint. The larger memory, the more time lag, the easier to overshoot and oscillate.

3) dirty pages are constantly fluctuating around the setpoint, so is pos_ratio.

With (1) and (2), it's a control system very susceptible to disturbs. With (3) we get constant disturbs. Well I had very hard time and played dirty tricks (which you may never want to know ;-) trying to tradeoff between response time and stableness..

Quoted 34 lines · Wu Fengguang

Quoted 24 lines · Jan Kara

Quoted 15 lines · Peter Zijlstra

Quoted 14 lines · Peter Zijlstra

Quoted 6 lines

origin - dirty
pos_ratio = --------------
origin - goal

which comes from the below [*] control line, so that when (dirty == goal), pos_ratio == 1.0:

OK, so basically you want a linear function for which:

f(goal) = 1 and has a root somewhere > goal.

(that one line is much more informative than all your graphs put together, one can start from there and derive your function)

Quoted 7 lines

Quoted 1 line

That does indeed get you the above function, now what does it mean?

So going by:

write_bw
ref_bw = dirty_ratelimit * pos_ratio * --------
dirty_bw

Quoted 8 lines

Actually, thinking about these formulas, why do we even bother with
computing all these factors like write_bw, dirty_bw, pos_ratio, ... Couldn't we just have a feedback loop (probably similar to the one computing pos_ratio) which will maintain single value - ratelimit? When we are getting close to dirty limit, we will scale ratelimit down, when we will be getting significantly below dirty limit, we will scale the ratelimit up. Because looking at the formulas it seems to me that the net effect is the same - pos_ratio basically overrules everything...

Quoted 3 lines

Good question. That is actually one of the early approaches I tried. It somehow worked, however the resulted ratelimit is not only slow responding, but also oscillating all the time.

Yes, I think I vaguely remember that.

Quoted 12 lines

This is due to the imperfections

1) pos_ratio at best only provides a "direction" for adjusting the ratelimit. There is only vague clues that if pos_ratio is small, the errors in ratelimit should be small.

2) Due to time-lag, the assumptions in (1) about "direction" and "error size" can be wrong. The ratelimit may already be over-adjusted when the dirty pages take time to approach the setpoint. The larger memory, the more time lag, the easier to overshoot and oscillate.

Quoted 7 lines

3) dirty pages are constantly fluctuating around the setpoint, so is pos_ratio.

With (1) and (2), it's a control system very susceptible to disturbs. With (3) we get constant disturbs. Well I had very hard time and played dirty tricks (which you may never want to know ;-) trying to tradeoff between response time and stableness..

Yes, I can see especially 2) is a problem. But I don't understand why
your current formula would be that much different. As Peter decoded from your code, your current formula is:
write_bw
ref_bw = dirty_ratelimit * pos_ratio * --------
dirty_bw

while previously it was essentially:
ref_bw = dirty_ratelimit * pos_ratio

So what is so magical about computing write_bw and dirty_bw separately? Is it because previously you did not use derivation of distance from the goal for updating pos_ratio? Because in your current formula write_bw/dirty_bw is a derivation of position...

Quoted 7 lines · Peter Zijlstra

Quoted 6 lines

origin - dirty
pos_ratio = --------------
origin - goal

which comes from the below [*] control line, so that when (dirty == goal), pos_ratio == 1.0:

Quoted 8 lines

OK, so basically you want a linear function for which:

f(goal) = 1 and has a root somewhere > goal.

(that one line is much more informative than all your graphs put together, one can start from there and derive your function)

That does indeed get you the above function, now what does it mean?

So going by:

write_bw
ref_bw = dirty_ratelimit * pos_ratio * --------
dirty_bw

pos_ratio seems to be the feedback on the deviation of the dirty pages around its setpoint.

So we adjust the reference bw (or rather ratelimit)
to take account of the shift in output vs input capacity as well as the shift in dirty pages around its setpoint.

From that we derive the condition that:

pos_ratio(setpoint) := 1

Now in order to create a linear function we need one more condition. We get one from the fact that once we hit the limit we should hard throttle our writers. We get that by setting the ratelimit to 0, because, after all, pause = nr_dirtied / ratelimit would yield inf. in that case. Thus:

pos_ratio(limit) := 0

Using these two conditions we can solve the equations and get your:

limit - dirty
pos_ratio(dirty) = ----------------
limit - setpoint

Now, for some reason you chose not to use limit, but something like min(limit, 4*thresh) something to do with the slope affecting the rate of adjustment. This wants a comment someplace.

Quoted 5 lines · Peter Zijlstra

Quoted 4 lines · Wu Fengguang

mm/page-writeback.c +0 -0

@@ -538,11 +538,6 @@ static unsigned long bdi_position_ratio(
        goal = thresh - thresh / DIRTY_SCOPE;
        origin = 4 * thresh;
 

Quoted 8 lines

mm/page-writeback.c static unsigned long bdi_position_ratio( · line 543

Quoted 8 lines

mm/page-writeback.c +0 -5

-       if (unlikely(origin < limit && dirty > (goal + origin) / 2)) {
-               origin = limit;                 /* auxiliary control line */
-               goal = (goal + origin) / 2;
-               pos_ratio >>= 1;
-       }
        pos_ratio = origin - dirty;
        pos_ratio <<= BANDWIDTH_CALC_SHIFT;
        do_div(pos_ratio, origin - goal + 1); 

FYI I've updated the fix to the below one, so that @limit will be used as the origin in the rare case of (4*thresh < dirty).

Hi Fengguang,

Ok, so just trying to understand this pos_ratio little better.

You have following basic formula.

origin - dirty
pos_ratio = --------------
origin - goal

Terminology is very confusing and following is my understanding.

- setpoint == goal

setpoint is the point where we would like our number of dirty pages to be and at this point pos_ratio = 1. For global dirty this number seems to be (thresh - thresh / DIRTY_SCOPE)

- thresh
dirty page threshold calculated from dirty_ratio (Certain percentage of total memory).

- Origin (seems to be equivalent of limit)

This seems to be the reference point/limit we don't want to cross and distance from this limit basically decides the pos_ratio. Closer we are to limit, lower the pos_ratio and further we are higher the pos_ratio.

So threshold is just a number which helps us determine goal and limit.

goal = thresh - thresh / DIRTY_SCOPE
limit = 4*thresh

So goal is where we want to be and we start throttling the task more as we move away goal and approach limit. We keep the limit high enough so that (origin-dirty) does not become negative entity.

So we do expect to cross "thresh" otherwise thresh itself could have served as limit?

If my understanding is right, then can we get rid of terms "setpoint" and "origin". Would it be easier to understand the things if we just talk in terms of "goal" and "limit" and how these are derived from "thresh".

thresh == soft limit
limit == 4*thresh (hard limit)
goal = thresh - thresh / DIRTY_SCOPE (where we want system to
be in steady state).
limit - dirty
pos_ratio = --------------
limit - goal

Thanks
Vivek

So going by:

write_bw
ref_bw = dirty_ratelimit * pos_ratio * --------
dirty_bw

pos_ratio seems to be the feedback on the deviation of the dirty pages around its setpoint. So we adjust the reference bw (or rather ratelimit) to take account of the shift in output vs input capacity as well as the shift in dirty pages around its setpoint.

From that we derive the condition that:

pos_ratio(setpoint) := 1

Now in order to create a linear function we need one more condition. We get one from the fact that once we hit the limit we should hard throttle our writers. We get that by setting the ratelimit to 0, because, after all, pause = nr_dirtied / ratelimit would yield inf. in that case. Thus:

pos_ratio(limit) := 0

Using these two conditions we can solve the equations and get your:

limit - dirty
pos_ratio(dirty) = ----------------
limit - setpoint

Now, for some reason you chose not to use limit, but something like min(limit, 4*thresh) something to do with the slope affecting the rate of adjustment. This wants a comment someplace.

Quoted 28 lines · Peter Zijlstra

So going by:

write_bw
ref_bw = dirty_ratelimit * pos_ratio * --------
dirty_bw

pos_ratio seems to be the feedback on the deviation of the dirty pages around its setpoint. So we adjust the reference bw (or rather ratelimit) to take account of the shift in output vs input capacity as well as the shift in dirty pages around its setpoint.

From that we derive the condition that:

pos_ratio(setpoint) := 1

Now in order to create a linear function we need one more condition. We get one from the fact that once we hit the limit we should hard throttle our writers. We get that by setting the ratelimit to 0, because, after all, pause = nr_dirtied / ratelimit would yield inf. in that case. Thus:

pos_ratio(limit) := 0

Using these two conditions we can solve the equations and get your:

limit - dirty
pos_ratio(dirty) = ----------------
limit - setpoint

Quoted 3 lines

Now, for some reason you chose not to use limit, but something like min(limit, 4*thresh) something to do with the slope affecting the rate of adjustment. This wants a comment someplace.

Ok, so I think that pos_ratio(limit) := 0, is a stronger condition than your negative slope (df/dx < 0), simply because it implies your condition and because it expresses our hard stop at limit.

Also, while I know this is totally over the top, but..

I saw you added a ramp and brake area in future patches, so have you considered using a third order polynomial instead?

The simple:

f(x) = -x^3

has the 'right' shape, all we need is move it so that:

f(s) = 1

and stretch it to put the single root at our limit. You'd get something like:

               s - x 3

f(x) := 1 + (-----)
d

Which, as required, is 1 at our setpoint and the factor d stretches the middle bit. Which has a single (real) root at:

x = s + d,

by setting that to our limit, we get:

d = l - s

Making our final function look like:

               s - x 3

f(x) := 1 + (-----)
l - s

You can clamp it at [0,2] or so.

The implementation wouldn't be too horrid either, something like:

unsigned long bdi_pos_ratio(..)

{
	if (dirty > limit)
		return 0;

	if (dirty < 2*setpoint - limit)
		return 2 * SCALE;

	x = SCALE * (setpoint - dirty) / (limit - setpoint);
	xx = (x * x) / SCALE;
	xxx = (xx * x) / SCALE;

	return xxx;
}

Quoted 5 lines

Making our final function look like:

               s - x 3

f(x) := 1 + (-----)
l - s

Very intuitive reasoning, thanks!

I substituted real numbers to the function assuming a mem=2GB system.

with limit=thresh:

        gnuplot> set xrange [60000:80000]
        gnuplot> plot 1 +  (70000.0 - x)**3/(80000-70000.0)**3

with limit=thresh+thresh/DIRTY_SCOPE

        gnuplot> set xrange [60000:90000]
        gnuplot> plot 1 +  (70000.0 - x)**3/(90000-70000.0)**3

Figures attached. The latter produces reasonably flat slope and I'll give it a spin in the dd tests :)

Quoted 1 line

You can clamp it at [0,2] or so.

Looking at the figures, we may even do without the clamp because it's already inside the range [0, 2].

Quoted 16 lines

The implementation wouldn't be too horrid either, something like:

unsigned long bdi_pos_ratio(..)

{
	if (dirty > limit)
		return 0;

	if (dirty < 2*setpoint - limit)
		return 2 * SCALE;

	x = SCALE * (setpoint - dirty) / (limit - setpoint);
	xx = (x * x) / SCALE;
	xxx = (xx * x) / SCALE;

	return xxx;
}

Looks very neat, much simpler than the three curves solution!

Thanks,
Fengguang

Quoted 5 lines

Making our final function look like:

               s - x 3

f(x) := 1 + (-----)
l - s

Very intuitive reasoning, thanks!

I substituted real numbers to the function assuming a mem=2GB system.

with limit=thresh:

        gnuplot> set xrange [60000:80000]
        gnuplot> plot 1 +  (70000.0 - x)**3/(80000-70000.0)**3

Code is

        unsigned long freerun = (thresh + bg_thresh) / 2;

        setpoint = (limit + freerun) / 2;
        pos_ratio = abs(dirty - setpoint);
        pos_ratio <<= BANDWIDTH_CALC_SHIFT;
        do_div(pos_ratio, limit - setpoint + 1);

        x = pos_ratio;
        pos_ratio = pos_ratio * x >> BANDWIDTH_CALC_SHIFT;
        pos_ratio = pos_ratio * x >> BANDWIDTH_CALC_SHIFT;

        if (dirty > setpoint)
                pos_ratio = -pos_ratio;
        pos_ratio += 1 << BANDWIDTH_CALC_SHIFT; 

Quoted 4 lines · Wu Fengguang

Code is

        unsigned long freerun = (thresh + bg_thresh) / 2;

Quoted 4 lines

        setpoint = (limit + freerun) / 2;
        pos_ratio = abs(dirty - setpoint);
        pos_ratio <<= BANDWIDTH_CALC_SHIFT;
        do_div(pos_ratio, limit - setpoint + 1);

Why do you use do_div()? from the code those things are unsigned long, and you can divide that just fine.

Also, there's div64_s64 that can do signed divides for s64 types. That'll loose the extra conditionals you used for abs and putting the sign back.

Quoted 3 lines

        x = pos_ratio;
        pos_ratio = pos_ratio * x >> BANDWIDTH_CALC_SHIFT;
        pos_ratio = pos_ratio * x >> BANDWIDTH_CALC_SHIFT;

So on 32bit with unsigned long that gets 32=2*(10+b) bits for x, that solves to 6, which isn't going to be enough I figure since (dirty-setpoint) !< 64.

So you really need to use u64/s64 types here, unsigned long just won't do, with u64 you have 64=2(10+b) 22 bits for x, which should fit.

Because pos_ratio was "unsigned long long"..

Quoted 3 lines

               s - x 3

f(x) := 1 + (-----)
l - s

Looks very neat, much simpler than the three curves solution!

Quoted 6 lines · Wu Fengguang

Quoted 3 lines

               s - x 3

f(x) := 1 + (-----)
l - s

Looks very neat, much simpler than the three curves solution!

Glad you like it, there is of course the small matter of real-world behaviour to consider, lets hope that works as well :-)

               s - x 3

f(x) := 1 + (-----)
d

Quoted 5 lines · Peter Zijlstra

               s - x 3

f(x) := 1 + (-----)
d

btw, if you want steeper slopes for rampup and brake you can add another factor like:

                 s - x 3

f(x) := 1 + a(-----)
d

And solve the whole f(l)=0 thing again to determine d in l and a.

For 0 < a < 1 the slopes increase.

Quoted 13 lines · Peter Zijlstra

Quoted 5 lines · Peter Zijlstra

               s - x 3

f(x) := 1 + (-----)
d

btw, if you want steeper slopes for rampup and brake you can add another factor like:

                 s - x 3

f(x) := 1 + a(-----)
d

Quoted 3 lines

And solve the whole f(l)=0 thing again to determine d in l and a.

For 0 < a < 1 the slopes increase.

Yes, we can leave it as a future tuning option. For now I'm pretty satisfied with the current function's shape :)

Now all of the above would seem to suggest:

dirty_ratelimit := ref_bw

However for that you use:

  if (pos_bw < dirty_ratelimit && ref_bw < dirty_ratelimit)
        dirty_ratelimit = max(ref_bw, pos_bw);

  if (pos_bw > dirty_ratelimit && ref_bw > dirty_ratelimit)
        dirty_ratelimit = min(ref_bw, pos_bw);

You have:

pos_bw = dirty_ratelimit * pos_ratio

Which is ref_bw without the write_bw/dirty_bw factor, this confuses me.. why are you ignoring the shift in output vs input rate there?

On Tue, 2011-08-09 at 19:20 +0200, Peter Zijlstra wrote:

Quoted 3 lines

Now all of the above would seem to suggest:

dirty_ratelimit := ref_bw

Quoted 7 lines

However for that you use:

  if (pos_bw < dirty_ratelimit && ref_bw < dirty_ratelimit)
        dirty_ratelimit = max(ref_bw, pos_bw);

  if (pos_bw > dirty_ratelimit && ref_bw > dirty_ratelimit)
        dirty_ratelimit = min(ref_bw, pos_bw);

Quoted 6 lines

You have:

pos_bw = dirty_ratelimit * pos_ratio

Which is ref_bw without the write_bw/dirty_bw factor, this confuses me.. why are you ignoring the shift in output vs input rate there?

Could you elaborate on this primary feedback loop? Its the one part I don't feel I actually understand well.

Quoted 1 line · Peter Zijlstra

On Tue, 2011-08-09 at 19:20 +0200, Peter Zijlstra wrote:

To start with,

                                                write_bw
        ref_bw = task_ratelimit_in_past_200ms * --------
                                                dirty_bw

where
task_ratelimit_in_past_200ms ~= dirty_ratelimit * pos_ratio

Quoted 3 lines

Quoted 3 lines

Now all of the above would seem to suggest:

dirty_ratelimit := ref_bw

Right, ideally ref_bw is the balanced dirty ratelimit. I actually started with exactly the above equation when I got choked by pure pos_bw based feedback control (as mentioned in the reply to Jan's email) and introduced the ref_bw estimation as the way out.

But there are some imperfections in ref_bw, too. Which makes it not suitable for direct use:

1) large fluctuations

2) due to truncates and fs redirties, the (write_bw <=> dirty_bw) becomes unbalanced match, which leads to large systematical errors in ref_bw. The truncates, due to its possibly bumpy nature, can hardly be compensated smoothly.

3) since we ultimately want to

- keep the dirty pages around the setpoint as long time as possible
- keep the fluctuations of task ratelimit as small as possible

the update policy used for (2) also serves the above goals nicely:
if for some reason the dirty pages are high (pos_bw < dirty_ratelimit), and dirty_ratelimit is low (dirty_ratelimit < ref_bw), there is no point to bring up dirty_ratelimit in a hurry and to hurt both the above two goals.

Quoted 7 lines

Quoted 7 lines

However for that you use:

  if (pos_bw < dirty_ratelimit && ref_bw < dirty_ratelimit)
        dirty_ratelimit = max(ref_bw, pos_bw);

  if (pos_bw > dirty_ratelimit && ref_bw > dirty_ratelimit)
        dirty_ratelimit = min(ref_bw, pos_bw);

The above are merely constraints to the dirty_ratelimit update. It serves to

1) stop adjusting the rate when it's against the position control target (the adjusted rate will slow down the progress of dirty pages going back to setpoint).

2) limit the step size. pos_bw is changing values step by step, leaving a consistent trace comparing to the randomly jumping ref_bw. pos_bw also has smaller errors in stable state and normally have larger errors when there are big errors in rate. So it's a pretty good limiting factor for the step size of dirty_ratelimit.

Hope the above elaboration helps :)

Quoted 21 lines · Wu Fengguang

Quoted 1 line · Peter Zijlstra

On Tue, 2011-08-09 at 19:20 +0200, Peter Zijlstra wrote:

To start with,

                                                write_bw
        ref_bw = task_ratelimit_in_past_200ms * --------
                                                dirty_bw

where
task_ratelimit_in_past_200ms ~= dirty_ratelimit * pos_ratio

Quoted 3 lines

Quoted 3 lines

Now all of the above would seem to suggest:

dirty_ratelimit := ref_bw

Right, ideally ref_bw is the balanced dirty ratelimit. I actually started with exactly the above equation when I got choked by pure pos_bw based feedback control (as mentioned in the reply to Jan's email) and introduced the ref_bw estimation as the way out.

Quoted 4 lines

But there are some imperfections in ref_bw, too. Which makes it not suitable for direct use:

1) large fluctuations

OK, understood.

Quoted 4 lines

2) due to truncates and fs redirties, the (write_bw <=> dirty_bw) becomes unbalanced match, which leads to large systematical errors in ref_bw. The truncates, due to its possibly bumpy nature, can hardly be compensated smoothly.

OK.

Quoted 4 lines

3) since we ultimately want to

- keep the dirty pages around the setpoint as long time as possible
- keep the fluctuations of task ratelimit as small as possible

Fair enough ;-)

Quoted 5 lines

the update policy used for (2) also serves the above goals nicely:
if for some reason the dirty pages are high (pos_bw < dirty_ratelimit), and dirty_ratelimit is low (dirty_ratelimit < ref_bw), there is no point to bring up dirty_ratelimit in a hurry and to hurt both the above two goals.

Right, so still I feel somewhat befuddled, so we have:

dirty_ratelimit - rate at which we throttle dirtiers as
estimated upto 200ms ago.

pos_ratio - ratio adjusting the dirty_ratelimit
for variance in dirty pages around its target

bw_ratio - ratio adjusting the dirty_ratelimit
for variance in input/output bandwidth

and we need to basically do:

dirty_ratelimit *= pos_ratio * bw_ratio

to update the dirty_ratelimit to reflect the current state. However per
1) and 2) bw_ratio is crappy and hard to fix.

So you propose to update dirty_ratelimit only if both pos_ratio and bw_ratio point in the same direction, however that would result in:

if (pos_ratio < UNIT && bw_ratio < UNIT ||

      pos_ratio > UNIT && bw_ratio > UNIT) {
	dirty_ratelimit = (dirty_ratelimit * pos_ratio) / UNIT;
	dirty_ratelimit = (dirty_ratelimit * bw_ratio) / UNIT;

}

Quoted 8 lines

Quoted 7 lines

Quoted 7 lines

However for that you use:

  if (pos_bw < dirty_ratelimit && ref_bw < dirty_ratelimit)
        dirty_ratelimit = max(ref_bw, pos_bw);

  if (pos_bw > dirty_ratelimit && ref_bw > dirty_ratelimit)
        dirty_ratelimit = min(ref_bw, pos_bw);

Quoted 6 lines

The above are merely constraints to the dirty_ratelimit update. It serves to

1) stop adjusting the rate when it's against the position control target (the adjusted rate will slow down the progress of dirty pages going back to setpoint).

Not strictly speaking, suppose pos_ratio = 0.5 and bw_ratio = 1.1, then they point in different directions however:

0.5 < 1 && 0.5 * 1.1 < 1

so your code will in fact update the dirty_ratelimit, even though the two factors point in opposite directions.

Quoted 5 lines

2) limit the step size. pos_bw is changing values step by step, leaving a consistent trace comparing to the randomly jumping ref_bw. pos_bw also has smaller errors in stable state and normally have larger errors when there are big errors in rate. So it's a pretty good limiting factor for the step size of dirty_ratelimit.

OK, so that's the min/max stuff, however it only works because you use pos_bw and ref_bw instead of the fully separated factors.

Quoted 1 line

Hope the above elaboration helps :)

A little..

- not a factor at all for updating balanced_rate (whether or not we do (2)) well, in this concept: the balanced_rate formula inherently does not derive the balanced_rate_(i+1) from balanced_rate_i. Rather it's based on the ratelimit executed for the past 200ms:

          balanced_rate_(i+1) = task_ratelimit_200ms * bw_ratio

and task_ratelimit_200ms happen to can be estimated from

task_ratelimit_200ms ~= balanced_rate_i * pos_ratio

We may alternatively record every task_ratelimit executed in the past 200ms and average them all to get task_ratelimit_200ms. In this way we take the "superfluous" pos_ratio out of sight :)

There is fundamentally no dependency between balanced_rate_(i+1) and balanced_rate_i/task_ratelimit_200ms: the balanced_rate estimation only asks for _whatever_ CONSTANT task ratelimit to be executed for 200ms, then it get the balanced rate from the dirty_rate feedback.

Quoted 6 lines · Wu Fengguang

- not a factor at all for updating balanced_rate (whether or not we do (2)) well, in this concept: the balanced_rate formula inherently does not derive the balanced_rate_(i+1) from balanced_rate_i. Rather it's based on the ratelimit executed for the past 200ms:

          balanced_rate_(i+1) = task_ratelimit_200ms * bw_ratio

Ok, this is where it all goes funny..

So if you want completely separated feedback loops I would expect

something like:

	balance_rate_(i+1) = balance_rate_(i) * bw_ratio   ; every 200ms

The former is a complete feedback loop, expressing the new value in the old value (*) with bw_ratio as feedback parameter; if we throttled too much, the dirty_rate will have dropped and the bw_ratio will be <1 causing the balance_rate to drop increasing the dirty_rate, and vice versa.

(*) which is the form I expected and why I thought your primary feedback loop looked like: rate_(i+1) = rate_(i) * pos_ratio * bw_ratio

With the above balance_rate is an independent variable that tracks the write bandwidth. Now possibly you'd want a low-pass filter on that since your bw_ratio is a bit funny in the head, but that's another story.

Then when you use the balance_rate to actually throttle tasks you apply your secondary control steering the dirty page count, yielding:

task_rate = balance_rate * pos_ratio

Quoted 3 lines

and task_ratelimit_200ms happen to can be estimated from

task_ratelimit_200ms ~= balanced_rate_i * pos_ratio

Quoted 3 lines

We may alternatively record every task_ratelimit executed in the past 200ms and average them all to get task_ratelimit_200ms. In this way we take the "superfluous" pos_ratio out of sight :)

Right, so I'm not at all sure that makes sense, its not immediately evident that <task_ratelimit> ~= balance_rate * pos_ratio. Nor is it clear to me why your primary feedback loop uses task_ratelimit_200ms at all.

Quoted 4 lines

There is fundamentally no dependency between balanced_rate_(i+1) and balanced_rate_i/task_ratelimit_200ms: the balanced_rate estimation only asks for _whatever_ CONSTANT task ratelimit to be executed for 200ms, then it get the balanced rate from the dirty_rate feedback.

How can there not be a relation between balance_rate_(i+1) and balance_rate_(i) ?

Quoted 11 lines · Peter Zijlstra

Quoted 6 lines · Wu Fengguang

- not a factor at all for updating balanced_rate (whether or not we do (2)) well, in this concept: the balanced_rate formula inherently does not derive the balanced_rate_(i+1) from balanced_rate_i. Rather it's based on the ratelimit executed for the past 200ms:

          balanced_rate_(i+1) = task_ratelimit_200ms * bw_ratio

Ok, this is where it all goes funny..

So if you want completely separated feedback loops I would expect

If call it feedback loops, then it's a series of independent feedback loops of depth 1. Because each balanced_rate is a fresh estimation dependent solely on

- writeout bandwidth
- N, the number of dd tasks

in the past 200ms.

As long as a CONSTANT ratelimit (whatever value it is) is executed in the past 200ms, we can get the same balanced_rate.

balanced_rate = CONSTANT_ratelimit * write_bw / dirty_rate

The resulted balanced_rate is independent of how large the CONSTANT ratelimit is, because if we start with a doubled CONSTANT ratelimit, we'll see doubled dirty_rate and result in the same balanced_rate.

In that manner, balance_rate_(i+1) is not really depending on the value of balance_rate_(i): whatever balance_rate_(i) is, we are going to get the same balance_rate_(i+1) if not considering estimation errors. Note that the estimation errors mainly come from the fluctuations in dirty_rate.

That may well be what's already in your mind, just that we disagree about the terms ;)

Quoted 9 lines

something like:

	balance_rate_(i+1) = balance_rate_(i) * bw_ratio   ; every 200ms

The former is a complete feedback loop, expressing the new value in the old value (*) with bw_ratio as feedback parameter; if we throttled too much, the dirty_rate will have dropped and the bw_ratio will be <1 causing the balance_rate to drop increasing the dirty_rate, and vice versa.

In principle, the bw_ratio works that way. However since balance_rate_(i) is not the exact _executed_ ratelimit in balance_dirty_pages().

Quoted 2 lines

(*) which is the form I expected and why I thought your primary feedback loop looked like: rate_(i+1) = rate_(i) * pos_ratio * bw_ratio

Because the executed ratelimit was rate_(i) * pos_ratio.

Quoted 3 lines

With the above balance_rate is an independent variable that tracks the write bandwidth. Now possibly you'd want a low-pass filter on that since your bw_ratio is a bit funny in the head, but that's another story.

Yeah.

Quoted 4 lines

Then when you use the balance_rate to actually throttle tasks you apply your secondary control steering the dirty page count, yielding:

task_rate = balance_rate * pos_ratio

Right. Note the above formula is not a derived one, but an original one that later leads to pos_ratio showing up in the calculation of balanced_rate.

Quoted 4 lines

Quoted 3 lines

and task_ratelimit_200ms happen to can be estimated from

task_ratelimit_200ms ~= balanced_rate_i * pos_ratio

Quoted 8 lines

Quoted 3 lines

We may alternatively record every task_ratelimit executed in the past 200ms and average them all to get task_ratelimit_200ms. In this way we take the "superfluous" pos_ratio out of sight :)

Right, so I'm not at all sure that makes sense, its not immediately evident that <task_ratelimit> ~= balance_rate * pos_ratio. Nor is it clear to me why your primary feedback loop uses task_ratelimit_200ms at all.

task_ratelimit is used and hence defined to be (balance_rate * pos_ratio) by balance_dirty_pages(). So this is an original formula:

task_ratelimit = balance_rate * pos_ratio

task_ratelimit_200ms is also used as an original data source in

balanced_rate = task_ratelimit_200ms * write_bw / dirty_rate

You somehow directly jump to

balanced_rate = task_ratelimit_200ms * write_bw / dirty_rate

without explaining why following will not work.

balanced_rate_(i+1) = balance_rate(i) * write_bw / dirty_rate

Quoted 7 lines

You somehow directly jump to

balanced_rate = task_ratelimit_200ms * write_bw / dirty_rate

without explaining why following will not work.

balanced_rate_(i+1) = balance_rate(i) * write_bw / dirty_rate

Thanks for asking that, it's probably the root of confusions, so let me answer it standalone.

It's actually pretty simple to explain this equation:

                                               write_bw
        balanced_rate = task_ratelimit_200ms * ----------       (1)
                                               dirty_rate

If there are N dd tasks, each task is throttled at task_ratelimit_200ms for the past 200ms, we are going to measure the overall bdi dirty rate

dirty_rate = N * task_ratelimit_200ms (2)

put (2) into (1) we get

balanced_rate = write_bw / N (3)

So equation (1) is the right estimation to get the desired target (3).

As for

                                                  write_bw
        balanced_rate_(i+1) = balanced_rate_(i) * ----------    (4)
                                                  dirty_rate

Let's compare it with the "expanded" form of (1):

                                                              write_bw
        balanced_rate_(i+1) = balanced_rate_(i) * pos_ratio * ----------      (5)
                                                              dirty_rate

So the difference lies in pos_ratio.

Believe it or not, it's exactly the seemingly use of pos_ratio that makes (5) independent(*) of the position control.

Why? Look at (4), assume the system is in a state

- dirty rate is already balanced, ie. balanced_rate_(i) = write_bw / N
- dirty position is not balanced, for example pos_ratio = 0.5

balance_dirty_pages() will be rate limiting each tasks at half the balanced dirty rate, yielding a measured

dirty_rate = write_bw / 2 (6)

Put (6) into (4), we get

        balanced_rate_(i+1) = balanced_rate_(i) * 2
                            = (write_bw / N) * 2

That means, any position imbalance will lead to balanced_rate estimation errors if we follow (4). Whereas if (1)/(5) is used, we always get the right balanced dirty ratelimit value whether or not (pos_ratio == 1.0), hence make the rate estimation independent(*) of dirty position control.

(*) independent as in real values, not the seemingly relations in equation

Quoted 67 lines · Wu Fengguang

Quoted 7 lines

You somehow directly jump to

balanced_rate = task_ratelimit_200ms * write_bw / dirty_rate

without explaining why following will not work.

balanced_rate_(i+1) = balance_rate(i) * write_bw / dirty_rate

Thanks for asking that, it's probably the root of confusions, so let me answer it standalone.

It's actually pretty simple to explain this equation:

                                               write_bw
        balanced_rate = task_ratelimit_200ms * ----------       (1)
                                               dirty_rate

If there are N dd tasks, each task is throttled at task_ratelimit_200ms for the past 200ms, we are going to measure the overall bdi dirty rate

dirty_rate = N * task_ratelimit_200ms (2)

put (2) into (1) we get

balanced_rate = write_bw / N (3)

So equation (1) is the right estimation to get the desired target (3).

As for

                                                  write_bw
        balanced_rate_(i+1) = balanced_rate_(i) * ----------    (4)
                                                  dirty_rate

Let's compare it with the "expanded" form of (1):

                                                              write_bw
        balanced_rate_(i+1) = balanced_rate_(i) * pos_ratio * ----------      (5)
                                                              dirty_rate

So the difference lies in pos_ratio.

Believe it or not, it's exactly the seemingly use of pos_ratio that makes (5) independent(*) of the position control.

Why? Look at (4), assume the system is in a state

- dirty rate is already balanced, ie. balanced_rate_(i) = write_bw / N
- dirty position is not balanced, for example pos_ratio = 0.5

balance_dirty_pages() will be rate limiting each tasks at half the balanced dirty rate, yielding a measured

dirty_rate = write_bw / 2 (6)

Put (6) into (4), we get

        balanced_rate_(i+1) = balanced_rate_(i) * 2
                            = (write_bw / N) * 2

That means, any position imbalance will lead to balanced_rate estimation errors if we follow (4). Whereas if (1)/(5) is used, we always get the right balanced dirty ratelimit value whether or not (pos_ratio == 1.0), hence make the rate estimation independent(*) of dirty position control.

Quoted 1 line

(*) independent as in real values, not the seemingly relations in equation

The assumption here is that N is a constant.. in the above case pos_ratio would eventually end up at 1 and things would be good again. I see your argument about oscillations, but I think you can introduce similar effects by varying N.

Quoted 16 lines · Peter Zijlstra

Quoted 12 lines · Wu Fengguang

Put (6) into (4), we get

        balanced_rate_(i+1) = balanced_rate_(i) * 2
                            = (write_bw / N) * 2

That means, any position imbalance will lead to balanced_rate estimation errors if we follow (4). Whereas if (1)/(5) is used, we always get the right balanced dirty ratelimit value whether or not (pos_ratio == 1.0), hence make the rate estimation independent(*) of dirty position control.

(*) independent as in real values, not the seemingly relations in equation

Quoted 4 lines

The assumption here is that N is a constant.. in the above case pos_ratio would eventually end up at 1 and things would be good again. I see your argument about oscillations, but I think you can introduce similar effects by varying N.

Yeah, it's very possible for N to change over time, in which case balanced_rate will adapt to new N in similar way.

Quoted 22 lines · Wu Fengguang

Quoted 20 lines · Peter Zijlstra

Quoted 5 lines · Wu Fengguang

Put (6) into (4), we get

        balanced_rate_(i+1) = balanced_rate_(i) * 2
                            = (write_bw / N) * 2

Quoted 7 lines

That means, any position imbalance will lead to balanced_rate estimation errors if we follow (4). Whereas if (1)/(5) is used, we always get the right balanced dirty ratelimit value whether or not (pos_ratio == 1.0), hence make the rate estimation independent(*) of dirty position control.

(*) independent as in real values, not the seemingly relations in equation

The assumption here is that N is a constant.. in the above case pos_ratio would eventually end up at 1 and things would be good again. I see your argument about oscillations, but I think you can introduce similar effects by varying N.

Quoted 2 lines

Yeah, it's very possible for N to change over time, in which case balanced_rate will adapt to new N in similar way.

Gah.. but but but, that gives the same stuff as your (6)+(4). Why won't you accept that for pos_ratio but you don't mind for N ?

Sorry I'm now feeling lost...

Quoted 1 line · Wu Fengguang

Sorry I'm now feeling lost...

hehe welcome to my world ;-)

Seriously though, I appreciate all the effort you put in trying to explain things. I feel I do understand things now, although I might not completely agree with them quite yet ;-)

I'll go read the v9 patch-set you send out and look at some of the details (such as pos_ratio being comprised of both global and bdi limits, which so far has been somewhat glossed over).

Now I get 3 figures. Test case is: run 1 dd write task for 300s, with a "disturber" dd read task during roughly 120-130s.

Quoted 2 lines · Wu Fengguang

Now I get 3 figures. Test case is: run 1 dd write task for 300s, with a "disturber" dd read task during roughly 120-130s.

Ah, but ideally the disturber task should run in bursts of 100ms (<feedback period), otherwise your N is indeed mostly constant.

Quoted 4 lines · Peter Zijlstra

Quoted 2 lines · Wu Fengguang

Now I get 3 figures. Test case is: run 1 dd write task for 300s, with a "disturber" dd read task during roughly 120-130s.

Quoted 2 lines

Ah, but ideally the disturber task should run in bursts of 100ms (<feedback period), otherwise your N is indeed mostly constant.

Ah yeah, the disturber task should be a dd writer! Then we get

- 120s: N=1 => N=2
- 130s: N=2 => N=1

We got similar result as in the read disturber case, even though one disturbs N and the other impacts writeout bandwith. The original patchset is consistently performing much better :)

Quoted 3 lines · Wu Fengguang

We got similar result as in the read disturber case, even though one disturbs N and the other impacts writeout bandwith. The original patchset is consistently performing much better :)

It does indeed, and I figure on these timescales it makes sense to assumes N is a constant. Fair enough, thanks!

Quoted 7 lines

You somehow directly jump to

balanced_rate = task_ratelimit_200ms * write_bw / dirty_rate

without explaining why following will not work.

balanced_rate_(i+1) = balance_rate(i) * write_bw / dirty_rate

Thanks for asking that, it's probably the root of confusions, so let me answer it standalone.

It's actually pretty simple to explain this equation:

                                               write_bw
        balanced_rate = task_ratelimit_200ms * ----------       (1)
                                               dirty_rate

If there are N dd tasks, each task is throttled at task_ratelimit_200ms for the past 200ms, we are going to measure the overall bdi dirty rate

dirty_rate = N * task_ratelimit_200ms (2)

put (2) into (1) we get

balanced_rate = write_bw / N (3)

So equation (1) is the right estimation to get the desired target (3).

As for

                                                  write_bw
        balanced_rate_(i+1) = balanced_rate_(i) * ----------    (4)
                                                  dirty_rate

Let's compare it with the "expanded" form of (1):

                                                              write_bw
        balanced_rate_(i+1) = balanced_rate_(i) * pos_ratio * ----------      (5)
                                                              dirty_rate

So the difference lies in pos_ratio.

Believe it or not, it's exactly the seemingly use of pos_ratio that makes (5) independent(*) of the position control.

Why? Look at (4), assume the system is in a state

- dirty rate is already balanced, ie. balanced_rate_(i) = write_bw / N
- dirty position is not balanced, for example pos_ratio = 0.5

balance_dirty_pages() will be rate limiting each tasks at half the balanced dirty rate, yielding a measured

dirty_rate = write_bw / 2 (6)

Put (6) into (4), we get

        balanced_rate_(i+1) = balanced_rate_(i) * 2
                            = (write_bw / N) * 2

That means, any position imbalance will lead to balanced_rate estimation errors if we follow (4). Whereas if (1)/(5) is used, we always get the right balanced dirty ratelimit value whether or not (pos_ratio == 1.0), hence make the rate estimation independent(*) of dirty position control.

(*) independent as in real values, not the seemingly relations in equation

Quoted 67 lines · Wu Fengguang

Quoted 7 lines

You somehow directly jump to

balanced_rate = task_ratelimit_200ms * write_bw / dirty_rate

without explaining why following will not work.

balanced_rate_(i+1) = balance_rate(i) * write_bw / dirty_rate

Thanks for asking that, it's probably the root of confusions, so let me answer it standalone.

It's actually pretty simple to explain this equation:

                                               write_bw
        balanced_rate = task_ratelimit_200ms * ----------       (1)
                                               dirty_rate

If there are N dd tasks, each task is throttled at task_ratelimit_200ms for the past 200ms, we are going to measure the overall bdi dirty rate

dirty_rate = N * task_ratelimit_200ms (2)

put (2) into (1) we get

balanced_rate = write_bw / N (3)

So equation (1) is the right estimation to get the desired target (3).

As for

                                                  write_bw
        balanced_rate_(i+1) = balanced_rate_(i) * ----------    (4)
                                                  dirty_rate

Let's compare it with the "expanded" form of (1):

                                                              write_bw
        balanced_rate_(i+1) = balanced_rate_(i) * pos_ratio * ----------      (5)
                                                              dirty_rate

So the difference lies in pos_ratio.

Believe it or not, it's exactly the seemingly use of pos_ratio that makes (5) independent(*) of the position control.

Why? Look at (4), assume the system is in a state

- dirty rate is already balanced, ie. balanced_rate_(i) = write_bw / N
- dirty position is not balanced, for example pos_ratio = 0.5

balance_dirty_pages() will be rate limiting each tasks at half the balanced dirty rate, yielding a measured

dirty_rate = write_bw / 2 (6)

Put (6) into (4), we get

        balanced_rate_(i+1) = balanced_rate_(i) * 2
                            = (write_bw / N) * 2

That means, any position imbalance will lead to balanced_rate estimation errors if we follow (4). Whereas if (1)/(5) is used, we always get the right balanced dirty ratelimit value whether or not (pos_ratio == 1.0), hence make the rate estimation independent(*) of dirty position control.

Quoted 1 line

(*) independent as in real values, not the seemingly relations in equation

Ok, I think I am beginning to see your point. Let me just elaborate on the example you gave.

Assume a system is completely balanced and a task is writing at 100MB/s rate.

write_bw = dirty_rate = 100MB/s, pos_ratio = 1; N=1

bdi->dirty_ratelimit = 100MB/s

Now another tasks starts dirtying the page cache on same bdi. Number of dirty pages should go up pretty fast and likely position ratio feedback will kick in to reduce the dirtying rate. (rate based feedback does not kick in till next 200ms) and pos_ratio feedback seems to be instantaneous.

Assume new pos_ratio is .5

So new throttle rate for both the tasks is 50MB/s.

bdi->dirty_ratelimit = 100MB/s (a feedback has not kicked in yet) task_ratelimit = bdi->dirty_ratelimit * pos_ratio = 100 *.5 = 50MB/s

Now lets say 200ms have passed and rate base feedback is reevaluated.

write_bw
bdi->dirty_ratelimit_(i+1) = bdi->dirty_ratelimit_i * ---------
dirty_bw

bdi->dirty_ratelimit_(i+1) = 100 * 100/100 = 100MB/s

Ideally bdi->dirty_ratelimit should have now become 50MB/s as N=2 but that did not happen. And reason being that there are two feedback control loops and pos_ratio loops reacts to imbalances much more quickly. Because previous loop has already reacted to the imbalance and reduced the dirtying rate of task, rate based loop does not try to adjust anything and thinks everything is just fine.

Things are fine in the sense that still dirty_rate == write_bw but system is not balanced in terms of number of dirty pages and pos_ratio=.5

So you are trying to make one feedback loop aware of second loop so that if second loop is unbalanced, first loop reacts to that as well and not just look at dirty_rate and write_bw. So refining new balanced rate by pos_ratio helps.
write_bw
bdi->dirty_ratelimit_(i+1) = bdi->dirty_ratelimit_i * --------- * pos_ratio
dirty_bw

Now if global dirty pages are imbalanced, balanced rate will still go down despite the fact that dirty_bw == write_bw. This will lead to further reduction in task dirty rate. Which in turn will lead to reduced number of dirty rate and should eventually lead to pos_ratio=1.

A related question though I should have asked you this long back. How does throttling based on rate helps. Why we could not just work with two pos_ratios. One is gloabl postion ratio and other is bdi position ratio. And then throttle task gradually to achieve smooth throttling behavior. IOW, what property does rate provide which is not available just by looking at per bdi dirty pages. Can't we come up with bdi setpoint and limit the way you have done for gloabl setpoint and throttle tasks accordingly?

Quoted 8 lines

So you are trying to make one feedback loop aware of second loop so that if second loop is unbalanced, first loop reacts to that as well and not just look at dirty_rate and write_bw. So refining new balanced rate by pos_ratio helps.
write_bw
bdi->dirty_ratelimit_(i+1) = bdi->dirty_ratelimit_i * --------- * pos_ratio
dirty_bw

Quoted 4 lines

Now if global dirty pages are imbalanced, balanced rate will still go down despite the fact that dirty_bw == write_bw. This will lead to further reduction in task dirty rate. Which in turn will lead to reduced number of dirty rate and should eventually lead to pos_ratio=1.

Right, that's a good alternative viewpoint to the below one.

write_bw
bdi->dirty_ratelimit_(i+1) = task_ratelimit_i * ---------
dirty_bw

(1) the periodic rate estimation uses that to refresh the balanced rate on every 200ms
(2) as long as the rate estimation is correct, pos_ratio is able to drive itself to 1.0

Quoted 9 lines

A related question though I should have asked you this long back. How does throttling based on rate helps. Why we could not just work with two pos_ratios. One is gloabl postion ratio and other is bdi position ratio. And then throttle task gradually to achieve smooth throttling behavior. IOW, what property does rate provide which is not available just by looking at per bdi dirty pages. Can't we come up with bdi setpoint and limit the way you have done for gloabl setpoint and throttle tasks accordingly?

Good question. If we have no idea of the balanced rate at all, but still want to limit dirty pages within the range [freerun, limit], all we can do is to throttle the task at eg. 1TB/s at @freerun and 0 at @limit. Then you get a really sharp control line which will make task_ratelimit fluctuate like mad...

So the balanced rate estimation is the key to get smooth task_ratelimit, while pos_ratio is the ultimate guarantee for the dirty pages range.

On Thu, Aug 25, 2011 at 11:19:34AM +0800, Wu Fengguang wrote:

[..]

Quoted 13 lines

Quoted 8 lines

So you are trying to make one feedback loop aware of second loop so that if second loop is unbalanced, first loop reacts to that as well and not just look at dirty_rate and write_bw. So refining new balanced rate by pos_ratio helps.
write_bw
bdi->dirty_ratelimit_(i+1) = bdi->dirty_ratelimit_i * --------- * pos_ratio
dirty_bw

Quoted 4 lines

Now if global dirty pages are imbalanced, balanced rate will still go down despite the fact that dirty_bw == write_bw. This will lead to further reduction in task dirty rate. Which in turn will lead to reduced number of dirty rate and should eventually lead to pos_ratio=1.

Quoted 8 lines

Right, that's a good alternative viewpoint to the below one.

write_bw
bdi->dirty_ratelimit_(i+1) = task_ratelimit_i * ---------
dirty_bw

(1) the periodic rate estimation uses that to refresh the balanced rate on every 200ms
(2) as long as the rate estimation is correct, pos_ratio is able to drive itself to 1.0

Personally I found it much easier to understand the other representation. Once you have come up with equation.

balance_rate_(i+1) = balance_rate(i) * write_bw/dirty_bw

Can you please put few lines of comments to explain that why above alone is not sufficient and we need to take pos_ratio also in to account to keep number of dirty pages in check. And then go onto

balance_rate_(i+1) = balance_rate(i) * write_bw/dirty_bw * pos_ratio

This kind of maintains the continuity of explanation and explains that why are we deviating from the theory we discussed so far.

Quoted 16 lines

Quoted 9 lines

A related question though I should have asked you this long back. How does throttling based on rate helps. Why we could not just work with two pos_ratios. One is gloabl postion ratio and other is bdi position ratio. And then throttle task gradually to achieve smooth throttling behavior. IOW, what property does rate provide which is not available just by looking at per bdi dirty pages. Can't we come up with bdi setpoint and limit the way you have done for gloabl setpoint and throttle tasks accordingly?

Good question. If we have no idea of the balanced rate at all, but still want to limit dirty pages within the range [freerun, limit], all we can do is to throttle the task at eg. 1TB/s at @freerun and 0 at @limit. Then you get a really sharp control line which will make task_ratelimit fluctuate like mad...

Quoted 2 lines

So the balanced rate estimation is the key to get smooth task_ratelimit, while pos_ratio is the ultimate guarantee for the dirty pages range.

Ok, that makes sense. By keeping an estimation of rate at which bdi can write, our range of throttling goes down. Say 0 to 300MB/s instead of 0 to 1TB/sec and that can lead to a more smooth behavior.

/*
* A linear estimation of the "balanced" throttle rate. The theory is,
* if there are N dd tasks, each throttled at task_ratelimit, the bdi's
* dirty_rate will be measured to be (N * task_ratelimit). So the below
* formula will yield the balanced rate limit (write_bw / N). *
* Note that the expanded form is not a pure rate feedback:
* rate_(i+1) = rate_(i) * (write_bw / dirty_rate) (1)
* but also takes pos_ratio into account:
* rate_(i+1) = rate_(i) * (write_bw / dirty_rate) * pos_ratio (2)
*
* (1) is not realistic because pos_ratio also takes part in balancing
* the dirty rate. Consider the state
* pos_ratio = 0.5 (3)
* rate = 2 * (write_bw / N) (4)
* If (1) is used, it will stuck in that state! Because each dd will be
* throttled at
* task_ratelimit = pos_ratio * rate = (write_bw / N) (5)
* yielding
* dirty_rate = N * task_ratelimit = write_bw (6)
* put (6) into (1) we get
* rate_(i+1) = rate_(i) (7)

*
* So we end up using (2) to always keep
* rate_(i+1) ~= (write_bw / N) (8)
* regardless of the value of pos_ratio. As long as (8) is satisfied,
* pos_ratio is able to drive itself to 1.0, which is not only where
* the dirty count meet the setpoint, but also where the slope of
* pos_ratio is most flat and hence task_ratelimit is least fluctuated. */

Quoted 22 lines · Wu Fengguang

/*
* A linear estimation of the "balanced" throttle rate. The theory is,
* if there are N dd tasks, each throttled at task_ratelimit, the bdi's
* dirty_rate will be measured to be (N * task_ratelimit). So the below
* formula will yield the balanced rate limit (write_bw / N). *
* Note that the expanded form is not a pure rate feedback:
* rate_(i+1) = rate_(i) * (write_bw / dirty_rate) (1)
* but also takes pos_ratio into account:
* rate_(i+1) = rate_(i) * (write_bw / dirty_rate) * pos_ratio (2)
*
* (1) is not realistic because pos_ratio also takes part in balancing
* the dirty rate. Consider the state
* pos_ratio = 0.5 (3)
* rate = 2 * (write_bw / N) (4)
* If (1) is used, it will stuck in that state! Because each dd will be
* throttled at
* task_ratelimit = pos_ratio * rate = (write_bw / N) (5)
* yielding
* dirty_rate = N * task_ratelimit = write_bw (6)
* put (6) into (1) we get
* rate_(i+1) = rate_(i) (7)

Quoted 8 lines

*
* So we end up using (2) to always keep
* rate_(i+1) ~= (write_bw / N) (8)
* regardless of the value of pos_ratio. As long as (8) is satisfied,
* pos_ratio is able to drive itself to 1.0, which is not only where
* the dirty count meet the setpoint, but also where the slope of
* pos_ratio is most flat and hence task_ratelimit is least fluctuated. */

I'm still not buying this, it has the massive assumption N is a constant, without that assumption you get the same kind of thing you get from not adding pos_ratio to the feedback term.

Also, I've yet to see what harm it does if you leave it out, all feedback loops should stabilize just fine.

Ok, I think I am beginning to see your point. Let me just elaborate on the example you gave.

Assume a system is completely balanced and a task is writing at 100MB/s rate.

write_bw = dirty_rate = 100MB/s, pos_ratio = 1; N=1

bdi->dirty_ratelimit = 100MB/s

Now another tasks starts dirtying the page cache on same bdi. Number of dirty pages should go up pretty fast and likely position ratio feedback will kick in to reduce the dirtying rate. (rate based feedback does not kick in till next 200ms) and pos_ratio feedback seems to be instantaneous. Assume new pos_ratio is .5

So new throttle rate for both the tasks is 50MB/s.

bdi->dirty_ratelimit = 100MB/s (a feedback has not kicked in yet) task_ratelimit = bdi->dirty_ratelimit * pos_ratio = 100 *.5 = 50MB/s

Now lets say 200ms have passed and rate base feedback is reevaluated.

write_bw
bdi->dirty_ratelimit_(i+1) = bdi->dirty_ratelimit_i * ---------
dirty_bw

bdi->dirty_ratelimit_(i+1) = 100 * 100/100 = 100MB/s

Ideally bdi->dirty_ratelimit should have now become 50MB/s as N=2 but that did not happen. And reason being that there are two feedback control loops and pos_ratio loops reacts to imbalances much more quickly. Because previous loop has already reacted to the imbalance and reduced the dirtying rate of task, rate based loop does not try to adjust anything and thinks everything is just fine.

Things are fine in the sense that still dirty_rate == write_bw but system is not balanced in terms of number of dirty pages and pos_ratio=.5

So you are trying to make one feedback loop aware of second loop so that if second loop is unbalanced, first loop reacts to that as well and not just look at dirty_rate and write_bw. So refining new balanced rate by pos_ratio helps.
write_bw
bdi->dirty_ratelimit_(i+1) = bdi->dirty_ratelimit_i * --------- * pos_ratio
dirty_bw

Now if global dirty pages are imbalanced, balanced rate will still go down despite the fact that dirty_bw == write_bw. This will lead to further reduction in task dirty rate. Which in turn will lead to reduced number of dirty rate and should eventually lead to pos_ratio=1.

Quoted 48 lines · Vivek Goyal

Ok, I think I am beginning to see your point. Let me just elaborate on the example you gave.

Assume a system is completely balanced and a task is writing at 100MB/s rate.

write_bw = dirty_rate = 100MB/s, pos_ratio = 1; N=1

bdi->dirty_ratelimit = 100MB/s

Now another tasks starts dirtying the page cache on same bdi. Number of dirty pages should go up pretty fast and likely position ratio feedback will kick in to reduce the dirtying rate. (rate based feedback does not kick in till next 200ms) and pos_ratio feedback seems to be instantaneous. Assume new pos_ratio is .5

So new throttle rate for both the tasks is 50MB/s.

bdi->dirty_ratelimit = 100MB/s (a feedback has not kicked in yet) task_ratelimit = bdi->dirty_ratelimit * pos_ratio = 100 *.5 = 50MB/s

Now lets say 200ms have passed and rate base feedback is reevaluated.

write_bw
bdi->dirty_ratelimit_(i+1) = bdi->dirty_ratelimit_i * ---------
dirty_bw

bdi->dirty_ratelimit_(i+1) = 100 * 100/100 = 100MB/s

Ideally bdi->dirty_ratelimit should have now become 50MB/s as N=2 but that did not happen. And reason being that there are two feedback control loops and pos_ratio loops reacts to imbalances much more quickly. Because previous loop has already reacted to the imbalance and reduced the dirtying rate of task, rate based loop does not try to adjust anything and thinks everything is just fine.

Things are fine in the sense that still dirty_rate == write_bw but system is not balanced in terms of number of dirty pages and pos_ratio=.5

So you are trying to make one feedback loop aware of second loop so that if second loop is unbalanced, first loop reacts to that as well and not just look at dirty_rate and write_bw. So refining new balanced rate by pos_ratio helps.
write_bw
bdi->dirty_ratelimit_(i+1) = bdi->dirty_ratelimit_i * --------- * pos_ratio
dirty_bw

Quoted 4 lines

Now if global dirty pages are imbalanced, balanced rate will still go down despite the fact that dirty_bw == write_bw. This will lead to further reduction in task dirty rate. Which in turn will lead to reduced number of dirty rate and should eventually lead to pos_ratio=1.

Ok so this argument makes sense, is there some formalism to describe such systems where such things are more evident?

Quoted 3 lines

Ok so this argument makes sense, is there some formalism to describe such systems where such things are more evident?

I find the most easy and clean way to describe it is,

(1) the below formula

                                                          write_bw  
    bdi->dirty_ratelimit_(i+1) = bdi->dirty_ratelimit_i * --------- * pos_ratio
                                                          dirty_bw

is able to yield

    dirty_ratelimit_(i) ~= (write_bw / N)

as long as

- write_bw, dirty_bw and pos_ratio are not changing rapidly
- dirty pages are not around @freerun or @limit

Otherwise there will be larger estimation errors.

(2) based on (1), we get

task_ratelimit ~= (write_bw / N) * pos_ratio

So the pos_ratio feedback is able to drive dirty count to the setpoint, where pos_ratio = 1.

That interpretation based on _real values_ can neatly decouple the two feedback loops :) It makes full utilization of the fact "the dirty_ratelimit _value_ is independent on pos_ratio except for possible impacts on estimation errors".

Quoted 25 lines · Wu Fengguang

Quoted 3 lines

Ok so this argument makes sense, is there some formalism to describe such systems where such things are more evident?

I find the most easy and clean way to describe it is,

(1) the below formula

                                                          write_bw  
    bdi->dirty_ratelimit_(i+1) = bdi->dirty_ratelimit_i * --------- * pos_ratio
                                                          dirty_bw

is able to yield

    dirty_ratelimit_(i) ~= (write_bw / N)

as long as

- write_bw, dirty_bw and pos_ratio are not changing rapidly
- dirty pages are not around @freerun or @limit

Otherwise there will be larger estimation errors.

(2) based on (1), we get

task_ratelimit ~= (write_bw / N) * pos_ratio

Quoted 7 lines

So the pos_ratio feedback is able to drive dirty count to the setpoint, where pos_ratio = 1.

That interpretation based on _real values_ can neatly decouple the two feedback loops :) It makes full utilization of the fact "the dirty_ratelimit _value_ is independent on pos_ratio except for possible impacts on estimation errors".

OK, so the 'problem' I have with this is that the whole control thing really doesn't care about N. All it does is measure:

- dirty rate
- writeback rate

observe:

- dirty count; with the independent input of its setpoint

control:

- ratelimit

so I was looking for a way to describe the interaction between the two feedback loops without involving the exact details of what they're controlling, but that might just end up being an oxymoron.

Quoted 11 lines · Peter Zijlstra

Quoted 6 lines · Wu Fengguang

- not a factor at all for updating balanced_rate (whether or not we do (2)) well, in this concept: the balanced_rate formula inherently does not derive the balanced_rate_(i+1) from balanced_rate_i. Rather it's based on the ratelimit executed for the past 200ms:

          balanced_rate_(i+1) = task_ratelimit_200ms * bw_ratio

Ok, this is where it all goes funny..

So if you want completely separated feedback loops I would expect

If call it feedback loops, then it's a series of independent feedback loops of depth 1. Because each balanced_rate is a fresh estimation dependent solely on

- writeout bandwidth
- N, the number of dd tasks

in the past 200ms.

As long as a CONSTANT ratelimit (whatever value it is) is executed in the past 200ms, we can get the same balanced_rate.

balanced_rate = CONSTANT_ratelimit * write_bw / dirty_rate

The resulted balanced_rate is independent of how large the CONSTANT ratelimit is, because if we start with a doubled CONSTANT ratelimit, we'll see doubled dirty_rate and result in the same balanced_rate.

In that manner, balance_rate_(i+1) is not really depending on the value of balance_rate_(i): whatever balance_rate_(i) is, we are going to get the same balance_rate_(i+1)

Quoted 9 lines

something like:

	balance_rate_(i+1) = balance_rate_(i) * bw_ratio   ; every 200ms

The former is a complete feedback loop, expressing the new value in the old value (*) with bw_ratio as feedback parameter; if we throttled too much, the dirty_rate will have dropped and the bw_ratio will be <1 causing the balance_rate to drop increasing the dirty_rate, and vice versa.

In principle, the bw_ratio works that way. However since balance_rate_(i) is not the exact _executed_ ratelimit in balance_dirty_pages().

Quoted 2 lines

(*) which is the form I expected and why I thought your primary feedback loop looked like: rate_(i+1) = rate_(i) * pos_ratio * bw_ratio

Because the executed ratelimit was rate_(i) * pos_ratio.

Quoted 4 lines

Then when you use the balance_rate to actually throttle tasks you apply your secondary control steering the dirty page count, yielding:

task_rate = balance_rate * pos_ratio

Right. Note the above formula is not a derived one,

but an original
one that later leads to pos_ratio showing up in the calculation of balanced_rate.

Quoted 4 lines

Quoted 3 lines

and task_ratelimit_200ms happen to can be estimated from

task_ratelimit_200ms ~= balanced_rate_i * pos_ratio

Quoted 8 lines

Quoted 3 lines

We may alternatively record every task_ratelimit executed in the past 200ms and average them all to get task_ratelimit_200ms. In this way we take the "superfluous" pos_ratio out of sight :)

Right, so I'm not at all sure that makes sense, its not immediately evident that <task_ratelimit> ~= balance_rate * pos_ratio. Nor is it clear to me why your primary feedback loop uses task_ratelimit_200ms at all.

task_ratelimit is used and hence defined to be (balance_rate * pos_ratio) by balance_dirty_pages(). So this is an original formula:

task_ratelimit = balance_rate * pos_ratio

task_ratelimit_200ms is also used as an original data source in

balanced_rate = task_ratelimit_200ms * write_bw / dirty_rate

Then we try to estimate task_ratelimit_200ms by assuming all tasks have been executing the same CONSTANT ratelimit in balance_dirty_pages(). Hence we get

task_ratelimit_200ms ~= prev_balance_rate * pos_ratio

Quoted 7 lines

Quoted 4 lines

There is fundamentally no dependency between balanced_rate_(i+1) and balanced_rate_i/task_ratelimit_200ms: the balanced_rate estimation only asks for _whatever_ CONSTANT task ratelimit to be executed for 200ms, then it get the balanced rate from the dirty_rate feedback.

How can there not be a relation between balance_rate_(i+1) and balance_rate_(i) ?

In this manner: even though balance_rate_(i) is somehow used for calculating balance_rate_(i+1), the latter will evaluate to the same value given whatever balance_rate_(i).

Quoted 27 lines · Wu Fengguang

Quoted 11 lines · Peter Zijlstra

Quoted 6 lines · Wu Fengguang

- not a factor at all for updating balanced_rate (whether or not we do (2)) well, in this concept: the balanced_rate formula inherently does not derive the balanced_rate_(i+1) from balanced_rate_i. Rather it's based on the ratelimit executed for the past 200ms:

          balanced_rate_(i+1) = task_ratelimit_200ms * bw_ratio

Ok, this is where it all goes funny..

So if you want completely separated feedback loops I would expect

If call it feedback loops, then it's a series of independent feedback loops of depth 1. Because each balanced_rate is a fresh estimation dependent solely on

- writeout bandwidth
- N, the number of dd tasks

in the past 200ms.

As long as a CONSTANT ratelimit (whatever value it is) is executed in the past 200ms, we can get the same balanced_rate.

balanced_rate = CONSTANT_ratelimit * write_bw / dirty_rate

Quoted 7 lines

The resulted balanced_rate is independent of how large the CONSTANT ratelimit is, because if we start with a doubled CONSTANT ratelimit, we'll see doubled dirty_rate and result in the same balanced_rate.

In that manner, balance_rate_(i+1) is not really depending on the value of balance_rate_(i): whatever balance_rate_(i) is, we are going to get the same balance_rate_(i+1)

At best this argument says it doesn't matter what we use, making balance_rate_i an equally valid choice. However I don't buy this, your argument is broken, your CONSTANT_ratelimit breaks feedback but then you rely on the iterative form of feedback to finish your argument.

Consider:

	r_(i+1) = r_i * ratio_i

you say, r_i := C for all i, then by definition ratio_i must be 1 and you've got nothing. The only way your conclusion can be right is by allowing the proper iteration, otherwise we'll never reach the equilibrium.

Now it is true you can introduce random perturbations in r_i at any given point and still end up in equilibrium, such is the power of iterative feedback, but that doesn't say you can do away with r_i.

Quoted 10 lines

Quoted 9 lines

something like:

	balance_rate_(i+1) = balance_rate_(i) * bw_ratio   ; every 200ms

The former is a complete feedback loop, expressing the new value in the old value (*) with bw_ratio as feedback parameter; if we throttled too much, the dirty_rate will have dropped and the bw_ratio will be <1 causing the balance_rate to drop increasing the dirty_rate, and vice versa.

Quoted 3 lines

In principle, the bw_ratio works that way. However since balance_rate_(i) is not the exact _executed_ ratelimit in balance_dirty_pages().

This seems to be where your argument goes bad, the actually executed ratelimit is not important, the variance introduced by pos_ratio is purely for the benefit of the dirty page count.

It doesn't matter for the balance_rate. Without pos_ratio, the dirty page count would stay stable (ignoring all these oscillations and other fun things), and therefore it is the balance_rate we should be using for the iterative feedback.

Quoted 4 lines

Quoted 2 lines

(*) which is the form I expected and why I thought your primary feedback loop looked like: rate_(i+1) = rate_(i) * pos_ratio * bw_ratio

Because the executed ratelimit was rate_(i) * pos_ratio.

No, because iterative feedback has the form:

new = old $op $feedback-term

Quoted 6 lines

Quoted 4 lines

Then when you use the balance_rate to actually throttle tasks you apply your secondary control steering the dirty page count, yielding:

task_rate = balance_rate * pos_ratio

Right. Note the above formula is not a derived one,

Agreed, its not a derived expression but the originator of the dirty page count control.

Quoted 3 lines

but an original
one that later leads to pos_ratio showing up in the calculation of balanced_rate.

That's where I disagree :-)

Quoted 13 lines

Quoted 4 lines

Quoted 3 lines

and task_ratelimit_200ms happen to can be estimated from

task_ratelimit_200ms ~= balanced_rate_i * pos_ratio

Quoted 8 lines

Quoted 3 lines

We may alternatively record every task_ratelimit executed in the past 200ms and average them all to get task_ratelimit_200ms. In this way we take the "superfluous" pos_ratio out of sight :)

Right, so I'm not at all sure that makes sense, its not immediately evident that <task_ratelimit> ~= balance_rate * pos_ratio. Nor is it clear to me why your primary feedback loop uses task_ratelimit_200ms at all.

Quoted 8 lines

task_ratelimit is used and hence defined to be (balance_rate * pos_ratio) by balance_dirty_pages(). So this is an original formula:

task_ratelimit = balance_rate * pos_ratio

task_ratelimit_200ms is also used as an original data source in

balanced_rate = task_ratelimit_200ms * write_bw / dirty_rate

But that's exactly where you conflate the positional feedback with the throughput feedback, the effective ratelimit includes the positional feedback so that the dirty page count can move around, but that is completely orthogonal to the throughput feedback since the throughout thing would leave the dirty count constant (ideal case again).

That is, yes the iterative feedback still works because you still got your primary feedback in place, but the addition of pos_ratio in the feedback loop is a pure perturbation and doesn't matter one whit.

Quoted 4 lines

Then we try to estimate task_ratelimit_200ms by assuming all tasks have been executing the same CONSTANT ratelimit in balance_dirty_pages(). Hence we get

Quoted 1 line

task_ratelimit_200ms ~= prev_balance_rate * pos_ratio

But this just cannot be true (and, as argued above, is completely unnecessary).

Consider the case where the dirty count is way below the setpoint but the base ratelimit is pretty accurate. In that case we would start out by creating very low task ratelimits such that the dirty count can

increase. Once we match the setpoint we go back to the base ratelimit. The average over those 200ms would be <1, but since we're right at the setpoint when we do the base ratelimit feedback we pick exactly 1.

Anyway, its completely irrelevant.. :-)

Quoted 8 lines

Quoted 7 lines

Quoted 4 lines

There is fundamentally no dependency between balanced_rate_(i+1) and balanced_rate_i/task_ratelimit_200ms: the balanced_rate estimation only asks for _whatever_ CONSTANT task ratelimit to be executed for 200ms, then it get the balanced rate from the dirty_rate feedback.

How can there not be a relation between balance_rate_(i+1) and balance_rate_(i) ?

Quoted 3 lines

In this manner: even though balance_rate_(i) is somehow used for calculating balance_rate_(i+1), the latter will evaluate to the same value given whatever balance_rate_(i).

But only if you allow for the iterative feedback to work, you absolutely need that balance_rate_(i), without that its completely broken.

Quoted 6 lines · Wu Fengguang

- not a factor at all for updating balanced_rate (whether or not we do (2)) well, in this concept: the balanced_rate formula inherently does not derive the balanced_rate_(i+1) from balanced_rate_i. Rather it's based on the ratelimit executed for the past 200ms:

          balanced_rate_(i+1) = task_ratelimit_200ms * bw_ratio

Ok, this is where it all goes funny..

So if you want completely separated feedback loops I would expect something like:

	balance_rate_(i+1) = balance_rate_(i) * bw_ratio   ; every 200ms

The former is a complete feedback loop, expressing the new value in the old value (*) with bw_ratio as feedback parameter; if we throttled too much, the dirty_rate will have dropped and the bw_ratio will be <1 causing the balance_rate to drop increasing the dirty_rate, and vice versa.

(*) which is the form I expected and why I thought your primary feedback loop looked like: rate_(i+1) = rate_(i) * pos_ratio * bw_ratio

With the above balance_rate is an independent variable that tracks the write bandwidth. Now possibly you'd want a low-pass filter on that since your bw_ratio is a bit funny in the head, but that's another story.

Then when you use the balance_rate to actually throttle tasks you apply your secondary control steering the dirty page count, yielding:

task_rate = balance_rate * pos_ratio

Quoted 3 lines

and task_ratelimit_200ms happen to can be estimated from

task_ratelimit_200ms ~= balanced_rate_i * pos_ratio

Quoted 3 lines

We may alternatively record every task_ratelimit executed in the past 200ms and average them all to get task_ratelimit_200ms. In this way we take the "superfluous" pos_ratio out of sight :)

Right, so I'm not at all sure that makes sense, its not immediately evident that <task_ratelimit> ~= balance_rate * pos_ratio. Nor is it clear to me why your primary feedback loop uses task_ratelimit_200ms at all.

Old scheme is,
|
free run area | throttle area
----------------------------------------+---------------------------->
thresh^ dirty pages

New scheme is,

^ task rate limit

  |
  |            *
  |             *
  |              *
  |[free run]      *      [smooth throttled]
  |                  *
  |                     *
  |                         *
  ..bdi->dirty_ratelimit..........*
  |                               .     *
  |                               .          *
  |                               .              *
  |                               .                 *
  |                               .                    *
  +-------------------------------.-----------------------*------------>
                          setpoint^                  limit^  dirty pages

For simplicity, only the global/bdi setpoint control lines are implemented here, so the [*] curve is more straight than the ideal one showed in the above figure.

bdi_position_ratio() provides a scale factor to bdi->dirty_ratelimit, so that the resulted task rate limit can drive the dirty pages back to the global/bdi setpoints.

Signed-off-by Wu Fengguang <[email protected]>

---
 mm/page-writeback.c |  143 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 143 insertions(+)

mm/page-writeback.c +136 -0

@@ -46,6 +46,8 @@
  */
 #define BANDWIDTH_INTERVAL	max(HZ/5, 1)
 
+#define BANDWIDTH_CALC_SHIFT	10
+
 /*
  * After a CPU has dirtied this many pages, balance_dirty_pages_ratelimited
  * will look to see if it needs to force writeback or throttling.

@@ -495,6 +497,147 @@ unsigned long bdi_dirty_limit(struct bac
 	return bdi_dirty;
 }
 
+/*
+ * Dirty position control.
+ *
+ * (o) global/bdi setpoints
+ *
+ *  When the number of dirty pages go higher/lower than the setpoint, the dirty
+ *  position ratio (and hence dirty rate limit) will be decreased/increased to
+ *  bring the dirty pages back to the setpoint.
+ *
+ *                              setpoint
+ *                                 v
+ * |-------------------------------*-------------------------------|-----------|
+ * ^                               ^                               ^           ^
+ * (thresh + background_thresh)/2  thresh - thresh/DIRTY_SCOPE     thresh  limit
+ *
+ *                          bdi setpoint
+ *                                 v
+ * |-------------------------------*-------------------------------------------|
+ * ^                               ^                                           ^
+ * 0                               bdi_thresh - bdi_thresh/DIRTY_SCOPE     limit
+ *
+ * (o) pseudo code
+ *
+ *     pos_ratio = 1 << BANDWIDTH_CALC_SHIFT
+ *
+ *     if (dirty < thresh) scale up   pos_ratio
+ *     if (dirty > thresh) scale down pos_ratio
+ *
+ *     if (bdi_dirty < bdi_thresh) scale up   pos_ratio
+ *     if (bdi_dirty > bdi_thresh) scale down pos_ratio
+ *
+ * (o) global/bdi control lines
+ *
+ * Based on the number of dirty pages (the X), pos_ratio (the Y) is scaled by
+ * several control lines in turn.
+ *
+ * The control lines for the global/bdi setpoints both stretch up to @limit.
+ * If any control line drops below Y=0 before reaching @limit, an auxiliary
+ * line will be setup to connect them. The below figure illustrates the main
+ * bdi control line with an auxiliary line extending it to @limit.
+ *
+ * This allows smoothly throttling bdi_dirty down to normal if it starts high
+ * in situations like
+ * - start writing to a slow SD card and a fast disk at the same time. The SD
+ *   card's bdi_dirty may rush to 5 times higher than bdi setpoint.
+ * - the bdi dirty thresh goes down quickly due to change of JBOD workload
+ *
+ *   o
+ *     o
+ *       o                                      [o] main control line
+ *         o                                    [*] auxiliary control line
+ *           o
+ *             o
+ *               o
+ *                 o
+ *                   o
+ *                     o
+ *                       o--------------------- balance point, bw scale = 1
+ *                       | o
+ *                       |   o
+ *                       |     o
+ *                       |       o
+ *                       |         o
+ *                       |           o
+ *                       |             o------- connect point, bw scale = 1/2
+ *                       |               .*
+ *                       |                 .   *
+ *                       |                   .      *
+ *                       |                     .         *
+ *                       |                       .           *
+ *                       |                         .              *
+ *                       |                           .                 *
+ *  [--------------------+-----------------------------.--------------------*]
+ *  0                 bdi setpoint                 bdi origin            limit
+ *
+ * The bdi control line: if (origin < limit), an auxiliary control line (*)
+ * will be setup to extend the main control line (o) to @limit.
+ */
+static unsigned long bdi_position_ratio(struct backing_dev_info *bdi,
+					unsigned long thresh,
+					unsigned long dirty,
+					unsigned long bdi_thresh,
+					unsigned long bdi_dirty)
+{
+	unsigned long limit = hard_dirty_limit(thresh);
+	unsigned long origin;
+	unsigned long goal;
+	unsigned long long span;
+	unsigned long long pos_ratio;	/* for scaling up/down the rate limit */
+
+	if (unlikely(dirty >= limit))
+		return 0;
+
+	/*
+	 * global setpoint
+	 */
+	goal = thresh - thresh / DIRTY_SCOPE;
+	origin = 4 * thresh;
+
+	if (unlikely(origin < limit && dirty > (goal + origin) / 2)) {
+		origin = limit;			/* auxiliary control line */
+		goal = (goal + origin) / 2;
+		pos_ratio >>= 1;
+	}
+	pos_ratio = origin - dirty;
+	pos_ratio <<= BANDWIDTH_CALC_SHIFT;
+	do_div(pos_ratio, origin - goal + 1);
+
+	/*
+	 * bdi setpoint
+	 */
+	if (unlikely(bdi_thresh > thresh))
+		bdi_thresh = thresh;
+	goal = bdi_thresh - bdi_thresh / DIRTY_SCOPE;
+	/*
+	 * Use span=(4*bw) in single disk case and transit to bdi_thresh in
+	 * JBOD case.  For JBOD, bdi_thresh could fluctuate up to its own size.
+	 * Otherwise the bdi write bandwidth is good for limiting the floating
+	 * area, which makes the bdi control line a good backup when the global
+	 * control line is too flat/weak in large memory systems.
+	 */
+	span = (u64) bdi_thresh * (thresh - bdi_thresh) +
+		(4 * bdi->avg_write_bandwidth) * bdi_thresh;
+	do_div(span, thresh + 1);
+	origin = goal + 2 * span;
+
+	if (unlikely(bdi_dirty > goal + span)) {
+		if (bdi_dirty > limit)
+			return 0;
+		if (origin < limit) {
+			origin = limit;		/* auxiliary control line */
+			goal += span;
+			pos_ratio >>= 1;
+		}

Quoted 4 lines

bdi_position_ratio() provides a scale factor to bdi->dirty_ratelimit, so that the resulted task rate limit can drive the dirty pages back to the global/bdi setpoints.

IMHO, "position_ratio" is not necessarily very intutive. Can there be a better name? Based on your slides, it is scaling factor applied to task rate limit depending on how well we are doing in terms of meeting our goal of dirty limit. Will "dirty_rate_scale_factor" or something like that make sense and be little more intutive?

From (1) and (2), we get equality

It's all about bdi->dirty_ratelimit, which aims to be (write_bw / N) when there are N dd tasks.

On write() syscall, use bdi->dirty_ratelimit
============================================

    balance_dirty_pages(pages_dirtied)
    {
        pos_bw = bdi->dirty_ratelimit * bdi_position_ratio();
        pause = pages_dirtied / pos_bw;
        sleep(pause);
    }

On every 200ms, update bdi->dirty_ratelimit
===========================================

    bdi_update_dirty_ratelimit()
    {
        bw = bdi->dirty_ratelimit;
        ref_bw = bw * bdi_position_ratio() * write_bw / dirty_bw;
        if (dirty pages unbalanced)
             bdi->dirty_ratelimit = (bw * 3 + ref_bw) / 4;
    }

Estimation of balanced bdi->dirty_ratelimit
===========================================

When started N dd, throttle each dd at

task_ratelimit = pos_bw (any non-zero initial value is OK)

After 200ms, we got

dirty_bw = # of pages dirtied by app / 200ms write_bw = # of pages written to disk / 200ms

For aggressive dirtiers, the equality holds

         dirty_bw == N * task_ratelimit
                  == N * pos_bw                      	(1)

The balanced throttle bandwidth can be estimated by

ref_bw = pos_bw * write_bw / dirty_bw (2)

Quoted 1 line

From (1) and (2), we get equality

         ref_bw == write_bw / N                      	(3)

If the N dd's are all throttled at ref_bw, the dirty/writeback rates will match. So ref_bw is the balanced dirty rate.

Quoted 45 lines · Wu Fengguang

It's all about bdi->dirty_ratelimit, which aims to be (write_bw / N) when there are N dd tasks.

On write() syscall, use bdi->dirty_ratelimit
============================================

    balance_dirty_pages(pages_dirtied)
    {
        pos_bw = bdi->dirty_ratelimit * bdi_position_ratio();
        pause = pages_dirtied / pos_bw;
        sleep(pause);
    }

On every 200ms, update bdi->dirty_ratelimit
===========================================

    bdi_update_dirty_ratelimit()
    {
        bw = bdi->dirty_ratelimit;
        ref_bw = bw * bdi_position_ratio() * write_bw / dirty_bw;
        if (dirty pages unbalanced)
             bdi->dirty_ratelimit = (bw * 3 + ref_bw) / 4;
    }

Estimation of balanced bdi->dirty_ratelimit
===========================================

When started N dd, throttle each dd at

task_ratelimit = pos_bw (any non-zero initial value is OK)

After 200ms, we got

dirty_bw = # of pages dirtied by app / 200ms write_bw = # of pages written to disk / 200ms

For aggressive dirtiers, the equality holds

         dirty_bw == N * task_ratelimit
                  == N * pos_bw                      	(1)

The balanced throttle bandwidth can be estimated by

ref_bw = pos_bw * write_bw / dirty_bw (2)

Quoted 6 lines

Quoted 1 line

From (1) and (2), we get equality

         ref_bw == write_bw / N                      	(3)

If the N dd's are all throttled at ref_bw, the dirty/writeback rates will match. So ref_bw is the balanced dirty rate.

Hi Fengguang,

So how much work it is to extend all this to handle the case of cgroups?

IOW, I would imagine that you shall have to keep track of per cgroup/per bdi state of many of the variables. For example, write_bw will become per cgroup/per bdi entity instead of per bdi entity only. Same should be true for position ratio, dirty_bw etc?

I am assuming that if some cgroup is low weight on end device, then WRITE bandwidth of that cgroup should go down and that should be accounted for at per bdi state and task throttling should happen accordingly so that a lower weight cgroup tasks get throttled more as compared to higher weight cgroup tasks?

Estimation of balanced bdi->dirty_ratelimit
===========================================

When started N dd, throttle each dd at

task_ratelimit = pos_bw (any non-zero initial value is OK)

After 200ms, we got

dirty_bw = # of pages dirtied by app / 200ms write_bw = # of pages written to disk / 200ms

For aggressive dirtiers, the equality holds

         dirty_bw == N * task_ratelimit
                  == N * pos_bw                         (1)

The balanced throttle bandwidth can be estimated by

ref_bw = pos_bw * write_bw / dirty_bw (2)

Quoted 1 line

From (1) and (2), we get equality

         ref_bw == write_bw / N                         (3)

If the N dd's are all throttled at ref_bw, the dirty/writeback rates will match. So ref_bw is the balanced dirty rate.

In practice, the ref_bw calculated by (2) may fluctuate and have estimation errors. So the bdi->dirty_ratelimit update policy is to follow it only when both pos_bw and ref_bw point to the same direction (indicating not only the dirty position has deviated from the global/bdi setpoints, but also it's still departing away).

Quoted 4 lines · Wu Fengguang

Estimation of balanced bdi->dirty_ratelimit
===========================================

Quoted 3 lines

When started N dd, throttle each dd at

task_ratelimit = pos_bw (any non-zero initial value is OK)

This is (0), since it makes (1). But it fails to explain what the difference is between task_ratelimit and pos_bw (and why positional bandwidth is a good name).

Quoted 4 lines

After 200ms, we got

dirty_bw = # of pages dirtied by app / 200ms write_bw = # of pages written to disk / 200ms

Right, so that I get. And our premise for the whole work is to delay applications so that we match the dirty_bw to the write_bw, right?

Quoted 4 lines

For aggressive dirtiers, the equality holds

         dirty_bw == N * task_ratelimit
                  == N * pos_bw                         (1)

So dirty_bw is in pages/s, so task_ratelimit should also be in pages/s, since N is a unit-less number.

What does task_ratelimit in pages/s mean? Since we make the tasks sleep the only thing we can make from this is a measure of pages. So I expect (in a later patch) we compute the sleep time on the amount of pages we want written out, using this ratelimit measure, right?

Quoted 3 lines

The balanced throttle bandwidth can be estimated by

ref_bw = pos_bw * write_bw / dirty_bw (2)

Here you introduce reference bandwidth, what does it mean and what is its relation to positional bandwidth. Going by the equation, we got (pages/s * pages/s) / (pages/s) so we indeed have a bandwidth unit.

write_bw/dirty_bw is the ration between output and input of dirty pages, but what is pos_bw and what does that make ref_bw?

Quoted 3 lines

Quoted 1 line

From (1) and (2), we get equality

         ref_bw == write_bw / N                         (3)

Somehow this seems like the primary postulate, yet you present it like a derivation. The whole purpose of your control system is to provide this fairness between processes, therefore I would expect you start out with this postulate and reason therefrom.

Quoted 2 lines

If the N dd's are all throttled at ref_bw, the dirty/writeback rates will match. So ref_bw is the balanced dirty rate.

Which does lead to the question why its not called that instead ;-)

Quoted 5 lines

In practice, the ref_bw calculated by (2) may fluctuate and have estimation errors. So the bdi->dirty_ratelimit update policy is to follow it only when both pos_bw and ref_bw point to the same direction (indicating not only the dirty position has deviated from the global/bdi setpoints, but also it's still departing away).

Which is where you introduce the need for pos_bw, yet you have not yet explained its meaning. In this explanation you allude to it being the speed (first time derivative) of the deviation from the setpoint.

The set point's measure is in pages, so the measure of its first time derivative would indeed be pages/s, just like bandwidth, but calling it a bandwidth seems highly confusing indeed.

I would also like a few more words on your update condition, why did you pick those, and what are the full ramifications of them.

Also missing in this story is your pos_ratio thing, it is used in the code, but there is no explanation on how it ties in with the above things.

You seem very skilled in control systems (your earlier read-ahead work was also a very complex system),

but the explanations of your systems are highly confusing.

Can you go back to the roots and explain how you constructed your model and why you did so? (without using graphs please)

PS. I'm not criticizing your work, the results are impressive (as always), but I find it very hard to understand.

PPS. If it would help, feel free to refer me to educational material on control system theory, either online or in books.

: When started N dd, we would like to throttle each dd at :
: balanced_rate == write_bw / N (1)
:
: We don't know N beforehand, but still can estimate balanced_rate : within 200ms.
:
: Start by throttling each dd task at rate
:
: task_ratelimit = task_ratelimit_0 (2)
: (any non-zero initial value is OK)
:
: After 200ms, we got
:
: dirty_rate = # of pages dirtied by all dd's / 200ms
: write_bw = # of pages written to the disk / 200ms
:
: For the aggressive dd dirtiers, the equality holds
:
: dirty_rate == N * task_rate
: == N * task_ratelimit
: == N * task_ratelimit_0 (3)
: Or
: task_ratelimit_0 = dirty_rate / N (4)
:

: So the balanced throttle bandwidth can be estimated by :
: balanced_rate = task_ratelimit_0 * (write_bw / dirty_rate) (5)
:
: Because with (4) and (5) we can get the desired equality (1):
:
: balanced_rate == (dirty_rate / N) * (write_bw / dirty_rate)
: == write_bw / N

So if the dirty pages are ABOVE the setpoints, we throttle each task a bit more HEAVY than balanced_rate, so that the dirty pages are created less fast than they are cleaned, thus DROP to the setpoints (and the reverse). With that positional adjustment, the formula is transformed from

task_ratelimit = balanced_rate

to

task_ratelimit = balanced_rate * pos_ratio

In terms of the negative feedback control theory, the bdi_position_ratio() function (control lines) can be expressed as

1) f(setpoint) = 1.0
2) df/dt < 0

3) optionally, abs(df/dt) should be large on large errors (= dirty - setpoint) in order to cancel the errors fast, and be smaller when dirty pages get closer to the setpoints in order to avoid overshooting.

How about something like the below, it still needs some more work, but its more or less complete in that is now explains both controls in one story. The actual update bit is still missing.

---

balance_dirty_pages() needs to throttle tasks dirtying pages such that the total amount of dirty pages stays below the specified dirty limit in order to avoid memory deadlocks. Furthermore we desire fairness in that tasks get throttled proportionally to the amount of pages they dirty.

IOW we want to throttle tasks such that we match the dirty rate to the writeout bandwidth, this yields a stable amount of dirty pages:

ratelimit = writeout_bandwidth

The fairness requirements gives us:

task_ratelimit = write_bandwidth / N

Quoted 25 lines

: When started N dd, we would like to throttle each dd at :
: balanced_rate == write_bw / N (1)
:
: We don't know N beforehand, but still can estimate balanced_rate : within 200ms.
:
: Start by throttling each dd task at rate
:
: task_ratelimit = task_ratelimit_0 (2)
: (any non-zero initial value is OK)
:
: After 200ms, we got
:
: dirty_rate = # of pages dirtied by all dd's / 200ms
: write_bw = # of pages written to the disk / 200ms
:
: For the aggressive dd dirtiers, the equality holds
:
: dirty_rate == N * task_rate
: == N * task_ratelimit
: == N * task_ratelimit_0 (3)
: Or
: task_ratelimit_0 = dirty_rate / N (4)
:

Quoted 8 lines

: So the balanced throttle bandwidth can be estimated by :
: balanced_rate = task_ratelimit_0 * (write_bw / dirty_rate) (5)
:
: Because with (4) and (5) we can get the desired equality (1):
:
: balanced_rate == (dirty_rate / N) * (write_bw / dirty_rate)
: == write_bw / N

Then using the balance_rate we can compute task pause times like:

	task_pause = task->nr_dirtied / task_ratelimit

[ however all that still misses the primary feedback of:

task_ratelimit_(i+1) = task_ratelimit_i * (write_bw / dirty_rate)

there's still some confusion in the above due to task_ratelimit and balanced_rate.
]

However, while the above gives us means of matching the dirty rate to the writeout bandwidth, it at best provides us with a stable dirty page count (assuming a static system). In order to control the dirty page count such that it is high enough to provide performance, but does not exceed the specified limit we need another control.

Quoted 21 lines

So if the dirty pages are ABOVE the setpoints, we throttle each task a bit more HEAVY than balanced_rate, so that the dirty pages are created less fast than they are cleaned, thus DROP to the setpoints (and the reverse). With that positional adjustment, the formula is transformed from

task_ratelimit = balanced_rate

to

task_ratelimit = balanced_rate * pos_ratio

In terms of the negative feedback control theory, the bdi_position_ratio() function (control lines) can be expressed as

1) f(setpoint) = 1.0
2) df/dt < 0

3) optionally, abs(df/dt) should be large on large errors (= dirty - setpoint) in order to cancel the errors fast, and be smaller when dirty pages get closer to the setpoints in order to avoid overshooting.