João Bernardo Sena Amaro

A Distributed and Hierarchical Architecture for Deferred Validation of Transactions in Key-Value Stores

Tese submetida para provas de mestrado em Engenharia Informática e de Computadores Instituto Superior Técnico, Universidade de Lisboa.


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.


A Distributed and Hierarchical Architecture for Deferred Validation of Transactions in Key-Value Stores
João Bernardo Sena Amaro
MSc Thesis. Instituto Superior Técnico, Universidade de Lisboa.
November, 2018.
Available BibTeX, MSC Thesis, and extended abstract, and mid-term report.
Uma Arquitetura Distribuída e Hierárquica para Validação Diferida de Transações em Sistemas de Armazenamento Chave-Valor.
J. Amaro, L. Rodrigues, M. Bravo, M. Matos and P. Romano
Actas do décimo Simpósio de Informática (Inforum), Coimbra, Portugal, Sep. 2018.
Available poster abstract (pdf).

Luís Rodrigues