Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
2001-05-15
2004-04-27
McLean-Mayo, Kimberly (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
C711S154000
Reexamination Certificate
active
06728854
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This invention relates generally to computer data storage and retrieval, and more particularly to a way to provide transaction management in connection with write operations on a data storage space, such as a cache, to enable data recovery in the case of a non-graceful shutdown.
BACKGROUND OF THE INVENTION
A cache is an amount of data storage space that is used to hold recently accessed data for future access. The retrieval of data from the cache is typically significantly faster than accessing a data source from which the data in the cache are originally obtained. By storing recently accessed data in the cache, the data can be retrieved and made available quickly the next time they are requested. Data caching is one of the most fundamental concepts in computer science and has been widely applied in various applications where it is desirable to minimize the data access time.
For instance, in the context of accessing information available from the World Wide Web (“WWW”) on the Internet, it is common for a proxy server of a private network to use a cache unit to store data objects downloaded from various Websites in response to requests by computers on the private network. When the proxy server receives a request from a computer on the private network for a particular data object, it first checks the cache unit to see whether the requested object is already in the cache unit. If there is a cache hit (i.e., the requested data object is found in the cache unit), the requested object is retrieved from the cache and sent to the requesting computer. On the other hand, if the requested object is not in the cache, the proxy server forwards the request on to the Internet so the requested data object can be downloaded from a Website. Since the speed of downloading data objects from Websites can be very slow, a properly implemented cache unit can significantly reduce the average amount of time for a user to receive a requested data object, thereby providing a significantly improved user experience.
The performance requirements on the cache unit can be very high. For instance, a typical implementation of a cache unit may be expected to hold 50 million data objects. With such a large number of data objects, it can become very difficult to effectively manage the usage of the cache space to provide an adequate performance of the caching operation.
One of the different aspects of cache management that can become more complicated as the number of objects increases is transaction management. In the parlance of computer science, a database management system should pass the “ACID test.” The acronym “ACID” stands for atomicity, consistency, isolation, and durability, which form a set of requirements that should be satisfied by a well-designed database management. Transaction management for a data storage space, such as the cache unit for caching downloaded objects, facilitates the atomicity aspect by monitoring operations that write data objects into the storage space to keep track of whether the operations have been completed successfully. This information is necessary to ensure that the stored data can be reliably recovered in the case of a non-graceful shutdown during which the regular measures for ensuring the integrity of data and operational states cannot be taken. A non-graceful shutdown may be caused by a variety of reasons such as power failure, hardware break down, software problems such as operating system crashes, administration fault (which leads to the termination of the process that executes the cache unit), etc. Without transaction management, it is difficult to tell after the non-graceful shutdown which objects in the database had been written successfully before the shutdown and which objects may have undefined contents because their write operations were interrupted by the shutdown.
Traditional transaction management schemes often employ complex data structures for keeping track of the transactional status of write operations and require high overhead to maintain the data structures. In the case of managing a cache, when the number of objects to be cached becomes very large, transaction management based on conventional schemes can become highly complex and require unacceptably high overhead, causing the caching operation to slow down significantly.
SUMMARY OF THE INVENTION
In view of the foregoing, the present invention provides a system and method for providing transaction management for write operations performed on a data storage space, such as a cache. The invention is based on the recognition that in the context of object caching and some other applications it is acceptable to lose some data (e.g., 5-10%). In accordance with this recognition, the invention provides a very simple transaction management model that is inherently “lossy” but is very easy to implement and has extremely low operational overhead. In this transaction management model, the data storage space is viewed as having one (or more) generally localized active area that contains active data objects, i.e., objects on which the write operations are ongoing. A transient zone is set to cover the active area, and the boundary of the transient zone is adjusted from time to time to maintain a comfortable margin from the active area. The boundary of the transient zone is persistently tracked so that the boundary information will not be lost in the case of a non-graceful shutdown. When there is a non-graceful shutdown, the data within the transient zone are deemed corrupted and may be discarded, while the data outside the transient zone should still be stable (i.e., not corrupted) and may be used for data recovery.
The transaction management of the invention is drastically simpler and faster than traditional transaction management schemes. The computation time complexity of the transaction management scheme of the invention is of the order of O(1) per write operation of a data object. The sizes of memory and persistent storage spaces that are required to support the transaction management are also O(1). Moreover, the number of I/O write operations required by the transaction management scheme is O(1) for supporting reliable persistence of data as large the whole cache. That is, this system needs a small constant number of I/O write operations to manage and support reliable caching of fresh data as large as the whole cache space. These outstanding complexity estimations are affected by neither the number of ongoing write operations nor the size of the dataset or cache storage space.
Additional features and advantages of the invention will be made apparent from the following detailed description of illustrative embodiments, which proceeds with reference to the accompanying figures.
REFERENCES:
patent: 6353874 (2002-03-01), Morein
patent: 2001/0037475 (2001-11-01), Bradshaw et al.
Leydig , Voit & Mayer, Ltd.
McLean-Mayo Kimberly
Microsoft Corporation
LandOfFree
System and method for providing transaction management for a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for providing transaction management for a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for providing transaction management for a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3207671