Granted Patent B2

US 9,342,256 · App. 13/831,448 · Granted May 17, 2016

Inventors: James G. Peterson (San Jose, CA); Nisha Talagala (Livermore, CA); Swaminathan Sundararaman (San Jose, CA); Sriram Subramanian (San Jose, CA)

Assignee: SANDISK TECHNOLOGIES, INC.

G06F3/065G06F3/0619G06F3/0688G06F11/1402G06F17/30088

Abstract

Claims (57)

1. A method, comprising:

maintaining, by a computing system, information that indicates the state of data associated with an application at a particular point in time;

assigning, by the computing system, an epoch number to a current epoch, wherein the current epoch is an interval between the particular point in time and a future point in time;

writing, by the computing system during the current epoch, a block of data to the storage device using a logical address, wherein the writing includes storing the epoch number in the same page as the block of data and wherein one or more bits of the logical address encode the epoch number.

2. The method of claim 1 , further comprising:

associating, by the computing system, a logical address range with the epoch number;

translating, by the computing system, an address of a storage request from the application during the current epoch to a logical address within the logical address range; and

storing, by the computing system, the logical address with the block of data.

3. The method of claim 2 , further comprising:

the computing system providing a logical address space for a storage device on which the block of data is stored, wherein the logical address space is larger than a physical address space of the storage device, wherein the logical address range is part of the logical address space.

4. The method of claim 1 , wherein a size of the block of data is a smallest addressable unit for a storage device to which the block is written.

5. The method of claim 1 , wherein the information includes snapshot data for a snapshot that shares a common ancestor snapshot with one or more other snapshots.

6. The method of claim 1 , further comprising:

servicing a read request during the current epoch by providing data written to a storage device during a previous epoch.

7. The method of claim 1 , further comprising:

performing a storage request that is associated with the epoch number by:

determining an entry in a forward mapping structure based on the epoch number; and

translating a logical address of the storage request to a physical address of a storage device using the entry.

8. The method of claim 1 , further comprising:

receiving a storage request and an epoch number associated with the storage request; and

applying an offset to an address of the storage request based on the epoch number.

9. The method of claim 1 , further comprising:

merging, after an end of the current epoch, the information with other information that indicates the state of data at the beginning of a later epoch, wherein the merging includes associating data written during the current epoch with an epoch number of the later epoch.

10. The method of claim 1 , further comprising:

reconstructing a data structure that indicates parent-child relationships between one or more snapshots based on the epoch number stored with the block of data.

11. An apparatus, comprising:

an association module configured to associate a logical address range for a storage device with an epoch number, wherein the epoch number is associated with write operations to the storage device during a particular epoch; and

a storage module configured to service one or more storage operations associated with the epoch number using the logical address range, wherein one or more bits of logical addresses in the logical address range encode the epoch number of the particular epoch,

wherein at least a portion of the association module and storage module comprise one or more of a hardware circuit and program instructions stored on one or more non-transitory computer readable media.

12. The apparatus of claim 11 , wherein the storage module is further configured to:

perform a write operation that includes writing a block of data to the storage device including storing the epoch number on the storage device in the same erase block as the block of data.

13. The apparatus of claim 11 , wherein the storage module is further configured to:

perform a read operation using a different logical address range associated with an epoch number of a previous epoch in response to determining that the read operation is for data written during the previous epoch; and

translate a logical address within the different address range to a physical address of the storage device to perform the read operation.

14. The apparatus of claim 11 , wherein the storage module is further configured to:

perform a write operation to a logical address in the logical address range; and

indicate that the logical address is associated with valid data for the particular epoch.

15. The apparatus of claim 11 , wherein the storage module is further configured to:

delete data associated with the particular epoch by issuing a trim command for the logical address range.

16. A non-transitory computer readable medium having program instructions stored thereon, wherein the program instructions are executable by a computing system to cause the computing system to perform operations comprising:

configuring a storage device such that the storage device has a logical address space that is larger than a physical address space of the storage device;

performing a first write operation during a first epoch using a first logical address range within the logical address space, wherein one or more bits of logical addresses in the first logical address range encode a first epoch number; and

performing a second write operation during a second, later epoch using a second logical address range within the logical address space, wherein one or more bits of logical addresses in the second logical address range encode a second epoch number.

17. The non-transitory computer-readable storage medium of claim 16 ,

wherein the performing the first write operation during the first epoch includes storing an epoch number associated with the first epoch and a first logical address on the storage device at a location associated with the write operation, wherein the first logical address is within the first logical address range.

18. The non-transitory computer-readable storage medium of claim 16 , wherein the operations further comprise:

applying an offset to an address of a storage request based on an epoch number provided with the storage request, wherein applying the offset provides a new logical address.

19. The non-transitory computer-readable storage medium of claim 16 , wherein the operations further comprise:

receiving a read request during the second epoch;

determining that a logical address for the read request in the second logical address range does not have a valid translation to a physical address; and

in response to the determining, servicing the read request using data from a physical location mapped to a logical address in the first address range.

20. The non-transitory computer-readable storage medium of claim 16 , wherein the operations further comprise:

handling storage requests to the storage device using a strict log structure.

21. An apparatus, comprising:

a first means for determining a logical address for a write operation based a current epoch number, wherein one or more bits of the logical address encode the current epoch number;

a second means for translating the logical address to a physical address on a storage device; and

a third means for storing the current epoch number on the storage device, wherein storing the current epoch number comprises storing the current epoch number at the same physical location as a target of the write operation.

Assignments (9)

Continuity (1)