Distributed data store with an orderstamp to ensure progress

• US 20070011159A1
• Filed: 12/14/2005
• Published: 01/11/2007
• Est. Priority Date: 12/15/2004
• Status: Active Grant

• Current Assignee: Applied Invention, LLC
• Original Assignee: Applied Minds, Inc.
• Inventors: Hillis, W. Daniel, Bax, Eric, Kolehmainen, Mathias
• Granted Patent: US 7,590,635 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2322 using timestamps
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

A distributed data store labels operations with globally unique identifiers that contain approximate timestamps. The labels are used to address causes of inconsistency in the distributed data store while ensuring progress. A first mode is provided that stores the latest label for each entry is useful if re-inserts and deletes are rare. Another mode is provided that stores a history of labels for each entry can be used if there are many re-inserts and deletes. A further mode is provided that stores a history of labels for queries can report updates to query answers as inserts and deletes settle across the distributed data store.

Claims

1. A method for addressing inconsistency and ensuring progress in a distributed data store, comprising the steps of:

labeling an insert with an orderstamp;

recording for each entry in a computer the latest orderstamp among orderstamps for insert operations for that entry that have been processed by the computer;

labeling a query with an orderstamp; and

when processing a query on a computer, identifying entries that are in a subset specified by the query, that are covered by the computer, and that have latest insert orderstamp before the orderstamp of the query.

2. A method for addressing inconsistency and ensuring progress in a distributed data store, comprising the steps of:

labeling an insert with an orderstamp;

labeling a delete with an orderstamp;

recording for each entry in a computer a latest orderstamp and among orderstamps for insert and delete operations for that entry that have been processed by the computer;

recording for each entry in the computer whether an operation corresponding to the latest orderstamp is an insert or a delete;

labeling a query with an orderstamp; and

when processing a query on a computer, identifying entries that are in a subset specified by the query, that are covered by the computer, that have latest orderstamp before the orderstamp of the query, and that have operation type insert corresponding to the latest orderstamp.

3. The method of claim 2, further comprising the steps of:

when processing a query on a computer, identifying whether there is at least one entry that is in a subset specified by the query, that is covered by the computer, and that has latest orderstamp after the orderstamp of the query; and

if there is such an entry, indicating that the query answer may have been affected by a re-insert or a delete.

4. A method for addressing inconsistency and ensuring progress in a distributed data store, comprising the steps of:

labeling an insert with an orderstamp;

labeling a delete with an orderstamp;

recording for each entry in a computer a history of inserts and deletes and for that entry that have been processed by the computer and corresponding orderstamps;

labeling a query with an orderstamp;

when processing a query on a computer, identifying entries that are in a subset specified by the query, that are covered by the computer, that have in the history for the entry an orderstamp before the orderstamp of the query, and that have in the history for the entry latest orderstamp before the orderstamp of the query corresponding to an insert.

5. A method for addressing inconsistency and ensuring progress in a distributed data store, comprising the steps of:

labeling an insert with an orderstamp;

labeling a delete with an orderstamp;

recording for each entry in a computer a history of inserts and deletes and for that entry that have been processed by the computer and corresponding orderstamps;

labeling a query with an orderstamp;

recording for a computer a history of queries processed by the computer and the corresponding orderstamps;

when processing a query on a computer, identifying entries that are in a subset specified by the query, that are covered by the computer, that have in the history for the entry an orderstamp before the orderstamp of the query, and that have in the history for the entry latest orderstamp before the orderstamp of the query corresponding to an insert.

6. The method of claim 5, further comprising the steps of:

when processing an insert or delete, determining whether having processed the insert or delete before any queries in the query history would have affected the query answers; and

if so, indicating which queries would have been affected.

7. A distributed data store, comprising:

a set of modes of operation, each mode using orderstamps to address any of the following concerns;

inconsistency due to duplicate operations;

inconsistency due to order of operations;

inconsistency due to synchronization, query ceilings; and

inconsistency due to settling.

8. The data store of claim 7, said modes comprising any of a mode for:

maintaining greatest insert or delete orderstamp for each entry;

maintaining insert and delete history for each entry; and

maintaining insert, delete, and query histories.

9. The data store of claim 7, said mode comprising:

means for labeling an insert with an orderstamp;

means for recording for each entry in a computer the latest orderstamp among orderstamps for insert operations for that entry that have been processed by the computer;

means for labeling a query with an orderstamp; and

when processing a query on a computer, means for identifying entries that are in a subset specified by the query, that are covered by the computer, and that have latest insert orderstamp before the orderstamp of the query.

10. The data store of claim 7, said mode comprising:

means for labeling an insert with an orderstamp;

means for labeling a delete with an orderstamp;

means for recording for each entry in a computer a latest orderstamp and among orderstamps for insert and delete operations for that entry that have been processed by the computer;

means for recording for each entry in the computer whether an operation corresponding to the latest orderstamp is an insert or a delete;

means for labeling a query with an orderstamp; and

when processing a query on a computer, means for identifying entries that are in a subset specified by the query, that are covered by the computer, that have latest orderstamp before the orderstamp of the query, and that have operation type insert corresponding to the latest orderstamp.

11. The data store of claim 7, said mode comprising:

means for labeling an insert with an orderstamp;

means for labeling a delete with an orderstamp;

means for recording for each entry in a computer a history of inserts and deletes and for that entry that have been processed by the computer and corresponding orderstamps;

means for labeling a query with an orderstamp;

when processing a query on a computer, means for identifying entries that are in a subset specified by the query, that are covered by the computer, that have in the history for the entry an orderstamp before the orderstamp of the query, and that have in the history for the entry latest orderstamp before the orderstamp of the query corresponding to an insert.

12. The data store of claim 7, said mode comprising:

means for labeling an insert with an orderstamp;

means for labeling a delete with an orderstamp;

means for recording for each entry in a computer a history of inserts and deletes and for that entry that have been processed by the computer and corresponding orderstamps;

means for labeling a query with an orderstamp;

means for recording for a computer a history of queries processed by the computer and the corresponding orderstamps;

when processing a query on a computer, means for identifying entries that are in a subset specified by the query, that are covered by the computer, that have in the history for the entry an orderstamp before the orderstamp of the query, and that have in the history for the entry latest orderstamp before the orderstamp of the query corresponding to an insert.

13. A method for a computer reclaiming storage periodically, continuously using a low-priority thread, or when storage is needed, comprising the steps of:

determining if memory time exceeds settling time, in which case there is no inconsistency due to settling;

determining if a computer records a time up to which it has reclaimed storage (cut time), wherein said computer recognizes and reports operations that arrive with orderstamps that have time earlier than said cut time;

determining if a computer processes a query when said cut time of said computer is after a query ceiling, wherein said computer reports as possible sources of inconsistency due to settling any entries that are in a subset specified by said query and have an earliest orderstamp in an entry history after a query ceiling; and

determining if a computer processes an insert or delete when said cut time of said computer is later than a time of an orderstamp of an insert or delete operation, wherein said computer includes said operation in a history for an entry only if said entry has no history or if said entry history includes an orderstamp before an orderstamp of the insert or delete operation being processed.