Using a first-in-first-out (FIFO) wraparound address lookup table (ALT) to manage cached data

A data storage device, comprising:

• a non-volatile memory (NVM);
• a first level map stored as a data structure in a first memory and arranged as a first-in-first-out (FIFO) buffer to list a plurality of host access commands in an order corresponding to an order in which the host access commands were received from a host device, the FIFO buffer storing a different host tag value for each of the host access commands;
• a cache memory configured to store user data blocks associated with the host access commands listed in the FIFO buffer, each of the user data blocks having a logical address;
• a second level map stored as a data structure in a second memory and arranged as a cache map to correlate cache addresses in the cache memory at which the user data blocks are stored to the host tag values stored in the FIFO buffer, the first memory, the second memory, and the cache memory comprise on-chip local volatile memory that is incorporated into a system on chip (SOC) integrated circuit device;
• and
• a control circuit configured to, responsive to receipt of a new host access command from the host device, search the FIFO buffer to identify a selected host access command from the plurality of host access commands listed in the FIFO buffer having a logical address that corresponds to a logical address associated with the new host access command, to use the host tag value from the FIFO buffer for the selected host access command as an input value to the second level map to locate a selected cache address in the cache memory, and to transfer a selected user data block stored at the selected cache address to the host device to service the new host access command.