In response to receiving a request from a client to store an object, a key-durable storage system may assign the object to a volume in its data store, generate a key for the object (e.g., an opaque identifier that encodes information for locating the object in the data store), store the object on one disk in the assigned volume, store the key redundantly in the assigned volume (e.g., using a replication or erasure coding technique), and may return the key to the client. To retrieve the object, the client may send a request including the key, and the system may return the object to the client. If a disk fails, the system may determine which objects were lost, and may return the corresponding keys to the appropriate clients in a notification. The system may be used to back up a more expensive object-redundant storage system.