1. A method comprising: executing requests to write data on a non-volatile recording medium, by storing data segments at respective storage locations of the non-volatile recording medium, maintaining a first set of metadata on a volatile recording medium, the first set of metadata associating logical addresses with respective storage locations of stored data segments corresponding to the logical addresses on the non-volatile recording medium and indicating a state of the stored data segments, and maintaining a second set of metadata on the non-volatile recording medium, the second set of metadata associating storage locations of the non-volatile recording medium with respective stored data segments corresponding to the logical addresses and indicating a state of the stored data segments; updating the second set of metadata in response to a first operation performed on the stored data segments, including a particular stored data segment, wherein the second set of metadata is updated to indicate a state of the particular stored data segment that differs from a state of the particular stored data segment indicated by the first set of metadata, the first set of metadata and the second set of metadata associating the particular stored data segment with a same logical address and a same storage location on the non-volatile recording medium; and updating the first set of metadata in response to a subsequent operation performed on the stored data segments, wherein the first set of metadata is updated based on the first operation.