Anti-item for deletion of content in a distributed datastore

• US 20060129517A1
• Filed: 07/08/2005
• Published: 06/15/2006
• Est. Priority Date: 12/15/2004
• Status: Active Grant

• Current Assignee: Applied Invention, LLC
• Original Assignee: Applied Minds, Inc.
• Inventors: Hillis, W. Daniel
• Granted Patent: US 7,774,308 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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. In particular, the invention provides an apparatus and method of deletion that uses an already well defined procedure for insertion of data.

Claims

1. A method for deleting a data item from within a distributed datastore, comprising the steps of:

inserting an anti-item into said distributed datastore;

propagating said anti-item to at least one storage location within said datastore using an insertion procedure; and

effecting deletion of said data item from said at least one storage location after arrival of said anti-item at said at least one storage location;

wherein said data item was previously inserted using said insertion procedure.

2. The method of claim 1, said insertion procedure comprising the step of:

propagating said data item and said anti-item based on a structure of said data item and said anti-item;

wherein said structure of said data item and said anti-item ensure propagation of said data item and said anti-item to a common set of data storage locations by said insertion procedure.

3. The method of claim 1, wherein said data item and said anti-item comprise tuples having numeric values;

and wherein said insertion procedure comprises the step of propagating said data item and said anti-item based upon at least one of said numeric values.

4. The method of claim 3, wherein each of said tuples comprises a deletion key value;

wherein said deletion key value distinguishes said data item from said anti-item; and

wherein said insertion procedure does not propagate said data item and said anti-item based upon said deletion key value.

5. The method of claim 3, wherein said anti-item comprises a wild card value corresponding to any and all valid key values.

6. The method of claim 1, wherein said effecting deletion step comprises the step of removing said data item and said anti-item from said distributed datastore immediately upon arrival of said anti-item at said at least one storage location.

7. The method of claim 1, wherein said effecting deletion step comprises the step of providing an offline garbage collection process to remove said data item and said anti-item from said distributed datastore substantially after arrival of said anti-item at said at least one storage location.

8. The method of claim 1, wherein said effecting deletion step comprises the step of:

storing said data item and said anti-item at said at least one storage location; and

subsequently excluding said data item from operations retrieving data from said distributed datastore.

9. An apparatus for deleting a data item from within a distributed datastore, comprising:

means for inserting an anti-item into said distributed datastore;

means for propagating said anti-item to at least one storage location within said datastore using an insertion mechanism; and

means for effecting deletion of said data item from said at least one storage location after arrival of said anti-item at said at least one storage location;

wherein said data item was previously inserted using said insertion mechanism.

10. The apparatus of claim 9, said insertion mechanism comprising:

means for propagating said data item and said anti-item based on a structure of said data item and said anti-item;

wherein said structure of said data item and said anti-item ensure propagation of said data item and said anti-item to a common set of data storage locations by said insertion mechanism.

11. The apparatus of claim 9, wherein said data item and said anti-item comprise tuples having numeric values;

and wherein said insertion mechanism comprises means for propagating said data item and said anti-item based upon at least one of said numeric values.

12. The apparatus of claim 11, wherein each of said tuples comprises a deletion key value;

wherein said deletion key value distinguishes said data item from said anti-item; and

wherein said insertion mechanism does not propagate said data item and said anti-item based upon said deletion key value.

13. The apparatus of claim 11, wherein said anti-item comprises a wild card value corresponding to any and all valid key values.

14. The apparatus of claim 9, wherein said means for effecting deletion comprises removing said data item and said anti-item from said distributed datastore immediately upon arrival of said anti-item at said at least one storage location.

15. The apparatus of claim 9, wherein said means for effecting deletion comprises means for providing an offline garbage collection process to remove said data item and said anti-item from said distributed datastore substantially after arrival of said anti-item at said at least one storage location.

16. The apparatus of claim 9, wherein said means for effecting deletion comprises:

means for storing said data item and said anti-item at said at least one storage location; and

means for subsequently excluding said data item from operations retrieving data from said distributed datastore.