Methodology for managing weakly consistent replicated databases

• US 5,581,754 A
• Filed: 12/07/1994
• Issued: 12/03/1996
• Est. Priority Date: 12/07/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): Alam, Hosain T.
• Application Number:
  US08/352,012
• Time in Patent Office: 727 Days
• Field of Search: 395/600, 395/425, 395/575, 395/650, 395/725, 395/800, 395/153-161, 395/200.03
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2329 using versioning
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99939 Privileged access

Abstract

Write operations for weakly consistent replicated database systems have embedded conflict detection and conflict resolution procedures for identifying and resolving, respectively conflicts between such write operations and the current state of any given instance of such a database. These write operations are committed to a firm execution order by the host for one instance of such a database, and this execution order propagates to the other instances of the database. Accordingly, a write log distinguishes between the writes that are known to be committed to a firm execution order (the "tentative writes") is maintained for each instance of the database, thereby enabling the user to explicitly identifying the stable data and the potentially unstable data in any given instance of the database. Furthermore, provision is made for enabling users to select from a set of predefined consistency guarantees across all instances of such a database for any given session.

Claims

1. A methodology for managing weakly consistent replicated databases, said methodology comprising

including respective application-specific dependency checking mechanisms in write operations for identifying write operations that conflict with any instance of said database that said write operations are prepared to update;

including respective application-specific conflict resolution mechanisms in said write operations for resolving any conflicts identified by said dependency checking mechanisms;

maintaining committed and tentative portions of a write log for each instance of said database to distinguish between write updates for said instance of said database that do and do not have a firm execution order, respectively; and

enforcing any enforceable session consistency guarantees that have been selected for a particular session across all instances of said database for said session.