Identification of data with predetermined data pattern

• US 10,282,096 B1
• Filed: 12/17/2014
• Issued: 05/07/2019
• Est. Priority Date: 12/17/2014
• Status: Active Grant

• Current Assignee: JP Morgan Chase Bank, N.A. (JP Morgan Chase & Co)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Boyle, William B.
• Primary Examiner(s): Bragdon, Reginald D
• Assistant Examiner(s): Vo, Thanh D
• Application Number:
  US14/574,123
• Time in Patent Office: 1,602 Days
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 12/0653 with centralised address assignment
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/205 Hybrid memory, e.g. using both volatile and non-volatile memory
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• 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/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

Managing data stored in a Data Storage Device (DSD) including a memory. A translation table is maintained mapping logical addresses for data to physical addresses corresponding to a location where the data is stored in the memory. A data pattern is identified of particular data to be stored in the memory or of particular data already stored in the memory, and it is indicated in the translation table that at least one logical address for the particular data is associated with the data pattern.

Claims

1. A Data Storage Device (DSD), comprising:

a memory for storing data; and

a controller configured to;

identify a data pattern of data stored in the memory during garbage collection in the memory;

receive a write command to store write data including the data pattern previously identified during the garbage collection, the data pattern included in the write data corresponding to at least one logical address;

identify the data pattern in the write data;

consolidate the at least one logical address with one or more other logical addresses in a translation table;

indicate in the translation table that the at least one logical address is associated with the data pattern by associating the at least one logical address for the data pattern in the write data with a predetermined value stored in the translation table, wherein the predetermined value is a physical address beyond a range of available physical addresses for the DSD; and

write the write data without writing the data pattern in the memory to perform the write command.

2. The DSD of claim 1, wherein the controller is further configured to write the data pattern identified during the garbage collection in an area of the memory reserved for storing data patterns.

3. The DSD of claim 1, wherein the controller is further configured to:

generate an entry in the translation table mapping the at least one logical address to the physical address beyond a range of available physical addresses for the DSD.

4. The DSD of claim 1, wherein the write command to store the write data including the data pattern is part of a rebuild process for another DSD in a Redundant Array of Independent Disks (RAID).

5. The DSD of claim 1, wherein the write command to store the write data including the data pattern is part of a formatting process performed by an operating system of a host in communication with the DSD.

6. The DSD of claim 1, wherein the data pattern is stored within an area of the memory reserved for storing data patterns.

7. The DSD of claim 1, wherein the controller is further configured to identify a different data pattern of different data stored in the memory as a part of performing a maintenance operation on the memory.

8. The DSD of claim 7, wherein the maintenance operation is a garbage collection operation for reclaiming portions of the memory storing obsolete data.

9. The DSD of claim 1, wherein the controller is further configured to:

identify data previously stored in the memory that includes the data pattern;

modify the translation table to indicate that at least one physical address for the data previously stored in the memory is available for storing new data; and

associate, in the translation table, one or more logical addresses for the data previously stored in the memory with the data pattern.

10. The DSD of claim 1, wherein the controller is further configured to map a plurality of logical addresses to the data pattern stored in the translation table for additional data including the data pattern.

11. The DSD of claim 1, wherein the DSD further comprises at least one volatile memory configured to include a data pattern buffer and a comparison buffer, and wherein in identifying the data pattern in the write data, the controller is further configured to:

store the data pattern in the data pattern buffer;

store the write data in the comparison buffer; and

compare the data pattern stored in the data pattern buffer with the write data stored in the comparison buffer.

12. The DSD of claim 1, wherein the memory is a rotating magnetic disk.

13. The DSD of claim 1, wherein the memory is a solid-state memory.

14. The DSD of claim 1, wherein the controller is further configured to learn a new data pattern by comparing data stored in the memory with other data stored in the memory.

15. A method of managing data stored in a Data Storage Device (DSD) including a memory, the method comprising:

identifying a data pattern of data stored in the memory during garbage collection in the memory;

receiving a write command to store write data including the data pattern previously identified during the garbage collection, the data pattern included in the write data corresponding to at least one logical address;

identifying the data pattern in the write data;

consolidating the at least one logical address with one or more other logical addresses in a translation table;

indicating in the translation table that the at least one logical address is associated with the data pattern by associating the at least one logical address for the data pattern in the write data with a predetermined value stored in the translation table, wherein the predetermined value is a physical address beyond a range of available physical addresses for the DSD; and

writing the write data without writing the data pattern in the memory to perform the write command.

16. The method of claim 15 further comprising writing the data pattern identified during the garbage collection in an area of the memory reserved for storing data patterns.

17. The method of claim 15, further comprising generating an entry in the translation table mapping the at least one logical address to the physical address beyond a range of available physical addresses for the DSD.

18. The method of claim 15, wherein the write command to store the write data including the data pattern is part of a rebuild process for another DSD in a Redundant Array of Independent Disks (RAID).

19. The method of claim 15, wherein the write command to store the write data including the data pattern is part of a formatting process performed by an operating system of a host in communication with the DSD.

20. The method of claim 15, wherein the data pattern is stored within an area of the memory reserved for storing data patterns.

21. The method of claim 15, further comprising identifying a different data pattern of different data stored in the memory as a part of performing a maintenance operation on the memory.

22. The method of claim 21, wherein the maintenance operation is a garbage collection operation for reclaiming portions of the memory storing obsolete data.

23. The method of claim 15, further comprising:

identifying data previously stored in the memory that includes the data pattern;

modifying the translation table to indicate that at least one physical address for the data previously stored in the memory is available for storing new data; and

associating, in the translation table, one or more logical addresses for the data previously stored in the memory with the data pattern.

24. The method of claim 15, further comprising mapping a plurality of logical addresses to the data pattern stored in the translation table for additional data including the data pattern.

25. The method of claim 15, wherein the DSD further includes at least one volatile memory configured to include a data pattern buffer and a comparison buffer, and wherein in identifying the data pattern in the write data, the method further comprises:

storing the data pattern in the data pattern buffer;

storing the write data in the comparison buffer; and

comparing the data pattern stored in the data pattern buffer with the write data stored in the comparison buffer.

26. The method of claim 15, wherein the memory is a rotating magnetic disk.

27. The method of claim 15, wherein the memory is a solid-state memory.

28. The method of claim 15, further comprising learning a new data pattern by comparing data stored in the memory to other data stored in the memory.

29. A non-transitory computer readable medium storing computer executable instructions for managing data stored in a Data Storage Device (DSD) including a memory, wherein when the computer executable instructions are executed by a controller, the computer executable instructions cause the controller to:

identify a data pattern of data stored in the memory during garbage collection in the memory;

receive a write command to store write data including the data pattern previously identified during the garbage collection, the data pattern included in the write data corresponding to at least one logical address;

identify the data pattern in the write data;

consolidate the at least one logical address with one or more other logical addresses in a translation table;

indicate in the translation table that the at least one logical address is associated with the data pattern by associating the at least one logical address for the data pattern in the write data with a predetermined value stored in the translation table, wherein the predetermined value is a physical address beyond a range of available physical addresses for the DSD; and

write the write data without writing the data pattern in the memory to perform the write command.

30. A Data Storage Device (DSD), comprising:

a memory for storing data; and

a controller configured to;

receive a write command to store write data including particular data, wherein the write command is part of a rebuild process for another DSD in a Redundant Array of Independent Disks (RAID);

identify a data pattern in the particular data of the write data, the data pattern in the particular data corresponding to at least one logical address;

consolidate the at least one logical address with one or more other logical addresses in a translation table;

indicate in the translation table that the at least one logical address is associated with the data pattern by associating the at least one logical address for the data pattern in the write data with a predetermined value stored in the translation table, wherein the predetermined value is a physical address beyond a range of available physical addresses for the DSD; and

write the write data without writing the particular data in the memory to perform the write command.

31. The DSD of claim 30, wherein the data pattern is stored in an area of the memory reserved for storing data patterns.

32. The DSD of claim 30, wherein the DSD further comprises at least one volatile memory configured to include a data pattern buffer and a comparison buffer, and wherein in identifying the data pattern in the particular data, the controller is further configured to:

store the data pattern in the data pattern buffer;

store the particular data in the comparison buffer; and

compare the data pattern stored in the data pattern buffer with the particular data stored in the comparison buffer.

33. The DSD of claim 30, wherein the controller is further configured to learn a new data pattern by comparing data stored in the memory with other data stored in the memory.

34. The DSD of claim 33, wherein the controller is further configured to learn the new data pattern when performing a maintenance operation.