{en_GB= Fine Grained Transaction Scheduling In Replicated Databases Via Symbolic Execution} {} EVALUATED

Detalhes: {pt=Atualmente, a maioria dos serviços disponíveis na Internet dependem de base de dados para armazenar a sua informação. Estes serviços tendem a ter fortes requisitos de escalabilidade, disponibilidade e tolerância a faltas, o que requer com que sejam desenvolvidas técnicas eficientes de replicação de base de dados. No entanto, nestes sistemas a replicação introduz custos não negligenciáveis para garantir que o estado das replicas é mantido devidamente sincronizado. Uma abordagem clássica, é a State Machine Replication (SMR), que é uma técnica usada para implementar soluções tolerantes a faltas. SMR tem algumas limitações no que conta ao paralelismo, pois requer que a execução seja determinística. Para resolver estas limitações, as soluções do estado da arte dependem que os acessos a ser feitos sejam determinados automaticamente ou pelos programadores. O último caso, não é perfeito pois identificar os acessos de transações complexas não é trivial e no primeiro caso ou os acessos determinados não são precisos ou é feito uma suposição otimista que aumenta a probabilidade de ocorrerem abortes. Isto tem um impacto no grau de paralelismo e no desempenho geral do sistema. Esta tese resolve as limitações destas soluções usando a Execução Simbólica para determinar a priori e com precisão os acessos que as transações realizam. Com isto tornaremos o processo de escalonamento mais eficiente. A nossa abordagem Symbolic-SMR, foi avaliada usando uma micro-benchmark e usando a benchmark TPC-C . Nestas experiências, a Symbolic -SMR superou o desempenho das soluções do estado da arte em 2 a 5 vezes., en=Nowadays, most modern Internet services make large use of databases to store relevant data. These services tend to have strong scalability, high availability and fault tolerance requirements that create a strong urge for designing highly efficient database replication techniques. However, in environments, such as database systems, that offer strong consistency guarantees, replication introduces non-negligible costs in order to ensure that the state maintained by the various replicas is properly synchronized. A typical approach is State Machine Replication (SMR), which is a technique to implement fault-tolerant solutions. SMR has limitations when it comes to parallelism because it requires deterministic execution. However, to solve these limitations, state of the art solutions rely either on automatic prediction or programmer input about the set of data items to be accessed. The latter is not optimal since complex workloads exhibit non-trivial storage accesses which are hard to predict while the former either relies on coarse-grained prediction or on an optimistic guess that increases the probability of aborts in case of misprediction. This impacts the solution parallelism degree as well as the overall system throughput, respectively. This thesis addresses the aforementioned limitations, by the use of Symbolic Execution to determine a fine-grained a priori knowledge of the transactions' conflict classes to improve the efficiency of the scheduling process. To evaluate Symb-SMR, we used a micro-benchmark and the TPC-C benchmark. In these experiments, our solution achieved a throughput 2 to 5 times higher than current state of the art solutions.}

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

Publicação

Obra sujeita a Direitos de Autor

Orientação

AUTOR

Miguel Cândido Viegas (ist176532)

ORIENTADOR

Paolo Romano

Departamento de Engenharia Informática (DEI)

Professor Associado

ORIENTADOR

Miguel Ângelo Marques de Matos

Departamento de Engenharia Informática (DEI)

Professor Auxiliar