Data layout for recovery and durability

• US 9,454,441 B2
• Filed: 05/20/2011
• Issued: 09/27/2016
• Est. Priority Date: 04/19/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Elson, Jeremy E., Nightingale, Edmund B., Douceur, John R., Schechter, Stuart, Montgomery, Peter L.
• Primary Examiner(s): Kassim, Khaled
• Assistant Examiner(s): BELETE, BERHANU D
• Application Number:
  US13/112,978
• Publication Number:
  US 20110258483A1
• Time in Patent Office: 1,957 Days
• Field of Search: 714/4.11, 709220-223, 709/239, 709/245, 713/176, 726/2, 726/3, 707/9, 707/10, 707/104.1
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1662 the resynchronized component or unit being a persistent storage device re-synchronization of failed mirror storage G06F11/2082; rebuild or reconstruction of parity RAID storage G06F11/1008
• CPC Class Codes: G06F 11/2035 without idle spare hardware
• CPC Class Codes: G06F 11/2048 where the redundant components share neither address space nor persistent storage
• CPC Class Codes: G06F 2211/104 Metadata, i.e. metadata associated with RAID systems with parity

Abstract

A Metadata server described herein is configured to generate a metadata table optimized for data durability and recovery. In generating the metadata table, the metadata server associates each possible combination of servers with one of the indices of the table, thereby ensuring that each server participates in recovery in the event of a server failure. In addition, the metadata server may also associate one or more additional servers with each index to provide added data durability. Upon generating the metadata table, the metadata server provides the metadata table to clients or servers. Alternatively, the metadata server may provide rules and parameters to clients to enable those clients to identify servers storing data items. The clients may use these parameters and an index as inputs to the rules to determine the identities of servers storing or designated to store data items corresponding to the index.

Claims

1. A method comprising:

receiving, by a computing device, a total number of servers in a system and one or more rules defining a virtual metadata table of the system;

determining, by the computing device, identities of a subset of the servers by utilizing at least an index to the virtual metadata table, the index associated with one or more data items stored on the subset of the servers, and the total number of servers in the system as inputs to the one or more rules defining the virtual metadata table, wherein the one or more rules include;

a first formula to identify a first server of the subset of servers based at least in part on the index and the total number of servers in the system;

a second formula to identify a second server of the subset of servers based at least in part on the index and a first output of the first formula; and

a third formula to identify a third server of the subset of servers based at least in part on the first output of the first formula and a second output of the second formula; and

generating, by the computing device, a metadata table corresponding to the virtual metadata table, wherein data at the computing device is stored in the subset of servers based at least in part on the metadata table.

2. The method of claim 1, further comprising receiving from a metadata server of the system at least one of the total number of servers in the system or the one or more rules defining the virtual metadata table.

3. The method of claim 1, wherein the determining the identities of the subset of servers further includes utilizing at least one of a specific number of servers included in the subset of servers, a number of failure domains in the system, or a pseudo-random seed as inputs to the one or more rules.

4. The method of claim 1, further comprising locating the index in the metadata table.

5. The method of claim 1, further comprising determining a replacement server in the event of a server failure based on the one or more rules or based on one or more replacement rules generated responsive to the server failure.

6. The method of claim 1, wherein:

the first formula includes f(1,r)=(floor(r)/(n));

the second formula includes f(2,r)=(r+f(1,r)); and

the third formula includes f(3,r)=(f(1,r)+f(2,r)),

wherein r is the index, n is the total number of servers in the system, f(1,r) is the first identified server of the subset of servers, f(2,r) is the second identified server of the subset of servers, f(3,r) is the third identified server of the subset of servers, and both the indices and the servers of the subset of servers are integers.

7. The method of claim 1, wherein the rules include non-constant arithmetic progressions input to mod operations using the total number of servers in the system as a divisor.

8. The method of claim 1, wherein the servers in the system are virtual servers.

9. A computing device comprising:

one or more processors;

one or more computer storage media storing computer-executable instructions that, when executed by the one or more processors, cause the one or more processors to;

receive, by the computing device, a total number of servers in a system and one or more rules defining a virtual metadata table of the system;

determine, by the computing device, identities of a subset of the servers by utilizing at least an index to the virtual metadata table, the index associated with one or more data items stored on the subset of the servers, and the total number of servers in the system as inputs to the one or more rules defining the virtual metadata table, wherein the one or more rules include;

a first formula to identify a first server of the subset of servers based at least in part on the index and the total number of servers in the system;

a second formula to identify a second server of the subset of servers based at least in part on the index and a first output of the first formula; and

a third formula to identify a third server of the subset of servers based at least in part on the first output of the first formula and a second output of the second formula; and

generate, by the computing device, a metadata table corresponding to the virtual metadata table, wherein data at the computing device is stored in the subset of servers based at least in part on the metadata table.

10. The computing device of claim 9, wherein the computer-executable instructions further cause the one or more processors to receive from a metadata server of the system at least one of the total number of servers in the system or the one or more rules defining the virtual metadata table.

11. The computing device of claim 9, wherein the determining the identities of the subset of servers further includes utilizing at least one of a specific number of servers included in the subset of servers, a number of failure domains in the system, or a pseudo-random seed as inputs to the one or more rules.

12. The metadata server of claim 9, wherein the computer-executable instructions further cause the one or more processors to locate the index in the metadata table.

13. The computing device of claim 9, wherein the computer-executable instructions further cause the one or more processors to determine a replacement server in the event of a server failure based on the one or more rules or based on one or more replacement rules generated responsive to the server failure.

14. The computing device of claim 9, wherein:

the first formula includes f(1,r)=(floor(r)/(n));

the second formula includes f(2,r)=(r+f(1,r)); and

the third formula includes f(3,r)=(f(1,r)+f(2,r)),

wherein r is the index, n is the total number of servers in the system, f(1,r) is the first server of the subset of servers, f(2,r) is the second server of the subset of servers, f(3,r) is the third server of the subset of servers, and both the indices and the servers of the subset of servers are integers.

15. The computing device of claim 9, wherein the rules include arithmetic progressions input to mod operations using the total number of servers in the system as a divisor.

16. A system comprising:

one or more processors;

one or more computer storage media storing computer-executable instructions that, when executed by the one or more processors, cause the one or more processors to;

receive a number of servers in the system and one or more rules defining a virtual metadata table of the system;

determine identities of the subset of the servers based at least in part on an index to the virtual metadata table, the index associated with one or more data items stored on the subset of the servers, and the number of servers in the system as inputs to the one or more rules defining the virtual metadata table, wherein the one or more rules include;

a first formula to identify a first server of the subset of servers based at least in part on the index and the number of servers in the system;

a second formula to identify a second server of the subset of servers based at least in part on the index and a first output of the first formula; and

a third formula to identify a third server of the subset of servers based at least in part on the first output of the first formula and a second output of the second formula; and

generate a metadata table corresponding to the virtual metadata table, wherein data at the computing device is stored in the subset of servers based at least in part on the metadata table.

17. The system of claim 16, wherein the computer-executable instructions further cause the one or more processors to receive from a metadata server of the system at least one of the number of servers in the system or the one or more rules defining the virtual metadata table.

18. The system of claim 16, wherein the determining the identities of the subset of servers further includes utilizing at least one of a specific number of servers included in the subset of servers, a number of failure domains in the system, or a pseudo-random seed as inputs to the one or more rules.

19. The system of claim 16, wherein the computer-executable instructions further cause the one or more processors to determine a replacement server in the event of a server failure based on the one or more rules or based on one or more replacement rules.

20. The system of claim 16, wherein:

the first formula includes f(1,r)=(floor(r)/(n));

the second formula includes f(2,r)=(r+f(1,r)); and

the third formula includes f(3,r)=(f(1,r)+f(2,r)),

wherein r is the index, n is the number of servers in the system, f(1,r) is the first server of the subset of servers, f(2,r) is the second server of the subset of servers, f(3,r) is the third server of the subset of servers, and both of the index and the servers of the subset of servers are integers.