Les principales contributions de cette thèse sont au nombre de trois. La première partie de cette thèse concerne le développement d’un nouveau protocole de réplication nommé LibRe, permettant de limiter le nombre de lectures obsolètes dans un système de stockage distribué. LibRe est un acronyme signifiant "Library for Replication". Le principal objectif de LibRe est d’assurer la cohérence des données en contactant un minimum de répliques durant les opérations de lectures où d’écritures. Dans ce protocole, lors d’une opération d’écriture, chaque réplique met à jour un registre (la "librairie"), de manière asynchrone, avec l’identifiant de version de la donnée modifiée. Lors des opérations de lecture, la requête est transférée au réplica le plus approprié en fonction de l’information figurant dans le registre. Ce mécanisme permet de limiter le nombre de lectures obsolétes. L’évaluation de la cohérence d’un système reste un problème difficile à resoudre, que ce soit par simulation ou par évaluation en conditions réelles. Par conséquent nous avons développé un simulateur appelé Simizer, qui permet d’évaluer et de comparer la performance de différents protocoles de cohérence. Le système d’évaluation de bases de données YCSB a aussi été étendu pour évaluer l’échange entre cohérence et latence dans les systèmes de stockage modernes. Le code du simulateur et les modifications apportées à l’outil YCSB sont disponibles sous licence libre.Bien que les systèmes de bases de données modernes adaptent les garanties de cohérence à la demande de l’utilisateur, anticiper le niveau de cohérence requis pour chaque opération reste difficile pour un développeur d’application. La deuxième contribution de cette thèse cherche à résoudre ce problème en permettant à la base de données de remplacer le niveau de cohérence défini par défaut par d’autres règles définies à partir d’informations externes. Ces informations peuvent être fournies par l’administrateur ou un service extérieur. Dans cette thèse, nous validons ce modèle à l’aide d’une implémentation au sein du système de bases de données distribué Cassandra. La troisième contribution de cette thèse concerne la résolution des conflits de mise à jour. La résolution de ce type de conflits nécessite de retenir toutes les valeurs possibles d’un objet pour permettre la résolution du conflit grâce à une connaissance spécifique côté client. Ceci implique des coûts supplémentaires en termes de débit et de latence. Dans cette thèse nous discutons le besoin et la conception d’un nouveau type d’objet distribué, le registre à priorité, qui utilise une stratégie de détection et de résolution de conflits spécifique au domaine, et l’implante côté serveur. Notre approche utilise la notion d’ordre de remplacement spécifique. Nous montrons qu’un type de donnée paramètrée par un tel ordre peut fournir une solution efficace pour les applications demandant des solutions spécifiques à la résolution des conflits. Nous décrivons aussi l’implémentation d’une preuve de concept au sein de Cassandra. / The main contributions of this thesis are three folds. The first contribution of the thesis focuses on an efficient way to control stale reads in modern database systems with the help of a new consistency protocol called LibRe. LibRe is an acronym for Library for Replication. The main goal of the LibRe protocol is to ensure data consistency by contacting a minimum number of replica nodes during read and write operations with the help of a library information. According to the protocol, during write operations each replica node updates a registry (library) asynchronously with the recent version identifier of the updated data. Forwarding the read requests to a right replica node referring the registry information helps to control stale reads during read operations. Evaluation of data consistency remains challenging both via simulation as well as in a real world setup. Hence, we implemented a new simulation toolkit called Simizer that helps to evaluate the performance of different consistency policies in a fast and efficient way. We also extended an existing benchmark tool YCSB that helps to evaluate the consistency-latency tradeoff offered by modern database systems. The codebase of the simulator and the extended YCSB are made open-source for public access. The performance of the LibRe protocol is validated both via simulation as well as in a real setup with the help of extended YCSB.Although the modern database systems adapt the consistency guarantees of the system per query basis, anticipating the consistency level of an application query in advance during application development time remains challenging for the application developers. In order to overcome this limitation, the second contribution of the thesis focuses on enabling the database system to override the application-defined consistency options during run time with the help of an external input. The external input could be given by a data administrator or by an external service. The thesis validates the proposed model with the help of a prototype implementation inside the Cassandra distributed storage system.The third contribution of the thesis focuses on resolving update conflicts. Resolving update conflicts often involve maintaining all possible values and perform the resolution via domain-specific knowledge at the client side. This involves additional cost in terms of network bandwidth and latency, and considerable complexity. In this thesis, we discuss the motivation and design of a novel data type called priority register that implements a domain-specific conflict detection and resolution scheme directly at the database side, while leaving open the option of additional reconciliation at the application level. Our approach uses the notion of an application-defined replacement ordering and we show that a data type parameterized by such an order can provide an efficient solution for applications that demand domain-specific conflict resolution. We also describe the proof of concept implementation of the priority register inside Cassandra. The conclusion and perspectives of the thesis work are summarized at the end.

Les bases de données répliquées cohérentes à terme récentes encapsulent la complexité de la concurrence et des pannes par le biais d'une interface supportant la cohérence causale, protégeant l'application des problèmes d'ordre, et/ou des Types de Données Répliqués (RDTs), assurant une sémantique convergente des mises-à-jour concurrentes en utilisant une interface objet. Cependant, les algorithmes fiables pour les RDTs et la cohérence causale ont un coût en terme de taille des métadonnées. Cette thèse étudie la conception de tels algorithmes avec une taille de métadonnées minimisée et leurs limites. Notre première contribution est une étude de la complexité des métadonnées des RDTs. Les nombreuses implémentations existantes impliquent un important surcoût en espace de stockage. Nous concevons un ensemble optimisé et un registre RDTs avec un surcoût des métadonnées réduit au nombre de répliques. Nous démontrons également les bornes inférieures de la taille des métadonnées pour six RDTs, prouvant ainsi l'optimalité de quatre implémentations. Notre seconde contribution est le design de SwiftCloud, une base de données répliquée causalement cohérente d'objets RDTs pour les applications côté client. Nous concevons des algorithmes qui supportent un grand nombre de répliques partielles côté client, s'appuyant sur le cloud, tout en étant tolérant aux fautes et avec une faible taille de métadonnées. Nous démontrons comment supporter la disponibilité (y compris la capacité à basculer entre des centre de données lors d'une erreur), la cohérence et le passage à l'échelle (petite taille de métadonnées, parallélisme) au détriment d'un léger retard dans l'actualisation des données. / Eventually consistent replicated databases offer excellent responsiveness and fault-tolerance, but expose applications to the complexity of concurrency andfailures. Recent databases encapsulate these problems behind a stronger interface, supporting causal consistency, which protects the application from orderinganomalies, and/or Replicated Data Types (RDTs), which ensure convergent semantics of concurrent updates using object interface. However, dependable algorithms for RDT and causal consistency come at a cost in metadata size. This thesis studies the design of such algorithms with minimized metadata, and the limits of the design space. Our first contribution is a study of metadata complexity of RDTs. RDTs use metadata to provide rich semantics; many existing RDT implementations incur high overhead in storage space. We design optimized set and register RDTs with metadata overhead reduced to the number of replicas. We also demonstrate metadata lower bounds for six RDTs, thereby proving optimality of four implementations. Our second contribution is the design of SwiftCloud, a replicated causally-consistent RDT object database for client-side applications. We devise algorithms to support high numbers of client-side partial replicas backed by the cloud, in a fault-tolerant manner, with small metadata. We demonstrate how to support availability and consistency, at the expense of some slight data staleness; i.e., our approach trades freshness for scalability (small metadata, parallelism), and availability (ability to fail-over between data centers). We validate our approach with experiments involving thousands of client replicas.

Cette thèse présente les résultats du projet de recherche Coopeer sur le thème de la conception collaborative. Ce travail a permis de mettre en place une architecture d'égal à égal pour la conception assistée par ordinateur (CAO) associée à une méthode optimiste de résolution automatique des conflits pour assurer la cohérence des données répliquées. Cette méthode s'appuie sur une estampille à double identification et sur une gestion de la simultanéité basée sur des priorités. La gestion du groupe de travail et la tolérance aux pannes y sont également adressées. La méthode est applicable à la CAO, mais aussi à tout type d'application collaborative complexe.