Optimizing distributed storage in cloud environments

Cloud storage, in the context of this research, is defined to be the abstraction of storage spanning multiple machines into a single storage pool that end-users can access without knowing the internal details of where or how the storage is maintained. Traditionally, cloud storage is used to refer to the storage pool in data centers. In our work, in addition to data center based cloud storage, we also consider a vehicular network based cloud storage—storage obtained by pooling together the storage on vehicles, typically connected by a vehicular network. In this thesis, we optimize the distributed storage in these two cloud environments. Specifically, we identify two challenges each in the two cloud environments and propose solutions to these challenges. In Chapter 3, we consider the first important challenge in the vehicular cloud, namely the high latencies of on-demand content access. We investigate the benefits of using erasure codes in reducing the content access latencies through both analysis and realistic trace-based simulations. We show that a key parameter affecting the file download latency is the ratio of file size to download bandwidth. When this ratio is small so that a file can be communicated in a single encounter, we find that coding techniques offer very little benefit over simple file replication. However, we analytically show that for large ratios, for a memoryless contact model, distributed erasure coding yields a latency benefit of N/α over uncoded replication, where N is the number of vehicles and α the redundancy factor. In Chapter 4, we consider the second challenge, namely the problem of helper node allocation. In order to relay a file from a node that has the file to another that wants the file, it may be necessary to enlist the help of other relaying nodes. When there are multiple types of files, an existing pool of helper nodes cannot help the dissemination of all the files due to storage and bandwidth constraints. In the chapter, we formulate and address mathematically this fundamental problem of resource allocation in the form of helper nodes in disseminating multiple contents. In the second half of the thesis, the data center cloud is considered. In Chapter 5 we investigate how to optimize the repair traffic in data centers, while keeping the storage overhead as low as possible. Node failures are frequent in data centers and when repairing failed nodes, network traffic is used (which is called repair traffic). Replication has the lowest possible repair traffic; however, replication has large storage overhead. The storage overhead can be reduced by using Reed Solomon codes, but they generate significantly more repair traffic than replication. We implement in Hadoop HDFS a new class of erasure codes called Locally Repairable Codes (LRCs) that can reduce the repair traffic by approximately 2x as compared to Reed Solomon Codes, while only requiring 14% more storage (for our particular implementation). The last challenge we consider is the problem of placement of blocks in a data center. When placing replicas or erasure encoded blocks in a data center, the common approach is to place them on separate racks. While this can help reduce the probability of permanent data loss, it creates cross-rack traffic when repairing failed nodes. This can slow down repair, thereby affecting reliability. In Chapter 6, we identify a tradeoff between fault tolerance and repair speed when placing data in a data center and capture this tradeoff into a single metric called Mean Time To Data Loss (MTTDL). We use this metric to determine how to store blocks to maximize reliability. (Abstract shortened by UMI.)