Provide a mechanism to monitor the consumption rate of a resource.
More...
Namespaces |
| namespace | balb |
Detailed Description
- Outline
-
-
- Purpose:
- Provide a mechanism to monitor the consumption rate of a resource.
-
- Classes:
-
- See also:
- Component balb_ratelimiter
-
- Description:
- This component provides a mechanism,
balb::LeakyBucket, that implements a leaky bucket algorithm that allows clients to monitor whether a resource is being consumed at a particular rate.
- The name of this mechanism, leaky bucket, derives from an analogy of pouring water into a bucket with a hole at the bottom. The maximum rate at which water will drain out the bucket depends on the size of the hole, and not on the rate at which water is poured into the bucket. If more water is being poured into the bucket than being drained, the bucket will eventually overflow. If the person pouring water into a leaky bucket ensures the bucket doesn't overflow, then the average rate they pour water will, over time, be limited by the rate at which water flows out of the bucket. By analogy, a leaky bucket provides a means to limit the rate of consumption of some resource (water poured into the bucket) to a configured rate (the size of the hole in the bucket).
- The behavior of a leaky bucket is determined by two properties: the capacity and the drain rate. The drain rate, measured in
units/s, is the rate at which the resource is drained. The capacity, measured in units, is the maximum amount of the resource that the leaky bucket can hold before it overflows. unit is a generic unit of measurement (e.g., bytes, number of messages, packets, liters, clock cycles, etc.). Note that the drain rate determines average rate of resource consumption, while the capacity restricts the time period over which the average actual rate of resource consumption approaches the drain rate.
-
- Adding Units:
- Units can be added to a leaky bucket by either submitting them or reserving them. Submitted units are removed from a leaky bucket at the drain rate, while reserved units remain unchanged until they are later either cancelled (removed from the leaky bucket) or submitted.
-
- Submitting Units:
- Units can be submitted to a leaky bucket by invoking the
submit method, and should be added only after the resource had been consumed.
- Figure 1 illustrates a typical workflow for submitting units to a leaky bucket.
Fig. 1: Capacity = 5 units, Rate = 1 unit / second
Submit 5 Submit 2
7| | 7| | 7| | 7| |
6| | 6| | 6| | 6| |
c--5|~~~~~| c--5|-----| c--5|-----| c--5|-----|
4|~~~~~| 4| | 4| | 4| |
3|~~~~~| 3| | 3|~~~~~| 3| |
2|~~~~~| 2| | 2|~~~~~| 2| |
1|~~~~~| 1|~~~~~| 1|~~~~~| 1| |
+-- --+ +-- --+ +-- --+ +-- --+
Time: t0 t0 + 4s t0 + 4s t0 + 10s
c = 5 units and a drain rate of d = 1 units/s. At t0, we submit 5 units to the leaky bucket, bringing the total number of units held up to 5. At 't0 + 4s', 4 units have been drained from the leaky bucket, bringing the number of units held down to 1. Finally, at t0 + 10s, all units have been drained from the leaky bucket, making it empty.
- Unlike a real-life water bucket, units submitted to a leaky bucket don't spillover after its capacity has been exceeded, instead the leaky bucket may hold a number of units beyond its capacity, as examined in Figure 2 below., these units are still contained in the leaky bucket.
- Figure 2 illustrates what happens if a leaky bucket exceeds its capacity. This scenario is the same as that in Figure 1, but at time
t0 + 4s, we submit 6 units instead of 2. Fig. 2: Capacity = 5 units, Rate = 1 unit / second
Submit 5 Submit 6
7| | 7| | 7|~~~~~| 7| |
6| | 6| | 6|~~~~~| 6| |
c--5|~~~~~| c--5|-----| c--5|~~~~~| c--5|-----|
4|~~~~~| 4| | 4|~~~~~| 4| |
3|~~~~~| 3| | 3|~~~~~| 3| |
2|~~~~~| 2| | 2|~~~~~| 2| |
1|~~~~~| 1|~~~~~| 1|~~~~~| 1|~~~~~|
+-- --+ +-- --+ +-- --+ +-- --+
Time: t0 t0 + 4s t0 + 4s t0 + 10s
t0 + 4s, when the number of units held by the leaky bucket is 1, we submit 6 more units. This brings the number of units held to 7, which exceeds the capacity of the leaky bucket. At t0 + 10s, 6 units had been drained from the leaky bucket bring the number of units held down to 1.
-
- Reserving Units:
- Units can be reserved for a leaky bucket using the
reserve method, and they may be later canceled using the cancelReserved method or submitted using the submitReserved method. Unlike submitted units, reserved units do not drain from the leaky bucket; like submitted units, reserved units count toward the total number of units for the purposes of determining whether a leaky bucket has exceeded its capacity. Reserving units effectively decreases the capacity of a leaky bucket. Therefore, the time interval between reserving units and submitting or canceling the reservation should be kept as short as possible. For a practical example of using reserved units, please see balb_reservationguard.
- Figure 3 illustrate an example of how reserving units works in a leaky bucket.
Fig. 3: Capacity = 5 units, Rate = 1 unit / second
Reserve 4 Submit 3 Cancel 1
from reserve from reserve
7| | 7| | 7| | 7| | 7| |
6| | 6| | 6| | 6| | 6| |
c--5|-----| c--5|-----| c--5|-----| c--5|-----| c--5|-----|
4|#####| 4|#####| 4|~~~~~| 4| | 4| |
3|#####| 3|#####| 3|~~~~~| 3| | 3| |
2|#####| 2|#####| 2|~~~~~| 2| | 2| |
1|#####| 1|#####| 1|#####| 1|#####| 1| |
+-- --+ +-- --+ +-- --+ +-- --+ +-- --+
Time: t0 t0 + 5s t0 + 6s t0 + 9s t0 + 10s
c = 5 units and a drain rate of d = 1 units/s. At t0 we reserve 4 units. At 't0 + 5s', we observe that none of the reserved units are drained from the leaky bucket. At t0 + 6s, we submit 3 of the previously reserved units, which brings the number of reserved units down to 1 and the number of units held up to 3. At t0 + 9s, we observe that all but the remaining reserved unit have been drained from the bucket. Finally, at t0 + 10s, we cancel the remaining reserved unit.
-
- Monitoring Resource Usage:
- The recommended usage of a leaky bucket is to first check whether 1 unit can be added without causing the leaky bucket to overflow, and if so, consume the desired amount of the resource. Afterwards, submit the amount of consumed resource to the leaky bucket.
-
- Checking for Overflow:
- A leaky bucket can be queried whether submitting a 1 more unit would cause it to overflow via the
wouldOverflow method. This method facilitates the recommended usage of a leak bucket: check whether 1 more unit can be added without causing the leaky bucket to overflow, and if so, consume the desired amount of the resource (which may be more than 1). Compared to the alternative -- checking whether the desired amount can be submitted without overflow -- this recommended usage may allow a limited spike in the rate of actual consumption when the leaky bucket is empty (which is often acceptable) but is able to sustain a long term average that is actually closer to the drain rate.
-
- Modeling a Network Connection:
- The primary use case of leaky bucket is limiting the rate at which data is written on a network. In this use case, the drain rate of the bucket corresponds to the ideal maximum transmission rate that the client wishes to enforce on their outgoing connection. Clients may choose to provide a value related to the physical limitations of their network or any other arbitrary limit. The function of a leaky bucket's capacity is to limit the time period over which the average actual transmission rate may exceed the configured drain rate of the leaky bucket (see
Approximations section and Sliding Time-Window section).
-
- Approximations:
- Leaky bucket is modeled on a water bucket with a hole, but as a leaky bucket does not manage any resources, there are several approximations to this model:
-
Units are submitted instantaneously to the leaky bucket, whereas the consumption of a resource occurs over time at a rate that depends on the nature and speed of the resource.
-
Leaky bucket simulates the consumption of a resource with a specified fixed drain rate, but the resource is actually consumed at different rates over time. This approximation still guarantees that the actual consumption rate does not exceed the specified drain rate when amortized over some configured period of time (determined by the capacity and the drain rate of the bucket), but does not prevent the consumption rate from spiking above the drain rate for shorter periods of time (see 'Sliding Time-Window' section).
-
- Sliding Time-Window:
- One of the properties of the resource pattern created by using a leaky bucket is an approximation of a sliding time window over which the average consumption rate is guaranteed to be less than the drain rate. This time period can be calculated using the leaky bucket's capacity and drain rate, which can be conveniently performed using the
calculateTimeWindow class method.
-
- Time Synchronization:
- Leaky bucket does not utilize an internal timer, so timing must be handled manually. Clients can specify an initial time interval for the leaky bucket at construction or using the
reset method. Whenever the number of units in a leaky bucket needs to be updated, clients must invoke the updateState method specifying the current time interval. Since leaky bucket cares only about the elapsed time (not absolute time), the specified time intervals may be relative to any arbitrary time origin, though all of them must refer to the same origin. For the sake of consistency, clients are encouraged to use the unix epoch time (such as the values returned by bdlt::CurrentTime::now).
-
- Usage:
- This section illustrates the intended use of this component.
-
- Example 1: Controlling Network Traffic Generation:
- In some systems, data is processed faster than they are consumed by I/O interfaces. This could lead to data loss due to the overflowing of the buffers where data is queued before being processed. In other systems, generic resources are shared, and their consumption might need to be managed in order to guarantee quality-of-service (QOS).
- Suppose we have a network interface capable of transferring at a rate of 1024 byte/s and an application wants to transmit 5 KB (5120 bytes) of data over that network in 20 different 256-bytes data chunks. We want to send data over this interface and want to ensure the transmission uses on average less than 50% of the available bandwidth, or 512 byte/s. In this way, other clients can still reasonably send and receive data using the same network interface.
- Further suppose that we have a function,
sendData, that transmits a specified data buffer over that network interface: bool sendData(const char *buffer, size_t dataSize);
unit, the unit of measurement for leaky bucket, corresponds to byte in this example: Then, we define a data buffer to be sent, the size of each data chunk, and the total size of the data to transmit: Notice that, for the sake of brevity, we elide the loading of buffer with the data to be sent.
- Now, we send the chunks of data using a loop. For each iteration, we check whether submitting another byte would cause the leaky bucket to overflow. If not, we send an additional chunk of data and submit the number of bytes sent to the leaky bucket. Note that
submit is invoked only after the data has been sent. char *data = buffer;
while (dataSent < totalSize) {
now = bdlt::CurrentTime::now();
if (!bucket.wouldOverflow(now)) {
if (true == sendData(data, chunkSize)) {
data += chunkSize;
bucket.submit(chunkSize);
dataSent += chunkSize;
}
}
calculateTimeToSubmit method: Notice that we wait by putting the thread into a sleep state instead of using busy-waiting to better optimize for multi-threaded applications.
