Systems and methods for contextual storage

• US 9,250,817 B2
• Filed: 09/18/2013
• Issued: 02/02/2016
• Est. Priority Date: 03/18/2011
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Sandisk Technologies Incorporated (Western Digital Corporation)
• Inventors: Flynn, David, Wipfel, Robert, Nellans, David, Strasser, John
• Primary Examiner(s): Chery, Mardochee
• Application Number:
  US14/030,717
• Publication Number:
  US 20140025872A1
• Time in Patent Office: 867 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/00 Accessing, addressing or allocating within memory systems or architectures digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 13/16 for access to memory bus G06F13/28 takes precedence
• 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/0629 Configuration or reconfiguration of storage systems
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0634 by changing the state or mode of one or more devices
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/065 Replication mechanisms
• 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
• CPC Class Codes: G11C 16/06 Auxiliary circuits, e.g. for writing into memory

Abstract

A storage layer presents logical address space of a non-volatile storage device. The storage layer maintains logical interfaces to the non-volatile storage device, which may include arbitrary, any-to-any mappings between logical identifiers and storage resources. Data may be stored on the non-volatile storage device in a contextual format, which includes persistent metadata that defines the logical interface of the data. The storage layer may modify the logical interface of data that is stored in the contextual format. The modified logical interface may be inconsistent with the existing contextual format of the data on the non-volatile storage media. The storage layer may provide access to the data in the inconsistent contextual format through the modified logical interface. The contextual format of the data may be updated to be consistent with the modified logical interface in a write out-of-place storage operation.

Claims

1. A method, comprising:

performing a logical copy operation pertaining to a plurality of data segments stored on a non-volatile storage device to reference the stored data segments through a first set of logical addresses of a logical address space and a second, different set of logical addresses of the same logical address space;

servicing a request to revise data of a stored data segment, wherein the stored data segment is referenced by a first logical address in the first set of logical addresses and a second logical address in the second set of logical addresses, and wherein servicing the request comprises writing at least the revised data to a different data segment on the non-volatile storage device; and

referencing the stored data segment through the first logical address and referencing the different data segment through the second logical address after servicing the request.

2. The method of claim 1, wherein the plurality of data segments are stored within a log on the non-volatile storage device, and wherein writing the revised data comprises appending the different data segment to the log, such that the log comprises both the stored data segment and the different data segment.

3. The method of claim 1, wherein performing the logical copy operation comprises storing a persistent note on the non-volatile storage device configured to associate the plurality of data segments stored on the non-volatile storage device with the first set of logical identifiers and the second set of logical identifiers.

4. The method of claim 3, wherein both the first set of logical identifiers and the second set of logical identifiers reference the plurality of data segments through one or more reference entries, and wherein the persistent note is configured to bind the first set of logical identifiers and the second set of logical identifiers to the reference entries.

5. The method of claim 3, wherein the persistent note is configured to associate physical addresses of the plurality of data segments on the non-volatile storage device with the first set of logical identifiers and the second set of logical identifiers.

6. The method of claim 3, further comprising reconstructing associations between the plurality of data segments stored on the non-volatile storage device and the first set of logical identifiers and the second set of logical identifiers by use of the persistent note.

7. The method of claim 1, further comprising rewriting the plurality of data segments on the non-volatile storage device in a contextual format configured to associate the plurality of data segments with logical identifiers of the first set of logical identifiers and logical identifiers of the second set of logical identifiers.

8. The method of claim 7, wherein rewriting the plurality of data segments comprises rewriting the data segments in respective packets, the packets comprising persistent metadata configured to reference logical identifiers of both the first set of logical identifiers and the second set of logical identifiers.

9. An apparatus, comprising:

a storage layer configured to manage a logical copy of data stored within an ordered log on a non-volatile storage device, such that the stored data is mapped to a first set of logical identifiers and to a second, different set of logical identifiers of a logical address space; and

a log storage module configured to append data corresponding to the first logical identifier to the ordered log in response to a write request pertaining to a first logical identifier in the first set, wherein the appended data is configured to modify a portion of the stored data mapped to a second logical identifier in the second set of logical identifiers, and

wherein the storage layer is configured to map the first logical identifier to the appended data and to retain a mapping between the second logical identifier of the second set of logical identifiers and the stored data.

10. The apparatus of claim 9, wherein the log storage module is further configured to append persistent metadata to the ordered log on the non-volatile storage device, and wherein the persistent metadata is configured to associate the data stored within the ordered log on the non-volatile storage device with the second set of logical identifiers.

11. The apparatus of claim 10, wherein the storage layer is configured to invalidate the persistent metadata in response to rewriting the data in a contextual format that associates the data with the first set of logical identifiers and the second set of logical identifiers.

12. The apparatus of claim 10, wherein the data is stored in a contextual format configured to associate the data with an original set of logical identifiers, and wherein the persistent metadata is configured to bind physical addresses of the data on the non-volatile storage device to logical identifiers of both the original set of logical identifiers and one or more other, different sets of logical identifiers.

13. The apparatus of claim 9, wherein the storage layer is configured to reference the data through two or more entries in an index, including a first entry and a second entry, and wherein both the first entry and the second entry are configured to reference physical storage locations of the data through a reference entry.

14. The apparatus of claim 13, wherein the storage layer is configured to bind the first logical identifier to a physical storage location of the appended data by use of an entry in the index, and to retain a binding between the portion of the data modified by the appended data and another logical identifier.

15. A non-transitory computer-readable storage medium comprising instructions configured to cause a machine to perform operations, comprising:

storing a set of data segments on a non-volatile storage device with persistent metadata configured to associate the stored data segments with respective logical addresses of a logical address space;

modifying a logical interface of the data segments to provide access to the set of stored data segments through two or more different groups of logical addresses, wherein the two or more different groups of logical addresses correspond to a particular logical address space;

writing a modified data segment to the non-volatile storage device with persistent metadata configured to associate the written data segment with a logical address of a first one of the two or more groups of logical addresses, wherein the written data segment is configured to replace a selected one of the set of stored data segments; and

providing access to the written data segment through the logical address of the first group of logical addresses, and to the selected stored data segment through a logical identifier of a different one of the two or more groups of logical addresses.

16. The non-transitory computer-readable storage medium of claim 15, wherein the operations further comprise storing a persistent note on the non-volatile storage device configured to associate the set of stored data segments with the two or more groups of logical addresses.

17. The non-transitory computer-readable storage medium of claim 15, wherein the set of stored data segments are stored within an ordered log on the non-volatile storage device, and wherein writing the modified data segment comprises appending the modified data segment at an append point within the log and at a different physical address than a physical address of the selected stored data segment.

18. The non-transitory computer-readable storage medium of claim 15, wherein logical addresses of the first group of logical addresses reference physical addresses of one or more of the stored data segments in the set of data segments.

19. The non-transitory computer-readable storage medium of claim 15, the operations further comprising modifying the logical interface of the set of stored data segments in response to a request to create a logical copy of the stored data segments.

20. The non-transitory computer-readable storage medium of claim 15, the operations further comprising rewriting one or more of the stored data segments in the set of stored data segments in a packet format configured to bind the one or more rewritten data segments to logical addresses in the two or more groups of logical addresses.