rfc677.txt

RFC 相关的技术文档


RFC 677          The Maintenance of Duplicate Databases     January 1975


of a modification must be positively confirmed before removing a DBMP
from the list of recipients).(2)

    When a DBMP receives an assignment modification (either locally or
from another DBMP) it compares the timestamp of the modification with
the timestamp of the copy of the entry in its database and keeps
whichever is more "recent" as defined by the ordering given above.  Thus
when all existing assignments to a given entry have been distributed to
all the DBMPs, they are guaranteed have the same "latest" value
associated with that entry.


Creation

    Creation and deletion of entries pose more of a problem. Note that
the ability to create new, previously unknown entries requires that a
DBMP be able to handle assignments to unknown entries. For example,
consider the case of an entry XYZ created by DBMP A, and the following
sequence of events: DBMP A tells DBMP B about the new entry, and
subsequently B assigns a new value to XYZ; DBMP B then tells DBMP C
about the assignment before C has heard from A about the creation.  DBMP
C must either save the assignment to XYZ until it hears about the
creation, or simply assume the creation will be coming and use the "new"
entry right away. The latter is more in the spirit of trying to keep the
database as "up-to-date" as possible and leads to no inconsistencies.


Deletion

    Deletion of entries is the main problem for this database system.
If deletion is taken to mean immediate removal from the database, then
problems arise. Consider the following scenario:
        XYZ is an entry known by all DBMPs.
        XYZ is deleted at DBMP A.
        XYZ is modified at DBMP B (before B is notified of the deletion
            by A).
Now, consider a third DBMP, C. C may hear from DBMP B before DBMP A, in
which case XYZ ends up deleted at DBMP C. C may however hear from DBMP A

----------
(2) This same process (local modification and queuing for remote
distribution) is, of course, performed for the other possible operations
on the database. The details of how the local modification is done
safely, how the messages are queued, how confirmation of delivery is
done, etc., though important, will not be discussed here.  The use of an
addressee list attached to the modification to be delivered is
conceptually easy to work with and not difficult to implement in
practice.



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


before DBMP B. In this case, if C removes XYZ from its database, then
the assignment to XYZ initiated by DBMP B will result in the re-creation
of XYZ at DBMP C. To prevent this C must remember that XYZ has been
deleted until it is "safe" to completely forget about XYZ.

    One approach to this problem is to never actually remove an entry
from the database. Deletion just marks the entry as being deleted by
setting a "deleted" flag associated each entry. However, the problem of
receiving assignments to deleted entries still exists. For example, DBMP
A may receive an assignment from DBMP B to an entry which A has marked
as deleted. DBMP A can not tell whether B has not heard about the
deletion, or has heard about it but has also received a re-creation
request for the entry, which hasn't reached DBMP A. To enable A to
resolve such situations we include another timestamp in all entries: the
timestamp of the entry's creation. Thus in the above example, DBMP A can
compare the creation timestamps of the assignment and the deleted entry.
The one with the later creation timestamp is kept. Indeed whenever a
modification with an old creation timestamp is received it can be
ignored.

    We now have a 5-tuple for entries and modifications:
        E ::= (S,V,F,CT,T)
        S is the selector
        V is the associated value
        F is the deleted/not-deleted flag
        CT is the timestamp of creation
        T is the timestamp of this (last) modification

    Note that the values of the F, CT, and T components of a
modification uniquely specify the type of modification. Thus only the
5-tuple to become the new entry for a selector, not the type of
modification, need be communicated:
        F = not deleted, CT = T => creation
        F = not deleted, CT < T => assignment
        F = deleted => deletion

    The mechanism described above handles all the desired operations on
the distributed database in a way that guarantees the consistency of all
copies. A modification to the database will take effect at each DBMP as
soon as it receives the request from the DBMP originating the change.

    A deficiency with this scheme is that deleted entries are never
removed from the database. A method which permits "garbage collection"
of deleted entries is discussed below.







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


Removal of Deleted Entries

    The basic constraint is that a DBMP should not remove a deleted
entry until it will never receive any assignments with the same selector
(S) and the same or older create time (CT). If it fails to do this, then
it will be unable to distinguish these "out of date" assignments from
assignments to a newly created entry for the same S.  To be able do
this, each DBMP must know for each deleted entry whether all other DBMPs
have heard about the deletion. To accomplish this, each DBMP could
notify the other DBMPs whenever it hears about a deletion. If these
notifications are transmitted in order with the "normal" sequence of
modifications, then upon receipt of such a notification a DBMP can be
sure that the sending DBMP has delivered any outstanding assignments to
the deleted entry, has marked it as deleted, and will not generate any
new assignments to it. Keeping track of, and exchanging messages about,
each individual deleted entry in this manner is, however, somewhat more
elaborate than necessary.

    Having each DBMP deliver all its own modifications in sequential
order (by timestamp) allows the following simplification. We have all
DBMPs maintain a table of the timestamps of the last modification
received from each other DBMP. Any DBMP, say A, is then guaranteed to
have received all modifications originating at another DBMP, say B.
which have timestamps earlier than (or equal to) the entry for B in A s
copy of this table. If this table is exchanged between DBMPs, then all
DBMPs would have a second N*N (N= number of DBMPs) table where entry
(I,J) would be the timestamp of the last modification received by DBMP I
from DBMP J. Thus DBMP A can remove a deleted entry whose deletion
originated at DBMP K when all entries in the Kth column of this table at
DBMP A are later than or equal to the timestamp of the deleted entry.
When a DBMP receives a deletion modification, in addition to acting on
it and acknowledging receipt of it, the DBMP should also send its table
of last timestamps received to all other DBMPs. This is sent in a
timestamped message which is queued with the "normal" modification
messages.

    A refinement to this approach, which reduces the amount of
information exchanged and the size of the tables, is to have the DBMPs
exchange only the oldest of the entries in the first table (of
timestamps of last modifications received from other DBMPs). These would
then be saved in a 1*N table, replacing the N*N table. A DBMP receiving
a modification with a timestamp equal to or older than the oldest
timestamp in its second table knows that the modification has been
confirmed as being received by all other DBMPs. A deleted entry can thus
be removed when its timestamp satisfies this condition. A DBMP would,
upon receipt of a deletion modification, queue up a message with this
"timestamp of oldest last modification received" for delivery to all
other DBMPs.



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


Summary of solution:

    An entry in the database is a 5-tuple:
        (S,V,F,CT,T) where
        S is an selector used in all references to this entry.
        V is its present value.
        F is a deleted/undeleted flag.
        CT is the timestamp of the creation of this entry.
        T is the timestamp of the modification which set the current V
          and/or F of the entry.
        A timestamp is a pair (time,DBMP) where the DBMP identifies the
          site at which the time was generated, and the DBMPs are
          (arbitrarily) ordered, so that timestamps are completely
          ordered.

    A modification is a pair (Set-of-DBMPs,Entry) where Set-of-DBMPs is
    the set of DBMPs to which the Entry has yet to be delivered.

    An ordered (by timestamp) list of modifications is kept at each
    DBMP. The DBMP periodically attempts to deliver modification
    requests to those DBMPs which remain in the Set-of-DBMPs associated
    with each modification. Modification entries are removed from this
    list when they have been delivered to all DBMPs.

    When a DBMP receives a modification request from another DBMP, it
    compares the timestamps of the request with the timestamps of the
    corresponding entry (if any) in its database, and acts upon or
    disregards the new entry accordingly.

    Each DBMP keeps a vector of the timestamp (T) of the last
    modification received by it from each other DBMP.

    When a DBMP receives a deletion modification, it sends a timestamped
    message to all other DBMPs containing the oldest timestamp in its
    vector of timestamps of last modification received. Each DBMP keeps
    a second vector of the last of these timestamps received from each
    other DBMP.

    A deleted entry may be removed from the database when its timestamp
    (T) is older than all the timestamps in this second vector of
    timestamps received from other DBMPs.










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


Conclusion

    This paper has presented techniques by which a number of loosely
coupled processes can maintain duplicate copies of a database, despite
the unreliability of their only means of communication. The copies of
the database can be kept "consistent'. However it is possible for
seemingly anomalous behavior to occur. For example a user may assign a
value to a selector using one DBMP, later use another DBMP and assign a
new value, and still later find that the first value is the one that
remains in the database. This can occur if the clocks used by the two
DBMPs for their timestamps are sufficiently out of synchrony that the
second assignment is timestamped as having taken place before the first
assignment. To the extent that the communication paths can be made
reliable, and the clocks used by the processes kept close to synchrony,
the probability of seemingly strange behavior can be made very small.
However, the distributed nature of the system dictates that this
probability can never be zero.

    The major innovation presented here is the explicit representation
of the time sequence of modifications through timestamps for both
modifications and entries. This enables the each DBMP to select the same
"most-recent" modification of an entry. In addition, timestamps enable
the DBMPs to decide when a deleted entry is no longer referenced (i.e.,
still active anywhere) and can be deallocated. These techniques should
have broader utility in building and modeling other systems of
concurrent, cooperating processes.










       [ This RFC was put into machine readable form for entry ]
       [ into the online RFC archives by Alex McKenzie with    ]
       [ support from GTE, formerly BBN Corp.            12/99 ]












Johnson & Thomas                                               [Page 10]