System and method for scalable and space efficient hardening of a fixed sized hash table over an unreliable tier

Patent metadata

Field	Value
Publication number	US-11243930-B2
Application number	US-201916527468-A
Country	US
Kind code	B2
Filing date	Jul 31, 2019
Priority date	Jul 31, 2019
Publication date	Feb 8, 2022
Grant date	Feb 8, 2022

Abstract

A method, computer program product, and computer system for storing data in a bucket of a plurality of buckets. A spare bucket may be reserved in the plurality of buckets. A copy of the data may be stored in the spare bucket. A pointer to the data in the bucket and a pointer to the copy of the data in the spare bucket may be updated based upon, at least in part, storing the data in the bucket and storing the copy of the data in the spare bucket.

First claim

What is claimed is:

1. A computer-implemented method comprising:
storing data in a bucket of a plurality of buckets, wherein the data in the bucket is stored in a consecutive-cyclic manner, wherein the bucket is assigned to a head index indicative of a location of the bucket;
reserving a spare bucket in the plurality of buckets, wherein the spare bucket is a next slot from the bucket;
storing a copy of the data in the spare bucket, wherein the spare bucket is assigned to a spare index indicative of a location of the spare bucket; and
updating a pointer to the data in the bucket and a pointer to the copy of the data in the spare bucket based upon, at least in part, storing the data in the bucket and storing the copy of the data in the spare bucket.

2. The computer-implemented method of claim 1 wherein updating the pointer to the copy of the data in the spare bucket includes pointing to the bucket storing the data.

3. The computer-implemented method of claim 1 further comprising updating the plurality of buckets in the consecutive-cyclic manner.

4. The computer-implemented method of claim 1 further comprising dividing the plurality of buckets between a fixed number of domains.

5. The computer-implemented method of claim 4 wherein each domain of the fixed number of domains is an instance of an independent logical tier.

6. The computer-implemented method of claim 4 wherein each domain of the fixed number of domains includes its own header and spare metadata member.

7. The computer-implemented method of claim 1 further comprising reading the bucket of the plurality of buckets, wherein reading the bucket of the plurality of buckets includes:
skipping one or more slots from a respective slot stated in the head index, and
skipping one or more additional slots when a respective slot stated in the spare index is reached.

8. A computer program product residing on a non-transitory computer readable storage medium having a plurality of instructions stored thereon which, when executed across one or more processors, causes at least a portion of the one or more processors to perform operations comprising:
storing data in a bucket of a plurality of buckets, wherein the data in the bucket is stored in a consecutive-cyclic manner, wherein the bucket is assigned to a head index indicative of a location of the bucket;
reserving a spare bucket in the plurality of buckets, wherein the spare bucket is a next slot from the bucket;
storing a copy of the data in the spare bucket, wherein the spare bucket is assigned to a spare index indicative of a location of the spare bucket; and
updating a pointer to the data in the bucket and a pointer to the copy of the data in the spare bucket based upon, at least in part, storing the data in the bucket and storing the copy of the data in the spare bucket.

9. The computer program product of claim 8 wherein updating the pointer to the copy of the data in the spare bucket includes pointing to the bucket storing the data.

10. The computer program product of claim 8 wherein the operations further comprise updating the plurality of buckets in the consecutive-cyclic manner.

11. The computer program product of claim 8 wherein the operations further comprise dividing the plurality of buckets between a fixed number of domains.

12. The computer program product of claim 11 wherein each domain of the fixed number of domains is an instance of an independent logical tier.

13. The computer program product of claim 11 wherein each domain of the fixed number of domains includes its own header and spare metadata member.

14. A computing system including:
one or more memories; and
one or more processors configured to perform operations comprising:
storing data in a bucket of a plurality of buckets, wherein the data in the bucket is stored in a consecutive-cyclic manner, wherein the bucket is assigned to a head index indicative of a location of the bucket;
reserving a spare bucket in the plurality of buckets;
storing a copy of the data in the spare bucket, wherein the spare bucket is assigned to a spare index indicative of a location of the spare bucket; and
updating a pointer to the data in the bucket and a pointer to the copy of the data in the spare bucket based upon, at least in part, storing the data in the bucket and storing the copy of the data in the spare bucket.

15. The computing system of claim 14 wherein updating the pointer to the copy of the data in the spare bucket includes pointing to the bucket storing the data.

16. The computing system of claim 14 wherein the operations further comprise updating the plurality of buckets in the consecutive-cyclic manner.

17. The computing system of claim 14 wherein the operations further comprise dividing the plurality of buckets between a fixed number of domains.

18. The computing system of claim 17 wherein each domain of the fixed number of domains is an instance of an independent logical tier, and wherein each domain of the fixed number of domains includes its own header and spare metadata member.

Assignees

• Emc Ip Holding Co Llc

Inventors

• Harel Bar
• Shabi Uri
• Rahamim Maor

Classifications

• G06F16/2255 Primary

  Hash tables · CPC title

• G06F16/2379

  Updates performed during online database operations; commit processing · CPC title