Multi-version Storage: Code Design and Repair in Distributed Storage Systems

With the rapid growth of data volume, data storage has attracted more and more researchinterests in recent years. Distributed storage systems play important roles ofmeeting the demand for data storage in large amounts. That is, data are stored bymultiple storage nodes which are connected together with various network topologies.The main merits of such distributed storage are faster response, higher reliability andbetter scalability. However, due to network failure, link outage or bu↵er overflow, theupdated data might not be received by all storage nodes, resulting in the coexistenceof multiple versions of the file in the system. Thus, the major challenge is consistency,which means that the latest version of the file is accessible to any read request. We aimto study multi-version storage and code design in distributed storage systems, where thelatest version of the file or a version close to the latest version is recoverable. Moreover,compared to previous studies, higher availability can be achieved in our system model,namely, at least one version of the file can be obtained.On the other hand, both storage nodes and links are vulnerable to fail in storage systems.For the sake of reliability demand, the lost data is supposed to be reconstructed.In this thesis, additional storage nodes dedicated to repair (DR storage nodes) are introducedin the repair process. The results show that optimal repair bandwidth withminimal additional storage space can be achieved by introducing a certain number ofDR storage nodes. Subsequently, linear combinations are provided to reduce the communicationcost of repair where the link cost is high. Last but not the least, we showthat the cooperation among surviving nodes and DR storage nodes suffices to completethe repair process successfully even with link failure.Med tanke på den snabbt växande volymen av data, har intresset för forskning på datalagring vuxit under de senaste åren. Distribuerade lagringssystem spelar en viktig rolli att möta behovet av stora volymer av lagring. Distribuerade lagringssystem är alltsånär data är sparad på flera noder som är sammankopplade på olika sätt i ett nätverk.Jämfört med traditionella lokala lagringar, har distribuerad lagring fördelen att den harkortare svarstider, högre tillförlitlighet och bättre skalbarhet. Men om nätverket gårner, det blir ett länkavbrott eller maxkapaciteten i en buffert nås, kan det hända attall uppdatering inte når ut till alla noder, vilket resulterar i att flera olika versioner aven fil finns sparande samtidigt i systemet. Därför är en av utmaningarna är att varakonsekvent, att det alltid är den senaste versionen av en fil finns tillgänglig för allavid varje given tidpunkt. Målet med detta arbete är att studera flerversionslagrade fileroch hur programmeringsdesignen för distribuerade lagringssystem ser ut. Med andraord, finns det flera versioner av en fil, ska alla kunna återskapas. Jämfört med tidigarestudier, har vi med vårt system uppnått högre tillgänglighet, nämligen att en klient harfått tag i alla fall en version av en fil.Ett vanligt förkommande problem i det distribuerade lagringssystemen är fel i nodernaoch då ska en ny nod skapas för att öka behovet av tillit. I detta projekt, extralagringsnoder för reparation (DR lagringsnoder) är introducerade i reparationsprocessen.Resultatet visar att den optimala reparationsbandbredden med minimalt extra lagringsutrymmekan uppnås genom att introducera en specifikt antal DR lagringsnoder.Efter det, linjärkombinationer är framtagna för att reducera kostnaden att reparera därlänkkostnaden är hög. Sist men inte minst har vi kunnat påvisa att samarbete medandra fortfarande uppkopplade noder och med DR lagringsnoderna räcker för att utföraen lyckad reparationsprocess, även med länkavbrott