WARNING:
JavaScript is turned OFF. None of the links on this concept map will
work until it is reactivated.
If you need help turning JavaScript On, click here.
This Concept Map, created with IHMC CmapTools, has information related to: ch15 repl tran, Transactions with replicated data ???? objects in transactional systems are replicated to enhance availability and performance the effect of transactions on replicated objects should be the same as if they had been performed one at a time on a single set of objects. this property is called one-copy serializability. it is similar to, but not to be confused with, sequential consistency. sequential consistency does not take transactions into account each RM provides concurrency control and recovery of its own objects we assume two-phase locking in this section replication makes recovery more complicated when an RM recovers, it restores its objects with information from other RMs, a number of ‘votes’ is assigned to each physical copy of a logical file at an RM a vote is a weighting giving the desirability of using a particular copy. each read operation must obtain a read quorum of R votes before it can read from any up-to-date copy each write operation must obtain a write quorum of W votes before it can do an update operation. R and W are set for a group of replica managers such that W > half the total votes R + W > total number of votes for the group ensuring that any pair contain common copies (i.e. a read quorum and a write quorum or two write quora) therefore in a partition it is not possible to perform conflicting operations on the same file, but in different partitions. ???? groups of RMs can be configured to give different performance or reliability characteristics once the R and W have been chosen for a set of RMs: the reliability and performance of write operations may be increased by decreasing W and similarly for reads by decreasing R the performance of read operations is degraded by the need to collect a read consensus examples from Gifford three examples show the range of properties that can be achieved by allocating weights to the various RMs in a group and assigning R and W appropriately weak representatives (on local disk) have zero votes, get a read quorum from RMs with votes and then read from the local copy, Transactions with replicated data Available copies Replica manager failure An RM can fail by crashing and is replaced by a new process the new process restores its state from its recovery file FEs use timeouts in case an RM fails then try the request at another RM in the case of a write, the RM passing it on may observe failures If an RM is doing recovery, it rejects requests (& FE tries another RM) For one-copy serializability, failures and recoveries are serialized with respect to transactions that is, if a transaction observes that a failure occurs, it must be observed before it started or after it finished one-copy serializability is not achieved if different transactions make conflicting failure observations, Transactions with replicated data Available copies replication the simple read one/write all scheme is not realistic because it cannot be carried out if some of the RMs are unavailable, either because the have crashed or because of a communication failure the available copies replication scheme is designed to allow some RMs to be temporarily unavailable a read request can be performed by any available RM writes requests are performed by the receiving RM and all other available RMs in the group, Transactions with replicated data Quorum consensus methods To prevent transactions in different partitions from producing inconsistent results make a rule that operations can be performed in only one of the partitions. RMs in different partitions cannot communicate: each subgroup decides independently whether they can perform operations. A quorum is a subgroup of RMs whose size gives it the right to perform operations. e.g. if having the majority of the RMs could be the criterion in quorum consensus schemes update operations may be performed by a subset of the RMs and the other RMs have out-of-date copies version numbers or timestamps are used to determine which copies are up-to-date operations are applied only to copies with the current version number, Transactions with replicated data Architectures for replicated transactions We assume that an FE sends requests to one of a group of RMs in the primary copy approach, all FEs communicate with a single RM which propagates updates to back-ups. In other schemes, FEs may communicate with any RM and coordination between RMs is more complex an RM that receives a request is responsible for getting cooperation from the other RMs rules as to how many RMs are involved vary with the replication scheme e.g. in the read one/write all scheme, one RM is required for a read request and all RMs for a write request propagate requests immediately or at the end of a transaction? in the primary copy scheme, we can wait until end of transaction (concurrency control is applied at the primary) but if transactions access the same objects at different RMs, we need to propagate the requests so that concurrency control can be applied two-phase commit protocol becomes a two-level nested 2PC. If a coordinator or worker is an RM it will communicate with other RMs that it passed requests to during the transaction, a number of ‘votes’ is assigned to each physical copy of a logical file at an RM a vote is a weighting giving the desirability of using a particular copy. each read operation must obtain a read quorum of R votes before it can read from any up-to-date copy each write operation must obtain a write quorum of W votes before it can do an update operation. R and W are set for a group of replica managers such that W > half the total votes R + W > total number of votes for the group ensuring that any pair contain common copies (i.e. a read quorum and a write quorum or two write quora) therefore in a partition it is not possible to perform conflicting operations on the same file, but in different partitions. ???? before a read operation, a read quorum is collected by making version number enquiries at RMs to find a set of copies, the sum of whose votes is not less than R (not all of these copies need be up to date). as each read quorum overlaps with every write quorum, every read quorum is certain to include at least one current copy. the read operation may be applied to any up-to-date copy. before a write operation, a write quorum is collected by making version number enquiries at RMs to find a set with up-to-date copies, the sum of whose votes is not less than W. if there are insufficient up-to-date copies, then an out-of-date file is replaced with a current one, to enable the quorum to be established. the write operation is then applied by each RM in the write quorum, the version number is incremented and completion is reported to the client. the files at the remaining available RMs are then updated in the background. Two-phase read/write locking is used for concurrency control the version number enquiry sets read locks (read and write quora overlap), Replica manager failure An RM can fail by crashing and is replaced by a new process the new process restores its state from its recovery file FEs use timeouts in case an RM fails then try the request at another RM in the case of a write, the RM passing it on may observe failures If an RM is doing recovery, it rejects requests (& FE tries another RM) For one-copy serializability, failures and recoveries are serialized with respect to transactions that is, if a transaction observes that a failure occurs, it must be observed before it started or after it finished one-copy serializability is not achieved if different transactions make conflicting failure observations Gifford’s quorum consensus file replication scheme a number of ‘votes’ is assigned to each physical copy of a logical file at an RM a vote is a weighting giving the desirability of using a particular copy. each read operation must obtain a read quorum of R votes before it can read from any up-to-date copy each write operation must obtain a write quorum of W votes before it can do an update operation. R and W are set for a group of replica managers such that W > half the total votes R + W > total number of votes for the group ensuring that any pair contain common copies (i.e. a read quorum and a write quorum or two write quora) therefore in a partition it is not possible to perform conflicting operations on the same file, but in different partitions.