# US 2017/0255388 A1 · Efficient and Dynamically Sized Reverse Map to Handle Variable Size Data

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

- Number: US 2017/0255388 A1
- Document ID: US20170255388A1
- Status: Published application
- Kind: A1
- Application number: 15/062,456
- Filed: 2016-03-07
- Published: 2017-09-07
- Earliest claimed: 2016-03-07
- Assignees: HGST Netherlands B.V.
- Applicants: HGST Netherlands B.V.
- Inventors: Sandeep Sharma; Saurabh Manchanda
- Web page: https://patentgrep.com/patent/US20170255388A1

## CPC

- G06F 3/0605: {by facilitating the interaction with a user or administrator}
- G06F 3/0608: {Saving storage space on storage systems}
- G06F 3/0631: {by allocating resources to storage systems}
- G06F 3/064: {Management of blocks}
- G06F 3/0679: {Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]}
- G06F 12/0238: {Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory}
- G06F 12/10: Address translation
- G06F 12/1018: involving hashing techniques, e.g. inverted page tables
- G06F 2212/1016: Performance improvement
- G06F 2212/1044: Space efficiency improvement
- G06F 2212/1048: Scalability
- G06F 2212/214: Solid state disk
- G06F 2212/401: Compressed data
- 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

A system comprising a processor and a memory storing instructions that, when executed, cause the system to receive a data stream including one or more data blocks; determine a size of the one or more data blocks; determine a number of mappings needed for a physical block based on the size of a data block and a size of the physical block, the number of mappings being variable for different physical blocks depending on the size of the one or more data blocks storing in the physical block; retrieve a dynamically sized reverse map, the dynamically sized reverse map being a dynamic tree structure; determine a starting location in the dynamically sized reverse map for mappings of the one or more data blocks; and create an entry for the physical block in the dynamically sized reverse map.

## Claims

### Claim 1

A method comprising:
receiving a data stream including one or more data blocks;
determining a size of the one or more data blocks;
determining a number of mappings based on the size of the one or more data blocks and a size of a physical block, the number of mappings being variable for different physical blocks depending on the size of the one or more data blocks stored in the physical block;
retrieving a dynamically sized reverse map, a size of the dynamically sized reverse map corresponding to the variable number of mappings for different physical blocks;
determining a starting location in the dynamically sized reverse map for mappings of the one or more data blocks; and
creating an entry for the physical block in the dynamically sized reverse map, the entry including the number of mappings of the physical block and the starting location for the one or more data blocks, the entry being an index of the numbers of mappings for the physical block.

### Claim 2 (depends on 1)

The method of claim 1, wherein dynamically sized reverse map includes a dynamic tree structure having an extensible node for a plurality of buffer entries, one buffer entry for each of the one or more data blocks.

### Claim 3 (depends on 1)

The method of claim 1, further comprising creating, a buffer entry for each of the one or more data blocks, the buffer entry including a logical block number, a physical block number, a starting sector in the physical block, and a number of sectors occupied in the physical block.

### Claim 4 (depends on 3)

The method of claim 3, wherein the buffer entry is persisted to the storage device.

### Claim 5 (depends on 3)

The method of claim 3, wherein the number of sectors occupied in the physical block is determined based on the size of each of the one or more data blocks and a size of the sector.

### Claim 6 (depends on 4)

The method of claim 4, wherein the number of mappings of the physical block represents the number of buffer entries a physical block consumes.

### Claim 7 (depends on 1)

The method of claim 1, further comprising:
receiving a request to copy a plurality of data blocks from a first range of logical address to a second range of logical address;
determining a size of the plurality of data blocks;
determining number of references the plurality of data blocks occupy based on the size of the plurality of data blocks;
determining a forward pointer based on the dynamically sized reverse map for the plurality of data blocks; and
updating the dynamically sized reverse map with an extra entry with the forward pointer and the number of references.

### Claim 8 (depends on 1)

The method of claim 1, further comprising:
retrieving information of a map segment from a segment header;
determining a use count of write blocks of the map segment;
determining whether the map segment satisfies dynamically sized reverse map updating criteria based on the use count of the map segment;
responsive to the map segment satisfying the dynamically sized reverse map updating criteria, performing dynamically sized reverse map updating on the map segment; and
updating the information of the map segment in the segment header.

### Claim 9 (depends on 8)

The method of claim 8, wherein the map segment stores the dynamically sized reverse map.

### Claim 10

A system comprising:
a dynamically sized reverse map having a variable size corresponding to a variable number of mappings for different physical blocks of a storage device; and
a processor coupled to the dynamically sized reverse map, the processor configured to:
receive a data stream including one or more data blocks;
determine a size of the one or more data blocks;
determine a number of mappings needed for a physical block based on the size of a data block and a size of the physical block, the number of mappings being variable for different physical blocks depending on the size of the one or more data blocks storing in the physical block;
determine a starting location in the dynamically sized reverse map for mappings of the one or more data blocks; and
create an entry for the physical block in the dynamically sized reverse map, the entry including the number of mappings of the physical block and the starting location for the one or more data blocks, the entry being an index of the variable numbers of mappings for the physical block.

### Claim 11 (depends on 10)

The system of claim 10, wherein the dynamically sized reverse map includes a dynamic tree structure having an extensible node extensible node for a plurality of buffer entries, one buffer entry for each of the one or more data blocks.

### Claim 12 (depends on 10)

The system of claim 10, wherein the extensible node includes buffer entry for each of the one or more data blocks, the buffer entry including a logical block number, a physical block number, a starting sector in the physical block, and a number of sectors occupied in the physical block.

### Claim 13 (depends on 12)

The system of claim 12, wherein the processor is configured to persist the buffer entry to the storage device.

### Claim 14 (depends on 12)

The system of claim 12, wherein the number of sectors occupied in the physical block is determined based on the size of each of the one or more data blocks and a size of the sector.

### Claim 15 (depends on 4)

The method of claim 4, wherein the number of mappings of the physical block represents the number of buffer entries a physical block consumes.

### Claim 16 (depends on 10)

The system of claim 10, wherein the processor is further configured to:
receive a request to copy a plurality of data blocks from a first range of logical address to a second range of logical address;
determine a size of the plurality of data blocks;
determine number of references the plurality of data blocks occupy based on the size of the plurality of data blocks;
determine a forward pointer based on the dynamically sized reverse map for the plurality of data blocks; and
update the dynamically sized reverse map with an extra entry with the forward pointer and the number of references.

### Claim 17 (depends on 10)

The system of claim 10, wherein the processor is further configured to:
retrieve information of a map segment from a segment header;
determine a use count of write blocks of the map segment;
determine whether the map segment satisfies dynamically sized reverse map updating criteria based on the use count of the map segment;
responsive to the map segment satisfying the dynamically sized reverse map updating criteria, perform dynamically sized reverse map updating on the map segment; and
updating the information of the map segment in the segment header.

### Claim 18 (depends on 17)

The system of claim 17, wherein the map segment stores the dynamically sized reverse map.