Patent Number: 7,769,792

Title: Low overhead thread synchronization system and method for garbage collecting stale data in a document repository without interrupting concurrent querying

Abstract: A tokenspace repository stores documents as a sequence of tokens. In each of a sequence of non-overlapping epochs, execution of a respective set of queries against the repository is initiated in a plurality of threads. During each epoch, entries identifying portions of the repository to be deleted are added to a respective epoch-specific list. The system or process maintains a respective epoch-specific count of the number of threads that potentially reference any of the portions of the repository identified by entries in the respective epoch-specific list; and it also maintains the epoch-specific count of each prior epoch whose epoch-specific count is not equal to a predefined final value. After the end of each epoch, when the corresponding epoch-specific count reaches the predefined final value, the system or process deletes from the repository all portions of the repository corresponding to the entries in the corresponding epoch-specific list.

Inventors: Burrows; Michael (Palo Alto, CA), Dean; Jeffrey A. (Palo Alto, CA)

Assignee: Google Inc.

International Classification: G06F 17/30 (20060101)

Expiration Date: 8/03/12018