Parallel Serialization of Request Processing

• US 20120197958A1
• Filed: 01/31/2011
• Published: 08/02/2012
• Est. Priority Date: 01/31/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Nightingale, Edmund B., Elson, Jeremy E.
• Granted Patent: US 8,996,611 B2
• Time in Patent Office: Days
• US Class Current: 709/201
• CPC Class Codes: G06F 2209/5017 Task decomposition
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals

Abstract

A plurality of servers configured to receive a plurality of requests associated with a plurality of byte sequences are described herein. The requests for each byte sequence are received by a single one of the servers. Each server is further configured to serially process the requests it receives while the other servers also perform serial processing of requests in parallel with the server. Also, the requests for each byte sequence are transmitted to the single one of the servers by a plurality of clients, each client independently identifying the single one of the servers for the byte sequence based on system metadata.

Claims

1. A method comprising:

receiving, by a plurality of servers, a plurality of requests associated with a plurality of byte sequences, the requests for each byte sequence being received by a single one of the servers; and

serially processing the requests at each of the servers, wherein the plurality of servers perform the processing in parallel with respect to each other.

2. The method of claim 1, wherein the requests include at least one of create requests for creating byte sequences, extend requests for extending byte sequences, or delete requests for deleting byte sequences.

3. The method of claim 2, further comprising gathering a plurality of extend requests for a byte sequence, processing the gathered extend requests as a single extend request, and responding to clients that sent the gathered extend requests as if the gathered extend requests were processed individually.

4. The method of claim 2, wherein the requests include the extend requests for extending byte sequences and processing an extend request comprises assigning a client that sent the extend request a plurality of tracts of data belonging to the byte sequence that is extended by the extend request.

5. The method of claim 1, wherein the requests are requests for operations that require coordination between multiple clients.

6. The method of claim 1, wherein the requests identify a plurality of replica servers and the serially processing comprises performing a two-phase commit at each server and the replica servers of that server.

7. The method of claim 1, wherein metadata for each byte sequence is stored on the server processing the requests for that byte sequence.

8. The method of claim 1, further comprising, in response to determining that a request is a create request for a byte sequence that has already been created or a delete request for a byte sequence that has already been deleted, notifying a client that transmitted the create request or the delete request that the create request or the delete request has failed.

9. The method of claim 1, further comprising notifying clients that sent the requests of the success or failure of the requests.

10. The method of claim 1, further comprising:

comparing, by each server, a version identifier included in one of the requests with a version identifier known to the server, the version identifiers being associated with a locator table;

when the version identifier in the request indicates a more recent version than the version identifier known to the server, updating the version identifier known to the server; and

when the version identifier known to the server indicates a more recent version than the version identifier in the request, notifying a client that sent the request that the request has failed.

11. A system comprising:

a plurality of servers each including a processor, a storage device, and logic configured to perform operations including;

receiving a plurality of requests associated with a byte sequence, wherein the requests are for operations that require coordination between multiple clients,

serially processing the requests, and

storing results of the requests in the storage device as metadata of the byte sequence,

wherein the plurality of servers perform the processing in parallel with respect to each other.

12. The system of claim 11, wherein the servers are tract servers each storing a plurality of tracts of data associated with multiple byte sequences in the storage device of that server, the multiple byte sequences each being comprised of multiple tracts of data.

13. The system of claim 12, wherein the operations of the servers collectively include processing read requests or write requests in parallel with the serially processed requests.

14. A method comprising:

receiving, by each of a plurality of client devices, system metadata associated with a plurality of servers;

based at least in part on the system metadata, identifying, by each of the plurality of client devices, one of the plurality of servers as storing metadata for a byte sequence, the client devices each independently identifying the same one of the plurality of servers for the same byte sequence; and

sending, by each of the plurality of client devices, requests associated with the metadata of the byte sequence to the identified server.

15. The method of claim 14, wherein the system metadata includes a locator table associating servers with fixed length representations, each fixed length representation associated with one or more translations of one or more tract identifiers.

16. The method of claim 15, wherein the metadata for the byte sequence is associated with a tract identifier comprised of a byte sequence identifier and a reserved offset value.

17. The method of claim 16, further comprising generating the byte sequence identifier by one of the client devices prior to transmitting a create request for the byte sequence.

18. The method of claim 14, wherein the requests include at least one of a size request to determine a size of the byte sequence, a create request for creating the byte sequence, an extend request for extending the byte sequence, or a delete request for deleting the byte sequence.

19. The method of claim 18, wherein each client device is enabled to perform read or write operations to the byte sequence by sending a request associated with the metadata of the byte sequence and by receiving a response to that request.

20. The method of claim 14, further comprising identifying replicas of the identified server and including identifications of the replicas in the requests.