Physical media aware spacially coupled journaling and replay

• US 10,540,102 B2
• Filed: 09/30/2016
• Issued: 01/21/2020
• Est. Priority Date: 09/30/2016
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Peterson, Phillip, Baryudin, Leonid, Sladic, Daniel, Biswas, Sujan
• Primary Examiner(s): Guyton, Philip
• Application Number:
  US15/282,295
• Publication Number:
  US 20180095680A1
• Time in Patent Office: 1,208 Days
• CPC Class Codes: G06F 11/1008 in individual solid state devices G06F11/1004 takes precedence
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/10 Address translation
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7202 Allocation control and policies
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 2212/7208 Multiple device management, e.g. distributing data over multiple flash devices
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• 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/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G11C 2029/4402 Internal storage of test result, quality data, chip identification, repair information
• CPC Class Codes: G11C 29/765 in solid state disks

Abstract

An indirection mapping data structure can maintain a mapping between logical block addresses used by a host computer and physical data storage locations on a solid state drive. Changes to the indirection mapping data structure can be stored in journals. When a journal is full, the journal can be stored to a predetermined location on the cluster block determined based on the number of entries stored by the journal, leading to a number of journals scattered throughout the cluster block at predetermined locations. Each physical chunk of media, whether written with data or marked as defective is journaled. Such a journaling scheme, where the journal locations are predetermined and each physical chunk of media is journaled is referred to as physical media-aware spatially coupled journaling. During replay the spatially coupled journals can be retrieved from the predefined locations within cluster blocks and used to rebuild the indirection mapping data structure.

Claims

1. A computer-implemented method, comprising:

storing an indirection mapping table for a solid state drive (SSD) in memory, the indirection mapping table including a plurality of indirection units that map physical data locations on the SSD to logical addresses used by a host computer;

receiving a write request from the host computer to store data to the SSD;

storing the data to a physical data location in a cluster block on the SSD;

storing an indirection unit mapping the data to the physical data location in the cluster block on the SSD in the indirection mapping table;

generating an entry to a journal using the indirection unit, the journal including a plurality of entries corresponding to a fixed amount of disk space on the SSD, at least one entry from the plurality of entries indicating a corresponding physical data location on the SSD is defective;

determining the journal includes a maximum number of journal entries;

storing the journal to a predetermined location on the SSD, the predetermined location co-located immediately after the data it describes in the cluster block;

determining power has been restored after a power outage has occurred;

generating a new indirection mapping table using at least the journal stored at the predetermined location on the SSD; and

generating a bad block map using at least the journal stored at the predetermined location.

2. The computer-implemented method of claim 1, further comprising:

receiving a subsequent write request;

determining a physical data location on the SSD corresponding to the subsequent write request is defective; and

generating a subsequent entry to the journal including a bad block value that indicates the physical data location corresponding to the subsequent write request is defective.

3. The computer-implemented method of claim 1, wherein the journal includes a header including a cluster block sequence number for the cluster block, and a content area including a plurality of entries mapping physical data locations of data on the cluster block to logical addresses.

4. The computer-implemented method of claim 1, wherein the data is stored to the SSD in a multi-level cell or triple level cell mode, and the journal is stored to the SSD in a single level cell mode.

5. A computer-implemented method, comprising:

receiving a write request to store data to a solid state drive (SSD);

storing the data to a physical data location in a cluster block on the SSD;

updating an indirection mapping table based at least in part on the write request, the indirection mapping table mapping physical data locations on the SSD to logical addresses;

generating an entry to a journal based at least in part on the write request;

detecting a journal storage event;

storing the journal to a predetermined location on the SSD, wherein the predetermined location causes the stored journal to be co-located with the data it describes in the cluster block, and wherein the storing the journal is based at least in part on the number of entries stored by the journal; and

generating a new indirection mapping table using at least the journal stored at the predetermined location.

6. The computer-implemented method of claim 5, wherein each entry to the journal corresponds to a fixed amount of disk space and the journal is associated with a corresponding maximum number of entries, and wherein detecting a journal storage event includes:

determining the maximum number of journal entries have been written to the journal.

7. The computer-implemented method of claim 5, wherein each entry to the journal corresponds to a variable amount of disk space, and wherein detecting a journal storage event includes:

determining the journal includes a number of entries corresponding to a predetermined amount of disk space on the SSD.

8. The computer-implemented method of claim 5, wherein each journal includes a header including a cluster block sequence number for a cluster block being written, and a content area, including a plurality of entries mapping physical locations of data on the cluster block to the logical addresses.

9. The computer-implemented method of claim 5, further comprising:

receiving a subsequent write request;

determining a physical location on the SSD corresponding to the subsequent write request is defective; and

generating a subsequent entry to the journal including a bad block value that indicates the physical location corresponding to the subsequent write request is defective.

10. The computer-implemented method of claim 5, further comprising:

detecting a replay event;

retrieving a plurality of journals from a plurality of predetermined locations; and

generating a bad block map based at least on the plurality of journals.

11. The computer-implemented method of claim 9, wherein retrieving a plurality of journals from a plurality of predetermined locations further comprises:

retrieving a journal from each cluster block at a first predetermined location; and

determining a cluster block sequence using the journal from each cluster block.

12. The computer-implemented method of claim 9, wherein generating a bad block map based on the plurality of journals further comprises:

storing a bad block map in memory, the bad block map including at least one physical location on the SSD that is defective;

determining a journal entry includes a bad block value; and

updating the bad block map based on the journal entry, including a physical location on the SSD corresponding to the journal entry.

13. The computer-implemented method of claim 5, further comprising:

writing the data to the SSD in a multi-level cell or triple level cell mode.

14. The computer-implemented method of claim 13, wherein storing the journal to a predetermined location on the SSD further comprises:

writing the journal to the predetermined location on the SSD in a single level cell mode.

15. A system, comprising:

at least one processor; and

memory including instructions that, when executed by the at least one processor, cause the system to;

receive a write request to store data to a solid state drive (SSD);

store the data to a physical data location in a cluster block on the SSD;

update an indirection mapping table based at least in part on the write request, the indirection mapping table mapping physical data locations on the SSD to logical addresses;

generate an entry to a journal based at least in part on the write request;

detect a journal storage event;

store the journal to a predetermined location on the SSD, wherein the predetermined location causes the stored journal to be co-located with the data it describes in the cluster block, and wherein the storing the journal is based at least in part on the number of entries stored by the journal; and

generate a new indirection mapping table using at least the journal stored at the predetermined location.

16. The system of claim 15, wherein each entry to the journal corresponds to a fixed amount of physical storage space and the journal is associated with a corresponding maximum number of entries, and wherein the instructions to detect a journal storage event when executed further cause the system to:

determine the maximum number of journal entries have been written to the journal.

17. The system of claim 15, wherein each entry to the journal corresponds to a variable amount of disk space, and wherein the instructions to detect a journal storage event when executed further cause the system to:

determine the journal includes a number of entries corresponding to a predetermined amount of disk space on the SSD.

18. The system of claim 15, wherein the instructions when executed further cause the system to:

determine, upon receiving a subsequent write request, a physical location on the SSD corresponding to the subsequent write request is defective; and

generate a subsequent entry to the journal including a bad block value that indicates the physical location corresponding to the subsequent write request is defective.