Object storage device with probabilistic data structure
First Claim
1. An object storage device, comprising:
- control circuitry;
a storage media operative to store an object store; and
a memory coupled to the control circuitry operative to store a first probabilistic data structure having data indicating the presence of data in the object store, and further operative to store a second probabilistic data structure having data indicating the presence of data in the same object store, wherein the first probabilistic data structure is at least one of smaller than the second probabilistic data structure and includes fewer values in a lookup set than the second probabilistic data structure such that use of the second probabilistic data structure results in less false positives than use of the first probabilistic data structure, and wherein the first probabilistic data structure is at least one of a Bloom filter, a quotient filter, and an approximate membership query data structure; and
wherein the control circuitry is configured to;
receive an interrogation from a computing device for an object;
utilize the first probabilistic data structure to determine whether the object is possibly stored in the object store or definitely not stored in the object store on the storage media by generating a hash value from at least one of the object, a name of the object, and a key associated with the object and comparing the hash value to values of the first probabilistic data structure;
in response to the determination that the object is possibly stored in the object store when utilizing the first probabilistic data structure, utilize the second probabilistic data structure to further determine whether the object is possibly stored in the object store or definitely not stored in the object store on the storage media;
in response to a determination that the object is definitely not stored in the object store when utilizing either the first probabilistic data structure or the second probabilistic data structure, respond to the interrogation that the object is not stored in the object store; and
in response to a determination that the object is possibly stored in the object store when utilizing the second probabilistic data structure, access the object store to determine if the object is definitely stored in the object store or definitely not stored in the object store.
6 Assignments
0 Petitions
Accused Products
Abstract
Systems and methods for utilizing probabilistic data structures to handle interrogations regarding whether or not objects might be stored in an object store of an object storage device are disclosed. More particularly, a controller of an object storage device includes control circuitry and a memory operative to store a probabilistic data structure. The probabilistic data structure has data related to the presence of data in an object store of the object storage device. The control circuitry is configured to receive an interrogation from a computing device for an object; utilize the probabilistic data structure to determine that the object is possibly stored in the object store or definitely not stored in the object store; and in response to a determination that the object is definitely not stored in the object store, respond to the interrogation that the object is not stored in the object store.
-
Citations
12 Claims
-
1. An object storage device, comprising:
-
control circuitry; a storage media operative to store an object store; and a memory coupled to the control circuitry operative to store a first probabilistic data structure having data indicating the presence of data in the object store, and further operative to store a second probabilistic data structure having data indicating the presence of data in the same object store, wherein the first probabilistic data structure is at least one of smaller than the second probabilistic data structure and includes fewer values in a lookup set than the second probabilistic data structure such that use of the second probabilistic data structure results in less false positives than use of the first probabilistic data structure, and wherein the first probabilistic data structure is at least one of a Bloom filter, a quotient filter, and an approximate membership query data structure; and wherein the control circuitry is configured to; receive an interrogation from a computing device for an object; utilize the first probabilistic data structure to determine whether the object is possibly stored in the object store or definitely not stored in the object store on the storage media by generating a hash value from at least one of the object, a name of the object, and a key associated with the object and comparing the hash value to values of the first probabilistic data structure; in response to the determination that the object is possibly stored in the object store when utilizing the first probabilistic data structure, utilize the second probabilistic data structure to further determine whether the object is possibly stored in the object store or definitely not stored in the object store on the storage media; in response to a determination that the object is definitely not stored in the object store when utilizing either the first probabilistic data structure or the second probabilistic data structure, respond to the interrogation that the object is not stored in the object store; and in response to a determination that the object is possibly stored in the object store when utilizing the second probabilistic data structure, access the object store to determine if the object is definitely stored in the object store or definitely not stored in the object store. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. A controller of an object storage device, comprising:
-
control circuitry; and a memory coupled to the control circuitry operative to store a first probabilistic data structure having data indicating the presence of data in an object store of the object storage device, and further operative to store a second probabilistic data structure having data indicating the presence of data in the same object store of the object storage device, wherein the first probabilistic data structure is at least one of smaller than the second probabilistic data structure and includes fewer values in a lookup set than the second probabilistic data structure such that use of the second probabilistic data structure results in less false positives than use of the first probabilistic data structure, and wherein the first probabilistic data structure is at least one of a Bloom filter, a quotient filter, and an approximate membership query data structure; and wherein the control circuitry is configured to; receive an interrogation from a computing device for an object; utilize the first probabilistic data structure to determine that the object is possibly stored in the object store or definitely not stored in the object store by generating a hash value from at least one of the object, a name of the object, and a key associated with the object and comparing the hash value to values of the first probabilistic data structure; in response to the determination that the object is possibly stored in the object store when utilizing the first probabilistic data structure, utilize the second probabilistic data structure to further determine whether the object is possibly stored in the object store or definitely not stored in the object store; in response to a determination that the object is definitely not stored in the object store when utilizing either the first probabilistic data structure or the second probabilistic data structure, respond to the interrogation that the object is not stored in the object store; and in response to a determination that the object is possibly stored in the object store when utilizing the second probabilistic data structure, access the object store to determine if the object is definitely stored in the object store or definitely not stored in the object store.
-
-
10. A method for operating a controller of an object storage device, the method comprising:
-
receiving an interrogation for an object from a computing device utilizing a controller of an object storage device; utilizing a first probabilistic data structure stored in a memory of the object storage device, the first probabilistic data structure having data indicating the presence of data in an object store of the storage device, to determine that the object is possibly stored in the object store or definitely not stored in the object store by generating a hash value from at least one of the object, a name of the object, and a key associated with the object and comparing the hash value to values of the first probabilistic data structure, wherein the first probabilistic data structure is at least one of a Bloom filter, a quotient filter, and an approximate membership query data structure; in response to the determination that the object is possibly stored in the object store when utilizing the first probabilistic data structure, utilizing a second probabilistic data structure to further determine whether the object is possibly stored in the same object store or definitely not stored in the object store, wherein the first probabilistic data structure is at least one of smaller than the second probabilistic data structure and includes fewer values in a lookup set than the second probabilistic data structure such that use of the second probabilistic data structure results in less false positives than use of the first probabilistic data structure; in response to a determination that the object is definitely not stored in the object store when utilizing the first probabilistic data structure or the second probabilistic data structure, responding to the interrogation utilizing the controller that the object is not stored in the object store; and in response to a determination that the object is possibly stored in the object store when utilizing the second probabilistic data structure, accessing the object store to determine if the object is definitely stored in the object store or definitely not stored in the object store. - View Dependent Claims (11, 12)
-
Specification