Dynamic end-to-end reliable causal delivery middleware for geo-replicated services

Abstract

O crescimento da dependência de serviços baseados na Internet, durante as últimas duas décadas, causou um aumento na adoção de sistemas geo-replicados. O desenho deste sistemas é enquadrado à luz do teorema CAP. Neste contexto os modelos de coerência relaxada – Eventual Consistency – permitem reduzir o tempo de resposta para com os utilizadores finais e, assim, aumentar a disponibilidade dos sistemas e obter interações mais rápidas. O advento de novas técnicas de convergência como Conflictfree Replicated Data Types, amplamente adotados na indústria de geo-replicação como seja no Facebook, PayPal, Microsoft, SoundCloud, entre outros, permitiu também um maior enquadramento formal destas técnicas. Em particular, o modelo de coerência causal, provou ser o modelo mais forte para sistemas sempre disponíveis. Assim torna-se relevante revisitar as técnicas de comunicação causal em grupo, e associado middleware de transmissão, pois sendo que muitos destes sistemas foram originalmente construídas à perto de três décadas, precisam de ser adequados ao contexto actual de utilização. Esta tese principia pela análise de novas abstrações para a garantia de propriedades end-to-end no registo e entrega causal. Prossegue com a observação de anomalias e ineficiências resultantes de implementações multi-threaded de entrega causal, e com a identificação de uma primeira abordagem para garantir causalidade entres os dois extremos do sistema. Após a identificação de problemas na escalabilidade nas implementações que se baseiam em vectores versão ou relógios lógicos, é proposta uma nova solução baseada na manipulação de grafos de dependências e numa eficiente manutenção e simplificação dos mesmos, recorrendo à observação de propriedades de estabilidade. É também proposta uma nova API aos utilizadores do middleware de comunicação. A avaliação das soluções propostas foi feita com base num sistema programado em Erlang e foi feita a sua avaliação de desempenho e aplicação a quatro casos de estudo.

The reliance on Internet-based services during the past two decades caused a leap in geo-replicated systems, as a means to target clients across the globe, in the light of the CAP theorem. Therefore, relaxed consistency models got a lot of attention to reduce the response time to end users, and thus boost the availability of the systems at the cost of delayed – Eventual Consistency–. Together with the advent of new convergence techniques like Conflict-free Replicated Data Types—widely adopted in the georeplication industry like Facebook, PayPal, Microsoft, SoundCloud, etc., this lead to the reliance on more useful tradeoff consistency models like the causal consistency model, proven to be strongest model for available systems. Intuitively, this suggested another visit to revise the causality techniques, broadcast middleware, and abstractions, originally built three decades earlier for a different set of digital services, i.e., applications, capabilities, and usage. The research in this thesis analyzes the end to end workflow of causality-based services, leading to the identification of new problems and shortcoming in state of the art causality techniques and abstractions, and proposing novel corresponding ones. First, this work discovers that, given that many applications are today multi-threaded, handling causality while overlooking this fact will lead into semantic pitfalls in some classes of applications. A corresponding technique is proposed in this thesis to apply end-to-end time-stamping at the application level instead of the causal middleware. Second, this thesis points out a scalability problem in state of the art causal broadcast middlewares that rely on vector clocks for timestamping. This thesis proposes the first graph-based abstraction for timestamping which is proven to be one order of magnitude more scalable and efficient than its state of the art counterpart. Third, this work identifies existing redundancy in the time-stamping methods used in both causal middleware and application logic, and thus proposes a slightly modified, but effective, API that reduces the bandwidth metadata overhead by half. The API includes the notion of causal stability that makes garbage collection fast and easy. Fourth, this thesis introduces the first technique for dynamic causality middleware, crucial in elastic services, leading to guaranteed causal delivery under dynamic membership. These contributions are then implemented in a comprehensive well-engineered codebase in Erlang. To demonstrate its usefulness and feasibility, this work has been applied to four practical use-cases and projects during the course of this thesis.