A method of allocating storage in a distributed storage system includes receiving a data structure including a plurality of identifiers of storage devices organized by failure zones. Any device of a first failure zone does not share a point of failure with any device of a second failure zone. The method also includes receiving a storage allocation request, identifying a first storage device using a first pointer referencing an unallocated device of the first failure zone, and modifying the first pointer to reference a next unallocated device of the second failure zone. The method also includes identifying a second storage device using a second pointer referencing an unallocated device of the second failure zone, modifying the second pointer to reference a next unallocated device of the second failure zone, and responding to the storage allocation request by providing identifiers of the first storage device and the second storage device.