Maintaining consistency of database replicas

  • US 6,098,078 A
  • Filed: 12/23/1996
  • Issued: 08/01/2000
  • Est. Priority Date: 12/29/1995
  • Status: Expired due to Term
  • ×
    • Pin Icon | RPX Insight
    • Pin
First Claim
Patent Images

1. In a computer network comprising at least one server for serving at least one client, said network being adapted for storing a plurality of database replicas, each of said database replicas comprising a plurality of data items, a method for maintaining consistency among corresponding data items in said database replicas without the need to examine content or version information for every one of said data items in any of said database replicas, comprising the steps of:

  • generating a database version vector for each of at least a pair of said database replicas, each of said database version vectors comprising a plurality of version vector components, said version vector components being one-to-one associated with each of said servers having one of said database replicas, each of said version vector components reflecting the number of updates previously performed on said corresponding data item at said server;

    associating version information with each of said data items in each of said database replicas;

    maintaining one or more logs of updates associated with each of said database replicas;

    each of said logs having the property that, for every data item x in a particular one of said database replicas and every server j that has one of said database replicas, said log for said particular database replica contains at least a log record 1(x,j) of the last update to data item x at server j that is reflected in said particular database replica'"'"'s copy of data item x, said log record containing at least the name of data item x and the total update count of all updates that server j had seen at the time of the last update made from server j to said particular database replica; and

    determining which of said data items in each of said database replicas needs updating in order to restore complete consistency among each of said data items in a pair of said database replicas. comprising the steps, in combination of;

    comparing the database version vectors of said pair of said database replicas in a component-wise fashion in order to make an initial threshold determination of whether any of said data items in any of said database replicas have been recently updated and thus require that a full comparison be made at the data item level; and

    determining, without the need to examine said version information of all of said data items, which individual data items in each of said database replicas needs updating with updates present in corresponding data items of another database replica, comprising the steps of;

    for every server j having one of said database replicas with a version vector component in its associated database version vector that is greater than the corresponding version vector component in the database version vector of said particular database replica, determining which of said log records 1(x,j) on said server j have a total update count that exceeds the total number of updates obtained from said corresponding version vector component of the database version vector for said particular database; and

    determining therefrom that the corresponding data items in said particular database replica are older than the corresponding data items in said server j'"'"'s database replica and therefore need to be updated.

View all claims
    ×
    ×

    Thank you for your feedback

    ×
    ×