16 Distributed Database Architecture

Dr R. Baskaran

Horizontal partitioning

 

Horizontal partitioning divides a table into multiple tables. Each table then contains the same number of columns, but fewer rows. For example, a table that contains 1 billion rows could be partitioned horizontally into 12 tables, with each smaller table representing one month of data for a specific year. Any queries requiring data for a specific month only reference the appropriate table.

 

Determining how to partition the tables horizontally depends on how data is analyzed. You should partition the tables so that queries reference as few tables as possible. Otherwise, excessive UNION queries, used to merge the tables logically at query time, can affect performance. For more information about querying horizontally partitioned tables.

 

Partitioning data horizontally based on age and use is common. For example, a table may contain data for the last five years, but only data from the current year is regularly accessed. In this case, you may consider partitioning the data into five tables, with each table containing data from only one year.

 

Vertical partitioning

 

Vertical partitioning divides a table into multiple tables that contain fewer columns. The two types of vertical partitioning are normalization and row splitting:Normalization is the standard database process of removing redundant columns from a table and putting them in secondary tables that are linked to the primary table by primary key and foreign key relationships.

 

Row splitting divides the original table vertically into tables with fewer columns. Each logical row in a split table matches the same logical row in the other tables as identified by a UNIQUE KEY column that is identical in all of the partitioned tables. For example, joining the row with ID 712 from each split table re-creates the original row.

 

Like horizontal partitioning, vertical partitioning lets queries scan less data. This increases query performance. For example, a table that contains seven columns of which only the first four are generally referenced may benefit from splitting the last three columns into a separate table.

 

Vertical partitioning should be considered carefully, because analyzing data from multiple partitions requires queries that join the tables. Vertical partitioning also could affect performance if partitions are very large.

 

Homogeneous Distributed Databases

 

In a homogeneous distributed database, all the sites use identical DBMS and operating systems. Its properties are −

  • The sites use very similar software.
  • The sites use identical DBMS or DBMS from the same vendor.
  • Each site is aware of all other sites and cooperates with other sites to process user requests.
  • The database is accessed through a single interface as if it is a single database.

    Types of Homogeneous Distributed Database

 

There are two types of homogeneous distributed database −

 

Autonomous − Each database is independent that functions on its own. They are integrated by a controlling application and use message passing to share data updates.

 

Non-autonomous − Data is distributed across the homogeneous nodes and a central or master DBMS co-ordinates data updates across the sites.

 

Heterogeneous Distributed Databases

 

In a heterogeneous distributed database, different sites have different operating systems, DBMS products and data models. Its properties are −

  • Different sites use dissimilar schemas and software.
  • The system may be composed of a variety of DBMSs like relational, network, hierarchical or object oriented.
  • Query processing is complex due to dissimilar schemas.
  • Transaction processing is complex due to dissimilar software.
  • A site may not be aware of other sites and so there is limited co-operation in processing user requests.

   Types of Heterogeneous Distributed Databases

 

 Federated − The heterogeneous database systems are independent in nature and integrated together so that they function as a single database system.

 

 Un-federated − The database systems employ a central coordinating module through which the databases are accessed.

 

Distributed DBMS Architectures

DDBMS architectures are generally developed depending on three parameters −

 

Distribution − It states the physical distribution of data across the different sites.

 

Autonomy − It indicates the distribution of control of the database system and the degree to which each constituent DBMS can operate independently.

 

Heterogeneity − It refers to the uniformity or dissimilarity of the data models, system components and databases.

 

Architectural Models

 

Some of the common architectural models are − Client – Server Architecture for DDBMS Peer – to – Peer Architecture for DDBMS Multi – DBMS Architecture.

 

Client – Server Architecture for DDBMS

 

This is a two-level architecture where the functionality is divided into servers and clients. The server functions primarily encompass data management, query processing, optimization and transaction management. Client functions include mainly user interface. However, they have some functions like consistency checking and transaction management.

 

Peer- to-Peer Architecture for DDBMS

In these systems, each peer acts both as a client and a server for imparting database services. The peers share their resource with other peers and co -ordinate their activities. This architecture generally has four levels of schemas −

 

Global Conceptual Schema − Depicts the global logical view of data.

Local Conceptual Schema − Depicts logical data organization at each site.

Local Internal Schema − Depicts physical data organization at each site.

External Schema − Depicts user view of data.

 

Multi – DBMS Architectures

 

This is an integrated database system formed by a collection of two or more autonomous database systems.

Multi-DBMS can be expressed through six levels of schemas −

 

Multi-database View Level − Depicts multiple user views comprising of subsets of the integrated distributed database.

 

Multi-database Conceptual Level − Depicts integrated multi-database that comprises of global logical multi-database structure definitions.

 

Multi-database Internal Level − Depicts the data distribution across different sites and multi-database to local data mapping.

 

Local database View Level − Depicts public view of local data.

 

Local database Conceptual Level − Depicts local data organization at each site.

 

Local database Internal Level − Depicts physical data organization at each site.

 

There are two design alternatives for multi-DBMS −

Model with multi-database conceptual level.

Model without multi-database conceptual level.

 

Design Alternatives

 

The distribution design alternatives for the tables in a DDBMS are as follows − Non-replicated and non-  fragmented

Fully replicated

Partially replicated

Fragmented

Mixed

 

Non-replicated & Non-fragmented

 

In this design alternative, different tables are placed at different sites. Data is placed so that it is at a close proximity to the site where it is used most. It is most suitable for database systems where the percentage of queries needed to join information in tables placed at different sites is low. If an appropriate distribution strategy is adopted, then this design alternative helps to reduce the communication cost during data processing.

 

Fully Replicated

 

In this design alternative, at each site, one copy of all the database tables is stored. Since, each site has its own copy of the entire database, queries are very fast requiring negligible communication cost. On the contrary, the massive redundancy in data requires huge cost during update operations. Hence, this is suitable for systems where a large number of queries is required to be handled whereas the number of database updates is low.

 

 Partially Replicated

 

Copies of tables or portions of tables are stored at different sites. The distribution of the tables is done in accordance to the frequency of access. This takes into consideration the fact that the frequency of accessing the tables vary considerably from site to site. The number of copies of the tables (or portions) depends on how frequently the access queries execute and the site which generate the access queries.

 

Fragmented

 

In this design, a table is divided into two or more pieces referred to as fragments or partitions, and each fragment can be stored at different sites. This considers the fact that it seldom happens that all data stored in a table is required at a given site. Moreover, fragmentation increases parallelism and provides better disaster recovery. Here, there is only one copy of each fragment in the system, i.e. no redundant data.

 

The three fragmentation techniques are −

Vertical fragmentation

Horizontal fragmentation

Hybrid fragmentation

 

Mixed Distribution

 

This is a combination of fragmentation and partial replications. Here, the tables are initially fragmented in any form (horizontal or vertical), and then these fragments are partially replicated across the different sites according to the frequency of accessing the fragments.

 

Data Replication

 

Data replication is the process of storing separate copies of the database at two or more sites. It is a popular fault tolerance technique of distributed databases.

 

Advantages of Data Replication

 

Reliability − In case of failure of any site, the database system continues to work since a copy is available at another site(s).

Reduction in Network Load − Since local copies of data are available, query processing can be done with reduced network usage, particularly during prime hours. Data updating can be done at non-prime hours.

Quicker Response − Availability of local copies of data ensures quick query processing and consequently quick response time.

Simpler Transactions − Transactions require less number of joins of tables located at different sites and minimal coordination across the network. Thus, they become simpler in nature.

 

Disadvantages of Data Replication

 

Increased Storage Requirements − Maintaining multiple copies of data is associated with increased storage costs. The storage space required is in multiples of the storage required for a centralized system.

 

Increased Cost and Complexity of Data Updating − Each time a data item is updated, the update needs to be reflected in all the copies of the data at the different sites. This requires complex synchronization techniques and protocols.

 

Undesirable Application – Database coupling − If complex update mechanisms are not used, removing data inconsistency requires complex co-ordination at application level. This results in undesirable application – database coupling.

 

Some commonly used replication techniques are − Snapshot replication

Near-real-time replication

Pull replication

 

Fragmentation

 

Fragmentation is the task of dividing a table into a set of smaller tables. The subsets of the table are called fragments. Fragmentation can be of three types: horizontal, vertical, and hybrid (combination of horizontal and vertical). Horizontal fragmentation can further be classified into two techniques: primary horizontal fragmentation and derived horizontal fragmentation.

 

Fragmentation should be done in a way so that the original table can be reconstructed from the fragments. This is needed so that the original table can be reconstructed from the fragments whenever required. This requirement is called “reconstructiveness.”

 

Advantages of Fragmentation

 

Since data is stored close to the site of usage, efficiency of the database system is increased.Local query optimization techniques are sufficient for most queries since data is locally available.Since irrelevant data is not available at the sites, security and privacy of the database system can be maintained.

 

Disadvantages of Fragmentation

 

When data from different fragments are required, the access speeds may be very high. In case of recursive fragmentations, the job of reconstruction will need expensive techniques.Lack of back-up copies of data in different sites may render the database ineffective in case of failure of a site.

 

Vertical Fragmentation

 

In vertical fragmentation, the fields or columns of a table are grouped into fragments. In order to maintain reconstructiveness, each fragment should contain the primary key field(s) of the table. Vertical fragmentation can be used to enforce privacy of data.

 

Horizontal Fragmentation

 

Horizontal fragmentation groups the tuples of a table in accordance to values of one or more fields. Horizontal fragmentation should also confirm to the rule of reconstructiveness. Each horizontal fragment must have all columns of the original base table.

   

Hybrid Fragmentation

 

In hybrid fragmentation, a combination of horizontal and vertical fragmentation techniques are used. This is the most flexible fragmentation technique since it generates fragments with minimal extraneous information. However, reconstruction of the original table is often an expensive task.

 

Hybrid fragmentation can be done in two alternative ways − At first, generate a set of horizontal fragments; then generate vertical fragments from one or more of the horizontal fragments.

 

At first, generate a set of vertical fragments; then generate horizontal fragments from one or more of the vertical fragments.

 

Distributed One-phase Commit

 

Distributed one-phase commit is the simplest commit protocol. Let us consider that there is a controlling site and a number of slave sites where the transaction is being executed. The steps in distributed commit are −

 

After each slave has locally completed its transaction, it sends a “DONE” message to the controlling site.The slaves wait for “Commit” or “Abort” message from the controlling site. This waiting time is called window of vulnerability.

 

When the controlling site receives “DONE” message from each slave, it makes a decision to commit or abort. This is called the commit point. Then, it sends this message to all the slaves.On receiving this message, a slave either commits or aborts and then sends an acknowledgement message to the controlling site.

 

Distributed Two-phase Commit

 

Distributed two-phase commit reduces the vulnerability of one-phase commit protocols. The steps performed in the two phases are as follows −

 

Phase 1: Prepare Phase

 

After each slave has locally completed its transaction, it sends a “DONE” message to the controlling site. When the controlling site has received “DONE” message from all slaves, it sends a “Prepare” message to the slaves.The slaves vote on whether they still want to commit or not. If a slave wants to commit, it sends a “Ready” message.A slave that does not want to commit sends a “Not Ready” message. This may happen when the slave has conflicting concurrent transactions or there is a timeout.

 

Phase 2: Commit/Abort Phase

 

After the controlling site has received “Ready” message from all the slaves − The controlling site sends a “Global Commit” message to the slaves.The slaves apply the transaction and send a “Commit ACK” message to the controlling site.When the controlling site receives “Commit ACK” message from all the slaves, it considers the transaction as committed.After the controlling site has received the first “Not Ready” message from any slave − The controlling site sends a “Global Abort” message to the slaves.The slaves abort the transaction and send a “Abort ACK” message to the controlling site. When the controlling site receives “Abort ACK” message from all the slaves, it considers the transaction as aborted.

 

Distributed Three-phase Commit

 

The steps in distributed three-phase commit are as follows −

 

Phase 1: Prepare Phase

 

The steps are same as in distributed two-phase commit.

 

Phase 2: Prepare to Commit Phase

 

The controlling site issues an “Enter Prepared State” broadcast message.

The slave sites vote “OK” in response.

 

Phase 3: Commit / Abort Phase

 

The steps are same as two-phase commit except that “Commit ACK”/”Abort ACK” message is not required.There are three classical approaches for deadlock handling, namely − Deadlock prevention.Deadlock avoidance.Deadlock detection and removal.All of the three approaches can be incorporated in both a centralized and a distributed database system.

 

Deadlock Prevention

 

The deadlock prevention approach does not allow any transaction to acquire locks that will lead to deadlocks. The convention is that when more than one transactions request for locking the same data item, only one of them is granted the lock.One of the most popular deadlock prevention methods is pre-acquisition of all the locks. In this method, a transaction acquires all the locks before starting to execute and retains the locks for the entire duration of transaction. If another transaction needs any of the already acquired locks, it has to wait until all the locks it needs are available. Using this approach, the system is prevented from being deadlocked since none of the waiting transactions are holding any lock.

 

Deadlock Avoidance

 

The deadlock avoidance approach handles deadlocks before they occur. It analyzes the transactions and the locks to determine whether or not waiting leads to a deadlock. The method can be briefly stated as follows. Transactions start executing and request data items that they need to lock. The lock manager checks whether the lock is available. If it is available, the lock manager allocates the data item and the transaction acquires the lock. However, if the item is locked by some other transaction in incompatible mode, the lock manager runs an algorithm to test whether keeping the transaction in waiting state will cause a deadlock or not. Accordingly, the algorithm decides whether the transaction can wait or one of the transactions should be aborted.

 

There are two algorithms for this purpose, namely wait-die and wound-wait. Let us assume that there are two transactions, T1 and T2, where T1 tries to lock a data item which is already locked by T2. The algorithms are as follows −

   

Wait-Die − If T1 is older than T2, T1 is allowed to wait. Otherwise, if T1 is younger than T2, T1 is aborted and later restarted.

 

Wound-Wait − If T1 is older than T2, T2 is aborted and later restarted. Otherwise, if T1 is younger than T2, T1 is allowed to wait.

 

Deadlock Detection and Removal

 

The deadlock detection and removal approach runs a deadlock detection algorithm periodically and removes deadlock in case there is one. It does not check for deadlock when a transaction places a request for a lock. When a transaction requests a lock, the lock manager checks whether it is available. If it is available, the transaction is allowed to lock the data item; otherwise the transaction is allowed to wait.

 

Since there are no precautions while granting lock requests, some of the transactions may be deadlocked. To detect deadlocks, the lock manager periodically checks if the wait-forgraph has cycles. If the system is deadlocked, the lock manager chooses a victim transaction from each cycle. The victim is aborted and rolled back; and then restarted later. Some of the methods used for victim selection are −

  • Choose the youngest transaction.
  • Choose the transaction with fewest data items.
  • Choose the transaction that has performed least number of updates.
  • Choose the transaction having least restart overhead.
  • Choose the transaction which is common to two or more cycles.

This approach is primarily suited for systems having transactions low and where fast response to lock requests is needed.

 

Deadlock Handling in Distributed Systems

 

Transaction processing in a distributed database system is also distributed, i.e. the same transaction may be processing at more than one site. The two main deadlock handling concerns in a distributed database system that are not present in a centralized system are transaction location and transaction control. Once these concerns are addressed, deadlocks are handled through any of deadlock prevention, deadlock avoidance or deadlock detection and removal.

 

Transaction Location

 

Transactions in a distributed database system are processed in multiple sites and use data items in multiple sites. The amount of data processing is not uniformly distributed among these sites. The time period of processing also varies. Thus the same transaction may be active at some sites and inactive at others. When two conflicting transactions are located in a site, it may happen that one of them is in inactive state. This condition does not arise in a centralized system. This concern is called transaction location issue.

 

This concern may be addressed by Daisy Chain model. In this model, a transaction carries certain details when it moves from one site to another. Some of the details are the list of tables required, the list of sites required, the list of visited tables and sites, the list of tables and sites that are yet to be visited and the list of acquired locks with types. After a transaction terminates by either commit or abort, the information should be sent to all the concerned sites.

   

Transaction Control

 

Transaction control is concerned with designating and controlling the sites required for processing a transaction in a distributed database system. There are many options regarding the choice of where to process the transaction and how to designate the center of control, like −

  • One server may be selected as the center of control.
  • The center of control may travel from one server to another.
  • The responsibility of controlling may be shared by a number of servers.

 

Distributed Deadlock Prevention

 

Just like in centralized deadlock prevention, in distributed deadlock prevention approach, a transaction should acquire all the locks before starting to execute. This prevents deadlocks.The site where the transaction enters is designated as the controlling site. The controlling site sends messages to the sites where the data items are located to lock the items. Then it waits for confirmation. When all the sites have confirmed that they have locked the data items, transaction starts. If any site or communication link fails, the transaction has to wait until they have been repaired.Though the implementation is simple, this approach has some drawbacks − Pre-acquisition of locks requires a long time for communication delays. This increases the time required for transaction.

 

In case of site or link failure, a transaction has to wait for a long time so that the sites recover. Meanwhile, in the running sites, the items are locked. This may prevent other transactions from executing.

 

If the controlling site fails, it cannot communicate with the other sites. These sites continue to keep the locked data items in their locked state, thus resulting in blocking.

 

Distributed Deadlock Avoidance

 

As in centralized system, distributed deadlock avoidance handles deadlock prior to occurrence. Additionally, in distributed systems, transaction location and transaction control issues needs to be addressed. Due to the distributed nature of the transaction, the following conflicts may occur −

  • Conflict between two transactions in the same site.
  • Conflict between two transactions in different sites.

 

In case of conflict, one of the transactions may be aborted or allowed to wait as per distributed wait-die or distributed wound-wait algorithms.

 

Let us assume that there are two transactions, T1 and T2. T1 arrives at Site P and tries to lock a data item which is already locked by T2 at that site. Hence, there is a conflict at Site P. The algorithms are as follows −

 

Distributed Wound-DieIf T1 is older than T2, T1 is allowed to wait. T1 can resume execution after Site P receives a message that T2 has either committed or aborted successfully at all sites. If T1 is younger than T2, T1 is aborted. The concurrency control at Site P sends a message to all sites where T1 has visited to abort T1. The controlling site notifies the user when T1 has been successfully aborted in all the sites.

     Distributed Wait-Wait

 

If T1 is older than T2, T2 needs to be aborted. If T2 is active at Site P, Site P aborts and rolls back T2 and then broadcasts this message to other relevant sites. If T2 has left Site P but is active at Site Q, Site P broadcasts that T2 has been aborted; Site L then aborts and rolls back T2 and sends this message to all sites.If T1 is younger than T1, T1 is allowed to wait. T1 can resume execution after Site P receives a message that T2 has completed processing.

 

Distributed Deadlock Detection

 

Just like centralized deadlock detection approach, deadlocks are allowed to occur and are removed if detected. The system does not perform any checks when a transaction places a lock request. For implementation, global wait-for-graphs are created. Existence of a cycle in the global wait-for-graph indicates deadlocks. However, it is difficult to spot deadlocks since transaction waits for resources across the network.

 

Alternatively, deadlock detection algorithms can use timers. Each transaction is associated with a timer which is set to a time period in which a transaction is expected to finish. If a transaction does not finish within this time period, the timer goes off, indicating a possible deadlock.

 

Another tool used for deadlock handling is a deadlock detector. In a centralized system, there is one deadlock detector. In a distributed system, there can be more than one deadlock detectors. A deadlock detector can find deadlocks for the sites under its control. There are three alternatives for deadlock detection in a distributed system, namely.

 

Centralized Deadlock Detector − One site is designated as the central deadlock detector.

Hierarchical Deadlock Detector − A number of deadlock detectors are arranged in hierarchy.

Distributed Deadlock Detector − All the sites participate in detecting deadlocks and removing them.