# US 2014/0195725 A1 · Method and system for data storage

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

- Number: US 2014/0195725 A1
- Document ID: US20140195725A1
- Status: Published application
- Kind: A1
- Application number: 14/149,993
- Filed: 2014-01-08
- Published: 2014-07-10
- Earliest claimed: 2013-01-08
- Assignees: Violin Memory, Inc.
- Applicants: Violin Memory Inc.
- Inventors: Jon C.R. Bennett
- Web page: https://patentgrep.com/patent/US20140195725A1

## CPC

- G06F 12/0246: {in block erasable memory, e.g. flash memory}
- G06F 12/06: Addressing a physical block of locations, e.g. base addressing, module addressing, memory dedication (G06F12/08 takes precedence)
- 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 and method of storing data in a semiconductor-type non-volatile memory is described, where a physical storage address of data is made available to a user application such as a file system and where characteristics of the memory system that may be allocated on a physical or a logical basis to a user are separately characterizable as to performance, size, redundancy, or the like. A read request to the memory system may be serviced by accessing the physical address included in the read request rather than using a logical-to-physical address lookup in the memory system. Garbage collection operations may be performed on a virtual-physical-block basis to preserve the relationship between the physical address known to the user and the actual physical location of the data.

## Claims

### Claim 1

A method of managing storage of data, including:
providing a nonvolatile memory device for storing data, the non-volatile memory device having a processor, volatile memory and non-volatile memory; and
configuring the processor for:
interpreting a read data command from a user to determine whether the read data command is a first type of read data command or a second type of read data command, and
wherein, the read data command is of the first type when the command includes a logical address and does not include a physical address in the nonvolatile at which the data is stored; and
the read data command is of the second type when the read data command includes at least the physical address in the nonvolatile memory at which the data is stored in memory; and,
responsive to the first type of read data command, determining the physical address of the data, retrieving data from the physical address in the nonvolatile memory and returning the data to the user; or
responsive to the second type of read command, retrieving data from the physical address in the nonvolatile memory and returning the data to the user,
wherein a relationship between the logical address and the physical address is maintained in an indirection table in the nonvolatile memory device.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
reading metadata for retrieved data;
comparing at least a portion of the metadata for retrieved data with at least a portion of metadata in the first or the second type of read command: and either,
returning the retrieved data to the user if the portions of the metadata of retrieved data and the metadata of the first or the second type of read command match; or,
returning an error message to the user if the portions of the metadata of retrieved data and the metadata of the first or the second type of read command do not match.

### Claim 3

A method of managing data storage in a memory, including:
providing a nonvolatile memory device for storing data, the non-volatile memory device having a processor, volatile memory and non-volatile memory;
configuring the processor for:
interpreting a write command from a user to determine whether the write command is a first type or a second type,
wherein the write command is of the first type when the command includes a logical address and does not include a physical address where the data is to be stored; and
the write command is of the second type when the write command includes at least a physical address at which the data is stored in the nonvolatile memory; and,
responsive to the write command of the first type, determining the physical address in the nonvolatile memory where data associated with the write command of the first type is to be stored in the nonvolatile memory, in accordance with a protocol, and associating the physical address with the logical address in an indirection table; and
responsive to the write command of second type, determining a physical address in the nonvolatile memory where data associated with the write command of the second type is to be stored, in accordance with a protocol, and including the physical address in a response message to the user and indirection table,
wherein the indirection table is maintained in the nonvolatile memory device.

### Claim 4 (depends on 3)

The method of claim 3, further comprising:
writing data associated with the first or the second type of write command to the nonvolatile memory; and
writing metadata associated with the first or the second type of write command to the nonvolatile memory device.

### Claim 5 (depends on 3)

The method of claim 3, further comprising:
using metadata of the second type of write command; and
comparing a portion of the metadata of the second type of write command with a portion of the metadata associated with the data stored at the physical address in the nonvolatile memory provided in the second type of write command; and,
performing the step of determining a physical address responsive to the second type of write command if the portion of the metadata of the second type write command matches the portion of the metadata stored at the physical address in the nonvolatile memory specified by the second type of write command; or
returning an error message to the user if the portion of the metadata of the second type of write command does not match the portion of the metadata stored at the physical address specified by the second type of write command.

### Claim 6 (depends on 3)

The method of claim 3, further comprising:
determining if second type of write command includes a logical address, and using the logical address as a portion of the metadata stored for the determined physical address, or
determining if the second type of write command does not include the logical address, and providing the logical address, associated with determined physical address, in a response message to a user; and
storing the provided logical address as metadata.

### Claim 7 (depends on 3)

The method of claim 3, wherein the metadata includes at least one of the logical address, a hash of the data stored at the logical address, a sequence number, or a time value.

### Claim 8 (depends on 3)

The method of claim 3, wherein the non-volatile memory is comprised of storage locations having physical addresses, groups of storage addresses comprising a block of memory of the plurality of blocks of memory of the nonvolatile memory, having a characteristic that the block of memory can be written once before being entirely erased.

### Claim 9 (depends on 8)

The method of claim 8, wherein a plurality of blocks form a group of blocks and the group of blocks are associated with one of a logical address range or a physical address range.

### Claim 10

A method of garbage collection in a memory system, comprising:
providing a memory system, including a non-volatile memory, volatile memory and a processor;
maintaining a first indirection table associating logical addresses with physical addresses, the memory being organized as a plurality of blocks having a plurality of physical addresses;
characterizing each physical address as being one of valid, obsolete or free;
selecting a block of the plurality of blocks in accordance with a protocol;
reading the data from valid storage locations of the selected block to a buffer in the volatile memory while maintaining an association of valid data with the physical address from which it has been read;
maintaining a cache of data to be written to the non-volatile memory;
erasing the selected block of the plurality of blocks;
selecting a physical address for the data in the cache from the indirection table, in accordance with a protocol; and
writing data from the buffer and the data in the cache to a block selected from a pool of blocks that have been erased to provide free physical storage locations.

### Claim 11 (depends on 10)

The method of claim 10, wherein the protocol for selecting blocks provides for wear leveling.

### Claim 12 (depends on 11)

The method of claim 11, wherein the data, including metadata is written to each physical address in bit-inverted format depending on a number of times the selected block has previously been erased.

### Claim 13 (depends on 12)

The method of claim 12, wherein the physical address represents an extent comprising a page.

### Claim 14 (depends on 10)

The method of claim 10, wherein the protocol for selecting the block to be erased provides for maintenance of a pool of erased blocks.

### Claim 15 (depends on 10)

The method of claim 10, wherein the selected block is erased and the step of writing valid data and the data is to the selected block.

### Claim 16 (depends on 10)

The method of claim 10, wherein the protocol for determining a free physical address maintains a relationship between physical addresses of valid data of the selected block and associates data in the cache with storage locations previously designated as either obsolete or free in the selected block.

### Claim 17 (depends on 10)

The method of claim 10, further comprising:
maintaining a second indirection table such that the physical address is associated with a block address and a relative physical address within each block; and
exchanging a block address of the selected block with a block address of the block selected from a pool of free blocks.

### Claim 18 (depends on 17)

The method of claim 17, wherein the first indirection table and the second indirection table are maintained as a single table.

### Claim 19

A device for storing data, comprising:
a nonvolatile semiconductor memory, the memory being organized as blocks, each block comprising a plurality of physical locations where a data is storable;
a processor having an associated buffer memory and communicating with a data interface and the nonvolatile semiconductor memory;
wherein the processor is configured to receive commands through the data interface and to manage storage of data in the nonvolatile semiconductor memory; and to
interpret a read data command from a user to determine whether the read data command is a first type of read data command or a second type of read data command, and
wherein the read data command is of the first type when the command includes a logical address and does not include a physical address; and the read data command is of the second type when the command includes at least a physical address at which the data is stored in memory; and,
responsive to the first type of read data command, determine the physical address of the data; retrieve data from the physical address in the non-volatile memory and return the data to the user; or
responsive to the second type of read command, retrieve data from the physical address in the non-volatile memory and return the data to the user,
wherein a relationship between the logical address and the physical address is maintained in an indirection table.

### Claim 20 (depends on 19)

The device of claim 19, further comprising:
the processor configured to:
read metadata for retrieved data;
compare at least a portion of the metadata of retrieved data with at least a portion of metadata in the first or the second type of read command: and either,
return the retrieved data to the user if the portions of the metadata of retrieved data and the metadata of the first or the second type of read command match; or,
return an error message to the user if the portions of the metadata of retrieved data and the metadata of the first of the second type of read command do not match.

### Claim 21 (depends on 20)

The device of claim 20, further comprising:
the processor configured to:
interpret a write data command from the user to determine whether the write data command is of the first type or the second type;
wherein the write data command is of the first type when the command includes the logical address and does not include a physical address where the data is to be stored; and
the write data command is of the second type when the command includes at least a physical address at which the data is stored in memory; and,
responsive to the command of the first type, determine the physical address in the non-volatile semiconductor memory where data associated with the first type of write data command is to be stored, in accordance with a protocol, and associate the physical address with the logical address in an indirection table; or,
responsive to the command of the second type, determine a physical address in the non-volatile semiconductor memory where data associated with the second type of write data command is to be stored, in accordance with a protocol, and include the physical address in a response message to the user and in the indirection table.

### Claim 22 (depends on 21)

The device of claim 21, further comprising:
the processor configured to:
write data associated with the command of the first or the second type to the nonvolatile semiconductor memory; and
write metadata associated with the command of the first or the second to the nonvolatile semiconductor memory device.

### Claim 23 (depends on 20)

The device of claim 20, further comprising:
the processor configured to:
compare a portion of the metadata of the command of the second type with a portion of the metadata associated with the data stored at the physical address provided in the second type of write data command; and,
perform the step of determining a physical address responsive to the command of the second type if the portion of the metadata of the command of the second type matches the portion of the metadata stored at the physical address of the command of the second type; or
return the error message to the user if the portion of the metadata of the command of the second type does not match the portion of the metadata stored at the physical address of the command of the second type.

### Claim 24 (depends on 20)

The device of claim 20, further comprising:
the processor configured to:
determine if second type of write data command includes a first logical address, and use the first logical address as a portion of the metadata, or
determine if the second type of write data command does not include a first logical address, and provide a second logical address, associated with the determined physical address, in a response message to the user; and
store the second logical address as metadata for the data.

### Claim 25 (depends on 20)

The device of claim 20, wherein the metadata includes at least one of the logical addresses, a hash of the data stored at the one of the logical addresses, a sequence number, or a time value.

### Claim 26 (depends on 20)

The device of claim 20, wherein the non-volatile semiconductor memory is comprised of storage locations having physical addresses, groups of storage addresses comprising a block of memory, and having a characteristic that a block of memory can be written once before being entirely erased.

### Claim 27 (depends on 26)

The device of claim 26, wherein a plurality of blocks form a group of blocks and the group of blocks are associated with one of a logical address range or a physical address range.

### Claim 28 (depends on 20)

The device of claim 20, further comprising:
the processor configured to:
receive a TRIM command from the user, the TRIM command identifying at least one physical address to be disassociated from a corresponding logical address in the indirection table; and
set a status of the physical address associated with the logical address in the indirection table to invalid; and
disassociate the physical address from the logical address.

### Claim 29 (depends on 28)

The device of claim 28, wherein the TRIM command includes a base logical block address and an extent.

### Claim 30 (depends on 29)

The device of claim 29, wherein metadata of the extent, included in the TRIM command is compared with the metadata of the at least one physical address of the extent the physical address is status is set to invalid and the physical address is dissociated from the logical address when the metadata matches.