WO2026017050A1 - Io scheduling method, electronic device, storage medium, and program product - Google Patents

Abstract

The present application relates to the technical field of input/output (IO) scheduling, and specifically relates to an IO scheduling method, an electronic device, a storage medium, and a program product. The method comprises: acquiring a current IO request to be processed; identifying said current IO request to determine target request data corresponding to said current IO request; determining a requested position of the target request data in a storage device and a requested data volume corresponding to the target request data; and on the basis of the requested position and the requested data volume, placing said current IO request into a target IO request processing queue to schedule said current IO request. IO requests to be processed in a plurality of IO request processing queues can be simultaneously processed, and there is no need to schedule the next IO request to be processed until the previous IO request to be processed is completed scheduling, thereby improving the overall IO request performance of a distributed storage system.

Description

IO scheduling methods, electronic devices, storage media and application products

Cross-reference to related applications

This application claims priority to Chinese Patent Application No. 202410962881.9, filed on July 18, 2024, entitled "IO Scheduling Method, Electronic Device, Storage Medium and Program Product", the entire contents of which are incorporated herein by reference.

Technical Field

This application relates to the field of I/O scheduling technology, specifically to I/O scheduling methods, electronic devices, storage media, and program products.

Background Technology

In a distributed storage system, storage resources are shared by all clients. Therefore, the distributed storage system receives I/O (Input/Output) requests from different clients. These I/O requests may pertain to the same byte range within the same LUN (Logical Unit Number), different byte ranges within the same LUN, or individual byte ranges within different LUNs.

To improve the management efficiency of distributed storage systems, OBJs (objects, the smallest data management unit in a distributed storage system) are typically used as the smallest management unit for storage resources, and a LUN consists of several OBJs. However, in related technologies, pending I/O requests are usually placed in the same I/O request processing queue and then scheduled sequentially. However, the I/O scheduling methods in these technologies do not significantly improve the concurrency of I/O scheduling.

Summary of the Invention

In view of this, this application provides an I/O scheduling method, electronic device, storage medium, and program product to solve the I/O scheduling problem.

In a first aspect, this application provides an IO scheduling method, the method comprising: obtaining a currently pending IO request; identifying the currently pending IO request and determining the target request data corresponding to the currently pending IO request; determining the request location of the target request data in the storage device and the corresponding request data volume of the target request data; and, based on the request location and request data volume corresponding to the target request data, placing the currently pending IO request into a target IO request processing queue and scheduling the currently pending IO request.

The IO scheduling method provided in this application embodiment obtains the currently pending IO requests; identifies the currently pending IO requests and determines the target request data corresponding to them, ensuring the accuracy of the determined target request data. It determines the request location of the target request data in the storage device and the corresponding request data volume. Based on the request location and request data volume, the currently pending IO requests are placed into a target IO request processing queue, and then scheduled. This ensures the accuracy of placing the currently pending IO requests into the target IO request processing queue. Furthermore, the method schedules the currently pending IO requests from the target IO request processing queue, ensuring the accuracy of scheduling. This allows for the simultaneous processing of pending IO requests in multiple IO request processing queues, eliminating the need to wait for the previous pending IO requests to complete before scheduling the next pending IO request, thereby further improving the overall IO request performance of the distributed storage system.

In one optional implementation, based on the request location and request data volume corresponding to the target request data, the current pending IO request is placed into the target IO request processing queue, and the current pending IO request is scheduled, including: comparing the request data volume with a preset request data volume threshold; if the request data volume is less than or equal to the preset request data volume threshold, based on the request location, the current pending IO request is placed into the target IO request processing queue, and the current pending IO request is scheduled; if the request data volume is greater than the preset request data volume threshold, the current pending IO request is split into multiple sub-pending IO requests based on the target request data; based on the sub-request location corresponding to the sub-target data of each sub-pending IO request, each sub-pending IO request is placed into the target IO request processing queue corresponding to its respective sub-pending IO request, and the multiple sub-pending IO requests are scheduled.

In one optional implementation, the current pending IO request is placed into the target IO request processing queue according to the request location and request data volume corresponding to the target request data, including: determining the number of target data management units corresponding to the target request data according to the request location and request data volume corresponding to the target request data; if the number of target data management units is 1, then the current pending IO request is placed into the target IO request processing queue corresponding to the target data management unit according to the target data management unit.

The IO scheduling method provided in this application determines the number of target data management units corresponding to the target request data based on the request location and the amount of request data, ensuring the accuracy of the determined number of target data management units. If the number of target data management units is 1, the currently pending IO request is placed into the target IO request processing queue corresponding to the target data management unit, ensuring the accuracy of placing the currently pending IO request into the target IO request processing queue corresponding to the target data management unit.

In one optional implementation, determining the number of target data management units corresponding to the target request data based on the request location and the amount of request data includes: determining the target logical unit corresponding to the target request data and the offset of the request location within the target logical unit based on the request location corresponding to the target request data, thereby obtaining the data management unit corresponding to the start address of the target request data; determining the data management unit corresponding to the end address of the target request data based on the amount of request data; if the data management unit corresponding to the start address and the data management unit corresponding to the end address are the same data management unit, determining the number of target data management units to be 1; if the data management unit corresponding to the start address and the data management unit corresponding to the end address are different data management units, determining the number of target data management units to be greater than 1.

In one optional implementation, the current pending IO request is placed into the target IO request processing queue according to the request location and the amount of request data corresponding to the target request data. The method further includes: if the number of target data management units is greater than 1, the current pending IO request is split into multiple sub-pending IO requests according to the number of target data management units; the number of sub-pending IO requests is consistent with the number of target data management units; and each sub-pending IO request is placed into the corresponding target IO request processing queue according to the target data management unit corresponding to each sub-pending IO request, so as to schedule each sub-pending IO request.

The IO scheduling method provided in this application, if the number of target data management units is greater than 1, splits the current pending IO request into multiple sub-pending IO requests based on the number of target data management units, ensuring the accuracy of splitting the current pending IO request into multiple sub-pending IO requests. Based on the target data management unit corresponding to each sub-pending IO request, each sub-pending IO request is placed into the corresponding target IO request processing queue for scheduling, ensuring the accuracy of placing each sub-pending IO request into the corresponding target IO request processing queue, thereby further improving the overall IO request performance of the distributed storage system.

In one optional implementation, there are multiple IO request processing queues. Placing the currently pending IO request into a target IO request processing queue includes: obtaining the queue number corresponding to the IO request processing queue; obtaining the identification information of the target data management unit corresponding to the currently pending IO request; and placing the currently pending IO request into the target IO request processing queue according to the queue number and the identification information.

The IO scheduling method provided in this application embodiment obtains the queue number corresponding to the IO request processing queue; obtains the identification information of the target data management unit corresponding to the current IO request to be processed; and puts the current IO request to be processed into the target IO request processing queue according to the queue number and the identification information, thereby ensuring the accuracy of putting the current IO request to be processed into the target IO request processing queue.

In one optional implementation, obtaining the number of queues corresponding to the IO request processing queue includes: calculating the number of queues based on the number of logical units and the number of data management units included in each logical unit.

In one optional implementation, the identification information of the target data management unit is the positional order identifier of the target data management unit in the corresponding logical unit. Based on the queue number and the identification information, the current IO request to be processed is placed into the target IO request processing queue, including: performing a modulo calculation on the queue number using the positional order identifier; determining the target IO request processing queue corresponding to the current IO request to be processed from each IO request processing queue based on the calculation result; and placing the current IO request to be processed into the target IO request processing queue.

The IO scheduling method provided in this application uses a positional order identifier to perform a modulo calculation on the number of queues. Based on the calculation result, the target IO request processing queue corresponding to the current IO request to be processed is determined from each IO request processing queue, ensuring the accuracy of the determined target IO request processing queue. The current IO request to be processed is then placed into the target IO request processing queue, ensuring the accuracy of placing the current IO request to be processed into the target IO request processing queue.

In one optional implementation, placing the current pending IO request into the target IO request processing queue includes: obtaining historical request data corresponding to each historical pending IO request in the target IO request processing queue; determining from the target IO request processing queue that the historical request data belongs to each first historical IO request to be compared in the target data management unit; comparing the target request data with the first historical request data corresponding to each first historical IO request to be compared; and placing the current pending IO request into the target IO request processing queue based on the comparison result.

The IO scheduling method provided in this application obtains historical request data corresponding to each historical IO request to be processed in the target IO request processing queue; determines each first historical IO request to be compared whose historical request data is located in the target data management unit from the target IO request processing queue, ensuring that the historical request data corresponding to each first historical IO request to be compared and the target request data are both located in the target data management unit, thereby ensuring that there may be overlapping data between the historical request data corresponding to each first historical IO request to be compared and the target request data. The target request data is compared with the first historical request data to be compared corresponding to each first historical IO request to be compared, ensuring the accuracy of the comparison result. Based on the comparison result, the current IO request to be processed is placed into the target IO request processing queue, ensuring the accuracy of placing the current IO request to be processed into the target IO request processing queue.

In one optional implementation, obtaining historical request data corresponding to each historical pending IO request in the target IO request processing queue includes: obtaining each historical pending IO request in the target IO request processing queue; identifying each historical pending IO request to obtain historical request data corresponding to each historical pending IO request and a historical data management unit corresponding to the historical request data.

In one optional implementation, the current IO request to be processed is placed into the target IO request processing queue according to the comparison result, including: if there is no overlapping data between the target request data and each of the first historical request data to be compared, then the current IO request to be processed is placed into the target IO request processing queue.

The IO scheduling method provided in this application embodiment, if there is no overlapping data between the target request data and each first historical request data to be compared, then the current IO request to be processed is placed in the target IO request processing queue, thereby ensuring that when processing each first historical request data to be compared, there is no IO request to be processed that overlaps with each first historical IO request to be compared, thus avoiding the problem of data inconsistency caused by the frequent occurrence of additional IO request operations for an address before the IO request for a certain address has been completed.

In an optional implementation, based on the comparison results, the current pending IO request is placed into the target IO request processing queue, and the method further includes: if there is overlapping data between the target request data and each of the first historical request data to be compared, then the first historical IO request to be compared that has overlapping data with the target request data is determined as the target historical IO request; the current pending IO request is placed into the first target mutex list corresponding to the target historical IO request; when the target historical IO request is processed, the current pending IO request is placed into the target IO request processing queue.

The IO scheduling method provided in this application, if there is overlapping data between the target request data and each of the first historical request data to be compared, determines the first historical IO request to be compared that has overlapping data as the target historical IO request, thus ensuring the accuracy of the determined target historical IO request. The current IO request to be processed is placed in the first target mutex linked list corresponding to the target historical IO request, thereby avoiding data inconsistency caused by adding the current IO request to be processed while processing the target historical IO request. When the target historical IO request is processed, the current IO request to be processed is placed in the target IO request processing queue, thereby avoiding data inconsistency.

In one optional implementation, when the target historical IO request has been processed, the current pending IO request is placed into the target IO request processing queue, including: temporarily storing the first target mutex list using a temporary linked list head; removing the target historical IO request from the first target mutex list; removing the target historical IO request from the target IO request processing queue; traversing the temporarily stored first target mutex list through the temporary linked list head, and sequentially performing the following steps on each other pending IO request on the first target mutex list other than the target historical IO request: removing the other pending IO requests from the first target mutex list, and putting the other pending IO requests back into the target IO request processing queue.

In one optional implementation, after the target historical IO request is processed, the current pending IO request is placed into the target IO request processing queue, including: after the target historical IO request is processed, retrieving each second historical IO request to be compared from the target IO request processing queue; the historical request data corresponding to the second historical IO request to be compared is located in the target data management unit; comparing the target request data with the second historical request data corresponding to the second historical IO request to be compared; if there is no overlapping data between the target request data and each second historical request data to be compared, then placing the current pending IO request into the target IO request processing queue; if there is overlapping data between the target request data and each second historical request data to be compared, then placing the current pending IO request into a second target mutex list, wherein the second target mutex list is the mutex list corresponding to the second historical request data to be compared that has overlapping data with the target request data.

The IO scheduling method provided in this application, after the target historical IO request has been processed, retrieves each second historical IO request to be compared from the target IO request processing queue, ensuring that the second historical request data corresponding to each second historical IO request to be compared and the target request data are both in the target data management unit. The target request data is compared with the second historical request data corresponding to the second historical IO requests to be compared; if there is no overlapping data between the target request data and each second historical request data to be compared, the current IO request to be processed is placed in the target IO request processing queue. If there is overlapping data between the target request data and each second historical request data to be compared, the current IO request to be processed is placed in the second target mutex list. This avoids the problem of data inconsistency caused by frequent additional IO request operations for a certain address before an IO request for that address has been completed.

In one optional implementation, comparing the target request data with the first historical request data corresponding to each first historical IO request to be compared includes: determining the target position offset of the target request data in the target data management unit based on the request position corresponding to the target request data; obtaining the historical position offset and historical data volume of the first historical request data to be compared in the target data management unit; and comparing the target request data with the first historical request data corresponding to each first historical IO request to be compared based on the relationship between the target position offset, the request data volume, the historical position offset, and the historical data volume.

The IO scheduling method provided in this application determines the target position offset of the target request data in the target data management unit based on the request position corresponding to the target request data, ensuring the accuracy of the determined target position offset. It obtains the historical position offset and historical data volume of the first historical request data to be compared in the target data management unit; based on the relationship between the target position offset, request data volume, historical position offset, and historical data volume, it compares the target request data with the first historical request data corresponding to each first historical IO request to be compared, ensuring the accuracy of the obtained comparison results.

In one optional implementation, based on the relationship between the target position offset, the requested data volume, the historical position offset, and the historical data volume, the target requested data is compared with the first historical request data corresponding to each first historical IO request to be compared. This includes: calculating the sum of the historical position offset and the historical data volume to obtain a first total offset; calculating the sum of the target position offset and the requested data volume to obtain a second total offset; comparing the target position offset with the first total offset; comparing the historical position offset with the second total offset; if the target position offset is greater than the first total offset, or the historical position offset is greater than the second total offset, then it is determined that there is no overlapping data between the target requested data and each first historical request data to be compared.

The IO scheduling method provided in this application calculates the sum of historical position offsets and historical data volumes to obtain a first total offset, ensuring the accuracy of the calculated first total offset. It also calculates the sum of target position offsets and requested data volumes to obtain a second total offset, ensuring the accuracy of the calculated second total offset. The target position offset is compared with the first total offset; the historical position offset is compared with the second total offset. If the target position offset is greater than the first total offset, or if the historical position offset is greater than the second total offset, then it is determined that there is no overlapping data between the target requested data and each of the first historical requested data to be compared, ensuring the accuracy of the determined non-overlapping data between the target requested data and each of the first historical requested data to be compared.

In one alternative implementation, scheduling the currently pending I/O requests includes: scheduling the currently pending I/O requests in the target I/O request processing queue using a target processing thread; the target processing thread is any one of a plurality of processing threads.

The IO scheduling method provided in this application uses a target processing thread to schedule the current pending IO requests in the target IO request processing queue. The target processing thread can be any one of multiple processing threads, thereby ensuring the accuracy of scheduling the current pending IO requests and realizing the parallel scheduling of multiple pending IO requests, further improving the overall IO request performance of the distributed storage system.

Secondly, this application provides an electronic device, including: a memory and a processor, which are communicatively connected to each other. The memory stores computer instructions, and the processor executes the computer instructions to perform the IO scheduling method of the first aspect or any corresponding embodiment described above.

Thirdly, this application provides a computer non-transitory readable storage medium storing computer instructions, which are used to cause a computer to execute the IO scheduling method of the first aspect or any corresponding embodiment described above.

Fourthly, this application provides a computer program product, including computer instructions for causing a computer to execute the I/O scheduling method of the first aspect or any corresponding embodiment thereof.

Attached Figure Description

To more clearly illustrate the technical solutions in the specific embodiments or related technologies of this application, the drawings used in the description of the specific embodiments or related technologies will be briefly introduced below. Obviously, the drawings described below are some embodiments of this application. For those skilled in the art, other drawings can be obtained from these drawings without creative effort.

Figure 1 is a schematic diagram of the architecture of a distributed storage system according to an embodiment of this application;

Figure 2 is a flowchart illustrating a first IO scheduling method according to an embodiment of this application;

Figure 3 is a flowchart illustrating a second IO scheduling method according to an embodiment of this application;

Figure 4 is a flowchart illustrating a third IO scheduling method according to an embodiment of this application;

Figure 5 is a flowchart illustrating that there is no overlap between the first type of target request data and each first historical request data to be compared according to an embodiment of this application.

Figure 6 is a flowchart illustrating that there is no overlap between the second type of target request data and each of the first historical request data to be compared according to an embodiment of this application;

Figure 7 is a schematic diagram of placing the current pending IO request into the target IO request processing queue according to an embodiment of this application;

Figure 8 is a flowchart illustrating the overlapping data between the first type of target request data and each first historical request data to be compared according to an embodiment of this application.

Figure 9 is a flowchart illustrating the overlapping data between the second type of target request data and each of the first historical request data to be compared, according to an embodiment of this application.

Figure 10 is a flowchart of the mutex list addition logic according to an embodiment of this application;

Figure 11 is a flowchart of the mutex list removal logic according to an embodiment of this application;

Figure 12 is a schematic diagram showing that there is overlap between the current pending IO request and multiple target historical IO requests according to an embodiment of this application;

Figure 13 is a schematic diagram of splitting the current pending IO request according to an embodiment of this application;

Figure 14 is a schematic diagram of optimizing the IO request processing queue according to an embodiment of this application.

Figure 15 is a schematic diagram illustrating a fourth IO scheduling method according to an embodiment of this application;

Figure 16 is a structural block diagram of an IO scheduling device according to an embodiment of this application;

Figure 17 is a schematic diagram of the hardware structure of an electronic device according to an embodiment of this application.

Detailed Implementation

To make the objectives, technical solutions, and advantages of the embodiments of this application clearer, the technical solutions of the embodiments of this application will be clearly and completely described below with reference to the accompanying drawings. Obviously, the described embodiments are only some embodiments of this application, not all embodiments. Based on the embodiments of this application, all other embodiments obtained by those skilled in the art without creative effort are within the scope of protection of this application.

For a hyperconverged server, all data read and write operations ultimately occur on the distributed storage system. Therefore, the performance of the distributed storage system is crucial to the overall performance of the hyperconverged server. The distributed storage system provides iSCSI (Internet Small Computer System Interface, a network standard protocol) target service, supporting multiple iSCSI clients to simultaneously initiate connection requests. This means that the storage resources of the distributed storage system are shared by all clients. Consequently, the distributed storage system receives IO requests from different clients. These IO requests may pertain to the same byte range within the same logical unit, different byte ranges within the same logical unit, or individual byte ranges within different logical units.

To improve the management efficiency of distributed storage systems, data management units (DMUs) are typically used as the smallest management unit for storage resources. A logical unit consists of several DMUs. The DMU in a distributed storage system is similar to the concept of a sector on a physical disk. Smaller DMUs result in finer granularity of storage resource management and higher I/O concurrency, but also higher disk loss (each DMU corresponds to metadata; for the same disk capacity, smaller DMUs result in more DMUs, more metadata, more disk space occupied, and less usable disk space), and lower management efficiency. Conversely, larger DMUs result in finer granularity of storage resource management, lower I/O concurrency, but lower disk loss and higher management efficiency. Currently, the industry typically sets the DMU to 4MB (Megabyte).

To improve the IO concurrency of a distributed storage system, IO requests from different logical units and IO requests from different regions of the same logical unit can be processed concurrently because the storage resources are independent of each other, thereby increasing IO concurrency.

However, for IO requests with overlapping storage resources, all IO requests are executed in the request processing queue in a FIFO (First In First Out) manner for the sake of data consistency. The IO request data block is used as the granularity of IO scheduling. This execution method does solve the data consistency problem at the IO scheduling level, but it is not friendly to the overall performance of the distributed storage system. This is because different IO requests of the same logical unit may not have read-write or write-write dependencies. These requests can be scheduled and executed earlier without waiting for the requests that arrived earlier to be executed.

With the increasing parallelism of I/O requests, new I/O requests for the same address often occur before the previous one is completed. To avoid data inconsistency, traditional solutions wait for the previous I/O request to finish before scheduling the next one. However, in scenarios with high I/O pressure, especially when there are numerous simultaneous read and write accesses to the same storage resource, the traditional I/O scheduling strategy can be further optimized. There is still room for improvement in I/O concurrency, and the overall I/O performance of the distributed storage system can be further enhanced.

Based on this, this application provides an IO scheduling method applied to a distributed storage system, as shown in Figure 1. The architecture of the distributed storage system, from top to bottom, consists of a protocol layer, an IO scheduling layer, a storage engine layer, a device driver layer, and physical disks. The protocol layer is used to receive and parse connection requests and IO requests initiated by various clients. Since mutual exclusion of storage resources is not involved, concurrency can be maximized here. The IO scheduling layer no longer uses the entire IO request as the smallest scheduling unit, but rather processes IO requests using a data management unit as the smallest scheduling unit.

In some embodiments, as shown in Figure 2, the processing flow of the IO scheduling method is as follows: Obtain the current pending IO request; identify the current pending IO request and determine the target request data corresponding to it, ensuring the accuracy of the determined target request data. Determine the request location of the target request data in the storage device and the corresponding request data volume. When the data length of an IO request is greater than the length of a data management unit or spans two adjacent data management units aligned to 4MB (the size of a data management unit), the requested data length is divided into multiple different data management units aligned to 4MB and processed concurrently. Specific implementation details are described later. When multiple IO requests exist simultaneously for data in the same data management unit, the granularity of concurrent IO scheduling is reduced based on the overlap of data intervals in each IO request, thereby increasing IO concurrency. The storage engine layer manages the physical disk (data from multiple logical units may be distributed across multiple disks). The device driver layer connects the physical disk and the software operating system. The physical disk stores user data.

It should be noted that the IO scheduling method provided in this application embodiment can be executed by an IO scheduling device. This IO scheduling device can be implemented as part or all of an electronic device through software, hardware, or a combination of both. The electronic device can be a server or a terminal. In this application embodiment, the server can be a single server or a server cluster composed of multiple servers. The terminal in this application embodiment can be a smartphone, personal computer, tablet computer, wearable device, or other intelligent hardware device such as an intelligent robot. The following method embodiments will all use an electronic device as an example for explanation.

According to an embodiment of this application, an IO scheduling method embodiment is provided. It should be noted that the steps shown in the flowchart in the accompanying drawings can be executed in a computer system such as a set of computer-executable instructions. Although a logical order is shown in the flowchart, in some cases, the steps shown or described may be executed in a different order than that shown here.

This embodiment provides an I/O scheduling method that can be used in the aforementioned electronic device. Figure 3 is a flowchart of the I/O scheduling method according to an embodiment of this application. As shown in Figure 3, the process includes the following steps:

Step S101: Obtain the currently pending IO requests.

In some embodiments, the electronic device can receive currently pending I/O requests input by the user, or it can receive currently pending I/O requests sent by other devices. This application does not specifically limit the method by which the electronic device obtains currently pending I/O requests.

Step S102: Identify the current pending IO request and determine the target request data corresponding to the current pending IO request.

In some embodiments, the electronic device can identify the currently pending I/O request and determine the target request data corresponding to the currently pending I/O request.

Step S103: Determine the request location of the target request data in the storage device and the corresponding request data volume of the target request data.

In some embodiments, the electronic device identifies the target request data corresponding to the current pending IO request, determines the request location of the target request data in the storage device, and the corresponding request data volume of the target request data.

Step S104: Based on the request location and request data volume corresponding to the target request data, the current pending IO request is placed into the target IO request processing queue, and the current pending IO request is scheduled.

In some embodiments, the electronic device may compare the amount of request data corresponding to the target request data with a preset request data amount threshold.

If the amount of request data corresponding to the target request data is not greater than the preset request data amount threshold, then according to the request position corresponding to the target request data, the current pending IO request is placed into the target IO request processing queue, and the current pending IO request is scheduled.

If the amount of request data corresponding to the target request data is greater than a preset request data volume threshold, the current pending IO request is split into multiple sub-pending IO requests based on the target request data. Then, based on the sub-request position corresponding to the sub-target data of each sub-pending IO request, each sub-pending IO request is placed into its corresponding target IO request processing queue, and the multiple sub-pending IO requests are scheduled.

The IO scheduling method provided in this application embodiment obtains the currently pending IO requests; identifies the currently pending IO requests and determines the target request data corresponding to them, ensuring the accuracy of the determined target request data. It determines the request location of the target request data in the storage device and the corresponding request data volume. Based on the request location and request data volume, the currently pending IO requests are placed into a target IO request processing queue, and then scheduled. This ensures the accuracy of placing the currently pending IO requests into the target IO request processing queue. Furthermore, the method schedules the currently pending IO requests from the target IO request processing queue, ensuring the accuracy of scheduling. This allows for the simultaneous processing of pending IO requests in multiple IO request processing queues, eliminating the need to wait for the previous pending IO requests to complete before scheduling the next pending IO request, thereby further improving the overall IO request performance of the distributed storage system.

This embodiment provides an I/O scheduling method that can be used in the aforementioned electronic device. Figure 4 is a flowchart of the I/O scheduling method according to an embodiment of this application. As shown in Figure 4, the process includes the following steps:

Step S201: Obtain the currently pending IO requests.

Please refer to Figure 3 for a description of step S101; it will not be repeated here.

Step S202: Identify the current pending IO request and determine the target request data corresponding to the current pending IO request.

Please refer to Figure 3 for a description of step S102; it will not be repeated here.

Step S203: Determine the request location of the target request data in the storage device and the corresponding request data volume of the target request data.

Please refer to Figure 3 for a description of step S103; it will not be repeated here.

Step S204: Based on the request location and request data volume corresponding to the target request data, the current pending IO request is placed into the target IO request processing queue, and the current pending IO request is scheduled.

In some embodiments, step S204 above, "placing the current pending IO request into the target IO request processing queue according to the request location and request data volume corresponding to the target request data," may include the following steps:

Step S2041: Determine the number of target data management units corresponding to the target request data based on the request location and the amount of request data corresponding to the target request data.

In some embodiments, the electronic device may determine the number of target data management units corresponding to the target request data based on the request location and the amount of request data.

In this system, the target data management unit is the smallest data management unit, and each target data management unit has a unique identifier. The distributed storage system can include multiple logical units, and each logical unit includes multiple data management units. The data storage capacity corresponding to each data management unit can be 4MB, 3MB, or other storage capacities. This embodiment does not specifically limit the data storage capacity corresponding to each data management unit.

In some embodiments, the electronic device can determine the target logic unit corresponding to the target request data and the offset of the target request position within the target logic unit based on the request position corresponding to the target request data, thereby determining the data management unit corresponding to the start address of the target request data. Then, it determines the data management unit corresponding to the end address of the target request data based on the data volume corresponding to the target request data. If they correspond to the same data management unit, the number of target data management units is 1. If the start address and end address of the target request data correspond to different data management units, the number of target data management units is not 1.

Step S2042: If the number of target data management units is 1, then according to the target data management unit, the current unprocessed IO request is placed into the target IO request processing queue corresponding to the target data management unit.

In one optional embodiment of this application, there are multiple IO request processing queues, and step S2042 above may include the following steps:

Step a1: Obtain the number of queues corresponding to the IO request processing queue.

In some embodiments, the electronic device can receive the number of queues corresponding to the IO request processing queue set by the user, or it can receive the number of queues corresponding to the IO request processing queue sent by other devices. The electronic device can also calculate the number of queues corresponding to the IO request processing queue based on the number of logical units in the distributed storage system and the number of data management units included in each logical unit.

For example, for the same logical unit, the number of queues corresponding to the IO request processing queue is obtained by dividing the number of data management units included in each logical unit by 3.

Step a2: Obtain the identification information of the target data management unit corresponding to the current pending IO request.

In some embodiments, the electronic device can determine the target data management unit and its identification information based on the start and end addresses of the target request data.

Step a3: Based on the queue number and identification information, place the currently pending IO request into the target IO request processing queue.

In some embodiments, the identification information of the target data management unit is the positional identifier of the target data management unit in the corresponding logical unit, and step a3 above may include the following steps:

Step a31: Calculate the queue size using the positional order identifier modulo operation.

In some embodiments, the electronic device uses the positional sequence identifier to perform a modulo calculation on the queue size.

Step a32: Based on the calculation results, determine the target IO request processing queue corresponding to the current IO request to be processed from each IO request processing queue.

In some embodiments, the electronic device determines the target IO request processing queue corresponding to the current IO request to be processed from each IO request processing queue based on the calculation results.

For example, assuming the number of queues is 3, the electronic device divides the position sequence identifier of the target data management unit in the corresponding logical unit by 3 and takes the remainder. If the remainder is 0, the target IO request processing queue corresponding to the current IO request to be processed is determined as IO request processing queue 0; if the remainder is 1, the target IO request processing queue corresponding to the current IO request to be processed is determined as IO request processing queue 1; if the remainder is 2, the target IO request processing queue corresponding to the current IO request to be processed is determined as IO request processing queue 2.

Step a33: Place the currently pending IO request into the target IO request processing queue.

In some embodiments, after determining the target IO request processing queue corresponding to the current IO request to be processed, the current IO request to be processed can be placed into the target IO request processing queue.

In some embodiments, step a33 above may include the following steps:

Step a331: Obtain the historical request data corresponding to each historical pending IO request in the target IO request processing queue.

In some embodiments, the electronic device can obtain each historical pending IO request from the target IO request processing queue, identify each historical pending IO request, and determine the historical request data corresponding to each historical pending IO request and the historical data management unit corresponding to the historical request data.

Step a332: Determine from the target IO request processing queue each of the first historical IO requests to be compared in the target data management unit.

In some embodiments, the electronic device compares the historical data management unit corresponding to the historical request data of each historical pending IO request with the target data management unit. Then, it determines from the target IO request processing queue each first historical IO request to be compared whose historical request data is located in the target data management unit. That is, the historical data management unit corresponding to the historical request data of each first historical IO request to be compared is consistent with the target data management unit corresponding to the target request data.

Step a333: Compare the target request data with the first historical request data corresponding to each first historical IO request to be compared.

In some embodiments, step a333 above may include the following steps:

Step a3331: Determine the target position offset of the target request data in the target data management unit based on the request position corresponding to the target request data.

In some embodiments, the electronic device can determine the target position offset of the target request data in the target data management unit based on the request position corresponding to the target request data.

Step a3332: Obtain the historical position offset and historical data volume of the first historical request data to be compared in the target data management unit.

In some embodiments, the electronic device can identify the first historical request data to be compared corresponding to the first historical IO request to be compared, and determine the historical position offset and historical data volume of the first historical request data to be compared in the target data management unit.

Step a3333: Based on the relationship between the target position offset, the requested data volume, the historical position offset, and the historical data volume, compare the target requested data with the first historical request data corresponding to each first historical IO request to be compared.

In some embodiments, step a3333 described above may include the following steps:

Step a33331: Calculate the sum of the historical position offset and the historical data volume to obtain the first total offset.

In some embodiments, the electronic device calculates the sum of the historical location offset and the amount of historical data to obtain a first total offset.

Step a33332: Calculate the sum of the target position offset and the requested data amount to obtain the second total offset.

In some embodiments, the electronic device calculates the sum of the target location offset and the requested data amount to obtain a second total offset.

Step a33333: Compare the target position offset with the first total offset.

Step a33334: Compare the historical position offset with the second total offset.

Step a33335: If the target position offset is greater than the first total offset, or the historical position offset is greater than the second total offset, then it is determined that there is no overlapping data between the target request data and each of the first historical request data to be compared.

In some embodiments, the electronic device compares the target position offset with a first total offset and compares the historical position offset with a second total offset.

If the target location offset is greater than the first total offset, or the historical location offset is greater than the second total offset, then it is determined that there is no overlapping data between the target request data and each of the first historical request data to be compared.

For example, Figure 5 illustrates the case where the historical position offset is greater than the second total offset. In Figure 5, the top represents the current IO request to be processed, and the bottom represents the first historical IO request to be compared. Wherein, the end position of the target data corresponding to the current IO request to be processed is smaller than the start position of the first historical request data to be compared in the first historical IO request to be compared, i.e., a_offset + a_len < b_offset, then it is determined that there is no overlapping data between the target request data and each of the first historical request data to be compared.

Figure 6 illustrates the case where the target position offset is greater than the first total offset. In Figure 6, the top represents the current I/O request to be processed, and the bottom represents the first set of historical I/O requests to be compared. If the starting position of the target data corresponding to the current I/O request to be processed is greater than the ending position of the first set of historical I/O requests to be compared (i.e., a_offset > b_offset + b_len), then it is determined that there is no overlapping data between the target request data and each of the first set of historical I/O requests to be compared.

Step a334: Based on the comparison results, put the current pending IO request into the target IO request processing queue.

In some embodiments, step a334 above may include the following steps:

Step a3341: If there is no overlapping data between the target request data and each of the first historical request data to be compared, then the current IO request to be processed is placed into the target IO request processing queue.

In some embodiments, if there is no overlapping data between the target request data and each of the first historical request data to be compared, the current IO request to be processed is placed in the target IO request processing queue.

For example, as shown in Figure 7, if there is no overlap between the target request data and each of the first historical request data to be compared, then the current IO request to be processed is placed into the target IO request processing queue.

Step a3342: If there is overlapping data between the target request data and each of the first historical request data to be compared, then the first historical IO request to be compared that has overlapping data with the target request data is determined as the target historical IO request.

In some embodiments, if there is overlapping data between the target request data and each of the first historical request data to be compared, then the first historical IO request to be compared that has overlapping data with the target request data is determined as the target historical IO request.

Step a3343: Place the current pending IO request into the first target mutex linked list corresponding to the target historical IO request.

In some embodiments, the electronic device places the current pending IO request into the first target mutex list corresponding to the target historical IO request based on the identification information corresponding to the target historical IO request.

As shown in Figure 8, obj_1c is the current pending IO request, and obj_1a is the target historical IO request. Since the target request data of the current pending IO request overlaps with the data range of the first historical IO request to be compared in the target data management unit in the target IO request processing queue, i.e., there is storage resource contention and mutual exclusion, it is necessary to first add the current pending IO request to the mutex list of the first historical IO request to be compared with the overlapping data range. After that is processed, the current pending IO request on the mutex list is then re-attempted to be added to the target IO request processing queue.

As shown in Figure 9, obj_1c is the current pending IO request, and obj_1b is the target historical IO request. Since the target request data of the current pending IO request overlaps with the data range of the first first historical IO request to be compared in the target data management unit within the target IO request processing queue, meaning there is no storage resource contention, the two can be processed concurrently. However, the data range of the second first historical IO request to be compared in the target data management unit within the target IO request processing queue overlaps, meaning there is storage resource contention. Therefore, the current pending IO request needs to be added to the mutex list of the second first historical IO request with overlapping data ranges. After that second request is processed, the current pending IO request on the mutex list can be re-added to the target IO request processing queue.

In one optional implementation of this application, as shown in Figure 10, a flowchart of the logic for adding logic to the mutex linked list is presented. First, the type of the OBJ request is determined. If the OBJ request is not a read/write IO request, the process ends directly, because other IO requests such as management or query IO requests do not require actual IO read/write processing, and therefore do not need to execute the relevant logic involved in this method. If the OBJ request is a read/write IO request, it is determined whether the target IO request processing queue is empty. If the target IO request processing queue is empty, it is directly added to the tail of the queue and the process ends. If the target IO request processing queue is not empty, it needs to be traversed from the head to the tail of the queue. If a target historical IO request with the same OID (Object Identifier) as the current pending IO request (i.e., both are within the target data management unit) and overlapping data ranges is found in the target IO request processing queue, then it is determined whether the linked list of the target historical IO request has been initialized. If the linked list has not been initialized, it is initialized and used as the head of a mutex linked list. Then, the current pending IO request is added to the tail of the mutex linked list, and the process ends. If no target historical IO request with the same OID and overlapping data ranges as the current pending IO request is found in the target IO request processing queue, the current pending IO request is added to the tail of the IO request processing queue, and the process ends.

The mutex linked list supports multiple pending requests to be attached simultaneously. Requests must be attached to the tail of the list in chronological order, and requests cannot be inserted in the middle of the list.

Step a3344: Once the target historical IO requests have been processed, place the current pending IO requests into the target IO request processing queue.

In one optional implementation of this application, when a target historical IO request is processed, it needs to be removed from the target IO request processing queue. Simultaneously, the currently pending IO requests with overlapping data ranges are removed from the mutex list corresponding to the target historical IO request and attempted to be re-added to the target IO request processing queue. The specific implementation logic is shown in Figure 11. Figure 11 is a flowchart of the mutex list removal logic. For a target historical IO request about to be dequeued, it is first determined whether the mutex list of the target historical IO request has been initialized and is not empty. If the mutex list on the target historical IO request is not initialized, it means that the target historical IO request has never had a history of overlapping data regions, and the target historical IO request can be directly removed from the target IO request processing queue. If the mutex list on the target historical IO request has been initialized but the list is empty, it means that the target historical IO request has had a history of overlapping data regions, but currently there is no storage resource mutual exclusion, and it can be directly removed from the target IO request processing queue. If the mutex list on the target historical IO request has been initialized and is not empty, the following processing is required. First, a temporary linked list head is used to temporarily store the mutex list on the target historical IO request (to prevent the loss of IO mutex list information on the target historical IO request). Then, the target historical IO request is removed from the mutex list and then removed from the target IO request processing queue. Then, the previously stored mutex list is traversed through the temporary linked list head, and the following operations are performed on other pending IO requests on the mutex list in order: the other pending IO requests are removed from the mutex list, and the mutex list addition logic described above is used to try to add them back to the target IO request processing queue.

In some embodiments, step a3344 above may include the following steps:

Step a33441: After the target historical IO request is processed, retrieve each second historical IO request to be compared from the target IO request processing queue again.

Among them, the historical request data corresponding to the second historical IO request to be compared is located in the target data management unit.

In some embodiments, once the target historical IO request has been processed, each second historical IO request to be compared is retrieved again from the target IO request processing queue.

Step a33442: Compare the target request data with the second historical request data corresponding to the second historical IO request to be compared.

In some embodiments, the electronic device compares the target request data with the second historical request data corresponding to the second historical IO request to be compared.

Step a33443: If there is no overlapping data between the target request data and each of the second historical request data to be compared, then the current IO request to be processed is placed into the target IO request processing queue.

In some embodiments, if there is no overlapping data between the target request data and each of the second historical request data to be compared, the electronic device places the current pending IO request into the target IO request processing queue.

Step a33444: If there is overlapping data between the target request data and each of the second historical request data to be compared, then the current IO request to be processed is placed into the second target mutex list.

The second target mutex list is the mutex list corresponding to the second historical request data to be compared that has overlapping data with the target request data.

In some embodiments, if there is overlapping data between the target request data and each of the second historical request data to be compared, the current IO request to be processed is placed into the second target mutex list.

For example, as shown in Figure 12, this diagram illustrates overlapping data between the current pending IO request and multiple target historical IO requests. Since the target request data of the current pending IO request overlaps with the data range of the first historical IO request to be compared in the target data management unit within the target IO request processing queue, meaning there is storage resource contention and mutual exclusion, the current pending IO request needs to be added to the mutex list of the first historical IO request to be compared with overlapping data ranges. After that request is processed, the current pending IO request on the mutex list is then re-added to the target IO request processing queue. The reason for choosing to add it to the first historical IO request to be compared is that when traversing the target IO request processing queue, following the traversal order from beginning to end, if overlap is found, there is no need to continue traversing, thus improving performance.

Then, once the target historical I/O requests have been processed, each second historical I/O request to be compared is retrieved from the target I/O request processing queue. The target request data is compared with the second historical I/O request data corresponding to the second historical I/O requests to be compared. If there is overlapping data between the target request data and each of the second historical I/O requests to be compared, the current I/O request to be processed is placed into the second target mutex list.

Step S2043: If the number of target data management units is greater than 1, then the current pending IO request is split according to the number of target data management units to obtain multiple sub-pending IO requests.

The number of sub-IO requests to be processed is consistent with the number of target data management units.

For example, as shown in Figure 13, a logical unit consists of several data management units. If the target request data is a data block with an offset of offset and length of len on this logical unit, and this data block is divided according to 4MB alignment and falls on 3 data management units, then the current pending IO request is split into requests to 3 different data management units, which can participate in the IO scheduling strategy of the distributed storage system respectively. Therefore, the number of target data management units is 3.

Step S2044: Based on the target data management unit corresponding to each sub-IO request to be processed, place each sub-IO request to be processed into the corresponding target IO request processing queue in order to schedule each sub-IO request to be processed.

In some embodiments, the process of placing each sub-IO request to be processed into the corresponding target IO request processing queue can be referred to in the above embodiment of "if the number of target data management units is 1, then according to the target data management unit, the current IO request to be processed is placed into the target IO request processing queue corresponding to the target data management unit", which will not be elaborated here.

In some embodiments, the "scheduling of the current pending IO requests" in step S204 above may include the following steps:

Step S2045: Use the target processing thread to schedule the currently pending IO requests in the target IO request processing queue.

The target processing thread can be any one of multiple processing threads.

For example, Figure 14 illustrates the optimization of the IO request processing queue. Each IO request processing queue is managed by a single thread (not a worker thread in the thread pool), primarily responsible for traversing the IO request processing queue, enqueuing and dequeuing data management unit requests, and managing the mutex linked list. When a new data management unit request arrives at the IO scheduling layer, its OID is moduloed (i.e., the remainder when the OID is divided by 3). If the result is 0, the data management unit request is placed in the first IO request processing queue; if the result is 1, it is placed in the second IO request processing queue; and if the result is 2, it is placed in the third IO request processing queue. This splits the IO request processing queue from one to three, shortening the queue length and reducing the time spent traversing the queue, thereby improving the efficiency of IO request processing queue management. The management method for each IO request processing queue is consistent, as described above.

By default, worker threads in the thread pool are evenly distributed across various I/O request processing queues to handle data management unit requests. When the load on the I/O request processing queues is uneven, the worker threads in the thread pool can dynamically balance the load across multiple I/O request processing queues to maximize the concurrent processing capacity of the thread pool and ensure the processing speed of each queue as much as possible.

The IO scheduling method provided in this application determines the number of target data management units corresponding to the target request data based on the request location and request data volume, ensuring the accuracy of the determined number of target data management units. If the number of target data management units is 1, the method obtains the queue number corresponding to the IO request processing queue; obtains the identification information of the target data management unit corresponding to the currently pending IO request; calculates the queue number modulo using the position order identifier; and determines the target IO request processing queue corresponding to the currently pending IO request from each IO request processing queue based on the calculation result, ensuring the accuracy of the determined target IO request processing queue.

The process involves: acquiring historical request data corresponding to each historical pending IO request in the target IO request processing queue; determining the first comparison historical IO requests whose historical request data is located in the target data management unit, ensuring that both the historical request data and the target request data for each of the first comparison historical IO requests are located in the target data management unit, thus preventing potential overlap between the historical request data and the target request data; determining the target position offset of the target request data in the target data management unit based on the request position corresponding to the target request data, ensuring the accuracy of the determined target position offset; acquiring the historical position offset and historical data volume of the first comparison historical request data in the target data management unit; calculating the sum of the historical position offset and the historical data volume to obtain the first total offset, ensuring the accuracy of the calculated first total offset; and calculating the sum of the target position offset and the request data volume to obtain the second total offset, ensuring the accuracy of the calculated second total offset. The target position offset is compared with the first total offset; the historical position offset is compared with the second total offset; if the target position offset is greater than the first total offset, or the historical position offset is greater than the second total offset, then it is determined that there is no overlapping data between the target request data and each of the first historical request data to be compared, thus ensuring the accuracy of the determination that there is no overlapping data between the target request data and each of the first historical request data to be compared.

If there is no overlapping data between the target request data and each of the first historical request data to be compared, the current pending IO request is placed in the target IO request processing queue. This ensures that when processing each of the first historical request data to be compared, there are no pending IO requests with overlapping data with each of the first historical IO requests to be compared. This avoids the problem of data inconsistency caused by IO requests to a certain address being added before the IO request to that address has been completed.

If there is overlap between the target request data and each of the first historical request data to be compared, the first historical IO request with overlapping data is identified as the target historical IO request, ensuring the accuracy of the identified target historical IO request. The current pending IO request is placed in the first target mutex linked list corresponding to the target historical IO request, thus preventing data inconsistency caused by adding the current pending IO request while processing the target historical IO request. Once the target historical IO request is processed, the current pending IO request is placed in the target IO request processing queue, further preventing data inconsistency.

Once the target historical I/O request is processed, the second historical I/O requests to be compared are retrieved from the target I/O request processing queue. This ensures that the second historical request data corresponding to each retrieved second historical I/O request to be compared, along with the target request data, are both within the target data management unit. The target request data is compared with the second historical request data corresponding to the second historical I/O requests to be compared. If there is no overlapping data between the target request data and the second historical request data to be compared, the current I/O request to be processed is placed in the target I/O request processing queue. If there is overlapping data between the target request data and the second historical request data to be compared, the current I/O request to be processed is placed in the second target mutex list. This avoids the problem of data inconsistency caused by additional I/O requests to a certain address occurring before an I/O request to that address has been completed.

If the number of target data management units is greater than one, the current pending IO request is split into multiple sub-pending IO requests based on the number of target data management units. This ensures the accuracy of splitting the current pending IO request into multiple sub-pending IO requests. Each sub-pending IO request is then placed into its corresponding target IO request processing queue based on the target data management unit it corresponds to, enabling scheduling of each sub-pending IO request. This ensures the accuracy of placing each sub-pending IO request into its corresponding target IO request processing queue, thereby further improving the overall IO request performance of the distributed storage system.

The target processing thread is used to schedule the currently pending IO requests in the target IO request processing queue. The target processing thread can be any one of multiple processing threads, which ensures the accuracy of scheduling the currently pending IO requests and enables the parallel scheduling of multiple pending IO requests, thereby further improving the overall IO request performance of the distributed storage system.

To better illustrate the IO scheduling method described in the embodiments of this application, this application provides a specific implementation method for a concurrent IO scheduling method based on data interval mutual exclusion. Taking Figure 15 as an example, the implementation of the technology of this application is explained in detail.

Assume the total capacity of the target logical unit to be accessed is 12MB, consisting of three 4MB (obj_size) data management units (numbered sequentially from 0), namely obj_0, obj_1, and obj_2, with corresponding OIDs of 0x0000123400000000, 0x0000123400000001, and 0x0000123400000002, respectively. Two consecutive IO read/write requests, IO_req1 and IO_req2, are made. The offset_1 of IO_req1 is 3MB and the length len_1 is 3MB. The offset_2 of IO_req2 is 5MB and the length len_2 is 4MB.

During the initialization of the distributed storage system, the first threshold `worker_num` is configured to be 3, meaning the maximum number of worker threads in the thread pool is 3, numbered starting from 0. The multi-IO request processing queue feature is enabled, and the second threshold `queue_num` is configured to be 3, meaning there are 3 IO request processing queues simultaneously, numbered starting from 0. Thread pool load balancing is also enabled by default, meaning the 3 worker threads (`worker_num`) are evenly distributed across the 3 IO request processing queues to handle IO requests.

First, the distributed storage system receives the IO write request IO_req1. Upon inspection, it finds that the requested data range spans two data management units and needs to be split. The inspection and splitting methods are as follows:

(1) Calculate which data management unit the starting address of the requested data block is located in;
offset_1/obj_size=3/4=0...3;

That is, the starting address is located in the 0th data management unit, i.e., obj_0.

(2) Calculate which data management unit the end address of the requested data block is located in;
(offset_1+len_1)/obj_size=(3+3)/4=1...2;

The end address is located in the first data management unit, namely obj_1.

(3) Determine whether the IO request needs to be split;

Since the data management unit where the starting address is located and the data management unit where the ending address is located are not in the same data management unit, it is necessary to align according to obj_size and split the IO request into two data management unit requests for IO scheduling respectively.

The first sub-IO_req1 request is obj_0a_p1, which requests an offset_a_p1 of 3MB and a length len_a_p1 of 1MB in obj_0.

The second sub-IO_req1 request is obj_1a_p2, which requests that the offset_a_p2 in obj_1 is 0 and the length len_a_p2 is 2MB;

Then, the two sub-IO requests, obj_0a_p1 and obj_1a_p2, are placed on the IO request processing queue for scheduling. Here's a supplementary explanation of the naming: "obj_0" indicates the target data management unit is obj_0, "a" indicates the first concurrent IO request, and "p1" and "p2" indicate that the IO request is split into two data management unit requests.

(1) Perform a modulo operation on the OID of the data management unit that the first data management unit requests obj_0a_p1 to access:
oid%queue_num=0x0000123400000000/3=0;

The first sub-IO_req1 request, obj_0a_p1, should be placed in the 0th IO request processing queue. Since this sub-IO_req1 is a read/write IO request and the IO request processing queue 0 is currently empty, it can be directly enqueued.

(2) Perform a modulo operation on the OID of the data management unit that the second data management unit requests obj_1a_p2 to access:
oid%queue_num=0x0000123400000001/3=1;

The second sub-IO_req1obj_1a_p2 should be placed in the first IO request processing queue. Since this sub-IO_req1 request is a read/write IO request and the IO request processing queue 1 is currently empty, it can be directly enqueued.

Immediately afterwards, the sub-IO_req1 request is scheduled by IO, and the worker threads in the thread pool begin to process the IO.

Before the IO write request IO_req1 is completed, the distributed storage system concurrently receives the IO read request IO_req2. Upon inspection, it is found that the requested data range spans two data management units and needs to be split. The inspection and splitting methods are as follows:

(1) Calculate which data management unit the starting address of the requested data block is located in;
offset_2/obj_size=5/4=1...1;

That is, the starting address is located in the first data management unit, namely obj_1.

(2) Calculate which data management unit the end address of the requested data block is located in;
(offset_1+len_1)/obj_size=(5+4)/4=2...1;

The end address is located in the second data management unit, namely obj_2.

(3) Determine whether the IO request needs to be split;

Since the data management unit where the starting address is located and the data management unit where the ending address is located are not in the same data management unit, it is necessary to align according to obj_size and split the IO request into two data management unit requests for IO scheduling respectively.

The first sub-IO_req2 request is obj_1b_p1, which requests an offset_b_p1 of 1MB and a length len_b_p1 of 3MB in obj_1.

The second sub-IO_req2 request is obj_2b_p2, which requests an offset_b_p2 of 0 and a length len_b_p2 of 1MB in obj_2.

Then, these two sub-IO_req2 requests, obj_1b_p1 and obj_2b_p2, are placed on the IO request processing queue for scheduling.

(1) Perform a modulo operation on the OID of the data management unit to be accessed by the first sub-IO_req2 request obj_1b_p1:
oid%queue_num=0x0000123400000001%3=1;

The first data management unit request, obj_1b_p1, should be placed in the first IO request processing queue. This data management unit request is a read-write IO request. Since IO request processing queue 1 is not empty, it's necessary to first traverse IO request processing queue 1 to check if there is already a data management unit request in the target IO request processing queue that overlaps with the data range of the new data management unit request. It is found that both the existing data management unit request obj_1a_p2 and the new data management unit request obj_1b_p1 need to access the storage resource obj_1 with oid 0x0000123400000001. Therefore, it is necessary to determine whether the data ranges of these two data management unit requests overlap, that is, to determine the size of the start and end addresses of the data ranges requested by the two data management unit requests within obj_1.

The starting address of the data in obj_1a_p2 is: offset_a_p2 = 0 (MB);

The end address of the data in obj_1a_p2 in obj_1: offset_a_p2 + len_a_p2 = 0 + 2 = 2 (MB);

That is, the data range of obj_1a_p2 in obj_1 is [0,2] MB;

The starting address of the data in obj_1b_p1: offset_b_p1 = 1 (MB);

The end address of the data in obj_1b_p1: offset_b_p2 + len_b_p2 = 1 + 3 = 4 (MB);

That is, the data range of obj_1b_p1 in obj_1 is [1,4] MB;

The data range [0,2]MB and the data range [1,4]MB overlap, so obj_1b_p1 needs to be added to the IO mutex list first. The specific operation is as follows:

If the check reveals that the linked list of obj_1a_p2 is not initialized, then the linked list is initialized and used as the head of the IO mutex linked list. Then, the new data management unit request obj_1b_p1 is added to the tail of the IO mutex linked list. At this time, the new data management unit request obj_1b_p1 does not participate in IO scheduling. It needs to wait for the data management unit request obj_1a_p2 to complete before attempting to add the new data management unit request obj_1b_p1 to the IO request processing queue for scheduling.

(2) Perform a modulo operation on the OID of the data management unit that the second data management unit requests obj_2b_p2 to access:
oid%queue_num=0x0000123400000002%3=2;

The second data management unit request, obj_2b_p2, should be placed in the second IO request processing queue. Since this data management unit request is a read/write IO request and IO request processing queue 2 is currently empty, it can be directly enqueued.

At this point, each of the three IO request processing queues has one data management unit request being concurrently processed by worker threads in the thread pool, and there is one more data management unit request waiting to be scheduled on IO request processing queue 1.

Once the data management unit request obj_0a_p1 on IO request processing queue 0 has been processed, it needs to be removed from the IO request processing queue. The specific process is as follows: Upon inspection, it is found that the linked list on the data management unit request has not been initialized, so the data management unit request can be directly removed from the IO request processing queue.

After the data management unit request obj_1a_p2 on IO request processing queue 1 is processed, it needs to be removed from IO request processing queue 1. The specific process is as follows: Upon inspection, it is found that the linked list for the data management unit request has been initialized and is not empty. A temporary linked list head is used to temporarily store the data management unit request. Then, the data management unit request is removed from the IO mutex list. Next, the data management unit request is removed from IO request processing queue 1. Then, the IO mutex list is traversed through the temporary linked list head to retrieve the data management unit request obj_1b_p1 (i.e., the data management unit request is removed from the IO mutex list). Then, an attempt is made to add it back to IO request processing queue 1. At this point, IO request processing queue 1 is empty, so it is simply added to the tail of the queue. The IO mutex list traversal is now complete, and the process ends. At this point, the two data management unit requests obj_0a_p1 and obj_1a_p2, split from the IO write request IO_req1, have both been processed. The results are merged and returned to the user.

Once the data management unit request obj_2a_p2 on IO request processing queue 2 has been processed, it needs to be removed from the IO request processing queue. The specific process is as follows: Upon inspection, it is found that the linked list on the data management unit request has not been initialized, so the data management unit request can be directly removed from the IO request processing queue.

At this point, the IO request list only contains the data management unit request obj_1b_p1. After the data management unit request is completed, the two data management unit requests obj_1b_p1 and obj_2b_p2, which were split from the IO read request IO_req2, have been processed. The results are then merged and returned to the user.

This embodiment also provides an I/O scheduling device configured to implement the above embodiments and optional implementations, details of which will not be repeated. As used below, the term "module" can be a combination of software and/or hardware that implements a predetermined function. Although the device described in the following embodiments is preferably implemented in software, hardware implementation, or a combination of software and hardware, is also possible and contemplated.

This embodiment provides an IO scheduling device, as shown in FIG16, including: an acquisition module 501, configured to acquire a currently pending IO request; a first determination module 502, configured to identify the currently pending IO request and determine the target request data corresponding to the currently pending IO request; a second determination module 503, configured to determine the request location of the target request data in the storage device and the corresponding request data volume of the target request data; and a scheduling module 504, configured to place the currently pending IO request into a target IO request processing queue according to the request location and request data volume corresponding to the target request data, and schedule the currently pending IO request.

Further functional descriptions of the above modules and units are the same as those in the corresponding embodiments described above, and will not be repeated here.

In this embodiment, the IO scheduling device is presented in the form of a functional unit. Here, a unit refers to an ASIC (Application Specific Integrated Circuit) circuit, a processor and memory that execute one or more software or fixed programs, and/or other devices that can provide the above functions.

This application also provides an electronic device having the IO scheduling device shown in FIG16 above.

Please refer to Figure 17, which is a schematic diagram of an electronic device provided in an optional embodiment of this application. As shown in Figure 17, the electronic device includes: one or more processors 10, a memory 20, and interfaces for connecting the various components, including high-speed interfaces and low-speed interfaces. The various components communicate with each other using different buses and can be mounted on a common motherboard or otherwise installed as needed. The processor can process instructions executed within the electronic device, including instructions stored in or on memory to display graphical information of a GUI on an external input/output device (such as a display device coupled to the interface). In some optional embodiments, multiple processors and/or multiple buses can be used with multiple memories and multiple memory sets, if desired. Similarly, multiple electronic devices can be connected, each providing some of the necessary operations (e.g., as a server array, a group of blade servers, or a multiprocessor system). Figure 17 uses one processor 10 as an example.

Processor 10 may be a central processing unit, a network processor, or a combination thereof. Processor 10 may also include hardware chips. These hardware chips may be application-specific integrated circuits (ASICs), programmable logic devices (PLDs), or combinations thereof. The programmable logic devices may be complex programmable logic devices (CLPs), field-programmable gate arrays (FPGAs), general-purpose array logic (GDAs), or any combination thereof.

The memory 20 stores instructions executable by at least one processor 10 to cause at least one processor 10 to perform the method shown in the above embodiments.

The memory 20 may include a program storage area and a data storage area. The program storage area may store the operating system and applications required for at least one function; the data storage area may store data created based on the use of the electronic device. Furthermore, the memory 20 may include high-speed random access memory and may also include non-transitory memory, such as at least one disk storage device, flash memory device, or other non-transitory solid-state storage device. In some alternative embodiments, the memory 20 may optionally include memory remotely located relative to the processor 10, and these remote memories may be connected to the electronic device via a network. Examples of such networks include, but are not limited to, the Internet, intranets, local area networks, mobile communication networks, and combinations thereof.

The memory 20 may include volatile memory, such as random access memory; the memory may also include non-volatile memory, such as flash memory, hard disk or solid-state drive; the memory 20 may also include a combination of the above types of memory.

The electronic device also includes an input device 30 and an output device 40. The processor 10, memory 20, input device 30 and output device 20 can be connected via a bus or other means, as shown in Figure 17, which illustrates a bus connection.

Input device 30 can receive input numerical or character information, and generate key signal inputs related to user settings and function control of the electronic device, such as a touch screen, keypad, mouse, trackpad, touchpad, joystick, one or more mouse buttons, trackball, joystick, etc. Output device 40 may include display devices, auxiliary lighting devices (e.g., LEDs (Light Emitting Diodes)), and haptic feedback devices (e.g., vibration motors). The aforementioned display devices include, but are not limited to, liquid crystal displays, LEDs, displays, and plasma displays. In some alternative embodiments, the display device may be a touch screen.

This application also provides a computer-readable storage medium. The methods described in this application can be implemented in hardware or firmware, or implemented as recordable on a storage medium, or implemented as computer code downloaded over a network and originally stored on a remote storage medium or a non-transitory machine-readable storage medium and subsequently stored on a local storage medium. Thus, the methods described herein can be processed by software stored on a storage medium using a general-purpose computer, a dedicated processor, or programmable or dedicated hardware. The storage medium can be a magnetic disk, optical disk, read-only memory, random access memory, flash memory, hard disk, or solid-state drive, etc.; optionally, the storage medium may also include combinations of the above types of memory. It is understood that computers, processors, microprocessor controllers, or programmable hardware include storage components capable of storing or receiving software or computer code, which, when accessed and executed by the computer, processor, or hardware, implements the methods shown in the above embodiments.

A portion of this application can be applied as a computer program product, such as computer program instructions, which, when executed by a computer, can invoke or provide the methods and/or technical solutions according to this application through the operation of the computer. Those skilled in the art will understand that the forms in which computer program instructions exist in a computer-readable medium include, but are not limited to, source files, executable files, installation package files, etc. Correspondingly, the ways in which computer program instructions are executed by a computer include, but are not limited to: the computer directly executing the instructions, or the computer compiling the instructions and then executing the corresponding compiled program, or the computer reading and executing the instructions, or the computer reading and installing the instructions and then executing the corresponding installed program. Here, the computer-readable medium can be any available computer-readable storage medium or communication medium accessible to a computer.

Although embodiments of this application have been described in conjunction with the accompanying drawings, those skilled in the art can make various modifications and variations without departing from the spirit and scope of this application, and all such modifications and variations fall within the scope defined by the appended claims.

Claims (20)

An input/output (I/O) scheduling method, characterized in that the method includes: Get the currently pending I/O requests; Identify the current pending IO request and determine the target request data corresponding to the current pending IO request; Determine the requested location of the target requested data in the storage device and the corresponding amount of requested data; Based on the request location and the amount of request data corresponding to the target request data, the current pending IO request is placed into the target IO request processing queue, and the current pending IO request is scheduled. The method according to claim 1, characterized in that, the step of placing the currently pending IO request into the target IO request processing queue according to the request position and the amount of request data corresponding to the target request data, and scheduling the currently pending IO request, includes: Compare the requested data volume with a preset requested data volume threshold; If the requested data volume is less than or equal to the preset requested data volume threshold, the current pending IO request is placed into the target IO request processing queue according to the request location, and the current pending IO request is scheduled. When the requested data volume is greater than the preset requested data volume threshold, the current pending IO request is split according to the target request data to obtain multiple sub-pending IO requests; according to the sub-request position corresponding to the sub-target data of each sub-pending IO request, each sub-pending IO request is placed into the target IO request processing queue corresponding to each sub-pending IO request, and the multiple sub-pending IO requests are scheduled. According to the method of claim 1, the step of placing the currently pending IO request into the target IO request processing queue based on the request position corresponding to the target request data and the amount of request data includes: The number of target data management units corresponding to the target request data is determined based on the request location and the amount of request data. If the number of target data management units is 1, then according to the target data management unit, the current unprocessed IO request is placed into the target IO request processing queue corresponding to the target data management unit. The method according to claim 3, characterized in that, determining the number of target data management units corresponding to the target request data based on the request location and the amount of request data corresponding to the target request data includes: Based on the request position corresponding to the target request data, determine the target logic unit corresponding to the target request data and the offset of the request position corresponding to the target request data in the target logic unit, and obtain the data management unit corresponding to the starting address of the target request data; Determine the data management unit corresponding to the end address of the target request data based on the requested data volume; If the data management unit corresponding to the starting address and the data management unit corresponding to the ending address are the same data management unit, the number of the target data management units is determined to be 1. If the data management unit corresponding to the starting address and the data management unit corresponding to the ending address are different data management units, the number of target data management units is determined to be greater than 1. The method according to claim 3, characterized in that, the step of placing the currently pending IO request into the target IO request processing queue according to the request position corresponding to the target request data and the request data volume, further includes: If the number of target data management units is greater than 1, then the current pending IO request is split into multiple sub-pending IO requests based on the number of target data management units; the number of sub-pending IO requests is the same as the number of target data management units. According to the target data management unit corresponding to each sub-IO request to be processed, each sub-IO request to be processed is placed into the corresponding target IO request processing queue for scheduling. According to the method of claim 3, wherein there are multiple IO request processing queues, and the step of placing the currently pending IO request into the target IO request processing queue corresponding to the target data management unit according to the target data management unit includes: Get the number of queues corresponding to the IO request processing queue; Obtain the identification information of the target data management unit corresponding to the currently pending IO request; Based on the queue size and the identification information, the current pending IO request is placed into the target IO request processing queue. According to the method of claim 6, the step of obtaining the number of queues corresponding to the IO request processing queue includes: The number of queues is calculated based on the number of logical units and the number of data management units included in each logical unit. According to the method of claim 6, the identification information of the target data management unit is the positional identifier of the target data management unit in the corresponding logical unit, and the step of placing the current unprocessed IO request into the target IO request processing queue according to the queue quantity and the identification information includes: The number of queues is calculated modulo the positional sequence identifier. Based on the calculation results, the target IO request processing queue corresponding to the current IO request to be processed is determined from each of the IO request processing queues; The currently pending IO request is placed into the target IO request processing queue. The method according to claim 8, wherein placing the currently pending IO request into the target IO request processing queue comprises: Obtain the historical request data corresponding to each historical unprocessed IO request in the target IO request processing queue; The historical request data is determined from the target IO request processing queue to be in each of the first historical IO requests to be compared in the target data management unit; The target request data is compared with the first historical request data corresponding to each of the first historical IO requests to be compared; Based on the comparison results, the currently pending IO request is placed into the target IO request processing queue. According to the method of claim 9, the step of obtaining historical request data corresponding to each historical unprocessed IO request in the target IO request processing queue includes: Obtain each of the historical pending IO requests from the target IO request processing queue; Each of the historical pending IO requests is identified, and the historical request data corresponding to each of the historical pending IO requests and the historical data management unit corresponding to the historical request data are obtained. According to the method of claim 9, the step of placing the current unprocessed IO request into the target IO request processing queue based on the comparison result includes: If there is no overlap between the target request data and each of the first historical request data to be compared, then the current IO request to be processed is placed in the target IO request processing queue. The method according to claim 9, characterized in that, the step of placing the current unprocessed IO request into the target IO request processing queue according to the comparison result further includes: If there is overlapping data between the target request data and each of the first historical request data to be compared, then the first historical IO request to be compared that has overlapping data with the target request data is determined as the target historical IO request; Place the current pending IO request into the first target mutex linked list corresponding to the target historical IO request; Once the target historical IO request has been processed, the current pending IO request is placed into the target IO request processing queue. According to the method of claim 12, the step of placing the currently pending IO request into the target IO request processing queue after the target historical IO request has been processed includes: Use the head of a temporary linked list to temporarily store the first target mutex linked list; Remove the target historical IO request from the first target mutex list; Remove the target historical IO request from the target IO request processing queue; By traversing the temporarily stored first target mutex list through the head of the temporary linked list, the following steps are performed on each other pending IO request on the first target mutex list in sequence, except for the target historical IO request: the other pending IO requests are removed from the first target mutex list, and the other pending IO requests are put back into the target IO request processing queue. According to the method of claim 12, the step of placing the currently pending IO request into the target IO request processing queue after the target historical IO request has been processed includes: Once the target historical IO request has been processed, each second historical IO request to be compared is retrieved again from the target IO request processing queue; the historical request data corresponding to the second historical IO request to be compared is located in the target data management unit; The target request data is compared with the second historical request data corresponding to the second historical IO request to be compared. If there is no overlap between the target request data and each of the second historical request data to be compared, then the current IO request to be processed is placed in the target IO request processing queue; If there is overlapping data between the target request data and each of the second historical request data to be compared, the current IO request to be processed is placed in the second target mutex list, wherein the second target mutex list is the mutex list corresponding to the second historical request data to be compared that has overlapping data with the target request data. The method according to claim 9, characterized in that, comparing the target request data with the first historical request data corresponding to each of the first historical IO requests to be compared, includes: Based on the request location corresponding to the target request data, determine the target position offset of the target request data in the target data management unit; Obtain the historical position offset and historical data volume of the first historical request data to be compared in the target data management unit; Based on the relationship between the target location offset, the requested data volume, the historical location offset, and the historical data volume, the target requested data is compared with the first historical requested data corresponding to each of the first historical IO requests to be compared. The method according to claim 15, characterized in that, comparing the target request data with the first historical request data corresponding to each of the first historical IO requests to be compared, based on the relationship between the target position offset, the requested data volume, the historical position offset, and the historical data volume, includes: Calculate the sum of the historical position offset and the historical data volume to obtain the first total offset; Calculate the sum of the target location offset and the requested data amount to obtain the second total offset; Compare the target position offset with the first total offset; Compare the historical position offset with the second total offset; If the target location offset is greater than the first total offset, or the historical location offset is greater than the second total offset, then it is determined that there is no overlapping data between the target request data and each of the first historical request data to be compared. The method according to claim 1, wherein scheduling the currently pending I/O request includes: The target processing thread is used to schedule the currently pending IO requests in the target IO request processing queue; the target processing thread is any one of multiple processing threads. An electronic device, characterized in that it comprises: A memory and a processor are communicatively connected, the memory stores computer instructions, and the processor executes the input/output I/O scheduling method of any one of claims 1 to 17 by executing the computer instructions. A non-transitory readable storage medium for computers, characterized in that the non-transitory readable storage medium stores computer instructions, the computer instructions being used to cause a computer to execute the input/output I/O scheduling method according to any one of claims 1 to 17. A computer program product, characterized in that it includes computer instructions, said computer instructions being used to cause a computer to execute the input/output I/O scheduling method according to any one of claims 1 to 17.