Scaling Problem In Fault-tolerant Distributed Storage Systems

Nowadays large-scale distributed storage systems store original data with redun-dant information to maintain data availability. There are two types of redundant mecha-nisms, i.e., replication and erasure coding. Since erasure codes incur much less storage overhead for the same fault-tolerance, they are receiving wider deployment in modern storage systems. On the other hand, the amount of digital data that needs to be stored continues to explode, storage systems have a continuous growing demand on storage capacity and I/O bandwidth. When foreground user-level applications require more for the storage capability and I/O performance, a storage system adds new storage devices and migrates part of the data into the new devices, and this operation is called storage system scaling. Hence, it is meaningful to study scaling for erasure coded distributed storage systems in the era of cloud storage and data centers. This dissertation studies scaling for erasure coded distributed storage systems mainly from three aspects, design a scaling algorithm, schedule the user I/O requests and system I/O requests in online scaling processes, optimize the post-scaling user access performance. Its main work and contributions are as follows.(1) Scaling for Cauchy Reed-Solomon (CRS)-Coded Distributed Storage Sys-temsSince modern storage systems require larger amount of fault-tolerance, it becomes more important to consider scaling for distributed storage systems with CRS codes which are resilient to a general number of failures. CRS codes are especially applicable to distributed storage systems composed of multiple storage nodes and the inter-connect network, and examples of such systems include CleverSafe, OceanStore. The scaling process involves migrating part of the data blocks into new storage nodes and modifying the parity blocks. The data migration and parity modification bring inevitably storage I/Os and network consumptions that directly affect the on-scaling system performance. This dissertation studies scaling for CRS-coded distributed storage systems. To mini-mize the I/O overhead, we propose a three-phase optimization scaling scheme for CRS codes. Specifically, we first design the post-scaling encoding matrix, and then design the on-scaling data migration process, and finally use parity blocks to decode several data blocks to further optimize the designed data migration process. Our scheme out-performs the basic scheme in that our scheme is capable of efficiently and gradually reducing the system I/Os and network transfers. We implement both our scheme and the basic scheme on a real distributed file system, and conduct extensive experiments to validate the efficiency of our scheme. Experimental results show that our scheme saves the scaling time of the basic scheme in both single-threaded and multi-threaded architectures.(2) Popularity-based Online ScalingIn real storage systems, most foreground user-level applications require the under-lying systems to supply 7x24 hours of online services. Thus, when storage systems per-form online scaling, the foreground user I/O requests and the underlying migration I/O requests compete for the available disk resources, and this competition inevitably de-grades the user and migration response time performance during scaling. However, the existing scaling approaches rarely consider the user I/O requests when they are initially designed, and when they are deployed in online environments, they result in degraded on-scaling user and migration response time performance. This dissertation addresses this challenge by designing an online scaling scheme, named popularity-based online scaling (POS), for existing scaling approaches. POS combines two prominent charac-teristics in real system user accesses, i.e., data popularity and data locality. POS divides the whole storage space into multiple zones and measures the popularity (mainly using the metric of access frequency) of each zone. Based on the measured popularity, POS varies the scaling sequences of different storage areas by first migrating the hot storage areas. Within each area, POS exploits data locality to better respond the user accesses. POS is orthogonal to existing scaling approaches and can be deployed atop them to im-prove the online scaling performance. In particular, we implement the existing RAID-0 scaling approach, FastScale, and POS atop FastScale on disksim. Through extensive trace-driven evaluations, we show that POS is capable of improving the online user and migration response time performance over FastScale notably.(3) Optimize Post-scaling User Read/Write PerformanceStorage system scaling must consider both the on-scaling performance and the post-scaling user read/write performance. On the one hand, if the amount of system I/Os during scaling is large, then the scaling window will be too long which impacts the on-scaling user and migration response time performance. On the other hand, s-torage systems must serve the regular user read/write operations after scaling, and so the post-scaling user access performance is also important. However, existing scaling approaches mainly consider to minimize on-scaling data migration without optimizing the post-scaling user read/write performance.Since the scaling process changes the data layout, the scaling process directly affect the regular user access performance after scaling. As such, this dissertation considers to design a new scaling scheme. We start from RAID-0 scaling, and propose a new scaling scheme, called PostScale. PostScale minimizes data migration during scaling, and guarantees the maximum dispersal distribution of logically sequential data block- s after scaling. By doing this, PostScale shortens the scaling window, and meanwhile provides maximum parallel I/O accesses for user read/write requests after scaling. Sim-ulations show that PostScale has advantages over the two conventional RAID-0 scaling approaches, i.e., round-robin and FastScale. To be more specific, PostScale greatly shortens the scaling window over round-robin, and improves the post-scaling user ac-cess time performance over FastScale. PostScale can be further extended to be applied to RAID-5 scaling, Reed-Solomon-based distributed storage system scaling to enhance the post-scaling user access performance.