by Jake Shannon

"We need decentralization because only thus can we insure that the knowledge of the particular circumstances of time and place will be promptly used. But the ‘man on the spot’ cannot decide solely on the basis of his limited but intimate knowledge of the facts of his immediate surroundings. There still remains the problem of communicating to him such further information as he needs to fit his decisions into the whole pattern of changes of the larger economic system"

Friedrich A. von Hayek

An Introduction to Distributed Database Systems

Today, the Internet could be described as the ultimate distributed database system. Locally controlled and globally accessible, the information of the World Wide Web is a direct descendant of earlier distributed systems (three such ancestors were first built in the late seventies and early eighties, SDD-1 by the Computer Corporation of America, Distributed INGRES by the University of California, and R* at IBM in San Jose, California). A distributed database, as opposed to a centralized database, spreads the storage duties of the database across many smaller databases via telecommunication devices. This paper will survey traditional distributed database management systems while introducing a newer DDBMS called Mariposa.

The Structure of Distributed Databases

Before describing the environment of Mariposa, a survey of the traditional approach to distributed systems is important. The conceptual structure of a DDBMS is simple. The DDBMS consists of multiple computers called sites or nodes and transmit data via a communication network. Sites located geographically close to each other make up a local area network (LAN) whereas those spanning large geographical distances and connect by telecommunications lines are called a wide area network (WAN) or long-haul networks.

A client is a broad term which defines the user, computer, or software application that needs the data, services, or processing of another application or computer called the server. The client-server architecture was developed in an attempt to reduce complexity by dividing the DBMS software between a server and a client. Unfortunately, precisely how to divide the DBMS functionality between the client and the server is not yet clear. However, an emerging standard has begun to evolve.

Usually a DDBMS splits the software in three levels, the client, the server, and the communications software. Anytime a multisite query is submitted, there should be client server software. The client software, sometimes called an application processor or front-end machine, handles most of the distribution functions. The client server software accesses the data distribution information from the DDBMS catalog and processes all multisite access requests. The server software, sometimes called the database processor or back-end machine, behaves similar to a centralized DBMS, handling local data management. The communications software creates the communication basics utilized by the client to distribute commands and data among various sites as required. The communications software sometimes cooperates with a distributed operated system.

Opportunity Costs of Distributing the Database

First, a swift tally of the disadvantages of a centralized database systems versus a distributed database system is in order. Corporations often find that a distributed database management system (DDBMS) allows for more flexibility in organizing and using their data. For example, HCIA, a supplier of clinical data to healthcare providers recently switched from a slow mainframe database with over 30,000 magnetic tapes to a distributed database management system. What used to take weeks to respond to customer queries now takes a fraction of that, slashing the company’s response time to consumer demands by ninety percent.

Such benefits are not without costs however. Distributed DBMS generates many new problems to be addressed, such as maintaining data security. For example, if a local DBMS asks the operating system who the current user is, a DDBMS must somehow authenticate the remote user, who very well may be impersonating an authenticated user. You could try to bypass this by using passwords but passwords can be hacked. Another more expensive security alternative is to use a reputable third party to mediate between both parties (the method used by Kerberos) but coordinating agreement on the ‘trustworthy’ third party may not be the most realistic assumption to make in a multiplatform hardware environment.

Allowing more users access across different sites also creates integrity issues, besides the potential complications associated with using telecommunication lines to transport data. Moreover, current distributed optimizers (an optimizer is that part of the DDBMS that mathematically chooses the best way to use indexes and tables to complete SQL request statements) do not scale to meet the needs of real-world distributed systems. Complexity grows exponentially if the distributed DBMS is trying to integrate heterogeneous databases using a variety of new and legacy database management systems with different CPU speeds and/or different bandwidth requirements.

However on net, the advantages of utilizing a distributed database system outweigh the advantages of using a centralized database system where all data, software, and secondary storage devices exist at a single site. These advantages include increased reliability and availability, improved efficiency, and data sharing congruent with increased local control.

Two of the advantages, reliability and availability, are obvious. Reliability is the probability that a system is working at a particular moment. Availability is the probability that the system is continually accessible during a given time period. Since the data and database management systems are distributed over several sites, the risk that the entire DBMS will be completely down is significantly reduced. However, if one site goes down in a centralized DBMS, the entire system experiences failure. It is similar to using diversified assets in a financial portfolio to reduce your exposure to beta, or market risk.

Most businesses are geographically distributed and there seems there would be a natural affinity with a DDBMS since businesses require the improved efficiency afforded by distributing the database. Because smaller databases exist at each site in a large DDBMS, there are fewer transactions and queries submitted to each smaller local database. This reduces the time necessary for querying and transacting with the database. In a centralized DBMS, one site would have to handle all the queries and transactions submitted. Much like an economy, a DDBMS can benefit from the principle of division of labor too.

A DDBMS also allows controlled sharing of data, which leads us to the topic of transparency and autonomy.

Transparency and Autonomy

For a relational database to manage data at multiple sites in a network, a DBMS maintains the following collection of transparencies:

Location transparency: a query can access distributed objects without necessarily knowing their location.

Performance transparency: a distributed query optimizer can heuristically optimize a plan to execute any distributed command.

Copy transparency: there exists the option for the support of multiple copies of database objects, boosting both the availability and reliability of the system.

Transaction transparency: each transaction can result in updated data at multiple sites while behaving like a local transaction, i.e., the transaction gives the binary "commit" or "abort" result.

Fragment transparency: as long as a relation meets the distribution criteria, it may be dissected and stored at multiple sites.

Schema change transparency: database objects have to be deleted or added to the distributed catalog only once without having to make changes in all catalogs at all sites.

Local DBMS transparency: services must be provided regardless of which local database systems are actually managing local data.

Optional distribution transparency: enables the user to write global queries and transactions as though the database were centralized, without having to specify the sites at which the data referenced in the query or transaction resides.

Autonomy, on the other hand, is the degree to which access to the DDBMS has to be achieved through a client. There is an inverse relationship between client access to the DDBMS and local autonomy. The higher the degree of access a client has, the lower local autonomy and vice versa. The less the local autonomy a DDBMS has the more it appears to users to be a centralized DBMS since all access to the system is gained through the client. In a multidatabase system, or a federated DDBMS, the degree of local autonomy is very high because each server is an independent and autonomous centralized DBMS. The federated system has its own database administrator and its own local users and transactions.

The Design of Distributed Databases

In design engineering, you must break the project down into smaller units. In designing a DDBMS, the logical units of the database are fragments that are assigned for storage at the various nodes in the system. These fragments are the actual relation and can be broken down even further into horizontal and vertical fragments.

Horizontal fragmentation creates a subset of the tuples in that relation, dividing the relation by grouping rows. Vertical fragmentation keeps only certain attributes in the relation, dividing a relation by columns. Integrating the horizontal and vertical fragmentation results in mixed fragmentation. The fragments are then assigned to various nodes in the distributed system. A complete horizontal fragmentation is usually a disjoint. To reform a disjoint relation from a complete horizontal fragmentation a UNION operation must be applied. To reform a relation from a vertical fragmentation a OUTER UNION operation must be applied.

Within the database is a fragmentation schema which delineates a set of fragments which includes all tuples and attributes in the database. It also defines the condition that the entire database can be reformed from fragments by applying either UNION or OUTER UNION operations. Also within the database is an allocation schema which defines where fragments have been allocated to sites in the distributed system. Fragments located at more than one node have been replicated.

Replication of data increases the availability of data but also bogs down update operations since a single logical update must be executed upon every replication to maintain replication consistency. There are differing degrees of replication; full, partial, and no replication (sometimes called nonredundant allocation). Most of these replications are partial with a few outliers being either a full or nonredundant allocation. The replication schema describes the replication of fragments. The fragments and copies of the fragments are stored across different nodes somewhere in a process of storage called data distribution or data allocation.

Distributed Query Processing

A distributed query is one that selects data from databases located at multiple sites in a network and distributed processing performs computations on multiple CPUs to achieve a single result. Any SQL data manipulation statement that references tables at sites other than the site an application program is submitted to for compilation (i.e., the query site) is a called distributed query. DDBMS query optimization algorithms choose a distributed query execution strategy that attempts to reduce the quantity of data transferred. Minimizing the quantity of data transferred is a desirable optimization criterion since more data transported across telecommunications networks requires more time and labor.

There are many strategies available for distributed queries, including the inner table transfer strategy, semijoins, and Bloomjoins. The inner table transfer strategy involves shipping a table whole, transferring the most inner tuples for the least message overhead, but sends extraneous inner tuples that have no matching outer tuples and requires more I/O and CPU for reading the inner at its local site and then storing it in a temporary table at the joining site. However, multiple accesses to the temporary table (particularly in a nested-loop join) make an inner table transfer potentially cost effective in the long run since the temporary table is potentially much smaller than the permanent version.

One of the most efficient minimizing operations, semijoin, is frequently used to shrink the quantity of tuples before transferring it to another node. It does so by sending the joining column of one relation to the site where the other relation is located, where they are both combined. Soon after, the joining attributes and other attributes required in the result are projected and shipped back to the original site and joined with the original relation. The result is that the joining column of the original relation is transferred in one direction while a subset of the foreign relation is transferred in the other, minimizing the quantity of data transported.

The use of hashing techniques have proven themselves efficient ways of discovering matching values. Bloomjoins use Bloom filters to filter out tuples that have no matching tuples in a join and reduce the size of tables to be transported, in a similar fashion like semijoins, but are even better since the size of the inner table is reduced at an earlier stage. Also, semijoins require an extra join for reducing the inner table whereas Bloomjoins only require an addition scan in no particular order.

Distributed query optimizers seem to have evolved into two different types, those that use semijoin and everything else. So, if one is to assume that the cost of communication should be minimized, then a semijoin may be most cost effective. However, when the minimization takes into account the cost of communication and I/O and CPU costs, then hash joins (like Bloomjoins) may make more sense.

Concurrency Control

Concurrency control software properly coordinates updates to the database by multiple users, resulting in a database with correct data. In a distributed system, the complexity of such a task is multiplied. There may be problems with managing multiple copies of the data items and either the individual sites or the communication links may fail. There may also be complications in accessing distributed databases if some nodes fail during a distributed commit process.

Another problem in concurrency control is that a distributed deadlock may occur. A deadlock happens when two or more user processes of a database cannot complete their transactions due to the holding of a resource by each process which the other process needs in order to finish. A DBMS like ORACLE™ detects and resolves such deadlocks (which are very rare) by rolling back the work of one of the processes.

There are a variety of distributed concurrency control methods to deal with replicated data items in a DDBMS. A distinguished copy out of a particular data item is customary. Requests for locking and unlocking this data item are sent to the site that contains the copy. Three variations of the distinguished copy method are the primary site technique, the primary site technique with a back up site, and the primary copy technique.

In the primary site technique a primary site is assigned to be the coordinator site for all database items. It is similar to a centralized locking approach to concurrency control. Since all locking requests are sent to the coordinator site, bottlenecking may occur during high traffic times and if the coordinator site fails, the entire system can be compromised. Setting up a back up site reduces the risk of poor system reliability and availability due to coordinator site paralysis. This way, if the primary site goes down, the back up can take over the coordinator duties and a new back up site is chosen.

Recovery in Distributed Systems

Often times techniques for recovering the state of the system before a failure of the entire computer system is required. A distributed transaction must either be fully committed or aborted. A DDBMS can successfully recover from all single and multiple site failures, and certain cases of network partitions by using a two-phase commit. The two-phase commit ensures that a transaction is valid at all sites by the time it commits or rolls back. The key point is this, if an error occurs within the network or the machines within the network, all sites either commit or rollback together, guaranteed.

The Economic Approach to Distributed Databases

As a dynamic research project at the University of California at Berkeley designed for wide-area network (WAN) environments, the Mariposa distributed database management system is based on an economic paradigm in which processing sites buy and sell resources such as CPU time, I/O capacity and network bandwidth. It utilizes the model of a market economy to achieve optimal performance in equilibrium with the independence of each processing site. Using an economic bidding process to regulate name service, storage management, and query execution Mariposa allows geographically distant and heterogeneous DBMSs to work together to process queries. In general, clients find likely contractors, solicit bids for a given piece of work, and then select the winning bid. In Mariposa, brokers manage the bidding and query execution on behalf of clients, and clients direct brokers using budgets.

The market based DDBMS performs load balancing, thereby outperforming other DDBMS with static distributed query optimizers. Compare its performance to a traditional cost-based distributed query optimizer and the ability of a Mariposa system to adapt to a dynamic workload by using simple economic concepts such as the effect of supply and demand on prices becomes very clear. It outperforms a traditional optimizer by distributing work more evenly among the available sites. For example, a traditional optimizer will produce a query plan, complete with processing sites, whereas Mariposa first produces a query plan, then divides the work to be done among the available processors based on their current resource availability. This query plan is then passed into the query broker, which assigns a processing site to each site in the plan tree. First, the plan is broken up into plan chunks in pieces as small as a single node or as large as the entire query plan.

Mariposa was designed as middleware intended to exist between a single-site DBMS and a front-end application. It has been designed with the following principles in mind:

Scalability to a large number of cooperating sites.

Local autonomy. Each node must have control over its own resources. Including which objects to store and which queries to run. Query and data allocation cannot be done by a centralized, authoritarian query optimizer.

Data mobility. It should be easy and efficient to change the home of an object.

No global synchronization. Updates and schema changes should not force a site to synchronize with all other sites.

Easily configurable policies. It should be easy for a local database administrator to change the behavior of a Mariposa site. A Mariposa system should respond gracefully to changes in user activity and data access patterns to maintain low response time and high system throughput.

Summary

In summary, distributed database systems offer many desirable options and the new Agoric DDBMS, Mariposa, even more. The advantages of the Agoric system, or market modeled system, over the traditional DDBMS are best illustrated with the table in figure 1 below.