Systems and methods for effectively interacting with a flash memory

• US 9,690,713 B1
• Filed: 04/19/2015
• Issued: 06/27/2017
• Est. Priority Date: 04/22/2014
• Status: Active Grant

• Current Assignee: DataRobot, Inc.
• Original Assignee: Parallel Machines Ltd.
• Inventors: Khermosh, Lior, Zuckerman, Gal, Bar-Or, Ofer
• Primary Examiner(s): Cardwell, Eric S
• Application Number:
  US14/690,433
• Time in Patent Office: 800 Days
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 2212/2022 Flash memory
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays

Abstract

Various systems and methods to use a plurality of linked lists for keeping track of changes to be made in data sets currently in a flash memory. To enhance efficiency of the system, the changes to be made in any particular data set are aggregated in a random access memory (“RAM”) until a sufficient volume of changes have been aggregated to justify a rewrite of the flash memory block in which the particular data set is stored. Since a flash memory may have millions of memory blocks and data sets, there are potentially tremendous demands on the memory resources of the RAM to keep track of all the changes, but the problem presented by these potential demands is avoided through the use of linked lists, in which each list links all of the changes that have been aggregated in RAM and that apply to one specific data set.

Claims

1. A system operative to use a plurality of linked lists for keeping track of changes to be made in data sets currently stored in a flash memory, comprising:

a first compute element;

a first flash memory comprising a plurality of blocks currently storing respectively a plurality of data sets, in which said first flash memory is associated with a second compute element;

a first random access memory located in a first server together with said first compute element, in which said first random access memory comprises a plurality of linked lists associated respectively with the plurality of blocks, in which each linked list records a respective plurality of requirements to change the data set of the respective block, in which said plurality of requirements were made by said first compute element and have been accumulated in said linked list since the data set was last written to the respective block; and

a switching network;

wherein the first compute element is configured to;

identify one of the linked lists as being currently in condition to be used for updating the respective block;

traverse the linked list identified in order to accumulate all the respective plurality of requirements into an aggregated requirement to change the data set of the respective block; and

send said aggregated requirement accumulated to said second compute element via said switching network;

wherein said second compute element is configured to receive said aggregated requirement and change the data set of the respective block by performing a flash block write to the respective block in conjunction with said aggregated requirement.

2. The system of claim 1, wherein:

each of the linked lists comprises a plurality of data entries associated respectively with the plurality of requirements, in which each of the data entries is linked to the next data entry using a pointer to an address associated with the next such data entry, except to the most recent data entry which does not yet point to another data entry.

3. The system of claim 2, wherein said traversing of the linked list is done by performing a random access read cycle to each of the data entries in the linked list using said addresses as referenced by the pointers.

4. The system of claim 2, wherein:

all the pluralities of data entries are stored in a single memory space within said first random access memory, thereby resulting is said plurality of linked lists being interlaced across the single memory space, but such that said traversing is possible per each of the linked lists using said pointers.

5. The system of claim 1, wherein said identification is based on the number of requirements in the plurality of requirements.

6. The system of claim 5, wherein the linked list identified is the linked list associated with the highest number of requirements, as compared with the other linked lists.

7. The system of claim 1, wherein each of the plurality of requirements is stored in the respective linked list as a sequence of new data to be written to specific address in the respective block.

8. The system of claim 7, wherein said identification is based on the length of said sequences of new data, such that the identification is made when the sequences of new data exceeds a certain threshold length.

9. A system operative to use a plurality of linked lists for keeping track of changes to be made in data sets currently stored in a flash memory, comprising:

a first compute element;

a first flash memory comprising a plurality of blocks currently storing respectively a plurality of data sets; and

a first random access memory comprising a plurality of linked lists associated respectively with the plurality of blocks, in which each linked list records a respective plurality of requirements to change the data set of the respective block, in which said plurality of requirements were made by said first compute element and have been accumulated in said linked list since the data set was last written to the respective block;

wherein the system is configured to;

identify one of the linked lists as being currently in condition to be used for updating the respective block;

traverse the linked list identified in order to accumulate all the respective plurality of requirements into an aggregated requirement to change the data set of the respective block; and

change the data set of the respective block by performing a flash block write to the respective block in conjunction with said aggregated requirement;

wherein;

said system further comprises additional compute elements each of which is operative to make additional requirements to change the data set of at least some of the blocks, and in which each such additional compute element necessitates an additional plurality of linked lists in support of said additional requirements, thereby resulting is several pluralities of linked lists; and

said first random access memory is a shared memory pool which is large enough to store said several pluralities of linked lists.

10. A system operative to use a plurality of linked lists for keeping track of changes to be made in data sets currently stored in a flash memory, comprising:

a first compute element;

a first flash memory comprising a plurality of blocks currently storing respectively a plurality of data sets; and

a first random access memory comprising a plurality of linked lists associated respectively with the plurality of blocks, in which each linked list records a respective plurality of requirements to change the data set of the respective block, in which said plurality of requirements were made by said first compute element and have been accumulated in said linked list since the data set was last written to the respective block,

wherein the first compute element is configured to make a new requirement to change the data set of one of the blocks; and

the system is configured to link the new requirement to the linked list associated with said one of the blocks, thereby appending the new requirement to the plurality of requirements already associated with said one of the blocks;

wherein;

each of the linked lists comprises a plurality of data entries associated respectively with the plurality of requirements, in which each of the data entries is linked to the next data entry using a pointer to an address associated with the next such data entry, except to the most recent data entry which does not yet point to another data entry;

the new requirement is associated with a new data entry; and

said linkage of the new requirement to the linked list is performed by;

(i) adding, in conjunction with said most recent data entry, using a first random access write cycle, a new pointer to a new address to be associated with the new data entry, and (ii) adding, using a second random access write cycle, at the new address, the new data entry, in which said linkage is performed in less than one microsecond, as a result of the first random access write cycle and the second random access write cycle being both random access cycles performed in conjunction with said first random access memory.

11. The system of claim 10, wherein said first random access memory is a first dynamic random access memory.

12. The system of claim 10, wherein said new data entry is less than 500 (five hundred) bytes in length, thereby allowing low latency data writes in conjunction with small data objects such as said new data entry.