Fast and safe storage space reclamation for a data storage system
US11294805B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Apr 11, 2019 |
| Grant date | Apr 5, 2022 |
| Priority date | — |
| Expiry date | Oct 22, 2039 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F3/0688
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
The disclosed technology generally describes efficient garbage collection operations based on chunk filters (e.g., Bloom filters) maintained in association with object table partitions (e.g., trees). When an object update impacts a chunk, a corresponding chunk filter is updated, using the chunk's identifier as a chunk filter key by hashing the chunk identifier into chunk filter locations and setting bits at those locations. When garbage collection occurs, a garbage collection candidate chunk's identifier is similarly hashed to read the bit values at those locations in the chunk filters for the partitions. If any bit is zero, the chunk is definitely not in use in a partition; if no chunk filter for any partition indicates the candidate chunk is possibly in use, the chunk is garbage collected without tree scanning. If tree scanning is needed, only the partition(s) with an associated chunk filter that indicates “possibly in use” need to be scanned.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.