1Analysis of Erasure Coding in a Peer to PeerBackup SystemGeorge Nychis, Argyro Andreou, Deepti Chheda, and Alexander GiamasInformation Networking InstituteCarnegie Mellon University{gnychis,aandreou,dchheda,agiamas}@andrew.cmu.eduAbstract—The peer to peer architecture model is widely usedtoday for distributed systems deployment, which is increasinglybecoming used as a model for disk back up systems. Currently,popular peer to peer back up systems use replication to ensuredata redundancy, imposing a significant burden on system re-sources such as storage. Could the technique of erasure codingconstitute a more suitable data redundancy scheme for suchsystems? In this paper we explore the prospect of deployingerasure coding in a peer to peer back up system and analyze howit performs against replication. Erasure coding and replicationare compared in terms of CPU and network utilization, storageoverhead, fault tolerance, end to end delay, and scalability. Inaddition to the performance analysis we also determine theturning point between erasure coding and replication with regardto peer availability. We provide suggestions for erasure codingparameters with respect to peer availability and file size basedon this analysis.I. INTRODUCTIONThe growing need of computational power, storage, andcommunication bandwidth in personal computing has led todecentralized peer to peer system implementations. These sys-tems do not include dedicated servers for providing services,instead they include a number of personal computers operatingin a cooperative manner to provide higher levels of quality ofservice, magnitudes greater computational power, disk space,and use of network resources.The trend of peer to peer system deployment is alsoaffecting disk backup systems. The primary goal of a diskbackup system is to provide storage of data, ensuring that inthe event of software failure, hardware failures, or even naturaldisaster, the data will still be recoverable. Traditional backupsystems use centralized servers to provide mass storage fordata that needs extra levels of redundancy, using the client-server architecture. However, backup system implementationsare beginning to use the peer to peer architecture which caneliminate single points of failure to provide a greater level offault tolerance, while increasing storage capacity and drivingdown costs.Peer to peer disk backup systems can use replication tohandle events of peer failures. Each backup in this scenario isreplicated across the peers ensuring that even if only one peeris connected, the file will still be retrievable. Even thoughthis failure handling scheme provides a high probability ofretrieving files under severe peer failure conditions, it imposeslarge storage and network overhead. Current research hasprovided alternative failure handling methods that balancestorage and network overhead with a higher level of faulttolerance under peer failure conditions.In this paper we study the use of erasure coding as analternative failure handling scheme to replication. Our aimis to determine whether the former would constitute a morebalanced solution in terms of file retrieval capability under peerfailure condition, network bandwidth, and storage overheadthan the latter. To achieve this we began our implementationusing HiSpread, an open source peer to peer backup system,and incorporated the PASIS[9] project’s erasure coding libraryprovided by the Parallel Data Lab at Carnegie Mellon Univer-sity. For performance analysis of our experiments we used theEmulab[7] testbed located at the University of Utah.The paper is organized as follows. In Section 2 we provideintroductory information concerning erasure coding along withan example so that the concept is fully understood by thereader. In Section 3 we discuss related research to our topic.In Section 4 we provide a thorough description of how weincorporated the PASIS erasure coding library in HiSpread,referencing all of the challenges and problems we faced. InSection 5 we describe our experimental setup on Emulab,how we approached the issue what experiments should beperformed, and how they should be performed. In Section 6we provide a thorough analysis of the data we collected duringour experiments concerning CPU, disk, throughput, as well asother metrics, with comparisons between erasure coding andreplication. In Section 7 we provide insight on our future goalsregarding this project, and lastly in Section 8 we conclude thepaper.II. ERASURE CODINGErasure codes are characterized by their ability to provideredundancy, and hence failure resistance, without the overheadof strict replication. Erasure coding divides a block into mfragments and then produce n redundant fragments, where n >m. A key property of erasure coding is that for reconstructionof the block, only m fragments are needed out of the n totalfragments that resulted from the erasure coding procedure.This constitutes an erasure coding scheme of m of n.For example, the erasure coding scheme 5 of 8 would meanthat a block is first divided into 5 fragments and from theseblocks, an additional 2 fragments (n - m) are created. Any 5out of the 8 fragments that resulted out of the erasure codingprocedure would be sufficient to reconstruct the original block.2FileBlock BlockBlock.......m fragmentsErasureCodingoriginal m fragments+n-m additional fragments....Fig. 1. Erasure coding exampleFigure 1 depicts how erasure coding is applied to a file toproduce n total fragments for a given block.In our peer to peer backup system using erasure coding, wedivide the file to be backed up into a series of blocks. Thenwe apply erasure coding on each of these blocks to producethe additional redundant fragments per block. For instance, ifwe are applying the erasure coding scheme 3 of 5, each of thefile blocks are divided into 3 data fragments (m). These datafragments are then used to produce 2 additional redundantfragments (n-m), for a total of 5 fragments (n). To recovereach of the blocks we only need to have any 3 out of the 5fragments.It can be concluded from the above information that repli-cation is a corner case of erasure coding where m is alwaysequal to 1. RAID systems are also a case of erasure codes. Forinstance RAID levels 1 and 4 can be described by 1/2 and 4/5erasure code schemes respectively. More detailed informationabout erasure coding can be found in [2].III. RELATED WORKComparing how erasure coding can provide a more robustsolution in terms of efficient