Managing hash tables in a storage system

Patent metadata

Field	Value
Publication number	US-11438415-B2
Application number	US-201916669000-A
Country	US
Kind code	B2
Filing date	Oct 30, 2019
Priority date	Oct 30, 2019
Publication date	Sep 6, 2022
Grant date	Sep 6, 2022

Abstract

An aspect includes splitting a table of buckets into a fixed number of domains. Each of the domains includes a corresponding subset of the buckets. An aspect also includes providing a spare bucket for each of the subsets of the buckets and providing a metadata structure for each of the domains. The metadata structure includes a head pointer that points to a first bucket of a corresponding subset of the buckets and a spare_bucket pointer that points to the spare bucket of the subset of the buckets. An aspect further includes providing a split-spare bucket pointer that interleaves, during updates to data, among the subset of buckets in the domain. Data subject to the updates is stored in the spare bucket for a corresponding one of the domains. An aspect also includes updating the head pointer and the spare_bucket pointer for corresponding domains in response to updating the data.

First claim

What is claimed is:

1. A method comprising:
providing a table of buckets having a fixed number of domains, each of the domains including a corresponding subset of the buckets;
providing a spare bucket for each of the subsets of the buckets;
providing a metadata structure for each of the fixed number of domains, the metadata structure including a head pointer that points to a first bucket of a corresponding subset of the buckets and a spare_bucket pointer that points to the spare bucket of the corresponding subset of the buckets;
providing a split-spare bucket pointer that points to a split-spare bucket, the split-spare bucket being configured to receive sub-buckets during a split of the table, the split-spare bucket being used only when a split of the table is ongoing, such that the split-spare bucket is not used when a split of the table is not ongoing, and
updating the head pointer and the spare_bucket pointer for corresponding domains in response to updating the buckets.

2. The method of claim 1 , wherein a subset of the buckets corresponding to a first domain of the fixed number of domains is a first subset and another subset of the buckets corresponding to a second domain of the fixed number of domains is a second subset, the method further comprising:
splitting the first subset into a first subgroup of buckets and a second subgroup of buckets; and
splitting the second subset of the buckets into a third subgroup of buckets and a fourth subgroup of bucket.

3. The method of claim 2 , further comprising:
mapping buckets in the first subgroup and the second subgroup to the first subset; and
mapping buckets in the third subgroup and the fourth subgroup to the second subset;
wherein each mapping is implemented via a corresponding combined domain identifier and a corresponding bucket identifier.

4. The method of claim 1 , wherein the head pointer is atomically updated to point to the spare bucket in response to detecting that contents of the first bucket have been copied into the spare bucket.

5. The method of claim 1 , wherein the split-spare bucket is configured to occupy a last slot in the table before any given split of the tbale is initiated and the split-spare bucket is configured to occupy other than the last slot in the table while the given split is ongoing.

6. The method of claim 1 , wherein the updating includes updating the buckets in a consecutive-cyclic manner.

7. The method of claim 1 , wherein the metadata structure is stored in non-volatile memory.

8. A system comprising:
a memory having computer-executable instructions; and
a processor for executing the computer-executable instructions, the computer-executable instructions when executed by the processor cause the processor to perform operations, comprising
providing a table of buckets having a fixed number of domains, each of the domains including a corresponding subset of the buckets;
providing a spare bucket for each of the subsets of the buckets;
providing a metadata structure for each of the fixed number of domains, the metadata structure including a head pointer that points to a first bucket of a corresponding subset of the buckets and a spare_bucket pointer that points to the spare bucket of the corresponding subset of the buckets;
providing a split-spare bucket pointer that points to a split-spare bucket, the split-spare bucket being configured to receive sub-buckets during a split of the table, the split-spare bucket being used only when a split of the table is ongoing, such that the split-spare bucket is not used when a split of the table is not ongoiing; and
updating the head pointer and the spare bucket pointer for corresponding domains in response to updating the buckets.

9. The system of claim 8 , wherein a subset of the buckets corresponding to a first domain of the fixed number of domains is a first subset and another subset of the buckets corresponding to a second domain of the fixed number of domains is a second subset, the operations further comprising:
splitting the first subset into a first subgroup of buckets and a second subgroup of buckets; and
splitting the second subset of the buckets into a third subgroup of buckets and a fourth subgroup of bucket.

10. The system of claim 9 , wherein the operations further comprise:
mapping buckets in the first subgroup and the second subgroup to the first subset; and
mapping buckets in the third subgroup and the fourth subgroup to the second subset;
wherein each mapping is implemented via a corresponding combined domain identifier and a corresponding bucket identifier.

11. The system of claim 8 , wherein the head pointer is atomically updated to point to the spare bucket in response to detecting that contents of the first bucket have been copied into the spare bucket.

12. The system of claim 8 , wherein the split-spare bucket is configured to occupy a last slot in the table before any given split of the table is initiated, and the split-spare bucket is configured to occupy other than the last slot in the table while the given split is ongoing.

13. The system of claim 8 , wherein the updating includes updating the buckets in a consecutive-cyclic manner.

14. The system of claim 8 , wherein the metadata structure is stored in non-volatile memory.

15. A computer program product embodied on a non-transitory computer readable medium, the computer program product including instructions that, when executed by a computer, cause the computer to perform operations, comprising:
providing a table of buckets having a fixed number of domains, each of the domains including a corresponding subset of the buckets;
providing a spare bucket for each of the subsets of the buckets;
providing a metadata structure for each of the fixed number of domains, the metadata structure including a head pointer that points to a first bucket of a corresponding subset of the buckets and a spare_bucket pointer that points to the spare bucket of the corresponding subset of the buckets;
providing a split-spare bucket pointer that points to a split-spare bucket, the split-spare bucket being configured to receive sub-buckets during a split of the table, the split-spare bucket being used only when a split of the table is ongoing, such that the split-spare bucket is not used when a split of the table is not ongoing; and and
updating the head pointer and the spare_bucket pointer for corresponding domains in response to updating the bucket.

16. The computer program product of claim 15 , wherein a subset of the buckets corresponding to a first domain of the fixed number of domains is a first subset and another subset of the buckets corresponding to a second domain of the fixed number of domains is a second subset, the operations further comprising:
splitting the first subset into a first subgroup of buckets and a second subgroup of buckets; and
splitting the second subset of the buckets into a third subgroup of buckets and a fourth subgroup of bucket.

17. The computer program product of claim 16 , wherein the operations further comprise:
mapping buckets in the first subgroup and the second subgroup to the first subset; and
mapping buckets in the third subgroup and the fourth subgroup to the second subset;
wherein each mapping is implemented via a corresponding combined domain identifier and a corresponding bucket identifier.

18. The computer program product of claim 15 , wherein the head pointer is atomically updated to point to the spare bucket in response to detecting that contents of the first bucket have been copied into the spare

Assignees

• Emc Ip Holding Co Llc

Inventors

• Harel Bar
• Shabi Uri
• Rahamim Maor

Classifications

• G06F16/9014 Primary

  hash tables · CPC title

• H04L67/561

  Adding application-functional data or data for application control, e.g. adding metadata · CPC title

• H04L67/1097 Primary

  for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS] · CPC title

• H04L47/215

  using token-bucket · CPC title