Storage object deletion job management

A method, comprising:

• implementing a network-accessible multi-tenant storage service for storage objects owned by a plurality of clients;
• identifying a set of storage objects of the storage service to be deleted;
• storing, within the storage service, a plurality of deletion job objects, wherein each deletion job object of the plurality of deletion job objects comprises an indication of a subset of the set of storage objects;
• determining, based at least in part on a job validity criterion, whether one or more deletion operations corresponding to a particular deletion job object of the plurality of deletion job objects are to be scheduled, wherein the job validity criterion includes an indication of an expiration period for the particular deletion job object;
• in response to determining that the one or more deletion operations are to be scheduled, initiating a respective at least one deletion operation for at least one storage object indicated in the particular deletion job object;
• and
• in response to determining that one or more deletion operations for another deletion job object are not to be scheduled, initiating removal of the other deletion job object to avoid scheduling redundant deletion job objects that indicate one or more same storage objects that are to be deleted in accordance with the object retention policy.

A non-transitory computer-accessible storage medium storing program instructions that when executed on one or more processors:

• identify, during a particular deletion execution iteration, a particular deletion job object of a plurality of deletion job objects stored in a multi-tenant storage service, wherein the particular deletion job object indicates a collection of storage objects that are eligible for deletion from the storage service in accordance with one or more deletion criteria;
• determine, based at least in part on a job validity criterion, whether one or more deletion operations corresponding to the particular deletion job object of the plurality of deletion job objects are to be scheduled, wherein the job validity criterion includes an indication of an expiration period for the particular deletion job object;
• in response to a determination that the one or more deletion operations are to be scheduled, initiate a respective at least one deletion operation for at least one storage object indicated in the particular deletion job object;
• and
• in response to a determination that the one or more deletion operations are not to be scheduled, initiate removal of the particular deletion job object to avoid scheduling redundant deletion job objects that indicate one or more same storage objects that are to be deleted in accordance with the object retention policy.