Object storage device with probabilistic data structure

• US 10,282,371 B1
• Filed: 12/02/2014
• Issued: 05/07/2019
• Est. Priority Date: 12/02/2014
• Status: Active Grant

• Current Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Gaither, Blaine
• Primary Examiner(s): Corrielus, Jean M
• Application Number:
  US14/557,601
• Time in Patent Office: 1,617 Days
• Field of Search: 707609, 707602, 707756
• CPC Class Codes: 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
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2468 Fuzzy queries
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/289 Object oriented databases

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.

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.

2. The object storage device of claim 1, wherein the control circuitry is further configured to respond to the interrogation that the object is not stored in the object store, in the event the access of the object store determines that the object is definitely not stored in the object store.

3. The object storage device of claim 1, wherein the control circuitry is further configured to allocate space in the object store for the object, in the event it is determined that that object is definitely not stored in the object store when utilizing the first probabilistic data structure or the second probabilistic data structure and the interrogation is associated with a write request.

4. The object storage device of claim 1, wherein the control circuitry is further configured to, in the event the object is determined to be definitely stored in the object store and the interrogation is associated with a read request, perform at least one of:

copying the object to memory; and

providing the object to the computing device.

5. The object storage device of claim 1, wherein the control circuitry is further configured to allocate space in the object store for the object, in the event the access of the object store determines that the object is definitely not stored in the object store and the interrogation is associated with a write request.

6. The object storage device of claim 1, wherein the control circuitry is further configured to replace a probabilistic data structure, wherein the replacing comprises:

creating a new probabilistic data structure by analyzing objects stored in the object store;

modifying the probabilistic data structure and the new probabilistic data structure to account for objects allocated in the object store while the new probabilistic data structure is being created; and

utilizing the new probabilistic data structure instead of the probabilistic data structure once creation of the new probabilistic data structure is complete.

7. The object storage device of claim 6, wherein the control circuitry is further configured to determine to replace the probabilistic data structure upon at least one of:

occurrence of more than a threshold number of false positives;

expiration of a period of time; and

receipt of more than a threshold number of delete requests.

8. The object storage device of claim 1, wherein the storage media is further operative to store a second object store and the memory is further operative to store a third probabilistic data structure having data indicating the presence of data in the second object store, and wherein the control circuitry is further configured to utilize the third probabilistic data structure to determine that the object is possibly stored in the second object store or definitely not stored in the second object store.

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.

11. The method of claim 10, further comprising responding to the interrogation that the object is stored in the object store in response to the accessing of the object store determining the object is definitely stored in the object store.

12. The method of claim 10, further comprising replacing a probabilistic data structure, wherein the replacing comprises:

creating a new probabilistic data structure by analyzing objects stored in the object store;

modifying the probabilistic data structure and the new probabilistic data structure to account for objects allocated in the object store while the new probabilistic data structure is being created; and

utilizing the new probabilistic data structure instead of the probabilistic data structure once creation of the new probabilistic data structure is complete.