Detecting access sequences for data compression on non-volatile memory devices

• US 9,411,721 B2
• Filed: 11/15/2013
• Issued: 08/09/2016
• Est. Priority Date: 11/15/2013
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: Rostoker, Tal, Marcu, Alon
• Primary Examiner(s): Gu, Shawn X
• Application Number:
  US14/081,108
• Publication Number:
  US 20150143023A1
• Time in Patent Office: 998 Days
• US Class Current: 1/1
• 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/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

Abstract

Techniques are presented to allow non-volatile memory system to operate by determining ranges of logical addresses that a host typically accesses as together. For example, the system'"'"'s controller can determine that the host always, or most always, writes or reads a contiguous set of logical addresses as a single unit. The controller can exploit this information by operating on these ranges as single a unit for data operations it performs. To take one example, the memory system can treat such ranges as single units for on-system data compression prior to writing the data to non-volatile memory.

Claims

1. A method of operating a non-volatile memory system including a controller circuit and one or more non-volatile memory circuits, the method comprising:

receiving, at the controller circuit, logically-addressed host data from a host;

storing the host data in the one or more non-volatile memory circuits;

monitoring, by the controller circuit, access patterns by the host of the host data stored in the one or more non-volatile memory circuits;

determining, by the controller circuit, ranges of contiguous logical addresses of the host data that are accessed by the host as single entities in response to the monitoring;

maintaining, by the controller circuit, a record of the ranges of contiguous logical addresses of the host data that are accessed by the host as single entities;

merging, by the controller circuit, at least two of the ranges of contiguous logical addresses of the host data that are in the record into a single logical unit;

updating, by the controller circuit, the record to include the single logical unit; and

performing, by the controller circuit, a data operation on the single logical unit.

2. The method of claim 1, further comprising:

splitting one of the ranges of contiguous logical addresses that is in the record into separate logical units for the data operation; and

updating the record in response to the splitting.

3. The method of claim 1, further comprising:

adding another range of contiguous logical addresses to the record.

4. The method of claim 1, further comprising:

deleting one of the ranges of contiguous logical addresses from the record.

5. The method of claim 1, wherein the data operation includes compressing the host data corresponding to the single logical unit and storing the compressed host data in the one or more non-volatile memory circuits.

6. The method of claim 1, wherein the data operation includes performing internal garbage collection operations on the host data corresponding to the single logical unit.

7. The method of claim 1, wherein the data operation includes performing write operations on the host data corresponding to the single logical unit.

8. The method of claim 1, wherein the data operation includes performing a read operation on the host data corresponding to the single logical unit, wherein the read operation incorporates a predictive read.

9. The method of claim 1, wherein the data operation includes performing internal data backup operations on the host data corresponding to the single logical unit.

10. The method of claim 1, wherein the access patterns include read operations.

11. The method of claim 1, wherein the access patterns include write operations.

12. The method of claim 1, wherein the merging comprises:

determining, by the controller circuit, that the host consistently accesses a first range of the at least two ranges before the host accesses a second range of the at least two ranges.

13. A method of operating a non-volatile memory system, the memory system including one or more non-volatile memory circuits and a controller circuit that manages storage of logically-addressed host data received from a host in the one or more non-volatile memory circuits, the method comprising:

maintaining, by the controller circuit, a record of ranges of contiguous logical addresses that are accessed by the host as single entities;

treating, by the controller circuit, the ranges of contiguous logical addresses that are accessed by the host as single entities as single units for data operations; and

monitoring, by the controller circuit, access patterns by the host of the host data stored in the one or more non-volatile memory circuits and updating the record based on the monitoring, wherein the updating includes merging at least two of the ranges of contiguous logical addresses into a single logical unit; and

compressing the single logical unit.

14. The method of claim 13, wherein the monitoring and updating include:

creating an access table of the ranges of contiguous logical addresses;

creating a lookup table from the access table; and

determining the single units for data operations from the lookup table.

15. The method of claim 14, wherein the creating of the access table includes:

sequentially sorting start and end logical addresses of the ranges of contiguous logical addresses.

16. The method of claim 14, wherein the determining the single units for data operations from the lookup table includes:

determining whether each of the ranges of contiguous logical addresses accessed by the controller circuit is consistently followed by another of the ranges of contiguous logical addresses accessed by the controller circuit in the lookup table.

17. The method of claim 13, wherein the updating of the record further includes splitting of a range of contiguous logical addresses into separate units for the data operations by the controller circuit.

18. The method of claim 13, wherein the updating of the record further includes adding a range of contiguous logical addresses to the record.

19. The method of claim 13, wherein the updating of the record further includes deleting a range of contiguous logical addresses from the record.

20. A non-volatile memory device comprising:

a non-volatile memory circuit; and

a controller circuit configured to

receive logically-addressed host data from a host;

store the host data in the non-volatile memory circuit;

monitor access patterns by the host of the host data stored in the non-volatile memory circuit;

determine ranges of contiguous logical addresses of the host data that are accessed by the host as single entities in response to the monitoring;

maintain a record of the ranges of contiguous logical addresses of the host data that are accessed by the host as single entities;

merge at least two of the ranges of contiguous logical addresses of the host data that are in the record into a single logical unit;

update the record to include the single logical unit; and

perform a data operation on the single logical unit.

21. The device of claim 20, wherein, during the merge, the controller circuit is further configured to determine that the host consistently accesses a first range of the at least two ranges before the host accesses a second range of the at least two ranges.

22. The device of claim 20, wherein the controller circuit is further configured to split one of the ranges of contiguous logical addresses that is in the record into separate logical units for the data operation, and update the record in response to the split.

23. The device of claim 20, wherein the data operation includes compressing the host data corresponding to the single logical unit and storing the compressed host data in the non-volatile memory circuit.

24. The device of claim 20, wherein the data operation includes performing internal garbage collection operations on the host data corresponding to the single logical unit.

25. The device of claim 20, wherein the access patterns include read operations or write operations.