The failure and recovery problem for replicated databases
The failure and recovery problem for replicated databases
复制标题
复制数据库的故障与恢复问题
DOI：
10.1145/800221.806714
复制
发表时间：
1983
期刊：
影响因子：
--
通讯作者：
N. Goodman
中科院分区：
文献类型：
--
作者：
P. Bernstein;N. Goodman
复制数据库是一种分布式数据库，其中一些数据项冗余地存储在多个站点。主要目标是提高系统的可靠性。通过将关键数据存储在多个站点，即使一些站点出现故障，该系统也可以运行。然而，很少有分布式数据库系统支持复制数据，因为在站点发生故障和恢复时很难管理复制数据。
复制数据算法由两部分组成。一个是用于读取和写入数据项副本的规程。另一个是用于同步这些操作的并发控制算法。读写规程确保如果一个事务写入逻辑数据项x，而另一个事务读取或写入x，则存在该逻辑冲突的某些物理表现。并发控制算法同步物理冲突；它对逻辑冲突一无所知。在正确的复制数据算法中，冲突的物理表现必须足够强，以便同步物理冲突就足以保证正确性。
本文提出了一种理论来证明管理复制数据的算法的正确性。该理论是可串行化理论的扩展。我们将其应用于三种复制数据算法：Gifford的“Quorum Consensus”算法、Eagger和Sevcik的“Missing Writes”算法以及美国计算机公司的“Available Copies”算法。
A replicated database is a distributed database in which some data items are stored redundantly at multiple sites. The main goal is to improve system reliability. By storing critical data at multiple sites, the system can operate even though some sites have failed. However, few distributed database systems support replicated data, because it is difficult to manage as sites fail and recover.
A replicated data algorithm has two parts. One is a discipline for reading and writing data item copies. The other is a concurrency control algorithm for synchronizing those operations. The read-write discipline ensures that if one transaction writes logical data item ×, and another transaction reads or writes x, there is some physical manifestation of that logical conflict. The concurrency control algorithm synchronizes physical conflicts; it knows nothing about logical conflicts. In a correct replicated data algorithm, the physical manifestation of conflicts must be strong enough so that synchronizing physical conflicts is sufficient for correctness.
This paper presents a theory for proving the correctness of algorithms that manage replicated data. The theory is an extension of serializability theory. We apply it to three replicated data algorithms: Gifford's “quorum consensus” algorithm, Eager and Sevcik's “missing writes” algorithm, and Computer Corporation of America's “available copies” algorithm.