Reading logical groups of data from physical locations in memory using headers

1. A method for reading data stored in a non-volatile storage device having a plurality of physical memory portions having a predefined sequence of physical locations in one or more non-volatile memory (NVM) devices of the storage device, the method comprising:

executing a plurality of read commands, each read command of the plurality of read commands for reading a requested logical group of data from a specified logical address, the requested logical group of data comprising one or more logical portions, the executing including, for each read command of the plurality of read commands:

identifying, from a mapping table, a first physical location in the storage device corresponding to the logical address specified by the read command;

reading data from the first physical location in the storage device corresponding to the logical address;

determining whether the first physical location stores less than all of the requested logical group of data by:

decoding at least a portion of the data read from the first physical location; and

comparing a size of the decoded data to a size of the requested logical group of data, wherein the first physical location stores less than all of the requested logical group of data when the size of the decoded data is less than the size of the requested logical group of data;

in accordance with a determination that the first physical location in the storage device stores less than all of the logical group of data requested by the read command:

identifying a second physical location in the storage device based on information contained within the data read from the first physical location in the storage device, and

reading data from the second physical location in the storage device;

decoding at least respective portions of the data read from the first physical location and/or the second physical location in the storage device to produce the requested logical group of data; and

returning the requested logical group of data.

2. The method of claim 1 , wherein:

the first physical location corresponds to data for a head logical portion of the one or more logical portions of the requested logical group of data, and corresponds to a first physical memory portion of the plurality of physical memory portions;

the second physical location corresponds to data for a tail logical portion of the one or more logical portions of the requested logical group of data, and corresponds to a second physical memory portion of the plurality of physical memory portions, wherein the second physical memory portion is distinct from the first physical memory portion;

reading data from the first physical location includes reading data from the first physical memory portion; and

reading data from the second physical location includes reading data from the second physical memory portion.

3. The method of claim 2 , wherein the first physical memory portion is a first physical page of the storage device, and the second physical memory portion is a second physical page of the storage device.

4. The method of claim 2 , wherein the first physical memory portion is a physical memory portion of a first die, and the second physical memory portion is a physical memory portion of a second die, distinct from the first die.

5. The method of claim 2 , wherein the first physical memory portion and the second physical memory portion are distinct physical memory portions of a same die.

6. The method of claim 2 , wherein:

each of the plurality of physical memory portions comprises a respective integer number of codewords arranged in a respective sequence,

the first physical location corresponds to a subset of codewords, of respective codewords for the first physical memory portion, located at an end of the respective sequence, and

the second physical location corresponds to a subset of codewords, of respective codewords for the second physical memory portion, located at the end of the respective sequence.

7. The method of claim 6 , wherein the subset of codewords corresponding to the first physical location and the subset of codewords corresponding to the second physical location each comprise a single codeword.

8. The method of claim 6 , wherein the subset of codewords corresponding to the second physical location includes encoded data for a portion of the requested logical group of data and encoded data for a portion of a distinct logical group of data.

9. The method of claim 8 , wherein the encoded data for the portion of the distinct logical group of data corresponds to a head logical portion for the distinct logical group of data.

10. The method of claim 1 , further comprising determining whether the first physical location stores less than all of the requested logical group of data by reading a corresponding entry of the mapping table for the requested logical group of data, the corresponding entry indicating that the first physical location stores less than all of the requested logical group of data.

11. The method of claim 10 , wherein the corresponding entry includes a flag indicating whether the first physical location includes information specifying the second physical location.

12. The method of claim 10 , wherein the corresponding entry specifies the first and second physical locations corresponding to data for the one or more logical portions of the requested logical group of data, wherein the first and second physical locations correspond to distinct physical memory portions of the plurality of physical memory portions of the storage device.

13. The method of claim 10 , wherein the corresponding entry specifies a respective physical location at which the information specifying the second physical location is stored.

14. The method of claim 1 , wherein the information contained within the data read from the first physical location includes the information specifying the second physical location in the storage device.

15. The method of claim 1 , wherein:

the first physical location corresponds to data for a head logical portion of the one or more logical portions, and the second physical location corresponds to data for a tail logical portion of the one or more logical portions, and

the information contained within the data read from the first physical location is stored in a header segment that specifies:

the first physical location for the head logical portion and the second physical location for the tail logical portion;

a check value for the logical group of data for verifying the first physical location and/or the second physical location for the tail logical portion; and/or

additional parity bits for error correcting decoded data for the logical group of data.

16. The method of claim 1 , wherein the data read from the first physical location and the data read from the second physical location comprise respective sets of one or more codewords, and wherein the decoding comprises:

determining, for each of the respective sets of one or more codewords, a respective error correction format based on the respective physical location to which the respective set of one or more codewords corresponds; and

decoding each of the respective sets of codewords using the determined respective error correction format to produce the requested logical group of data.

17. A storage device, comprising:

one or more NVM devices, wherein a plurality of physical memory portions of the storage device has a predefined sequence of physical locations in the one or more NVM devices;

a memory controller;

an interface to receive a plurality of read commands, each read command of the plurality of read commands for reading a requested logical group of data from a specified logical address, the requested logical group of data comprising one or more logical portions;

wherein the memory controller is configured to:

identify, from a mapping table, a first physical location in the storage device corresponding to the specified logical addresses;

in accordance with a determination that the first physical location stores less than all of the logical group of data requested by the read command, identify a second physical location in the storage device based on information contained within data from the first physical location; and

wherein to determine whether the first physical location stores less than all of the requested logical group of data, the memory controller is further configured to:

decode at least a portion of the data read from the first physical location; and

compare a size of the decoded data to a size of the requested logical group of data, wherein the first physical location stores less than all of the requested logical group of data when the size of the decoded data is less than the size of the requested logical group of data.

18. A non-transitory computer readable storage medium, storing one or more programs for execution by one or more processors of a non-volatile storage device, the storage device comprising a plurality of physical memory portions having a predefined sequence of physical locations in one or more NVM devices of the storage device, and the one or more programs including instructions for performing operations comprising:

executing a plurality of read commands, each read command of the plurality of read commands for reading a requested logical group of data from a specified logical address, the requested logical group of data comprising one or more logical portions, the executing including, for each read command of the plurality of read commands:

identifying, from a mapping table, a first physical location in the storage device corresponding to the logical address specified by the read command;

reading data from the first physical location in the storage device corresponding to the logical address;

determining whether the first physical location stores less than all of the requested logical group of data by:

decoding at least a portion of the data read from the first physical location; and

comparing a size of the decoded data to a size of the requested logical group of data, wherein the first physical location stores less than all of the requested logical group of data when the size of the decoded data is less than the size of the requested logical group of data;

in accordance with a determination that the first physical location in the storage device stores less than all of the logical group of data requested by the read command:

identifying a second physical location in the storage device based on information contained within the data read from the first physical location in the storage device, and

reading data from the second physical location in the storage device;

decoding at least respective portions of the data read from the first physical location and/or the second physical location in the storage device to produce the requested logical group of data; and

returning the requested logical group of data.