FenixEdu™

Dissertação

{en_GB=A Distributed and Hierarchical Architecture for Deferred Validation of Transactions in Key-Value Stores} {} EVALUATED

Detalhes: {pt=Os sistemas de armazenamento chave-valor são hoje um componente central dos sistemas distribuídos de grande escala. Os primeiros sistemas deste tipo não ofereciam suporte para transações, mas com a sua evolução tornou-se relevante oferecer este tipo de garantias. O desafio que se coloca é como oferecer suporte transacional sem comprometer o elevado débito que caracteriza os sistemas chave-valor. Nesta tese propomos uma nova arquitetura para realizar a validação das transações, de forma distribuída. A arquitetura tira partido to facto dos dados guardados nos sistemas de armazenamento chave-valor atuais estarem particionados em vários servidores e de que dados correlacionados podem ser guardados no mesmo servidor desde que seja usada uma função de particionamento adequada. Neste contexto, transações que acedam a dados correlacionados da mesma partição (transações locais) podem ser validadas e confirmadas de forma concorrente, por diferentes servidores. Transações que acedam a múltiplas partições (transações distribuídas) podem demorar mais a ser validadas e confirmadas, mas sem atrasarem o processamento das primeiras. A arquitetura recorre a uma hierarquia em árvore de validadores, em que os nós folha são responsáveis por uma só partição, oferecendo maior débito e menor latência, enquanto que os nós que não são folha são responsáveis por múltiplas partições. Apresenta-se uma extensa avaliação experimental da arquitetura proposta que permite aferir as suas vantagens e limitações. Esta avaliação mostra que, nalguns cenários, a arquitetura proposta consegue melhorias até 23% em relação a outras estratégias alternativas para fazer a validação das transações, tal com a confirmação distribuída em duas fases., en=Key-value stores are today a fundamental component for building large-scale distributed systems. Early key-value stores did not offer any support for running transactions but, with time, it became obvious that such support could simplify the application design and development. The key challenge in this context is to support transactional semantics while preserving the scalability properties of key-value stores. In this thesis we propose an architecture to perform transaction validation in a distributed and scalable manner. The architecture exploits the fact that in the current key-value stores, data is partitioned across multiple servers and that correlated data can be stored in the same server if the appropriate partitioning function is used. In this context, transactions that access correlated data in the same partition (local transactions) can be validated and committed concurrently, by different servers. Transactions that access multiple partitions (distributed transactions) can take longer to be validated and committed, but do not interfere with local transactions. The architecture is based on a tree of transaction validators, where the leaf nodes are responsible for single partitions, offering higher throughput and lower latency, while non-leaf nodes are responsible for several partitions. We have performed an extensive experimental validation of the proposed architecture that highlights its advantages and limitations. The evaluation shows that, in some scenarios, the proposed architecture can offer improvements up to 23% when compared to other validation and commit strategies, such as distributed two-phase commit.}
Keywords: {pt=Transacções; Armazenamento Chave-Valor;, en=Transactions; Key-value Stores;}

Discussão: novembro 5, 2018, 9:0