Themis: Finding Imbalance Failures in Distributed File Systems via a Load Variance Model

A distributed file system (DFS) is a file system that spans across multiple file servers or multiple locations. The load balancing mechanism in a DFS is crucial, as it optimizes resource utilization across all nodes and improves response times. However, incorrect load scheduling or implementation errors in load balancing algorithms can lead to system imbalance, hang-ups, and even crashes. Such imbalance failures may be critical and pose a significant threat to the availability and security of distributed file systems. This paper presents a detailed study of real-world imbalance failures in four widely used DFSes, exploring their symptoms and triggering conditions. We found that test cases that incorporate both client requests and system configuration inputs are crucial for exposing these imbalances. However, generating such high-quality test cases is challenging due to the extensive combinations of these two input spaces. Guided by our study, we designed a testing framework named Themis. To efficiently prune the search space, Themis first models both the request and configuration inputs and transforms them into operation sequences. It then employs load variance-guided fuzzing to thoroughly explore the operation sequence and constantly generate test cases that make nodes loaded as differently as possible. Finally, Themis introduces a load detector to monitor the resource usage of each distributed node and precisely identify any imbalances. Themis has detected 10 new imbalance failures in four real-world DFSes, which have been addressed by the respective maintainers.