Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-04-20
2002-09-10
Von Buhr, Maria N. (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C711S103000, C711S133000, C711S159000
Reexamination Certificate
active
06449625
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to methods for storing data in FLASH memory and, more particularly, to methods for optimizing the use of FLASH memory in database systems.
BACKGROUND OF THE INVENTION
FLASH memory is a portable, high capacity storage unit capable of maintaining stored data memory units, however, it allows data to be updated only in blocks of predetermined size which is usually 64K bytes or larger. Accordingly, achieving a high storage efficiency when using FLASH memory as a database backup device is problematic in that a change to any particular data requires that the entire block containing that data be erased and rewritten. Compounding the problem is the fact that the flash memory is rated for a limited number of write cycles, and so frequent database updates can shorten the life of the FLASH memory unit. The invention addresses these and other problems.
SUMMARY OF THE INVENTION
It is accordingly an object of the present invention to provide a system and method for efficiently and optimally using FLASH memory as a data backup device for a database application. The data in the database are organized in a collection of logical data units called records.
According to one aspect of the invention, a method for storing data in memory blocks in an electronic or FLASH memory comprises the steps of writing records into addressably contiguous memory blocks of the FLASH device, and after writing to a predetermined memory block, performing a garbage collection cycle on the memory blocks so as to preserve non-superfluous data and to reclaim memory used by stale data. The data writing and garbage collection cycles are performed in addressably opposite directions.
In a garbage collection cycle each individual record in FLASH is checked to see if it contains the latest version of the data for the record. If it is the latest version, the data is new and is retained. Otherwise, the data is ‘stale’ and is evoked as unnecessary or garbage because a later version of the record already exists in the FLASH memory.
According to another aspect of the invention, a method for writing data to an electronic or FLASH memory logical stack comprises the step of pushing data onto a first logical stack until a predetermined block is filled and then performing a garbage collection cycle on that data in the same direction as the direction in which the data was pushed onto the stack. The preserved data after being popped from the first logical stack is pushed onto a stack whose opening faces a direction opposite that of the first stack.
Data recoverbility is achieved by logging database transactions to FLASH memory. These transactions are logged by writing transactions to contiguous blocks of FLASH memory in either an addressably sequential or an addressably reverse sequential manner. For the purpose of discussion, let us refer to the memory blocks that have the highest and the lowest address space as the ‘high-end’ and ‘low-end’ blocks of the Flash memory, respectively. Initially, transactions are written to FLASH memory starting from the low end toward the high end. Once these transactions occupy every block but the high-end block, a garbage collection cycle is performed. During the course of garbage collection, the previously written transactions are examined in a sequence opposite to the order they were written. These transactions are examined to identify transactions containing stale date, which are then discarded. The preserved data (i.e., the clean data that contain the latest version) will be stored in FLASH memory starting from the high-end block toward the low end. The transaction examination and the writing of the preserved data are preformed concurrently. Every time, when all the transactions in a block are processed, the entire block is erased to ensure there is always available memory space for writing the preserved data. This process continues until all the transactions in the FLASH memory are processed when the garbage collection cycle is completed. Another write cycle may start and new transactions can again be written to the FLASH memory starting from the available space following the preserved data written previously toward the low end. The write cycle continues until all but the low-end block is filled. At this point, another garbage collection cycle is commenced, this time from low-end to high-end.
This procedure may continue in such alternating manner until the database is backed up to an external permanent storage (e.g., a hard disk drive), at which point the entire FLASH is made available for a new write cycle. In a special case where the system does not have an external permanent storage, this alternating procedure can proceed indefinitely. However, in such case the size of the FLASH memory has to be large enough to accommodate the entire database and the logging overhead.
Viewed logically, the present method models a FLASH memory as a ‘two-way stack’ which is a combination of two logical stacks facing opposite directions that operate on one physical FLASH memory. Initially, transactions are pushed onto the first stack until only one block remains empty, at which point garbage collection commences. During the garbage collection cycle, transactions are ‘popped’ from the first stack and examined and preserved data is pushed to the second stack from the other end of the memory, i.e., the opening of the second stack faces a direction opposite that of the first stack. Once the garbage collection cycle terminates, new transactions are pushed into the second stack on top of the preserved data again until all but one block is filled. At this point a new garbage collection cycle commences. Transactions are again popped from the stack and examined. The push/garbage collection processes proceed in this alternating cycle continuously until the applicable database is written to permanent storage.
The system presented comprises a logical processing unit, a power-dependent primary memory unit, a FLASH memory unit, and a permanent storage unit or facility. The logical processing unit controls all functional aspects of the system. A real time version of the database resides in the power-dependent primary memory unit (e.g. RAM) while another copy of the database resides on a permanent storage device (e.g. hard disk drive.) The logical processing unit alternately pushes data into the two oppositely facing logical stacks of FLASH memory performing a garbage collection cycle between each series of pushes. At some predetermined point, the entire database resident in the power-dependent memory unit is written to a permanent storage device and all blocks of the FLASH memory can be made available for new data.
REFERENCES:
patent: 5592669 (1997-01-01), Robinson et al.
patent: 5640349 (1997-06-01), Kakinuma et al.
patent: 5687368 (1997-11-01), Nilsen
patent: 5734611 (1998-03-01), Kim et al.
patent: 5765175 (1998-06-01), Needham et al.
patent: 5832493 (1998-11-01), Marshall et al.
patent: 5873105 (1999-02-01), Tremblay et al.
patent: 5993845 (1999-11-01), Geerts et al.
patent: 6076138 (2000-06-01), Shin
patent: 6185581 (2001-02-01), Garthwaite
patent: 6209003 (2001-03-01), Mattis et al.
patent: 61264456 (1986-11-01), None
patent: 02022745 (1990-01-01), None
Darby & Darby
Lucent Technologies - Inc.
Von Buhr Maria N.
LandOfFree
Use of a two-way stack approach to optimize flash memory... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Use of a two-way stack approach to optimize flash memory..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Use of a two-way stack approach to optimize flash memory... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2874643