Anti-item for deletion of content in a distributed datastore

• US 7,774,308 B2
• Filed: 07/08/2005
• Issued: 08/10/2010
• Est. Priority Date: 12/15/2004
• Status: Expired due to Fees

• Current Assignee: Applied Invention, LLC
• Original Assignee: Applied Minds, Inc.
• Inventors: Hillis, W. Daniel
• Primary Examiner(s): Jalil; Neveen Abel
• Assistant Examiner(s): LIANG, VEI CHUNG
• Application Number:
  US11/177,789
• Publication Number:
  US 20060129517A1
• Time in Patent Office: 1,859 Days
• Field of Search: 719/316, 719/317, 717/132, 717/103
• US Class Current: 707/622
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: Y10S 707/966 Distributed

Abstract

An apparatus and method efficiently delete a first items within a distributed datastore. In particular, an already well defined procedure for insertion of data is used for deletion. Deletion of a first item is effected through the insertion of a second item. The second item can contain a deletion key or be denoted by an appended flag or modified associated meta-data value. The first item can be deleted upon arrival of the second item or subsequent to arrival through an offline garbage collection process.

Claims

1. A method for effectively deleting a first item stored in at least one storage location within a distributed datastore, comprising the steps of:

propagating said first item to said at least one storage location within said distributed datastore using a single insertion procedure;

inserting an anti-item into said distributed datastore, wherein said anti-item comprises a data item having a structure configured to effectively delete said first item from said at least one storage location within said datastore, wherein said first item and said anti-item comprise tuples having the same structure, but for a deletion key value, wherein said deletion key value distinguishes said first item from said anti-item; and

wherein effective deletion comprises excluding said first item from subsequent data retrieval operations; and

propagating said anti-item using said single insertion procedure, wherein said single insertion procedure ignores said deletion key value when propagating said first item and said anti-item, and wherein said single insertion procedure ensures that said anti-item reaches each of said at least one storage location of said first item.

2. The method of claim 1, wherein said tuples comprise numeric values.

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

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

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

6. The method of claim 1, wherein said effective deletion of said first item comprises the step of:

storing said first item and said anti-item.

7. An apparatus for effectively deleting a first item stored in at least one storage location within a distributed datastore, comprising:

one or more processors configured for performing a single insertion procedure for propagating said first item to said at least one storage location within said distributed datastore;

a computer program product comprising a computer-readable medium having computer-readable program code configured to be executed to insert an anti-item into said distributed datastore, wherein said anti-item comprises a data item having a structure configured to effectively delete said first item from said at least one storage location within said datastore, wherein said first item and said anti-item comprise tuples having the same structure, but for a deletion key value; and

wherein effective deletion comprises excluding said first item from subsequent data retrieval operations; and

wherein said one or more processors are further configured for performing said single insertion procedure for propagating said anti-item, wherein said single insertion procedure ignores said deletion key value when propagating said first item and said anti-item, and wherein said single insertion procedure ensures that said anti-item reaches each of said at least one storage location of said first item.

8. The apparatus of claim 7, wherein said tuples comprise numeric values.

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

10. The apparatus of claim 7, wherein said effective deletion of said first item comprises removing said first item and said anti-item from said distributed datastore immediately upon arrival of said anti-item at said at least one storage location.

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

12. The apparatus of claim 7, wherein said effective deletion of said first item comprises:

means for storing said first item and said anti-item at said at least one storage location.

13. A distributed computing architecture having a plurality of nodes and a plurality of client computing devices, said distributed computing architecture configured for effectively deleting a first item stored in at least one storage location within a distributed datastore, comprising:

at least one client computing device selected from among said plurality of client computing devices comprising a computer program product for;

inserting at least a first item into said distributed datastore;

at least one node selected from among a plurality of nodes comprising at least one processor configured for;

propagating said first item to said at least one storage location within said distributed datastore using a single insertion procedure;

wherein said computer program product within said at least one client is further configured for;

inserting an anti-item into said distributed datastore, wherein said anti-item comprises a data item having a structure configured to effectively delete said first item from at least one storage location within said datastore, wherein said first item and said anti-item comprise tuples having the same structure, but for a deletion key value, wherein said deletion key value distinguishes said first item from said anti-item, and wherein effective deletion comprises excluding said first item from subsequent data retrieval operations; and

wherein said at least one processor of said at least one node is further configured for;

propagating said anti-item using said single insertion procedure, wherein said single insertion procedure ignores said deletion key value when propagating said first item and said anti-item, and wherein said single insertion procedure ensures that said anti-item reaches each of said at least one storage location of said first item.

14. The architecture of claim 13, wherein said tuples comprise numeric values.

15. The architecture of claim 14, wherein said anti-item comprises a wild card value corresponding to any and all valid values.

16. The architecture of claim 13, wherein said effective deletion of said first item comprises removing said first item and said anti-item from said distributed datastore immediately upon arrival of said anti-item at said at least one storage location.

17. The architecture of claim 13, wherein said effective deletion of said first item comprises means for providing an offline garbage collection process to remove said first item and said anti-item from said distributed datastore substantially after arrival of said anti-item at said at least one storage location.

18. The architecture of claim 13, wherein said effective deletion of said first item comprises:

means for storing said first item and said anti-item at said at least one storage location.

19. An apparatus for effectively deleting a first item stored in at least one storage location within a distributed datastore, comprising:

one or more processors configured for performing a single insertion procedure for propagating said first item to said at least one storage location within said distributed datastore;

a computer program product comprising a computer-readable storage medium having computer-readable program code configured to be executed to insert an anti-item into said distributed datastore, wherein said anti-item comprises a data item having a structure configured to effectively delete said first item from at said least one storage location with said datastore, wherein said first item and said anti-item are distinguished by a binary indicator comprising any one of a flag and meta-data, and wherein effective deletion comprises excluding said first item from subsequent data retrieval operations; and

wherein said one or more processors are further configured to preform said single insertion procedure for propagating said anti-item, wherein said single insertion procedure ignores said binary indicator when propagating said first item and said anti-item, and wherein said single insertion procedure ensures that said anti-item reaches each of said at least one storage location of said first item.