Welcome to my homepage

@article{pr:osr15,
 author = {Paiva, Jo\~{a}o and Rodrigues, Lu\'{\i}s},
 title = {On Data Placement in Distributed Systems},
 journal = {SIGOPS Operating Systems Review},
 issue_date = {January 2015},
 volume = {49},
 number = {1},
 month = jan,
 year = {2015},
 issn = {0163-5980},
 pages = {126--130},
 numpages = {5},
 url = {http://doi.acm.org/10.1145/2723872.2723890},
 doi = {10.1145/2723872.2723890},
 acmid = {2723890},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {Data Placement, Distributed Systems, Key-Value Storage, Load Balancing, Replication, Scalability, Storage},
}

Data placement refers to the problem of deciding how to assign data items to nodes in a distributed system to optimize one or several of a number of performance criteria such as reducing network congestion, improving load balancing, among others. This document reports on our experience when addressing this problem in distributed systems of different scales, namely: medium size datacenter-scale and internet-scale systems.

@article{prrr:taas14,
author = {Paiva, Jo\~{a}o and Ruivo, Pedro and Romano, Paolo and Rodrigues, Lu\'{\i}s},
title = {AutoPlacer: Scalable Self-Tuning Data Placement in Distributed Key-Value Stores},
journal = {ACM Transactions on Autonomous and Adaptive Systems},
issue_date = {December 2014},
volume = {9},
number = {4},
month = dec,
year = {2014},
pages = {19:1--19:30},
doi = {10.1145/2641573},
articleno = {19},
numpages = {30},
publisher = {ACM},
address = {New York, NY, USA},
}

This paper addresses the problem of self-tuning the data placement in replicated key-value stores. The goal is to automatically optimize replica placement in a way that leverages locality patterns in data accesses, such that inter-node communication is minimized. To do this efficiently is extremely challenging, as one needs not only to find lightweight and scalable ways to identify the right assignment of data replicas to nodes, but also to preserve fast data lookup. The paper introduces new techniques that address these challenges. The first challenge is addressed by optimizing, in a decentralized way, the placement of the objects generating most remote operations for each node. The second challenge is addressed by combining the usage of consistent hashing with a novel data structure, which provides efficient probabilistic data placement. These techniques have been integrated in a popular open-source key-value store. The performance results show that the throughput of the optimized system can be six times better than a baseline system employing the widely used static placement based on consistent hashing.

@article{doprr:acr14,
author = {Diegues, Nuno and Orazov, Muhammet and Paiva, Jo\~{a}o and Rodrigues, Lu\'{\i}s and Romano, Paolo},
title = {Optimizing Hyperspace Hashing via Analytical Modelling and Adaptation},
journal = {SIGAPP Applied Computing Review},
issue_date = {June 2014},
volume = {14},
number = {2},
month = jun,
year = {2014},
issn = {1559-6915},
pages = {23--35},
numpages = {13},
doi = {10.1145/2656864.2656866},
publisher = {ACM},
address = {New York, NY, USA},
keywords = {HyperDex, analytical modelling, autonomic configuration, key-value store, multi-dimensional},
}

Hyperspace hashing is a recent multi-dimensional indexing technique for distributed key-value stores that aims at supporting efficient queries using multiple objects' attributes. However, the advantage of supporting complex queries comes at the cost of a complex configuration. In this paper we address the problem of automating the configuration of this innovative distributed indexing mechanism. We first show that a misconfiguration may significantly affect the performance of the system. We then derive a performance model that provides key insights on the behaviour of hyperspace hashing. Based on this model, we derive a technique to automatically and dynamically select the best configuration.

@inproceedings{doprr:sac14,
author = {Diegues, Nuno and Orazov, Muhammet and Paiva, Jo{\~a}o and Rodrigues, Lu{\'i}s and Romano, Paolo},
title = {Autonomic Configuration of HyperDex via Analytical Modelling},
address = {Gyeongju, Korea},
booktitle = {Proceedings of the 29th Symposium On Applied Computing},
series = {SAC'14},
publisher = {ACM},
month = mar,
year = {2014}
}

HyperDex is a recent multi-dimensional key-value store that allows efficient search for objects using their secondary attributes. However, the advantage of supporting complex queries comes at the cost of a complex configuration. In this paper we address the problem of automating the configuration of this sort of novel key-value stores. We first show that a misconfiguration may significantly affect the performance of such systems. We then derive a performance model that provides key insights on the behaviour of HyperDex. Based on this model, we derive a technique to automatically and dynamically select the best HyperDex configuration.

@inproceedings{pr:icpads13,
author = {Paiva, Jo{\~a}o and Rodrigues, Lu{\'i}s},
title = {Policies for Efficient Data Replication in P2P Systems},
booktitle = {Proceedings of the 19th International Conference on Parallel and Distributed Systems},
series = {ICPADS '13},
year = {2013},
pages = {404--411},
numpages = {8},
location = {Seoul, Korea},
doi = {10.1109/.62},
publisher = {IEEE Computer Society},
address = {Washington, DC, USA},
}

This paper addresses the problem of maintaining replicated data in large scale P2P systems. Although this topic has been extensively studied in the literature, to maintain replicated data in this setting, in an efficient manner, still remains a significant challenge. This paper proposes novel policies to address this problem and evaluates their performance against different criteria, such as monitoring costs, data transfer costs, and load unbalance costs. We show that one of these new policies significantly outperforms previous work. Interestingly, this policy is based on a somehow counter-intuitive approach, that uses less reliable nodes to store the most accessed data items. The insights to derive this policy were obtained from an in depth analysis of existing solutions, that is also captured in the paper.

@inproceedings{plr:nca13,
author={Paiva, J. and Leitao, J. and Rodrigues, L.},
title={Rollerchain: A {DHT} for Efficient Replication},
booktitle={Proceedings of the 12th IEEE International Symposium on Network Computing and Applications},
series = {NCA'13},
year={2013},
month={Aug},
pages={17-24},
publisher = {IEEE Computer Society},
address = {Washington, DC, USA},
location = {Cambridge, MA USA},
}

In this paper we present Rollerchain, a novel Distributed Hash Table that offers efficient data storage through the combination of gossip-based and structured overlay networks. The unstructured component maintains clusters of fully connected nodes, where each cluster acts as a virtual node in the structured component. This architecture simplifies the management of data replication and balances the load among nodes in the system. We have implemented a prototype of Rollerchain that we have used to experimentally validated its performance against other state of the art solutions.

@inproceedings{prrl:icac13,
author = {Paiva, Jo{\~a}o and Ruivo, Pedro and Romano, Paolo and Rodrigues, Lu{\'i}s},
title = {{AutoPlacer: scalable self-tuning data placement in distributed key-value stores}},
address = {San Jose, CA, USA},
booktitle = {Proceedings of the 10th International Conference on Autonomic Computing},
series = {ICAC'13},
year = {2013},
publisher = {USENIX},
month = jun,
url = {http://www.usenix.org/conference/icac13/autoplacer-scalable-self-tuning-data-placement-distributed-key-value-stores}
}

This paper addresses the problem of autonomic data placement in replicated key-value stores. The goal is to automatically optimize replica placement in a way that leverages locality patterns in data accesses, such that inter-node communication is minimized. To do this efficiently is extremely challenging, as one needs not only to find lightweight and scalable ways to identify the right data placement, but also to preserve fast data lookup. The paper introduces new techniques that address each of the challenges above. The first challenge is addressed by optimizing, in a decentralized way, the placement of the objects generating most remote operations for each node. The second challenge is addressed by combining the usage of consistent hashing with a novel data structure, which provides efficient probabilistic data placement. These techniques have been integrated in Infinispan, a popular open-source key-value store. The performance results show that the throughput of the optimized system can be 6 times better than a baseline system employing the widely used static placement based on consistent hashing.

@inproceedings{aplr:ladis10,
author = {Alveirinho, Jo{\~a}o and Paiva, Jo{\~a}o and Leit{\~a}o, Jo{\~a}o and Rodrigues, Lu{\'i}s},
title = {Flexible and Efficient Resource Location in Large-Scale Systems},
address = {Zurich, Switzerland},
booktitle = {Proceedings of the 4th ACM SIGOPS International Workshop on Large-Sacle Distributed Systems and Middleware},
series =  {LADIS'10},
publisher = {ACM},
month = jul,
year = "2010"
}

Inherent to the cloud computing paradigm is the ability to adjust or deploy, on demand, services to face dynamic changes on the workload. Therefore, one needs an infrastructure to keep track of the resource allocation in the system and to efficiently locate the resources required to launch a new service, or re-dimension a running service. In this paper we propose a novel peer-to-peer architecture for efficient resource location, that avoid the bottlenecks of centralized or hierarchical directory services.

@inproceedings{alpr:inforum10,
author = {Alveirinho, Jo{\~a}o and Leit{\~a}o, Jo{\~a}o and Paiva, Jo{\~a}o and Rodrigues, Lu{\'i}s},
title = {Curiata: Uma arquitectura P2P auto-organizável para uma localização flex{\'i}vel e eficiente de recursos},
address = {Braga, Portugal},
booktitle = "Actas do segundo Simpósio de Informática",
series = {Inforum'10},
month = jul,
year = "2010"
}

@inproceedings{fpr:inforum14,
author = {Ferreira, Manuel and Paiva, Jo{\~a}o and Rodrigues, Lu{\'i}s},
title = {Suporte eficiente para pesquisas seletivas em MapReduce},
address = {Porto, Portugal},
booktitle = {Actas do Sexto Simpósio de Informática},
series =  {Inforum'14},
month = set,
year = "2014"
}

@inproceedings{doprr:inforum13,
author = {Diegues, Nuno and Orazov, Muhammet and Paiva, Jo{\~a}o and Rodrigues, Lu{\'i}s and Romano, Paolo},
title = {Auto-Configuração de Bases de dados NoSQL Multi-Dimensionais},
address = {Evora, Portugal},
booktitle = {Actas do Quinto Simpósio de Informática},
series =  {Inforum'13},
month = set,
year = "2013"
}

@masterthesis{joaopaiva2009,
author={João Gonçalves Paiva},
month={november},
note={The increasing volume of data being created combined with the current informatization of society is rising the need to efficiently protect data from loss or corruption. However, data backup is typically a costly and tedious process.
Thus, this need for data protection is enabling the development of high efficiency storage, particularly solutions to allow the efficient backup of data and its modification history through techniques to achieve single-instance storage of information. This set of techniques is known as deduplication, and exploits data similarity in order to achieve lower network and data storage use.
This document presents a backup system with support for efficient storage of multiple versions of data through a recent and more bandwidth-efficient deduplication technique. This system, known as BackupChunk, can detect redundancy across sites by exchanging only light metadata structures, thus achieving better backup performance than current solutions.},
organization={Instituto Superior Técnico},
title={BackupChunk - Chunk-Based Backup System},
year=2009,
}

The increasing volume of data being created combined with the current informatization of society is rising the need to efficiently protect data from loss or corruption. However, data backup is typically a costly and tedious process.

Thus, this need for data protection is enabling the development of high efficiency storage, particularly solutions to allow the efficient backup of data and its modification history through techniques to achieve single-instance storage of information. This set of techniques is known as deduplication, and exploits data similarity in order to achieve lower network and data storage use.

This document presents a backup system with support for efficient storage of multiple versions of data through a recent and more bandwidth-efficient deduplication technique. This system, known as BackupChunk, can detect redundancy across sites by exchanging only light metadata structures, thus achieving better backup performance than current solutions.