Concurrent data structures

Abstract

The existence of items that are accessed and modified with high frequency in database management sys tems is a big obstacle to obtaining good performance. As such, it becomes more relevant to find methods allowing operations to execute efficiently and concurrently in order to increase application performance. Some concurrent approaches which can also deal with high concurrency, such as phase reconciliation [Narula et al., 2014] or CRDTs [Preguiça, 2018] already have a variety of data structures which can make use of these approaches. However, they are either not suitable for distributed systems or not designed for relational databases. This project aims to create a library of data structures able to withstand high concurrency through partition and randomness, as proposed for MRVs [Faria and Pereira, 2023] and suitable for distributed systems, but offering a more diverse range of structures to support different applications. This proposal is then evaluated with an implementation in an SQL database, which shows that this method brings an increase in performance, especially when contention is higher.

A existência de itens que são acedidos e modificados com grande frequência em sistemas de gestão de dados é um obstáculo significativo à obtenção de elevado desempenho. Assim, torna-se cada vez mais relevante encontrar métodos de lidar com a execução simultânea de operações que manipulam dados de forma eficiente, proporcionando às aplicações melhores tempos de resposta. No entanto, as abordagens existentes, como Phase Reconciliation [Narula et al., 2014] ou CRDTs [Preguiça, 2018], têm pressupostos estritos sobre a concorrência ou não foram desenhados para ser utilizadas em bases de dados relacionais. Este trabalho tem como objetivo a construção de uma biblioteca de estruturas de dados que toleram elevada concorrência através da partição e aleatoriedade, tal como proposto para os MRVs [Faria and Pereira, 2023] e adequado a sistemas distribuídos, mas oferecendo uma gama de estruturas mais diversa, para suportar diferentes aplicações. Esta proposta é avaliada com uma implementação em sistemas de bases de dados SQL que demonstra um aumento de desempenho, particularmente quando existe maior contenção.