Relaxed currency constraints

• US 20060219772A1
• Filed: 04/01/2005
• Published: 10/05/2006
• Est. Priority Date: 04/01/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ramakrishnan, Raghu, Bernstein, Philip A., Fekete, Alan D.
• Granted Patent: US 7,677,441 B2
• Time in Patent Office: Days
• US Class Current: 235/379
• CPC Class Codes: G06F 16/2308 Concurrency control transaction processing G06F9/466
• CPC Class Codes: G06F 16/2322 using timestamps
• CPC Class Codes: G06F 16/2329 using versioning
• CPC Class Codes: G06F 16/2343 Locking methods, e.g. distributed locking or locking implementation details
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

The subject invention pertains to transaction processing systems and methodologies that allows update transactions to read stale data copies and update a data store therewith. Each transactional operation, including a read, can carry or be associated with one or more freshness constraints or tests that specify how fresh a data copy must be in order to be read. More specifically, the subject invention provides systems and methods that extend transactions and serializability to account for out-of-date reads that are justified by freshness requirements.

Claims

1. A database update system comprising:

a receiver component that receives a database update transaction;

a process component that reads stale data and processes the transaction; and

a verification component to verify one or more freshness constraints associated with the transaction are satisfied during processing and/or at commit time.

2. The system of claim 1, the process component reads from a cache the stale data that satisfies one or more freshness constraints associated with the transaction.

3. The system of claim 2, at least one of the freshness constraints is time bound and limits the amount of time between the time a version becomes invalid and the time it is read.

4. The system of claim 2, at least one of the freshness constraints is value bound and specifies a percentage a read data value can vary from the value of a valid version.

5. The system of claim 2, at least one of the freshness constraints requires that when more than one data item is read, the data items be read from the same snapshot and the data items be read within a specified time of each other.

6. The system of claim 2, at least one of the freshness constraints requires that an aggregate computed over a read set of the transaction be within a specified percentage of a recent value.

7. The system of claim 2, each data item or group of data has metadata associated therewith identifying when the data item or group was last modified and when it is valid until to facilitate definition and enforcement of freshness constraints.

8. The system of claim 7, the verification component enforces a time bound freshness constraint via a determination of whether a time stamp associated with the execution of the transaction is less than or equal to the valid until time associated with a data item read by the transaction plus some specified period of time.

9. The system of claim 7, the verification component enforces a time-drift bound freshness constraint via a determination of whether the last modified time of the most recently modified data item read by the transaction is less than the minimum time a data item read by the transaction is valid until plus a specified time period.

10. A database update system for relaxed currency constraints ensuring the result is relaxed currency serializable comprising:

a means for reading out-of-date data associated with an update transaction and verifying it satisfies freshness constraints at read time; and

a means for verifying satisfaction of freshness constraints at commit time.

11. A method of transactional database interaction comprising:

reading stale cached data;

verifying that the read data satisfies one or more currency constraints associated with a transaction;

updating a database with the data from the cache; and

verifying the one or more currency constraints are satisfied at commit time.

12. The method of claim 11, a currency constraint is satisfied when data is read within a programmable time.

13. The method of claim 11, a currency constraint is satisfied when the value of data read is within a percentage of a value of a valid version.

14. The method of claim 11, a currency constraint is satisfied when more than one data item is read and the data items are read from the same snapshot.

15. The method of claim 11, a currency constraint is satisfied when the data items read are within a specified time of each other.

16. The method of claim 11, a currency constraint is satisfied when an aggregate computed over a set of data items read is within a specified percentage of a recent value.

17. The method of claim 11, further comprising associating a last modified timestamp and a valid-till timestamp with each copy of data.

18. The method of claim 17, verifying satisfaction of one or more constraints comprises determining whether a timestamp associated with the transaction is less than or equal to the valid-till timestamp associated with the data being read plus a specified period of time.

19. The method of claim 17, verifying satisfaction of one or more constraints comprises:

determining whether a set of data items to be read by the transaction is associated with the same snapshot; and

identifying the largest last-modified timestamp associated with a data item in the set;

identifying the smallest valid-till timestamp associated with a data item in the set; and

determining whether the largest last-modified timestamp is less than the smallest valid-till timestamp plus a specified period of time.

20. The method of claim 11, further comprising assigning the transaction a timestamp that is that is consistent with the constraints.