Aspects of a storage device including a memory and a controller are provided that allow for storage of tags identifying data types and sequence numbers with data to facilitate data recovery and system integrity checks following a power failure or other system failure event. The controller is configured during a write operation to include a tag in the data identifying the data type as a host write, a recycle write, or another internal write. Following a system failure event, the controller is configured to read the tags to identify the data type in the write. Based on the tags, the controller is configured to properly rebuild or update a logical-to-physical (L2P) table of the storage device to assign correct logical addresses to the most recent data during data recovery, as well as to verify correct logical addresses during system integrity checks.