Distributed Databases and Replication

Part I

Data Science 310

Boston University

What Is a Distributed Database?

• One in which data is:
  • partitioned / fragmented among multiple machines

     and/or

• replicated – copies of the same data are made available on multiple machines

• It is managed by a distributed DBMS (DDBMS) – processes on two or more machines that jointly provide access to a single logical database.

• The machines in question may be:
  • at different locations (e.g., different branches of a bank)
  • at the same location (e.g., a cluster of machines)

• In the remaining slides, we will use the term site to mean one of the machines involved in a DDBMS.
  • may or may not be at the same location

What Is a Distributed Database? (cont.)

• A given site may have a local copy of all, part, or none of a particular database.

• makes requests of other sites as needed

Fragmentation / Sharding

• Divides up a database’s records among several sites
  • the resulting “pieces” are known as fragments/shards

• Let R be a collection of records of the same type (e.g., a relation).

• Horizontal fragmentation divides up the “rows” of R.
  • R(a, b, c)→ R1(a, b, c), R2(a, b, c), …

• R = R1 ∪ R2 ∪ …

• Vertical fragmentation divides up the “columns” of R.
  • R(a, b, c) → R1(a, b), R2(a, c), … (a is the primary key)

• R = R1 ⋈ R2 ⋈ …

Fragmentation / Sharding (cont.)

• Another version of vertical fragmentation: divide up the tables (or other collections of records).

• e.g., site 1 gets tables A and B
     site 2 gets tables C and D

Example of Fragmentation

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

• Here’s one way of fragmenting it:

Replication

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

Reasons for Using a DDBMS

• to improve performance
  • how does distribution do this?

• to provide high availability
  • replication allows a database to remain available in the event of a failure at one site

• to allow for modular growth
  • add sites as demand increases
  • adapt to changes in organizational structure

• to integrate data from two or more existing systems
  • without needing to combine them

• allows for the continued use of legacy systems

• gives users a unified view of data maintained by different organizations

Challenges of Using a DDBMS (partial list)

• determining the best way to distribute the data
  • when should we use vertical/horizontal fragmentation?
  • what should be replicated, and how many copies do we need?

• determining the best way to execute a query
  • need to factor in communication costs

• maintaining integrity constraints (primary key, foreign key, etc.)

• ensuring that copies of replicated data remain consistent

• managing distributed txns: ones that involve data at multiple sites
  • atomicity and isolation can be harder to guarantee

Failures in a DDBMS

• In addition to the failures that can occur in a centralized system, there are additional types of failures for a DDBMS.

• These include:
  • the loss or corruption of messages
    • TCP/IP handles this type of error

• the failure of a site

• the failure of a communication link
  • can often be dealt with by rerouting the messages

• network partition: failures prevent communication between two subgroups of the sites

Distributed Transactions

• A distributed transaction involves data stored at multiple sites.

• One of the sites serves as the coordinator of the transaction.
  • one option: the site on which the txn originated

• The coordinator divides a distributed transaction into subtransactions, each of which executes on one of the sites.

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.

Synchronous Replication I: Read-Any, Write-All

• Read-Any: when reading an item, access any of the replicas.

• Write-All: when writing an item, must update all of the replicas.

• Works well when reads are much more frequent than writes.
• Drawback: writes are very expensive.

Synchronous Replication II: Voting

• When writing, update some fraction of the replicas.
  • each value has a version number that is increased when the value is updated

• When reading, read enough copies to ensure you get at least one copy of the most recent value (see next slide).

• the copies “vote” on the value of the item

• the copy with the highest version number is the most recent

• Drawback: reads are now more expensive

Synchronous Replication II: Voting (cont.)

• How many copies must be read?
  • let: n = the number of copies
        w = the number of copies that are written
        r = the number of copies that are read

• need: r > n – w (i.e., at least n – w + 1)

• example: n = 6 copies
        update w = 3 copies
        must read at least 4 copies

• Example: 6 copies of data item A, each with value = 4, version = 1.

• txn 2 updates A1, A2, and A4 to be 6 (and their version number becomes 2)

• txn 1 reads A2, A3, A5, and A6

• A2 has the highest version number (2), so its value (6) is the most recent.

Which of these allow us to ensure that clients always get the most up-to-date value?

• 10 replicas – i.e., 10 copies of each item
• voting-based approach with the following requirements:

	number of copies accessed when reading	number of copies accessed when writing
A.	7	3
B.	5	5
C.	9	2
D.	4	8

E. both A and B      F. both C and D

Distributed Concurrency Control

• To ensure the isolation of distributed transactions, need some form of distributed concurrency control.

• Extend the concurrency control schemes that we studied earlier.
  • we’ll focus on extending strict 2PL

• If we just used strict 2PL at each site, we would ensure that the schedule of subtxns at each site is serializable.
  • why isn’t this sufficient?

   because the equivalent serial orderings could be different at different sites

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: