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

• US 10,019,456 B2
• Filed: 06/29/2016
• Issued: 07/10/2018
• Est. Priority Date: 06/29/2016
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Markiewicz, Marcus, Borden, Nicolas
• Primary Examiner(s): DOAN, DUC T
• Application Number:
  US15/197,689
• Publication Number:
  US 20180004769A1
• Time in Patent Office: 741 Days
• Field of Search: None
• CPC Class Codes: G06F 16/14 Details of searching files based on file metadata
• CPC Class Codes: G06F 16/162 Delete operations erasing in storage systems G06F3/0652
• CPC Class Codes: G06F 16/1727 Details of free space management performed by the file system saving storage space on storage systems G06F3/0608; management of blocks in storage devices G06F3/064
• CPC Class Codes: G06F 16/1752 based on file chunks
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 3/0685 Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays

Abstract

To identify objects shared by entities and to, in turn, identify free space in nonvolatile storage, a computer system uses a probabilistic data structure which tests whether an element is a member of a set. Such probabilistic data structures are created for entities in the storage system that share objects. The probabilistic data structure for an entity represents the objects that are used by that entity. When an entity is deleted, each object used by that entity is compared to the probabilistic data structures of other entities to determine if there is a likelihood that the object is used by one or more of the other entities. If the likelihood determined for an object is above an acceptable threshold, then the object is not deleted. If the likelihood determined for an object is below the set threshold, then the object can be deleted and the corresponding storage locations can be marked as free.

Claims

1. A computer 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, wherein each entity includes one or more of the stored plurality of objects, wherein at least a first entity and a second entity of the plurality of entities can share objects;

a processing system comprising a processing unit and a memory, the processing system configured to;

in response to creating the 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 the 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; and

in response to deleting the second entity, for each object in the second set of the objects;

for each entity of the plurality of entities, apply a probabilistic data structure of the entity to the object to determine if the object likely is included in the entity, and

in response to a determination that the object is not likely included in any entity in the plurality of entities, delete the object.

2. The computer of claim 1, wherein the first probabilistic data structure comprises an array of a Bloom filter.

3. The computer of claim 1, wherein the first entity and the second entity are files in a file system.

4. The computer of claim 3, wherein the plurality of objects comprises blocks of data of files in the file system.

5. The computer of claim 1, wherein the first entity and the second entity are entities maintained by a storage management system that stores objects in files of a file system.

6. The computer of claim 1, wherein the probabilistic data structure for an entity, when queried with an identifier of an object, outputs a likelihood that the object is a member of a set objects included in the entity without allowing a false negative result.

7. 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, wherein each entity includes one or more of the stored plurality of objects, wherein at least a first entity and a second entity of the plurality of objects can share objects;

the processing system configured to;

in response to creating the 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 the 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; and

in response to deleting the second entity, for each object in the second set of the objects;

for each entity of the plurality of entities, apply a probabilistic data structure of the entity to the object to determine if the object likely is included in the entity, and

in response to a determination that the object is not likely included in any entity in the plurality of entities, delete the object.

8. The article of manufacture of claim 7, wherein the first probabilistic data structure comprises an array of a Bloom filter.

9. The article of manufacture of claim 7, wherein the first entity and the second entity are files in a file system.

10. The article of manufacture of claim 9, wherein the plurality of objects comprises blocks of data of files in the file system.

11. The article of manufacture of claim 7, wherein the first entity and the second entity are entities maintained by a storage management system that stores objects in files of a file system.

12. The article of manufacture of claim 7, wherein the probabilistic data structure for an entity, when queried with an identifier of an object, outputs a likelihood that the object is a member of a set objects included in the entity without allowing a false negative result.

13. 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 each entity includes one or more of the stored plurality of objects, wherein a first entity and a second entity in the plurality of objects can share objects, the computer-implemented process comprising:

in response to creating the 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 the 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;

for each entity of the plurality of entities, apply a probabilistic data structure of the entity to the object to determine if the object likely is included in the entity, and

in response to a determination that the object is not likely included in any entity in the plurality of entities, delete the object.

14. The computer-implemented process of claim 13, wherein the first probabilistic data structure comprises an array of a Bloom filter.

15. The computer-implemented process of claim 13, wherein the first entity and the second entity are files in a file system.

16. The computer-implemented process of claim 13, wherein the plurality of objects comprises blocks of data of files in the file system.

17. The computer-implemented process of claim 13, wherein the first entity and the second entity are entities maintained by a storage management system that stores objects in files of a file system.

18. The computer-implemented process of claim 13, wherein the probabilistic data structure for an entity, when queried with an identifier of an object, outputs a likelihood that the object is a member of a set objects included in the entity without allowing a false negative result.