Distributed Databases

19.3 Question: How might is distributed database designed for a local area network                                                                                                                                      differ from one designed for a wide area network?

19.3 Answer: Data transfer on a local-area network (LAN) is much faster than on a wide-area network (WAN). Thus replication and fragmentation will not increase throughput and speed-up on a LAN, as much as in a WAN. But even in a LAN, replication has its uses in increasing reliability and availability.

19.6 Question: To build a highly available distributed system, you must know what kinds of failures can occur

a)      List possible type of failure in a distributed system.

b)     Which items in your list are also applicable to centralized system?

19.6 Answer:

a)      The types of failure that can occur in a distributed system include

                               I.      Computer failure (site failure).

                            II.      Disk failure.

                         III.      Communication failure.

b)      The first two failure types can also occur on centralized systems.

19.7 Question: Consider a failure that occurs during 2PC for a transaction. For each possible failure that you listed in exercise 19.6a, explain how 2PC ensures transaction atomicity despite the failure.

19.7 Answer: A proof that 2PC guarantees atomic commits/aborts in spite of site and link failures, follows. The main idea is that after all sites reply with a <ready T> message; only the coordinator of a transaction can make a commit or abort decision. Any subsequent commit or abort by a site can happen only after it ascertains the coordinator’s decision, either directly from the coordinator, or indirectly from some other site. Let us enumerate the cases for a site aborting, and then for a site committing.

a)      A site can abort a transaction T (by writing an <abort T> log record) only under the following circumstances:-

                               I.      It has not yet written a <ready T> log-record. In this case, the coordinator could not have got, and will not get a<ready T> or<commit T> message from this site. Therefore only the coordinator can make an abort decision.

                            II.      It has written the <ready T> log record, but on inquiry it found out that some other site has an <abort T> log record. In this case it is correct for it to abort, because that other site would have ascertained the coordinator’s decision (either directly or indirectly) before actually aborting.

                         III.      It is itself the coordinator. In this case also no site could have committed, or will commit in the future, because commit decisions can be made only by the coordinator.

b)      A site can commit a transaction T (by writing an <commit T> log record) only under the following circumstances: -

                                           I.      It has written the <ready T> log record, and on inquiry it found out that some other site has a <commit T> log record. In this case it is correct for it to commit, because that other site would have ascertained the coordinator’s decision (either directly or indirectly) before actually committing.

                                        II.      It is itself the coordinator. In this case no other participating site can abort / would have aborted, because only the coordinator makes abort decisions.

19.8 Question: Consider a distributed with two sites, A & B. Can site distinguish among the following?

1.      B goes down.

2.      The link between A and B goes down

3.      B is extremely overloaded and response time is 100 times longer than normal.

What implications does your answer have for recovery in distributed system?

19.8 Answer: Site A cannot distinguish between the three cases until communication has resumed with site B. The action which it performs while B is inaccessible must be correct irrespective of which of these situations has actually occurred, and must be such that B can re-integrate consistently into the distributed system once communication is restored.

19.9 Question: The persistent messaging scheme described in this chapter depends on timestamps combined with discarding of received messages if they are too old suggest an alternative scheme based on sequence numbers instead of timestamps.

19.9 Answer: We can have a scheme based on sequence numbers similar to the scheme based on timestamps. We tag each message with a sequence number that is unique for the (sending site, receiving site) pair. The number is increased by 1 for each new message sent from the sending site to the receiving site.

The receiving site stores and acknowledges a received message only if it has received all lower numbered messages also; the message is stored in the received-messages relation.

The sending site retransmits a message until it has received an acknowledgement from the receiving site containing the sequence number of the transmitted message, or a higher sequence number. Once the acknowledgment is received, it can delete the message from its send queue.

The receiving site discards all messages it receives that have a lower sequence number than the latest stored message from the sending site. The receiving site discards from received-messages all but the (number of the) most recent message from each sending site (message can be discarded only after being processed locally).

Note that this scheme requires a fixed (and small) overhead at the receiving site for each sending site, regardless of the number of messages received. In contrast the timestamp scheme requires extra space for every message. The timestamp scheme would have lower storage overhead if the number of messages received within the timeout interval is small compared to the number of sites, whereas the sequence number scheme would have lower overhead otherwise.

19.10 Question: Give an example where the read one, write all available approach leads to an erroneous state.

19.10 Answer: Consider the balance in an account, replicated at N sites. Let the current balance be $100 – consistent across all sites. Consider two transactions T₁ and T₂ each depositing $10 in the account. Thus the balance would be $120 after both these transaction are executed. Let the transactions execute in sequence: T₁ first and then T₂. Let one of the sites, say s, be down when T₁ is executed and transaction T₂ reads the balance from site s. One can see that the balance at the primary site would be $110 at the end.

19.12 Question: Explain the difference between data replication in a distributed system and the maintenance of a remote backup site.

19.12 Answer: In remote backup systems all transactions are performed at the primary site and the data is replicated at the remote backup site. The remote backup site is kept synchronized with the updates at the primary site by sending all log records. Whenever the primary site fails, the remote backup site takes over processing. The distributed systems offer greater availability by having multiple copies of the data at different sites whereas the remote backup systems offer lesser availability at lower cost and execution overhead. In a distributed system, transaction code runs at all the sites whereas in a remote backup system it runs only at the primary site. The distributed system transactions follow two-phase commit to have the data in consistent state whereas a remote backup system does not follow two-phase commit and avoids related overhead.

19.13 Question: Give an example where lazy replication can lead to an inconsistent database state even when updates get an exclusive lock on the primary copy.

19.13 Answer: Consider the balance in an account, replicated at N sites. Let the current balance be $100 – consistent across all sites. Consider two transactions T₁ and T₂ each depositing $10 in the account. Thus the balance would be $120 after both these transaction are executed. Let the transactions execute in sequence: T₁ first and then T₂. Suppose the copy of the balance at one of the sites, say s, is not consistent – due to lazy replication strategy – with the primary copy after transaction T₁ is executed and let transaction T₂ read this copy of the balance. One can see that the balance at the primary site would be $110 at the end.

19.16 Question: consider the following deadlock-detection algorithm. When transaction T_i, at site S_1, requests a resource from T_j, at site S₃, a request message with timestamp n is sent. The edge (T_i, T_j, n) is inserted in the local wait-for of S_1. The edge (T_i, Tj, n) is inserted in the local wait-for graph of S₃ only if T_j has received the request message and cannot immediately grant the requested resource. A request form T_i to T_j in the same site is handled in the usual manner; no timestamps are associated with the edge (T_i, T_j). A central coordinator invokes the detection algorithm by sending an initiating message to each site in system.

            On receiving this message, a site sends its local wait-for graph the coordinator. Note that such a graph contains all local information that the site has about the state of the real graph. The wait-for graph reflects instantaneous state of the site, but it is not synchronized with respect to any other site.

            When the controller has received a reply from each site, it constructs graph as follows:

·         The graph contains a vertex for every transaction in the system.

·         The graph has an edge (T_i, T_j) if and only if

o   There is an edge (T_i, T_j) in one of the wait-for graphs.

o   An edge (T_i, T_j, n) (for some n) appears in more than one wait-for graph.

Show that, if there is cycle in the constructed graph, then the system is in a deadlock state, and that, if there is no cycle in the constructed graph, then the system was not in a deadlock state when the execution of the algorithm began.

19.16 Answer: Let us say a cycle T_i → T_j → …→ T_m → T_i exists in the graph built by the controller. The edges in the graph will either be local edges of the form (T_k, T_l) or distributed edges of the form (T_k, T_l, n). Each local edge (T_k, T_l) definitely implies that T_k is waiting for T_l. Since a distributed edge (T_k, T_l, n) is inserted into the graph only if T_k’s request has reached T_l and T_l cannot immediately release the lock, T_k is indeed waiting for T_l. Therefore every edge in the cycle indeed represents a transaction waiting for another. For a detailed proof that this implies a deadlock refer to Stuart et al. [1984]. We now prove the converse implication. As soon as it is discovered that T_k is waiting for T_l: -

a)      A local edge (T_k, T_l) is added if both are on the same site.

b)      The edge (T_k, T_l, n) is added in both the sites, if T_k and T_l are on different sites.

Therefore, if the algorithm were able to collect all the local wait-for graphs at the same instant, it would definitely discover a cycle in the constructed graph, in case there is a circular wait at that instant. If there is a circular wait at the instant when the algorithm began execution, none of the edges participating in that cycle can disappear until the algorithm finishes. Therefore, even though the algorithm cannot collect all the local graphs at the same instant, any cycle that existed just before it started will anyway detected.

19.17 Question: Consider a relation that is fragmented horizontally by plant-number:

            Employee (name, address, salary, plant-number)

Assume that each fragment has two replicas: one stored at the New York site and one stored at the plant site. Describe a good processing strategy for the following queries entered at the San Jose site.

a)      Find all employees at the Boca plant.

b)     Find the average salary of all employees.

c)      Find the highest paid employee at each of the following sites: Toronto, Edmonton, Vancouver, and Montreal.

d)     Find the lowest paid employee in the company.

19.17 Answer:

a)       

                               I.      Send the query P _name (employee) to the Boca plant.

                            II.      Have the Boca location send back the answer.

b)       

                               I.      Compute average at New York.

                            II.      Send answer to San Jose.

c)       

                               I.      Send the query to find the highest salaried employee to Toronto, Edmonton, Vancouver, and Montreal.

                            II.      Compute the queries at those sites.

                         III.      Return answers to San Jose.

d)      

                               I.      Send the query to find the lowest salaried employee to New York.

                            II.      Compute the query at New York.

                         III.      Send answer to San Jose.

19.20 Question: Compute semi join of r & s for the relations of figure 19.7.

19.20 Answer: The result is as follows.

r semi join s = A          B         C

  1        2          3

  5        3          2

19.22 Question: Given that LDAP functionality can be implemented on top of the database system, what is need for LDAP standard?

19.22 Answer: The reasons are:

a)      Directory access protocols are simplified protocols that cater to a limited type of access to data.

b)      Directory systems provide a simple mechanism to name objects in a hierarchical fashion, which can be used in a distributed directory system to specify what information is stored in each of the directory servers. The directory system can be set up to automatically forward queries made at one site to the other site, without user intervention.