Efficient metadata storage for a non-volatile storage device

Patent metadata

Field	Value
Publication number	US-11301149-B2
Application number	US-201916295652-A
Country	US
Kind code	B2
Filing date	Mar 7, 2019
Priority date	Mar 7, 2019
Publication date	Apr 12, 2022
Grant date	Apr 12, 2022

Abstract

Embodiments of the present disclosure relate to an electronic apparatus that includes a metadata generator, to generate an extents table (ET) that lists one or more extents pages (EPs), where an EP is a fixed size, and where the one or more EPs store one or more extents. An extent includes an allocation indication for a cluster in a memory device, where a number of the extents corresponds to a number of clusters of the memory device, where a subset number of the extents is stored in one of the one or more EPs, and where the subset number is based on the fixed size of the EP. The electronic apparatus further includes a metadata updater, to modify the allocation indication in the extent stored in the one of the one or more EPs, based on a corresponding change in an allocation of the cluster in the memory device.

First claim

What is claimed is:

1. An electronic apparatus, comprising:
a memory device;
a processor coupled with the memory device; and
logic executable on the processor to operate the memory device, wherein the logic includes:
a metadata generator, to generate at least first and second extents tables (ETs) that comprise a list of one or more extents pages (EPs), wherein when a number of EPs to be listed in the first or second ETs is a fixed number, an actual number of EPs listed in the first ET exceeds the fixed number, the second ET lists an excess number of EPs that is above the fixed number of EPs to be listed in the first ET, wherein each of the one or more EPs is to store one or more extents, wherein each EP of the one or more EPs is a fixed size, wherein an extent of the one or more extents includes an allocation indication for a cluster in the memory device, wherein the extent has a fixed size that comprises a fixed number of bits, wherein the cluster is mapped to a logical block with a range of logical block addresses (LBA), wherein the number of bits that indicate the allocation further indicate that the cluster is allocated by indicating an LBA corresponding to the cluster, wherein a number of the one or more extents corresponds to a number of clusters of the memory device, wherein a subset number of the one or more extents is stored in one of the one or more EPs, and wherein the subset number of the one or more extents stored in the one of the one or more EPs is based on the fixed number of the EPs; and
a metadata updater coupled with the metadata generator, to modify the allocation indication in the extent stored in the one of the one or more EPs, based on a corresponding change in an allocation of the cluster in the memory device, wherein to modify the allocation indication includes to select the extent to be updated from the ET based on a calculation, and write a single EP containing the selected extent to the memory device,
wherein the calculation includes:
a first division of a cluster number by a product of a subset number of extents stored in the one or the one or more EPs and a maximum number of EPs listed in the first or second ET, to generate a first whole number and a first whole-number remainder; and
a second division of the first whole-number remainder by the subset number of extents stored in the one or more EPs, to generate a second whole number and a second whole-number remainder,
wherein the second whole-number remainder of zero indicates that the extent is a last extent in an EP identified by the second whole number, and wherein the second whole-number remainder greater than zero indicates that the extent is an extent identified by the second whole-number remainder, in an EP identified by one plus the second whole number.

2. The electronic apparatus of claim 1 , wherein the fixed size of the EP is based on an atomic write size of the memory device, and wherein the subset number of the one or more extents stored in the one or more EPs is based on the fixed size of the EP and the size of the extent.

3. The electronic apparatus of claim 1 , wherein the memory device is a solid state drive that includes a thin-provisioned logical volume.

4. The electronic apparatus of claim 1 , wherein the number of clusters of the memory device is based on a size of the logical volume and a size of the cluster.

5. The electronic apparatus of claim 1 , wherein the metadata generator is further to write the first and second ETs and EPs to the memory device.

6. The electronic apparatus of claim 1 , wherein to modify the allocation indication in the extent stored in the one of the one or more EPs, based on the corresponding change in the allocation of the cluster in the memory device, the metadata updater is to:
identify a change in the allocation of the cluster;
identify, based on the calculation, the first or second ET that includes an EP that includes an extent mapped to the cluster;
identify, based on the calculation, the EP that includes the extent mapped to the cluster;
locate, based on the calculation, the extent mapped to the cluster;
update, to indicate the change in the allocation of the cluster, the allocation indication in the extent mapped to the cluster; and
write an updated EP to the memory device, wherein the updated EP is the single EP that includes a modified extent.

7. The electronic apparatus of claim 1 , further comprising a processor, wherein the metadata generator and metadata updater are executable on the processor, to generate the ET and modify the allocation indication in the extent stored in the one of the one or more extent pages.

8. The electronic apparatus of claim 7 , wherein the metadata generator and metadata updater comprise a memory storage driver.

9. The electronic apparatus of claim 8 , wherein the electronic apparatus comprises a computing device.

10. One or more non-transitory computer-readable media having instructions for generating metadata stored thereon that, when executed on a processor, cause the processor to:
generate at least first and second extents tables (ETs) that comprise a list of one or more extents pages (EPs), wherein when a number of EPs to be listed in the first or second ETs is a fixed number, an actual number of EPs listed in the first ET exceeds the fixed number, the second ET lists an excess number of EPs that is above the fixed number of EPs to be listed in the first ET, wherein each of the one or more EPs is to store one or more extents, wherein each EP of the one or more EPs is a fixed size, wherein an extent of the one or more extents includes an allocation indication for a cluster in a memory device coupled with the processor, wherein the extent has a fixed size that comprises a fixed number of bits, wherein the cluster is mapped to a logical block with a range of logical block addresses (LBA), wherein the number of bits that indicate the allocation further indicate that the cluster is allocated by indicating an LBA corresponding to the cluster, wherein a number of the one or more extents corresponds to a number of clusters of the memory device, wherein a subset number of the one or more extents is stored in one of the one or more EPs, and wherein the subset number of the one or more extents stored in the one of the one or more EPs is based on the fixed number of the EPs; and
modify the allocation indication in the extent stored in the one of the one or more EPs, based on a corresponding change in an allocation of the cluster in the memory device, wherein to modify the allocation indication includes to select the extent to be updated from the ET based on a calculation, and write a single EP containing the selected extent to the memory device,
wherein the calculation includes:
a first division of a cluster number by a product of a subset number of extents stored in the one or the one or more EPs and a maximum number of EPs listed in an ET, to generate a first whole number and a first whole-number remainder; and
a second division of the first whole-number remainder by the subset number of extents stored in the one or more EPs, to generate a second whole number and a second whole-number remainder,
wherein the second whole-number remainder of zero indicates that the extent is a last extent in an EP identified by the second whole number, and wherein the second whole-number remainder greater than zero indicates that the extent is an extent identified by the second whole-number remainder, in an EP identified by one plus the second whole number.

11. The one or more non-transitory, computer-readable media of claim 10 , wherein the fixed size of the EP is based on an atomic write size of the memory device, and wherein the subset num

Assignees

• Intel Corp

Inventors

• Harris James
• Walker Benjamin
• Zawadzki Tomasz

Classifications

• G06F3/0644

  Management of space entities, e.g. partitions, extents, pools · CPC title

• G06F3/0631 Primary

  by allocating resources to storage systems · CPC title

• G06F3/0679 Primary

  Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP] · CPC title

• G06F2212/657

  Virtual address space management · CPC title

• G06F3/0604

  Improving or facilitating administration, e.g. storage management · CPC title