×

Data consistency within a federation infrastructure

  • US 8,090,880 B2
  • Filed: 11/07/2007
  • Issued: 01/03/2012
  • Est. Priority Date: 11/09/2006
  • Status: Expired due to Fees
First Claim
Patent Images

1. In a federation infrastructure of a ring of nodes configured for bi-directional routing, a method for performing a data access transaction within a replica set maintained within a federation infrastructure, the method comprising:

  • an act of determining that a primary node has been elected from among a plurality of nodes in a replica set of nodes, the primary node being configured to accept and process client data access requests, the replica set comprising the primary node and one or more secondary nodes;

    an act of determining that the replica set includes a minimum number of secondary nodes as members based on a maximum number of tolerable simultaneous failures of secondary nodes of the replica set, the act further comprising;

    determining that the minimum number of secondary nodes is at least a write quorum defining a minimum number of secondary nodes necessary to perform a request to write data and to provide complete fault tolerance for the maximum number of tolerable simultaneous failures; and

    determining that the minimum number of secondary nodes is at least a read quorum defining a minimum number of secondary nodes necessary to provide complete fault tolerance for the maximum number of tolerable simultaneous failures;

    an act of the primary node receiving one or more client data access requests, each data access request indicating at least a portion of data that is to be accessed on at least the primary node in the replica set, each data access request comprising one of a request to write data to at least a write quorum of nodes in the replica set or a request to read data from at least one of the nodes in the replica set;

    an act of the primary node assigning a data sequence number (DSN) to each of the client data access requests that mutate state in the order the client data access requests are received, the data sequence numbers comprising a linearized processing order that is to be followed by each of the nodes in the replica set;

    an act of the primary node sending at least one of the client data access requests including any corresponding data sequence numbers to at least one of the secondary nodes, the sending including the primary node sending the data access request to at least the write quorum of nodes when the request is a request to write data, and the primary node sending the data access request to at least one of the secondary nodes when the request is a request to read data;

    an act of the primary node receiving, from at least a threshold number of secondary nodes, an acknowledgement indicating reception of the client data access request; and

    an act of the primary node committing the data access request, the committing including, when the data access request is a write request, verifying that the threshold number of secondary nodes acknowledging reception of the client data access request meets the write quorum of nodes and subsequently writing the data locally at the primary node according to the client data access request, and when the data access request is a read request, reading the data from the at least one of the secondary nodes.

View all claims
  • 2 Assignments
Timeline View
Assignment View
    ×
    ×