Semantic transactions in online applications

• US 8,825,743 B2
• Filed: 07/11/2008
• Issued: 09/02/2014
• Est. Priority Date: 07/12/2007
• Status: Active Grant

• Current Assignee: Cornell University
• Original Assignee: Cornell University
• Inventors: Gehrke, Johannes E., Gupta, Nitin, Unterbrunner, Philipp T., Demers, Alan J.
• Primary Examiner(s): Bengzon, Greg C
• Application Number:
  US12/668,697
• Publication Number:
  US 20100198914A1
• Time in Patent Office: 2,244 Days
• Field of Search: None
• 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 computer implemented method for enabling distributed transaction processing comprising the steps of:

(a) executing, at a client, a transaction against a local copy of objects;

the transaction occurring in a multiplayer online game;

annotating, at the client, the transaction with semantics, the semantics comprising a read set, the read set being a subset of an application state that determines execution characteristics of the transaction, and a write set, the write set being a subset of the application state that can be affected by the transaction;

(b) generating, at the client, tentative copies of the objects if necessary;

(c) committing or aborting, at the client, the generated copies if necessary;

(d) sending to a server the transaction, the transaction being timestamped at the server and integrated to a global log according to the transaction timestamp;

(e) receiving, at the client, a projection of the global log;

(f) validating, at the client, the transaction with respect to the projection; and

(g) installing, at the client, any updates to the transaction into a local replica if said step of validating is successful;

wherein application logic is located at the client; and

wherein steps (a) through (g) are performed by one or more processors executing computer readable code embodied in non-transitory computer usable media.

2. The method as in claim 1 further comprising the steps of:

combining a plurality of the transactions into a schedule; and

executing, at the client, the schedule according to the transaction timestamps.

3. The method as in claim 1 wherein the client comprises a plurality of the clients.

6. The method as in claim 3 further comprising the step of:

sending the transaction to a subset of the plurality of the clients.

7. The method as in claim 3 wherein at least one attribute of one of the plurality of clients 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 and

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

16. A physical node equipment in a communications network configured for carrying out the method of claim 1;

the method being carried out by the node in the communications network executing computer readable code embodied in non-transitory computer usable media.

17. A communications network having a physical node equipment configured for carrying out the method of claim 1;

the method being carried out by the node in the communications network executing computer readable code embodied in non-transitory computer usable media.

18. A non-transitory computer readable medium having instructions for carrying out the method of claim 1.

4. A computer enabled method for enabling distributed transaction processing comprising the steps of:

(a) executing, at a client, a transaction against a local copy of objects;

the transaction occurring in a multiplayer online game;

(b) generating, at the client, tentative copies of the objects if necessary;

(c) committing or aborting, at the client, the generated copies if necessary;

(d) sending to a server the transaction;

the transaction being timestamped at the server and integrated to a global log according to the transaction timestamp;

(e) receiving, at the client, a projection of the global log at the client;

(f) validating, at the client, the transaction with respect to the projection; and

(g) installing, at the client, any updates to the transaction into a local replica if said step of validating is successful;

wherein application logic is located at the client; and

wherein the client comprises a plurality of the clients; and

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 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 if it was issued by the one of the plurality of clients 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 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;

wherein steps (a) through (g) and (j) through (m) are performed by one or more processors executing computer readable code embodied in non-transitory computer usable media.

5. The method as in claim 4 further comprising the step of:

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

9. A system for enabling distributed transaction processing comprising:

one or more clients, each client comprising;

a tentative execution processor machine component configured for

executing a transaction against local copies of objects;

the transaction occurring in a multiplayer online game;

annotating the transaction with semantics, the semantics comprising a read set, the read set being a subset of an application state that determines execution characteristics of the transaction, and a write set, the write set being a subset of the application state that can be affected by the transaction; and

generating tentative copies of said objects if necessary;

an integration processor machine component configured for

committing or aborting said tentative copies if necessary;

sending to a server said transaction

a validation processor machine component configured for validating, at said client, said transaction with respect to said projection and

an installation processor machine component configured for installing any updates to said transaction into a local replica if said transaction is validated; and

a server comprising

another integration processor machine component configured for

timestamping said transaction;

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

sending a projection of said global log to said one or more clients;

wherein application logic is located at each one of said one or more clients; and

wherein the tentative execution processor, the integration processor, the validation processor and the installation processor are configured for executing recited functions by control information stored in non-transitory computer readable media.

10. The system as in claim 9 wherein said tentative execution processor machine component is further configured for:

combining a plurality of said transactions into a schedule; and

executing, at said client said schedule according to the transaction timestamps.

13. The system as in claim 9 wherein said another integration processor machine component is further configured for:

sending said transaction to a subset of said one or more clients.

14. The system as in claim 9 wherein attributes of at least one of said one or more clients can change.

15. The system as in claim 14 wherein said tentative execution processor machine component is further configured for:

setting boundaries for said change of said attributes of said client; and

invoking said integration processor, said validation processor, and said installation processor when said client is substantially close to said boundaries.

11. A system for enabling distributed transaction processing comprising:

a tentative execution processor machine component configured for

executing, at a client, a transaction against local copies of objects;

the transaction occurring in a multiplayer online game; and

generating tentative copies of said objects if necessary;

an integration processor machine component configured for

committing or aborting said tentative copies if necessary;

sending to a server said transaction;

timestamping said transaction;

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

sending a projection of said global log to said client;

a validation processor machine component configured for validating, at said client, said transaction with respect to said projection; and

an installation processor machine component configured for installing any updates to said transaction into a local replica if said transaction is validated;

wherein said client includes a plurality of said clients;

wherein the tentative execution processor, the integration processor, the validation processor machine component and the installation processor machine component are configured for executing computer readable code embodied in non-transitory computer usable media, and

wherein said validation processor machine component is further configured to;

(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 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 if it was issued by the one of the plurality of clients 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 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.

12. The system as in claim 11 wherein said validation processor machine component is further configured to:

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