Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2000-08-10
2004-08-03
Padmanabhan, Mano (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S113000, C711S134000, C711S135000, C365S185210, C365S185110, C365S185330
Reexamination Certificate
active
06772296
ABSTRACT:
BACKGROUND
1. Field of the Invention
The present invention relates to storing objects in persistent storage. More specifically, the present invention relates to a method and an apparatus that facilitates storing objects in a persistent storage medium with asymmetric access characteristics, wherein write accesses are much slower than read accesses.
2. Related Art
Millions of people are presently using hand-held computing devices, such as personal digital assistants (PDAs) and personal organizers, to perform simple tasks, such as looking up telephone numbers and scheduling tasks. Developers are continually attempting to migrate progressively larger applications to these hand-held computing devices in order to provide additional functionality. Unfortunately, the limited amount of memory within these hand-held computing devices limits the complexity and size of applications that can be run on them.
Existing virtual memory techniques can be used to increase the effective size of the memory in a hand-held computing device by allowing infrequently used pages within a virtual memory space to be moved to persistent storage. When a page that is located in persistent storage is later needed, it can be moved back into volatile memory.
However, existing techniques to provide virtual memory and to store persistent objects are presently tailored for secondary storage systems with symmetric access characteristics, wherein read and write accesses take roughly the same amount of time, and transfer units for both read and write accesses are the same size.
Designers are beginning to incorporate secondary storage with “asymmetric ” access characteristics, such as non-volatile flash memory, into hand-held computing devices in order to provide persistent storage for code and/or data. Read accesses to flash memory are roughly as fast as read accesses to RAM and have a minimum transfer unit of one to eight bytes. In contrast, write accesses to flash memory are much slower, and typically operate on a larger transfer unit of 512 to 512K bytes. Furthermore, flash memory wears out after several million repeated writing and erasure cycles.
Existing mechanisms to facilitate virtual memory and persistent objects presently do not take advantage of the fast read access time to flash memory. They instead require a block containing a data item to be copied from secondary storage to main memory before the data item can be read.
What is needed is a method and an apparatus for facilitating persistent storage in a flash memory that takes advantage of the fast read access times for flash memory and that evenly distributes write operations over the flash memory.
SUMMARY
One embodiment of the present invention provides a system that facilitates storage of objects in a persistent memory with asymmetric access characteristics. The system operates by receiving an access to an object. If the access is a read access, the system looks up the object through an indirectory. This indirectory includes an entry that points to a location of the object within the persistent memory if updates to the object have been recorded in the persistent memory. Otherwise, the indirectory entry points to a location of the object within a volatile memory. If the object is located in the volatile memory, the system reads the object from the volatile memory. Otherwise, if the object is located in the persistent memory, the system reads the object from the persistent memory directly without first copying the object into the volatile memory.
In one embodiment of the present invention, if the access is a write access, the system looks up the object through the indirectory. If the object is located in the persistent memory, the system allocates a location in the volatile memory for the object, and then copies the object from the persistent memory into the location in the volatile memory. The system then updates the indirectory entry for the object to point to the location in the volatile memory. Next, the system performs the write access to the object in the volatile memory. At a later time, the system commits the object to the persistent memory from the volatile memory.
In one embodiment of the present invention, while committing the object to the persistent memory, the system appends the object to a location within a log in the persistent memory, and then updates the indirectory entry for the object to point to the location of the object within the log.
In one embodiment of the present invention, in order to allocate the location in the volatile memory for the object, the system determines if there is space available for the object in the volatile memory. If not, the system creates additional space in the volatile memory by determining if a checkpointing operation is possible. If the checkpointing operation is possible, the system performs the checkpointing operation to commit updated objects from the volatile memory to a log within the persistent memory, thereby freeing up space in the volatile memory. The system also updates corresponding entries for the updated objects in the indirectory to point to the log within the persistent memory.
In a variation on this embodiment, if the checkpointing operation is not possible, the system creates space in the volatile memory by allocating a steal region in the persistent memory. The system then moves updated objects, which are not ready to be committed to the log, into the steal region in the persistent memory. The system also updates corresponding entries for the updated objects in the indirectory to point to the steal region in the persistent memory.
In one embodiment of the present invention, the system periodically checkpoints updated objects from the volatile memory to a log within the persistent memory, and then updates corresponding entries for the updated objects in the indirectory to point to the log in the persistent memory.
In one embodiment of the present invention, the persistent memory includes flash memory, and the volatile memory includes a volatile semi-conductor memory.
In one embodiment of the present invention, the object includes an object defined within an object oriented programming system.
REFERENCES:
patent: 5920863 (1999-07-01), McKeehan et al.
patent: 6061708 (2000-05-01), McKeehan et al.
patent: 6542967 (2003-04-01), Major
POS8, Eight International Workshop on Persistent Object Systems: Design, Implementation and Use, Aug. 30th Aug.-1st Sep. 1998 (http://www-ppg.dcs.st-and.ac.uk/Conferences/POS8/Abstracts.html).*
Publication entitled “Perdis: Design, Implementation, and Use of a Persistent Distributed Store”, By Paulo Ferreira et al., Institut National De Recherche En Informatique et en Automatique, No. 3525, Oct. 1998, Theme 1B.
Ho Thang
Padmanabhan Mano
Park Vaughan & Fleming LLP
Sun Microsystems Inc.
LandOfFree
Method and apparatus facilitating automatic persistence in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus facilitating automatic persistence in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus facilitating automatic persistence in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3292032