Systems and methods for log coordination

• US 10,073,630 B2
• Filed: 11/08/2013
• Issued: 09/11/2018
• Est. Priority Date: 11/08/2013
• Status: Expired due to Fees

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: Yang, Jingpei, Talagala, Nisha, Sundararaman, Swaminathan, Plasson, Ned, Gillis, Gregory N.
• Primary Examiner(s): LI, ZHUO H
• Application Number:
  US14/075,951
• Publication Number:
  US 20150134926A1
• Time in Patent Office: 1,768 Days
• CPC Class Codes: G06F 17/40 Data acquisition and logging for input to computer G06F3/00
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0623 in relation to content
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0664 at device level, e.g. emulation of a storage device or system
• CPC Class Codes: G06F 3/0673 Single storage device
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays

Abstract

A storage module may be configured to perform log storage operations on a storage log maintained on a non-volatile storage medium. An I/O client may utilize storage services of the storage module to maintain an upper-level log. The storage module may be configured to coordinate log storage and/or management operations between the storage log and the upper-level log. The coordination may include adapting a segment size of the logs to reduce write amplification. The coordination may further include coordinating validity information between log layers, adapting log grooming operations to reduce storage recovery overhead, defragmenting upper-level log data within the storage address space, preventing fragmentation of upper-level log data, and so on. The storage module may coordinate log operations by use of log coordination messages communicated between log layers.

Claims

1. A method, comprising:

writing data on a non-volatile storage medium in response to storage requests pertaining to a client log comprising logical log segments, the logical log segments comprising respective logical addresses of a logical address space, wherein writing the data comprises;

storing the data within a storage log comprising an ordered sequence of physical log segments, the physical log segments comprising respective physical addresses within a physical address space of the non-volatile storage medium;

receiving a notification pertaining to a client grooming operation, the client grooming operation to invalidate data of a logical log segment of the client log; and

coordinating storage grooming operations on physical log segments of the storage log based on the notification pertaining to the client grooming operation, wherein coordinating the storage grooming operations comprises;

identifying data pertaining to a particular logical log segment within two or more

physical log segments of the storage log, the two or more physical log segments comprising data that does not pertain to the particular logical log segment;

relocating the identified data from the two or more physical log segments to a first physical log segment of the storage log; and

relocating the data that does not pertain to the particular log segment from the two or more physical log segments to a second physical log segment of the storage log, different from the first physical log segment.

2. The method of claim 1, wherein storing the data within the storage log further comprises associating the data stored on the non-volatile storage medium with respective logical addresses in a translation map, and wherein the notification comprises a deallocation message specifying logical addresses to be invalidated in the client grooming operation, the specified logical addresses associated with data stored on the non-volatile storage medium in the translation map.

3. The method of claim 1, wherein coordinating the storage grooming operations comprises identifying data within a selected physical log segment of the storage log that does not need to be retained on the non-volatile storage medium based on the notification pertaining to the client grooming operation.

4. The method of claim 1, wherein data of the logical log is interleaved with other data within one or more physical log segments of the storage log, wherein coordinating the storage grooming operations comprises consolidating the interleaved data of the logical log within respective physical log segments of the storage log during the storage grooming operations.

5. The method of claim 1, further comprising:

maintaining a plurality of append points within the storage log, each append point corresponding to a respective physical address of the physical address space and a respective region of the logical address space; and

selecting one of the plurality of append points to store data of a storage request based on logical identifiers pertaining to the storage request.

6. A method, comprising:

writing data on a non-volatile storage medium in response to storage requests pertaining to a client log comprising logical log segments, the logical log segments comprising respective logical addresses of a logical address space, wherein writing the data comprises;

storing the data within a storage log comprising an ordered sequence of physical log segments, the physical log segments comprising respective physical addresses within a physical address space of the non-volatile storage medium;

receiving a notification pertaining to a client grooming operation, the client grooming operation to invalidate data of a logical log segment of the client log; and

coordinating storage grooming operations on physical log segments of the storage log based on the notification pertaining to the client grooming operation, wherein coordinating the storage grooming operations comprises one of;

pausing a storage grooming operation to recover a selected physical log segment of the storage log, wherein recovering the selected physical log segment comprises relocating valid data stored within the selected physical log segment to another physical log segment of the storage log and erasing the selected physical log segment, and

resuming the storage grooming operation to recover the selected physical log segment.

7. The method of claim 6, wherein storing the data within the storage log further comprises associating the data stored on the non-volatile storage medium with respective logical addresses in a translation map, and wherein the notification comprises a deallocation message specifying logical addresses to be invalidated in the client grooming operation, the specified logical addresses associated with data stored on the non-volatile storage medium in the translation map.

8. The method of claim 6, wherein coordinating the storage grooming operations comprises identifying data within a selected physical log segment of the storage log that does not need to be retained on the non-volatile storage medium based on the notification pertaining to the client grooming operation.

9. The method of claim 6, wherein data of the logical log is interleaved with other data within one or more physical log segments of the storage log, wherein coordinating the storage grooming operations comprises consolidating the interleaved data of the logical log within respective physical log segments of the storage log during the storage grooming operations.

10. The method of claim 6, further comprising:

maintaining a plurality of append points within the storage log, each append point corresponding to a respective physical address of the physical address space and a respective region of the logical address space; and

selecting one of the plurality of append points to store data of a storage request based on logical identifiers pertaining to the storage request.

11. A non-transitory computer-readable storage medium comprising instructions configured to cause a computing device to perform operations, the operations comprising:

managing a storage log comprising a plurality of physical log segments, the physical log segments comprising respective physical addresses of a physical address space of a non-volatile storage medium, wherein managing the storage log comprises maintaining a plurality of append points within the storage log, each append point corresponding to a respective physical log segment of the storage log; and

storing data within the storage log in response to write requests, wherein storing data within the storage log in response to a write request comprises;

determining whether the write request pertains to a logical log, the logical log corresponding to logical identifiers of a logical address space associated with the non-volatile storage medium,

selecting an append point for the write request from the plurality of append points maintained within the storage log based on the determining, and

storing the data of the write request within the storage log, wherein the data is stored at a physical address within the physical log segment corresponding to the selected append point, and

wherein maintaining the plurality of append points within the storage log further comprises;

maintaining a first append point for data pertaining to the logical log, and

maintaining a second append point for data that does not pertain to the logical log, the logical log comprising a set of logical identifiers of the logical address space, and

wherein selecting the append point for the write request further comprises;

selecting the first append point in response to determining that a logical identifier associated with the write request is within the set of logical identifiers, and

selecting the second append point in response to determining that the logical identifier associated with the write request is outside of the set of logical identifiers.

12. The non-transitory computer-readable storage medium of claim 11, the operations further comprising adjusting a storage recovery operation schedule for recovery operations on physical log segments of the storage log in response to log coordination metadata pertaining to recovery operations of the logical log.

13. The non-transitory computer-readable storage medium of claim 11, further comprising recovering a selected physical log segment of the storage log by identifying data within the selected physical log segment that does not need to be retained on the non-volatile storage medium based on validity information pertaining to one or more logical log segments of the logical log.

14. The non-transitory computer-readable storage medium of claim 11, the operations further comprising:

providing an application programming interface to receive log coordination information pertaining to the logical log at the storage log; and

determining whether the write request pertains to the logical log based on log coordination information received through the application programming interface.

15. The non-transitory computer-readable storage medium of claim 14, wherein the log coordination information received through the provided interface indicates logical identifiers that correspond to the logical log, and wherein determining whether the write request pertains to the logical log comprises determining whether the write request pertains to one or more of the indicated logical identifiers.

16. The non-transitory computer-readable storage medium of claim 14, the operations further comprising providing log coordination information pertaining to the storage log to a manager of the logical log through the application programming interface.

17. An apparatus comprising:

a log manager configured to implement log storage operations pertaining to a physical storage log maintained within a physical address space of a non-volatile storage medium, the log manager comprising;

a storage controller configured to implement log storage operations to write data within segments of the physical storage log, each segment of the physical storage log comprising a plurality of physical storage locations of the non-volatile storage medium, and to associate physical storage locations of the data with identifiers of a logical address space,

a groomer configured to implement log storage operations to recover selected segments of the physical storage log, wherein recovering a selected segment comprises erasing the physical storage locations comprising the selected segment of the physical storage log, and

a log coordinator configured to modify implementation of the log storage operations by one or more of the storage controller and the groomer in response to coordination information pertaining to an application log maintained within the logical address space, wherein the log coordinator configures the groomer to pause implementation of log storage operations to recover selected segments of the physical storage log in response to coordination information pertaining to an operation to recover one or more segments of the application log, the segments of the application log comprising respective logical identifiers of the logical address space.

18. The apparatus of claim 17, wherein the log coordinator configures the groomer to resume implementation of log storage operations to recover selected segments of the physical storage log in response to completion of the operation to recover the one or more segments of the application log.

19. An apparatus, comprising:

a log manager configured to implement log storage operations pertaining to a physical storage log maintained within a physical address space of a non-volatile storage medium, the log manager comprising;

a storage controller configured to implement log storage operations to write data within segments of the physical storage log, each segment of the physical storage log comprising a plurality of physical storage locations of the non-volatile storage medium, and to associate physical storage locations of the data with identifiers of a logical address space,

a groomer configured to implement log storage operations to recover selected segments of the physical storage log, wherein recovering a selected segment comprises erasing the physical storage locations comprising the selected segment of the physical storage log, and

a log coordinator configured to modify implementation of the log storage operations by one or more of the storage controller and the groomer in response to coordination information pertaining to an application log maintained within the logical address space, wherein, in response to the coordination information pertaining to the application log, the log coordinator configures the storage controller to;

distinguish data that pertains to the application log from data that does not pertain to the application log;

write data determined to pertain to the application log at a first append point of the physical storage log; and

write data determined to not pertain to the application log at a second append point of the physical storage log, the first append point and the second append point corresponding to different segments of the physical storage log.

20. The apparatus of claim 19, wherein the log coordinator is configured to provide coordination information pertaining to the physical storage log to a client, the provided coordination information indicating one or more of:

a size of a segment of the physical storage log, and a boundary between two or more segments of the physical storage log.