Continuous media file server for cold restriping following capacity change by repositioning data blocks in the multiple data servers

• US 5,991,804 A
• Filed: 06/20/1997
• Issued: 11/23/1999
• Est. Priority Date: 06/20/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Need, Dwayne R., Debgupta, Siddhartha, Bolosky, William J.
• Primary Examiner(s): Luu, Le H.
• Assistant Examiner(s): Cardone, Jason D.
• Application Number:
  US08/879,405
• Time in Patent Office: 886 Days
• Field of Search: 395/200.43, 395/200.5, 395/200.53, 395/200.61, 395/200.75, 395/200.38, 707/10, 709/208, 709/209, 709/213, 709/220, 709/221, 709/223, 709/231, 709/245
• US Class Current: 709/221
• CPC Class Codes: G06F 11/1096 Parity calculation or recalculation after configuration or reconfiguration of the system
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 11/2097 maintaining the standby controller/processing unit updated initialisation or re-synchronisation thereof G06F11/1658 and subgroups

Abstract

A continuous media file server has a controller connected to multiple data servers. Each data server supports at least one storage disk. Data files are distributed across the data servers so that data blocks of the data files are stored on each of the storage disks according to a present striping layout. The file server employs declustered mirroring techniques in which data is redundantly copied and stored on other disks and servers to guard against component failure. In the event that the storage capacity of the media file server is changed (i.e., by adding or removing one or more storage disks), the continuous media file server is restriped in a three-phase process. During the first phase, the controller determines a new striping layout of the data files across the storage disks which accounts for the capacity change. The controller then creates an ordered work list describing the data block moves that a corresponding data server needs to make to convert from the present striping layout to the new striping layout. The controller distributes the list to the data servers. The order of the latter two phases depends on whether disks are being added or removed. In one of the two final phases, the data servers reorganize the redundancy data for the new disk configuration. In the other of the two final phases, the data servers execute their respective work lists and communicate with one another to move the data blocks to the appropriate disks in conformance with the new striping layout.

Claims

1. In a continuous media file server having multiple data servers with each data server supporting at least one storage disk, wherein data files are distributed across the data servers so that blocks of the data files are stored on each of the storage disks according to a present striping layout, a method for configuring the continuous media file server following a change in storage capacity, comprising the following steps:

determining a new striping layout of the data files across the storage disks which accounts for the change in storage capacity;

creating a list specifying movement of data from present locations on the storage disks conforming to the present striping layout to new locations on the storage disks conforming to the new striping layout;

distributing the list to the data servers; and

executing the list, at the data servers, to move the data from the present locations to the new locations.

2. A method as recited in claim 1, wherein the determining step comprises allocating the blocks of the data files to the storage disks in sequential order.

3. A method as recited in claim 1, further comprising the step of evaluating, in an event that the storage capacity is reduced, whether the continuous media file server has sufficient capacity to store the data files.

4. A method as recited in claim 1, further comprising the step of constructing a map of the new striping layout.

5. A method as recited in claim 1, further comprising the step of constructing a bit map of the new striping layout having a bit entry representing each location on the storage disks in the new striping layout to assist in allocating data blocks to the locations of the new striping layout.

6. A method as recited in claim 1, wherein the creating step includes the step of assigning the data blocks to specific destination blocks on destination disks where the data blocks are to be moved according to the new striping layout.

7. A method as recited in claim 6, wherein the destination blocks include used blocks and at least some unused blocks, further comprising the step of first assigning the data blocks to the unused blocks on the destination disks and subsequently assigning the data blocks to the used blocks on the destination disks.

8. A method as recited in claim 1, further comprising the step of creating the list to include block movement summaries which specify a source disk and a source block located on the source disk where a particular data block presently resides and a destination disk and a destination block located on the destination disk where the particular block is to be moved according to the new striping layout.

9. A method as recited in claim 1, further comprising the step of deriving chains of data movements, each chain beginning with a block on a disk that is initially free and ending with a block on a disk that is finally free.

10. A method as recited in claim 1, further comprising the step of detecting cycles of data movements, each cycle beginning and ending with a same block on a disk.

11. A method as recited in claim 1, further comprising the following steps:

identifying data which resides on the same storage disk according to both the present striping layout and the new striping layout; and

omitting the identified data from the list.

12. A method as recited in claim 1, wherein the step of executing the lists is performed in parallel at the data servers.

13. A method as recited in claim 1, further comprising the step of communicating among the data servers to ensure that the data at the present locations are moved prior to being overwritten by the data being moved to the new locations.

14. A method as recited in claim 1, wherein the executing step comprises the following steps:

reading particular data from its present location on a source disk into a source data server supporting the source disk;

sending a write request from the source data server to a destination data server, the destination data server supporting a destination disk having the new location for the particular data;

determining, at the destination data server, whether the new location for the particular data is ready to be written to; and

if the new location is ready to be written to, transferring the particular data from the source data server to the destination data server and writing the particular data to the new location on the destination disk.

15. A method as recited in claim 14, further comprising the step of informing the source data server that the particular data has been written to the new location.

16. A method as recited in claim 1, wherein the data files are stored redundantly on the continuous media file server, further comprising the step of updating redundancy to reflect movement of the data.

17. A method as recited in claim 1, further comprising the step of logging events indicating when the data is moved to its new location.

18. A method as recited in claim 1, further comprising the following steps:

moving the data in a prescribed order from the storage disks;

logging events indicating when the data is moved to its new location; and

maintaining a pointer to each storage disks'"'"' work list indicating which data has been logged as being moved.

19. A method as recited in claim 1, further comprising the following steps:

moving the data in a prescribed order from the storage disks; and

maintaining a pointer to each storage disks'"'"' work list indicating which data was last transferred.

20. Computer-readable media having computer-executable instructions executable at the controller and the data servers for performing the steps of the method as recited in claim 1.

21. In a continuous media file server having a controller and multiple data servers with each data server supporting at least one storage disk, wherein data files are distributed across the data servers so that data blocks of the data files are stored on each of the storage disks, a method for configuring the continuous media file server following a change in storage capacity, comprising the following steps:

determining a new striping layout of the data files across the storage disks which accounts for the change in storage capacity;

creating a list with entries that assign the data blocks to destination blocks on destination disks where the data blocks are to be moved according to the new striping layout, individual list entries identifying a source block and a source disk where the data block presently resides as well as the destination block and the destination disk;

deriving chains of data block moves based on the list, each of the chains beginning with a destination block that is initially free prior to movement of any data blocks in the chain and ending with a source block that is finally free after movement of the data blocks in the chain;

detecting any cycles of data block moves within the list, each of the cycles beginning with a destination block and ending with a source block that is identical to the destination block;

constructing work lists for corresponding ones of the storage disks, the work lists containing individual links of the data block movement chains for performance by the respective data servers according to sequence of the links within the chains, at least some of the work lists further containing one or more of any said detected cycles;

distributing the work lists to the corresponding data servers;

for each list entry, performing in parallel at the data servers the following steps;

reading a particular data block from the source disk into a source data server responsible for the source disk;

sending a write request from the source data server to a destination data server, the destination data server supporting the destination disk;

determining, at the destination data server, whether the destination block is ready to be written to; and

if the destination block is ready to be written to, transferring the particular data block from the source data server to the destination data server and writing the particular data block to the destination block on the destination disk.

22. A method as recited in claim 21, further comprising the step of constructing a bit map of the new striping layout having a bit entry representing each location on the storage disks in the new striping layout to assist in allocating data blocks to the locations of the new striping layout.

23. A method as recited in claim 21, further comprising the step of omitting from the list any data blocks that reside on a storage disk which contains both the source block and the destination block.

24. A method as recited in claim 21, further comprising the step of informing the source data server that the particular data block has been written to the destination block.

25. A method as recited in claim 21, wherein the data files are stored redundantly on the continuous media file server, further comprising the step of updating redundancy to reflect movement of the data blocks.

26. A method as recited in claim 21, further comprising the step of logging an event indicating that the particular data block has been moved to the destination block.

27. Computer-readable media having computer-executable instructions executable at the controller and the data servers for performing the steps of the method as recited in claim 21.

28. In a continuous media file server having a controller and multiple data servers with each data server supporting at least one storage disk, wherein data files are distributed across the data servers so that data blocks of the data files are stored on each of the storage disks, a method for implementing a new storage configuration following a change in storage capacity, comprising the following steps:

determining a new striping layout of the data files across the storage disks which accounts for the change in storage capacity;

creating multiple lists for corresponding ones of the storage disks, each list having entries that specify movement of the data blocks from source blocks on source disk to destination blocks on destination disks where the data blocks are to be moved according to the new striping layout; and

ordering the entries on the lists to dictate an order in which the data servers are to move the data blocks.

29. A method as recited in claim 28, further comprising the following steps:

deriving chains of data block moves based on the list, each of the chains beginning with a destination block that is initially free prior to movement of any data blocks in the chain and ending with a source block that is finally free after movement of the data blocks in the chain; and

ordering the entries on the lists according to a sequence of the links within the chains.

30. A method as recited in claim 28, further comprising the following steps:

detecting any cycles of data block moves within the list, each of the cycles beginning with a destination block and ending with a source block that is identical to the destination block; and

posting entire cycles to ones of the lists.

31. A method as recited in claim 28, further comprising the step of distributing the lists to the data servers.

32. A method as recited in claim 28, further comprising the step of evaluating, in an event that the storage capacity is reduced, whether the continuous media file server has sufficient capacity to store the data files.

33. A method as recited in claim 28, further comprising the step of omitting from the lists any data blocks that already reside on the destination disk.

34. A computer programmed to perform the steps recited in the method of claim 28.

35. A computer-readable medium having computer-executable instructions for performing the steps of the method as recited in claim 28.

36. In a continuous media file server having a controller and multiple data servers with each data server supporting at least one storage disk, wherein data files are distributed across the data servers so that data blocks of the data files are stored on each of the storage disks, a method for operating each data server during reconfiguration of the continuous media file server following a change in storage capacity, comprising the following steps:

receiving a list from the controller, the list having entries that assign the data blocks to destination blocks on destination disks where the data blocks are to be moved, the entries identifying a source block and a source disk where the data block presently resides as well as the destination block and the destination disk;

for each entry on the list, reading a particular data block from the source disk;

sending a write request to a destination data server which supports the destination disk; and

in an event that the destination data server is ready to receive the data block, transferring the particular data block to the destination data server.

37. A method as recited in claim 36, further comprising the step of logging an event indicating when the particular data block is transferred to the destination block.

38. A method as recited in claim 36, further comprising the following steps:

reading and transferring data blocks in a prescribed order from the source disk;

logging events indicating that the data blocks are transferred to the destination blocks; and

maintaining a pointer to the source disks'"'"' work lists indicating which data blocks have been logged as being transferred.

39. A method as recited in claim 36, further comprising the following steps:

reading and transferring data blocks in a prescribed order from the source disk; and

maintaining a pointer to the source disk indicating which data block was last transferred.

40. A method as recited in claim 36, further comprising the following steps:

reading and transferring data blocks in a prescribed order from the source disk;

maintaining a pointer to the source disk indicating which data block was last transferred;

logging events indicating when the data blocks are transferred to the destination blocks; and

maintaining a pointer to the source disk indicating which data blocks have been logged as being transferred.

41. A computer programmed to perform the steps recited in the method of claim 36.

42. A computer-readable medium having computer-executable instructions for performing the steps of the method as recited in claim 36.

43. In a continuous media file server having a controller and multiple data servers with each data server supporting at least one storage disk, wherein data files are distributed across the data servers so that data blocks of the data files are stored on each of the storage disks, a method for providing fault tolerance in an event of system failure during reconfiguration of the continuous media file server following a change in storage capacity, comprising the following steps:

constructing work lists for corresponding ones of the storage disks, the work lists specifying movement of data blocks from present locations on source disk to new locations on destination disks;

communicating among the data servers to transfer in parallel the data blocks from the source disks to the destination disks;

transferring the data blocks in an order specified in the work lists from the source disks;

maintaining first pointers to the source disks indicating which data blocks on the respective source disks were last transferred;

logging events indicating when the data blocks are transferred to the destination blocks; and

maintaining second pointers to the source disks indicating which data blocks have been logged as being transferred.

44. A method as recited in claim 43, further comprising the step of commencing transfer of the data blocks located at the second pointers in an event that the continuous media server is recovering from system failure.

45. A continuous media file server, comprising:

multiple data servers, each data server supporting at least one storage disk, wherein data files are distributed across the data servers so that data blocks of the data files are stored on each of the storage disks according to a present striping layout;

a controller coupled to the data servers;

in an event that storage capacity of the media file server is changed, the controller being configured to determine a new striping layout of the data files across the storage disks which accounts for the change in storage capacity and to create a list specifying movement of data blocks from present locations on the storage disks conforming to the present striping layout to new locations on the storage disks conforming to the new striping layout; and

the data servers operating in parallel to execute the list to move the data blocks from the present locations to the new locations.

46. A continuous media file server as recited in claim 45, wherein the controller stripes the data blocks sequentially across the storage disks.

47. A continuous media file server as recited in claim 45, wherein the controller is configured to initially evaluate whether the continuous media file server has sufficient capacity to store the data files in an event that the storage capacity is reduced.

48. A continuous media file server as recited in claim 45, wherein the controller has a bit map of the new striping layout, the bit map having a bit entry representing each location on the storage disks in the new striping layout to assist in allocating data blocks to the locations of the new striping layout.

49. A continuous media file server as recited in claim 45, wherein the controller assigns the data blocks to specific destination blocks on destination disks where the data blocks are to be moved according to the new striping layout.

50. A continuous media file server as recited in claim 45, wherein the controller creates block movement summaries specifying movement of the data blocks from source blocks on source disks of the present striping layout to destination blocks on destination disks where the data blocks are to be moved according to the new striping layout.

51. A continuous media file server as recited in claim 47, wherein the controller derives chains of data block movements, each chain beginning with a destination block that is initially free and ending with a source block on a disk that is finally free.

52. A continuous media file server as recited in claim 50, wherein the controller detects cycles of data block movements, each cycle beginning with a destination block and ending with a source block that is identical to the destination block.

53. A continuous media file server as recited in claim 45, wherein:

the destination blocks include used blocks and unused blocks on the destination disk; and

the controller first assigns the data blocks to unused blocks on the destination disks and subsequently to used blocks in a selected order of the destination disks.

54. A continuous media file server as recited in claim 45, wherein the controller identifies certain data blocks which reside on storage disks which are the same under both the present striping layout and the new striping layout and omits these certain data blocks from the list.

55. A continuous media file server as recited in claim 45, wherein the data servers implement a protocol ensuring that the data blocks are moved prior to be overwritten.

56. A continuous media file server as recited in claim 45, wherein during execution of the list, a first one of the data servers reads a particular data block from a source disk and sends a write request to a second one of the data servers which supports a destination disk to which the data block is to be moved, the second data server retrieving the particular data block from the first data server and writing the particular data block to the destination disk.

57. A continuous media file server as recited in claim 56, wherein the second data server informs the first data server that the particular data block has been written to the destination disk.

58. A continuous media file server as recited in claim 45, wherein the data servers log events indicating that the data blocks are moved to the new locations.

59. A continuous media file server as recited in claim 45, wherein:

the data servers move the data in order from the storage disks; and

each of the storage disks maintains a pointer indicating which data blocks have been moved.

60. A continuous media file server as recited in claim 45, further comprising the following steps:

the data servers move the data in order from the storage disks and log events indicating when the data blocks are moved to the new locations; and

each of the storage disks maintains a pointer indicating which data blocks have been logged as being moved.

61. An interactive television system comprising the continuous media file server as recited in claim 45.

62. A network content provider comprising the continuous media file server as recited in claim 45.

63. A distributed control system for a continuous media file server, the continuous media file server having a controller and multiple data servers with each data server supporting at least one storage disk, wherein data files are distributed across the data servers so that data blocks of the data files are stored on each of the storage disks according to a present striping layout, the control system comprising:

a processor at the controller of the media file server, the controller-based processor being programmed to determine a new striping layout of the data files across the storage disks to account for a change in storage capacity and to create a list specifying movement of data blocks from present locations on the storage disks conforming to the present striping layout to new locations on the storage disks conforming to the new striping layout; and

a processor at each of the data servers, the data server-based processors being programmed to execute the list to move the data blocks from the present locations to the new locations.

64. An interactive television system comprising the distributed control system as recited in claim 63.

65. A network content provider comprising the distributed control system as recited in claim 63.

66. A computer-readable medium having computer-executable instructions for performing the following steps:

determining a new striping layout for distributing data files across multiple storage disks in a continuous media file server which has experienced a change in storage capacity, the new striping layout ensuring that data blocks of the data files are stored on each of the storage disks;

creating an executable list having entries that assign the data blocks to destination blocks on destination disks where the data blocks are to be moved according to the new striping layout; and

ordering the entries on the list to dictate an order in which the data blocks are to be moved.

67. A computer-readable medium having computer-executable instructions for performing the following steps:

receiving a list describing movement of data blocks from data files from a present striping layout to a new striping layout, the present and new striping layouts prescribing distributed placement of the data blocks across multiple storage disks in a manner that the data blocks from each data file are stored on each of the storage disks, the list having entries identifying source blocks on source disks where the data blocks presently reside and destination blocks on destination disks where the data blocks are to be moved;

for each entry on the list, reading a particular data block from the source disk;

sending a write request to write the data block to the destination disk; and

in an event that the destination disk is ready to receive the particular data block, transferring the particular data block to the destination disk.