1. A computer-implemented method for generating replication requests for objects in a distributed storage system, comprising: at a computer system including one or more processors and memory storing one or more programs for execution by the one or more processors: storing a plurality of objects in the distributed storage system, wherein each object has an associated replication policy that specifies a desired number of replicas of the respective object and specifies desired storage device types on which the replicas of the respective object are to be stored; identifying a plurality of objects in the distributed storage system whose associated replication policies have not been satisfied; ranking replication requests for the objects whose replication policies have not been satisfied based on respective numbers of replicas of the respective objects that need to be created in order to satisfy the replication policies for the objects; and generating replication requests for the identified plurality of objects based on the associated replication policies for the objects that have not been satisfied and on a current state of the distributed storage system, wherein each respective replication request for a respective object instructs a respective instance of the distributed storage system to replicate the respective object so as to better satisfy the respective replication policy associated with the respective object; and distributing at least a subset of the replication requests for the objects in the distributed storage system to respective instances of the distributed storage system corresponding to the replication requests, for execution at the respective instances.