Efficient protocols for generalized consensus and partial replication
Pierre Sutra · OpenGrey (Institut de l'Information Scientifique et Technique) · 2010
Un objet partage est un objet accede logiquement par plusieurs processus a la fois. Le placement sur plusieurs machines d'une copie physique d'un objet partage est appelee replication. La replication permet d'accroitre la disponibilite et les performances d'acces des objets partages dans un systeme reparti. Cette technique joue un role primordiale dans les systemes d'information modernes. Toutefois, la replication pose le problemes de la gestion de la coherence des repliques en presence d'acces concurrents en ecriture, de disfonctionnalites du reseau, ou de defaillances materielles et logicielles. Consensus est la primitive de communication centrale a la construction d'objets partages dans un systeme reparti. La complexite en temps, ou latence, de consensus determine par consequent les performances du systeme dans son ensemble. L'amelioration de la latence de consensus a fait l'objet de nombreux travaux dans la communaute des systemes repartis. En particulier, l'algorithme Paxos constitue une solution efficace et bien connue a consensus. Dans un article recent, Lamport ameliore Paxos. En prenant en compte la commutativite des operations. La nouvelle primitive de communication obtenue, denommee Genereralized Paxos, reduit la latence de Paxos lorsque les acces concurrents sont soit commutatifs soit spontanement ordonnes par le reseau. Cependant lorsqu'une collision a lieu, c'est a dire que deux repliques recoivent des operations concurrentes et non-commutatives dans des ordres differents, la latence de Generalized Paxos est superieure a celle de Paxos. Dans la premiere partie de cette these nous presentons un nouvel algorithme pour resoudre le consensus: FGGC. FGGC reduit le delai de recouvrement de Generalized Paxos lorsqu'une collision a lieu. Au cours des executions sans faute, la latence de FGGC est optimale: deux etapes de communication si les processus recoivent les operations non-commutatives dans le meme ordre, et trois dans le cas inverse. Par ailleurs, notre algorithme est optimal au regard des fautes: il tolere f<n/2 fautes ou n est le nombre de repliques, et utilise seulement f+1 processus pour progresser. Les processus repartis accedent rarement le meme objet. Il est donc interessant de repliquer partiellement les objets partages. La replication partielle ameliore la proximite et donc les performances des acces aux objets partages, et utilise les ressources de stockage de maniere econome. Dans la seconde partie de cette these nous traitons de la replication partielle. Nous presentons deux protocoles de consensus permettant l'acces transparent aux objets repliques partiellement. Nos protocoles sont authentiques, a savoir, si un commande accede un ensemble O d'objets simultanement, alors seules les repliques des objets inclus dans O executent des pas de calcul pour traiter cette commande. Le premier protocole que nous decrivons est sensible a un effet de bord: le convoyage, entre operations concurrentes qui ralentit leur execution. Notre deuxieme protocole ameliore les performances en diminuant l'effet de convoyage. Une evaluation montre l'efficacite de notre approche.