Implementation and evaluation of tagged causal multicast as a rust library

Abstract

Causal Consistency is gaining importance in modern geo-replicated distributed services: it is the strongest consistency model that does not sacrifice availability under high latency and network partitions. However, traditional causal delivery middleware, while ensuring a de livery order consistent with causality, does not provide client applications with knowledge about the end-to-end (as seen by each client process) happens-before relation. An end-to-end happens-before is essential to modern applications, namely for the semantics of operation based CRDTs, but also for traditional applications, in which its absence may cause incorrect behavior when using traditional causal delivery middleware. This thesis designs and im plements a Tagged Causal Multicast middleware service as a Rust library. Rust was chosen because it is a safe concurrent and fast programming language supporting both functional and imperative paradigms. This allows an efficient implementation where the use of com plex data structures does not decrease the performance as would be the case of using functional languages like Erlang. Finally, an empirical evaluation of the performance of this middleware service is made, comparing the novel graph-based implementation against a more traditional one based on vector clocks.

A Coerência Causal está a ganhar importância nos serviços distribuídos geo-replicados modernos: é o modelo de coerência mais forte que não sacrifica a disponibilidade face a partições de rede ou elevada latência. Contudo, middleware tradicional de entrega causal, apesar de garantir uma ordem de entrega consistente com a causalidade, não oferece às apli cações cliente o conhecimento sobre a relação happens-before do ponto de vista de cada pro cesso cliente. Um end-to-end happens-before é essencial para aplicações modernas, nomeada mente para a semântica de operações baseadas em CRDTs, mas também para aplicações tradicionais, na qual a sua ausência pode causar um comportamento incorreto quando se utiliza um middleware de entrega causal tradicional. Esta tese desenha e implementa um serviço de Tagged Causal Multicast, enquanto middleware, como uma biblioteca de Rust. Foi escolhida Rust por ser uma linguagem de programação segura e com bom suporte a con corrência, multi-paradigma, e apropriada para programação de sistemas. Isto permite uma implementação eficiente em que o uso de estruturas de dados complexas não diminui o desempenho, como seria o caso numa linguagem funcional como Erlang. Finalmente, é re alizada uma avaliação empírica do desempenho deste serviço de middleware, comparando a nova abordagem baseada em grafo com uma implementação mais tradicional baseada em relógios vectoriais.