PHYSICAL COMPRESSION OF DATA WITH FLAT OR SYSTEMATIC PATTERN

• US 20110161559A1
• Filed: 12/31/2009
• Published: 06/30/2011
• Est. Priority Date: 12/31/2009
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Sandisk Technologies Incorporated (Western Digital Corporation)
• Inventors: Yurzola, Damian P., Gorobets, Sergei A., Hutchison, Neil D., Erez, Eran
• Granted Patent: US 9,134,918 B2
• Time in Patent Office: Days
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 2212/7209 Validity control, e.g. using flags, time stamps or sequence numbers
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0616 in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

Abstract

Systems and methods are disclosed to improve the performance of a memory system by freeing up physical memory areas that correspond to logical block address ranges that have repeated data patterns. A controller detects data patterns in incoming data. When a data pattern is detected, the data is not written to non-volatile storage area. Rather, the logical block address range of the data is marked in a data structure as having pattern data. The pattern may also be recorded in the data structure as a pattern descriptor. Because the data having the data pattern is not written to the non-volatile storage area, the freed up corresponding physical memory area may be utilized by the memory system for other purposes, thereby improving the overall performance and endurance of the memory system.

Claims

1. A method for compressing data written to a non-volatile memory system, the method comprising a controller of the memory system:

receiving the data from a host;

detecting a repeated pattern in the data;

recording in a data structure a logical block address range of data having the repeated pattern without writing the data having the repeated pattern to non-volatile memory; and

marking the logical block address range in the data structure as having pattern data.

2. The method of claim 1 wherein the data structure is one of:

an erased fragment descriptor, an erased command log, a binary cache, or a group address table.

3. The method of claim 2 further comprising the controller of the memory system recording a pattern descriptor of the pattern data in one of the erased fragment descriptor, the erased command log, the binary cache, or the group address table.

4. The method of claim 1, wherein the repeated pattern in the data is detected by the controller of the memory system comparing data portions in the data with one another.

5. The method of claim 4 wherein the data portions are compared by an XOR operation between successive data portions.

6. The method of claim 1 further comprising the controller of the memory system:

recording in the data structure a plurality of logical block address ranges of data received from the host; and

marking the plurality of logical block address ranges in the data structure as having pattern data.

7. The method of claim 6 further comprising the controller of the memory system:

issuing a physical erase of the plurality of logical block address ranges if it is determined that the plurality of logical block address ranges spans an entire logical group.

8. The method of claim 7 wherein the logical group is a metablock.

9. The method of claim 1 further comprising the controller of the memory system utilizing an area of physical memory corresponding to the logical block address range as at least one of a binary cache, an update block, a spare block in a block pool, or an index table.

10. The method of claim 1 further comprising the controller of the memory system detecting a repeated pattern in the data by monitoring the data as the data is received from the host.

11. A non-volatile memory system comprising:

a data structure; and

a controller configured to;

receive data from a host;

detect a repeated pattern in the data;

record in the data structure a logical block address range of data having the repeated pattern without writing the data having the repeated pattern to non-volatile memory; and

mark the logical block address range in the data structure as having pattern data.

12. The non-volatile memory system of claim 11 wherein the data structure is one of:

an erased fragment descriptor, an erased command log, a binary cache, or a group address table.

13. The non-volatile memory system of claim 12 wherein the controller is configured to record a pattern descriptor of the pattern data in one of the erased fragment descriptor, the erased command log, the binary cache, or the group address table.

14. The non-volatile memory system of claim 11, wherein the controller is configured to compare data portions in the data with one another to detect the repeated pattern in the data.

15. The non-volatile memory system of claim 14 wherein the controller is configured to compare the data portions by an XOR operation between successive data portions.

16. The non-volatile memory system of claim 11 wherein the controller is configured to:

record in the data structure a plurality of logical block address ranges of data received from the host; and

mark the plurality of logical block address ranges in the data structure as having pattern data.

17. The non-volatile memory system of claim 16 wherein the controller is configured to issue a physical erase of the plurality of logical block address ranges if the controller determines that the plurality of logical block address ranges spans an entire logical group.

18. The non-volatile memory system of claim 17 wherein the logical group is a metablock.

19. The non-volatile memory system of claim 11 wherein the controller of the memory system is configured to utilize an area of physical memory corresponding to the logical block address range as at least one of a binary cache, an update block, a spare block in a block pool, or an index table.

20. The non-volatile memory system of claim 11 wherein the controller is configured to detect the repeated pattern in the data by monitoring the data as the data is received from the host.