Method for providing session consistency guarantees

• US 5,581,753 A
• Filed: 09/28/1994
• Issued: 12/03/1996
• Est. Priority Date: 09/28/1994
• Status: Expired due to Term

• Current Assignee: Yoranso Consulting LLC (Intellectual Ventures LLC)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Terry, Douglas B., Theimer, Marvin M., Spreitzer, Michael J., Welch, Brent B., Demers, Alan J., Petersen, Karin
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): PHAM, CUAN
• Application Number:
  US08/314,971
• Time in Patent Office: 797 Days
• Field of Search: 395/600, 395/325, 395/200, 395/575, 395/650, 395/480, 395/489
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1402 Saving, restoring, recovering or retrying
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

The present invention provides client-selected consistency guarantees to clients of a weakly consistent replicated database on a per "session" basis. The clients have access to utilities which allow the clients to, individually or collectively, define a "session" over which the selected guarantees are enforced. A "session" is broadly defined as a sequence of logically related Reads and Writes to the database. Sessions are initiated and terminated substantially independently of other sessions which may exist concurrently. Clients are allowed, however, to clone sessions and/or merge sessions with other clients. Clients select a minimum relevant subset of guarantees from among a set of pre-defined consistency guarantees, where "relevancy" is a client determined factor. At any given time, the system may be enforcing a number of different combinations of consistency guarantees. The guarantees ensure that all clients participating in a particular session view the database as having certain conditions of data consistency--the consistency of which is only provided with respect to the participants'"'"' Read and Write requests. Clients are allowed to downgrade their selected guarantees during the course of their sessions. One implementation of the present invention permits the selection of any one of four consistency guarantees.

Claims

1. In a database system having a plurality of servers, a plurality of clients, where at least some of said clients may access different servers at different times, including times when said servers contain inconsistent data values;

said servers storing weakly consistent replicated data;

said data being accessible and updatable by said clients; and

said data, once updated, being propagated by servers having said updated data to servers that do not have said updated data;

a method for providing relevant consistency guarantees for said data to every client participating in any session on a per session basis with respect to access and update requests belonging to each respective session, the steps of said method comprising;

A) defining a plurality of sessions, such that each of said sessions is composed of database access and update requests of at least one client;

B) selecting a client specified relevant subset of consistency guarantees for each session from a set of predefined, mutually distinguishable guarantees, where the relevancy of a given guarantee is decided by at least one of said clients; and

C) enforcing the selected guarantees for said at least one client during the course of said session even when said at least one client accesses different servers during the session.

2. The method for providing consistency guarantees as recited in claim 1 wherein the step of defining a session further comprises the step of initiating a session.

3. The method for providing consistency guarantees as recited in claim 1 wherein the step of defining a session further comprises the step of terminating a session.

4. The method for providing consistency guarantees as recited in claim 1 wherein the step of defining a session further comprises the step of cloning a session.

5. The method for providing consistency guarantees as recited in claim 1 wherein the step of defining a session further comprises the step of merging at least two sessions.

6. The method for providing consistency guarantees as recited in claim 1 wherein the step of defining a session further comprises the step of downgrading the set of guarantees during the course of a session.

7. The method for providing consistency guarantees as recited in claim 1 wherein said clients update data and access data at said servers by issuing a WRITE and a READ command respectively.

8. The method for providing consistency guarantees as recited in claim 7 wherein one of said session guarantees comprises the condition:

if Read R follows Write W in a session and R is performed at server S at time t, then W is included in DB(S,t).

9. The method for providing consistency guarantees as recited in claim 7 wherein one of said session guarantees comprises the condition:

if Read R1 occurs before R2 in a session and R1 accesses server S1 at time t1 and R2 accesses server S2 at time t2, then RelevantWrites(S1,t1,R1) is a subset of DB(S2,t2).

10. The method for providing consistency guarantees as recited in claim 7 wherein one of said session guarantees comprises the condition:

if Read R1 precedes Write W2 in a session and R1 is performed at server S1 at time t1, then, for any server S2, if W2 is in DB(S2) then any W1 in RelevantWrites(S1,t1,R1) is also in DB(S2) and WriteOrder(W1,W2).

11. The method for providing consistency guarantees as recited in claim 7 wherein one of said session guarantees comprises the condition:

if Read R1 precedes Write W2 in a session and R1 is performed at server S1 at time t1, then, for any server S2, if W2 is in DB(S2) then any W1 in RelevantWrites(S1,t1,R1) is also in DB(S2).

12. The method for providing consistency guarantees as recited in claim 7 wherein one of said session guarantees comprises the condition:

if Read R1 precedes Write W2 in a session and R1 is performed at server S1 at time t1, then, for any server S2, if W2 is in DB(S2) then, for any W1 in RelevantWrites(S1,t1,R1), WriteOrder(W1,W2).

13. The method for providing consistency guarantees as recited in claim 7 wherein one of said session guarantees comprises the condition:

if Write W1 precedes Write W2 in a session, then, for any server S2, if W2 in DB(S2) then W1 is also in DB(S2) and WriteOrder(W1,W2).

14. The method for providing consistency guarantees as recited in claim 7 wherein one of said session guarantees comprises the condition:

if Write W1 precedes Write W2 in a session, then, for any server S2, if W2 in DB(S2) then W1 is also in DB(S2).

15. The method for providing consistency guarantees as recited in claim 7 wherein one of said session guarantees comprises the condition:

if Write W1 precedes Write W2 in a session, then, for any server S2, if W2 in DB(S2) then WriteOrder(W1,W2).

16. The method for providing consistency guarantees as recited in claim 1 wherein the step of enforcing the guarantees further comprises the steps of:

locating at least one reachable server; and

discovering whether said at least one reachable server satisfies the selected guarantees.

17. The method for providing consistency guarantees as recited in claim 16 wherein the step of discovering further comprises the step of informing the client if no suitable server is found.