Database Replication (Synthesis Lectures on Data Management, 7)

Database replication is widely used for fault-tolerance, scalability and performance. The failure of one database replica does not stop the system from working as available replicas can take over the tasks of the failed replica. Scalability can be achieved by distributing the load across all replicas, and adding new replicas should the load increase. Finally, database replication can provide fast local access, even if clients are geographically distributed clients, if data copies are located close to clients. Despite its advantages, replication is not a straightforward technique to apply, and there are many hurdles to overcome. At the forefront is replica control: assuring that data copies remain consistent when updates occur. There exist many alternatives in regard to where updates can occur and when changes are propagated to data copies, how changes are applied, where the replication tool is located, etc. A particular challenge is to combine replica control with transaction management as it requires several operations to be treated as a single logical unit, and it provides atomicity, consistency, isolation and durability across the replicated system. The book provides a categorization of replica control mechanisms, presents several replica and concurrency control mechanisms in detail, and discusses many of the issues that arise when such solutions need to be implemented within or on top of relational database systems. Furthermore, the book presents the tasks that are needed to build a fault-tolerant replication solution, provides an overview of load-balancing strategies that allow load to be equally distributed across all replicas, and introduces the concept of self-provisioning that allows the replicated system to dynamically decide on the number of replicas that are needed to handle the current load. As performance evaluation is a crucial aspect when developing a replication tool, the book presents an analytical model of the scalability potential of various replication solution. For readers that are only interested in getting a good overview of the challenges of database replication and the general mechanisms of how to implement replication solutions, we recommend to read Chapters 1 to 4. For readers that want to get a more complete picture and a discussion of advanced issues, we further recommend the Chapters 5, 8, 9 and 10. Finally, Chapters 6 and 7 are of interest for those who want get familiar with thorough algorithm design and correctness reasoning. Table of Contents: Overview / 1-Copy-Equivalence and Consistency / Basic Protocols / Replication Architecture / The Scalability of Replication / Eager Replication and 1-Copy-Serializability / 1-Copy-Snapshot Isolation / Lazy Replication / Self-Configuration and Elasticity / Other Aspects of Replication Motivation......Page 13 Replica Control......Page 16 Other Issues......Page 18 Replication Model......Page 21 1-Copy-Isolation......Page 22 1-Copy-Atomicity......Page 25 Relationship Between Isolation, Atomicity and Durability......Page 26 Session Consistency.......Page 27 Eventual Consistency......Page 28 Protocol Description......Page 31 Example Execution......Page 33 Eager Properties......Page 34 Primary Copy vs. Update Anywhere......Page 35 Lazy vs. Eager Properties......Page 37 Primary Copy vs. Update Anywhere......Page 39 Summary......Page 41 Replication Architecture......Page 43 Middleware Based Architecture......Page 44 Kernel vs. Middleware Based Replication......Page 46 Processing of Write Operations......Page 47 Partial Replication......Page 49 Other Issues......Page 50 Group Communication and Reliable Multicast......Page 52 Simplifying Replication with Group Communication......Page 55 Related Work......Page 57 The Scalability of Replication......Page 59 Model......Page 60 The Analysis......Page 61 Related Work......Page 63 Eager Replication and 1-Copy-Serializability......Page 65 Example Execution......Page 66 Algorithm Properties......Page 67 Decentralized Middleware......Page 69 Protocol......Page 70 Example Execution......Page 71 Algorithm Properties......Page 72 Discussion......Page 73 Example Execution......Page 74 Algorithm Properties......Page 75 Related Work......Page 76 1-Copy-Snapshot Isolation......Page 79 Snapshot Isolation in a Non-Replicated System......Page 80 Snapshot Isolation in a Replicated System......Page 82 Primary Copy -- Centralized Middleware......Page 83 Example Execution......Page 84 Algorithm Properties......Page 87 Update Anywhere -- Centralized Middleware......Page 88 Protocol......Page 89 Algorithm Properties......Page 91 Update-Anywhere -- Decentralized Middleware......Page 93 Protocol Description......Page 94 Example Execution......Page 95 Snapshot Isolation vs. Traditional Optimistic Concurrency Control......Page 97 Related Work......Page 98 Boundary Types......Page 101 Basic Implementation......Page 102 Push vs. Pull Based Refresh......Page 103 Transaction Propagation......Page 104 Multiple Primaries......Page 106 Distributed vs. Central Conflict Management......Page 108 Conflict Detection......Page 109 Conflict Resolution......Page 111 Bounding Staleness......Page 113 Conflict Detection and Resolution......Page 114 Self-Configuration and Elasticity......Page 115 Failure Types......Page 116 Failover: Client Side......Page 117 Failover: Server Side......Page 118 Recovery......Page 120 Load-Balancing......Page 122 Other Optimization Techniques......Page 125 System Reconfiguration......Page 126 Deciding on the Right Number of Replicas......Page 127 Related Work......Page 128 Multi-Tier Architectures......Page 131 Quorums......Page 132 Mobile and Peer-to-Peer Environments......Page 133 Consistency......Page 135 Isolation......Page 136 Distributed Transactions and 2-Phase Commit......Page 139 Bibliography......Page 141 Authors' Biographies......Page 152 1. Overview Motivation Challenges Replica control Other issues 2. 1-copy-equivalence and consistency Replication model 1-copy-isolation 1-copy-atomicity 1-copy-durability Relationship between isolation, atomicity and durability 1-copy-consistency Session consistency Eventual consistency 3. Basic protocols Eager protocols Protocol description Example execution Eager properties Primary copy vs. update anywhere Lazy protocols Protocol description Example execution Lazy vs. eager properties Primary copy vs. update anywhere Summary 4. Replication architecture Where to locate the replication logic Kernel based architecture Middleware based architecture Kernel vs. middleware based replication Black vs. grey box middleware Processing of write operations Partial replication Other issues Group communication as building block Group communication and reliable multicast Simplifying replication with group communication Related work 5. The scalability of replication Model The analysis Related work 6. Eager replication and 1-copy-serializability Centralized middleware Protocol Example execution Algorithm properties Discussion Decentralized middleware Protocol Example execution Algorithm properties Discussion Decentralized middleware with asymmetric processing Protocol Example execution Algorithm properties Related work 7. 1-copy-snapshot isolation 1-copy-snapshot isolation Snapshot isolation in a non-replicated system Snapshot isolation in a replicated system Primary copy, centralized middleware Protocol Example execution Algorithm properties Update anywhere, centralized middleware Protocol Example execution Algorithm properties Update-anywhere, decentralized middleware Protocol description Example execution Algorithm properties Snapshot isolation vs.traditional optimistic concurrency control Related work 8. Lazy replication Bounding the staleness in lazy primary copy Boundary types Basic implementation Push vs. pull based refresh Materialized views Transaction propagation Multiple primaries Lazy update anywhere Distributed vs. central conflict management Conflict detection Conflict resolution Related work Bounding staleness Replica placement Conflict detection and resolution 9. Self-configuration and elasticity Self-healing Fault-tolerant measures during normal processing Failure types Failover: client side Failover: server side Recovery Self-optimization Load-balancing Other optimization techniques Elasticity: self-provisioning System reconfiguration Deciding on the right number of replicas Related work 10. Other aspects of replication Multi-tier architectures Quorums Mobile and peer-to-peer environments A. Transactions and the ACID properties A.1. Atomicity A.2. Consistency A.3. Durability A.4. Isolation A.5. Distributed transactions and 2-phase commit Bibliography Authors' biographies.