Lock-free updates to a data retention index

A method, comprising:

• providing a plurality of different processes with concurrent access to a data retention index comprising entries storing indications of data objects stored in a data store different from the data retention index, comprising:
• accessing a lock-free data structure to obtain different keys identifying respective ones of the entries of the data retention index for the different processes, wherein the lock-free data structure is different from the data retention index and the data objects;
• concurrently updating, subsequent to obtaining the different keys, the respective ones of the entries of the data retention index identified by the different keys to concurrently update indications of one or more of the data objects in the data store to retain;
• evaluating the data retention index to determine one or more other ones of the data objects in the data store not indicated in the data retention index to be retained in the data store;
• and
• identifying portions of the storage that store the determined one or more other ones of the data objects for reclamation.

A non-transitory, computer-readable storage medium, storing program instructions that when executed by one or more computing devices cause the one or more computing devices to implement:

• accessing, by a plurality of processes, a lock-free data structure to obtain different keys identifying respective entries of a data retention index, the data retention index comprising a plurality of entries storing indications of data objects to retain, the data objects stored in a data store different from the data retention index, wherein the lock-free data structure is different from the data retention index and the data objects;
• concurrently updating, by at least a first process and a second process of the plurality of processes subsequent to obtaining the different keys, respective entries in the data retention index identified by the different keys to concurrently update indications of one or more of the data objects in the data store to retain;
• evaluating the data retention index to determine one or more other ones of the data objects in the data store not indicated in the data retention index to be retained in the data store;
• and
• reclaiming one or more portions of the data store that store the determined one or more other ones of the data objects.