Granted Patent B1

US 9,880,744 · App. 14/978,071 · Granted Jan 30, 2018

Abstract

Claims (70)

1. A processor-based method for flash-friendly caching; comprising:

reading data from a first memory;

writing the data to a second memory, in a cache;

performing a first aligned block write of data from the second memory in the cache to a flash memory in the cache, responsive to accumulating sufficient data for the aligned block write;

switching alternating sections of the second memory, responsive to the accumulating sufficient data for the aligned block write; and

accumulating further data for a subsequent aligned block write while the first aligned block write is performed.

2. The method of claim 1 , further comprising:

determining whether data that is stored in the first memory is available for reading from the second memory of the cache; and

determining whether the data that is stored in the first memory is available for reading from the flash memory of the cache, responsive to determining that the data that is stored in the first memory is not available for reading from the second memory.

3. The method of claim 1 , further comprising:

searching for the data in a first hash table for the second memory, and, responsive to not finding the data in the first hash table, searching for the data in a second hash table for the flash memory.

4. The method of claim 1 , wherein the cache is a first-hit cache, and further comprising:

promoting data from the first-hit cache to an N-hit cache having a further flash memory and a further second memory, responsive to determining that the data being promoted is read at least N times in the first-hit cache, where N is an integer.

5. The method of claim 1 , wherein the first memory includes at least one of disk storage, network storage, or virtualized storage memory.

6. The method of claim 1 , further comprising:

receiving a request to write data to the first memory;

writing the write data to the second memory;

tracking modified blocks, arising from at least the write data, in the flash memory; and

writing the modified blocks from the flash memory to the first memory, responsive to the tracking reaching a predefined limit.

7. A tangible, non-transitory, computer-readable media having instructions thereupon which, when executed by a processor, cause the processor to perform a method comprising:

reading data from a first memory that his external to a cache;

writing the data to a second memory that is internal to the cache;

writing, using an aligned block write, data from the second memory to a flash memory that is internal to the cache, responsive to accumulating sufficient data in the second memory for the aligned block write;

switching alternating sections of the second memory, responsive to the accumulating sufficient data for the aligned block write; and

accumulating further data for a subsequent aligned block write while the aligned block write is performed.

8. The computer-readable media of claim 7 , wherein the accumulating and the performing the aligned block write further comprise:

accumulating a first sufficient amount of data in a first section of the second memory to perform a first aligned block write;

performing the first aligned block write from the first section of the second memory to the flash memory;

accumulating a second sufficient amount of data in a second section of the second memory to perform a second aligned block write; and

performing the second aligned block write from the second section of the second memory to the flash memory.

9. The computer-readable media of claim 7 , wherein the method further comprises:

consulting a first hash table to determine whether the data is in the second memory; and

consulting a second hash table to determine whether the data is in the flash memory, responsive to determining that the data is not in the second memory.

10. The computer-readable media of claim 7 , wherein the method further comprises:

determining that data in the cache is read at least N times; and

promoting the data that is read at least N times from the cache, as a first-hit cache, to an N-hit cache having a further flash memory and a further second memory with aligned block writes from the further second memory to the further flash memory.

11. The computer-readable media of claim 7 , wherein the method further comprises:

writing write data to the second memory, responsive to receiving a request to write the write data to the first memory;

counting modified blocks, arising from at least the write data, in the flash memory; and

writing the modified blocks from the flash memory to the first memory, responsive to reaching a predetermined time limit or the counting the modified blocks reaching a predefined count limit.

12. The computer-readable media of claim 7 , wherein the method further comprises:

comparing a distance of a data read from a chunk database in the flash memory to a write pointer of the chunk database; and

rewriting data of the data read to the second memory, responsive to determining that the distance is within a write proximity threshold.

13. A flash-friendly caching system, comprising:

a second memory, having RAM (random access memory);

a flash memory, coupled to the second memory, the second memory and the flash memory forming a cache; and

a processor, coupled to a first memory and the cache, and configured to perform actions comprising:

reading requested read data from the first memory, responsive to determining that the requested read data is not available in the cache;

writing the read data to the second memory, responsive to reading the read data from the first memory;

writing data from the second memory to the flash memory as an aligned block write, responsive to accumulating sufficient data in the second memory to perform the aligned block write;

switching alternating sections of the second memory, responsive to the accumulating sufficient data for the aligned block write; and

accumulating further data for a subsequent aligned block write while the first aligned block write is performed.

14. The flash-friendly caching system of claim 13 , further comprising:

a first hash table, configured to look up data in the second memory;

a second hash table, configured to look up data in the second memory; and

the processor further configured to look up the requested read data in the first hash table and look up the requested read data in the second has table responsive to not finding the read data with the first hash table.

15. The flash-friendly caching system of claim 13 , further comprising:

the second memory having a first section and a second section, configured to alternate so that the second section accumulates data while the first section has a first aligned block write to the flash memory, and the first section accumulates data while the second section has a second aligned block write to the flash memory.

16. The flash-friendly caching system of claim 13 , further comprising:

a checkpoint pointer, configured to count modified blocks in the flash memory and direct a flush of the flash memory to the first memory.

17. The flash-friendly caching system of claim 13 , further comprising:

a barrier pointer, configured to track a first end of valid data in a circular buffer in the flash memory; and

a write pointer, configured to track a second end of the valid data in the circular buffer, such that a further aligned block write to the flash memory starts at the write pointer.

18. The flash-friendly caching system of claim 13 , wherein the cache is a first-hit cache and further comprising:

an N-hit cache having a further second memory and a further flash memory; and

the processor further configured to promote a data chunk from the first-hit cache to the N-hit cache, responsive to the data chunk being read at least N times from the first-hit cache, wherein frequency of access evaluation of data chunks in the first-hit cache is independent of data read proximity to a write pointer of the first-hit cache.

19. The flash-friendly caching system of claim 13 , further comprising:

a file to hash key map for the cache;

a hash key to chunk ID (identifier) map for the cache; and

a chunk ID to hash key reverse hash map for the cache.

Assignments (12)