Data storage device using metadata and mapping table to identify valid user data on non-volatile media

[0001] The present application claims priority from co-pending provisional U.S. Patent Application Ser. No. 61/378,880, filed on Aug. 31, 2010, the specification of which is incorporated herein by reference.

[0002] Data storage devices, such as disk drives and solid state drives, can use “logical block address (LBA) indirection” to store user data on non-volatile media, such as a disk surface or Flash memory, wherein data for LBAs are not typically stored in the same physical location each time they are written. For example, if data is written to LBA 0, it may be stored in physical location 0 on the non-volatile media. But if it is written again later, it may be stored in a new physical location, such as physical location 20. Thus, with LBA indirection, a physical location on the non-volatile media may contain data for any LBA. When a host rewrites a particular LBA on a storage device with LBA indirection, the older copy of the LBA and associated user data is not overwritten or erased. The more recent copy of the LBA is written into a new physical location, thereby invalidating the user data stored in the old physical location.

[0003] In order to reuse old physical locations containing invalid data, a region of the non-volatile media containing the old physical locations can be erased. However, before erasing the region containing the invalid data, a garbage collection operation is typically performed to identify and migrate into another region any valid data that is stored in physical locations located in the same region of the non-volatile media as the invalid data.

[0004] There is, therefore, a need to efficiently identify valid user data on non-volatile media of a data storage device for migration during a garbage collection operation.

[0011] FIG. 1A shows a data storage device according to an embodiment of the present invention comprising a head 2 actuated radially over a disk surface 4 by an actuator arm 6, and a voice coil motor (VCM) 8 operable to rotate the actuator arm 6 about a pivot. The disk surface 4 comprises first and second zones 10 and 12, wherein the first zone 10 comprises a plurality of data tracks 14 and the second zone 12 comprises a plurality of data tracks 16. Each track 14 comprises a plurality of physical locations 18 and each track 16 comprises a plurality of physical locations 20. The plurality of physical locations 18 and 20 can be used by the host for reading and writing user data. In one embodiment, the first zone 10 is a high performance zone and the second zone 12 is a low performance zone. In an alternate embodiment of the invention, the disk surface 4 comprises a single zone comprising a plurality of data tracks. In another embodiment, the disk surface 4 comprises more than two zones, wherein each zone comprises a plurality of data tracks.

[0012] In the embodiment in FIG. 1A, the disk surface 4 further comprises a plurality of embedded servo sectors 22₁-22_N that define the tracks 14 in zone 10 and the tracks 16 in zone 12. The disk drive further comprises control circuitry 24, which is operable to process a read signal 26 emanating from the head 2 to demodulate the embedded servo sectors 22₁-22_N and generate a position error signal (PES). The PES represents a radial offset of the head 2 from a target track 14 in the first zone 10 or a target track 16 in the second zone 12. The control circuitry 24 is further operable to process the PES with a suitable servo compensator to generate a VCM control signal 25 applied to the VCM 8. The VCM 8 rotates the actuator arm 6 about a pivot in order to actuate the head 2 radially over the disk surface 4 in a direction that decreases the PES.

[0013] The disk drive further comprises a semiconductor memory (SM) 28 communicatively coupled to the control circuitry 24. The SM 28 can comprise, for example, dynamic random access memory (DRAM), Flash memory, or static random access memory (SRAM). The SM 28 further comprises a buffer for temporarily storing write user data received from the host via a write command and read user data requested by the host via a read command.

[0014] In the embodiment in FIG. 1A, logical block address (LBA) indirection is used to store user data in the plurality of physical locations 18 and 20 on the disk surface 4, wherein an LBA is generally stored in a different physical location each time it is written by the host. Thus, each of the plurality of physical locations 18 and 20 on the disk surface 4 may contain any LBA. In one embodiment, user data is written in each of the physical locations 18 and 20 sequentially in one direction. In an embodiment of the present invention, the tracks 14 and 16 on the disk surface 4 are written in a shingled manner such that a previously written track is partially overwritten.

[0015] In the embodiment of FIG. 1A, metadata associates each of the physical locations 18 on each of the tracks 14 with an LBA and user data. In an embodiment of the present invention, the metadata associating an LBA with each of the physical locations 18 on a track 14 is stored on the same track 14. In one embodiment, the metadata is stored in a physical location located at the head of each track. In another embodiment, the metadata is stored in a physical location located at the end of each track. In one embodiment of the present invention, the metadata is stored in a physical location located at the head of each track and at a physical location located at the middle of each track. In one embodiment, the metadata that associates each of the physical locations 18 on each of the tracks 14 with an LBA and user data is stored in a single physical location on the disk surface 4. For example, the single physical location can be located on one of the tracks 14 in the first zone 10. In one embodiment, the metadata associated with each of the physical locations 18 and 20 on the disk surface 4 is located in non-volatile semiconductor memory (e.g., Flash memory) in the disk drive.

[0016] The disk drive in FIG. 1A further comprises a mapping table comprising a mapping of each LBA in each of the physical locations on the disk surface 4. The mapping table can be stored, for example, in a physical location on the disk surface 4.

[0017] In one embodiment, the mapping table is stored in non-volatile semiconductor memory (e.g., Flash memory) in the disk drive.

[0018] FIG. 1B shows an embodiment of the present invention wherein metadata is written in a physical location at the head of each track on the disk surface and the metadata associates each physical location on the track with an LBA and user data. In the embodiment in FIG. 1B, the metadata includes a number of LBAs (#LBAs), wherein each LBA is associated with written user data in one of the physical locations on the track. In one embodiment, metadata can be stored in a physical location at the head of each track and in a physical location at the middle of each track. In another embodiment, the metadata can be stored in a physical location at the end of the track.

[0019] FIG. 2A shows an embodiment of the present invention wherein a circular buffer spans substantially the entire disk surface, and data is written from an inner diameter (ID) of the disk toward an outer diameter (OD) of the disk surface. Accordingly, the circular buffer comprises a head for writing new data and a tail that identifies invalid data that was previously “overwritten”. In one embodiment, the data is written in the circular buffer from the OD toward the ID of the disk surface. In one embodiment, the tracks are written in a shingled manner such that a previously written track is partially overwritten. Writing data in one direction (always at the head of the circular buffer) ensures that a previously written track is partially overwritten only on one side. In other embodiments, a circular buffer may be implemented on the disk surface without shingled writing.

[0020] FIG. 2B shows an embodiment of the present invention wherein the control circuitry 24 defines two circular buffers on the disk surface 4 which may be selected to service write commands received from the host as well as garbage collection writes using any suitable algorithm. In the embodiment of FIG. 2B, the first and second circular buffers are written from the ID toward the OD. In another embodiment, the first and second circular buffers are written from the OD toward the ID. In one embodiment, a first circular buffer is written from the ID to the middle diameter (MD), and a second circular buffer is written from the OD to the MD. In another embodiment of the present invention, the control circuitry 24 defines more than two circular buffers on the disk surface. In another embodiment, the present invention applies to more than one disk surface of a data storage device. For example, the metadata may be written on a different disk surface than the associated user data and LBAs, and/or the circular buffers may span more than one disk surface.

[0021] FIG. 3A is a flow diagram executed by the control circuitry 24 according to an embodiment of the present invention, wherein the control circuitry 24 executes a garbage collection operation on the disk surface (step 30). The control circuitry 24 reads first metadata associated with a first plurality of physical locations 18 on a non-volatile media (e.g., disk surface 4) (step 32). The first plurality of physical locations 18 can be located, for example, on at least one track 14 in the first zone 10 on the disk surface 4. In one embodiment of the present invention, the first plurality of physical locations 18 is located at the tail of a circular buffer on the disk surface 4. In one embodiment, the first metadata is located on the at least one track 14. In another embodiment, the first metadata is located in a physical location 18 in the first zone 10. In an embodiment of the invention, the first metadata is located in non-volatile semiconductor memory (e.g., Flash memory). The control circuitry 24 reads a mapping table to determine the current physical location for each LBA (step 34). The mapping table comprises a mapping of each LBA to a current physical location on the disk surface 4.

[0022] In the embodiment shown in the flow diagram in FIG. 3A, the control circuitry 24 compares the current physical location of each LBA to a corresponding one of the first plurality of physical locations 18 to identify valid user data (step 36). The control circuitry 24 determines whether the current physical location matches a corresponding one of the first plurality of physical locations 18 (step 38). If the current physical location does not match a corresponding one of the first plurality of physical locations 18, the LBA is associated with invalid user data (step 40). If the current physical location matches a corresponding one of the first plurality of physical locations 18, the LBA is associated with valid user data (step 40).

[0023] FIG. 3B is a flow diagram according to an embodiment of the present invention which extends the flow diagram of FIG. 3A. In the embodiment of FIG. 3B, the control circuitry 24 adds the physical location of each valid user data to a valid data list (step 44). For example, the valid data list can indicate the physical location of each valid user data. In an embodiment of the invention, the valid data list resides in SM 28. In one embodiment, the valid data list is located in non-volatile semiconductor memory (e.g., Flash memory) in the disk drive. The control circuitry 24 then reads the data associated with each physical location in the valid data list and writes it into the buffer (step 46). Then the control circuitry 24 writes the valid user data from the buffer into a second plurality of physical locations 20 on the disk surface 4 (step 48). In one embodiment, the second plurality of physical locations 20 is located at the head of a circular buffer on the disk surface 4. In an embodiment of the present invention, the control circuitry 24 sequentially writes in one direction the valid user data into the second plurality of physical locations 20 on at least one of tracks 16 on the disk surface 4.

[0024] In the embodiment shown in the flow diagram in FIG. 3B, the control circuitry 24 determines second metadata associating each LBA with valid user data to one of the second plurality of physical locations 20 (step 50). In one embodiment, the control circuitry 24 determines the second metadata prior to writing each valid user data into the second plurality of physical locations 20. The control circuitry 24 updates the mapping table after writing each valid user data into the second plurality of physical locations 20 (step 52). In the embodiment in FIG. 3B, the control circuitry 24 stores the second metadata on the non-volatile media (e.g., disk surface 4) (step 54). In one embodiment, the second metadata is stored in at least one of the second plurality of physical locations 20. In another embodiment, the second metadata is stored in non-volatile semiconductor memory (e.g., Flash memory) in the disk drive.

[0025] It is noted that the steps in the flow diagrams in FIGS. 3A and 3B are shown in a particular order to illustrate an embodiment of the present invention. In other embodiments, the steps in the flow diagrams in FIGS. 3A and 3B may be performed in a different order.

[0026] Any suitable control circuitry 24 may be employed in the embodiments of the present invention, such as any suitable integrated circuit or circuits. For example, the control circuitry 24 may be implemented within a read channel integrated circuit, or in a component separate from the read channel, such as a disk controller, or certain steps described above may be performed by a read channel and others by a disk controller. In one embodiment, the read channel and disk controller are implemented as separate integrated circuits, and in an alternative embodiment they are fabricated into a single integrated circuit or system on a chip (SOC). In addition, the control circuitry may include a suitable preamp circuit implemented as a separate integrated circuit, integrated into the read channel or disk controller circuit, or integrated into an SOC.

[0027] In one embodiment, the control circuitry 24 comprises a microprocessor executing instructions, the instructions being operable to cause the microprocessor to perform the steps of the flow diagrams described herein. The instructions may be stored in any computer-readable medium. In one embodiment, they may be stored on a non-volatile semiconductor memory external to the microprocessor, or integrated with the microprocessor in a SOC. In another embodiment, the instructions are stored on the disk surface 4 and read into a volatile semiconductor memory when the disk drive is powered on. In yet another embodiment, the control circuitry 24 comprises suitable logic circuitry, such as state machine circuitry.