# US 11,307,997 B2 · Logical to physical data storage mapping

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

- Number: US 11,307,997 B2
- Document ID: US11307997B2
- Status: Granted
- Kind: B2
- Application number: 16/909,617
- Filed: 2020-06-23
- Published: 2020-10-08
- Granted: 2022-04-19
- Earliest claimed: 2018-03-19
- Assignees: Seagate Technology LLC
- Applicants: Seagate Technology LLC
- Inventors: Hongmei Xie; Zejiang Qu; Hackbin Kim; Erich Franz Haratsch
- Web page: https://patentgrep.com/patent/US11307997B2

## CPC

- G06F 12/0238: {Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory}
- G06F 12/109: for multiple virtual address spaces, e.g. segmentation (G06F12/1036 takes precedence)
- G06F 3/061: {Improving I/O performance}
- G06F 3/0659: {Command handling arrangements, e.g. command buffers, queues, command scheduling}
- G06F 3/0673: {Single storage device}
- G06F 2212/1008: Correctness of operation, e.g. memory ordering
- G06F 2212/1016: Performance improvement
- G06F 2212/657: Virtual address space management
- G06F 2212/7201: Logical to physical mapping or translation of blocks or pages
- G06F 2212/7205: Cleaning, compaction, garbage collection, erase control
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Systems, methods and computer-readable memory for garbage collection in a storage device. One method comprises, upon a write of data to a first garbage collection unit (GCU) of the storage device, incrementing a number of logical mapping units stored in the first GCU along with a number of logical mapping units with valid data stored in the first GCU. A number of logical mapping units with invalid data stored in a second GCU is decremented based on the incremented number of logical mapping units with valid data stored in the first GCU. The second GCU is erased when a valid data rate of the second GCU is below a valid data rate of the first GCU.

## Claims

### Claim 1

A method of garbage collection in a storage device, the method comprising steps of, upon a write of new data associated with a logical mapping unit (LMU) to a first garbage collection unit (GCU):
incrementing a total number of logical mapping units stored in the first GCU;
incrementing a number of logical mapping units with valid data stored in the first GCU;
decrementing a number of logical mapping units with valid data stored in a second GCU, the second GCU containing old data associated with the LMU;
recycling the second GCU when a valid data rate of the second GCU is below a valid data rate of the first GCU; and
recycling the second GCU when the valid data rate of the second GCU is equal to the valid data rate of the first GCU and a total number of valid data bytes stored in the second GCU is below a total number of valid data bytes stored in the first GCU.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
computing an average compression rate of data stored in the second GCU based on a total number of logical mapping units stored in the second GCU, a size of a logical mapping unit, a total number of physical mapping units in the second GCU, and a size of a physical mapping unit;
computing a universal compressed data length for logical mapping units stored in the second GCU based on the average compression rate; and
in conjunction with decrementing the number of logical mapping units with valid data stored in the second GCU, reducing the total number of valid data bytes stored in the second GCU by the universal compressed data length.

### Claim 3 (depends on 2)

The method of claim 2, wherein computing the universal compressed data length for the second GCU comprises:
dividing the size of a logical mapping unit by the average compression rate.

### Claim 4 (depends on 2)

The method of claim 2, further comprising:
computing the total number of valid data bytes stored in the second GCU based on the number of logical mapping units with valid data stored in the second GCU, the size of a logical mapping unit, and the average compression rate.

### Claim 5 (depends on 1)

The method of claim 1, wherein the valid data rate of the first and second GCU are computed by dividing the number of logical mapping units with valid data stored in the GCU by the total number of logical mapping units stored in the GCU.

### Claim 6

A storage system, comprising:
a storage device comprising a plurality of garbage collection units (GCUs); and
a controller comprising a map and operable to, upon a write of new data associated with a logical mapping unit (LMU) to a first GCU,
increment a total number of physical mapping units used to store logical mapping units with valid data in the first GCU based on a number of physical units occupied by the new data from a new map entry associated with the LMU in the map,
decrement a total number of physical mapping units used to store logical mapping units with valid data in a second GCU, the second GCU containing old data associated with the LMU, based on a number of physical units occupied by the old data from an old map entry associated with the LMU in the map, and
recycle the second GCU when the total number of physical mapping units used to store logical mapping units with valid data of the second GCU is below the total number of physical mapping units used to store logical mapping units with valid data of the first GCU.

### Claim 7 (depends on 6)

The storage system of claim 6, wherein each map entry in the map contains a length of the data associated with the LMU, and wherein the number of physical units occupied by the data associated with the LMU is computed by dividing the length of the data from the map entry associated with the LMU by a smallest number of data bytes stored in one physical mapping unit.

### Claim 8

A non-transitory memory storing instructions that, when executed by a processor of a controller associated with a storage device, cause the controller to:
upon a write of new data associated with a logical mapping unit (LMU) a first garbage collection unit (GCU) of the storage device, increment a total number of logical mapping units stored in the first GCU;
increment a number of logical mapping units with valid data stored in the first GCU;
decrement a number of logical mapping units with valid data stored in a second GCU, the second GCU containing old data associated with the LMU;
compute an average compression rate of data stored in the first and second GCUs based on the total number of logical mapping units stored in the GCU, a size of a logical mapping unit, a total number of physical mapping units in the GCU, and a size of a physical mapping unit;
compute a size of valid data bytes stored in the first and second GCUs by multiplying the number of logical mapping units with valid data stored in the GCU by the size of a logical mapping unit and dividing by the average compression rate of data stored in the GCU; and
decide whether to recycle the second GCU based on a comparison of the size of valid data bytes stored in the second GCU and the size of valid data bytes stored in the first GCU.

### Claim 9 (depends on 8)

The non-transitory memory of claim 8, wherein deciding to recycle the second GCU is further based a comparison of the number of logical mapping units with valid data stored in the second GCU and the number of logical mapping units with valid data stored in the first GCU.