Dispersed bloom filter for determining presence of an object

• US 10,296,263 B2
• Filed: 02/22/2018
• Issued: 05/21/2019
• Est. Priority Date: 04/30/2014
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Dhuse, Greg R., Resch, Jason K.
• Primary Examiner(s): Abad, Farley
• Assistant Examiner(s): Yu, Henry W
• Application Number:
  US15/902,083
• Publication Number:
  US 20180181314A1
• Time in Patent Office: 453 Days
• Field of Search: 710 15, 710 62, 710 74
• CPC Class Codes: G06F 11/1004 to protect a block of data words, e.g. CRC or checksum G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1088 Reconstruction on already foreseen single or plurality of spare disks
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 2221/2107 File encryption
• CPC Class Codes: G06F 3/0607 by facilitating the process of upgrading existing storage systems, e.g. for improving compatibility between host and storage device
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0637 Permissions
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H04L 41/082 the condition being updates or upgrades of network functionality
• CPC Class Codes: H04L 41/5096 wherein the managed service relates to distributed or central networked applications

Abstract

A computing device includes an interface configured to interface and communicate with a dispersed storage network (DSN), a memory that stores operational instructions, and processing circuitry operably coupled to the interface and to the memory. The processing circuitry is configured to execute the operational instructions to perform various operations and functions. The computing device receives a store data object request and facilitates distributed storage of the data object in storage units (SUs). the computing device applies unique deterministic functions to the object name to generate deterministic values. For a deterministic value, the computing device identifies a corresponding SU based on the deterministic value and the bucket mapping scheme. The computing device transmits an update bucket request to the corresponding SU to be used by the corresponding SU to update a state value of a bucket that is locally stored by the corresponding SU to indicate an active state.

Claims

1. A computing device comprising:

an interface configured to interface and communicate with a dispersed or distributed storage network (DSN);

memory that stores operational instructions; and

processing circuitry operably coupled to the interface and to the memory, wherein the processing circuitry is configured to execute the operational instructions to;

receive a store data object request that includes a data object and an object name of the data object;

facilitate distributed storage of a set of encoded data slices (EDSs) that are based on the data object in a plurality of storage units (SUs) of the DSN based on dispersed error encoding of the data object in accordance with dispersed error encoding parameters;

apply a plurality of unique deterministic functions to the object name to generate a plurality of deterministic values, wherein each of the plurality of deterministic values ranges from 1 to a number of buckets, wherein each SU of the plurality of SUs is associated with a corresponding portion of deterministic range values based on a bucket mapping scheme;

for a deterministic value of the plurality of deterministic values, identify a corresponding SU of the plurality of SUs based on the deterministic value and the bucket mapping scheme; and

transmit an update bucket request to the corresponding SU to be used by the corresponding SU to update a state value of a bucket that is locally stored by the corresponding SU to indicate an active state based on receiving the update bucket request that corresponds to the deterministic value that is associated with the bucket that is locally stored by the corresponding SU, wherein the update bucket request includes the deterministic value.

2. The computing device of claim 1, wherein:

n, K, and M are respective positive integers;

the plurality of SUs includes n SUs;

the plurality of unique deterministic functions includes K unique deterministic functions;

the plurality of deterministic values includes K deterministic values;

the number of buckets includes M buckets; and

the each SU of the plurality of SUs is associated with M/n buckets based on the bucket mapping scheme including an even distribution.

3. The computing device of claim 1, wherein the processing circuitry is further configured to execute the operational instructions to:

receive a plurality of bucket state responses from at least some of the plurality of SUs;

determine that the set of EDSs that are based on the data object are stored in the plurality of SUs based on a number of the plurality of bucket state responses indicating the active state being greater than or equal to a first threshold level; and

determine that the set of EDSs that are based on the data object are not stored in the plurality of SUs based on the number of the plurality of bucket state responses indicating an inactive state being greater than or equal to a second threshold level that is lower than the first threshold level.

4. The computing device of claim 1, wherein the processing circuitry is further configured to execute the operational instructions to:

dispersed error encode the data object to generate the set of EDSs, wherein the data object is segmented into a plurality of data segments, wherein a data segment of the plurality of data segments is dispersed error encoded in accordance with dispersed error encoding parameters to produce the set of EDSs; and

generate a set of write slice requests that includes the set of EDSs and a set of slice names; and

transmit the set of write slice requests to the plurality of SUs to facilitate the distributed storage of the set of EDSs therein.

5. The computing device of claim 4, wherein:

a decode threshold number of EDSs are needed to recover the data segment;

a read threshold number of EDSs provides for reconstruction of the data segment;

a write threshold number of EDSs provides for a successful transfer of the set of EDSs from a first at least one location in the DSN to a second at least one location in the DSN;

the set of EDSs is of pillar width and includes a pillar number of EDSs;

each of the decode threshold number, the read threshold number, and the write threshold number is less than the pillar number; and

the write threshold number is greater than or equal to the read threshold number that is greater than or equal to the decode threshold number.

6. The computing device of claim 1, wherein the computing device is located at a first premises that is remotely located from a second premises of at least one SU of the plurality of SUs within the DSN.

7. The computing device of claim 1 further comprising:

a SU of the plurality of SUs within the DSN, a wireless smart phone, a laptop, a tablet, a personal computers (PC), a work station, or a video game device.

8. The computing device of claim 1, wherein the DSN includes at least one of a wireless communication system, a wire lined communication system, a non-public intranet system, a public internet system, a local area network (LAN), or a wide area network (WAN).

9. A computing device comprising:

an interface configured to interface and communicate with a dispersed or distributed storage network (DSN);

memory that stores operational instructions; and

processing circuitry operably coupled to the interface and to the memory, wherein the processing circuitry is configured to execute the operational instructions to;

receive a store data object request that includes a data object and an object name of the data object;

dispersed error encode the data object to generate a set of encoded data slices (EDSs), wherein the data object is segmented into a plurality of data segments, wherein a data segment of the plurality of data segments is dispersed error encoded in accordance with dispersed error encoding parameters to produce the set of EDSs;

facilitate distributed storage of the set of EDSs that are based on the data object in a plurality of storage units (SUs) of the DSN based on dispersed error encoding of the data object in accordance with dispersed error encoding parameters;

apply a plurality of unique deterministic functions to the object name to generate a plurality of deterministic values, wherein each of the plurality of deterministic values ranges from 1 to a number of buckets, wherein each SU of the plurality of SUs is associated with a corresponding portion of deterministic range values based on a bucket mapping scheme;

for a deterministic value of the plurality of deterministic values, identify a corresponding SU of the plurality of SUs based on the deterministic value and the bucket mapping scheme;

transmit an update bucket request to the corresponding SU to be used by the corresponding SU to update a state value of a bucket that is locally stored by the corresponding SU to indicate an active state based on receiving the update bucket request that corresponds to the deterministic value that is associated with the bucket that is locally stored by the corresponding SU, wherein the update bucket request includes the deterministic value;

receive a plurality of bucket state responses from at least some of the plurality of SUs;

determine that the set of EDSs that are based on the data object are stored in the plurality of SUs based on a number of the plurality of bucket state responses indicating the active state being greater than or equal to a first threshold level; and

determine that the set of EDSs that are based on the data object are not stored in the plurality of SUs based on the number of the plurality of bucket state responses indicating an inactive state being greater than or equal to a second threshold level that is lower than the first threshold level.

10. The computing device of claim 9, wherein:

n, K, and M are respective positive integers;

the plurality of SUs includes n SUs;

the plurality of unique deterministic functions includes K unique deterministic functions;

the plurality of deterministic values includes K deterministic values;

the number of buckets includes M buckets; and

the each SU of the plurality of SUs is associated with M/n buckets based on the bucket mapping scheme including an even distribution.

11. The computing device of claim 9, wherein:

a decode threshold number of EDSs are needed to recover the data segment;

a read threshold number of EDSs provides for reconstruction of the data segment;

a write threshold number of EDSs provides for a successful transfer of the set of EDSs from a first at least one location in the DSN to a second at least one location in the DSN;

the set of EDSs is of pillar width and includes a pillar number of EDSs;

each of the decode threshold number, the read threshold number, and the write threshold number is less than the pillar number; and

the write threshold number is greater than or equal to the read threshold number that is greater than or equal to the decode threshold number.

12. The computing device of claim 9 further comprising:

a SU of the plurality of SUs within the DSN, a wireless smart phone, a laptop, a tablet, a personal computers (PC), a work station, or a video game device.

13. The computing device of claim 9, wherein the DSN includes at least one of a wireless communication system, a wire lined communication system, a non-public intranet system, a public internet system, a local area network (LAN), or a wide area network (WAN).

14. A method for execution by a computing device, the method comprising:

receiving, via an interface of the computing device configured to interface and communicate with a dispersed or distributed storage network (DSN), a store data object request that includes a data object and an object name of the data object;

facilitating distributed storage of a set of encoded data slices (EDSs) that are based on the data object in a plurality of storage units (SUs) of the DSN based on dispersed error encoding of the data object in accordance with dispersed error encoding parameters;

applying a plurality of unique deterministic functions to the object name to generate a plurality of deterministic values, wherein each of the plurality of deterministic values ranges from 1 to a number of buckets, wherein each SU of the plurality of SUs is associated with a corresponding portion of deterministic range values based on a bucket mapping scheme;

for a deterministic value of the plurality of deterministic values, identifying a corresponding SU of the plurality of SUs based on the deterministic value and the bucket mapping scheme; and

transmitting, via the interface, an update bucket request to the corresponding SU to be used by the corresponding SU to update a state value of a bucket that is locally stored by the corresponding SU to indicate an active state based on receiving the update bucket request that corresponds to the deterministic value that is associated with the bucket that is locally stored by the corresponding SU, wherein the update bucket request includes the deterministic value.

15. The method of claim 14, wherein:

n, K, and M are respective positive integers;

the plurality of SUs includes n SUs;

the plurality of unique deterministic functions includes K unique deterministic functions;

the plurality of deterministic values includes K deterministic values;

the number of buckets includes M buckets; and

the each SU of the plurality of SUs is associated with M/n buckets based on the bucket mapping scheme including an even distribution.

16. The method of claim 14 further comprising:

receiving, via the interface, a plurality of bucket state responses from at least some of the plurality of SUs;

determining that the set of EDSs that are based on the data object are stored in the plurality of SUs based on a number of the plurality of bucket state responses indicating the active state being greater than or equal to a first threshold level; and

determining that the set of EDSs that are based on the data object are not stored in the plurality of SUs based on the number of the plurality of bucket state responses indicating an inactive state being greater than or equal to a second threshold level that is lower than the first threshold level.

17. The method of claim 14 further comprising:

dispersed error encoding the data object to generate the set of EDSs, wherein the data object is segmented into a plurality of data segments, wherein a data segment of the plurality of data segments is dispersed error encoded in accordance with dispersed error encoding parameters to produce the set of EDSs; and

generating a set of write slice requests that includes the set of EDSs and a set of slice names; and

transmitting, via the interface, the set of write slice requests to the plurality of SUs to facilitate the distributed storage of the set of EDSs therein.

18. The method of claim 17, wherein:

a decode threshold number of EDSs are needed to recover the data segment;

a read threshold number of EDSs provides for reconstruction of the data segment;

a write threshold number of EDSs provides for a successful transfer of the set of EDSs from a first at least one location in the DSN to a second at least one location in the DSN;

the set of EDSs is of pillar width and includes a pillar number of EDSs;

each of the decode threshold number, the read threshold number, and the write threshold number is less than the pillar number; and

the write threshold number is greater than or equal to the read threshold number that is greater than or equal to the decode threshold number.

19. The method of claim 14, wherein the computing device includes a SU of the plurality of SUs within the DSN, a wireless smart phone, a laptop, a tablet, a personal computers (PC), a work station, or a video game device.

20. The method of claim 14, wherein the DSN includes at least one of a wireless communication system, a wire lined communication system, a non-public intranet system, a public internet system, a local area network (LAN), or a wide area network (WAN).