Lecture
Distributed databases (RBD) - a set of logically interrelated databases distributed in a computer network.
RDB consists of a set of nodes connected by a communication network, in which:
Each node is itself a database system. Any user can perform operations on the data on his local node in the same way as if this node were not at all part of a distributed system. A distributed database system can be viewed as a partnership between individual local DBMSs on separate local nodes.
The fundamental principle of creating distributed databases ("rule 0"): For a user, a distributed system should look just like an unallocated system.
The fundamental principle has the effect of certain additional rules or objectives. There are twelve such goals:
M. Tamer Ozzu, Patrick Valduriz
Source: Journal of Database Management Systems # 4/1996, Open Systems Publishing House
New edition: Sergey Kuznetsov, 2009
Original: M. Tamer Ozsu, Patrick Valduriez. Distributed and parallel database systems.
Introduction Basic Concepts Distributed and Parallel Database Technologies
Architectural challenges Request processing and optimization Simultaneous access control Reliability protocols Replication protocols
Research issues
Data Placement Network Scalability Issues Distributed and Parallel Request Processing Distributed Transaction Processing
Conclusion Term Definitions Literature
The formation of database management systems (DBMS) coincided in time with significant success in the development of technologies for distributed computing and parallel processing. As a result, distributed database management systems and parallel database management systems have emerged. These systems are becoming the dominant tools for creating data-intensive applications.
By integrating workstations into a distributed environment, it becomes possible to more efficiently distribute functions in it when application programs run on workstations, called application servers, and databases are served by dedicated computers, called database servers . This serves as a source for the development of such distributed architectures where the nodes are not just general-purpose computers, but specialized servers.
A parallel computer, or multiprocessor itself is a distributed system made up of nodes (processors, memory components) connected by a fast network inside a common case. The technology of distributed databases can be naturally revised and extended to parallel database systems , that is, database systems on parallel computers [DeWitt and Gray, 1992, Valduriez, 1993]. Thanks to the parallelism used in systems of this type in data management [Boral, 1988], users get high performance and high availability database servers for a significantly lower price than equivalent mainframe-based systems [DeWitt and Gray, 1992, Valduriez, 1993].
The article presents an overview of technologies of distributed and parallel DBMS, highlighted their distinctive features, marked by similar features. The purpose of the review is to help in understanding the unique role of the systems of each of these two types and their complementarity in solving data management problems.
A distributed database (DDB - distributed database) is a collection of logically interconnected databases distributed in a computer network. A distributed database management system is defined as a software system that allows you to manage a distributed database in such a way that its distribution is transparent to users [Ozsu and Valduriez, 1991a]. This definition should clarify two distinctive architectural features. The first of these is that the system consists of a (possibly empty) set of query receiving nodes (query site) and a nonempty set of data nodes (data site). Data nodes have the means to store data, but request receiving nodes do not. At the request receiving nodes, only programs that implement the user interface for accessing the data stored in the data nodes are executed. The second feature is that the nodes are logically independent computers. Consequently, such a node has its own main and external memory, it has its own operating system (maybe the same on all nodes, and perhaps not) and it is possible to run applications. Nodes are connected by a computer network, and are not included in the multiprocessor configuration. It is important to emphasize the weak connectivity of processors that have their own operating systems and operate independently.
The database is physically distributed across data nodes based on data fragmentation and replication [Ceri et al., 1987]. With a relational database schema, each relation is fragmented into horizontal or vertical sections. Horizontal fragmentation is implemented using a selection operation that directs each tuple of a relationship into one of the sections, guided by the fragmentation predicate. For example, for an Employee relationship, fragmentation is possible according to the location of the employee jobs. With vertical fragmentation, the relationship is divided into sections using the projection operation. For example, one section of the Employee relationship may contain the fields Emp_number , Emp_name and Address , and the other Emp_number fields Emp_number , Salary and Manager . Due to fragmentation, the data approaches the place of their most intensive use, which potentially reduces shipping costs; the size of the relations involved in user queries is also reduced.
Data fragments can also be replicated based on the nature of access to them. This is useful if the same data is accessed from applications running on different nodes. In this case, in terms of cost savings, it is more efficient to duplicate data in a number of nodes than to continuously transfer data between nodes.
By weakening the distinctive features of a distributed DBMS, a parallel database system is obtained. There is no clear distinction between parallel and distributed DBMS. In particular, parallel DBMS architectures with no shared resources (sharing-nothing), which are discussed below, are similar to loosely coupled distributed systems. Parallel DBMSs use the latest multiprocessor architectures, and on the basis of this approach, high-performance, high-availability database servers are created, the cost of which is significantly lower than the equivalent systems on the mainframe.
A parallel DBMS can be defined as a DBMS implemented on a multiprocessor computer. Such a definition implies the presence of many alternatives, the range of which varies from directly transferring existing DBMS with processing only the interface to the operating system to sophisticated combinations of parallel processing algorithms and database functions leading to new hardware-software architectures. As always, one has to choose between portability (on multiple platforms) and efficiency. Sophisticated approaches are aimed mainly at more fully using the advantages of a particular multiprocessor at the expense of portability.
The solution, therefore, is to use large-scale parallelism in order to increase the power of individual components by integrating them into an integrated system based on appropriate parallel database software. It is important to use standard hardware components in order to be able to use the results of constant technological improvements with a minimum lag. The database software can provide three types of parallelism inherent in intensive data processing applications. Inter-query parallelism involves the simultaneous execution of multiple queries related to different transactions. By intra query parallelism is meant the simultaneous execution of several operations at once (for example, sampling operations) related to the same request. Both intra-request and inter-request parallelism are implemented on the basis of data separation , similar to horizontal fragmentation. Finally, the concept of intraoperative parallelism means the parallel execution of a single operation as a set of suboperations with the application, in addition to data fragmentation, also the fragmentation of functions . Set-oriented database languages provide many possibilities for the use of intra-operational parallelism.
The following are characteristic features of parallel and distributed DBMS.
Transparency issues are more critical for distributed than for parallel DBMS. There are two reasons for this. Firstly, multiprocessor systems for which parallel DBMSs are implemented operate under the control of a single operating system. The operating system can be organized in such a way as to assume some aspects of the functionality of the DBMS, thereby providing a certain degree of transparency. Second, software development on parallel systems is supported by parallel programming languages that also provide some degree of transparency.
In distributed DBMS, data and applications that access them can be localized on the same node, thereby eliminating (or reducing) the need for remote data access, which is characteristic of data-processing systems in time-sharing mode. Further, since fewer applications are running on each node and a smaller portion of the database is stored, it is also possible to reduce the competition in accessing data and resources. Finally, concurrency, intrinsic to distributed systems, opens up possibilities for implementing inter-request and intra-request parallelism.
If user access to the database is only in the execution of queries (that is, there is read-only access), then the implementation of inter-query and intra-query parallelism implies replication of the maximum possible part of the database. But, since in practice, access to the database is not only readable, in order to implement intermittent reading and data modification operations, support of distributed transactions (discussed in a later section) is necessary.
High performance is one of the most important goals for the achievement of which the technologies of parallel DBMS are aimed. As a rule, it is provided by combining several mutually complementary solutions, such as the use of database-oriented operating systems, concurrency, optimization, and load balancing. Having an operating system that is “aware” of the specific needs of databases (for example, with regard to buffer management) simplifies the implementation of lower-level database functions and helps reduce their cost. Thus, the cost of sending a message can be significantly reduced (up to several hundred instructions) through the use of a specialized communication protocol. Parallelization mechanisms contribute to an increase in the overall system capacity (inter-request parallelism), and lower response times for individual transactions (intra-request and intra-operation parallelism).
Technologies of distributed and parallel DBMS are also aimed at improving reliability, because, due to data replication, single points of failure are eliminated. Failure of one node or failure of the communication line does not lead to the failure of the entire system. Even if part of the data becomes inaccessible, with proper organization of the system, users may have access to the rest of the information. The "right organization" means support for distributed transactions and reliability assurance protocols (i.e., commit and restore protocols). These issues are discussed in the next section.
In a parallel and distributed database environment, it is easier to resolve issues related to the increase in database size or processing needs. In this case, it is rarely necessary to seriously rebuild the system; Empowerment is usually achieved by adding processor power or memory.
Ideally, a parallel (and, to a lesser extent, distributed) DBMS has the property of linear scalability (linear scaleup) and linear acceleration (linear speedup) . Linear scalability is understood to mean maintaining the same level of performance while increasing the size of the database and simultaneously proportional increase in processor power and memory. Linear acceleration means that with increasing processor power and memory while maintaining the same size of the database, the performance will increase proportionally. Moreover, the expansion of the system should require only a minimal reorganization of the existing database.
Taking into account the price / performance ratio for microprocessors and workstations, it turns out to be more economical to create a system of several small computers than to implement it on an equivalent one large machine. Many commercial distributed DBMSs operate on mini-computers and workstations precisely because of the more favorable price / performance ratio. Technologies based on the use of workstations have become so widespread due to the fact that most commercial DBMSs can work within local networks where workstations are mainly used. The development of distributed databases designed for global WANs can lead to an increased role for mainframes. On the other hand, future-generation distributed DBMSs are likely to support hierarchical network structures, whose nodes are clusters of computers interacting in a local network, and the clusters themselves are connected via high-speed backbones.
Distributed and parallel DBMSs provide the same functionality as centralized DBMS, except for the fact that they work in an environment where data is distributed across computer network nodes or a multiprocessor system. As already mentioned, users may be completely unaware of the distribution of data. Thus, these systems provide users with a logically integrated view of a physically distributed database. Support for such a presentation is the source of a number of complex problems that must be solved by system functions. This section is devoted to the discussion of these problems. It is assumed that the reader is familiar with the basic concepts of databases.
There are many alternatives to distributed processing. The client-server architecture is currently the most popular [Orfali et al., 1994], when multiple client machines access one database server. In such systems, which can be defined as multi-client / single-server systems, database management problems are relatively easy to solve, since all of it is stored on one server. The tasks that you have to face here are client buffer management, data caching and, possibly, locking. Data management is implemented centrally on a single server.
A more distributed and more flexible is a multi-client / multi-server type architecture, when the database is hosted on several servers, which need to interact with each other in order to calculate the result of a user query or perform a transaction. Each client machine has its own "home" server; it sends custom requests to it. The interaction of servers with each other is transparent to users. Most of the existing DBMSs implement one of these two types of client-server architecture.
In a truly distributed DBMS client and server machines do not differ. Ideally, each node can act both as a client and as a server. Such architectures, the type of which is defined as peer-to-peer , require complex data management protocols distributed across several nodes. The offer of products of this type is delayed due to the complexity of the software necessary for their implementation.
Parallel system architectures vary between two extreme points called an architecture without shared resources (shared-nothing) and a shared memory architecture (shared-memory) . The intermediate position is occupied by a shared-disk architecture .
When using the approach without shared resources, each processor has multiply access to its own RAM and to a set of disks. Thus, each node can be considered as a local machine (with its own database and software) in a distributed database system. The difference between parallel DBMSs without shared resources and distributed DBMSs, in essence, boils down to a difference in implementation platforms; therefore, most solutions developed for distributed databases can also be successfully applied to parallel databases of this type. Architectures without shared resources have three major advantages: low costs, extensibility, high availability. Their most significant problems are implementation complexity and (potential) load balancing difficulties.
Examples of parallel database systems are DBC (Teradata) and NonStop-SQL (Tandem) products, as well as a number of prototypes, such as BUBBA [Boral et al., 1990], EDS [EDS, 1990], GAMMA [DeWitt et al., 1990], GRACE [Fushimi et al., 1986], PRISMA [Apers et al., 1992] and ARBRE [Lorie et al., 1989].
The approach of shared memory is that each processor is connected to all memory modules and disk devices via fast communication lines (high-speed buses or coordinate switches). There are several mainframe types that follow this approach: IBM3090, DPS8 (Bull), and symmetric multiprocessor systems like Sequent and Encore. The two strengths of shared memory systems are simplicity and good load balancing. The three most significant problems associated with this approach are cost, limited scalability, and low reliability.
The systems of parallel databases with shared memory include XPRS [Stonebraker et al., 1988], DBS3 [Bergsten et al., 1991] and Volcano [Graefe, 1990], as well as the most well-known industrial DBMS transferred to shared memory multiprocessors. The first example of such a system was the implementation of DB2 on IBM3090 with six processors. All commercial products currently known (such as Ingres and Oracle) use only inter-request (but not intra-request) parallelism.
In systems with shared disks, each processor has access to any disk device through special connections and exclusive access to its own RAM. Thus, each processor can read any database pages and store them in its cache. To avoid conflicts when accessing the same pages, global blocking mechanisms and cache reconciliation protocols are required. The drive-based approach has the following advantages: low cost, scalability, good load balancing, high availability, easy migration from single-processor systems. At the same time, they are associated with certain difficulties: the complexity of the system, potential performance problems.
Examples of parallel DBMS with shared disks: IMS / VS Data Sharing (IBM) product, as well as DEC VAX DBMS and Rdb products. The Oracle implementation on VAXcluster (DEC) and NCUBE also uses disk partitioning, since this approach requires minimal extensions in the database engine. Отметим, что во всех этих системах применяется только межзапросный параллелизм.
Обработка запроса (query processing) – это процесс трансляции декларативного определения запроса в операции манипулирования данными низкого уровня. Стандартным языком запросов, поддерживаемым современными СУБД, является SQL. Оптимизация запроса (query optimization) – это процедура выбора "наилучшей" стратегии выполнения запроса из множества альтернатив.
Для централизованной СУБД весь процесс состоит обычно из двух шагов: декомпозиции запроса (query decomposition) и оптимизации запроса . Декомпозиция запроса – это трансляция его с языка SQL в выражение реляционной алгебры. В ходе декомпозиции запрос подвергается семантическому анализу; при этом некорректные запросы отвергаются, а корректные упрощаются. Упрощение заключается, в частности, в исключении избыточных предикатов, которые могли быть привнесены за счет использования представлений, а также исходя из ограничений безопасности и семантической целостности. Упрощенный запрос преобразуется в алгебраическую форму.
Для заданного SQL-запроса существует более чем одно алгебраическое представление, причем некоторые из них могут быть "лучше" других. "Качество" алгебраического выражения определяется исходя из объема затрат, необходимых для его вычисления. Традиционная процедура состоит в том, чтобы сначала оттранслировать SQL-запрос в какое-нибудь выражение, а затем, применяя правила эквивалентных алгебраических преобразований, получать из него другие алгебраические преобразования, пока не будет найдено "наилучшее". При поиске "наилучшего" выражения используется функция стоимости, в соответствии с которой вычисляется сумма затрат, необходимых для выполнения запроса. Этот процесс и называется оптимизацией запросов.
В распределенной СУБД между шагами декомпозиции и оптимизации запроса включаются еще два действия: локализация данных (data localization) и глобальная оптимизация запроса (global query optimization) .
Исходной информацией для локализации данных служит исходное алгебраическое выражение, полученное на шаге декомпозиции запроса. В исходном алгебраическом выражении фигурируют глобальные отношения без учета их фрагментации или распределения. Основная роль локализации данных заключается в том, чтобы локализовать участвующие в запросе данные, используя информацию об их распределении. На этом шаге выявляются фрагменты, реально участвующие в запросе, и запрос преобразуется к форме, где операции применяются уже не к глобальным отношениям, а к фрагментам. Как отмечалось выше, правила фрагментации выражаются посредством реляционных операций (селекции для горизонтальной фрагментации и проекции для вертикальной). Распределенные отношения реконструируются путем применения инверсии правил фрагментации. Это называется программой локализации . Программа локализации для горизонтально (вертикально) фрагментированного отношения представляет собой объединение (union) (соединение (join)) соответствующих фрагментов. Таким образом, на шаге локализации данных каждое глобальное отношение запрос заменяется его программой локализации, а затем результирующий фрагментный запрос упрощается и реструктурируется с целью получения другого "хорошего" запроса. Для упрощения и реструктуризации могут использоваться те же правила, что и на шаге декомпозиции. Как и на шаге декомпозиции, окончательный запрос над фрагментами может быть еще далек от оптимального; данный процесс лишь исключает "плохие" алгебраические запросы.
Исходной информацией для третьего шага является фрагментный запрос, т. е. алгебраическое выражение над фрагментами. Цель глобальной оптимизации – найти стратегию выполнения запроса, близкую к оптимальной. Напомним, что нахождение оптимальной стратегии – вычислительно трудноразрешимая задача. Стратегию выполнения распределенного запроса можно выразить в терминах операций реляционной алгебры и коммуникационных примитивов (операций send/receive), используемых для пересылки данных между узлами. На предыдущих шагах запрос уже был в определенной мере оптимизирован, в частности, за счет удаления избыточных выражений. Однако проведенная оптимизация не зависела от характеристик фрагментов, например их мощности. Кроме того, на предыдущих шагах еще не учитывались коммуникационные операции. Путем изменения порядка операций внутри одного фрагментного запроса можно получить много эквивалентных планов его выполнения. Оптимизация запроса заключается в нахождении "наилучшего" плана из множества возможных планов, исследуемых оптимизатором 1) .
Оптимизатор запросов обычно представляется в виде трех компонентов: пространство поиска, модель стоимости и стратегия поиска. Пространство поиска – это множество альтернативных планов выполнения исходного запроса. Эти планы эквивалентны в том смысле, что они дают один и тот же результат, но различаются порядком и способами выполнения отдельных операций. Модель стоимости – это способ оценить стоимость данного плана выполнения запроса. Для достижения точности модель стоимости должна основываться на точных знаниях о среде параллельных вычислений. Стратегия поиска – это способ обхода пространства поиска и выбора наилучшего плана. Она определяет, какие планы и в каком порядке следует выбирать и оценивать.
В распределенной среде функция стоимости, часто определяемая в единицах времени, оценивает затраты вычислительных ресурсов, таких как дисковое пространство, число обменов с дисками, время центрального процессора, коммуникации и т.д. Обычно это некоторая взвешенная сумма затрат ввода-вывода, центрального процессора и коммуникаций. В распределенных СУБД применяется упрощенный подход, когда в качестве наиболее значимых рассматриваются лишь коммуникационные затраты. Это справедливо для глобальных сетей, где из-за ограниченной пропускной способности линий связи пересылки данных обходятся значительно дороже, чем при локальной обработке. Чтобы определить порядок выполнения операций, необходимо оценить стоимости выполнения планов с другим порядком операций. Определение стоимости выполнения до реального выполнения запроса (статическая оптимизация) основано на статистике фрагментов и формулах для оценки мощности результатов реляционных операций. Таким образом, решения, принимаемые в ходе оптимизации, зависят от имеющейся статистики фрагментов.
Важным аспектом оптимизации запросов является порядок выполнения соединений , поскольку его изменение может привести к ускорению на нескольких порядков. Базовый метод оптимизации последовательности распределенных операций соединения заключается в применении операции полусоединения (semijoin). Основное преимущество полусоединений в распределенной системе – это сокращение размеров операндов, участвующих в соединениях, и, следовательно, коммуникационных затрат. Однако в более современных методах, учитывающих, наряду с коммуникационным расходами, также и затраты на локальную обработку, полусоединения не используются, поскольку они приводят к увеличению объема локальной обработки. Результатом работы глобального оптимизатора является оптимизированное алгебраическое выражение, включающее коммуникационные операции над фрагментами.
Параллельная обработка запросов в целом подобна распределенной обработке запросов. Она опирается на преимущества внутризапросного параллелизма, который обсуждался выше, а также межоперационного параллелизма.
Внутриоперационный (intra-operation) параллелизм достигается за счет выполнения операции сразу на нескольких узлах многопроцессорной машины. Для этого необходимо предварительное разбиение операндов, т.е. их горизонтальная фрагментация по узлам. Способ разделения базового отношения относится к области физического проектирования базы данных. Обычно разделение производится путем применения некоторой хэш-функции к тому атрибуту отношения, который будет часто являться атрибутом соединения. Набор узлов, в которых хранится отношение, называется домашним набором (home) . Домашним набором узлов операции (home of an operation) называется набор узлов, в которых она выполняется; оно должно совпадать с домашним набором узлов ее операндов, чтобы операция имела доступ к своим операндам. Это значит, что для бинарных операций, таких как соединения, может потребоваться переразделение (repartitioning) одного из операндов. В некоторых случаях оптимизатор, возможно, сочтет целесообразным провести переразделение обоих операндов. Для реализации внутриоперационного параллелизма в параллельных СУБД применимы некоторые методы, разработанные для распределенных баз данных.
Межоперационный (inter-operation) параллелизм имеет место, когда одновременно выполняются две или более операции, независимые или связанные общим потоком данных. Термином поток данных (dataflow) мы обозначаем форму параллелизма, реализуемую методами конвейерной обработки (pipelining) . При независимом параллелизме операции выполняются одновременно или в произвольном порядке. Независимый параллелизм возможен, только если операции не содержат в качестве операндов общих данных.
Если несколько пользователей одновременно (concurrently) осуществляет доступ (на чтение и запись) к совместно используемой базе данных, то для поддержки согласованного состояния данных требуется синхронизовать доступ. Синхронизация достигается путем применения алгоритмов управления одновременным доступом (concurrency control algorithm) , гарантирующих следование критериям корректности, таким как сериализуемость (serializability) . Доступ пользователей к данным инкапсулируются в рамках транзакций [Gray, 1981], которые на нижнем уровне выглядят как последовательности операций чтения и записи данных. Алгоритмы управления одновременным доступом обеспечивают соблюдение свойства изолированности выполнения транзакций, которое заключается в том, что воздействия одной транзакции на базу данных не будут зависеть (т.е. будут изолированы) от других транзакций, пока эта первая транзакция не завершит свое выполнение.
Наиболее популярные алгоритмы управления одновременным доступом основаны на механизме блокировок . В таких схемах всякий раз, когда транзакция пытается получить доступ к какой-либо единице памяти (как правило, странице), на эту единицу накладывается блокировка в одном из режимов – совместном (shared) или монопольном (exclusive). Блокировки накладываются в соответствии с правилами совместимости блокировок, исключающими конфликты чтение-запись , запись-чтение и запись-запись . Согласно известной теореме, сериализуемость транзакций заведомо гарантируется, если блокировки, относящиеся к одновременно выполняемым транзакциям, удовлетворяют простому правилу: "Ни одна блокировка от имени какой-либо транзакции не должна устанавливаться после снятия хотя бы одной ранее установленной блокировки". Это правило известно под названием двухфазной блокировки [Gray, 1979], поскольку транзакция проходит при этом сначала фазу "роста", когда она устанавливает блокировки, а затем фазу "сжатия", когда блокировки снимаются. В общем случае снятие блокировок до завершения транзакции проблематично. Поэтому в большинстве алгоритмов управления одновременным доступом применяется более жесткий подход, когда блокировки не снимаются до конца транзакции.
Для распределенных СУБД возникает проблема распространения свойства сериализуемости и алгоритмов управления одновременным доступом на распределенную среду. В таких системах операции, относящиеся к одной транзакции, могут выполняться на нескольких узлах, где располагаются необходимые данные. В этом случае наибольшую сложность представляет обеспечение сериализуемости. Эта сложность связана с тем, что на разных узлах порядок сериализации одного и того же множества транзакций может оказаться различным. Поэтому выполнение множества распределенных транзакций является сериализуемым тогда и только тогда, когда:
Алгоритмы управления распределенным одновременным доступом поддерживают это свойство, называемое глобальной сериализуемостью (global serializability) . В алгоритмах, основанных на блокировках, для этого применяется один из трех методов: централизованное блокирование, блокирование первичных копий и распределенное блокирование.
При централизованном блокировании (centralized locking) для всей распределенной базы данных поддерживается единая таблица блокировок. Эта таблица, располагаемая в одном из узлов, находится под управлением единого менеджера блокировок. Менеджер блокировок отвечает за установку и снятие блокировок от имени транзакций. Поскольку управление всеми блокировками сосредоточено на одном узле, то оно аналогично централизованному управлению одновременным доступом, и глобальная сериализуемость обеспечивается достаточно легко. Соответствующие алгоритмы просты в реализации, но с ними связаны две проблемы. Во-первых, центральный узел может стать узким местом как из-за большого объема обработки данных, так и из-за генерируемого вокруг него интенсивного сетевого трафика. Во-вторых, надежность такой системы ограничена, поскольку отказ или недоступность центрального узла приводит к выходу из строя всей системы.
Блокирование первичных копий (primary copy locking) – это алгоритм управления одновременным доступом, применяемый для баз данных с репликациями, где копии одних и тех же данных могут храниться в нескольких узлах. Одна из таких копий определяется как первичная копия, и для доступа к любому элементу данных необходимо установить блокировку на его первичную копию. Множество первичных копий элементов данных известно всем узлам распределенной системы, и запросы транзакций на блокирование направляются в узлы, где хранятся первичные копии. Если в распределенной базе данных репликации не используются, то данный алгоритм сводится к алгоритму распределенного блокирования. Алгоритм блокирования первичных копий был предложен для прототипа распределенной версии Ingres.
Алгоритм распределенного (или децентрализованного ) блокирования (distributed (decentralized) locking), предполагает распределение обязанностей по управлению блокировками между всеми узлами системы. Для выполнения транзакции необходимо участие и взаимная координация менеджеров блокировок в нескольких узлах. Блокировки устанавливаются во всех узлах, данные которых участвуют в транзакции. Алгоритмам распределенного блокирования не свойственны издержки механизма централизованного блокирования, связанные с перегруженностью центрального узла. Однако алгоритмы этого типа сложнее, а коммуникационные затраты, необходимые для установки всех требуемых блокировок, выше. Алгоритмы распределенного блокирования применяются в системах System R* и NonStop SQL.
Общий побочный эффект всех алгоритмов управления одновременным доступом посредством блокирования – возможность тупиковых ситуаций (deadlock) . Задача обнаружения и преодоления тупиков особенно сложна в распределенных системах. Тем не менее, благодаря относительной простоте и эффективности алгоритмов блокирования, они имеют значительно большую популярность, чем альтернативные алгоритмы, основанные на временн ы х метках (timestamp-based algorithms) , а также алгоритмы оптимистического управления одновременным доступом (optimistic concurrency control) . Алгоритмы, основанные на временн ы х метках, выполняют конфликтующие операции транзакций в соответствии с временными метками, назначаемыми транзакциям при их поступлении в систему. Алгоритмы оптимистического управления одновременным доступом исходят из предположения о том, что конфликты между транзакциями редки, и доводят транзакцию до конца, а затем производят проверку корректности. Если выясняется, что фиксация данной транзакции повлечет нарушение сериализуемости, то транзакция откатывается и запускается снова.
Как отмечалось выше, распределенные СУБД потенциально более надежны в силу того, что системные компоненты в них дублируются, и тем самым исключаются одиночные точки отказа. Для реализации этого потенциала необходима тщательная проработка структуры системы, а также соответствующие протоколы обработки системных сбоев.
В распределенной СУБД различаются четыре типа сбоев: сбой транзакции (transaction failure) , сбой узла (системы) (site (system) failure) , сбой носителя (диска) (media (disk) failure) и сбой коммуникационной линии (communication line failure) .
Причин сбоев транзакции может быть несколько: ошибки, вызванные неверными входными данными, обнаружение возникшего или возможного тупика. Обычный способ обработки таких сбоев заключается в том, чтобы прервать транзакцию и откатить базу данных к состоянию, предшествовавшему началу транзакции.
Сбои узлов (систем) могут быть вызваны аппаратными отказами (процессора, оперативной памяти, питания) или программными ошибками (в системном или прикладном коде). Системные сбои приводят к потере содержимого оперативной памяти. Поэтому в этом случае пропадут все элементы базы данных данных, находящиеся в буферах оперативной памяти (и называемые также неустойчивой базой данных (volatile database) ). В то же время данные, находящиеся во вторичной памяти (называемые также стабильной базой данных (stable database) ), остаются в сохранности. Для поддержания сохранности данных обычно применяют протоколы журнализации (logging protocol) , например, журнализация с упреждающей записью (Write-Ahead Logging) , которые создают в системных журналах записи обо всех изменениях в базе данных и в подходящие моменты времени перемещают журнальные записи, а также страницы неустойчивой базы данных в стабильную память. В распределенной базе данных проблема системных сбоев выражается еще и в том, что отказавший узел не может участвовать в выполнении какой-либо транзакции.
Сбои носителей – это сбои устройств вторичной памяти, на которых хранится стабильная база данных. Обычно эта проблема решается путем дублирования устройств вторичной памяти и поддержки архивных копий базы данных. Сбои носителей рассматриваются обычно как локальная проблема узла, и специальных механизмов для их обработки в распределенных СУБД не предусматривается.
Рассмотренные выше три типа сбоев характерны и для централизованных, и для распределенных СУБД. Коммуникационные сбои, напротив,
продолжение следует...
Часть 1 Distributed and parallel database systems
Часть 2 Исследовательские проблемы - Distributed and parallel database systems
Часть 3 Объект и предмет исследования. - Distributed and parallel database systems
Comments
To leave a comment
Databases, knowledge and data warehousing. Big data, DBMS and SQL and noSQL
Terms: Databases, knowledge and data warehousing. Big data, DBMS and SQL and noSQL