METHOD AND APPARATUS FOR LARGE SCALE DATA STORAGE

• US 20100306269A1
• Filed: 05/24/2010
• Published: 12/02/2010
• Est. Priority Date: 05/26/2009
• Status: Active Grant

• Current Assignee: Pi-Coral Incorporated
• Original Assignee: Pi-Coral Incorporated
• Inventors: Osmond, Roger Frederick
• Granted Patent: US 9,015,198 B2
• Time in Patent Office: Days
• US Class Current: 707/792
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 16/113 Details of archiving lifecycle management in storage systems G06F3/0649; backup systems G06F11/1446
• 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/148 File search processing
• CPC Class Codes: G06F 16/18 File system types
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 16/188 Virtual file systems
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06F 2216/03 Data mining
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

A logical apparatus and associated methods provide highly scalable and flexible data storage in a network of computers. The apparatus provides flexible organizational and access control mechanisms and a practical and efficient way to work with smaller portions of a data storage system at a given time to enable sparse population, caching, paging and related functions. A data structure, called a virtual container, comprises references to objects stored in a data storage system such that the same object can be visible from different virtual containers, if such virtual containers hold references to said object. Access controls further enhance the effectiveness of the methods and structures to enable multiple simultaneous organizational schemes and selective sharing of objects. Participating nodes provide access to objects stored on said nodes and their participating peer nodes, employing the data storage apparatus, such that balance in the network is achieved by data placement decisions that may combine common constraints and a node'"'"'s individual self interest.

Claims

1. A logical data storage apparatus comprising:

a physical storage layer comprising data storage containers such as magnetic or optical disks, LUNs, and RAID groups;

a logical storage layer comprising logical data storage containers such as file systems, folders and directories;

a virtual storage layer comprising virtual containers,

wherein said virtual containers are complex data structures and,

wherein said virtual containers may contain a plurality of logical references to stored logical objects and,

wherein logical objects referenced in said virtual containers may be stored in one or more logical containers.

2. The apparatus of claim 1 wherein a virtual container may exist as a whole or in part on one or more than one physical computer systems and,

wherein the totality of parts constitutes at least the full contents of said virtual container.

3. The apparatus of claim 1 wherein an object stored in a virtual container may exist in whole or in part in one or more instances of said virtual container.

4. The apparatus of claim 1 wherein different instances (replicas) of the same object or the same container may be implemented differently on different storage nodes or in different logical containers.

5. The apparatus of claim 1 wherein different instances (replicas) of the same object or the same container may be populated to different extents on different storage nodes or in different logical containers.

6. The apparatus of claim 1 wherein an arrangement of virtual containers may be configured in such a manner as to appear to have an organizational structure such as a hierarchy or tree, a chain, a list, or a table.

7. The apparatus of claim 1 wherein ownership of a container implies ownership of stored objects contained within said container.

8. The method of claim 7 wherein access to stored objects may be restricted to exclude client access other than via references in virtual containers.

9. The method of claim 7 wherein the owner of a container may assign access rights to others.

10. The method of claim 7 wherein the owner of a container may assign access rights to others and,

wherein said access rights may be further constrained by policies of a second container that logically encloses the first container.

11. The apparatus of claim 1 wherein logical references in a container at the virtual storage layer may refer to objects stored in more than one logical container such as a file system, at the logical storage layer.

12. The apparatus of claim 1 wherein some objects, including but not limited to large objects, may be subdivided into multiple elements and,

wherein each element may be stored independently and,

wherein a client may refer to the separate parts or to the original object as a unit.

13. The apparatus of claim 1 wherein a container may hold references to related objects,

wherein said objects are of various and possibly dissimilar types or forms, such as text files, data files, audio files, videos, executable programs or virtual machine images and,

wherein said container may represent a complex object and,

wherein said object, a virtual container, may have a single identifier such as a URI by which clients may access it as a whole or access its constituent objects.

14. The apparatus of claim 1 wherein virtual containers may comprise:

multiple levels of indexable structures and associated mapping structures such as bitmaps,

wherein the lowest or final level of structures may contain, at each index position, an instance of or reference to a conventional data structure such as a hash table,

wherein said conventional data structure may contain references to or instances of stored objects

and,

wherein the levels other than the lowest or final level are indexed according to a sequence of indices generated for that purpose from a unique identifier representing a stored object.

15. A method as applied to the apparatus of claim 1 wherein a single hashing operation on an object'"'"'s unique identifier may yield a hash key comprising a sequence of digits wherein each digit may be used as an index into a structure at an associated.

16. The method of claim 15 wherein the maximum index value at any level does not exceed that which can be stored electronically in 16 bits (2 bytes).

17. The method of claim 15 wherein the maximum number of items at any layer other than the lowest or final layer does not exceed the maximum number of entries that can be stored in a directory or folder of a typical conventional file system such as NTFS, ext3.

18. A method as applied to the apparatus of claim 1 wherein the information describing the object, versus data contained within the object itself (“

object metadata”

), may be arranged such that a storage node may know the state of an object, with respect to presence and existence as follows;

known to not exist or,

known possibly to exist or,

known certainly to exist or,

present in the storage node'"'"'s addressable space.

19. The method of claim 18 wherein a storage node, having knowledge of the existence, non-existence or presence of an object may apply that knowledge such that said storage node may:

terminate a search for said object if said object is known to not exist or,

defer a search for said object if said object is known possibly or certainly to exist but is known not to be present or,

continue a search for said object if said object is known to be present.

20. The method of claim 18 wherein instances or replicas of a given virtual container may contain similar or dissimilar subsets of said virtual container'"'"'s contents and wherein a storage node having an instance of said virtual container.