Back to results
US 2010/0146331 A1Published application
System and Method for Logging Operations
AssigneeYahoo! Inc.
InventorsBenjamin Reed, Flavio Junqueira
Life of this patent
Estimating the term…
Abstract
In a system for storing and retrieving a plurality of records, the plurality of records associated with a ledger, a client issues read and write requests associated with one of the plurality of records, a plurality of record servers responds to the requests received from the client, and a management server maintains and coordinates, between the client and the record servers, information associated with the ledger, records, and record servers.
Claims23
A system for storing and retrieving at least one of a plurality of records, the plurality of records associated with a ledger, said system comprising:
- a client for issuing read and write requests associated with the at least one record;
- a plurality of record servers for responding to the requests received from the client, wherein each record server comprises:
- a request processor for receiving the requests issued by the client;
- and
- at least one ledger device for storing or retrieving the at least one record according to a write or read instruction received from the request processor, wherein the ledger is assigned to the at least one ledger device;
- a management server for maintaining and coordinating, between the client and the record servers, information associated with the at least one ledger device, the at least one record, and the plurality of record servers.
3 more elements
A method of storing a first record to a plurality of record servers, said method comprising using a processor to perform the steps of:
- associating the first record with a ledger;
- selecting, from the plurality of record servers, a first subset of record servers, wherein each record server in the first subset is associated with the ledger;
- issuing a write request to each record server in the first subset;
- receiving an acknowledgement from each record server in the first subset that the write was successful;
- if, after a predetermined amount of time, a first acknowledgement is not received from each record server in the first subset, repeating said selecting and said issuing until a first acknowledgement is received from each record server in the first subset;
- if, for any of the plurality of records in the ledger that comes before the first record in the ledger, it is not known whether that record has been written to a second subset of record servers, waiting until a second acknowledgement has been received confirming that the record has been written to the second subset of record servers, wherein each record server in the second subset is associated with the ledger;
- and
- acknowledging that the first record was stored to the first subset.
5 more elements
A method of reading a record associated with a ledger, said method comprising using a processor to perform the steps of:
- selecting a subset of record servers from a plurality of record servers, wherein the subset of record servers is associated with the ledger;
- sending a read request corresponding to the record to each record server in the subset;
- in response to said sending, receiving the record from at least one of the record servers in the subset;
- and
- if the record is not received after a predetermined amount of time, repeating said selecting and said sending until the record is received.
2 more elements
A method of closing out a ledger, said method comprising using a processor to perform the steps of;
- if there are any outstanding records to be written to the ledger, waiting for the writes to complete;
- sending to a management server record information comprising:
- a record ID uniquely identifying the last record written to the ledger;
- and
- a ledger ID uniquely identifying the ledger;
- receiving an acknowledgement from the management server that the record information has been received by the management server;
- if, after a predetermined period of time, an acknowledgement has not been received from the management server, repeating said sending until the management server acknowledges;
- and
- acknowledging that the ledger is closed.
6 more elements
A method of recovering a ledger from a fault, wherein the ledger comprises a plurality of records, said method comprising using a processor to perform the steps of:
- determining a subset of record servers from a plurality of record servers, wherein the subset comprises all record servers in the plurality of record servers that are associated with the ledger;
- receiving, from each record server in the subset, the last record written to the ledger, wherein each record comprises:
- a first record ID uniquely identifying the record;
- and
- a second record ID uniquely identifying the last known record written to the ledger before the record corresponding to the first record ID;
- determining, from the received records, the largest second record ID;
- receiving, from each record server in the subset, a list of record IDs corresponding to every record in the ledger with a record ID greater than the largest second record ID;
- for each record ID i greater than the largest second record ID, starting with one plus the largest second record ID and continuing until the ledger is closed with the record ID of the last record written to the ledger set equal to i minus one:
- if none of the received lists contains a record ID equal to i, closing the ledger;
- attempting to read record i from the record server associated with each of the received lists that contains a record ID equal to i:
- if the record cannot be read from any of the associated record servers, closing the ledger;
- if the record can be read from a quorum of the associated record servers, incrementing i by one;
- and
- if the record can be read from at least one of the associated record servers, but from less than a quorum:
- writing the record to a quorum of record servers from the subset;
- and
- incrementing i by one.
14 more elements
A computer-readable medium encoded with a set of instructions which, when performed by a computer, perform a method of storing a first record to a plurality of record servers, said method comprising:
- associating the first record with a ledger;
- selecting, from the plurality of record servers, a first subset of record servers, wherein each record server in the first subset is associated with the ledger;
- issuing a write request to each record server in the first subset;
- receiving an acknowledgement from each record server in the first subset that the write was successful;
- if, after a predetermined amount of time, a first acknowledgement is not received from each record server in the first subset, repeating said selecting and said issuing until a first acknowledgement is received from each record server in the first subset;
- if, for any of the plurality of records in the ledger that comes before the first record in the ledger, it is not known whether that record has been written to a second subset of record servers, waiting until a second acknowledgement has been received confirming that the record has been written to the second subset of record servers, wherein each record server in the second subset is associated with the ledger;
- and
- acknowledging that the first record was stored to the first subset.
5 more elements
A computer-readable medium encoded with a set of instructions which, when performed by a computer, perform a method of reading a record associated with a ledger, said method comprising:
- selecting a subset of record servers from a plurality of record servers, wherein the subset of record servers is associated with the ledger;
- sending a read request corresponding to the record to each record server in the subset;
- in response to said sending, receiving the record from at least one of the record servers in the subset;
- and
- if the record is not received after a predetermined amount of time, repeating said selecting and said sending until the record is received.
2 more elements
A computer-readable medium encoded with a set of instructions which, when performed by a computer, perform a method of closing out a ledger, said method comprising;
- if there are any outstanding records to be written to the ledger, waiting for the writes to complete;
- sending to a management server record information comprising:
- a record ID uniquely identifying the last record written to the ledger;
- and
- a ledger ID uniquely identifying the ledger;
- receiving an acknowledgement from the management server that the record information has been received by the management server;
- if, after a predetermined period of time, an acknowledgement has not been received from the management server, repeating said sending until the management server acknowledges;
- and
- acknowledging that the ledger is closed.
6 more elements
A computer-readable medium encoded with a set of instructions which, when performed by a computer, perform a method of recovering a ledger from a fault, wherein the ledger comprises a plurality of records, said method comprising:
- determining a subset of record servers from a plurality of record servers, wherein the subset comprises all record servers in the plurality of record servers that are associated with the ledger;
- receiving, from each record server in the subset, the last record written to the ledger, wherein each record comprises:
- a first record ID uniquely identifying the record;
- and
- a second record ID uniquely identifying the last known record written to the ledger before the record corresponding to the first record ID;
- determining, from the received records, the largest second record ID;
- receiving, from each record server in the subset, a list of record IDs corresponding to every record in the ledger with a record ID greater than the largest second record ID;
- for each record ID i greater than the largest second record ID, starting with one plus the largest second record ID and continuing until the ledger is closed with the record ID of the last record written to the ledger set equal to i minus one:
- if none of the received lists contains a record ID equal to i, closing the ledger;
- attempting to read record i from the record server associated with each of the received lists that contains a record ID equal to i:
- if the record cannot be read from any of the associated record servers, closing the ledger;
- if the record can be read from a quorum of the associated record servers, incrementing i by one;
- and
- if the record can be read from at least one of the associated record servers, but from less than a quorum:
- writing the record to a quorum of record servers from the subset;
- and
- incrementing i by one.
14 more elements
Dependencies are inferred from the claim text.