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: generating replication requests for objects in a distributed storage system based at least in part on replication policies for the objects and a current state of the distributed storage system, wherein a respective replication request for a respective object instructs a respective instance of the distributed storage system to replicate the respective object so as to at least partially satisfy a replication policy for the respective object, wherein a respective replication policy includes criteria specifying at least storage device types on which replicas of object are to be stored; partitioning the replication requests into groups of respective replication requests corresponding to respective instances of the distributed storage system at which the respective replication requests are to be performed; and for a respective group of respective replication requests, determining a respective subset of replication requests for the respective group of respective replication requests that can be completed within a predetermined time interval; and distributing the respective subset of replication requests for the respective group of respective replication requests to the respective instance of the distributed storage system corresponding to the respective group of respective replication requests for execution.