Systems and methods for referencing data on a storage medium

• US 10,019,353 B2
• Filed: 06/24/2013
• Issued: 07/10/2018
• Est. Priority Date: 03/02/2012
• Status: Active Grant

• Current Assignee: Unification Technologies LLC (Acacia Research Corporation)
• Original Assignee: Longitude Enterprise Flash S.à r.l. (Vector Capital Corporation)
• Inventors: Orme, Evan, Peterson, James G., Vigor, Kevin, Flynn, David
• Primary Examiner(s): Rigol, Yaima
• Application Number:
  US13/925,410
• Publication Number:
  US 20130282953A1
• Time in Patent Office: 1,842 Days
• Field of Search: None
• CPC Class Codes: G06F 11/108 Parity data distribution in semiconductor storages, e.g. in SSD
• CPC Class Codes: G06F 12/0238 Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2211/109 Sector level checksum or ECC, i.e. sector or stripe level checksum or ECC in addition to the RAID parity calculation
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7208 Multiple device management, e.g. distributing data over multiple flash devices
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0664 at device level, e.g. emulation of a storage device or system
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: H04L 12/4625 Single bridge functionality, e.g. connection of two networks over a single bridge
• CPC Class Codes: H04L 12/6418 Hybrid transport
• CPC Class Codes: H04L 12/66 Arrangements for connecting between networks having differing types of switching systems, e.g. gateways
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H05K 7/1444 Complex or three-dimensional-arrangements; Stepped or dual mother boards

Abstract

A storage layer is configured to store data at respective offsets within storage units of a storage device. Physical addresses of the data may be segmented into a first portion identifying the storage unit in which the data is stored, and a second portion that indicates the offset of the data within the identified storage unit. An index of the data offsets (e.g., second portions of the physical addresses) may be persisted on the storage device. The first portion of the address may be associated with logical addresses of the data in a forward index. The forward index may omit the second portion of the physical addresses, which may reduce the memory overhead of the index and/or allow the forward index to reference larger storage devices. Data of a particular logical address may be accessed using the first portion of the physical address maintained in the forward index, and the second portion of the media address stored on the storage device.

Claims

1. A method, comprising:

arranging a plurality of data segments for storage at respective offsets within a storage unit of a solid-state storage medium;

mapping front-end addresses of the data segments to a physical address of the storage unit in a first index;

generating a second index for storage on the solid-state storage medium, wherein the second index is configured to associate front-end addresses of each of the plurality of data segments with respective offsets within the storage unit and wherein an entry of the second index includes a front-end address of a data segment of the plurality of data segments and indicates an offset of the data segment within the storage unit; and

accessing a requested data segment of the plurality of data segments, where accessing the requested data segment comprises;

performing a first translation comprising mapping a front-end address of the requested data segment to a physical address of the storage unit in the first index; and

performing a second translation comprising reading the second index stored at the physical address, and mapping the front-end address of the requested data segment to an offset of the requested data segment in the second index.

2. The method of claim 1, further comprising compressing one or more of the plurality of data segments for storage within the storage unit such that a compressed size of the compressed data segments differs from an uncompressed size of the data segments, wherein the offset of the data segment within the storage unit is based on the compressed size of the data segments.

3. The method of claim 1, further comprising storing the second index on the solid-state storage medium.

4. The method of claim 3, further comprising storing the second index on the storage unit comprising the plurality of data segments.

5. The method of claim 3, further comprising omitting the offset of the data segment from the first index.

6. The method of claim 1, wherein the data segment is associated with a particular front-end address, the method further comprising:

determining a storage address of the data segment by use of a storage unit address mapped to the particular front-end address in the first index and a data segment offset associated with the particular front-end address in the second index stored on the storage unit.

7. A non-transitory computer-readable storage medium comprising program instructions stored thereon, wherein the program instructions are executable by a computing system to cause the computing system to perform a method, comprising:

arranging a plurality of data segments for storage at respective offsets within a storage unit of a solid-state storage medium;

mapping front-end addresses of the data segments to a physical address of the storage unit in a first index;

generating a second index for storage on the solid-state storage medium, wherein the second index is configured to associate each of the plurality of data segments with a corresponding offset within the storage unit and wherein the second index is configured to associate the front-end address of the data segments with respective offsets of the data segments within the storage unit; and

accessing a requested data segment of the plurality of data segments by;

accessing a physical address of a storage unit mapped to the particular front-end address in the first index, and

reading the second index stored at the determined physical address to determine an offset of the requested data segment within the storage unit.

8. The non-transitory computer-readable storage medium of claim 7, wherein the method further comprises compressing one or more of the plurality of data segments for storage within the storage unit such that a compressed size of the compressed data segments differs from an uncompressed size of the data segments, wherein the offset of the data segment within the storage unit is based on the compressed size of the data segments.

9. The non-transitory computer-readable storage medium of claim 7, wherein the method further comprises storing the second index on the solid-state storage medium.

10. The non-transitory computer-readable storage medium of claim 9, wherein the method further comprises storing the second index on the storage unit comprising the plurality of data segments.

11. The non-transitory computer-readable storage medium of claim 9, wherein the method further comprises omitting the offset of the data segment from the first index.

12. The non-transitory computer-readable storage medium of claim 7, wherein the data segment is associated with a particular front-end address, and wherein the method further comprises determining a storage address of a data segment by:

mapping the particular front-end address to a storage unit address in the first index; and

determining the offset of the data segment by mapping the particular front-end address to an entry of the second index stored at the storage unit address.