Method and system for managing distributed content and related metadata

• US 20020133491A1
• Filed: 10/26/2001
• Published: 09/19/2002
• Est. Priority Date: 10/26/2000
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Prismedia Networks Incorporated
• Inventors: Cho-Hung Chan, Desmond, Huang, Tsan-Fung, Mills, George Harlow, Sim, Siew Yong, Flood, James C. Jr., Orzen, Matthew, Isaacson, Trygve, Chai, Wencheng
• Granted Patent: US 7,272,613 B2
• Time in Patent Office: Days
• US Class Current: 707/10
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/1014 based on the content of a request
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 67/1034 Reaction to server failures by a load balancer
• CPC Class Codes: H04L 69/14 Multichannel or multilink protocols
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

The invention provides a method and system for creating an innovative file system that separates its directory presentation from its data store. The method and system include processing, division, distribution, managing, synchronizing, and reassembling of file system objects that does not delay the presentation of the content to the user, but also uses a reduced amount of storage space. The invention includes the ability to manage and control the integrity of the files distributed across the network, and the ability to serve and reconstruct files in real time using a Virtual File Control System.

Claims

1. A method of efficiently managing storage in a distributed network having a plurality of connected nodes comprising the steps of:

determining when a certain file storage parameter exceeds a pruning threshold; and

performing a pruning cycle including;

(a) identifying the content components associated with the storage;

(b) selectively pruning the content components based at least in part on usage statistics so that the file storage parameter is reduced to below the pruning threshold; and

(c) updating metadata associated with the content components to reflect the updated storage system parameters.

2. The method of claim 1, further comprising the step of:

presenting the contents of the updated storage network as a virtual file system so that all the files appear locally accessible to any node.

3. The method of claim 2, further comprising the step of:

serving the files to users independent of the physical location of the content components.

4. The method of claim 3, further comprising the step of:

serving the files to users at substantially the same rate as would be possible if the entire file was stored locally.

5. The method of claim 4, wherein:

the serving step requires less aggregated network communication traffic that would be required if the whole file were to be served to the user from a single node.

6. The method of claim 3, wherein:

the serving step is performed in parallel with the pruning step.

7. The method of claim 1, wherein the determining step includes the steps of:

i. monitoring total available storage;

ii. monitoring file distribution traffic, including the rate of arrival of new content at a node and the current local size of each file; and

iii. monitoring the usage of individual files over time.

8. The method of claim 1, wherein the determining step includes the steps of:

i. periodically calculating the available storage and predicted file distribution rate; and

ii. re-calculating the pruning threshold.

9. The method of claim 1, wherein the determining step includes the steps of:

i. periodically calculating a pruning frequency based at least in part on the predicted file distribution rate; and

ii. periodically performing the pruning cycle based on the pruning frequency.

10. The method of claim 1, wherein the determining step includes the steps of:

i. periodically calculating a pruning frequency based at least in part on the network traffic; and

ii. periodically performing the pruning cycle based on the pruning frequency.

11. The method of claim 8, wherein the re-calculating step includes the step of:

applying dynamically selected criteria to rank and select files for pruning, wherein the criteria are based at least in part on a cost function.

12. The method of claim 8, wherein the re-calculating step includes the step of:

applying dynamically selected criteria to rank and select files for pruning, wherein the criteria include total available storage, file distribution traffic, and the usage of individual files over time.

13. The method of claim 8, wherein the re-calculating step includes the step of:

applying dynamically selected criteria to rank and select files for pruning, wherein the criteria are based at least in part on total inter-node network traffic, reducing peak inter-node network traffic, reducing total cost of inter-node network traffic, reducing computational overhead, and ensuring delivery of the files within a predetermined criteria.

14. The method of claim 7, wherein the determining step further the steps of:

(d) calculating the content components that must be stored locally in order to meet predetermined network and delivery criteria; and

(e) calculating the amount of the file that can be pruned while meeting the predetermined network and delivery criteria.

15. The method of claim 8, wherein the determining step further the steps of:

(c) calculating the content components that must be stored locally in order to meet predetermined network and delivery criteria; and

(d) calculating the amount of the file that can be pruned while meeting the predetermined network criteria.

16. The method of claim 11, wherein the determining step further the steps of:

(c) calculating the content components that must be stored locally in order to meet predetermined network and delivery criteria; and

(d) calculating the amount of the file that can be pruned while meeting the predetermined network and delivery criteria.

18. The computer program product of claim 17, further comprising a routine configured to:

present the contents of the updated storage network as a virtual file system so that all the files appear locally accessible to any node.

19. The computer program product of claim 18, further comprising a routine configured to:

serve the files to users independent of the physical location of the content components.

20. The computer program product of claim 19, further comprising a routine configured to:

serve the files to users at substantially the same rate as would be possible if the entire file was stored locally.

21. The computer program product of claim 20, wherein the routine configured to serve the files requires less aggregated network communication traffic that would be required if the whole file were to be served to the user from a single node.

22. The computer program product of claim 19, wherein the routine configured to serve is performed in parallel with the pruning cycle.

23. The computer program product of claim 17, wherein the determine routine includes routines configured to:

i. monitor total available storage;

ii. monitor file distribution traffic, including the rate of arrival of new content at a node and the current local size of each file; and

iii. monitor the usage of individual files over time.

24. The computer program product of claim 17, wherein the determine routine includes routines configured to:

i. periodically calculate the available storage and predicted file distribution rate; and

ii. re-calculate the pruning threshold.

25. The computer program product of claim 17, wherein the determine routine includes routines configured to:

i. periodically calculate a pruning frequency based at least in part on the predicted file distribution rate; and

ii. periodically perform the pruning cycle based on the pruning frequency.

26. The computer program product of claim 17, wherein the determine routine includes routines configured to:

i. periodically calculate a pruning frequency based at least in part on the network traffic; and

ii. periodically perform the pruning cycle based on the pruning frequency.

27. The computer program product of claim 24, wherein the re-calculating routine includes a routine configured to:

apply dynamically selected criteria to rank and select files for pruning, wherein the criteria are based at least in part on a cost function.

28. The computer program product of claim 24, wherein the re-calculating routine includes a routine configured to:

apply dynamically selected criteria to rank and select files for pruning, wherein the criteria include total available storage, file distribution traffic, and the usage of individual files over time.

29. The computer program product of claim 24, wherein the re-calculating routine includes a routine configured to:

apply dynamically selected criteria to rank and select files for pruning, wherein the criteria are based at least in part on total inter-node network traffic, reducing peak inter-node network traffic, reducing total cost of inter-node network traffic, reducing computational overhead, and ensuring delivery of the files within a predetermined criteria.

30. The computer program product of claim 23, wherein the determine routine includes routines configured to:

(d) calculate the content components that must be stored locally in order to meet predetermined network and delivery criteria; and

(e) calculate the amount of the file that can be pruned while meeting the predetermined network and delivery criteria.

31. The computer program product of claim 24, wherein the determine routine includes routines configured to:

(c) calculate the content components that must be stored locally in order to meet predetermined network and delivery criteria; and

(d) calculate the amount of the file that can be pruned while meeting the predetermined network criteria.

32. The computer program product of claim 27, wherein the determine routine includes routines configured to:

(c) calculate the content components that must be stored locally in order to meet predetermined network and delivery criteria; and

(d) calculate the amount of the file that can be pruned while meeting the predetermined network and delivery criteria.

17. A computer program product for efficiently managing storage in a distributed network having a plurality of connected nodes wherein the computer program product comprises a plurality of routines configured to:

determine when a certain file storage parameter exceeds a pruning threshold; and

perform a pruning cycle including;

(a) identifying the content components associated with the storage;

(b) selectively pruning the content components based at least in part on usage statistics so that the file storage parameter is reduced to below the pruning threshold; and

(c) updating metadata associated with the content components to reflect the updated storage system parameters.

33. A method for distributing a file system object in a network having a plurality of network nodes comprising steps of:

(a) receiving a request to distribute a file system object;

(b) processing the request to generate metadata based on the requested file system object;

(c) distributing metadata and at least a portion of the file system object to a plurality of qualifying nodes based on distribution criteria; and

(d) integrating metadata in respective meta file systems in the qualifying nodes to represent the distribution of the file system object.

35. The method of claim 34, wherein in response to the distribution command, the receiving node issues a command to download a portion of the related file system object.

36. The method of claim 34, wherein the file distribution command comprises a distribution protocol command including any one or more of the following commands:

Put, Distribute, Replicate, Get, Prepare, Search, Remove, Clean, Info, Learn, Fetch, Fetch Info, and Stop.

38. The method of claim 37, wherein the file system object change is a change which adds a new volume or directory, and wherein said updating step includes at least one of creating a directory as a sub-directory into the meta file system structure so that the sub-directory presents the new volume or directory, or replacing the associated metadata.

34. A method for propagating a distribution command related to file system object changes in a network having a plurality of network nodes comprising steps of, at each network node:

(a) creating a distribution map containing distribution criteria for a respective node;

(b) forwarding the distribution command to a qualified set of neighbors in part based on the distribution map; and

(c) in response to the distribution command, managing storage and meta file system in the network nodes, and issuing the same command to another qualified set of neighbors to represent the distribution of information across network nodes.

37. A method for building meta file systems for directories and volumes, comprising:

(a) receiving a file system object change request from a user or from another node;

(b) processing the change request to generate associated metadata;

(c) distributing a command containing information regarding file system object change to a plurality of qualified nodes that meet a distribution criteria, the information including file system object metadata;

(d) receiving file system object metadata; and

(e) updating the meta file system structure to represent the file system object change.

39. A method for building meta file system for files, comprising:

(a) receiving new file object or file object change request from a user or from another node;

(b) processing the file object or file object change request to generate metadata;

(c) distributing a command related to the changes to a plurality of nodes based on distribution criteria, the command including file object metadata;

(d) receiving file object metadata;

(e) adding a block index array into the received file object metadata;

(f) placing the file object metadata in an appropriate directory within the meta file system;

(g) storing some block files of the file object in at least one storage device; and

(h) updating block index arrays in respective network nodes based on the distribution map.

40. A method for deleting a file object, comprising

(a) receiving a delete request from a user or from another node to delete the file object;

(b) locate the metadata of the file object;

(c) distributing a command related to the delete request to a plurality of nodes based on distribution criteria;

(d) removing metadata from the meta file system to represent deletion of the file system object; and

(e) removing block files from block storage device corresponding to the file system object requested to be deleted.

41. A method for deleting a file system object, comprising

(a) receiving a delete request from a user or from another node

(b) locate the metadata of the file system object;

(c) distributing a command related to the deletion to a plurality of nodes based on distribution criteria;

(d) removing metadata from a meta file system;

(e) removing a directory from the meta file system that corresponds to the deleting of the file system object.

42. A method for re-locating a file system object in a metwork, comprising:

(a) receiving a re-location request from a user or from another node;

(b) locate the metadata of the file system object;

(c) distributing a command related to the re-location of the object to a plurality of nodes based on a distribution criteria;

(d) changing the metadata of the file system object and all the other related objects in the directory the corresponds to the file system object being re-located; and

(e) relocating the file system object from one location of the meta file system to another location within the meta file system in accordance with the re-location request.

43. A method for applying distribution policies when distributing a file system object, comprising:

(a) configuring a set of distribution policies;

(b) looking up at least one distribution policy using parameters that apply to the distribution; and

(c) allocating network and storage resources based on the distribution policy.

44. A method for storing multiple data blocks associated to a file in a plurality of storage devices, comprising:

(a) creating a block storage indexing array with the number of cells equivalent to the total number of blocks that made up the file;

(b) marking cells that do not have an associated data block with a zero value;

(c) storing data blocks into a plurality of storage devices and indicates in the appropriate cells in the array the index number of the storage devices; and

(d) naming the data block using a hashing algorithm and node-limited path.

45. A method for serving a random request to a file in a network node, comprising:

(a) calculating a cell position in an appropriate block index array using a requesting offset and number of bytes to read;

(b) applying a hashing algorithm using a device index in a cell;

(c) reading data from a block file; and

(d) serving the data.

46. A method for serving random request to a file in a network node, comprising:

(a) calculating a cell position in an appropriate block index array using the requesting offset and number of bytes to read;

(b) issuing a PREPARE command to download the requesting blocks from remote nodes in a network;

(c) downloading the blocks from remote nodes in parallel;

(d) storing data blocks into a plurality of storage devices and indicating in the appropriate cells in the array the index number of the storage devices;

(e) naming the data block using a hashing algorithm and node-limited path; and

(f) serving the data.

47. A method for applying file server policy when serving a file system, comprising:

(a) configuring a set of service policies based on a set of parameters;

(b) looking up at least one policy using at least one parameter; and

(c) applying each policy by allocating network and storage resources for the service.

48. A method for separating a file system presentation of content from storge of the content, comprising:

storing content in storage devices across network nodes; and

using a meta file system and metadata at each node to associate a file system view with data stored in storage devices across the network nodes.

49. A method for building an virtual in-memory file system that includes an overlay file system, comprising:

(a) loading meta file system and metadata to create a file system presentation;

(b) caching meta information that associates the virtual file system objects to the data stored in a plurality of storage devices; and

(c) serving file system requests by mapping the requests to the actual data in the storage using cached meta information.

50. A method for building a scalable virtual in-memory file system that includes selective and dynamic caching of a virtual file control system:

(a) loading part of meta file system and metadata to create a file system presentation;

(b) caching part of the information that associates the virtual file system objects to the data stored in a plurality of storage devices;

(c) serving file system requests by mapping the requests to the actual data in the storage using cached meta information if information exists in a cache;

(d) if information does not exist in cache, tearing down part of the file system presentation information and removing part of the cache that are least frequently accessed, and loading the requesting metadata to re-construct a partial file system presentation that request by users; and

(e) serving file system requests by mapping the requests to the actual data in the storage.

51. A method for dividing a large file for storage and distribution in an SCDN comprising:

dynamically selecting a block size during storage and distribution of content across nodes of the SCDN, including;

using an optimum block size that reduces or avoids storage fragmentation, maximizes transfer efficiency, and is not significantly larger than a “

flash interval”

.

52. A method for aggregating a storage and file system from a plurality of servers comprising:

(a) receiving a file system request to add, delete, or modify a file system object at a first node;

(b) processing the file system request to generate metadata;

(c) distributing the metadata and subset of file system object received at the first node to a plurality of nodes;

(d) integrating information from the first node to receiving nodesa;

(e) receiving a file system request to add, delete, or modify a file system object at a second node in the set of receiving nodes;

(f) processing the file system request to generate metadata;

(g) distributing the metadata and subset of file system object received at the first node to a second plurality of nodes which include the first node; and

(h) integrating metadata information from the second node to the second set of nodes.