SEMANTIC TRANSACTIONS IN ONLINE APPLICATIONS

• US 20100198914A1
• Filed: 07/11/2008
• Published: 08/05/2010
• Est. Priority Date: 07/12/2007
• Status: Active Grant

• Current Assignee: Cornell University
• Original Assignee: Cornell University
• Inventors: Gupta, Nitin, Gehrke, Johannes E., Unterbrunner, Philipp T., Demers, Alan J.
• Granted Patent: US 8,825,743 B2
• Time in Patent Office: Days
• US Class Current: 709/203
• CPC Class Codes: G06F 16/2315 Optimistic concurrency control
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 9/466 Transaction processing

Abstract

A system and method for enabling distributed transaction processing by moving all application logic away from the server and into the client by using an optimistic concurrency control framework with client-side transaction validation including virtual full replication under a transactional programming model with full Atomicity, Consistency, Isolation, and Durability (ACID) properties.

Claims

1. :

A method for enabling distributed transaction processing comprising the steps of;

(a) executing (101), at a client (17), a transaction (21) against a local copy of objects (34);

(b) generating (103) tentative copies of the objects (34) if necessary;

(c) committing (105) or aborting the generated copies if necessary;

(d) sending (107) to a server (11) the transaction (21);

(e) timestamping (109) the transaction (21);

(f) integrating (111), at the server (11) the transaction (21) to a global log(37) according to the transaction timestamp;

(g) sending (113) a projection of the global log(37) to the client (17);

(h) validating (115), at the client (17), the transaction (21) with respect to the projection; and

(i) installing (117) any updates to the transaction (21) into a local replica (35) if said step of validating is successful.

2. :

The method as in claim 1 further comprising the steps of;

combining a plurality of the transactions (21) into a schedule (23); and

executing, at the client (17), the schedule (23) according to the transaction timestamps.

3. :

The method as in claim 1 wherein the client (17) comprises a plurality of the clients (17).

4. :

The method as in claim 3 wherein said step of validating comprises the steps of;

(j) locally certifying a read r_j(x_i) of T_j if and only if T_i was issued by the same one of the plurality of clients (17) as T_j and if and only if T_i has issued a commit request, or T_i has committed;

(k) locally certifying a write w_j(x_j) of T_j if and only if (I) no write w_k(x_k) with k>

j has already been locally certified, and (II) no reads r_k(x_i) where k>

j have been locally certified;

(l) locally certifying the transaction (21) if it was issued by the one of the plurality of clients (17) performing said step of validating, and said steps of locally certifying the read and locally certifying the write succeed, and a commit request is encountered; and

(m) locally aborting the transaction (21) if one of said steps of locally certifying the read or locally certifying the write is not successful, or the read or the write is aborted,

wherein i, j, and k are times, r_j(x_i) is defined as a read at time j of object x committed at time i, T_i|T_j are transactions at times i and j, and w_j(x_j) is defined as a write at time j of object x committed at time j.

5. :

The method as in claim 4 further comprising the step of;

appending an abort step to the schedule (23) if and only if the transaction (21) is aborted because one of said steps (j) (m) was not successful, and because the client (17) performing said step of validation is one of the plurality of clients (17) that initiated the transaction (21).

6. :

The method as in claim 3 further comprising the step of;

sending the transaction (21) to a subset of the plurality of the clients (17).

7. :

The method as in claim 3 wherein at least one attribute of one of the plurality of clients (17) can change.

8. :

The method as in claim 7 further comprising the step of;

setting boundaries for the change of the at least one attribute of the client (17); and

performing steps (c)-(i) when the client (17) is substantially close to the boundaries.

17. :

A node in a communications network for carrying out the method of claim 1.

18. :

A computer program product for carrying out the method of claim 1.

19. :

A communications network having a node for carrying out the method of claim 1.

20. :

A computer readable medium having instructions for carrying out the method of claim 1.

9. :

A system (100) for enabling distributed transaction processing comprising;

a tentative execution processor (25) for

executing, at a client (17), a transaction (21) against local copies (36) of objects (34); and

generating tentative copies (38) of said objects (34) if necessary;

an integration processor (27) for

committing or aborting said tentative copies (38) if necessary;

sending to a server (11) said transaction (21);

timestamping said transaction (21);

integrating, at said server (11) the timestamped transaction to a global log(37) according to the transaction timestamp; and

sending a projection (42) of said global log(37) to said client (17);

a validation processor (29) for validating, at said client (17), said transaction (21) with respect to said projection (42); and

an installation processor (31) for installing any updates to said transaction (21) into a local replica (35) if said transaction (21) is validated.

10. :

The system (100) as in claim 9 wherein said a tentative execution processor (25) is further for;

combining a plurality of said transactions (21) into a schedule (23); and

executing, at said client (17), said schedule (23) according to the transaction timestamps.

11. :

The system (100) as in claim 9 wherein said client (17) includes a plurality of said clients (17).

12. :

The system (100) as in claim 11 wherein said validation processor (29) is further for;

(j) locally certifying a read r_j(x_i) of T_j if and only if T_i was issued by the same one of said plurality of said clients (17) as T_j and if and only if T_i has issued a commit request, or T_i has committed;

(k) locally certifying a write w_j(x_j) of T_j if and only if (I) no write w_k(x_k) with k>

j has already been locally certified, and (II) no reads r_k(x_i) where k>

j have been locally certified;

(l) locally certifying said transaction (21) if it was issued by the one of the plurality of clients (17) performing said step of validating, and said steps of locally certifying said read and locally certifying said write succeed, and a commit request is encountered; and

(m) locally aborting said transaction (21) if one of said steps of locally certifying said read or locally certifying said write is not successful, or said read or said write is aborted,

wherein i, j, and k are times, r_j(x_i) is defined as said read at time j of object x committed at time i, T_i|T_j are transactions at times i and j, and w_j(x_j) is defined as said write at time j of object x committed at time j.

13. :

The system (100) as in claim 12 wherein said validation processor (29) is further for;

appending an abort step to said schedule (23) if and only if said transaction (21) is aborted because one of said steps (j)-(m) was not successful, and because said client (17) executing said validation processor (29) is one of said plurality of said clients (17) that initiated said transaction (21).

14. :

The system (100) as in claim 11 wherein said integration processor (27) is further for;

sending said transaction (21) to a subset of said plurality of said clients (17).

15. :

The system (100) as in claim 11 wherein attributes of at least one of said plurality of clients (17) can change.

16. :

The system (100) as in claim 15 wherein said tentative execution processor (25) is further for;

setting boundaries for said change of said attributes of said client (17); and

invoking said integration processor (27), said validation processor (29), and said installation processor (31) when said client (17) is substantially close to said boundaries.