An Efficient Hierarchical Object Placement Algorithm for Object Storage Systems

With the prevalence of object-based storage systems, one of the big challenges in such systems is how to design an effective object placement algorithm which can locate object in constant time, distribute data evenly among object-based devices and adapt well to the changes of devices. A majority of proposed approaches are appropriate for single level mode, while the multi-level approaches cannot locate object in constant time and have bad adaptability. This paper presents a novel hierarchy object placement algorithm to distribute several petabytes of objects among tens or hundreds of thousands of devices. Specially, it uses Max-Min algorithm to classify the devices into some classes for different devices configuration. Then, we propose EFAH hashing algorithm to assign data between classes and within a class. The theoretical analysis and experimental study show that this new hierarchy object placement can locate data in constant time to reduce the computation overhead of metadata server and avoid the performance bottleneck. Moreover, it can distribute objects evenly among devices to balance I/O load. In the event of devices changes, our approach can redistribute fewer objects to preserve even distribution so that the performance of systems would not be affected in the process of rebalancing I/O load.