Distributed Databases and MapReduce

Question 1

Data Partitioning

Answer 1

• Data is partitioned or fragmented across multiple machines

Question 2

Data Replication

Answer 2

• Copies of the same data are made available on multiple machines

Question 3

Horizontal Fragmentation

Answer 3

• Divides up the rows of a collection of records

Question 4

Vertical Fragmentation

Answer 4

• Divides up the columns of a collection of records

Question 5

Advantages of a Distributed Database

Answer 5

• Improves performance
• High availability
• Modular growth
• Integrates data from multiple existing systems

Question 6

Challenges of a Distributed Database

Answer 6

• Distributing the data
• Efficient query execution
• Maintaining integrity constraints (PK, FK, etc)
• Replicated data remains consistent
• Managing distributed transactions

Question 7

Distributed Transaction

Answer 7

• A transaction that involves data stored at multiple sites
• One site serves as the coordinator

Question 8

Synchronous Replication

Answer 8

• Transactions are guaranteed to see the most up-to-date value of an item

Question 9

Asynchronous Replication

Answer 9

• Transactions are not guaranteed to see the most up-to-date value of an item

Question 10

Primary-Site Replication

Answer 10

• One replica is designated the primary replica
• Receives all writes and updates the secondary replicas

Question 11

Peer-to-Peer Replication

Answer 11

• More than one replica can be updated

Question 12

Synchronous Replication: Read-Any, Write-All

Answer 12

• When reading an item, access any of the replicas
• When writing an item, must update all of the replicas

Question 13

Synchronous Replication: Voting

Answer 13

• n = number of copies, w = copies written, r = copies read
• Need r > n - w

Question 14

Global Locks

Answer 14

• Shared and exclusive locks for a logical item
• No two transactions can hold a global exclusive lock for the same item
• Any number of transactions can hold a global shared lock for an item

Question 15

Centralized Locking

Answer 15

• One site manages the lock requests for all items in the distributed database
• The lock site can become a bottleneck

Question 16

Primary-Copy Locking

Answer 16

• One copy of an item is designated the primary copy
• The site holding the primary copy handles all lock requests for that item

Question 17

Fully Distributed Locking

Answer 17

• A transaction acquires a global lock for an item by locking a sufficient number of the item’s copies
• n = total copies, x = number locked for global exclusive lock, s = number locked for global shared lock
• Need x > n / 2
• Need s > n - x

Question 18

Distributed Deadlock Handling

Answer 18

• Difficult to detect deadlock, so roll back a transaction if it waits too long (timeout)

Question 19

MapReduce

Answer 19

• Splits the collection of records into subcollections that are processed in parallel

Question 20

Benefits of MapReduce

Answer 20

• Parallel processing
• Fewer data transfer across machines
• Fault tolerance

Question 21

Mapper

Answer 21

• Applies a map function to each record to create (key, value) pairs

Question 22

Reducer

Answer 22

• Applies a reduce function to each (key, value list)

Question 23

Chaining MapReduce Jobs

Answer 23

• Map the reduced results of the first job to an arbitrary constant key to create one reducer task