Memory management and recovery for datacenters

• US 8,181,061 B2
• Filed: 04/19/2010
• Issued: 05/15/2012
• Est. Priority Date: 04/19/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Nightingale, Edmund B., Elson, Jeremy E., Howell, Jonathan R., Hunt, Galen C.
• Primary Examiner(s): LE, DIEU MINH T
• Application Number:
  US12/763,133
• Publication Number:
  US 20110258482A1
• Time in Patent Office: 757 Days
• Field of Search: 714/4.11, 714/4.12, 714/4.2, 714/4.21, 714/6.12, 714/6.2, 714/6.22, 714/6.3, 714/6.32
• US Class Current: 714/4.11
• 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 system including a plurality of servers, a client, and a metadata server is described herein. The servers each store tracts of data, a plurality of the tracts comprising a byte sequence and being distributed among the plurality of servers. To locate the tracts, the metadata server generates a table that is used by the client to identify servers associated with the tracts, enabling the client to provide requests to the servers. The metadata server also enables recovery in the event of a server failure. Further, the servers construct tables of tract identifiers and locations to use in responding to the client requests.

Claims

1. A method implemented by at least one metadata server, the method comprising:

determining that a server of a plurality of servers has failed;

determining tracts of data stored on the failed server;

determining other servers of the plurality of servers also storing the tracts of data, the tracts of data being distributed among the other servers; and

instructing, based in part on the determining that the server has failed, the other servers to write the tracts of data to additional servers to create replicas of the tracts of data, at least two of the other servers performing the writing in parallel.

2. The method of claim 1, wherein the determining the tracts and the determining the other servers comprises utilizing a locator table that associates representations of the tracts with the plurality of servers.

3. The method of claim 2, wherein the determining the tracts comprises determining prefixes included in translations to fixed lengths of identifiers of the tracts, the prefixes being associated by the locator table with the servers.

4. The method of claim 2, further comprising, upon performing the instructing, generating an updated locator table showing the representations being associated with the additional servers.

5. The method of claim 1, further comprising associating each tract with at least two servers to ensure redundancy.

6. The method of claim 5, further comprising selecting a number of servers associated with each tract based at least in part on a target recovery duration.

7. The method of claim 1, wherein determining that the server has failed comprises receiving notification from the failed server that the server is going to fail or has failed.

8. The method of claim 1, wherein the determining the tracts and the determining the other servers comprises utilizing a locator table that associates representations of the tracts with the plurality of servers, and

wherein the determining the tracts comprises determining prefixes included in translations to fixed lengths of identifiers of the tracts, the prefixes being associated by the locator table with the servers.

9. A server system comprising:

a processor;

a storage unit coupled to the processor and storing a plurality of tracts of data and identifiers of the tracts, each tract having a same size as each other tract, each tract identifier having a same size as each other tract identifier, and each tract identifier being stored next to the tract it identifies; and

a plurality of executable instructions configured to be operated by the processor to program the server system to construct a table identifying the tracts stored in the storage unit and their locations in the storage unit by scanning the storage unit for tract identifiers based at least in part on the tract size and the tract identifier size.

10. The server system of claim 9, wherein each tract identifier is stored after content of the tract.

11. The server system of claim 9, wherein the instructions are configured to program the server system to construct the table in response to a failure or a reboot.

12. The server system of claim 9, wherein the storage unit also stores representations of groups of tracts, each group of tracts including tracts from multiple byte sequences.

13. A computer-readable storage medium comprising:

a plurality of computer-readable instructions stored on the storage medium and configured to program a server system to perform operations including;

marking one or more entries in a table for a first part of a storage unit memory as out of date, the table indicating identities of tracts of data stored in the storage unit memory and locations in the storage unit memory where the tracts are stored;

writing tracts received in a plurality of write requests to the first part of the storage unit memory; and

in response to filling the first part of the storage unit memory,

updating the one or more entries marked out of date with the identities of the written tracts and their locations, and

marking additional one or more entries for a second part of the storage unit memory as out of date.

14. The computer-readable storage medium of claim 13, wherein the operations further include selecting a size of the first part and the second part that reduces a number of movements across a disk comprising the storage unit memory of a component that writes to and reads from the storage unit memory.

15. The computer-readable storage medium of claim 14, wherein the operations further include queuing a read request and performing the read request when the component is within a predetermined distance of the tract associated with the read request.

16. The computer-readable storage medium of claim 14, wherein the operations further include determining which location within the first part to write a tract to based at least in part on read requests received by the server system.

17. The computer-readable storage medium of claim 13, wherein the operations further include updating the one or more entries marked out of date with the identities of the written tracts and their locations while the server system is idle.

18. The computer-readable storage medium of claim 13, wherein the operations further include caching identities of the tracts received in the write requests and locations where the data items were written and performing the updating based at least in part on the cached identities and locations.

19. The computer-readable storage medium of claim 13, wherein the operations further include updating entries marked out of date when recovering from a failure, the updating including scanning parts of the storage unit memory associated with the entries marked out of date.

20. The computer-readable storage medium of claim 13, wherein each tract has a same size as other tracts is associated with a tract identifier, and each tract identifier has a same size as other tract identifiers and is stored next to the tract it identifies.