Dependability and caching enhancements in distributed systems

Abstract

The enormous amountof information is being usedin regular activities henceit is important to store and analyzesuch data.This gives the figment that this data is arranged locally on the client's PC. As a general rule, the Internet speaks ofa gigantic distributed system that appears as a single resource to the user. Adistributed system is an accumulation of autonomous computers connected by communication channels that appears to its clients as a single coherent system.Distributed systems should befault tolerant, scalable and highly available.Hadoop is a popular framework with a distributed file system used to store data. It providesfast, reliable and transparent access of data to a large number of heterogeneous and geographically distributed users.The major challengesin large scale distributed systems include availability, scalability, reliability, caching, opennessandtransparency.This thesis proposes approaches to enhance availability, reliability and caching in a distributed system.Reliability is the probability of a system functioning correctly overa given period of time.In a good distributed file system, the probability of loss of stored data should be minimized. Caching improves data access speed by storing the recently used information in main memory.The main goal of this research work is to improve the performance of the Hadoop Distributed File System. The objectives of the research work include minimizingthe loss of stored data using erasure codes, improvingthe data access speed by maintainingthe recently accessed information in an associative cachewith Least Unified Value eviction policyand enhancing the viavailability of NameNode using a ImprovedElection Algorithm and maintaining metadata in multiple locations.This research proposes an approach to improvereliability of data on the Hadoop file system through Tornado, Turbo and Reed Solomon Codes. In Hadoop, data aresplit into blocks that are distributed in the cluster. To maintain reliability, blocks are replicated. NameNode maintains metadata about the size and location of blocks and their replicas. Erasure codes create checksum blocks from data blocks that make up the file. The existing file system uses Low Density Parity-Check (LDPC) codes for detection and correction of errors. LDPC error correction is restricted to the minimumnumber of error bits. This research proposes the usage of Tornado codes to detect and correct multiple bit errors in a storage system.Tornado codes are simple to implement usingXOR operation. Turbocodes are more accurate and fast forencoding/decoding and for correcting multipleerrors. Therefore, Turbo codes are highly desirablefor storage and retrieval of data for large clusters.ReedSolomon codes are block-based error correcting codesconsisting oftwo parts, namelydata part and parity part.The encoding process adds the parity symbols to message block. ReedSolomon codes can be described as an 𝑠1′,𝑝1′code, where 𝑠1′is the block length in symbols and 𝑝1′is the number of information symbols in the message. There are 𝑠1′−𝑝1′parity symbols whichare calculated based on the data part. This research compares the performance of LDPC with the proposed approach, namely Tornado, Turbo and Reed-Solomon codes for block storage in HDFS. Encoding speed of Reed Solomon codes is faster by 10%, 15% and 30% when compared to that of Tornado, Turbo and LDPC codes respectively. viiThe second objective of the research work is to improve access speed of information using Associativecaching withLeast Unified Value (LUV)replacement policy. It works based on the object value which is calculated from past reference history of the data item.The proposed replacement policy LUV on associative caching reduces file access time from 10% to 15% for a single node cluster and 15% to 30% for a multi node cluster.The third objective of the research work is to improve availability of NameNode using anImprovedElection Algorithm.The ImprovedElection Algorithm electsa new NameNode whenthe primary NameNode goes down.The election procedure is time efficient and involves less message passing between nodes.The speed of read/write operations increases from 6 to 8 times by using Namespace Partition Table (NPT) in NameNodes when compared to Local File System (LFS).The proposed reliability, availability and caching mechanism have been tested on a Digital Library Service (DLS) application. Experimental results show that the proposed algorithms improve the overall quality ofservice on the Hadoop Distributed File System.To summarize (i) Encoding speed of Reed Solomoncodes is faster by 10%, 15% and 30% and decoding of Reed Solomon codes is faster by 10%, 15% and 40% when compared to that of Turbo, Tornado and LDPC respectively. (ii) The proposed LUV replacement policy on associative caching reduces file fetching time by 10% to 15% for a single node cluster and 15% to 30% for a multi node cluster and (iii) The performance of the read/write operations in improvedelection algorithm toelect a new coordinator (NameNode) whenthe primary NameNode fails,improves by 6 to 8 times as the Namespace Partition Table (NPT) is maintained in multiple NameNodes when compared to searching data in single NameNode. viiiEffective adaptive algorithms canbe developed to adjust configuration of replication process including metadata buffer size.LUV replacement policy and erasure codes can be used in cloud to enable efficient and reliable data access.Erasure codes can be applied for cloud storage to maintain data in a reliable manner.