Data journaling for large solid state storage devices with low DRAM/SRAM

• US 10,635,654 B2
• Filed: 06/12/2017
• Issued: 04/28/2020
• Est. Priority Date: 06/12/2017
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Hof, Eran, Erlihson, Michael, Dashevsky, Shmuel, Kong, Jun Jin
• Primary Examiner(s): Lane, John A
• Application Number:
  US15/619,981
• Publication Number:
  US 20180357268A1
• Time in Patent Office: 1,051 Days
• Field of Search: None
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/2358 Change logging, detection, and notification replication G06F16/27
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data

Abstract

A data journaling method in a solid state storage device, the method including: receiving a read request; determining whether updated data mapping for the read request is located in at least one of a volatile journal and a nonvolatile journal using a Bloom filter; searching the volatile journal if the updated data mapping for the request is located in the Bloom filter, and then, searching the nonvolatile journal if the updated data mapping for the request is not found in the volatile journal; and stopping the search when the updated data mapping is found.

Claims

1. A data journaling method in a solid state storage device, the method comprising:

receiving a read request;

determining if a journal commit process is taking place;

determining, when the journal commit process is taking place, whether updated data mapping for the read request is located in at least one of a volatile journal and nonvolatile journal using a Bloom filter;

searching the volatile journal if the updated data mapping for the request is located by the Bloom filter and then, searching the nonvolatile journal if the updated data mapping for the request is not found in the volatile journal; and

stopping the search when the updated data mapping is found.

2. The method of claim 1, wherein the Bloom filter is stored in volatile memory.

3. The method of claim 2, wherein the volatile memory is random access memory.

4. The method of claim 1, further comprising, for each entry written to the volatile journal, adding its write host address to the Bloom filter to indicate that its updated data mapping resides in the volatile journal or the nonvolatile journal.

5. The method of claim 1, further comprising searching a logical-to-physical mapping page on a nonvolatile metadata page for the updated data mapping when the Bloom filter returns a false positive.

6. The method of claim 5, wherein the metadata page is stored in NAND flash memory.

7. The method of claim 1, wherein prior to searching the nonvolatile journal, the method further comprises searching another Bloom filter to find a read address corresponding to the read request.

8. A data journaling method in a solid state storage device, the method comprising:

receiving a read request;

determining, when a journal commit process is taking place, whether updated data mapping for the read request is located in a given set using a Bloom filter that stores for every write journal entry, its logical block address; and

searching a metadata page if the updated data mapping for the request is not located by the Bloom filter.

9. A data journaling method in a solid state storage device, the method comprising:

receiving a read request;

determining, when a journal commit process is taking place, whether updated data mapping for the read request in located in a first dataset using a first Bloom filter; and

searching a volatile journal if the updated data mapping for the read request is located by the first Bloom filter.

10. The method of claim 9, further comprising determining whether the updated data mapping for the read request is located in a second dataset by using a second Bloom filter if the volatile journal does not contain the updated mapping for the read request, or if the first Bloom filter does not find the updated data mapping for the read request.

11. The method of claim 10, further comprising parsing a journal if the second Bloom filter finds the updated data mapping for the read request and stopping the search when the updated data mapping is found.

12. The method of claim 10, further comprising:

parsing a journal if the second Bloom filter finds the updated data mapping for the read request; and

if the updated data mapping is not found, reading the updated data mapping from a metadata page in nonvolatile memory.

13. The method of claim 10, further comprising reading the updated data mapping from a metadata page in nonvolatile memory if the second Bloom filter does not contain the updated data mapping for the read request.

14. The method of claim 9, further comprising adding new items to the first Bloom filter during the journal commit process.

15. The method of claim 9, wherein a second Bloom filter is only used when the journal commit process is not taking place, the method further comprising:

after the journal commit process is finished, deleting the second Bloom filter and replacing the second Bloom filter with the first Bloom filter.