Locator Table and Client Library for Datacenters

• US 20110258297A1
• Filed: 04/19/2010
• Published: 10/20/2011
• Est. Priority Date: 04/19/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Elson, Jeremy E., Hunt, Galen C., Nightingale, Edmund B., Howell, Jonathan R.
• Granted Patent: US 8,533,299 B2
• Time in Patent Office: Days
• US Class Current: 709/220
• 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/2094 Redundant storage or storage space G06F11/2056 takes precedence
• 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 comprising:

identifying, by a client system, at least one server as being associated with a tract of data, the tract of data being one of a plurality of tracts of data comprising a byte sequence and the identifying includes looking up the at least one server in a locator table that distributes the tracts among a plurality of servers, the locator table distributing the tracts by associating servers with tracts based at least in part on translations to fixed lengths of tract identifiers; and

providing, by the client system, a request associated with the tract to the at least one server.

2. The method of claim 1, wherein the translations ensure that two sequential tracts are associated with different servers.

3. The method of claim 1, wherein the associating comprises associating based on prefixes included in the translations, at least one of the prefixes being shared between multiple translations and the tracts respectively associated with the multiple translations.

4. The method of claim 3, wherein each entry of the locator table includes a prefix and one or more servers associated with the prefix.

5. The method of claim 1, further comprising calculating the translations using a hash algorithm.

6. The method of claim 1, further comprising utilizing at least a prefix included in a translation to lookup the at least one server, the locator table indexing the plurality of servers by prefixes included in the translations.

7. The method of claim 1, further comprising receiving a request for the byte sequence from a file system interface of the client system, the file system interface representing the byte sequence as a file.

8. The method of claim 1, wherein the looking up is based at least in part on a tract identifier of the tract, the tract identifier comprising a byte sequence identifier and a tract sequence number.

9. The method of claim 1, wherein the request is one of a plurality of read requests for the tracts comprising the byte sequence, and the client system receives the tracts from the plurality of servers in parallel.

10. The method of claim 1, further comprising receiving a tract of an empty length in response to a read request for the tract in an event that the tract has not been written to.

11. A computer-readable storage medium comprising:

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

generating a locator table that distributes a plurality of tracts of data among a plurality of servers by associating servers with tracts based at least on a number of available servers and on translations to fixed lengths of tract identifiers, the translations ensuring that two sequential tracts are associated with different servers; and

making available the locator table to at least one client system.

12. The computer-readable storage medium of claim 11, wherein the associating comprises associating based at least in part on prefixes included in the translations, at least one of the prefixes being shared between multiple translations and the tracts respectively associated with the multiple translations,

wherein the operations further include notifying servers of the prefixes that the servers are associated with, and

wherein multiple servers are associated with each tract to provide redundancy.

13. The computer-readable storage medium of claim 12, wherein a size of the locator table and/or a size of the prefixes are related to a number of the servers that are available.

14. The computer-readable storage medium of claim 11, wherein the locator table accommodates the inclusion of new tracts without requiring a refresh or update of the locator table.

15. The computer-readable storage medium of claim 11, wherein multiple servers are associated with each tract to provide redundancy.

16. The computer-readable storage medium of claim 11, wherein the operations further include updating the locator table in response to a failure of one of the servers or in response to an addition of a new server to the plurality of servers.

17. The computer-readable storage medium of claim 11, wherein at least one of the servers is identified in the locator table by an Internet Protocol (IP) address.

18. A client system comprising:

a processor; and

a plurality of executable instructions configured to be operated by the processor to program the client system to perform operations including;

determining whether a byte sequence has been opened in an append mode or a random write mode;

in response to determining that the byte sequence has been opened in an append mode, requesting allocation of a tract of data belonging to the byte sequence and writing to the requested tract; and

in response to determining that the byte sequence has been opened in a random write mode, writing to a tract of data belonging to the byte sequence.

19. The client system of claim 18, wherein the operations further include coordinating with other client systems about how to open the byte sequence.

20. The client system of claim 18, wherein the tract allocated in response to the request is a next available tract in the byte sequence.