Granted Patent B2

US 10,990,316 · App. 16/457,298 · Granted Apr 27, 2021

Inventors: Mikhael Zaidman (Modiin, IL); Yonatan Halevi (Petah Tikva, IL); Judah Gamliel Hahn (Ofra, IL); Arseniy Aharonov (Rehovot, IL); Yoav Markus (Tel Aviv, IL)

Assignee: Western Digital Technologies, Inc.

G06F3/0652G06F3/0619G06F3/0679G06F16/1734G06F16/907

Abstract

Claims (71)

1. An apparatus comprising a processor having programmed instructions that:

write data having mixed data types sequentially to a plurality of data entries of a first physical erase block (PEB) in intermediate storage, wherein the data having the mixed data types includes first data having a first data type;

maintain metadata in a plurality of metadata entries in a log, wherein the metadata corresponds to the data having the mixed data types;

scan a window of the plurality of metadata entries starting with an oldest valid metadata entry;

select the first data having the first data type responsive to the first data corresponding to a largest number of metadata entries in the window of the plurality of metadata entries;

and

evacuate the first data having the first data type to a second PEB in main memory responsive to the selection.

2. The apparatus of claim 1 , the processor having further programmed instructions that:

determine that the second PEB is open and is assigned to any data having the first data type as a condition to write the first data to the second PEB.

3. The apparatus of claim 1 , the processor having further programmed instructions that, responsive to evacuating data corresponding to the oldest valid metadata entry, shift the window such that the window starts with a next oldest valid metadata entry.

4. The apparatus of claim 1 , the processor having further programmed instructions that:

determine that data corresponding to the first data type is evacuated from the first PEB;

determine that the second PEB is closed;

identify a third PEB in main memory that is open;

select a second data type corresponding to second data and corresponding to an updated largest number of metadata entries in the window of the plurality of metadata entries; and

write the second data to the third PEB.

5. The apparatus of claim 1 , wherein the plurality of metadata entries includes a first metadata entry and a second metadata entry adjacent to the first metadata entry, wherein the processor has further programmed instructions that:

determine that the first metadata entry and the second metadata entry have a same data type; and

concatenate the first metadata entry and the second metadata entry.

6. The apparatus of claim 1 , wherein the log includes a first log in flash memory and a second log in random-access memory (RAM), wherein the plurality of metadata entries include a plurality of first metadata entries in the flash memory and a plurality of second metadata entries in the RAM, wherein the metadata includes first metadata and second metadata, wherein the processor has further programmed instructions that:

write the metadata to the first metadata entries; and

write the first metadata to the second metadata entries.

7. The apparatus of claim 6 , wherein the data having mixed data types includes second data corresponding to the first metadata, wherein the processor has further programmed instructions that:

evacuate the second data corresponding to the first metadata; and

write the second metadata to the second metadata entries.

8. The apparatus of claim 1 , the processor having further programmed instructions that:

determine that a first portion of the plurality of data entries of the first PEB are evacuated to the main memory; and

erase the first PEB.

9. The apparatus of claim 8 , the processor having further programmed instructions that maintains a plurality of input/output (I/O) type identifiers including a write I/O type identifier, wherein the first portion of the plurality of data entries of the first PEB corresponds with the write I/O type identifier.

10. The apparatus of claim 1 , wherein:

the data types comprise different deletion characteristics; and

the first data type comprises a first deletion characteristic.

11. The apparatus of claim 1 , wherein the data types describe a frequency at which the data corresponding to the data types is updated and/or deleted.

12. A system comprising:

a hosts log history (HLH) log; and

a controller coupled to the HLH log, wherein the controller:

writes data having mixed deletion characteristics sequentially to a plurality of data entries of a first physical erase block (PEB) in intermediate storage, wherein the data having the mixed deletion characteristics includes first data having a first deletion characteristic;

maintains metadata in a plurality of metadata entries in the HLH log, wherein the metadata corresponds to the data having the mixed deletion characteristics, wherein the plurality of metadata entries includes a first metadata entry and a second metadata entry adjacent to the first metadata entry;

concatenates the first metadata entry and the second metadata entry responsive to a determination that the first metadata entry and the second metadata entry have a same deletion characteristic;

identifies, using the HLH log, the first data having the first deletion characteristic; and

evacuates the first data having the first deletion characteristic to a second PEB in main memory.

13. The system of claim 12 , wherein the controller:

maintains a plurality of log identifiers (IDs) identifying different deletion characteristics;

selects a first log ID of the plurality of log IDs, wherein the first log ID identifies the first deletion characteristic corresponding to the first data;

determines that the second PEB is open and is assigned to any data having the first deletion characteristic; and

writes the first data to the second PEB.

14. The system of claim 13 , wherein the controller:

scans a window of the plurality of metadata entries starting with an oldest valid metadata entry; and

selects the first log ID responsive to the first log ID corresponding to a largest number of metadata entries in the window of the plurality of metadata entries.

15. The system of claim 14 , wherein the controller, responsive to evacuating data corresponding to the oldest valid metadata entry, shifts the window such that the window starts with a next oldest valid metadata entry.

16. The system of claim 14 , wherein the controller:

determines that all data corresponding to the first log ID is evacuated;

selects a second log ID, wherein the second log ID identifies a second deletion characteristic corresponding to second data; and

writes the second data to the second PEB.

17. A method comprising:

writing, by a controller, data having mixed deletion characteristics sequentially to a plurality of data entries of a first physical erase block (PEB) in intermediate storage, wherein the data having the mixed deletion characteristics includes first data having a first deletion characteristic;

maintaining, by the controller, metadata in a plurality of metadata entries in a log, wherein the metadata corresponds to the data having the mixed deletion characteristics, including maintaining a plurality of log identifiers (IDs) identifying different deletion characteristics;

computing, by the controller, a data payload for each log ID in a window of the plurality of metadata entries that starts with an oldest valid metadata entry, wherein computing the data payload for a respective log ID comprises summing data entries in the first PEB that are pointed to by the metadata entries having the respective log ID;

selecting, by the controller, the first data in the first PEB responsive to a first log ID identifying the first deletion characteristic corresponding to a largest data payload;

and

evacuating, by the controller, the first data having the first deletion characteristic to a second PEB in main memory responsive to the selection.

18. The method of claim 17 , further comprising:

determining, by the controller, that the second PEB is open and is assigned to any data having the first deletion characteristic; and

wherein evacuating, by the controller, the first data having the first to a second PEB in main memory comprises writing the first data to the second PEB.

19. The method of claim 17 , further comprising, responsive to evacuating data corresponding to the oldest valid metadata entry, shifting, by the controller, the window such that the window starts with a next oldest valid metadata entry.

20. The method of claim 17 , further comprising:

determining, by the controller, that data corresponding to the first log ID is evacuated;

determining, by the controller, that the second PEB is closed;

identifying, by the controller, a third PEB in main memory that is open;

selecting, by the controller, a second log ID, wherein the second log ID identifies a second deletion characteristic corresponding to second data and corresponding to an updated largest number of metadata entries in the window of the plurality of metadata entries; and

write the second data to the third PEB.

Assignments (8)

Continuity (1)