System and method for distributed network data storage

• US 7,085,819 B2
• Filed: 12/20/2001
• Issued: 08/01/2006
• Est. Priority Date: 12/20/2001
• Status: Expired due to Fees

• Current Assignee: Sigma Storage
• Original Assignee: Sigma Storage
• Inventors: Fordelon, Ericson G., Bright, Jonathan D., Ryan, Matthew B., Chandy, John A.
• Primary Examiner(s): Lim, Krisna
• Assistant Examiner(s): REILLY, SEAN M
• Application Number:
  US10/038,049
• Publication Number:
  US 20030120723A1
• Time in Patent Office: 1,685 Days
• Field of Search: 709/203, 709213-219, 709/223, 709/224, 714/100, 714 4- 7, 711/203, 711/205
• US Class Current: 709/217
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 11/1474 in transactions G06F16/20 takes precedence
• CPC Class Codes: G06F 11/2089 Redundant storage control functionality
• CPC Class Codes: G06F 11/2097 maintaining the standby controller/processing unit updated initialisation or re-synchronisation thereof G06F11/1658 and subgroups
• CPC Class Codes: G06F 2003/0697 device management, e.g. handlers, drivers, I/O schedulers
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems

Abstract

A distributed network data storage method includes receiving a data set from a client, defining a virtual device to include a plurality of device portions each on one of a plurality of network servers, parsing the data set into a plurality of data portions, and writing each of the data portions to a corresponding one of the virtual device portions. Methods are also disclosed for securely writing data to the virtual devices, and for identifying and reconstructing corrupt data. A system for implementing the data storage/retrieval method includes a plurality of network servers, each running a distributed RAID server application. The servers communicate with clients via a first network, and with each other via a second network.

Claims

1. A data storage method comprising:

receiving a data set from a client;

defining a virtual device to include device portions on a plurality of network servers said step of defining said virtual device including determining the number of data portions into which said data set is to be parsed, selecting a number of servers from said plurality of servers corresponding to said number of data portions, and defining a data portion file for each selected server to store a corresponding one of said data portions;

parsing said data set into a plurality of data portions;

writing each of said data portions to a corresponding one of said device portions by transmitting each of said data portions to a corresponding one of said network servers as a corresponding one of said data portion files;

transmitting a commit signal to each of said corresponding network servers, said commit signals causing said network servers to commit said data portions to memory;

transmitting a ready signal to a backup controller after transmitting each of said data portions to a corresponding one of said network servers; and

transmitting a done signal to said backup controller after transmitting said commit signals to said servers;

whereby said backup controller responsive to receiving said ready signal and not receiving said done signal, transmits a commit signal to said corresponding network servers.

2. A data storage method according to claim 1, wherein:

said data set is received from said client via a first network; and

and said data portions are written to said device portions via a second network.

3. A data storage method according to claim 1, further comprising:

receiving additional data sets from additional clients;

defining additional virtual devices to include device portions on said plurality of network servers;

parsing each said additional data set into a plurality of data portions; and

writing each of said data portions of said additional data sets to a corresponding one of said device portions of said additional virtual devices.

4. A data storage method according to claim 3, wherein no more than one user data file is written to each of said virtual devices.

5. A data storage method according to claim 3, wherein no more than one directory data file is written to each of said virtual devices.

6. A data storage method according to claim 3, wherein no more than one meta-data file is written to each of said virtual devices.

7. A data storage method according to claim 3, wherein each of said virtual devices contains no more than one type of data.

8. A data storage method according to claim 1, further comprising incorporating said virtual device into a data structure distributed across said plurality of network servers.

9. A data storage method according to claim 8, wherein said data set includes new directory data, and incorporating said device into said data structure includes:

parsing a new sub-directory entry;

writing said parsed subdirectory entry to a virtual directory device defined across said plurality of network servers, said virtual directory device corresponding to a current directory in which the new directory will be included;

parsing a new meta-data entry;

writing said parsed meta-data entry to a virtual meta-data device defined across said plurality of network servers, said virtual meta-data device corresponding to said current directory;

defining a new virtual directory device across said plurality of network servers;

parsing said new directory data;

writing said parsed new directory data to said new virtual directory device; and

defining a new virtual meta-data device across said plurality of network servers.

10. A data storage method according to claim 8, wherein said data set includes new user file data, and incorporating said virtual device into said data structure comprises:

parsing a new file entry;

writing said parsed file entry to a virtual directory device defined across said plurality of network servers, said virtual directory device corresponding to a current directory in which the new file will be included;

parsing a new meta-data entry;

writing said parsed meta-data entry to a virtual meta-data device defined across said plurality of network servers, said virtual meta-data device corresponding to said W current directory.

11. A data storage method according to claim 1, wherein said number of data portions depends on the type of data set.

12. A data storage method according to claim 1, wherein each said data portion file is assigned a name, said name including:

an identifier uniquely identifying said virtual device;

a file number uniquely identifying said data portion file with respect to other data portion files corresponding to said virtual device; and

the total number of said data portion files corresponding to said virtual device.

13. A data storage method according to claim 1, wherein:

said step of defining said virtual device includes defining one of said device portions to include parity data; and

said step of parsing said data includes generating said parity data.

14. A data storage method according to claim 1, wherein said step of selecting a number of servers from said plurality of servers includes selecting said servers based at least in part on the available storage capacity of said servers.

15. A data storage method according to claim 1, further comprising transmitting a signal to said client indicating that said data set has been stored, after said data set has been received, but before said data set has been written to said virtual device.

16. A data storage method according to claim 1, further comprising:

writing said data set to local non-volatile memory; and

transmitting a signal to said client indicating that said data set has been stored, after said data set has been written to said non-volatile memory, but before said data set has been written to said virtual device.

17. A data storage method according to claim 1, further comprising transmitting a signal to said client indicating that said data has been stored, only after said data set has been written to said virtual device.

18. A data storage method according to claim 1, further comprising transmitting a signal to said client indicating that said data has been stored, said signal being transmitted at one of the following times depending on a predetermined criteria;

after said data set has been received, but before said data set has been written to said virtual device;

after said data set has been written to local non-volatile memory, but before said data set has been written to said virtual device;

or

only after said data set has been written to said virtual device.

19. A data storage method according to claim 18, wherein said predetermined criteria includes a data type of said data set.

20. A data storage method according to claim 18, wherein said predetermined criteria includes a file name extension associated with said data set.

21. A data storage method according to claim 1 further comprising:

determining whether a confirmation signal has been received from each of said corresponding network servers, said confirmation signals indicating that said network servers have committed said data portions to memory; and

writing a write failure entry to at least one fact server, said write failure entry identifying any of said corresponding network servers from which said confirmation signals are not received.

22. A data storage method according to claim 21, wherein said write failure entry is written to at least two fact servers.

23. A data storage method according to claim 22, wherein said fact servers each reside on a different one of said plurality of network servers.

24. A data storage method according to claim 22, further comprising:

periodically polling said fact servers;

correcting any data portion files corresponding to incomplete writes identified by said fact servers.

25. A data storage method according to claim 1, further comprising:

determining whether a confirmation signal has been received from each of said corresponding network servers, said confirmation signals indicating that said network servers have committed said data portions to memory; and

writing a write failure entry to at least one fact server, said write failure entry identifying any of said corresponding network servers from which said confirmation signals are not received; and

wherein

said backup controller, responsive to receiving said ready signal and not receiving said done signal, performs said steps of determining whether said confirmation signals have been received and writing said write failure entry to said fact server.

26. A data storage method according to claim 25, wherein said write failure entry is written to at least two fact servers.

27. A data storage method according to claim 26, wherein said fact servers each reside on a different one of said plurality of network servers.

28. A data storage method according to claim 1, wherein said step of receiving said data set from said client comprises:

writing said data set to local nonvolatile data storage; and

writing a local data entry to a fact server, said local data entry indicating that valid data is stored in said local nonvolatile data storage.

29. A data storage method according to claim 28, wherein said local data entry is written to at least two fact servers.

30. A data storage method according to claim 29, wherein said fact servers each reside on a different one of said plurality of network servers.

31. A data storage method according to claim 28, further comprising:

removing said data set from said local nonvolatile memory after said data set is written to said virtual device; and

updating said fact server to indicate that said data set is no longer in said local nonvolatile data storage.

32. A data storage method according to claim 1, further comprising:

receiving a data request from a client;

retrieving a virtual device definition corresponding to the requested data, said virtual device definition identifying device portions located on a plurality of network servers;

retrieving data portion files from said device portions;

collating said retrieved data portion files to generate the requested data; and

transmitting the requested data to said client.

33. A data storage method according to claim 32, wherein said step of retrieving said virtual device definition comprises:

retrieving virtual meta-data device information from a current directory;

retrieving meta-data portion files from said plurality of network servers;

collating said meta-data portion files to generate mete-data; and

retrieving said virtual device definition from said mete-data.

34. A data storage method according to claim 32, wherein said step of retrieving data portion files from said device portions comprises:

transmitting requests for said data portion files to network servers corresponding to said device portions; and

receiving said data portion files from said network servers.

35. A data storage method according to claim 34, wherein each said data portion file is assigned a name, said name including:

an identifier uniquely identifying the requested data;

a file number uniquely identifying said data portion file with respect to other data portion files corresponding to the data; and

the total number of said data portion files corresponding to the requested data.

36. A data storage method according to claim 34, wherein said step of retrieving data portion files from said device portions comprises:

determining which one of a plurality of controllers has access to said virtual device, said controllers residing on said network servers; and

invoking said controller with access to said virtual device to retrieve said data portion files.

37. A data storage method according to claim 36, wherein said step of retrieving said virtual device definition comprises:

determining which one of said plurality of controllers has access to another virtual device storing said virtual device definition; and

invoking said controller with access to said another virtual device to retrieve said virtual device definition.

38. A data storage method according to claim 37, wherein said steps of determining which ones of said plurality of controllers have access to said virtual devices include selecting said controllers depending on the type of data stored in said virtual devices.

39. A data storage method according to claim 34, wherein;

said step of receiving said data portion files from said network servers includes receiving all but one of said data portion files; and

said step of collating said data portion files includes generating said one data portion file based on parity data included in said received data portion files.

40. A data storage method according to claim 32, further comprising:

polling at least one fact server to determine whether said virtual device includes a potentially corrupt data portion file; and

reconstructing said potentially corrupt data portion file.

41. A data storage method according to claim 32, further comprising:

polling at least one fact server to determine whether said virtual device includes a potentially corrupt data portion file;

polling at least one fact server to determine whether said requested data is stored in nonvolatile data storage; and

retrieving said requested data from said nonvolatile data storage instead of said virtual device, if said virtual device includes a potentially corrupt data portion file and said requested data is stored in said nonvolatile data storage.

42. A data storage method according to claim 32, wherein:

communication with said client is via a first network; and

communication with said network servers is via a second network.

43. A data storage method according to claim 42, wherein communication between said client and said network servers is via said first network.

44. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 1.

45. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 2.

46. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 3.

47. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 4.

48. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 5.

49. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 6.

50. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 7.

51. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 8.

52. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 9.

53. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 10.

54. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 11.

55. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 12.

56. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 13.

57. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 14.

58. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 15.

59. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 16.

60. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 17.

61. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 18.

62. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 19.

63. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 20.

64. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 21.

65. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 22.

66. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 23.

67. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 24.

68. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 25.

69. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 26.

70. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 27.

71. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 28.

72. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 29.

73. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 30.

74. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 31.

75. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 32.

76. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 33.

77. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 34.

78. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 35.

79. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 36.

80. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 37.

81. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 38.

82. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 39.

83. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 40.

84. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 41.

85. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 42.

86. A computer-readable medium having code embodied therein for causing an electronic device to perform the method of claim 43.

87. A data storage system comprising:

a network interface to facilitate communication with clients and with a plurality of network servers; and

a file server, responsive to receiving a file to be stored from one of said clients, and operative to define a virtual device to include device portions on said plurality of network servers, to parse said file into a plurality of file portions, and to write each of said file portions to a corresponding one of said device portions, said file server including a client process for receiving said file from said client and a distribution controller, responsive to said client process, and operative to determine the number of file portions into which said file is to be parsed, to select a number of servers from said plurality of servers corresponding to said number of file portions, and to define a portion file for each selected server to store a corresponding one of said file portions; and

an input/output process, responsive to receiving requests for locally stored portion files from said distribution controller, and operative to retrieve and transmit said portion files to said distribution controller; and

wherein

said distribution controller is further operative to transmit a commit signal to each of said corresponding network servers, said commit signals causing said network servers to commit said portion files to memory, to transmit a ready signal to a backup controller after transmitting each of said portion files to a corresponding one of said network servers, and to transmit a done signal to said backup controller after transmitting said commit signals to said servers;

whereby said back controller, responsive to receiving said ready signal and not receiving said done signal, transmits a commit signal to said corresponding network servers.

88. A data storage system according to claim 87, wherein said network interface comprises:

a first network adapter to facilitate communication between said data storage system and said clients; and

a second network adapter to facilitate communication between said data storage system and said plurality of network servers.

89. A data storage system according to claim 87, further comprising a data storage device for storing at least one of said file portion, whereby said data storage system is capable of functioning as one of said plurality of network servers.

90. A data storage system according to claim 87, wherein said virtual device is limited to storing no more than on file.

91. A data storage system according to claim 87, wherein said distribution controller determines the number of file portions into which the file is to be parsed based, at least in part, on the file type of the file.

92. A data storage system according to claim 87, wherein said distribution controller is further operative to assign a name to each of said portion files, said name including:

an identifier uniquely identifying said file;

a file number uniquely identifying said portion file with respect to other portion files associated with said data set; and

the total number of said portion files associated with said data set.

93. A data storage system according to claim 87, wherein said distribution controller is further operative to:

define an additional portion file to include parity data; and

to generate said additional portion file from said portion files.

94. A data storage system according to claim 87, wherein said distribution controller is further operative to:

to determine the available storage on each of said plurality of servers; and

to select servers from said plurality of servers based at least in part on the available storage capacity of said servers.

95. A data storage system according to claim 87, wherein said distribution controller is further operative to transmit a signal to said client indicating that said file has been stored, said signal being transmitted after said file has been received by said client process, but before said file has been written to said virtual device.

96. A data storage system according to claim 87, wherein said distribution controller is further operative to:

write said file to local non-volatile memory; and

to transmit a signal to said client indicating that said file has been stored, after said file has been written to said non-volatile memory, but before said file has been written to said virtual device.

97. A data storage system according to claim 87, wherein said distribution controller is further operative to transmit a signal to said client indicating that said file has been stored, only after said file has been written to said virtual device.

98. A data storage system according to claim 87, wherein said distribution controller, responsive to predetermined criteria, is further operative to transmit a signal to said client indicating that said file has been stored, said signal being transmitted at one of the following times:

after said file has been received, but before said file has been written to said virtual device;

after said file has been written to local non-volatile memory, but before said file has been written to said virtual device;

or

only after receiving confirmation from said distribution controller that said file has been written to said virtual device.

99. A data storage system according to claim 98, wherein said predetermined criteria includes a file type of said file.

100. A data storage system according to claim 99, wherein said predetermined criteria includes a file name extension associated with said file.

101. A data storage system according to claim 87, wherein said distribution controller further is operative to:

determine whether a confirmation signal has been received from each of said corresponding network servers, said confirmation signals indicating that said network servers have committed said portion files to memory; and

write a write failure entry to at least one fact server, said write failure entry identifying any of said corresponding network servers from which said confirmation signals are not received.

102. A data storage system according to claim 101, wherein said distribution controller is operative to write said write failure entry at least two fact servers.

103. A data storage system according claim 102, wherein:

said fact servers each reside on a different one of said plurality of network servers; and

said data storage system further includes a fact server to receive entries from said network servers.

104. A data storage system according to claim 102, further comprising:

a local controller operative to poll said servers; and

wherein, responsive to a signal from said local controller, said distribution controller is operative to correct any portion files corresponding to incomplete writes identified by said fact servers.

105. A data storage system according to claim 87, wherein said distribution controller is further operative to:

receive confirmation signals from each of said corresponding network servers, said confirmation signals indicating that said network servers have committed said portion files to memory; and

write a write failure entry to at least fact server, said write failure entry identifying any of said corresponding network servers from which said confirmation signals are not received.

106. A data storage system according to claim 105, wherein said distribution controller is operative to write said write failure entries to at least two fact servers.

107. A data storage system according to claim 106, wherein said fact servers each reside on a different one of said plurality of network servers.

108. A data storage system according to claim 107, farther comprising:

a local controller operative to poll said fact severs; and

wherein

responsive to a signal from said local controller, said distribution controller is operative to correct any portion files corresponding to a write failure entry in at least one of said fact servers.

109. A data storage system according to claim 87, wherein said file server is operative to:

write said file to local nonvolatile data storage pending said write of said file portions to said device portions; and

writing a local data entry to a fact server, said local data entry indicating that said file is stored in said local nonvolatile data storage.

110. A data storage system according to claim 109, wherein said local data entry is written to at least two fact servers.

111. A data storage system according to claim 110, wherein said fact servers each reside on a different one of said plurality of network servers.

112. A data storage system according to claim 109, wherein said file server is further operative to:

remove said file from said local nonvolatile memory after said file portions are written to said device portions; and

update said fact server to indicate that said file is no longer in said local nonvolatile data storage.

113. A data storage system according to claim 87, further comprising:

a client interface operative to receive a file request from a client; and

wherein

said file server responsive to said file request is operative to retrieve a virtual device definition corresponding to said requested file, said virtual device definition identifying file portions located on a plurality of network servers, to retrieve said file portions, and to collate said retrieved file portions to generate said requested file.

114. A data storage system according to claim 113, wherein said client interface is further operative to transmit said requested file to said client.

115. A data storage system according to claim 114, wherein:

said file server includes a local controller responsive to said file request, and operative to retrieve virtual meta-data device information associated with said requested file from a current directory, said meta-data device information identifying meta-data device portions on said plurality of network servers; and

said distribution controller responsive to said virtual meta-data device information, is operative to retrieve meta-data portion files from said meta-data device portions, to collate said meta-data portion files to generate meta data, said meta-data including said virtual device definition corresponding to said requested file.

116. A data storage system according to claim 114, wherein said distribution controller responsive to said virtual device definition is operative to transmit requests for said file portions to said servers, and to receive said file portions from said servers.

117. A data storage system according to claim 116, wherein said file portions are identified by a file portion name, said file portion name including:

an identifier uniquely identifying said requested file;

a second identifier uniquely identifying said file portion with respect to said other file portions corresponding to said requested file; and

the total number of file portions corresponding to said requested file.

118. A data storage system according to claim 113, wherein said client interface, responsive to said file request, is operative to determine which of a plurality of controllers has access to said virtual device.

119. A data storage system according to claim 118, further comprising:

at least one of said plurality of controllers; and

wherein

at least one other of said plurality of controllers is located on one of said network servers of said plurality of network servers.

120. A data storage system according to claim 118, wherein which controller has access to said virtual device depends on the type of file stored in said virtual device.

121. A data storage system according to claim 120, wherein each of said controllers is able to handle only one type of file.

122. A data storage system according to claim 113, wherein said file server, responsive to receiving all but one of said file portion, is operative to generate said one file portion from parity data in one of said received file portions.

123. A data storage system according to claim 113, wherein:

said client interface communicates with clients via a first network; and

said file server communicates with said plurality of network servers via a second network.