A computer system comprising: one or more processors; and one or more computer-readable storage media having stored thereon computer-executable instructions that, when executed by the one or more processors, cause the computer system to schedule garbage collection in a distributed environment that includes a plurality of partitions that point to a plurality of data blocks that store data objects, the garbage collection scheduling being based on a cost to reclaim one or more of the data blocks for further use, the computer-executable instructions including instructions that, when executed by the one or more processors, cause the computer system to perform at least the following: determining a reclaim cost (261; 704) for one or more data blocks of one or more of the plurality of partitions during a garbage collection operation; determining a byte constant multiplier (531; 701) that is configured to modify the reclaim cost to account for the amount of data objects that may be rewritten during the garbage collection operation; accessing one or more of a baseline reclaim budget (551; 702) and a baseline rewrite budget (552; 703), the baseline reclaim budget specifying an acceptable amount of data blocks that should be reclaimed by the garbage collection operation and the baseline rewrite budget specifying an upper limit on the amount of data objects that may be rewritten during the garbage collection operation; iteratively varying one or more of the baseline reclaim budget, the baseline rewrite budget, and byte constant multiplier to determine an effect on the reclaim cost; and generating a schedule for garbage collection, the schedule including those data blocks that at least partially minimize the reclaim cost based on the iterative varying. one or more processors; and one or more computer-readable storage media having stored thereon computer-executable instructions that, when executed by the one or more processors, cause the computer system to schedule garbage collection in a distributed environment that includes a plurality of partitions that point to a plurality of data blocks that store data objects, the garbage collection scheduling being based on a cost to reclaim one or more of the data blocks for further use, the computer-executable instructions including instructions that, when executed by the one or more processors, cause the computer system to perform at least the following: determining a reclaim cost (261; 704) for one or more data blocks of one or more of the plurality of partitions during a garbage collection operation; determining a byte constant multiplier (531; 701) that is configured to modify the reclaim cost to account for the amount of data objects that may be rewritten during the garbage collection operation; accessing one or more of a baseline reclaim budget (551; 702) and a baseline rewrite budget (552; 703), the baseline reclaim budget specifying an acceptable amount of data blocks that should be reclaimed by the garbage collection operation and the baseline rewrite budget specifying an upper limit on the amount of data objects that may be rewritten during the garbage collection operation; iteratively varying one or more of the baseline reclaim budget, the baseline rewrite budget, and byte constant multiplier to determine an effect on the reclaim cost; and generating a schedule for garbage collection, the schedule including those data blocks that at least partially minimize the reclaim cost based on the iterative varying. determining a reclaim cost (261; 704) for one or more data blocks of one or more of the plurality of partitions during a garbage collection operation; determining a byte constant multiplier (531; 701) that is configured to modify the reclaim cost to account for the amount of data objects that may be rewritten during the garbage collection operation; accessing one or more of a baseline reclaim budget (551; 702) and a baseline rewrite budget (552; 703), the baseline reclaim budget specifying an acceptable amount of data blocks that should be reclaimed by the garbage collection operation and the baseline rewrite budget specifying an upper limit on the amount of data objects that may be rewritten during the garbage collection operation; iteratively varying one or more of the baseline reclaim budget, the baseline rewrite budget, and byte constant multiplier to determine an effect on the reclaim cost; and generating a schedule for garbage collection, the schedule including those data blocks that at least partially minimize the reclaim cost based on the iterative varying.