Faculté informatique et communications IC, Département d'informatique, Institut d'informatique fondamentale IIF (Laboratoire de systèmes répartis LSR)

The database state machine and group communication issues

Pedone, Fernando ; Schiper, André (Dir.)

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 1999 ; no 2090.

Ajouter à la liste personnelle
    Summary
    Distributed computing is reshaping the way people think about and do daily life activities. On-line ticket reservation, electronic commerce, and telebanking are examples of services that would be hardly imaginable without distributed computing. Nevertheless, widespread use of computers has some implications. As we become more depend on computers, computer malfunction increases in importance. Until recently, discussions about fault tolerant computer systems were restricted to very specific contexts, but this scenario starts to change, though. This thesis is about the design of fault tolerant computer systems. More specifically, this thesis focuses on how to develop database systems that behave correctly even in the event of failures. In order to achieve this objective, this work exploits the notions of data replication and group communication. Data replication is an intuitive way of dealing with failures: if one copy of the data is not available, access another one. However, guaranteeing the consistency of replicated data is not an easy task. Group communication is a high level abstraction that defines patterns on the communication of computer sites. The present work advocates the use of group communication in order to enforce data consistency. This thesis makes four major contributions. In the database domain, it introduces the Database State Machine and the Reordering technique. The Database State Machine is an approach to executing transactions in a cluster of database servers that communicate by message passing, and do not have access to shared memory nor to a common clock. In the Database State Machine, read-only transactions are processed locally on a database site, and update transactions are first executed locally on a database site, and them broadcast to the other database sites for certification and possibly commit. The certification test, necessary to commit update transactions, may result in aborts. In order to increase the number of transactions that successfully pass the certification test, we introduce the Reordering technique, which reorders transactions before they are committed. In the distributed system domain, the Generic Broadcast problem and the Optimistic Atomic Broadcast algorithm are proposed. Generic Broadcast is a group communication primitive that allows applications to define any order requirement they need. Reliable Broadcast, which does not guarantee any order on the delivery of messages, and Atomic Broadcast, which guarantees total order on the delivery of all messages, are special cases of Generic Broadcast. Using Generic Broadcast, we define a group communication primitive that guarantees the exact order needs of the Database State Machine. We also present an algorithm that solves Generic Broadcast. Optimistic Atomic Broadcast algorithms exploit system properties in order to implement total order delivery fast. These algorithms are based on system properties that do not always hold. However, it they hold for a certain period, ensuring total order delivery of messages is done faster than with traditional Atomic Broadcast algorithms. This thesis discusses optimism in the implementation of Atomic Broadcast primitives, and presents in detail the Optimistic Atomic Broadcast algorithm. The optimistic broadcast approach presented in this thesis is based on the spontaneous total order message reception property, which holds with high probability in local area networks under normal execution conditions (e.g., moderate load).
    Résumé
    Les systèmes répartis sont en train de modifier profondément nos activités quotidiennes: réservation de billets en-ligne, commerce électronique, telebanking, sont des exemples de services qui n'étaient pas imaginables avant l'arrivée des systèmes répartis. Néanmoins, l'utilisation à grande échelle de systèmes informatiques n'est pas sans conséquence. Plus on devient dépendant des ordinateurs, plus leur défaillance pose des problèmes. Jusqu'à récemment, les discussions sur la défaillance des systèmes informatiques ne concernaient que des cercles restreints. La situation est en train d'évoluer. Cette thèse aborde le problème de la conception de systèmes tolérants aux pannes. Plus spécifiquement, ce travail se concentre sur le développement de bases des données qui se comportent correctement même en cas de défaillances. Pour atteindre ce but, cette thèse se base sur les notions de réplication de données et sur les communications de groupes. La réplication de données est une idée naturelle pour tolérer les pannes: si une copie d'une donnée n'est pas disponible, il suffit d'accéder à une autre copie. Par contre, garantir la cohérence des données répliquées n'est pas une tâche simple. La thèse propose l'utilisation des mécanismes de communication de groupes pour garantir la cohérence des données. La thèse comporte quatre contributions majeures. Dans le domaine des bases de données, elle introduit la "Database State Machine" et la technique de réordonnancement. La Database State Machine est une manière de gérer des transactions s'exécutant sur un cluster de serveurs de bases de données communiquant par échange de messages, et n'ayant accès ni à une mémoire partagée ni à une horloge commune. Dans ce contexte, les transactions de lecture sont exécutées localement sur un serveur, et les transactions de mise à jour sont d'abord exécutées localement sur un serveur avant d'être diffusées aux autres serveurs pour le test de certification et la validation (commit) éventuelle. Le test de certification, nécessaire à la validation, peut conduire à avorter une transaction. Dans le but d'augmenter le taux de transactions que passent le test de certification, la thèse introduit la technique de réordonnancement, qui réordonne les transactions avant de les certifier. Dans le domaine de systèmes répartis, le problème de la Diffusion Générique (Generic Broadcast) et l'algorithme de Diffusion Atomique Optimiste (Optimistic Atomic Broadcast) sont introduits. La Diffusion Générique est une primitive de communication de groupes qui permet aux applications de définir l'ordre dont elles ont besoin. La Diffusion Fiable (Reliable Broadcast) qui ne garantit aucun ordre entre les messages, et la Diffusion Atomique (Atomic Broadcast) qui garantit l'ordre total pour la livraison de messages, sont des cas particuliers de la Diffusion Générique. La Diffusion Générique est une primitive de communication de groupes qui permet d'offrir l'ordre exact nécessaire pour la Database State Machine. La thèse présente également un algorithme qui résout la Diffusion Générique. Les algorithmes de Diffusion Atomique Optimiste exploitent les propriétés du système pour délivrer efficacement les messages dans un ordre total. Ces algorithmes sont basés sur des propriétés du système qui ne sont pas toujours satisfaites. Néanmoins, si elles sont satisfaites durant une certaine période de temps, l'algorithme assure l'ordre total plus efficacement que les algorithmes de diffusion atomique traditionnels. La thèse discute l'optimisme dans le contexte de la mise en oeuvre de la Diffusion Atomique, et présente en détail un algorithme. L'optimisme exploité par cet algorithme est basé sur la propriété d'ordre spontanée, qui est satisfaite avec une probabilité élevée dans des réseaux à petite échelle dans des conditions d'exécution normale (trafic modéré, par exemple).