1. A computer-implemented method for providing cost-effective and durable archival data storage service, comprising: under the control of one or more computer systems of an archival data storage system that are configured with executable instructions, receiving, over a network from a requestor system, a storage request to store a data object into the archival data storage system; causing storage of the data object in the archival data storage system; providing a data object identifier associated with data object; receiving, in connection with a retrieval request to retrieve the data object, the data object identifier; creating a retrieval job corresponding to the retrieval request; adding the retrieval job to a collection of pending jobs; processing, in one or more batches, the collection of pending jobs; and providing the retrieved data object.