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

Evaluating the performance of distributed agreement algorithms : tools, methodology and case studies

Urbán, Péter ; Schiper, André (Dir.)

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

Ajouter à la liste personnelle
    Summary
    Nowadays, networked computers are present in most aspects of everyday life. Moreover, essential parts of society come to depend on distributed systems formed of networked computers, thus making such systems secure and fault tolerant is a top priority. If the particular fault tolerance requirement is high availability, replication of components is a natural choice. Replication is a difficult problem as the state of the replicas must be kept consistent even if some replicas fail, and because in distributed systems, relying on centralized control or a certain timing behavior is often not feasible. Replication in distributed systems is often implemented using group communication. Group communication is concerned with providing high-level multipoint communication primitives and the associated tools. Most often, an emphasis is put on tolerating crash failures of processes. At the heart of most communication primitives lies an agreement problem: the members of a group must agree on things like the set of messages to be delivered to the application, the delivery order of messages, or the set of processes that crashed. A lot of algorithms to solve agreement problems have been proposed and their correctness proven. However, performance aspects of agreement algorithms have been somewhat neglected, for a variety of reasons: the lack of theoretical and practical tools to help performance evaluation, and the lack of well-defined benchmarks for agreement algorithms. Also, most performance studies focus on analyzing failure free runs only. In our view, the limited understanding of performance aspects, in both failure free scenarios and scenarios with failure handling, is an obstacle for adopting agreement protocols in practice, and is part of the explanation why such protocols are not in widespread use in the industry today. The main goal of this thesis is to advance the state of the art in this field. The thesis has major contributions in three domains: new tools, methodology and performance studies. As for new tools, a simulation and prototyping framework offers a practical tool, and some new complexity metrics a theoretical tool for the performance evaluation of agreement algorithms. As for methodology, the thesis proposes a set of well-defined benchmarks for atomic broadcast algorithms (such algorithms are important as they provide the basis for a number of replication techniques). Finally, three studies are presented that investigate important performance issues with agreement algorithms. The prototyping and simulation framework simplifies the tedious task of developing algorithms based on message passing, the communication model that most agreement algorithms are written for. In this framework, the same implementation can be reused for simulations and performance measurements on a real network. This characteristic greatly eases the task of validating simulation results with measurements (or vice versa). As for theoretical tools, we introduce two complexity metrics that predict performance with more accuracy than the traditional time and message complexity metrics. The key point is that our metrics take account for resource contention, both on the network and the hosts; resource contention is widely recognized as having a major impact on the performance of distributed algorithms. Extensive validation studies have been conducted. Currently, no widely accepted benchmarks exist for agreement algorithms or group communication toolkits, which makes comparing performance results from different sources difficult. In an attempt to consolidate the situation, we define a number of benchmarks for atomic broadcast. Our benchmarks include well-defined metrics, workloads and failure scenarios (faultloads). The use of the benchmarks is illustrated in two detailed case studies. Two widespread mechanisms for handling failures are unreliable failure detectors which provide inconsistent information about failures, and a group membership service which provides consistent information about failures, respectively. We analyze the performance tradeoffs of these two techniques, by comparing the performance of two atomic broadcast algorithms designed for an asynchronous system. Based on our results, we advocate a combined use of the two approaches to failure handling. In another case study, we compare two consensus algorithms designed for an asynchronous system. The two algorithms differ in how they coordinate the decision process: the one uses a centralized and the other a decentralized communication schema. Our results show that the performance tradeoffs are highly affected by a number of characteristics of the environment, like the availability of multicast and the amount of contention on the hosts versus the amount of contention on the network. Famous theoretical results state that a lot of important agreement problems are not solvable in the asynchronous system model. In our third case study, we investigate how these results are relevant for implementations of a replicated service, by conducting an experiment in a local area network. We exposed a replicated server to extremely high loads and required that the underlying failure detection service detects crashes very fast; the latter is important as the theoretical results are based on the impossibility of reliable failure detection. We found that our replicated server continued working even with the most extreme settings. We discuss the reasons for the robustness of our replicated server.
    Résumé
    De nos jours, les réseaux informatiques sont omniprésents dans notre vie quotidienne, et notre société est devenue de plus en plus dépendante de systèmes informatiques répartis. Par conséquent, garantir la sûreté de fonctionnement (p.ex., sécurité, tolérance aux pannes) de tels systèmes est devenu un objectif de première importance. Afin de garantir une certaine tolérance aux pannes et assurer un haut degré de disponibilité d'un système, il est naturel de chercher à en répliquer les composants. Néanmoins, la réplication est difficile à mettre en œuvre dans les systèmes répartis. La principale difficulté consiste à maintenir la cohérence des réplicas, tout en s'affranchissant d'un contrôle centralisé. La réplication dans les systèmes répartis est souvent mise en œuvre au moyen de mécanismes de communication de groupe. La communication de groupe est constituée de diverses primitives de communication de haut niveau avec destinations multiples, ainsi que d'outils associés. Dans la plupart des cas, l'accent est mis sur la tolérance aux pannes de processus de type fail-stop. Au cœur de ces primitives de communication, se trouve généralement un problème d'accord réparti ; par exemple, les membres d'un groupe doivent décider, d'un commun accord, l'ensemble des messages qu'ils vont remettre à l'application, l'ordre de livraison de ces messages, ou bien la liste des processus supposés être tombés en panne. Beaucoup d'algorithmes permettant de résoudre des problèmes d'accord ont été proposés et prouvés correct. Par contre, l'aspect performance de ces algorithmes a rarement été traité en profondeur. Cela est lié à plusieurs raisons dont les principales sont le manque d'outils, théoriques autant que pratiques, permettant de faciliter l'analyse de performance, ainsi que la quasi absence de bancs d'essais standards. D'autre part, le fait que la plupart des analyses sont restreintes à des exécutions sans défaillances est une raison supplémentaire. Selon nous, le manque de compréhension des aspects performance, tant pour les cas avec défaillances que sans, se pose comme un important facteur limitatif pour l'adoption en pratique de protocoles d'accord tolérants aux pannes. Cela peut notamment expliquer leur faible utilisation dans l'industrie. L'objectif principal de cette thèse est de faire progresser l'état de l'art dans ce domaine. Cette thèse présente des contributions majeures dans trois domaines : des outils nouveaux, une méthodologie et des études de performance. Sur le plan utilitaire, nous présentons un outil pratique ainsi qu'un outil théorique. L'outil pratique proposé est un environnement de simulation et de prototypage pour évaluer les performances d'algorithmes répartis. L'outil théorique est un jeu de mesures de complexité pour algorithmes répartis. Sur le plan méthodologique, cette thèse propose un ensemble de bancs d'essai pour algorithmes de diffusion atomique (ces algorithmes sont à la base de nombreuses techniques de réplication). Pour finir, trois études sont présentées, qui examinent divers aspects importants liés à la performance des algorithmes d'accord. L'environnement de simulation et de prototypage simplifie la tâche ardue du développement d'algorithmes basés sur les échange de messages, qui est le modèle le plus utilisé pour décrire les algorithmes d'accord. Dans cet environnement, une même implémentation peut être utilisée aussi bien pour des simulations que pour des mesures de performance dans un réseau réel. Cette caractéristique est importante car elle facilite la validation des simulations au moyen de mesures, et vice-versa. Au niveau des outils théoriques, deux métriques de complexité sont introduites. Elles permettent d'estimer la performance réelle d'algorithmes répartis de manière plus précise que les métriques traditionnelles de complexité en temps et en messages. L'intérêt principal de nos métriques est qu'elles prennent en compte la contention des ressources partagés, aussi au niveau du réseau que des processeurs des machines. La contention est considérée comme ayant une influence significative sur les performances des algorithmes répartis. Nos métriques ont été validés de manière extensive. Actuellement, il n'existe malheureusement pas encore de bancs d'essai standards pour évaluer des algorithmes d'accord ou des systèmes de communication de groupe. Ceci rend périlleuse la comparaison de résultats de performance provenant de sources différentes. Pour remédier à cette situation, nous définissons plusieurs bancs d'essai pour algorithmes de diffusion atomique. Ceux-ci incluent des métriques, des charges de travail et des scénarios avec défaillances clairement définis. L'utilisation des bancs d'essai proposés est illustrée au moyen de deux études de performance détaillées. Deux mécanismes répandus pour le traitement des défaillances sont les détecteurs de faute, qui fournissent une information incohérente sur l'occurrence de pannes de processus, et le service de composition de groupe, qui fournit une information cohérente. Nous analysons le rapport entre les performances de ces deux techniques, en menant une comparaison de deux algorithmes de diffusion atomique dans un système asynchrone. Les résultats indiquent qu'une utilisation combinée de ces deux approches offre les meilleures performances. Dans l'étude suivante, deux algorithmes de consensus sont comparés dans un système asynchrone. La différence principale entre ces algorithmes réside dans l'utilisation d'un schéma de communication centralisé pour l'un et décentralisé pour l'autre. Les résultats obtenus démontrent que leurs performances respectives dépendent de nombreuses caractéristiques liées à l'environnement, tel que la disponibilité d'un mécanisme de diffusion au niveau du réseau ou le degré de contention sur les machines par rapport à celui du réseau. Des résultats théoriques indiquent que beaucoup d'importants problèmes d'accord ne peuvent pas être résolus dans un modèle asynchrone. Dans la dernière étude de performance de cette thèse, nous cherchons à comprendre l'importance pratique de ces résultats par le biais d'expériences dans un réseau local. Nous avons soumis un serveur répliqué à des charges très élevées, tout en maintenant un service de détection de pannes efficace ; ce dernier point est essentiel car les résultats théoriques se basent sur l'impossibilité de détecter des pannes avec certitude. Le serveur répliqué fonctionnait, y compris avec les valeurs de paramètres les plus extrêmes. L'étude se termine donc sur une discussion des raisons possibles d'un tel comportement.