Distributed Databases and Replication

Part II

Data Science 310

Boston University

Recall: Fragmentation / Sharding

  • Here’s a relation from a centralized bank database:

  • Here’s one way of fragmenting it:

Recall: Replication

  • Replication involves putting copies of the same collection of records at different sites.

Recall: Distributed Concurrency Control (cont.)

  • Example of why special steps are needed:
    • voting-based synchronous replication with 6 replicas
    • let’s say that we configure the voting as before:
      • each write updates 3 copies
      • each read accesses 4 copies
    • can end up with schedules that are not conflict serializable
    • example:

What Do We Need?

  • We need shared and exclusive locks for a logical item, not just for individual copies of that item.
  • referred to as global locks
  • doesn’t necessarily mean locking every copy
  • Requirements for global locks:
    • no two txns can hold a global exclusive lock for the same item
  • any number of txns can hold a global shared lock for an item
  • a txn cannot acquire a global exclusive lock on an item if another txn holds a global shared lock on that item, and vice versa

What Do We Need? (cont.)

  • In addition, we need to ensure the correct ordering of operations within each distributed transaction.
    • don’t want a subtxn to get ahead of where it should be in the context of the txn as a whole
  • relevant even in the absence of replication
  • one option: have the coordinator of the txn acquire the necessary locks before sending operations to a site

Option 1: Centralized Locking

  • One site manages the lock requests for all items in the distributed database.
    • even items that don’t have copies stored at that site
  • since there’s only one place to acquire locks, these locks are obviously global locks!
  • Problems with this approach?
  • the lock site can become a bottleneck
  • if the lock site crashes, operations at all sites are blocked

Option 2: Primary-Copy Locking

  • One copy of an item is designated the primary copy.
  • The site holding the primary copy handles all lock requests for that item.
  • acquiring a shared lock for the primary copy gives you a global shared lock for the item
  • acquiring an exclusive lock for the primary copy gives you a global exclusive lock for the item
  • To prevent one site from becoming a bottleneck, distribute the primary copies among the sites.
  • Problem: If a site goes down, operations are blocked on all items for which it holds the primary copy.

Option 3: Fully Distributed Locking

  • No one site is responsible for managing lock requests for a given item.
  • A transaction acquires a global lock for an item by locking a sufficient number of the item’s copies.
  • these local locks combine to form the global lock
  • To acquire a global shared lock, acquire local shared locks for a sufficient number of copies (see next slide).
  • To acquire a global exclusive lock, acquire local exclusive locks for a sufficient number of copies (see next slide).

Option 3: Fully Distributed Locking (cont.)

  • How many copies must be locked?
    • let:   n = the total number of copies
          x = the number of copies that must be locked to acquire a global exclusive lock

      s = the number of copies that must be locked to acquire a global shared lock

  • we need x > n/2
    • guarantees that no two txns can both acquire a global exclusive lock at the same time
  • we need s > n – x  (i.e., s + x > n)
  • if there’s a global exclusive lock on an item, there aren’t enough unlocked copies for a global shared lock
  • if there’s a global shared lock on an item, there aren’t enough unlocked copies for a global excl. lock

Option 3: Fully Distributed Locking (cont.)

  • Our earlier example would no longer be possible:

Synchronous Replication and Fully Distributed Locking

  • Read-any write-all:
    • when writing an item, a txn must update all of the replicas
  • this gives it x = n exclusive locks, so x > n/2
  • when reading an item, a txn can access any of the replicas
  • this gives it s = 1 shared lock, and 1 > n – n
  • Voting:
    • when writing, a txn updates a majority of the copies – i.e., w copies, where w > n/2.
  • this gives it x > n/2 exclusive locks as required
  • when reading, a txn reads r > n – w copies
  • this gives it s > n – x shared locks as required

Which of these would work?

  • 9 replicas – i.e., 9 copies of each item
  • fully distributed locking
  • voting-based approach with the following requirements (number of copies):
read written
A. 5 5
B. 6 4
C. 7 3
D. 4 5

(select all that work)

Distributed Deadlock Handling

  • Under centralized locking, we can just use the waits-for graphs that we studied earlier in the semester.
  • Under the other two locking schemes, deadlock detection becomes more difficult.
  • local waits-for graphs alone will not necessarily detect a deadlock
    • example:

  • one option: periodically send local waits-for graphs to one site that checks for deadlocks
  • Instead of using deadlock detection, it’s often easier to use a timeout-based scheme.
    • if a txn waits too long, presume deadlock and roll it back!

Recall: Types of Replication

  • In synchronous replication, transactions are guaranteed to see the most up-to-date value of an item.
  • In asynchronous replication, transactions are not guaranteed to see the most up-to-date value.

Asynchronous Replication I: Primary Site

  • In primary-site replication, one replica is designated the primary or master replica.
  • All writes go to the primary.
    • propagated asynchronously to the other replicas (the secondaries)
  • The secondaries can only be read.
    • no locks are acquired when accessing them
    • thus, we only use them when performing read-only txns
  • Drawbacks of this approach?

Asynchronous Replication II: Peer-to-Peer

  • In peer-to-peer replication, more than one replica can be updated.
  • Problem: need to somehow resolve conflicting updates!