US 6,594,751 B1 · Method and apparatus for pointer relocation optimization for virtual memory mapping and transaction management in a database system

Abstract

There is provided an apparatus and a method for virtual memory mapping and transaction management for an object-oriented data base system having at least one permanent storage means for storing data and at least one data base, at least one cache memory for locally storing data addressed by physical addresses, and a processing unit including means for requesting data utilizing virtual addresses to access data in the cache memory, means for mapping virtual addresses to physical addresses and means for retaining the cached data after the conclusion of a transaction. The apparatus and method further provide that data retained in the cache across transactions will often not need further translation, referred to as forward relocation. The ability to make cached data usable across a sequence of transactions often without requiring further translation, while also providing that the total working set size of this data may be much larger than what can fit into a client computer's address space at any one time is referred to as relocation optimization, and is the primary advantage of this method. The method makes use of a single queue containing elements representing managed entities (pages, address space bindings) which orders the entities roughly by recency of use, and recycles address space of the least-recently used bindings in a way that preserves the validity of bindings necessary for the proper function of the client application with minimal overhead.

Claims6

Dependent claims

Apparatus for segregating data within a cache in a database system wherein pointers in said cache are virtual address pointers translated from persistent address pointers, comprising:

a) means for providing a transient relocation optimization queue to organize virtual address space and recycle said virtual address space across a series of transactions by a single client application having a plurality of flngers to designate positions in said queue, and a plurality of entries corresponding to cached data in the cache,
b) means for delimiting said queue into a plurality of sections with said fingers, a first section for containing entries for data used in a current transaction by said client application, a second section for containing entries that can be used by said client application without updating pointers, and a third section containing entries that cannot be used by said client application without updating pointers;
c) means for servicing requests from said client application for access to said data in said cache and for data not yet in said cache;
d) means for incorporating data into said cache that is not yet in said cache and translating pointers in said queue to update pointer information to reflect said incorporated data in said queue;
e) means for maintaining said updated pointer information for data previously incorporated into said cache;
f) means for removing data from said cache as it is no longer required by said client application and translating pointers in said queue to update pointer information to reflect said removed data in said queue;
g) means for updating pointers when providing access to said data corresponding to said entries in said third section of said queue, thereby providing fast access to data in said cache corresponding to said first and said second sections of said queue;
and
h) means for incrementally recycling said virtual address space used by entries in the second and third sections of said queue for use by data being incorporated into the cache, such that the address space so recycled will tend to be the virtual address space which is least recently used.

6 more elements

Apparatus for controlling the translation of references in data to virtual addresses in a computer system having a virtual memory system defining a virtual address space, and including at least one cache memory for temporarily storing data, a processing unit, and an application program utilizing the processing unit and data, the processing unit including means for requesting data utilizing a virtual address to access said data in the at least one cache memory, the virtual memory system including means for mapping virtual addresses to physical addresses, and means for detecting where access to data requested by the means for requesting is not permitted at the virtual address utilized by the means for requesting, the data consisting partly of intra- and interdata references, said method comprising:

(a) means for starting and ending address-space generations, much as transactions a manner by which the application program informs said method of the start and end of each term in a sequence of terms such that during each term all of the virtual address translations of references contained in data accessed by the application during the term must remain valid;
(b) means for segregating the data in each cache memory into three groups such that all of the data in the first group was accessed during the current term, the data in the second group is a mix of the remainder of data accessed during the current term and still resident in the cache and of data accessed in prior terms, and the data in the third group is the remainder of the data accessed during prior terms that is still resident in the cache;
(c) means for segregating the translations of references contained in said data into said three groups such that all of the translations of references in data contained in the first group are in the first group, some of the translations of references in data in the second group are in the first group and the remainder are in the second group, and some of the translations of references in data in the third group are in the first group, some in the second group, and the remainder in the third group;
(d) means for segregating the virtual address space consumed by said translations of references into the first and second groups such that all of the virtual address space consumed by a translation in either the first or second group is contained in the same group as the corresponding translation, and such that no translations in the third group consume virtual address space and are thus not immediately usable;
(e) means for forward relocation of data in a way that data in the third group which the application program attempts to access is incorporated into the first group, the translations of references in said data that are present in the second group are incorporated into the first group, the translations of references in said data that are present in the third group are provided with virtual address space and adjusted to make use of this virtual address space, and all said translations of references and corresponding virtual address space are incorporated into the first group;
(f) means for page displacement by resegregation of data in the second group unaccessed during the current term, having the virtual address space used by translations of references contained in it recycled, into the third group;
(g) means for DSCO handle displacement by resegregation of translations of references in the second group, where said references are only in data in the third group or no longer in the cache, into the third group with a corresponding freeing of the virtual address space consumed by said translations such that said virtual address space can be consumed by different translations;
(h) means for incorporating data in the second group accessed during the current term, along with translations of references in the second group for said data and the virtual address space consumed by said translations, is incorporated into the first group;
(i) means for inbound relocation by incorporating data not yet in the cache into the cache, translating its references from an external form into virtual addresses, and incorporating said data along with the virtual address space consumed by translations of its references is into the first group;
and
(j) means for outbound relocation translation references on data in the cache that is modified by the application program into an external form suitable for storage outside of the cache.

8 more elements

A method of segregating data within a cache in a database system wherein pointers in said cache are virtual address pointers translated from persistent address pointers, comprising the steps of:

a) providing a transient relocation optimization queue to organize virtual address space and recycle said virtual address space across a series of transactions by a single client application having a plurality of fingers to designate positions in said queue, and a plurality of entries corresponding to cached data in the cache,
b) delimiting said queue into a plurality of sections with said fingers, a first section for containing entries for data used in a current transaction by said client application, a second section for containing entries that can be used by said client application without updating pointers, and a third section containing entries that cannot be used by said client application without updating pointers;
c) servicing requests from said client application for access to said data in said cache and for data not yet in said cache;
d) incorporating data into said cache that is not yet in said cache and translating pointers on each database page in said queue to update pointer information to reflect said incorporated data in said queue and maintaining said updated pointer information for data previously incorporated into said cache;
e) removing data from said cache as it is no longer required by said client application and translating pointers in said queue update pointer information on a per page basis to reflect said removed data in said queue;
f) updating pointers when providing access to said data corresponding to said entries in said third section of said queue, and
g) incrementally recycling said virtual address space used by entries in the second and third sections of said queue for use by data being incorporated into the cache, such that the address space so recycled will tend to be the virtual address space which is least recently used;
thereby providing fast access to data in said cache corresponding to said first and said second sections of said queue.

5 more elements

A method of segregating data within a cache in a database system wherein pointers in said cache are virtual address pointers translated from persistent address pointers, comprising the steps of:

providing a relocation optimization queue having a plurality of fingers to designate positions in said queue, and a plurality of entries corresponding to cached data in the cache,
delimiting said queue into a plurality of sections with said fingers, a first section for containing entries for data used in a current transaction by a client application, a second section for containing entries that can be used by said client application without updating pointers, and a third section containing entries that cannot be used by said client application without updating pointers;
servicing requests from said client application for access to said data in said cache and for data not yet in said cache;
incorporating data into said cache that is not yet in said cache and translating pointers on each database page in said queue to update pointer information to reflect said incorporated data in said queue;
removing data from said cache as it is no longer required by said client application and translating pointers in said to queue to update pointer information on a per page basis to reflect said removed data in said queue;
and
updating pointers when providing access to said data corresponding to said entries in said third section of said queue,
thereby providing fast access to data in said cache corresponding to said first and said second sections of said queue wherein said processing steps are arranged for
recycling virtual address space used by entries in the second and third sections of said queue for use by data being incorporated into the cache, such that the address space so recycled will tend to be that which is least recently used;
moving said fingers as needed to properly maintain the homogeneity of the said sections delimited by said fingers;
preserving translations between pointers in the cache and virtual addresses as needed by said client application, at least until said client application specifies that some or all said translations may be recycled;
moving said fingers as needed to record the allowed recycling of said translations by said client application, without requiring further computation (other than the alteration of the memory protection on pages in the cache) to accommodate said recycling;
preserving many said translations after said client application specifies that they may be recycled, so that future re-use of said translations will not require relocation computations;
incorporating displaced address binding sets to record recycled translations, so that requests by said client application for the re-use of entries in said third section of said relocation optimization queue can be accommodated by searching over said recycled translations within said displaced address binding sets, and thus either arrive at or create appropriate translations for said entries;
and
removing said entries and said displaced address binding sets from said relocation optimization queue when they are no longer needed.

13 more elements

A method for controlling the translation of references in data to virtual addresses in a computer system having a virtual memory system defining a virtual address space, and including at least one cache memory for temporarily storing data, a processing unit, and an application program utilizing the processing unit and data, the processing unit including means for requesting data utilizing a virtual address to access said data in the at least one cache memory, the virtual memory system including means for mapping virtual addresses to physical addresses, and means for detecting where access to data requested by the means for requesting is not permitted at the virtual address utilized by the means for requesting, the data consisting partly of intra- and inter-data references, said method comprising:

(a) providing a manner by which the application program informs said method of the start and end of each term in a sequence of terms such that during each term all of the virtual address translations of references contained in data accessed by the application during the term must remain valid,
(b) segregating the data in each cache memory into three groups such that all of the data in the first group was accessed during the current term, the data in the second group is a mix of the remainder of data accessed during the current term and still resident in the cache and of data accessed in prior terms, and the data in the third group is the remainder of the data accessed during prior terms that is still resident in the cache,
(c) segregating the translations of references contained in said data into said three groups such that all of the translations of references in data contained in the first group are in the first group, some of the translations of references in data in the second group are in the first group and the remainder are in the second group, and some of the translations of references in data in the third group are in the first group, some in the second group, and the remainder in the third group,
(d) segregating the virtual address space consumed by said translations of references into the first and second groups such that all of the virtual address space consumed by a translation in either the first or second group is contained in the same group as the corresponding translation, and such that no translations in the third group consume virtual address space and are thus not immediately usable;
(e) incorporating data in the third group, which the application program attempts to access, into the first group, incorporating the translations of references in said data, that are present in the second group, into the first group, providing the translations of references in said data that are present in the third group with virtual address space and adjusting them to make use of this virtual address space, and wherein all said translations of references and corresponding virtual address space are incorporated into the first group;
(f) segregating in the second group unaccessed during the current term, having the virtual address space used by translations of references contained in it recycled, into the third group
(g) segregating translations of references in the second group, where said references are only in data in the third group or no longer in the cache, into the third group with a corresponding freeing of the virtual address space consumed by said translations such that said virtual address space can be consumed by different translations,
(h) providing a process by which data in the second group accessed during the current term, along with translations of references in the second group for said data and the virtual address space consumed by said translations, is incorporated into the first group;
(i) providing a process by which data not yet in the cache is incorporated into the cache, its references translated from an external form into virtual addresses, and said data along with the virtual address space consumed by translations of its references is incorporated into the first group;
and
(j) providing a process by which references on data in the cache that is modified by the application program can be translated into an external form suitable for storage outside of the cache.

8 more elements

Dependencies are inferred from the claim text.

Method and apparatus for pointer relocation optimization for virtual memory mapping and transaction management in a database system

Life of this patent

Method and apparatus for pointer relocation optimization for virtual memory mapping and transaction management in a database system

Life of this patent

Abstract

Claims6