Use of a two-way stack approach to optimize flash memory management for embedded database systems

• US 6,449,625 B1
• Filed: 04/20/1999
• Issued: 09/10/2002
• Est. Priority Date: 04/20/1999
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Wang, Jay
• Primary Examiner(s): Von Buhr, Maria N.
• Application Number:
  US09/295,198
• Time in Patent Office: 1,239 Days
• Field of Search: 707/205, 707/206, 711/100-106, 711/111-114, 711/132-136, 711/159, 711/160
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

A method and system for storing data in data blocks of predetermined size in an electronic memory (e.g. FLASH memory), particularly data such as updatable record of database transactions. The FLASH operates logically as two stacks where data is pushed into either end of the memory in alternating cycles. Between each push or write cycle, a garbage collection cycle is performed whereby only the most recent transaction performed on any particular record is preserved at one end of the stack, while the rest of the stack is made available for new data. When database being monitored is written to permanent memory, the entire FLASH is again made available for new data. If the database is periodically backed up to permanent memory, it can be restored to RAM by reducing the copy from the permanent memory and modifying it according to the record of database transactions in the electronic memory.

Claims

1. A method for storing data in data blocks of predetermined size in an electronic memory, comprising the steps of:

(a) writing data, in a first direction, into addressably contiguous data blocks of said electronic memory; and

(b) after writing to a predetermined data block, performing a garbage-collection cycle on said data blocks in a second direction which is opposite said first direction, whereby non-superfluous data is preserved in addressably contiguous data blocks of said electronic memory.

2. The method of claim 1, wherein said first direction is in an addressably sequential order and said garbage collection cycle is performed in an addressably reverse sequential order.

3. The method of claim 1, wherein said first direction is in an addressably reverse sequential order and said garbage collection cycle is performed in an addressably sequential order.

4. The method of claim 1, comprising the further steps of:

(c) reversing each said first and second directions; and

(d) repeating steps (a) and (b).

5. The method of claim 1 wherein said electronic memory is a FLASH memory.

6. The method of claim 1 further includes the steps of storing data as a database in a power dependent primary memory and modifying the data in the database in response to comments and wherein said electronic memory is power independent and the data in the datablocks of said electronic memory are a copy of modifications to said database.

7. The method of claim 6 further including the step of periodically storing a copy of said database in a power independent secondary memory and erasing the data in the datablocks of said electronic memory thereafter.

8. The method of claim 6 further including the steps of restoring the database to said power dependent primary memory after a power failure by writing the contents of the copy of said database from the secondary memory to said primary memory and modifying the copy of said data in said primary memory with the data from said electronic memory.

9. The method of claim 4, wherein said data includes a record_id which identifies a particular record in a database of records and wherein said garbage collection cycle includes the steps of:

reading the record_id of a record contained in a data block of said electronic memory;

determining whether the record corresponding to said record_id has already been encountered during the instant garbage collection cycle;

preserving said record if said record_id has not already been encountered during the instant collection cycle.

10. The method of claim 9 including the additional steps of:

setting a predetermined variable to correspond to the address of that data block in said electronic memory which is addressably contiguous in the direction of the cycle to the data block in which said record was instantly preserved.

11. The method of claim 10 wherein said addressably contiguous address comprises a sequentially smaller address when performing reverse sequential order garbage collection and a sequentially greater address when performing sequential order garbage collection.

12. The method of claim 9 wherein said step of reading said record_id proceeds in an addressably reverse sequential order starting with the addressably penultimate block of said electronic memory following a sequential write cycle.

13. The method of claim 9, wherein said step of reading said record_id proceeds in an addressably sequential order starting with the addressably second block of said electronic memory following a reverse sequential write cycle.

14. The method of claim 9 wherein, during a reverse sequential garbage collection cycle, said preserved record is written to the highest addressably ordered block in said electronic memory which does not presently contain preserved data.

15. The method of claim 9 wherein, during a sequential order garbage collection cycle, said preserved record is written to the lowest addressably ordered block in said electronic memory which does not presently contain preserved data.

16. The method of claim 9 wherein said step determining whether a record corresponding to said record_id has already been encountered is accomplished by:

storing the first instance of the record_id of each transaction encountered during the garbage collection cycle in a memory array and comparing subsequent record_ids stored in the memory array.

23. The system of claim 16 wherein said secondary memory comprises FLASH memory.

24. The system of claim 16 wherein said primary memory comprises RAM memory.

25. The system of claim 23, wherein after a power failure the database is removed by said logical processing unit reading data of the database from said permanent data stored to said primary memory and modifying said data in such primary memory with the data in said secondary memory.

17. A method for writing data to blocks of predetermined size within an electronic memory, said electronic memory comprising two logical stacks whose openings face a first and a second direction, comprising the steps of:

(a) pushing new data into said stack facing said first direction until all but one block is filled;

(b) performing in said first direction a garbage collection cycle to identify non-superfluous data residing in said stack; and

(c) pushing said non-superfluous data into said stack facing said second direction which is opposite said first direction.

18. The method of claim 17, comprising the further steps of:

(d) reversing said first and second directions and

(e) repeating steps (a) and (b) and (c).

19. The method of claim 17 comprising the additional steps of:

(d) writing the data in said electronic memory to a permanent storage memory unit; and

thereafter,

(e) erasing all of said data from said electronic memory.

20. The method of claim 17 wherein said electronic memory is a FLASH memory.

21. A system for maintaining data in an electronic database comprising:

(a) a power dependent primary memory which stores said database;

(b) a power independent secondary memory comprising two logical stacks of memory blocks each facing one of a first and second direction onto which data is pushed;

(c) a logical processing unit programmed to modify said database in response to a command and to carry out a data log operation by pushing data indicative of the modification onto the logical stack of said secondary memory facing a first direction until all but one block is filled, performing a garbage collection cycle in said first direction to identify non-superfluous data residing in said stack, pushing said non-superfluous data in a second stack facing said second direction which is opposite said first direction and reversing the first direction with the second direction and continuing said data log operation;

(d) a permanent data store connected to said logical processing unit; and

(e) a timer having a predetermined timer interval, said timer being connected to said logical processing unit and causing said data in said primary memory to transfer to said permanent store in response to the passage of said predetermined interval.

22. The system of claim 21 further comprising a sensor for sensing when the amount of preserved data in said secondary memory exceeds a predetermined capacity and causing said data in said primary memory to transfer to said primary store in response to an indication from said sensor due to sensing said predetermined criteria.