PHYSICAL MEDIA AWARE SPACIALLY COUPLED JOURNALING AND REPLAY

• US 20200133519A1
• Filed: 12/26/2019
• Published: 04/30/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
• Granted Patent: US 11,481,121 B2
• Time in Patent Office: 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:

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

updating a mapping table, the 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 request; and

storing, based at least in part on a number of entries stored by the journal, the journal to a predetermined location.

2. The computer-implemented method of claim 1, wherein the journal is co-located with data described by the journal.

3. The computer-implemented method of claim 1, wherein each entry to the journal corresponds to a fixed amount of SSD space.

4. The computer-implemented method of claim 1, wherein each entry to the journal corresponds to a variable amount of disk space, and further comprising detecting a journal storage event, the detecting a journal storage event including:

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

5. The computer-implemented method of claim 1, wherein each journal includes a header including a cluster block sequence number and a content area.

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

receiving a subsequent request;

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

generating a subsequent entry to the journal including a bad block value.

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

detecting a replay event;

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

rebuilding the mapping table based on the plurality of journals; and

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

8. The computer-implemented method of claim 7, 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.

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

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

10. 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 request to store data to a solid state drive (SSD);

update a mapping table, the 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 request; and

store, based at least in part on a number of entries stored by the journal, the journal to a predetermined location.

11. The system of claim 10, wherein the journal is co-located with data described by the journal.

12. The system of claim 10, wherein each entry to the journal corresponds to a fixed amount of SSD space.

13. The system of claim 10, wherein the instructions, when executed by the at least one processor, further cause the system to:

detect a journal storage event, the detecting a journal storage event including;

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

14. The system of claim 10, wherein each journal includes a header including a cluster block sequence number and a content area.

15. The system of claim 10, wherein the instructions, when executed by the at least one processor, further cause the system to:

receive a subsequent request;

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

generate a subsequent entry to the journal including a bad block value.

16. The system of claim 10, wherein the instructions, when executed by the at least one processor, further cause the system to:

detect a replay event;

retrieve a plurality of journals from a plurality of predetermined locations;

rebuild the mapping table based on the plurality of journals; and

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

17. A non-transitory computer-readable storage medium storing instructions that, when executed by at least one processor of a computing device, cause the computing device to:

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

update a mapping table, the 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 request; and

store, based at least in part on a number of entries stored by the journal, the journal to a predetermined location.

18. The non-transitory computer-readable storage medium of claim 17, wherein the instructions, when executed, further cause the computing device to:

detect a replay event;

retrieve plurality of journals from a plurality of predetermined locations;

rebuild the mapping table based on the plurality of journals; and

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

19. The non-transitory computer-readable storage medium of claim 18, wherein the instructions, when executed, further cause the computing device to:

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

determine a journal entry includes a bad block value; and

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

20. The non-transitory computer-readable storage medium of claim 17, wherein the instructions, when executed, cause the computing device to:

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