RFC677 日本語訳

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

1975年1月27日のネットワークワーキンググループポールR・ジョンソン(BBN-TENEX)RFC#677ロバートH.トーマス(BBN-TENEX)NIC#31507

                 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.

このRFCはARPAのようなネットワークでコピーされたデータベースを維持するという問題の監査調書です。 それは、簡潔に一般的な写しデータベース問題について議論して、次に、何らかの詳細に特定のタイプに関する写しデータベースの解答について概説します。 ここで開発された概念はTIPユーザー認証と会計システムにUser Identification Databaseのデザインに使用されました。 私たちは、一般に、これらの概念が分散データベース問題に適用可能であると信じています。

Johnson & Thomas                                                [Page 1]

RFC 677          The Maintenance of Duplicate Databases     January 1975

写しデータベース1975年1月のジョンソンとトーマス[1ページ]RFC677維持

Introduction

序論

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

分散ネットワーク環境には余分な写しコピーに関するデータベースを維持することに関する多くの動機があります。 2つの重要な動機は以下の通りです。

  - 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.

重要なデータのアクセシビリティは、冗長にそれを維持することによって、増加できます。 TIPログインと会計に使用されるデータベースは、高信頼性アクセサリーを達成するために冗長に分配されます。

  - 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.)

データは、よりはやくそうであることができます、そして、それが「近い」ときに、効率的にアクセスされて、アクセスは処理されます。 TIPユーザIDデータベースのコピーは急速な状態で保障するTIPログインサービスを支持しながら、各サイトで維持されます、効率的なアクセサリー (信頼性の問題は、このデータベースが冗長に維持されると決めて、効率問題は、コピーがそれぞれの認証サイトで維持されると決めます。)

    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.

独立しているデータベース管理の過程(DBMPs)のグループは、それぞれそれ自身のデータベースのコピーを維持しながら、データベースの写本を支持するシステムをモデル化できます。 これらの過程はネットワーク通信路の上で互いにコミュニケートします。 各DBMPには、データベースのコピーの完全なコントロールがあります。 それはすべての他からの要求に対応したデータベースのアクセスと変更の過程を扱います。 DBMPsは以下での要求だけに作用しますが、それらは実際に変更を引き起こすか、または溯源しているとしばしば言われるでしょう。

    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

重要な設計の検討はDBMPsの間の通信路が失敗を被りやすいということです。 したがって、1DBMPが中断される他のDBMPsとの相互作用を持っているかもしれない、そして/または、他のDBMPsとコミュニケートできる前に通信路が復職するまで、待たなければなりません。 この紙でコミュニケーションに関してされた仮定

Johnson & Thomas                                                [Page 2]

RFC 677          The Maintenance of Duplicate Databases     January 1975

写しデータベース1975年1月のジョンソンとトーマス[2ページ]RFC677維持

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.

経路はそれらが送られる同次で1つの過程から別の過程までのメッセージを送るということです。 これはアルパネットに関して本当です。 どんなそのような保証もしないネットワークにおいて、正しくメッセージを注文するのにDBMPsの間の通信プロトコルを使用できます。

    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.

さらに続くように、コピーされたデータベースとそれで許された操作の本質に関して、より正確であるのが必要です。 1つの極端には一定の書き込み禁止データベースがあります。 DBMPsのタスクはこの場合些細です。 彼らは、検索要求を評価するために単に応じます。 それとは正反対に、機能修飾要求(「X:=f(X、Y、Z)」などの)が許されていて、それが完全に制限するのに必要である一般的な共有データベースはそれらが変更されている間のエントリーへのアクセスですか? この場合、ただ一つのコンピュータ・システムに関する共有データベースのすべての問題が起こります(例えば、同期メカニズムの必要性と結果として起こる潜在的行き詰まり状況)、独立しているコンピュータの中で複数のデータベースコピーを分配させるのにユニークなそれらと同様に。 例えば、完全に一般的なシステムはネットワークが2つ以上のサブネットワークに仕切られるようになる通信障害による可能性に対処しなければなりません。 連動している変更のためのデータベースの原理的にロックを当てにするどんな解決策も非交信サブネットワークにおける過程が、同じ要素をロックするのを試みる可能性を切り抜けなければなりません。 それらの両方にそう(ロック規律に違反する)させなければなりませんか、パーティションがやむまで(任意に時間がかかるかもしれません)、それらの両方が待たなければなりませんか、またはすべての変更と恐らくまた、アクセスに他のものにおけるいくつかのDBMPsの結果として起こる依存と共に何らかの形式の集結されたか階層的なコントロールを使用しなければなりません。

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.

(セレクタ、Value)組であるエントリーの収集としてこの紙で調べられるべきデータベースのタイプの代理をされることができます。 それぞれのセレクタはユニークです、そして、DBMPsに関する限り、値は原子実体です。 提示されるメカニズムは値が、より大きい構造があるハンドルデータベース広げられるところで自分たちで広げられて、(セレクタ、値)組の収集になってください--この拡大だけがここでさらに考えられないということであるかもしれません。

Four operations are to be allowed on the database:

四則はデータベースに許容されることです:

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

1) 選択--セレクタを考えて、現在の関連値を返します。

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

2) 課題--セレクタと値を与えて、与えられた値はセレクタに関連している古い値を取り替えます。

Johnson & Thomas                                                [Page 3]

RFC 677          The Maintenance of Duplicate Databases     January 1975

写しデータベース1975年1月のジョンソンとトーマス[3ページ]RFC677維持

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

3) 創造--新しいセレクタと初期の値を与えて、新しい(セレクタ、初期の値)エントリーをデータベースに追加します。

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

4) 削除セレクタを与えて、データベースから既存(セレクタ、値)のエントリーを取り除きます。

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.

値の変更が課題に制限されることに注意してください。 「Factorial(X)である変化X」などの機能修飾要求は明確に除外されます。 それらを許容すると、システムの広い同期インタロックの使用は強制されるでしょう。

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.

「同じであること」へデータベースの写しを取っておくことができる範囲を調べなければなりません。 DBMPsのコミュニケーションの固有の遅れのために、データベースがいつも同じであることを保証するのは不可能です。 むしろ、私たちの目標はコピーが互いに「一貫していること」を保証することです。 これで、私たちは、各DBMPが他のすべてのDBMPsとコミュニケートできるくらいのどんなエントリー、および時間までのアップデート活動の休止も考えて、次に、そのエントリー(その存在と値)の状態がデータベースのすべてのコピーで同じになると言っています。

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

私たちは、データベースへの変更がそれを維持するDBMPsのどれかで由来することを許可します。 もちろんこれらの変化を他のDBMPsに伝えなければなりません。 一貫性を保障するために、DBMPsのすべてが「最終的である」と考えられる特定のエントリーへの変更がことであるのと同じ決定をしなければなりません。 「最新」の変化を選択するのは望ましいです。 しかしながら、以来、普遍的で、いつもアクセスしやすいジェネレータ(ネットワーク時間規格は十分であるべきである)の、そして、「最新」の一連番号のない分散システムにおける出来事の時間系列に近似できるだけであることを絶対に決定する方法が全くありません。 私たちは各変更にタイムスタンプを関連づけるのによる近似、および各エントリーの、より1時に発表されたタイムスタンプのユニークさ以来現行価値.(1)を設定した変更に関するタイムスタンプである後者を実行します。---------- (1) このような関係においてはそれには単調に増加していて、利用可能であることの必要な特性が妥当な精度と共にあるので、時間は役に立ちます。 これらの特性があるいかなる他の系列ナンバリングスキームも使用できて、得るのが簡単であるので、「時刻」は選ばれました。 主な欠点はそれがしばしば手動で設定されていて(その結果、誤りに傾向がある)であり、システムサービスの間止まるかもしれないということです。

Johnson & Thomas                                                [Page 4]

RFC 677          The Maintenance of Duplicate Databases     January 1975

写しデータベース1975年1月のジョンソンとトーマス[4ページ]RFC677維持

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.

中断。 コンピュータ・システムが、ネットワーク環境に順応することを学ぶとき、独立している時間ソースの使用は、より一般的になるべきです。 これはアルパネットに関するTENEXサイトで起こり始めています。

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:

DBMPを保証できないで、「起源のDBMP」はそれぞれのタイムスタンプの一部として含まれています。 (任意に)DBMPsを注文することによって、私たちには、その結果、唯一タイムスタンプを注文する手段があります。 各タイムスタンプは1組(T、D)です: Tが時間である、DはDBMP識別子です。 2つのタイムスタンプ(T1、D1)と(T2、D2)に関しては、私たちには、以下があります:

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

(T1、D1)>(T2、D2)<が>(T1>T2)と等しいです、または(T1=T2とD1>D2)(T1、D1)は「より最近である」と言われています。(T2、D2)

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

D1=D2とT1=T2であるなら、2つの変更が本当にコピー2部の同じ変更要求であると思われます。

    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.

タイムスタンプのユニークさを保障するために、それぞれの個々のDBMPがいろいろな時間を異なった変更に関連づけるのが必要です。 確かに、これはするのにおいて可能です、時間の単位の品位がただ一つのDBMPサイトで変更の頻度を制限するかもしれませんが。

    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

現在、データベースにおける各エントリーは三重です: E:、:= (S、V、T), SがどこのセレクタVであるかは関連値Tがエントリーへの最後の変化に関するタイムスタンプ(Time、DBMPは対にする)であるということです。

    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.

それぞれのDBMPに関するタスクは上から日付であって、与えることへデータベースの写しを取っておくために、それが持っている変更の情報に今までのところ受信されたということです。 同時に、それは、それぞれのエントリーが他のすべてのDBMPsのものと一致しているままであることを保障しなければなりません。 それが変更を受けるオーダーがそれらが他のDBMPsによって受け取られるオーダーと非常に異なるかもしれないという事実にもかかわらず、これをしなければなりません。 この紙の残りでは、私たちはDBMP操作へのそれらの効果に関して許容できるデータベース操作を調べます。

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

既存のエントリーと課題に関するケースを考えてください。 課題が開始されるとき(人か工程で)、かかわったDBMPは局所的に変更を行って、変更されたエントリーのコピーと変化を送らなければならないDBMPsの関連リストを作成します。 他のDBMPsに変更を渡すとき、どんなDBMPsも残らないまで、リストから彼らを取り除きます。 そして、変更のコピーは削除されます。 この分配メカニズムがエラーのないに違いない、(すなわち、領収書

Johnson & Thomas                                                [Page 5]

RFC 677          The Maintenance of Duplicate Databases     January 1975

写しデータベース1975年1月のジョンソンとトーマス[5ページ]RFC677維持

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

受取人のリストからDBMPを取り外す前にaでは、明確に変更を確認しなければならない、)(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.

DBMPが課題変更(局所的か別のDBMPからの)を受けるとき、それは、データベースにおけるエントリーのコピーに関するタイムスタンプと変更に関するタイムスタンプを比べて、保たれます(上で与えられた注文で定義されるように「最近よりです」)。 与えられたエントリーへのすべての既存の課題をすべてのDBMPsに広げてあるとき、その結果、彼らは保証されます。そのエントリーに関連している同じ「最新」値を持ってください。

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.

エントリーの創造と削除は一層の問題を引き起こします。 新しくて、以前に未知のエントリーを作成する能力が、DBMPが未知のエントリーに課題を扱うことができるのを必要とすることに注意してください。 例えば、エントリーに関するケースがDBMP Aによって作成されたXYZと、出来事の以下の系列であると考えてください: DBMP Aは新しいエントリーに関してDBMP Bに話します、そして、次にBは新しい値をXYZに割り当てます。 そして、Cが創造に関してAから聞かれる前にDBMP Bは課題に関してDBMP Cに話します。 DBMP Cは、創造について聞くまでXYZに課題を保存しなければならないか、または創造がすぐ「新しい」エントリーを使用しに来ると単に仮定しなければなりません。 後者は、さらに「最新である」としてのデータベースを可能に保とうとする精神にはあって、どんな矛盾にもつながりません。

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

エントリーの削除はこのデータベース・システムのための主な問題です。 データベースから即座の取り外しを意味するために削除を取るなら、問題は起こります。 以下のシナリオを考えてください: XYZはすべてのDBMPsによって知られていたエントリーです。 XYZはDBMP Bで変更されたDBMP A. XYZで削除されます(BがAによって削除について通知される前に)。 今度は、第3のDBMPを考えてください、とC.CはDBMP Aの前でDBMP Bから聞くかもしれなくて、しかしながら、XYZがどの場合にDBMP C.Cで削除されていた状態で終わるかは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.

---------- (2) この同じ過程(リモート分配のための地方の変更と列を作り)は他の可能な操作のためにもちろんデータベースに実行されます。 地方の変更がどう安全に完了しているかに関する詳細、メッセージがどう列に並ばせられるか、配送の確認がどう完了しているか、重要ですが、ここでなどについて議論しないでしょう。 提供される変更に添付された受け取り人リストの使用は、実際には概念的に扱いやすくて実行するのは難しくはありません。

Johnson & Thomas                                                [Page 6]

RFC 677          The Maintenance of Duplicate Databases     January 1975

写しデータベース1975年1月のジョンソンとトーマス[6ページ]RFC677維持

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.

次に、DBMP Bによって開始されたXYZへの課題がCがデータベースからXYZを取り外すならそうするDBMP B.In本件の前では、ToがこのCを防ぐというDBMP C.のXYZの改造における結果は、XYZを完全に忘れるのが「安全になる」まで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.

この問題への1つのアプローチは実際にデータベースからエントリーを決して取り除かないことです。 「削除された」旗を設定することによって削除されるのが各エントリーを関連づけたので、削除はただエントリーを示します。 しかしながら、削除されたエントリーに課題を受け取るという問題はまだ存在しています。 例えば、DBMP AはDBMP BからAが削除されるように示したエントリーまでの課題を受け取るかもしれません。 Bが削除について聞いていなかったか、またはそれについて聞きましたが、DBMP A.Toに達していないエントリーを求める改造要求を受け取ったか否かに関係なくも、Aが言うことができないDBMPが、Aがそのような状況を決議するのを可能にするので、私たちはすべてのエントリーで別のタイムスタンプを入れます: エントリーの創造に関するタイムスタンプ。 したがって、上記の例では、DBMP Aは課題と削除されたエントリーに関する創造タイムスタンプを比較できます。 後の創造タイムスタンプがあるものは保たれます。 本当に、古い創造タイムスタンプがある変更が受け取られているときはいつも、それを無視できます。

    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

私たちは現在、エントリーと変更のための5-tupleを持っています: E:、:= (S、V、F、コネチカット、T) SによるセレクタVが関連値Fが削除されたか削除されなかった旗のコネチカットによる創造Tに関するタイムスタンプがこの(最後)の変更に関するタイムスタンプであるということであるということであるということであるということです。

    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

変更のF、コネチカット、およびTコンポーネントの値が唯一変更のタイプを指定することに注意してください。 したがって、変更のタイプではなく、セレクタのための新しいエントリーになる5-tupleだけが伝えられなければなりません: 削除されなかったF=、コネチカット=Tは=が削除しなかった>創造Fと等しいです、>=が削除した>コネチカット<T=課題F=削除

    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.

メカニズムは分散データベースでハンドルの上にすべてのコピーの一貫性を保証する方法ですべての必要な操作について説明しました。 変化を溯源するDBMPから要求を受け取るとすぐに、データベースへの変更は各DBMPで実施するでしょう。

    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

写しデータベース1975年1月のジョンソンとトーマス[7ページ]RFC677維持

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.

基本的な規制が同じセレクタ(S)と同じくらいでどんな課題も決して受け取らないまでDBMPが削除されたエントリーを取り除くはずがないということである、 より古い、時間(コネチカット)を作成してください。 同じS.Toのために課題から新たに作成されたエントリーまでこれらの「時代遅れ」課題を区別するために、できてください。これをしないとであることができないこれをしてください、と他のすべてのDBMPsが削除について聞いたか否かに関係なく、各DBMPはそれぞれの削除されたエントリーに知らなければなりません。 これを達成するために、削除について聞くときはいつも、各DBMPは他のDBMPsに通知できました。 これらの通知が変更の「正常な」系列で整然とした状態で伝えられるなら、そのような通知を受け取り次第、DBMPは発信しているDBMPがどんな傑出している課題も削除されたエントリーに届けて、削除されるとしてそれをマークして、どんな新しい課題もそれに発生させないのを確信している場合があります。 しかしながら、それぞれの個々の削除されたエントリーに関して動向をおさえて、メッセージを交換するのはこの様に必要とするよりいくらか入念です。

    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.

各DBMPに連続したオーダー(タイムスタンプによる)におけるそれ自身のすべての変更を提供させると、以下の簡素化は許されます。 私たちはすべてのDBMPsに最後の変更に関するタイムスタンプのテーブルが互いからのDBMPを受けたと主張させます。 次に、どんなDBMP(たとえば、A)も別のDBMPで由来するすべての変更を受けたために保証されます、より早くタイムスタンプを持っている言いたい事B.、(等しい)、このテーブルのA sコピーのBのためのエントリー。 DBMPsの間でこのテーブルを交換するなら、DBMPsが第2のN*N(NはDBMPsの数と等しい)にエントリー(I、J)がDBMP Iによって受けられた最後の変更に関するタイムスタンプであるところでDBMP J.Thus DBMP Aからテーブルの上に置かせるすべてがすべてのエントリーがDBMP Aのこのテーブルに関するKthコラムにおいて削除されたエントリーに関するタイムスタンプと、より遅いか、または等しいときに削除がDBMP Kで由来した削除されたエントリーを取り除くことができます。 また、それに影響して、それの領収書を受け取ったことを知らせることに加えてDBMPが削除変更を受けるとき、DBMPは他のすべてのDBMPsに受け取られた最後のタイムスタンプのテーブルを送るはずです。 「正常な」変更メッセージで列に並ばせられるtimestampedメッセージでこれを送ります。

    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.

交換された情報量とテーブルのサイズを減少させるこのアプローチへの気品はDBMPs交換をエントリーで単に最初のテーブル(他のDBMPsから受けられた最後の変更に関するタイムスタンプの)で最も古くすることです。 そして、N*Nテーブルを取り替えて、これらは1*Nテーブルで救われるでしょう。 第2テーブルでは、タイムスタンプが等しいか、または最も古いタイムスタンプより古い状態で変更を受けるDBMPは、他のすべてのDBMPsによって受け取られるとして変更が確認されたのを知っています。 その結果、タイムスタンプがこの状態を満たすと、削除されたエントリーを取り除くことができます。 削除変更を受け取り次第、DBMPは配送のためにこの「最後の最も古い変更に関するタイムスタンプは受信であったこと」で他のすべてのDBMPsにメッセージの列を作るでしょう。

Johnson & Thomas                                                [Page 8]

RFC 677          The Maintenance of Duplicate Databases     January 1975

写しデータベース1975年1月のジョンソンとトーマス[8ページ]RFC677維持

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.

データベースへの登録は5-tupleです: (S、V、F、コネチカット、T) Sがこのエントリーのすべての参照で使用されるセレクタであるところ。 Vはその現在価値です。 Fは削除されたか非削除された旗です。 コネチカットはこのエントリーの創造に関するタイムスタンプです。 Tは変更に関するタイムスタンプです(エントリーの電流V、そして/または、Fを設定します)。 タイムスタンプはDBMPが時間が発生したサイトを特定して、DBMPsが(任意に)注文される1組(時間、DBMP)です、タイムスタンプが完全に注文されるように。

    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.

変更はDBMPsのSetがEntryがまだ渡されていないDBMPsのセットである1組(DBMPsのセット、Entry)です。

    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.

規則正しい(タイムスタンプによる)変更箇所一覧は各DBMPに保たれます。 DBMPは、定期的にDBMPsのSetに各変更に関連していたままで残っているそれらのDBMPsに変更要求を渡すのを試みます。 すべての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.

DBMPが別のDBMPから変更要求を受け取るとき、それは、それに従って、新しいエントリーをデータベースで対応するエントリーに関するタイムスタンプと要求に関するタイムスタンプを比べて(もしあれば)、作用するか、または無視します。

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

DBMPがDBMPであることをそれによって互いから受けられた最後の変更に関するタイムスタンプ(T)のベクトルに保つそれぞれ。

    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.

DBMPが削除変更を受けるとき、それは最後の変更に関するタイムスタンプのベクトルで最も古いタイムスタンプが受けた他のすべてのDBMPs含有にtimestampedメッセージを送ります。 各DBMPは互いから受け取られたこれらのタイムスタンプの最終2番目のベクトルに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.

タイムスタンプ(T)がタイムスタンプのこの2番目のベクトルにおけるすべてのタイムスタンプが他のDBMPsから受信されたより古いときに、データベースから削除されたエントリーを取り除くかもしれません。

Johnson & Thomas                                                [Page 9]

RFC 677          The Maintenance of Duplicate Databases     January 1975

写しデータベース1975年1月のジョンソンとトーマス[9ページ]RFC677維持

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.

この紙は多くの緩く結合した過程がデータベースの写本を維持できるテクニックを提示しました、それらのコミュニケーションの唯一の手段の非信頼性にもかかわらず。 '「一貫していること'へデータベースの写しを取っておくことができます」。 しかしながら、外観上変則的な振舞いが起こるのは、可能です。 例えば、ユーザは、1DBMPを使用することで値をセレクタに割り当てて、後で別のDBMPを使用して、新しい値を割り当てて、後で最初の値がデータベースに残っているものであることがまだわかっているかもしれません。 彼らのタイムスタンプに2DBMPsによって使用された時計が十分、起こるなら、これは最初の課題の前に行われて、2番目の課題がtimestampedされる同期から起こることができます。 外観上奇妙な振舞いの確率を非常に小さく通信路を信頼できるようにすることができて、工程で使用される時計が同期の近くに保たれたという範囲まで、することができます。 しかしながら、システムの分配された本質は、この確率がゼロであるはずがないと決めます。

    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.

ここに提示された主要な革新は変更とエントリーの両方のためのタイムスタンプを通した変更の時間系列の明白な表現です。 これが可能にする、エントリーの同じ「最新」の変更を選択する各DBMP。 さらに、タイムスタンプは、DBMPsがいつ削除されたエントリーにもう参照をつけないで(すなわち、どこでもまだアクティブな)、「反-割り当て」ることができるかを決めるのを可能にします。 これらのテクニックは同時発生の他のシステム、協調処理を建てて、モデル化する際に、より広いユーティリティを持つべきです。

       [ 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 ]

[このRFCはエントリーのためのマシンに入れられた読み込み可能なフォームでした]、[アレックス・マッケンジーによるオンラインRFCアーカイブ、][GTEからのサポート、以前BBN社12/99]

Johnson & Thomas                                               [Page 10]

ジョンソンとトーマス[10ページ]