Recovering free space in nonvolatile storage with a computer storage system supporting shared objects

An article of manufacture comprising:

• a computer storage device,
• computer program instructions stored on the computer storage device which, when processed by a processing system of a computer, the processing system comprising a processing unit and a memory, configures the computer to be comprising:
• a nonvolatile storage device;
• a plurality of objects stored on the nonvolatile storage device;
• a plurality of entities stored on the nonvolatile storage device, an entity comprising one or more of the stored plurality of objects, wherein a first entity and a second entity can share objects;
• the processing system configured to:
• in response to creating a first entity comprising a first set of the objects, generate a first probabilistic data structure representing inclusion of the first set of the objects in the first entity;
• in response to creating a second entity comprising a second set of the objects, generate a second probabilistic data structure representing inclusion of the second set of the objects in the second entity;
• in response to deleting the second entity, for each object in the second set of the objects, apply the first probabilistic data structure to determine if the object likely is in the first set of the objects.

A computer-implemented process performed by a computer program executing on a computer, the computer comprising a processing system, comprising a processing unit and a memory, and a nonvolatile storage device, a plurality of objects stored on the nonvolatile storage device, and a plurality of entities stored on the nonvolatile storage device, wherein an entity comprises one or more of the stored plurality of objects, wherein a first entity and a second entity can share objects, the computer-implemented process comprising:

• in response to creating a first entity comprising a first set of the objects, generating a first probabilistic data structure representing inclusion of the first set of the objects in the first entity;
• in response to creating a second entity comprising a second set of the objects, generating a second probabilistic data structure representing inclusion of the second set of the objects in the second entity;
• and
• in response to deleting the second entity, for each object in the second set of the objects, applying the first probabilistic data structure to determine if the object likely is in the first set of the objects.