Esta memoria describe el diseño y desarrollo de un nuevo motor de bases de datos NoSQL distribuido, que hemos llamado Treeless, diseñado y desarrollado por el autor de este trabajo. Este motor tiene como objetivos principales la eficiencia, disponibilidad, escalabilidad y simplicidad. Se ha desarrollado un sistema NoSQL de tipo clave-valor dado que esta clase de sistemas encaja adecuadamente con los requisitos. Dichos requisitos son el fruto de la utilización de nuevas tecnologías como el Big Data y la computación en la nube, y han desplazado a otros requisitos como la consistencia de la información. Para el desarrollo de este trabajo se ha estudiado detalladamente el documento Dynamo: Amazon’s Highly Available Key-value Store. En él se describen las principales técnicas y motivaciones inherentes al motor Dynamo, un motor de BDs de tipo llave-valor con alta disponibilidad. Para el desarrollo de Treeless se ha seguido el modelo de consistencia eventual, con la política Last Writer Wins. Muchas de las técnicas usadas en Treeless difieren de las usadas en Dynamo, pues se han tratado de simplificar algunos mecanismos como el método de reparación asíncrona, entre otros. En esta memoria se analizan las diferencias, ventajas y desventajas de cada uno de ellos. Las principales funcionalidades implementadas en Treeless son: particionado estático basado en funciones hash, rebalanceo automático del sistema, mecanismos de reparación (read-repair y reparación asíncrona), protocolo de heartbeat tipo gossip basado en resúmenes, buffering y operaciones CAS. Se han desarrollado dos algoritmos novedosos, que se describen en esta memoria. El primero trata la coordinación necesaria en la realización de operaciones CAS en un entorno distribuido. El algoritmo no es tolerante a particiones de red, generando resultados incorrectos cuando ocurre esta situación, pero sí es tolerante a fallos permanentes en los nodos. La implementación del algoritmo ha sido validada mediante tests. El segundo es una extensión a las sumas de verificación (checksums), que permite determinar si dos o más réplicas están suficientemente sincronizadas. El concepto de sincronización suficiente, así como el algoritmo creado para tal efecto, se introducirán en el apartado 4.3.1.3. Los resultados han sido satisfactorios, especialmente en cuanto a rendimiento. En este aspecto se han alcanzado valores similares a los obtenidos por Redis.

This Bachelor Thesis describes the development of a new NoSQL database management system, so-called Treeless. The engine targets efficiency, availability, scalability and simplicity. These requirements, products of the Big Data and the Cloud Computing, induce the usage of a key-value system. The previous work Dynamo: Amazon’s Highly Available Key-value Store has been very useful in the analysis, design and development of Treeless. Dynamo developers describe in this paper most techniques and motivations behind its DB engine, a high availability key-value store. We followed the eventual consistency model with the Last Writer Wins policy. However, most techniques present in Treeless differ from the ones used in Dynamo, we have made several simplifications. The advantages and disadvantages of these differences will be analyzed. The fundamental implemented techniques are: static partitioning based on hashing, automatic rebalance, repairing techniques (read-repair and asynchronous repair), gossip protocol based on digests, buffering and CAS (Compare And Swap) operations. Two novel algorithms are proposed. The first one is used to coordinate the system in CAS operations. The algorithm is not partition tolerant. However, it tolerates permanent node failures. The algorithm implementation has been tested. The second one is an extension of checksums that allows us to determine if two or more replicas are synchronized enough. This concept, the algorithm and the implementation are discussed in section 4.3.1.3. We have achieved positive results, especially in the performance section, with similar throughputs to those of mature NoSQL systems like Redis.