Anti-Item for Deletion of Content In A Distributed Datastore

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.

1 . A method of excluding a first item from a retrieval operation in a distributed datastore, said method comprising:
 inserting a second item into said distributed datastore, wherein said first item was previously inserted into said distributed datastore;   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 first item and said second item have equal key values for each key within said set of keys; and   wherein insertion 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.