Consistent read in a distributed database environment
First Claim
Patent Images
1. A method comprising:
- maintaining a LAST-TO-SEE-TIMESTAMP, associated with a session, which indicates a time of a last change made in the session that must be seen by the session;
maintaining with a data item version a CLONE-TIME that indicates a time at which a clone branch to which the data item version belongs was cloned from a current version of the data item;
determining that the data item version is to be supplied to the session based, at least in part, on a comparison between the CLONE-TIME and the LAST-TO-SEE-TIMESTAMP;
supplying the data item version to the session; and
setting said CLONE-TIME based on a CLONE-TIME of a non-current data item version when said data item version is cloned from said non-current data item version.
2 Assignments
0 Petitions
Accused Products
Abstract
Techniques are provided for determining which data item version to supply to a query. According to the techniques, the determination is made by associating a new field, which indicates the time a data item version was current, with each data item version; associating a new field with each query, which indicates the last change that the query must see made by the transaction to which the query belongs; and determining which data item version to use to answer the query based, in part, on a comparison between the values of the two new fields.
-
Citations
18 Claims
-
1. A method comprising:
-
maintaining a LAST-TO-SEE-TIMESTAMP, associated with a session, which indicates a time of a last change made in the session that must be seen by the session; maintaining with a data item version a CLONE-TIME that indicates a time at which a clone branch to which the data item version belongs was cloned from a current version of the data item; determining that the data item version is to be supplied to the session based, at least in part, on a comparison between the CLONE-TIME and the LAST-TO-SEE-TIMESTAMP; supplying the data item version to the session; and setting said CLONE-TIME based on a CLONE-TIME of a non-current data item version when said data item version is cloned from said non-current data item version.
-
-
2. A method comprising:
-
maintaining a LAST-TO-SEE-TIMESTAMP, associated with a session, which indicates a time of a last change made in the session that must be seen by the session; maintaining with a data item version a CLONE-TIME that indicates a time at which a clone branch to which the data item version belongs was cloned from a current version of the data item; determining that the data item version is to be supplied to the session based, at least in part, on a comparison between the CLONE-TIME and the LAST-TO-SEE-TIMESTAMP; supplying the data item version to the session; performing at least one of;
(a) presenting information that is based at least in part on the data item version that is supplied to the session, and (b) storing information that is based at least in part on the data item version that is supplied to the session;wherein a plurality of nodes in a cluster have data item versions for said data item; maintaining, for each node of said plurality of nodes, CLONE-TIME information for said data item; and selecting which node to send a request for said data item to based on said CLONE-TIME information. - View Dependent Claims (3, 4)
-
-
5. A method comprising:
-
maintaining a LAST-TO-SEE-TIMESTAMP, associated with a session, which indicates a time of a last change made in the session that must be seen by the session; maintaining with a data item version a CLONE-TIME that indicates a time at which a clone branch to which the data item version belongs was cloned from a current version of the data item; determining that the data item version is to be supplied to the session based, at least in part, on a comparison between the CLONE-TIME and the LAST-TO-SEE-TIMESTAMP; supplying the data item version to the session; and performing at least one of;
(a) presenting information that is based at least in part on the data item version that is supplied to the session, and (b)storing information that is based at least in part on the data item version that is supplied to the session;wherein a transaction that includes a query is executing in the session; wherein the LAST-TO-SEE-TIMESTAMP is associated with the query and indicates a time of a last change made by the transaction that must be seen by the query; and wherein the step of determining that the data item version is to be supplied to the session is performed by determining that the data item version is to be used to answer the query. - View Dependent Claims (6, 7)
-
-
8. A method comprising:
-
maintaining, for a plurality of data item versions that reside in a plurality of nodes, CLONE-TIME information that indicates when the data item versions were current; wherein, for each data item version of the plurality of data item versions, the CLONE-TIME information for that data item version indicates a time at which a clone branch to which that data item version belongs was cloned from a current version of a particular data item; determining, based at least in part on said CLONE-TIME information, which data item versions of said plurality of data items versions contain all changes that must be seen by a query; selecting a data item version to supply to said query from those data item versions that contain all changes that must be seen by said query; supplying the data item version to said query; and performing at least one of;
(a) presenting information that is based at least in part on the data item version that is supplied to the query, and (b) storing information that is based at least in part on the data item version that is supplied to the query;wherein the step of determining includes; determining, based on a CLONE-TIME associated with said data item version, whether changes that must be seen by said query have been made to said particular data item after creation of said data item version; and determining, based on a MOST-RECENT-INCLUSION-TIME associated with said data item version, whether changes that must be seen by said query have been removed from said data item version. - View Dependent Claims (9)
-
-
10. A computer-readable storage medium comprising instructions executable by one or more processors to instruct the one or more processors to perform steps comprising:
-
maintaining a LAST-TO-SEE-TIMESTAMP, associated with a session, which indicates a time of a last change made in the session that must be seen by the session; maintaining with a data item version a CLONE-TIME that indicates a time at which a clone branch to which the data item version belongs was cloned from a current version of the data item; determining that the data item version is to be supplied to the session based, at least in part, on a comparison between the CLONE-TIME and the LAST-TO-SEE-TIMESTAMP;
supplying the data item version to the session;supplying the data item version to the session; and setting said CLONE-TIME based on a CLONE-TIME of a non-current data item version when said data item version is cloned from said non-current data item version.
-
-
11. A computer-readable storage medium comprising instructions executable by one or more processors to instruct the one or more processors to perform steps comprising:
-
maintaining, for a plurality of data item versions that reside in a plurality of nodes, CLONE-TIME information that indicates when the data item versions were current; wherein, for each data item version of the plurality of data item versions, the CLONE-TIME information for that data item version indicates a time at which a clone branch to which that data item version belongs was cloned from a current version of a particular data item; determining, based at least in part on said CLONE-TIME information, which data item versions of said plurality of data items versions contain all changes that must be seen by a query; selecting a data item version to supply to said query from those data item versions that contain all changes that must be seen by said query; supplying the data item version to said query; and performing at least one of;
(a) presenting information that is based at least in part on the data item version that is supplied to the query, and (b) storing information that is based at least in part on the data item version that is supplied to the query;determining, based on a CLONE-TIME associated with said data item version, whether changes that must be seen by said query have been made to said particular data item after creation of said data item version; and determining, based on a MOST-RECENT-INCLUSION-TIME associated with said data item version, whether changes that must be seen by said query have been removed from said data item version.
-
-
12. A computer-readable storage medium comprising instructions executable by one or more processors to instruct the one or more processors to perform steps comprising:
-
maintaining, for a plurality of data item versions that reside in a plurality of nodes, CLONE-TIME information that indicates when the data item versions were current; wherein, for each data item version of the plurality of data item versions, the CLONE-TIME information for that data item version indicates a time at which a clone branch to which that data item version belongs was cloned from a current version of a particular data item; determining, based at least in part on said CLONE-TIME information, which data item versions of said plurality of data items versions contain all changes that must be seen by a query; selecting a data item version to supply to said query from those data item versions that contain all changes that must be seen by said query; supplying the data item version to said query; and performing at least one of;
(a) presenting information that is based at least in part on the data item version that is supplied to the query, and (b) storing information that is based at least in part on the data item version that is supplied to the query;wherein the step of selecting includes using the CLONE-TIME information to select a candidate that requires fewer changes to be removed than other candidates.
-
-
13. A computer-readable storage medium comprising instructions executable by one or more processors to instruct the one or more processors to perform steps comprising:
-
maintaining a LAST-TO-SEE-TIMESTAMP, associated with a session, which indicates a time of a last change made in the session that must be seen by the session; maintaining with a data item version a CLONE-TIME that indicates a time at which a clone branch to which the data item version belongs was cloned from a current version of the data item; determining that the data item version is to be supplied to the session based, at least in part, on a comparison between the CLONE-TIME and the LAST-TO-SEE-TIMESTAMP; supplying the data item version to the session; and performing at least one of;
(a) presenting information that is based at least in part on the data item version that is supplied to the session, and (b) storing information that is based at least in part on the data item version that is supplied to the session;wherein a transaction that includes a query is executing in the session; wherein the LAST-TO-SEE-TIMESTAMP is associated with the query and indicates a time of a last change made by the transaction that must be seen by the query; and wherein the step of determining that the data item version is to be supplied to the session is performed by determining that the data item version is to be used to answer the query. - View Dependent Claims (14, 15)
-
-
16. A computer-readable storage medium comprising instructions executable by one or more processors to instruct the one or more processors to perform steps comprising:
-
maintaining a LAST-TO-SEE-TIMESTAMP, associated with a session, which indicates a time of a last change made in the session that must be seen by the session; maintaining with a data item version a CLONE-TIME that indicates a time at which a clone branch to which the data item version belongs was cloned from a current version of the data item; determining that the data item version is to be supplied to the session based, at least in part, on a comparison between the CLONE-TIME and the LAST-TO-SEE-TIMESTAMP; supplying the data item version to the session; and performing at least one of;
(a) presenting information that is based at least in part on the data item version that is supplied to the session, and (b) storing information that is based at least in part on the data item version that is supplied to the session;wherein a plurality of nodes in a cluster have data item versions for said data item; maintaining, for each node of said plurality of nodes, CLONE-TIME information for said data item; and selecting which node to send a request for said data item to based on said CLONE-TIME information. - View Dependent Claims (17, 18)
-
Specification