Method for efficient storing of sparse files in a distributed cache

• US 20040117437A1
• Filed: 12/16/2002
• Published: 06/17/2004
• Est. Priority Date: 12/16/2002
• Status: Abandoned Application

• Current Assignee: Exanet Ltd (Dell Technologies Inc.)
• Original Assignee: Exanet Ltd (Dell Technologies Inc.)
• Inventors: Frank, Shahar
• Application Number:
  US10/319,494
• Publication Number:
  US 20040117437A1
• Time in Patent Office: Days
• US Class Current: 709/203
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/288 Distributed intermediate devices, i.e. intermediate devices for interaction with other intermediate devices on the same level
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]

Abstract

A method for performing efficient caching of sparse files in a distributed cache by use of an enumeration process is provided. According to the disclosed invention, the storage'"'"'s objects are cached in the order that these objects are kept in the storage'"'"'s directory. As a result, the directory content is enumerated in the cache, resulting in the cache not having to be associated with the server layout.

Claims

1. A method for caching sparse files in a distributed storage system, the distributed storage system comprising at least one client terminal and at least one storage node, the storage node comprising at least a storage means and a cache, wherein the method comprises:

receiving location information for a requested file;

searching the cache for the requested file;

if the requested file is not found in the cache, then fetching data chunks of the requested file from the storage means and updating the cache with the retrieved file;

if the requested file is found in the cache, then checking if the data chunks comprising the data of the requested file in the cache are in sequence, and if the data chunks are not in sequence, then fetching the missing data chunks from the storage means and updating the cache with the retrieved data chunks; and

returning the requested file to the client terminal.

2. The sparse file caching method as claimed in claim 1, wherein said location information is received from at least one of a client terminal, a computer server and a mapping means.

3. The sparse file caching method as claimed in claim 1, wherein the storage node is at least one of a host, a server, a file server, a file-system, a location independent file system and a geographically distributed computer system.

4. The sparse file caching method as claimed in claim 1, wherein the cache is least one of a skip-list based cache, a balanced tree based cache and a hash file based cache.

5. The sparse file caching method as claimed in claim 1, wherein the sparse file comprises a plurality of data chunks and at least a single space block.

6. The sparse file caching method as claimed in claim 5, wherein the plurality of data chunks occupies significantly less space then the single space block.

7. The sparse file caching method as claimed in claim 1, wherein the data chunk comprises a portion of the sparse file that contains valuable data.

8. The sparse file caching method as claimed in claim 1, wherein said method further comprises data chunk sequence means.

9. The sparse file caching method as claimed in claim 8, wherein said sequence means are at least a sequence flag associated with said data chunk.

10. The sparse file caching method as claimed in claim 1, wherein the sparse file is at least one of a snapshot file and a database file.

11. The sparse file caching method as claimed in claim 1, wherein the location information comprises at least a start address of the requested file.

12. The sparse file caching method as claimed in claim 11, wherein the location information further comprises the byte size of the requested file.

13. The sparse file caching method as claimed in claim 11, wherein the search in the cache for the requested file begins from the start address of the requested file.

14. The sparse file caching method as claimed in claim 1, wherein the location information comprises at least a start address of the requested file and an end address of the requested file.

15. The sparse file caching method as claimed in claim 14, wherein the search in the cache for the requested file begins from the start address of the requested file.

16. The sparse file caching method as claimed in claim 1, wherein checking if the data chunks are in sequence comprises checking the status of the sequence means associated with each of the data chunks.

17. The sparse file caching method as claimed in claim 1, wherein updating the cache comprises:

saving the data chunk fetched from the storage means in the cache; and

marking the sequence means associated with the data chunk as sequenced.

18. The sparse file caching method as claimed in claim 17, wherein saving the data chunk comprises allocating memory in the cache to fit the size of the data chunk.

19. Computer executable code for efficiently caching sparse files in a distributed storage system, the distributed storage system comprising at least one client terminal and at least one storage node, the storage node comprising a storage means and a cache, the code comprising:

a first portion of executable code that, when executed, receives location information for a requested file;

a second portion of executable code that, when executed, searches the cache for the requested file;

a third portion of executable code that, when executed, fetches the data chunks of the requested file from the storage means and updates the cache with the retrieved file, if the requested file is not found in the cache;

a fourth portion of executable code that, when executed, checks if the data chunks comprising the data of the requested file in the cache are in sequence, and if the data chunks are not in sequence, then fetches the missing data chunks from the storage means and updates the cache with the retrieved data chunks, if the requested file is found in the cache; and

a fifth portion of executable code that, when executed, returns the requested file to the client terminal.

20. The computer executable code as claimed in claim 19, wherein said location information is received from one of:

client terminal, a server, and mapping means.

21. The computer executable code as claimed in claim 19, wherein the storage node is at least one of a host, a server, a file server, a file-system, a location independent file system and a geographically distributed computer system.

22. The computer executable code as claimed in claim 19, wherein the cache is least one of a skip-list based cache, a balanced tree based cache and a hash file based cache.

23. The computer executable code as claimed in claim 19, wherein the sparse file comprises a plurality of data chunks and at least a single space block.

24. The computer executable code as claimed in claim 23, wherein the plurality of data chunks occupies significantly less space than the single space block.

25. The computer executable code as claimed in claim 19, wherein the data chunk comprises a portion of the file that contains a valuable data.

26. The computer executable code as claimed in claim 19, wherein sequence means are associated with each data chunk.

27. The computer executable code as claimed in claim 26, wherein said sequence means are at least a sequence flag.

28. The computer executable code as claimed in claim 19, wherein the sparse file is at least one of a snapshot file and a database file.

29. The computer executable code as claimed in claim 19, wherein the location information of the requested file comprises a start address of the requested file.

30. The computer executable code as claimed in claim 29, wherein the location information further comprises the byte size of the requested file.

31. The computer executable code as claimed in claim 24, wherein the second portion of executable code searches the cache starting from the start address of the requested file.

32. The computer executable code as claimed in claim 19, wherein the location information of the requested file comprises a start address of the requested file and an end address of the requested file.

33. The computer executable code as claimed in claim 31, wherein the second portion of executable code searches the cache starting from the start address of the requested file.

34. The computer executable code as claimed in claim 19, wherein the fourth portion of executable code checks if the data chunks are in sequence by determining the status of the sequence means associated with each of the data chunks.

35. The computer executable code as claimed in claim 19, wherein the fourth portion of executable code updates the cache by:

saving the data chunk fetched from the storage means in the cache; and

marking the sequence means associated with the data chunk as sequenced.

36. The computer executable code as claimed in claim 35, wherein saving the data chunk comprises allocating memory in the cache to fit the size of the data chunk.

37. A computer system capable of caching efficiently sparse files, the computer system comprising:

a cache adapted for storing variable size data chunks and further adapted to hold data chunks in a linked sequence;

a storage means capable of storing and retrieving the data chunks; and

the computer system being capable of being connected to at least one file requesting means via a network.

38. The computer system as claimed in claim 37, wherein said file requesting means are at least one of a client terminal, a server and mapping means.

39. The computer system as claimed in claim 37, wherein the network is at least one of a local area network, a wide area network and a geographically distrusted network.

40. The computer system as claimed in claim 37, wherein the computer system is at least one of a host, a file server, a file system and a location independent file system.

41. The computer system as claimed in claim 40, wherein the computer system is at least part of a geographically distributed computer system.

42. The computer system as claimed in claim 37, wherein the cache is least one of a skip-list based cache, a balanced tree based cache and a hash file based cache.

43. The computer system as claimed in claim 37, wherein, in order to cache sparse files, the computer system is adapted to:

receive location information for a requested file;

search the cache for the requested file;

if the requested file is not found in the cache, then fetch data chunks of the requested file from the storage means and update the cache with the retrieved file;

if the requested file is found in the cache, then check if the data chunks comprising the data of the requested file in the cache are in sequence, and if the data chunks are not in sequence, then fetch the missing data chunks from the storage means and update the cache with the retrieved data chunks; and

return the requested file to the client terminal.

44. The computer system as claimed in claim 43, wherein said location information is received from one of:

client terminal, computer server, mapping means.

45. The computer system as claimed in claim 43, wherein the sparse file comprises a plurality of data chunks and at least a single space block.

46. The computer system as claimed in claim 45, wherein the plurality of data chunks occupies significantly less space than the at least a single space block.

47. The computer system as claimed in claim 43, wherein the data chunk comprises a portion of the file that contains valuable data.

48. The computer system as claimed in claim 43, wherein the data chunk is further associated with sequence means.

49. The computer system as claimed in claim 48, wherein said sequence means are at least a sequence flag.

50. The computer system as claimed in claim 43, wherein the sparse file is at least one of a snapshot file and a database file.

51. The computer system as claimed in claim 43, wherein the location information of the requested file comprises a start address of the requested file.

52. The computer system as claimed in claim 51, wherein the location information further comprises the byte size of the requested file.

53. The computer system as claimed in claim 51, wherein the searching the cache for the requested file begins from the start address of the requested file.

54. The computer system as claimed in claim 43, wherein the location information of the requested file comprises at least a start address of the requested file and an end address of the requested file.

55. The computer system as claimed in claim 54, wherein the searching the cache for the requested file begins from the start address of the requested file.

56. The computer system as claimed in claim 43, wherein updating the cache comprises:

saving the data chunk fetched from the storage means in the cache;

marking the sequence means associated with the data chunk as sequenced.

57. The computer system as claimed in claim 56, wherein saving the data chunk comprises allocating memory in the cache to fit the size of the item.

58. A computer system adapted to caching sparse files, the computer system comprising:

a processor;

a cache;

a storage means;

a memory comprising software instructions adapted to enable the computer system to;

receiving location information for a requested file;

searching the cache for the requested file;

if the requested file is not found in the cache, then fetching data chunks of the requested file from the storage means and updating the cache with the retrieved file;

if the requested file is found in the cache, then checking if the data chunks comprising the data of the requested file in the cache are in sequence, and if the data chunks are not in sequence, then fetching the missing data chunks from the storage means and updating the cache with the retrieved data chunks; and

returning the requested file to a client terminal.

59. The computer system as claimed in claim 58, wherein checking if the data chunks are in sequence comprises checking the status of a sequence means associated with each of the data chunks.

60. The computer system as claimed in claim 58, wherein updating the cache comprises:

saving the data chunk fetched from the storage means in the cache; and

marking a sequence means associated with the data chunk as sequenced.

61. The computer system as claimed in claim 60, wherein saving the data chunk comprises allocating memory in the cache to fit the size of the data chunk.

62. A computer program product for caching sparse files, the computer program product comprising:

software instructions for enabling a computer to perform predetermined operations, and a computer readable medium bearing the software instructions;

wherein the predetermined operations comprise;

receiving location information for a requested file;

searching the cache for the requested file;

if the requested file is not found in a cache, then fetching data chunks of the requested file from a storage means and updating the cache with the retrieved file;

if the requested file is found in the cache, then checking if the data chunks comprising the data of the requested file in the cache are in sequence, and if the data chunks are not in sequence, then fetching the missing data chunks from the storage means and updating the cache with the retrieved data chunks; and

returning the requested file to a client terminal.

63. The computer program product as claimed in claim 62, wherein checking if the data chunks are in sequence comprises checking the status of a sequence means associated with each of the data chunks.

64. The computer program product as claimed in claim 62, wherein updating the cache comprises:

saving the data chunk fetched from the storage means in the cache; and

marking a sequence means associated with the data chunk as sequenced.

65. The computer program product as claimed in claim 64, wherein saving the data chunk comprises allocating memory in the cache to fit the size of the data chunk.