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

• US 9,671,960 B2
• Filed: 09/12/2014
• Issued: 06/06/2017
• Est. Priority Date: 09/12/2014
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Patel, Dhaval, Swaminathan, Manish, Muth, John, McClanahan, Edward D.
• Primary Examiner(s): Bragdon, Reginald
• Assistant Examiner(s): Wang, Edward
• Application Number:
  US14/484,565
• Publication Number:
  US 20160077745A1
• Time in Patent Office: 998 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 method comprising:

receiving, at an incoming rate, a plurality of write requests directed towards one or more logical units (LUN), each write request having data and processed at a node of a cluster, the node having a memory and connected to a storage array of solid state drives (SSDs);

storing the data of each write request as one or more user data extents in a first segment spanning a set of SSDs, the first segment having a log-structured layout;

tracking a percentage of free space of the first segment;

tracking a percentage of bytes relocated from the first segment to a second segment spanning the set of SSDs, the second segment having the log-structured layout;

computing an error by subtracting the percentage of free space from the percentage of bytes relocated; and

controlling a rate of cleaning the first segment by substantially matching the cleaning rate to the incoming rate based on the computed error.

2. The method of claim 1 wherein the computed error is computed in response to a change in the percentage of free space exceeding a threshold.

3. The method of claim 1 further comprising:

processing a relocation queue in proportion to a first weight assigned to the relocation queue, the first weight determined using the computed error, wherein the bytes relocated from the first segment to the second segment are queued to the relocation queue.

4. The method of claim 3 wherein the processing of the relocation queue in proportion to the first weight occurs by an amount of bytes processed from the relocation queue.

5. The method of claim 3 wherein the processing of the relocation queue in proportion to the first weight occurs by an amount of bytes processed from the relocation queue.

6. The method of claim 3 wherein the data of each write request is queued to a user data queue separate from the relocation queue.

7. The method claim 6 further comprising:

processing the user data queue in proportion to a second weight assigned to the user data queue such that a ratio of the first weight to the second weight is maintained.

8. The method of claim 3 wherein each SSD of the set of SSDs has a separate read relocation queue, and wherein the first weight is assigned to a write relocation write queue shared among the set of SSDs.

9. The method of claim 8 wherein the first weight is modified in response to a number of read requests in the read queues exceeding a threshold.

10. A method comprising:

receiving, at an incoming rate, a plurality of write requests directed towards one or more logical units (LUN), each write request having data and processed at a node of a cluster, the node having a memory and connected to a storage array of solid state drives (SSDs);

storing the data of each write request as one or more user data extents in a first segment spanning a set of SSDs, the first segment having a log-structured layout;

tracking an amount free space of the first segment;

tracking an amount bytes relocated from the first segment to a second segment spanning the set of SSDs;

setting a desired rate of relocating bytes from the first segment to the second segment by computing an error using the amount free space and the amount of bytes relocated; and

controlling a relocation queue to maintain the desired rate of cleaning, wherein relocate bytes are queued to the relocation queue.

11. A system comprising:

a storage system having a memory connected to a processor via a bus;

a storage array coupled to the storage system and having one or more solid state drives (SSDs);

a storage I/O stack executing on the processor of the storage system, the storage I/O stack configured to;

receive, at an incoming rate, a plurality of write requests directed towards one or more logical units (LUN), each write request having data;

store the data of each write request as one or more user data extents in a first segment spanning a set of SSDs, the first segment having a log-structured layout;

track a percentage of free space of the first segment;

track a percentage of bytes relocated from the first segment to a second segment spanning the set of SSDs, the second segment having the log-structured layout; and

compute an error by subtracting the percentage of free space from the percentage of bytes relocated; and

control a rate of cleaning the first segment by substantially matching the cleaning rate to the incoming rate based on the computed error.

12. The system of claim 11 wherein the computed error is computed in response to a change in the percentage of free space exceeding a threshold.

13. The system of claim 11 wherein the storage I/O stack is further configured to:

process a relocation queue in proportion to a first weight assigned to the relocation queue, the first weight determined using the computed error, wherein the bytes relocated from the first segment to the second segment are queued to the relocation queue.

14. The system of claim 13 wherein the data of each write request is queued to a user data queue separate from the relocation queue.

15. The system of claim 14 wherein the storage I/O stack is further configured to:

process the user data queue in proportion to a second weight assigned to the user data queue such that a ratio of the first weight to the second weight is maintained.

16. The system of claim 13 wherein each SSD of the set of SSDs has a separate read relocation queue, and wherein the first weight is assigned to a write queue shared among the set of SSDs.

17. The system of claim 16 wherein the first weight is modified in response to a number of read requests in the read queues exceeds a threshold.

18. The system of claim 16 wherein the first weight assigned to each write queue is modified in response to a number of relocation operations dispatched.