A scaleable and distributed B-tree with parallel out-of-order traversal

Abstract

In today's data driven community, the demand for larger storage and faster retrieval is ever increasing. The most common solution is the use of very large and expensive storage devices which are limited in scalability and processing power. Cheap high-speed networks give the possibility of distributed systems that can be used to provide collective storage and computational power from individual commodity hardware . Making use of these platforms for storing large data sets is a non-trivial task due to potential inconsistencies in the data structures, addressing issues, excessive redundant information and load balancing. In this dissertation we propose a system that takes advantage of multiple computers to store data. A B-tree is used in a distributed fashion providing fast access to the data. The proposed design utilises a replication scheme which increases the space and computational efficiency of the data structure, makes use of minimal network communication and sustains scalability. This is achieved through several techniques, such as lazy updates and path replication. Our data structure also provides high availability and consistency of the indices through several types of locks. Concurrent TCP/IP requests are also balanced between the processors of the system. This system also provides out-of-order traversal allowing all servers in the system to execute a concurrent linear search. We show that the number of hops to find a particular record in the distributed tree is in the worst case equal to the depth of the tree.