The disclosed embodiments relate to a data storage system that facilitates efficiently recovering from storage device failures. Upon receiving a request to retrieve a data block from the data storage system, the system uses a hash that identifies the data block to look up a bucket and an associated cell containing the data block. Note that the bucket aggregates a large number of data blocks and is located in the associated cell that comprises a set of object storage devices (OSDs). Within the cell, the system uses the bucket to look up an OSD that contains the bucket in a local bucket database (BDB) for the cell. Within the OSD, the system uses the bucket and the hash to look up an offset and a length for the data block in a write-ahead log that stores data blocks for the bucket. Finally, the system returns the data block from the determined offset.