EFFICIENT DATA OBJECT STORAGE AND RETRIEVAL

• US 20130290648A1
• Filed: 04/27/2012
• Published: 10/31/2013
• Est. Priority Date: 04/27/2012
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Goodson, Garth R., Shao, Minglong
• Granted Patent: US 8,793,466 B2
• Time in Patent Office: Days
• US Class Current: 711/154
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 12/04 Addressing variable-length words or parts of words
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0626 Reducing size or complexity of storage systems
• CPC Class Codes: G06F 3/0667 at data level, e.g. file, record or object virtualisation
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: G11B 27/11 by using information not detectable on the record carrier

Abstract

A data storage system includes a processor, a system memory, and logical extents. Blocks of storage in one or more physical storage devices are allocated to each of the logical extents. The processor maintains a logical container for data objects and the volume includes one or more of the logical extents. The processor stores data objects that are uniquely identified by object identifiers in the logical extents. The processor also maintains a first index that is stored in the system memory and maps a range of the object identifiers to a second index. The second index is also stored in a logical extent and indicates storage locations of the data objects associated with the range of the object identifiers.

Claims

1. A method, comprising:

in a data storage system, maintaining a logical container for a plurality of data objects, wherein the data objects are stored in one or more of a plurality of logical extents of the data storage system and the data objects are uniquely identified by object identifiers; and

maintaining first and second indexes for locating the data objects, wherein;

the first index maps a first range of the object identifiers to the second index; and

the second index indicates storage locations of the data objects associated with the first range of the object identifiers.

2. The method of claim 1, wherein the first index is stored in a solid state memory of the data storage system and the second index is stored in an extent of the plurality of logical extents.

3. The method of claim 1, wherein the plurality of logical extents each comprises at least a portion of one or more slabs, each slab defined as a set of blocks of storage in one or more physical storage devices.

4. The method of claim 1, wherein:

the first index maps a second range of the object identifiers to a third index; and

the third index indicates storage locations of each of the data objects associated with the second range of the object identifiers.

5. The method of claim 4, wherein the second index and the third index are stored in different logical extents.

6. The method of claim 1, wherein the first index maps the first range of the object identifiers to the second index by providing:

an identifier for an extent in which the second index is stored; and

an offset within the extent in which the second index is stored.

7. The method of claim 6, wherein indicating the storage locations of the data objects includes providing:

identifiers of extents in which each of the data objects of the first range are stored;

offsets within each of the extents in which each of the data objects of the first range are stored; and

lengths of each of the data objects of the first range.

8. The method of claim 1, wherein the storage locations of the data objects indicated in the second index are arranged in sequential order based on the associated object identifiers.

9. The method of claim 4, further comprising:

receiving a client request for one of the data objects;

selecting, from among the first range and the second range, a range associated with the requested data object;

determining a storage location of the requested data object from the second index if the selected range is the first range or determining the storage location of the requested data object from the third index if the selected range is the second range; and

retrieving the requested data object from the determined storage location.

10. The method of claim 1, further comprising:

receiving a new data object from a client to be stored in the data storage system;

allocating storage space in one of the plurality of logical extents;

writing the new data object to the allocated storage space; and

updating the first and the second indexes based on a location of the allocated storage space.

11. The method of claim 10, wherein the new data object is received from the client as a plurality of blocks and the storage space is not allocated until all of the blocks are received.

12. A data storage system, comprising:

a system memory;

a plurality of logical extents, wherein one or more blocks of storage in one or more physical storage devices are allocated to each of the plurality of logical extents; and

a processor configured to;

maintain a volume as a logical container for a plurality of data objects, wherein the volume includes one or more of the logical extents;

store data objects in one or more of the plurality of logical extents, wherein the data objects are uniquely identified by object identifiers;

maintain a first index, wherein the first index is stored in the system memory and maps a first range of the object identifiers to a second index; and

maintain the second index, wherein the second index is stored in a logical extent of the logical extents and indicates storage locations of the data objects associated with the first range of the object identifiers.

13. The data storage system of claim 12, wherein:

the first index maps a second range of the object identifiers to a third index; and

the third index indicates storage locations of each of the data objects associated with the second range of the object identifiers.

14. The data storage system of claim 13, wherein the second index and the third index are stored in different logical extents.

15. The data storage system of claim 12, wherein the first index maps the first range of the object identifiers to the second index by providing:

an identifier for an extent in which the second index is stored; and

an offset within the extent in which the second index is stored.

16. The data storage system of claim 15, wherein indicating the storage locations of the data objects includes providing:

identifiers of extents in which each of the data objects of the first range are stored;

offsets within each of the extents in which each of the data objects of the first range are stored; and

lengths of each of the data objects of the first range.

17. The data storage system of claim 12, wherein the storage locations of the data objects indicated in the second index are arranged in sequential order based on the associated object identifiers.

18. The data storage system of claim 13, wherein, in response to a client request for a data object, the processor is further configured to:

select, from among the first range and the second range, a range associated with the requested data object;

determine a storage location of the requested data object from the second index if the selected range is the first range or determine the storage location of the requested data object from the third index if the selected range is the second range.

19. The data storage system of claim 12, wherein the processor is further configured to:

receive a new data object from a client to be stored in the data storage system;

assign a new object identifier to the new data object;

allocate storage space in one of the plurality of logical extents;

write the new data object to the allocated storage space; and

update the first and the second indexes.

20. The data storage system of claim 19, wherein the new data object is received from the client as a plurality of blocks and the storage space is not allocated and the data object is not written until all of the blocks are received.

21. The data storage system of claim 12, wherein additional metadata associated with one of the data objects is stored with the data object.

22. A non-transitory machine-readable medium comprising instructions that, when executed by one or more processors, direct the one or more processors to:

in a data storage system, define a plurality of regions to contain data objects, the plurality of regions including a plurality of logical extents, wherein allocated to each said logical extent is at least a portion of one or more slabs allocated to a region that includes said logical extent, each said slab defined as a set of blocks of storage in one or more physical storage devices;

in the data storage system, maintain a plurality of volumes as logical containers of data, each of the volumes including one or more of the logical extents from one or more of the regions, wherein layouts of the logical extents within the regions are not visible to the plurality of volumes; and

maintain a first index in which a first group of unique object identifiers associated with a first group of the data objects is mapped to a second index and a second group of unique object identifiers associated with a second group of the data objects is mapped to a third index, wherein;

the first index is stored in solid state memory;

the second index is stored in one of the logical extents and indicates storage locations of the data objects of the first group; and

the third index is stored in another of the logical extents and indicates storage locations of the data objects associated with the second group.

23. The non-transitory machine-readable medium of claim 22, wherein the first index maps the first group of the object identifiers to the second index by providing:

an identifier for an extent in which the second index is stored; and

an offset within the extent in which the second index is stored.

24. The non-transitory machine-readable medium of claim 23, wherein indicating the storage locations of the data objects includes providing:

identifiers of extents in which each of the data objects of the first group are stored;

offsets within each of the extents in which each of the data objects of the first group are stored; and

lengths of the data objects.

25. The non-transitory machine-readable medium of claim 22, wherein the storage locations of the data objects indicated in the second and the third indexes are arranged in sequential order based on the associated object identifiers.

26. The non-transitory machine-readable medium of claim 22, wherein the instructions further direct the one or more processors to:

receive a request for a data object from a storage client;

select, from among the first group and the second group, a group associated with the requested data object; and

determine a storage location of the requested data object from the second index if the selected group is the first group or determine the storage location of the requested data object from the third index if the selected group is the second group.

27. The non-transitory machine-readable medium of claim 22, wherein the instructions further direct the one or more processors to:

receive a new data object from a client to be stored in the data storage system, wherein the new data object is received as a plurality of blocks;

allocate storage space in one of the plurality of logical extents after all of blocks are received; and

write the new data object to the allocated storage space.

28. A method, comprising:

in a data storage system, using a multi-level index for tracking locations of a plurality of data objects stored in a logical data container, the multi-level index including a first index and a second index mapped to the first index;

maintaining the first index in its entirety in a solid state memory in the data storage system;

maintaining the second index in a persistent mass storage facility separate from the solid state memory; and

accessing a logical extent in the persistent mass storage to retrieve one of the plurality of data objects by no more than two storage I/O operations, wherein said accessing includes using information contained in the first index and the second index to identify a storage location of said one of the plurality of data objects.

29. The method of claim 28 wherein the plurality of data objects are each uniquely identified by object identifiers and the first index maps a range of the object identifiers to the second index.

30. The method of claim 29 wherein the second index indicates storage locations of the data objects associated with the range.