Availability of multi-object operations

Highly-available distributed storage systems are commonly designed to optimize the availability of individual data objects, despite the fact that user level tasks typically request multiple objects. In this paper, we show that the assignment of object replicas (or fragments, in the case of erasure coding) to machines plays a dramatic role in the availability of such multi-object operations, without affecting the availability of individual objects. For example, for the TPCH benchmark under real-world failures, we observe differences of up to four nines between popular assignments used in existing systems. Experiments using our wide-area storage system prototype, MOAT, on the PlanetLab, as well as extensive simulations, show which assignments lead to the highest availability for a given setting.