# US 2020/0004461 A1 · Reverse directory structure in a garbage collection unit (gcu)

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2020/0004461 A1
- Document ID: US20200004461A1
- Status: Published application
- Kind: A1
- Application number: 16/212,200
- Filed: 2018-12-06
- Published: 2020-01-02
- Earliest claimed: 2018-06-29
- Assignees: Seagate Technology LLC
- Applicants: Seagate Technology LLC
- Inventors: Benjamin J. Scott; Steven S. Williams; Stephen H. Perimutter; Ryan J. Goss; Daniel J. Benjamin
- Web page: https://patentgrep.com/patent/US20200004461A1

## CPC

- G06F 3/0659: {Command handling arrangements, e.g. command buffers, queues, command scheduling}
- G06F 3/061: {Improving I/O performance}
- G06F 3/0613: {in relation to throughput}
- G06F 3/0619: {in relation to data integrity, e.g. data losses, bit errors}
- G06F 3/0656: {Data buffering arrangements}
- G06F 3/0679: {Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]}
- G06F 11/1004: {to protect a block of data words, e.g. CRC or checksum (G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00)}
- G06F 11/1012: {using codes or arrangements adapted for a specific type of error (G06F11/1048 takes precedence)}
- G06F 12/0253: {Garbage collection, i.e. reclamation of unreferenced memory}
- G06F 2212/1044: Space efficiency improvement
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Apparatus and method for managing metadata in a data storage device such as a solid-state drive (SSD). In some embodiments, a write stream is formed of user data blocks to be sequentially written to a non-volatile memory (NVM). An entry of a reverse directory footer is generated for each user data block in the write stream to describe a physical address in the NVM at which the corresponding user data block is to be stored. The entries are accumulated in a buffer memory until the total count of entries reaches a predetermined threshold and a complete footer data structure is formed. The complete footer data structure is thereafter inserted into the write stream for writing, with the data blocks, to the NVM. The complete footer data structure has an overall size that corresponds to an overall size of each of the user data blocks.

## Claims

### Claim 1

A method comprising:
forming a write stream of user data blocks to be written to a non-volatile memory (NVM);
generating an entry of a reverse directory footer for each user data block in the write stream to describe a physical address in the NVM at which the corresponding user data block is to be stored;
accumulating the entries of the reverse directory footer in a buffer memory; and
inserting the accumulated entries from the buffer memory into the write stream responsive to a count of the entries in the buffer memory reaching a predetermined threshold, the inserted entries forming a complete footer data structure having an overall size that corresponds to an overall size of each of the user data blocks.

### Claim 2 (depends on 1)

The method of claim 1, further comprising sequentially writing, to the NVM, the user data blocks described by the complete footer data structure followed by the complete footer data structure.

### Claim 3 (depends on 1)

The method of claim 1, wherein the NVM comprises a plurality of semiconductor memory dies, wherein a garbage collection unit (GCU) is formed by logically associating at least one erasure block from each of a subset of the dies, and wherein the user data blocks and the reverse directory footer are written to the GCU.

### Claim 4 (depends on 3)

The method of claim 3, wherein the user data blocks are written as parity sets comprising N total elements with N−1 data blocks plus a parity value to provide error protection for the N−1 data blocks, and the complete footer data structure is inserted among the user data blocks in a selected parity set.

### Claim 5 (depends on 4)

The method of claim 4, wherein the GCU comprises N erasure blocks.

### Claim 6 (depends on 4)

The method of claim 4, wherein the GCU comprises N−1 erasure blocks.

### Claim 7 (depends on 3)

The method of claim 3, further comprising performing a garbage collection operation upon the GCU by locating the complete footer data structure, using the located complete footer data structure to identify at least one user data block described thereby of current data, relocating the at least one user data block to a second GCU and performing an erasure operation upon the erasure blocks of the GCU.

### Claim 8 (depends on 1)

The method of claim 1, wherein the NVM comprises a plurality of semiconductor memory dies, and the method further comprises forming a plurality of die sets by grouping together different combinations of the dies, each die set configured to store user data associated with a different user.

### Claim 9 (depends on 1)

The method of claim 1, further comprising writing a plurality of spaced-apart reverse directory footer structures to a garbage collection unit (GCU) of the NVM, wherein each successive pair of first and second reverse directory footer structures in the GCU are separated by an intervening number of user data blocks that are described by the second reverse directory footer structure.

### Claim 10 (depends on 1)

The method of claim 1, wherein the NVM is a NAND flash memory of a solid-state drive (SSD).

### Claim 11 (depends on 1)

The method of claim 1, wherein each user data block comprises X kilo-bytes (KB) of user data, each entry comprises X bytes of footer data to describe the corresponding user data block, and each complete footer comprises 1024 entries.

### Claim 12

An apparatus comprising:
a non-volatile memory (NVM) comprising a plurality of semiconductor memory dies;
a data manager circuit configured to form a write stream of user data blocks to be written to a garbage collection unit (GCU) of the NVM;
a reverse directory manager circuit configured to generate an entry of a reverse directory footer for each user data block in the write stream to describe a physical address in the GCU at which the corresponding user data block is to be stored; and
a buffer memory configured to accumulate the entries generated by the reverse directory manager circuit until a total predetermined number of entries is reached to form a complete footer data structure, the reverse directory manager circuit further configured to insert the complete footer data structure into the write stream for writing to the GCU with the user data blocks, the complete footer data structure having an overall size that corresponds to an overall size of each of the user data blocks.

### Claim 13 (depends on 12)

The apparatus of claim 12, wherein the data manager circuit is further configured to sequentially write, to the GCU, the user data blocks described by the complete footer data structure followed by the complete footer data structure.

### Claim 14 (depends on 12)

The apparatus of claim 12, wherein the user data blocks are written as parity sets each comprising N total elements with N−1 data blocks plus a parity value to provide error protection for the N−1 data blocks, and the complete footer data structure is inserted among the N−1 data blocks.

### Claim 15 (depends on 14)

The apparatus of claim 14, wherein the GCU comprises N erasure blocks, each erasure block constituting a smallest amount of the NVM that can be erased at a time, each of the N erasure blocks disposed in a different semiconductor die of the NVM.

### Claim 16 (depends on 12)

The apparatus of claim 12, wherein the data manager circuit is further configured to perform a garbage collection operation to recycle the GCU by locating the complete footer data structure within the GCU, using the located complete footer data structure to identify at least one user data block described thereby of current data, relocating the at least one user data block to a second GCU and performing an erasure operation upon the erasure blocks of the GCU.

### Claim 17 (depends on 12)

The apparatus of claim 12, wherein a plurality of spaced-apart reverse directory footer structures are written to the GCU with each successive pair of first and second reverse directory footer structures in the GCU are separated by an intervening number of user data blocks that are described by the second reverse directory footer structure.

### Claim 18 (depends on 12)

The apparatus of claim 12, wherein the NVM is a NAND flash memory of a solid-state drive (SSD).

### Claim 19

A solid-state drive (SSD), comprising:
a non-volatile memory (NVM) characterized as a flash memory comprising a plurality of semiconductor memory dies, each die comprising flash memory cells arranged into a plurality of erasure blocks with each erasure block constituting a smallest grouping of the flash memory cells that can be concurrently erased;
a controller circuit configured to form a garbage collection unit (GCU) by grouping together a selected erasure block from each of a subset of the dies in the NVM, the GCU allocated and erased as a unit;
a data manager circuit configured to form a write stream of user data blocks to be written to the GCU;
a reverse directory manager circuit configured to generate an entry of a reverse directory footer for each user data block in the write stream to describe a physical address in the GCU at which the corresponding user data block is to be stored; and
a buffer memory configured to accumulate the entries generated by the reverse directory manager circuit until a total predetermined number of entries is reached to form a complete footer data structure, the reverse directory manager circuit further configured to insert the complete footer data structure into the write stream for writing to the GCU with the user data blocks, the complete footer data structure having an overall size that corresponds to an overall size of each of the user data blocks.

### Claim 20 (depends on 19)

The SSD of claim 19, wherein the dies are arranged into at least one namespace in accordance with the NVMe (Non-Volatile Memory Express) specification, the namespace assigned for storage of user data from a selected user, and wherein the GCU extends across dies in the namespace.
