rfc677.txt

RFC 相关的技术文档

Network Working Group                       Paul R. Johnson (BBN-TENEX)
RFC # 677                                   Robert H. Thomas (BBN-TENEX)
NIC # 31507                                 January 27, 1975





                 The Maintenance of Duplicate Databases


Preface:

This RFC is a working paper on the problem of maintaining duplicated
databases in an ARPA-like network. It briefly discusses the general
duplicate database problem, and then outlines in some detail a solution
for a particular type of duplicate database.  The concepts developed
here were used in the design of the User Identification Database for the
TIP user authentication and accounting system. We believe that these
concepts are generally applicable to distributed database problems.































Johnson & Thomas                                                [Page 1]

RFC 677          The Maintenance of Duplicate Databases     January 1975


Introduction

    There are a number of motivations for maintaining redundant,
duplicate copies of databases in a distributed network environment.  Two
important motivations are:

  - to increase reliability of data access.

    The accessibility of critical data can be increased by redundantly
    maintaining it. The database used for TIP login and accounting is
    redundantly distributed to achieve highly reliable access.

  - to insure efficiency of data access.

    Data can be more quickly and efficiently accessed when it is "near"
    the accessing process. A copy of the TIP user ID database is
    maintained at each site supporting the TIP login service to insure
    rapid, efficient access.  (Reliability considerations dictate that
    this database be redundantly maintained, and efficiency
    considerations dictate that a copy be maintained at each
    authentication site.)

    The design of a system to maintain redundant, duplicate databases is
a challenging task because of the inherent communication delay between
copies of the database, as well as the real world constraints of system
crashes, operator error, communication channel failure, etc.  This paper
discusses some of the problems we encountered in designing such a
system, and outlines a system design for maintaining a particular type
of database which solves those problems.


The Model

    A system for supporting duplicate copies of a database can be
modeled by a group of independent database management processes (DBMPs)
each maintaining its own copy of the database. These processes
communicate with each other over network communication paths. Each DBMP
has complete control over its copy of the database. It handles all
accesses to and modifications of the database in response to requests
from other processes. Though the DBMPs act only upon requests, in the
following they will often be said to be actually causing or originating
the modifications.

    An important design consideration is that the communication paths
between the DBMPs are subject to failures. Thus one DBMP may have its
interactions with other DBMPs interrupted and/or have to wait until
communication paths are re-established before it can communicate with
other DBMPs. An assumption made in this paper about the communication



Johnson & Thomas                                                [Page 2]

RFC 677          The Maintenance of Duplicate Databases     January 1975


paths is that messages from one process to another are delivered in the
same order that they are sent. This is true of the ARPANET. For networks
that make no such guarantee, communication protocols between the DBMPs
can be used to correctly order the messages.

    In order to proceed further, it is necessary to be more precise
about the nature of the duplicated database and the operations allowed
on it. A constant, read-only database is at one extreme. The task of the
DBMPs is trivial in this case. They simply respond to value retrieval
requests. At the other extreme is a general shared database where
functional modification requests (such as "X := f(X,Y,Z)") are allowed
and/or where it is necessary to completely restrict access to entries
while they are being modified. In this case all the problems of shared
databases on a single computer system arise (e.g., the need for
synchronization mechanisms and the resulting potential deadlock
situations), as well as those unique to having multiple database copies
distributed among independent computers. For example, a completely
general system must deal with the possibility of communication failures
which cause the network to become partitioned into two or more sub-
networks. Any solution which relies on locking an element of the
database for synchronized modification must cope with the possibility of
processes in non-communicating sub-networks attempting to lock the same
element. Either they both must be allowed to do so (which violates the
lock discipline), or they both must wait till the partition ceases
(which may take arbitrarily long), or some form of centralized or
hierarchical control must be used, with a resulting dependency of some
DBMPs on others for all modifications and perhaps accesses as well.


The Database

    The type of database to be examined in this paper can be represented
as a collection of entries which are (Selector,Value) pairs. Each
selector is unique and the values are atomic entities as far as the
DBMPs are concerned. The mechanisms to be presented may be extended to
handle databases with greater structure - where the values may
themselves be collections of (selector,value) pairs - but this extension
will not be considered further here.

Four operations are to be allowed on the database:

    1) Selection - given a selector, the current associated value is
    returned.

    2) Assignment - a selector and a value are given and the given value
    replaces the old value associated with the selector.





Johnson & Thomas                                                [Page 3]

RFC 677          The Maintenance of Duplicate Databases     January 1975


    3) Creation - a new selector and an initial value are given and a
    new (selector,initial value) entry is added to the database.

    4) Deletion- a selector is given and the existing (selector,value)
    entry is removed from the database.

Note that value modification is limited to assignment. Functional
modification requests - such as "Change X to be Factorial(X)" - are
specifically ruled out. Allowing them would force the use of system wide
synchronization interlocks.


Consistency

    The extent to which the copies of the database can be kept
"identical" must be examined. Because of the inherent delay in
communications between DBMPs, it is impossible to guarantee that the
data bases are identical at all times. Rather, our goal is to guarantee
that the copies are "consistent" with each other. By this we mean that
given a cessation of update activity to any entry, and enough time for
each DBMP to communicate with all other DBMPs, then the state of that
entry (its existence and value) will be identical in all copies of the
database.


Timestamps

    We permit modifications to the database to originate at any of the
DBMPs maintaining it. These changes must, of course, be communicated to
the other DBMPs. To insure consistency, all of the DBMPs must make the
same decision as to which modification to a particular entry is to be
considered "final". It is desirable to select the "most recent" change.
However, since there is no way to absolutely determine the time sequence
of events in a distributed system without a universal, always accessible
sequence number generator (a network time standard should suffice),
"most recent" can only be approximated. We accomplish the approximation
by associating a timestamp with each modification and with each entry,
the latter being the timestamp of the modification which set its current
value.(1) Since the uniqueness of timestamps given out at more than one
----------
(1) Time is useful in this context because it has the desired properties
of being monotonically increasing, and of being available with a
reasonable degree of accuracy. Any other sequence numbering scheme with
these properties can be used, "time-of-day" was chosen because it is
simple to obtain. Its main faults are that it is often manually set (and
thus prone to error), and it may stop during system service





Johnson & Thomas                                                [Page 4]

RFC 677          The Maintenance of Duplicate Databases     January 1975


interruptions. As computer systems learn to adapt to a network
environment, the use of an independent time source should become more
common. This is beginning to happen with the TENEX sites on the ARPANET.

DBMP can not be guaranteed, a "DBMP of origin" is included as part of
each timestamp. By (arbitrarily) ordering the DBMPs, we thus have a
means of uniquely ordering timestamps. Each
 timestamp is a pair (T,D): T is a time, D is a DBMP identifier. For two
timestamps (T1,D1) and (T2,D2) we have the following:

    (T1,D1)>(T2,D2) <=> (T1>T2) or (T1=T2 and D1>D2)
    (T1,D1) is said to be "more recent" than (T2,D2)

    If D1=D2 and T1=T2 it is assumed that the two modifications are
    really two copies of the same modification request.

    In order to insure the uniqueness of timestamps, it is necessary
that each individual DBMP associate different times with different
modifications. This is certainly possible to do, though the fineness of
the unit of time may restrict the frequency of modifications at a single
DBMP site.

    Each entry in the data base is now a triple:
      E ::= (S,V,T), where
      S is the selector
      V is the associated value
      T is the timestamp (a Time,DBMP pair) of the last change to the
        entry

    The task of each DBMP is to keep its copy of the database up-to-
date, given the information on modifications that it has received so
far. At the same time it must insure that each of its entries stays
consistent with those of all the other DBMPs. This must be done despite
the fact that the order in which it receives modifications may be very
different from the order in which they are received by other DBMPs. In
the remainder of this paper we examine the allowable database operations
with respect to their effect on DBMP operation.


Assignment

    Consider the case of assignment to an existing entry. When the
assignment is initiated (by a person or process) the DBMP involved makes
the change locally, and creates a copy of the modified entry and an
associated list of DBMPs to which the change must be sent. As the
modification is delivered to the other DBMPs, they are removed from the
list until no DBMPs remain. The copy of the modification is then
deleted. This distribution mechanism must be error free (i.e., receipt



Johnson & Thomas                                                [Page 5]