Anti-item for deletion of content in a distributed datastore

• US 8,131,781 B2
• Filed: 08/11/2011
• Issued: 03/06/2012
• Est. Priority Date: 12/15/2004
• Status: Active Grant

• Current Assignee: Applied Invention, LLC
• Original Assignee: Applied Minds LLC
• Inventors: Hillis, W. Daniel
• Primary Examiner(s): LIANG, VEI CHUNG
• Application Number:
  US13/208,225
• Publication Number:
  US 20110302223A1
• Time in Patent Office: 208 Days
• Field of Search: None
• US Class Current: 707/812
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: Y10S 707/966 Distributed

Abstract

The invention provides an efficient apparatus and method for deleting items within a distributed datastore. Deletion of items is accomplished using anti-items having the same structure as a conventional data item, but for a single tag, flag, or bit which indicates that it is an anti-item, wherein the single tag, flag, or bit but does not affect the location at which a data item or anti-item is ultimately stored within the datastore, thereby ensuring that, upon insertion, the anti-item reaches the same location or locations within the datastore as the original data item.

Claims

1. A method of excluding a first item from a retrieval operation operating on a distributed datastore data-store, said method comprising:

inserting a second item into said distributed datastore using an insertion procedure, wherein said first item was previously inserted into said distributed datastore with said insertion procedure, wherein said distributed datastore comprises a plurality of storage locations, and wherein said insertion procedure propagates said first item and said second item to a common set of one or more destinations among said plurality of storage locations;

wherein said first item and said second item each comprise a plurality of key values, one key value for each of a plurality of keys, wherein said retrieval operation is specified using a set of keys from said plurality of keys, wherein said insertion procedure operates based only on said set of keys;

wherein said first item and said second item have equal key values for each key within said set of keys; and

wherein arrival of said second item within said distributed data-store excludes said first item from said retrieval operation.

2. The method of claim 1, wherein said plurality of keys comprises a binary indicator in the form of a deletion key, wherein a key value of said deletion key distinguishes said first item and said second item from one another, and wherein said deletion key is not within said set of keys.

3. The method of claim 1, additionally comprising the step of:

removing said first item and said second item from said distributed datastore immediately upon insertion of said second item into said distributed datastore.

4. The method of claim 1, additionally comprising the step of:

executing an offline garbage collection process to remove said first item and said second item from said distributed datastore substantially after insertion of said second item into said distributed datastore.

5. The method of claim 1, wherein said plurality of key values are numeric.

6. The method of claim 1, wherein said second item comprises a wild card key value corresponding to any and all valid key values.