Hello, On Wed, Feb 17, 2016 at 10:02:00AM +0100, Paolo Valente wrote: > your first statement “bfq is using bandwidth as the virtual time" is > not very clear to me. In contrast, after that you raise a clear, Another way to put that would be "bfq is using bandwidth as the measure of IO resource provided by a device and to be distributed". ... > Bandwidth fluctuation is one of the key issues addressed in the very > definition of BFQ (more precisely in the definition of the engine of > BFQ, introduced in this patch). In particular, BFQ schedules queues > so as to approximate an ideal service in which every queue receives, > over any time interval, its share of the bandwidth, regardless of > the actual value of the bandwidth, and even if the bandwidth > fluctuates. IOW, in the ideal service approximated by BFQ, if the So, this is a problem. For illustration, let's ignore penalization of seeky workload and assume a hard drive which can do 100MB/s for a fully sequential workload and 1MB/s for 4k random one. In other words, a sequential workload doing 100 MB/s is consuming 100% of available IO resource and so does 4k random workload doing 1MB/s. Let's say there are two sequential workload. If the two workloads are interleaved, the total bandwidth achieved would be lower than 100MB/s with the amount of drop dependent on how often the two workloads are switched. Given big enough scheduling stride, the total won't be too much lower and assuming the same weight each should be getting bandwidth a bit lower than 50MB/s. If we do the same for two random workloads, the story is the same. Each should be getting close to 512KB/s of bandwidth. Now let's put one sequential workload and one random workload on the device. What *should* happen is clear - the sequential workload should be achieving close to 50MB/s while the random one 512KB/s so that each is still consuming the equal proportion of the available IO resource on the device. For devices with low concurrency such as disks, this measure of IO resources can be almost directly represented as how long each workload occupies the device. If we use the proportion of bandwidth a workload is getting as the measure of IO resource consumed, the picture becomes very different and, I think, lost. The amount of bandwidth available is heavily dependent on what mix of IOs the device is getting which would then feed back into how much proportion of IO resource each workload forming a feedback loop. More importantly, random workload would be consuming far more IO resource than it's entitled to. I assume that is why bfq currently would need special punishment of seeky workloads. In the end what that coefficient does is trying to translate bandwidth consumption to IO time consumption in an ad-hoc and inaccruate way. > bandwidth fluctuates during a given time interval, then, in every > sub-interval during which the bandwidth is constant (possibly an > infinitesimal time interval), each queue receives a fraction of the > total bandwidth equal to the ratio between its weight and the sum of > the weights of the active queues. BFQ is an optimal scheduler in > that it guarantees the minimum possible deviation, for a > slice-by-slice service scheme, with respect to the ideal > service. Finally, BFQ actually provides these fairness guarantees > only to queues whose I/O pattern yields a reasonably high > throughput. This fact has to do with the issue you raise. I don't think it's fair at all. It distributes undue amount of IO resources to seeky workloads and then tries to compensate for it by punishing them with a special coefficient. The devices bfq is targeting primarily are the ones where whether the workload is seeky or not results in multiple orders of magnitude difference in terms of available IO bandwidth. It simply doesn't make sense to use bandwidth as the measurement for available IO resources. That'd be worse than calcualting computation resource consumed as the number of instructions executed regardless of whether the instruction is a simple register to register move or double precision floating point division, which we don't do for obvious reasons. > The virtual time is the key concept used to achieve the above > optimal fairness guarantees. To show how intuitively, let me restate > the above guarantees in terms of "amount of service”, i.e., of > number of sectors read/written: BFQ guarantees that every active > queue receives, over any time interval, an amount of service equal > to the total amount of service provided by the system, multiplied by > the share of the bandwidth for the queue (apart from the > above-mentioned minimum, unavoidable deviation). Informally, this > implies that the amount of service received by each active queue, > during any given time interval, is proportional to the weight of the > queue. As a consequence, the normalized service received by every > active queue, i.e., the amount of service divided by the weight of > the queue, grows at the same rate. In BFQ, every queue is associated > with a virtual time, equal exactly to this normalized service. The > goal of BFQ is then to equalize queues’ virtual times (using also a > further global quantity, called system virtual time). To achieve > this goal, BFQ does not schedule time slices, but budgets, measured > in amount of service. I think I understand what you're saying. What I'm trying to say is the unit bfq is currently using for budgeting is almost completely bogus. It's the wrong unit. The "amount of service" a group receives is fundamentally "the amount of time" it occupies the target device. If that can be approximated by bandwidth as in network interfaces, using bandwidth as the unit is fine. However, that isn't the case at all for disks. > Hoping that we are now in sync on virtual times, I will try to > discuss your comment on why not to schedule time (slices) in the > first place. The fact that BFQ does not schedule time slices with > the same scheduling policy as CFQ, but budgets with an optimally > fair policy, provides the following main practical benefits: > > 1) It allows BFQ to distribute bandwidth as desired among processes > or groups of processes, regardless of: device parameters, bandwidth > fluctuation, overall workload composition (BFQ gives up this > bandwidth-fair policy only if this would cause a throughput drop, as > discussed in the second part of this email). It is impossible for a > time-based scheduling policy to provide such a service guarantee on > a device with a fluctuating bandwidth. In fact, a process achieving, > during its allotted time slice, a lower bandwidth than other luckier > processes, will just receive less service when it has the > opportunity to use the device. As a consequence, an unlucky process > may easily receive less bandwidth than another process with the same > weight, or even of a process with a lower weight. On HDDs, this > trivially happens to processes reading/writing on the inner zones of > the disk. On SSDs, the variability is due to more complex > causes. This problem has been one of the main motivations for the > definition of BFQ. I think you're confused about what IO resource is. Let's say there is one swing and two kids. When we say the two kids get to share the swing equally, it means that each kid would get the same amount of time on the swing, not the same number of strokes or the length of circumference traveled. A kid who gets 30% of the swing gets 30% time share of the swing regardless of who else the kid is sharing the swing with. This is exactly the same situation. > 2) The above bandwidth fairness of a budget-based policy is key for > providing sound low-latency guarantees to soft real-time > applications, such as audio or video players. In fact, a time-based > policy is nasty with an unlucky soft real-time process whose I/O > happens to yield, in the time slice during which the I/O requests of > the process are served, a lower throughput than the peak rate. The > reason is that, first, a lower throughput makes it more difficult > for the process to reach its target bandwidth. Secondly, the > scheduling policy does not tend to balance this unlucky situation at > all: the time slice for the process is basically the same as for any > other process with the same weight. This is one of the reasons why, > in our experiments, BFQ constantly guarantees to soft real-time > applications a much lower latency than CFQ. I don't think this is because of any fundamental properties of bandwidth being used as the unit but more that the algorithm favors low bandwidth consumers and the "soft real-time" ones don't get punished as seeky. It seems more a product of distortion in distribution scheme, which btw is fine if it serves a practical purpose, but this should be achievable in a different way too. > 3) For the same reasons as in the above case, a budget-based policy > is also key for providing sound high-responsiveness guarantees, > i.e., for guaranteeing that, even in the presence of heavy > background workloads, applications are started quickly, and in > general, that interactive tasks are completed promptly. Again, this > is one of the reasons why BFQ provides responsiveness guarantees not > comparable with CFQ. I probably am missing something but I don't quite get how the above property is a fundamental property of using bandwidth as the unit. If it is, it'd be only because the unit distorts the actual IO resource distribution in a favorable way. However, because the unit is distorted to begin with, bfq has to apply seeky penalty to correct it. I'd be far happier with opt-in correction (identifying the useful distortions and implementing them) than the current opt-out scheme where the fundamental unit is wrong. > For all the three cases above, and concerning unlucky applications, > i.e., applications whose I/O patterns yield a lower throughput than No, that's not an unlucky application. That's an expensive application in terms of IO. It's the slow swinging kid. > other applications, I think it is important to stress that the > unfairness, high-latency or low-responsiveness problems experienced > by these applications with a time-based policy are not transient: in > the presence of a background workload, these application are > mistreated in the same way *every time* their I/O is replayed. I think you're getting it backwards. Let's go back to the swing example. If you think allocating per-stroke or per-circumference-traveled is a valid strategy when different kids can show multiple orders of magnitude differences on those scales, please convince me why. > Unfortunately, there are applications for which BFQ cannot provide > the above desirable service guarantees: the applications whose I/O > patterns may kill the throughput if they are guaranteed the service > fairness in item 1 (they may also cause other applications to suffer > from a high latency). In this respect, if I have well understood the > “punish-seeky-queues” case you have highlighted, you refer to the > case where a process does not finish its budget within a reasonable > time interval. In this case, the process is de-scheduled, and > treated as if it has used all its budget. As you have noted, this is > a switch from a fair budget-based policy to a fair time-based > policy, to prevent I/O patterns yielding a very low throughput from > causing throughput and latency problems. This simple switch becomes > more complex with the refinements introduced by the following > patches, which take into account also whether the application is > soft real-time or interactive, and, if so, let the trade-off become > more favorable to the application, even if its I/O is not > throughput-friendly. I hope my point is clear by now. The above is correcting for the fundamental flaws in the unit used for distribution. It's mapping bandwidth to time in an ad-hoc and mostly arbitrary way. In the same cgroup, fairness can take the second seat to overall bandwidth or practical characteristics. That's completely fine. What bothers me are 1. The direction is the other way around. It starts with a flawed fundamental unit and then opts out "really bad ones". I think the better way would be using the correct resource unit as the basis and opt in specific distortions to achieve certain practical advantages. The later patches add specific opt-in behaviors anyway. 2. For IO control, the practical distortions should be much lower and the distribution should be based on the actual IO resource. Maybe I'm missing out something big. If so, please hammer it into me. Thanks. -- tejun -- To unsubscribe from this list: send the line "unsubscribe linux-block" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
