Archival storage and retrieval system

• US 9,785,498 B2
• Filed: 06/17/2011
• Issued: 10/10/2017
• Est. Priority Date: 04/29/2011
• Status: Active Grant

• Current Assignee: TATA Consultancy Services Limited (Tata Sons Pvt Ltd.)
• Original Assignee: TATA Consultancy Services Limited (Tata Sons Pvt Ltd.)
• Inventors: Misra, Prateep, Roy, Nilanjan, Naskar, Soumitra
• Primary Examiner(s): Shanmugasundaram, Kannan
• Application Number:
  US14/113,806
• Publication Number:
  US 20140052706A1
• Time in Patent Office: 2,307 Days
• CPC Class Codes: G06F 11/1004 to protect a block of data words, e.g. CRC or checksum G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 11/3034 where the computing system component is a storage system, e.g. DASD based or network based digital input from or digital output to record carriers G06F3/06; digital recording or reproducing G11B20/18; 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], H04L67/1097
• CPC Class Codes: G06F 11/3055 Monitoring arrangements for monitoring the status of the computing system or of the computing system component, e.g. monitoring if the computing system is on, off, available, not available error or fault processing without redundancy G06F11/0703; error detection or correction by redundancy in data representation G06F11/08; error detection or correction by redundancy in operation G06F11/14; error detection or correction by redundancy in hardware G06F11/16
• 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/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 16/1837 Management specially adapted to peer-to-peer storage networks topology management mechanisms of peer-to-peer networks H04L67/1042
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0617 in relation to availability
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

A highly reliable data archival and retrieval method that enables fine grained control over data availability is implemented across a Quality of Service driven archival system, configured to fragment the data into data and parity chunks for storing onto the storage node. The technique employed by the archival system enables files to be read without having need to access any metadata, thereby tolerating complete loss of such metadata. Further, the Quality of Service driven system architecture improves upon the system performance and throughput by means of a storage node regeneration process which ensures balanced load on participating storage node during various storage, retrieval and regeneration operations.

Claims

1. A file storage and retrieval system comprising:

a processing unit;

a plurality of storage nodes; and

a memory storing instructions, wherein the processing unit is configured to execute the instructions to;

receive a Quality of Service (QoS) levels and uniform resource name for a file enabling fine grained control over file availability stored across the plurality of storage nodes;

determine k data chunks and m parity chunks fragmented from file chunks by a file encoding and placement scheme wherein the QoS level associated with the each file specifies presence of desired number m_d of parity chunks and ensures total number of available chunks for any file to be above k+m_min chunks wherein m_min<

m_d;

determine a file chunk Uniform Resource Name (URN) for the k data chunks and m parity chunks;

determine a hash for each of the file chunk URNs;

determine a node key for each of the plurality of storage nodes using a hash function; and

store the k data chunks and m parity chunks across the plurality of storage nodes based on the node keys and the hashs for the file chunks;

a monitoring engine to track the status of lost file chunks stored on any one of the storage nodes for their participation in input/output operations performed on the system and regeneration mechanism on the lost chunks wherein regeneration is delayed as long as minimum number of available chunks is greater than k+m_min.

2. The system of claim 1, wherein the file is fragmented into data chunks and parity chunks by erasure encoding technique, and wherein the data chunks and parity chunks are used to reconstruct the file during file retrieval.

3. The system of claim 1, wherein the QoS level is specified by number of parity chunks and a minimum number of chunks that must always be available in the system.

4. The system of claim 1, wherein the number of data chunks remains fixed for all files of the system while the number of parity chunks vary based on the QoS level.

5. The system of claim 1, wherein a load balancer distributes encoding and decoding load uniformly across of the plurality of front end nodes.

6. The system of claim 1, wherein storing the file chunks includes comparing the hash of a file chunk URN with a node key of a storage node for placing the file chunk on the storage node such that no two data chunks reside on the same storage node.

7. The system of claim 1, wherein the storage node includes at least one of a physical machine with direct attached disks, a physical machine with network attached disks, and virtual machines with virtual disks or a program that access a cloud storage device.

8. The system of claim 1, wherein the storage nodes are further configured to perform regeneration of lost file chunks for subsequent storage of regenerated chunks.

9. The system of claim 1, wherein metadata corresponding to the file chunks is stored in one or more metadata servers and at least a portion of the metadata is also stored in the file chunks.

10. The system of claim 9, wherein the metadata includes at least one of file URN, desired QoS level, object owner and its creation time, checksum of original file, fragmented chunks, and the chunk header.

11. The system of claim 9, wherein the metadata is used when performing a lookup operation for the files.

12. The system of claim 1, wherein hash values are used as a checksum for the data chunks and the parity chunks during retrieval and regeneration.

13. The system of claim 9, wherein the metadata is stored in a hierarchical directory structure in the metadata server.

14. The system of claim 1, wherein a status of the file chunks is reported or dynamically updated as active, inactive, degraded or dead to trigger subsequent regeneration mechanism.