# US 2022/0035784 A1 · Representing and managing sampled data in storage systems > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2022/0035784 A1 - Document ID: US20220035784A1 - Status: Published application - Kind: A1 - Application number: 17/302,019 - Filed: 2021-04-21 - Published: 2022-02-03 - Earliest claimed: 2020-07-31 - Assignees: Hewlett Packard Enterprise Development LP - Applicants: Hewlett Packard Enterprise Development LP - Inventors: Sri Satya Sudhanva Kambhammettu; Narayanan Ananthakrishnan Nellayi; Anoop Kumar Raveendran; Subhakar Vipparti - Web page: https://patentgrep.com/patent/US20220035784A1 ## CPC - G06F 16/1748: {De-duplication implemented within the file system, e.g. based on file segments (de-duplication techniques in storage systems for the management of data blocks G06F3/0641)} - G06F 16/2237: {Vectors, bitmaps or matrices} - G06F 16/152: {using file content signatures, e.g. hash values} - G06F 16/21: Design, administration or maintenance of databases - G06F 16/2358: {Change logging, detection, and notification (replication G06F16/27)} - G06F 16/2453: Query optimisation - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Example implementation relates to generating a database for a set of entities associated with sampled data units of a storage system. A first data structure in the database maps, in a bit vector, each entity with a sampled signature of a set of sampled signatures. The set of sampled signatures are associated with the sampled data units. The set of entities associated with the set of sampled signatures are managed using the first data structure. ## Claims ### Claim 1 A method comprising: generating a database for a set of entities associated with sampled data units of a storage system, wherein the set of entities comprises a parent entity, and at least one of snapshots of the parent entity, snapshots of clones, clones of the parent entity, or clones of the snapshots, and wherein the database comprises of one or more data structures; employing a first data structure in the database that maps, in a bit vector of the first data structure, each entity in the set of entities with at least one sampled signature of a set of sampled signatures, wherein a mapping of each entity with the at least one sampled signature is stored as a bit vector file, and wherein the set of sampled signatures are associated with the sampled data units; and managing the set of entities associated with the set of sampled set of signatures using the first data structure. ### Claim 2 (depends on 1) The method of claim 1, wherein managing the set of entities associated with the sampled set of signatures in the storage system using the first data structure comprises: computing a reference count for the at least one sampled signature, wherein the reference count is computed by performing a bit vector summation of bit vectors of the entities mapping the at least one sampled signature. ### Claim 3 (depends on 1) The method of claim 1, wherein managing the set of entities associated with the sampled set of signatures in the storage system using the first data structure comprises: detecting, generation of a new entity in the storage system, wherein the new entity is mapped to at least one sampled signature in a bit vector of the first data structure, wherein the new entity is at least one of a parent entity, a snapshot and a clone and updating the first data structure with mapping of the new entity with at least one sampled signature. ### Claim 4 (depends on 1) The method of claim 1, wherein the database is updated during input/output (I/O) operations on the sampled data units associated with writable entities, wherein the writable entities, wherein the writable entities comprises of at least one of the parent entity and clones of the parent entity. ### Claim 5 (depends on 1) The method of claim 1, further comprising: employing a second data structure in the database to track an intra-entity reference count of a sampled signature when the intra-entity reference count of the sampled signature is greater than one for an entity, wherein the entity is one of a parent entity, a snapshot of the parent entity or of a clone, and a clone of the parent entity or of a snapshot. ### Claim 6 (depends on 5) The method of claim 5, wherein tracking the intra-entity reference count comprises: detecting a new signature in one of sampled data units of multiple sampled data units associated with the entity; determining if the new signature is present in the intra-entity reference count of the entity; and incrementing the intra-entity reference count for the sampled signature when the new signature is present in the intra-entity reference count of the entity. ### Claim 7 (depends on 1) The method of claim 1, wherein the bit vector mapping of each entity with at least one sampled signature indicates presence of a sampled signature in each entity of the set of entities. ### Claim 8 (depends on 1) The method of claim 1, wherein each entity of the set of entities present in the database is addressable using a plurality of pointers, wherein each pointer of the plurality of pointers is a link to access the bit vector file stored in the database for the respective entity in the set of entities. ### Claim 9 (depends on 1) The method of claim 1, wherein managing the set of entities associated with the sampled set of signatures of the storage system using the database further comprises: receiving a query to determine a unique space occupied by a subset of entities of the set of entities; performing a bit vector summation of the bit vectors associated with the subset of entities in the first data structure to compute a first reference count for each of the at least one sampled signature associated with the subset of entities; comparing, for each of the at least one sampled signature associated with each entity in the subset of entities, the first reference count of the at least one sampled signature with a second reference count of a corresponding at least one sampled signature from a third data structure, wherein the third data structure stores the second reference count of each sampled signature of the set of sampled signatures in the set of entities; identifying a subset of sampled signatures for which the first reference count computed from the first data structure matches the second reference count from the third data structure; and determining unique sampled data units occupied by the subset of entities based on the identified subset of sampled signatures. ### Claim 10 (depends on 8) The method of claim 8, wherein the second reference count of the at least one sampled signature in the set of sampled signatures is adjusted based on the I/O operations on the set of entities associated with the sampled data units in the storage system. ### Claim 11 (depends on 1) The method of claim 1, wherein bit vectors in the first data structure are stored in compressed format. ### Claim 12 (depends on 1) The method of claim 1, wherein managing of the set of entities associated with the sampled set of signatures in the storage system using the database further comprises: receiving a query to determine a rate of change for a subset of entities of the set of entities; comparing, for the subset of entities, the bit vector files in the first data structure at a first time with the bit vector files at a second time; identifying changes in the bit vector files of the subset of entities in the first data structure between the first time and the second time; and determining the rate of change in subset of entities based on the identified changes in the bit vector files of the subset of entities. ### Claim 13 A system comprising: a storage device to store data; a processor; and a machine-readable medium storing instructions that, when executed by the processor, cause the processor to: generate a database for a set of entities associated with sampled data units of a storage system, wherein the set of entities comprises of a parent entity, and at least one of snapshots of the parent entity, snapshots of clones, clones of the snapshots, or clones of the parent entity, and wherein the database comprises of one or more data structures; employ a first data structure in the database that maps, in a bit vector of the first data structure, each entity in the set of entities with at least one sampled signature of a set of sampled signatures, wherein the mapping of each entity with the at least one sampled signature is stored as a bit vector, and wherein the set of sampled signatures are associated with the sampled data units; and compute a reference count for the at least one sampled signature, wherein the reference count is computed by performing a bit vector summation of the bit vectors of the entities mapping the at least one sampled signature in the first data structure. ### Claim 14 (depends on 13) The apparatus of claim 13, wherein the bit vector mapping of each entity with at least one sampled signature indicates presence of a sampled signature in each entity of the set of entities. ### Claim 15 (depends on 13) The apparatus of claim 13, wherein each entity of the set of entities present in the database is addressable using a plurality of pointers, wherein each pointer of the plurality of pointers is a link to access the bit vector file stored in the database for the respective entity in the set of entities. ### Claim 16 (depends on 13) The apparatus of claim 13, wherein the instructions, when executed, cause the processor to: receive a request to determine a unique space occupied by a subset of entities of the set of entities; perform a bit vector summation of the bit vectors associated with the subset of entities in the first data structure to compute a first reference count for each of the at least one sampled signature associated with the subset of entities; compare, for each of the at least one sampled signature associated with each entity in the subset of entities, the first reference count of the at least one sampled signature with a second reference count of a corresponding at least one sampled signature from a third data structure, wherein the third data structure stores the second reference count of each sampled signature of the set of sampled signatures in the set of entities; identify a subset of sampled signatures for which the first reference count computed from the first data structure matches the second reference count from the third data structure; and determine the unique space occupied by the subset of entities based on the identified subset of sampled signatures. ### Claim 17 (depends on 13) The apparatus of claim 13, wherein the instructions, when executed, cause the processor to: detect, generation of a new entity in the storage system, wherein the entity is mapped to at least one sampled signature in a bit vector of the first data structure, and wherein the new entity is at least one of a parent entity, a snapshot and a clone of the parent entity; and update the first data structure with mapping of the new entity with at least one sampled signature. ### Claim 18 (depends on 13) The apparatus of claim 13, wherein the instructions, when executed, cause the processor to: receive a request to determine a rate of change for a subset of entities of the set of entities; compare, for the subset of entities, the stored bit vector files in the first data structure at a first time with the bit vector files at a second time, and wherein the subset of entities comprises at least one of a parent entity, a snapshot of the entity and a clone of the entity; identify changes in the bit vector files of the subset of entities in the first data structure between the first time and the second time; and determine the rate of change in subset of entities based on the identified changes in the bit vector files of the subset of entities. ### Claim 19 A non-transitory machine-readable storage medium comprising instructions, the instructions executable by a processor to: generate a database for a set of entities associated with sampled data units of a storage system, wherein the set of entities comprises of a parent entity, and at least one of snapshots of the parent entity, snapshots of clones, and clones of the snapshots, or clones of the parent entity, and wherein the database comprises of one or more data structures; employ a first data structure in the database that maps, in a bit vector of the first data structure, each entity in the set of entities with at least one sampled signature of a set of sampled signatures, wherein the mapping of each entity with the at least one sampled signature is stored as a bit vector, and wherein the set of sampled signatures are associated with the sampled data units; and compute a reference count for the at least one sampled signature, wherein the reference count is computed by performing a bit vector summation of the bit vectors of entities mapping the at least one sampled signature. ### Claim 20 The non-transitory computer machine-readable storage medium, wherein the database is updated during I/O operations on the sampled data units associated with at least one of the parent entity and clones.