Bloom filter partitioning

A system, comprising:

• a processor configured to:
• receive a representation of an item;
• use the representation to determine a particular partition with which the item is associated, wherein the particular partition with which the item is associated is one of a plurality of partitions corresponding to a volume that comprises the item, and each of the plurality of partitions have a corresponding partition-specific Bloom filter;
• determine whether the item is an element of a set with which the particular partition is associated, wherein the set comprises one or more objects stored in a distributed file system, and wherein the determining of whether the item is an element in the set comprises:
• checking a partition-specific Bloom filter corresponding to the particular partition to determine if the item is an element of the set;
• in response to determining that the partition-specific Bloom filter indicates that the item is not an element of the set, determining that the item is not an element of the set;
• and
• in response to determining that the partition-specific Bloom filter indicates that the item is an element of the set,
• querying a table associated with the set for the representation of the item, and
• determining that the item is an element of the set in the event that the querying of the table associated with the set indicates that the set includes the item;
• dynamically determine to partition or resize the partition-specific Bloom filter based at least in part on a computed probability of the partition-specific Bloom filter rendering a false positive, the computed probability being based at least in part on one or more of a filter size and a number of elements in the particular partition corresponding to the partition-specific Bloom filter;
• in response to determining to partition or resize the partition specific Bloom filter, partition or resize the partition-specific Bloom filter independent of one or more other partition-specific Bloom filters corresponding to the one or more other partitions of the plurality of partitions;
• and
• a storage device coupled to the processor and configured to store the partition-specific Bloom filter.

A computer program product embodied in a non-transitory computer readable storage medium and comprising computer instructions for:

• receiving a representation of an item;
• using the representation to determine a particular partition with which the item is associated, wherein the particular partition with which the item is associated is one of a plurality of partitions corresponding to a volume that comprises the item, and each of the plurality of partitions have a corresponding partition-specific Bloom filter;
• determining, by one or more processors, whether the item is an element of a set with which the particular partition is associated, wherein the set comprises one or more objects stored in a distributed file system, and wherein the determining of whether the item is an element in the set comprises:
• checking a partition-specific Bloom filter corresponding to the particular partition to determine if the item is an element of the set;
• in response to determining that the partition-specific Bloom filter indicates that the item is not an element of the set, determining that the item is not an element of the set;
• and
• in response to determining that the partition-specific Bloom filter indicates that the item is an element of the set,
• querying a table associated with the set for the representation of the item, and
• determining that the item is an element of the set in the event that the querying of the table associated with the set indicates that the set includes the item;
• dynamically determining to partition or resize the partition-specific Bloom filter based at least in part on a computed probability of the partition-specific Bloom filter rendering a false positive, the computed probability being based at least in part on one or more of a filter size and a number of elements in the particular partition corresponding to the partition-specific Bloom filter;
• and
• in response to determining to partition or resize the partition specific Bloom filter, partitioning or resizing the partition-specific Bloom filter independent of one or more other partition-specific Bloom filters corresponding to one or more other partitions of the plurality of partitions.