Rate matching technique for balancing segment cleaning and I/O workload

• US 10,210,082 B2
• Filed: 04/28/2017
• Issued: 02/19/2019
• Est. Priority Date: 09/12/2014
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Patel, Dhaval, Swaminathan, Manish, McClanahan, Edward D., Muth, John
• Primary Examiner(s): Bragdon, Reginald G
• Assistant Examiner(s): Wang, Edward
• Application Number:
  US15/581,800
• Publication Number:
  US 20170235673A1
• Time in Patent Office: 662 Days
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/1024 Latency reduction
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/702 Conservative garbage collection
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays

Abstract

A rate matching technique may be configured to adjust a rate of cleaning of one or more selected segments of the storage array to accommodate a variable rate of incoming workload processed by a storage input/output (I/O) stack executing on one or more nodes of a cluster. An extent store layer of the storage I/O stack may clean a segment in accordance with segment cleaning which, illustratively, may be embodied as a segment cleaning process. The rate matching technique may be implemented as a feedback control mechanism configured to adjust the segment cleaning process based on the incoming workload. Components of the feedback control mechanism may include one or more weight schedulers and various accounting data structures, e.g., counters, configured to track the progress of segment cleaning and free space usage. The counters may also be used to balance the rates of segment cleaning and incoming I/O workload, which may change depending upon an incoming I/O rate. When the incoming I/O rate changes, the rate of segment cleaning may be adjusted accordingly to ensure that rates are substantially balanced.

Claims

1. A system comprising:

a processor of a storage system coupled to a plurality of storage devices; and

a memory coupled to the processor and configured to store a storage input/output (I/O) stack executable by the processor, the storage I/O stack including a process configured to segment clean a segment spanning the storage devices, the memory further configured to store a feedback control loop having a plurality of accounting data structures used to balance a rate of the segment cleaning with a rate of incoming I/O workload of read and write operations directed to the storage devices, the feedback control loop further including a write weight scheduler and a plurality of read weight schedulers, the write weight scheduler provided for all storage devices of the segment to perform a full stripe write operation across the storage devices and a read weight scheduler provided for each storage device of the segment to perform a read operation to one storage device at a time.

2. The system of claim 1 wherein each weight scheduler includes queues associated with categories of the incoming I/O workload and wherein the categories of incoming I/O workload include user data workload, metadata workload and relocation workload.

3. The system of claim 2 wherein the queues include a data queue configured to queue incoming user data, a metadata queue configured to queue incoming metadata, and a relocation queue configured to queue relocation data during the segment cleaning.

4. The system of claim 3 wherein each weight scheduler is configured to exert control over the rate of the segment cleaning to substantially match the rate of the incoming I/O workload by assignment of weights to the queues according to a ratio.

5. The system of claim 4 wherein each queue is processed in proportion to a weight assigned to the queue.

6. The system of claim 4 wherein a number of bytes of the incoming I/O workload of each queue is processed to maintain the ratio of the weights assigned to the queues.

7. The system of claim 2 wherein the queues include separate assemblages of read queues associated with each of the plurality of read weight schedulers, wherein the separate assemblages of read queues include the queues associated with the categories of incoming I/O workload.

8. The system of claim 2 wherein the queues further include a single assemblage of write queues associated with the write weight scheduler, wherein the single assemblage of read queues include the queues associated with the categories of incoming I/O workload.

9. The system of claim 1 wherein the accounting data structures are configured to keep track of statistics used to derive a number of bytes of the segment relocated by the process during the segment cleaning.

10. The system of claim 9 wherein the accounting data structures include a segment cleaning progress accounting structure configured to compute a percentage of bytes relocated so as to track progress of the segment cleaning.

11. The system of claim 10 wherein the accounting data structures further include a free space accounting structure configured to compute a percentage of free space used so as to track free space usage within the segment.

12. A method comprising:

executing, by a processor coupled to a plurality of storage devices, a storage input/output (I/O) stack including a process configured to segment clean a segment spanning the storage devices;

storing a feedback control loop in a memory coupled to the processor, the feedback control loop having a plurality of accounting data structures, a write weight scheduler and a plurality of read weight schedulers;

balancing a rate of the segment cleaning with a rate of incoming I/O workload of read and write operations directed to the storage devices using the feedback control loop;

performing a full stripe write operation across the storage devices using the write weight scheduler provided for all storage devices of the segment; and

performing a read operation to one storage device at a time using a read weight scheduler provided for each storage device of the segment.

13. The method of claim 12 wherein each weight scheduler includes queues associated with categories of the incoming I/O workload and wherein the categories of incoming I/O workload include user data workload, metadata workload and relocation workload.

14. The method of claim 13 further comprising exerting control over the rate of the segment cleaning using each weight scheduler to substantially match the rate of the incoming I/O workload by assignment of weights to the queues according to a ratio.

15. The method of claim 14 further comprising processing each queue in proportion to a weight assigned to the queue.

16. The method of claim 14 further comprising processing a number of bytes of the incoming I/O workload of each queue to maintain the ratio of the weights assigned to the queues.

17. The method of claim 12 further comprising deriving a number of bytes of the segment relocated by the process during the segment cleaning using the accounting data structures.

18. The method of claim 17 further comprising computing a percentage of bytes relocated using a segment cleaning progress accounting structure of the accounting data structures to track progress of the segment cleaning.

19. The method of claim 18 further comprising computing a percentage of free space used using a free space accounting structure of the accounting data structures to track free space usage within the segment.

20. A non-transitory computer readable medium including program instructions for execution on one or more processors, the program instructions configured to:

implement a storage input/output (I/O) stack including a process configured to segment clean a segment spanning a plurality of storage devices coupled to a processor;

store a feedback control loop in a memory coupled to the processor, the feedback control loop having a plurality of accounting data structures, a write weight scheduler and a plurality of read weight schedulers;

balance a rate of the segment cleaning with a rate of incoming I/O workload of read and write operations directed to the storage devices using the feedback control loop;

perform a full stripe write operation across the storage devices using the write weight scheduler provided for all storage devices of the segment; and

perform a read operation to one storage device at a time using a read weight scheduler provided for each storage device of the segment.