Storage

Prior to dmclock(WPQ):

The main operations in the ceph cluster are client I/O, background recovery, and background operations(scrubbing, backfilling, trimming, PG deletion..etc). Before the 6.1 CEPH  version, the requests are scheduled by using the WPQ (Weighted Priority Queue) algorithm.WPQ prioritizes the tasks based on the assigned weights. Requests with higher weights are served before those with lower weights.

For example:

                                                                                       Table-1                             

The final execution order will be:  Trimming(5)->I/O(3)->PG deletion(2)->Recovery(1)

For any operation within the cluster, the system dynamically allocates and manages CPU, memory, network, and storage I/O resources. In WPQ, The system dynamically adjusts resource allocation (CPU, memory, network, and storage I/O) based on these weights.

To illustrate this let's take an example-

                                                                           Table-2

The throughput allocated to requests is in proportion to their weights.

               Throughput allocation ∝  Weight   

Assume that the  maximum throughput in the device is  1200 IOPS

The IOPS allocation is based on the formula -  T × (wi/∑wi)  where T = Total throughput w=Weight                    

So, for the recovery, the allocated throughput is =  1200 X ( 1/6) = 200 IOPS

                                    Similarly for PG deletion      =  1200 X ( 2/6) = 400 IOPS

                                                   for  I/O                     =  1200 X ( 3/6) = 600 IOPS

The minimum requirement for Recovery operation is 250, but 200 IOPS are allocated. Similarly, for the I/O operations, the minimum requirement is 1000, but 600 are allocated. In both scenarios, the resources are less than what is required. For PG deletion, the minimum requirement is 250, and allocated resources are 400 which is more than the required resources.

Drawbacks of WPQ:

        WPQ is not inherently a fairness algorithm. While it does provide a mechanism for prioritizing tasks based on weight.which means higher-weighted tasks will always receive more resources or attention than lower-weighted ones. This can lead to unfairness if low-priority tasks are consistently starved of resources.WPQ does not ensure that all tasks get an equal or proportional share of resources. 

mclock

Reservation is a guaranteed minimum resource allocation to an entity. It represents the amount of the resource the entity is guaranteed to receive, regardless of the overall system load or the demands of other entities. Even if the system is under heavy contention, the entity will still receive its reserved minimum. 

 A Limit is a defined maximum allocation of a resource that a service is permitted to consume. Reservations and limits are expressed in absolute units of the resource (e.g., bandwidth, IOPS)

Shares represent a relative allocation measure, defining the proportional distribution of a resource among competing entities. They specify the ratio in which different entities receive service. A higher share value indicates a larger allocation of the resource

These parameters are externally provided, the responsibility falls on the process providing them to choose values that are suitable for the system's needs.

 The mClock, manages resources for both active and idle services. For instance,  In CEPH  multiple services like I/O, recover, backfill, scrub, timing, PG deletion..etc share resources, some services might be actively requesting resources, while others might be temporarily idle. It's important to keep track of the progress of both active and idle services in terms of resource allocation. Even though an idle service isn't actively making requests, resource share should still be accounted for idle services. If an idle service suddenly becomes active, it shouldn't be unfairly penalized because it was previously idle. To achieve this synchronization, the mclock scheduling algorithm maintains a global tag value, often called "global virtual time" or just "virtual time."

Algorithm

   Mclock Algorithm provides pseudo code of various components of the algorithm.

The scheduler has three main components: (i) Tag Assignment (ii) Tag Adjustment and (iii) Request Scheduling.

Tag Assignment:

    Tag assignment assigns values to the R, L, and P tags for each I/O request. When a request comes in from a specific service at a certain time, this routine determines the appropriate tag values based on its reservations, limits, and share. The scheduler then uses these tags to decide when and how to process the request.

 Reservation Tag   R_i^r  = max{R_i^r-1 +1/r_i ,t}            

                                    Where R_i^r  =Reservation tag of request r from v_i

 Limit  Tag             L_i^r  = max{L_i^r-1 +1/l_i ,t}         

                                   Where L_i^r  =Limit tag of request r from v_i

 Shares Tag          P_i^r  = max{P_i^r-1 +1/p_i ,t}          

                               Where P_i^r  =Share tag  of request r from v_i

Tag Adjustment:

Tag adjustment is a mechanism employed to synchronize proportional share tags with actual real time. This calibration is essential when a previously idle service transitions to an active state. By adjusting the tags of the now-active service, the scheduler ensures that its resource allocation accurately reflects its fair share, preventing it from being unfairly penalized for its prior inactivity.

minPtag = minimum of all P tags; 

foreach active VM vj do 

P_j^r  = P_j^r − ( minPtag − t);

Request Scheduling:

mClock's request scheduling uses three tags (Reservation, Limit, and Weight) instead of just one. It alternates between two phases: constraint-based and weight-based. In the constraint-based phase, it prioritizes requests from services whose Reservation tags are less than the current time, ensuring minimum guaranteed service. Once all services have met their reservations, it switches to the weight-based phase. Here, it selects requests based on the Weight tag (proportional share), but only from VMs that haven't reached their Limit. Crucially, during the weight-based phase, mClock adjusts the Reservation tags of outstanding requests to prevent weight-based allocations from interfering with guaranteed reservations.

Example

To illustrate let's take the example with the  Max QueueDepth = 32

For t = 0 (Only I/O Request Arrives, All Services Idle)

Tag Adjustment

At t = 0, only an I/O request arrives, and all services (I/O, Recovery, Best-effort) are idle.    The “minPtag” adjustment is required.

    minPtag = minimum of all active P tags

   Since no active requests exist, so minPtag = 0

Only the I/O service is active now so the “p” Tag of I/O needs to adjust 

                 P_I/O¹ = 0−(0−0)=0

Tag Assignment

         (i)  Reservation Tag-

                                      Since R_I/O^r-1= 0  and the reservation is 10

          (ii) Limit Tag-

                                     Since L_I/O^r-1= 0  and the limit is 50

         (iii) Shares Tag-

                                     Since P_I/O^r-1= 0  and the share is 30

Schedule Request

        The number of currently active I/O operations is 0 which is greater than the maximum allowed queue depth of 32. The statement Active IOs ≥ Max QueueDepth is valid.

The set E is empty due to the absence of services satisfying the condition where the R tag ≤ t.Currently, the R tag value is 0.1, while t is 0.

Similarly, The set t E′  is empty due to the absence of services satisfying the condition where the L tag ≤ t.Currently, the L tag value is 0.02, while t is 0.

After execution of the method, The request remains in the queue and will be considered in the next scheduling cycle. 

 t=0 execution output