Method, electronic device, and computer program product for storing and searching for data

Patent metadata

Field	Value
Publication number	US-11645255-B2
Application number	US-202117224189-A
Country	US
Kind code	B2
Filing date	Apr 7, 2021
Priority date	Mar 15, 2021
Publication date	May 9, 2023
Grant date	May 9, 2023

Abstract

The present disclosure provides a method for storing data, including: storing data in a first node, the first node being selected from a first node set including a first edge node and child nodes thereof; selecting, from a second node set including a second edge node and child nodes thereof, a second node for storing the data, the first edge node being a child node of the second edge node; and storing the data in the second node. The present disclosure further provides a method for searching for data. The present disclosure can reduce the time for searching for data in a distributed storage system.

First claim

What is claimed is:

1. A method, comprising:
storing data in a first node, the first node being selected from a first node set comprising a first edge node and child nodes thereof, the first node set comprising a first ring of nodes at a first level in an arrangement of multiple hash rings;
selecting, from a second node set comprising a second edge node and child nodes thereof, a second node for storing the data, the first edge node being a child node of the second edge node; and
storing the data in the second node;
the method further comprising:
using a hash value of the data to search the first node set for the data; and
in response to a failure in finding the data in the first node set, using the hash value of the data to search for the data in the second node set;
wherein the second node set comprises a second ring of nodes at a second level in the arrangement of multiple hash rings, the first ring of nodes at the first level being arranged within the second ring of nodes at the second level in the arrangement of multiple hash rings;
wherein the first node is determined based on a comparison between hash values of nodes in the first node set and the hash value of the data;
wherein the second node is determined based on a comparison between hash values of nodes of the second node set and the hash value of the data; and
wherein the first ring of nodes at the first level comprises at least one node corresponding to a far edge node based on distance relative to a specified cloud and the second ring of nodes at the second level comprises at least one node corresponding to a near edge node based on distance relative to the specified cloud, the near edge node being closer to the specified cloud than the far edge node.

2. The method according to claim 1 , further comprising:
selecting, from a third node set comprising a third edge node and child nodes thereof, a third node for storing the data, the second edge node being a child node of the third edge node; and
storing the data in the third node.

3. The method according to claim 1 , further comprising:
in response to a failure in storing the data in the first node, storing the data in the first edge node; and
in response to a failure in storing the data in the second node, storing the data in the second edge node.

4. The method according to claim 1 , wherein the data is metadata of another piece of data and at least comprises a storage location of the other piece of data.

5. The method according to claim 1 , wherein the child nodes of the first edge node are terminal devices.

6. The method according to claim 1 , wherein the data and a hash value thereof are stored in association with one another.

7. A method, comprising:
using a hash value of the data to search a first node set comprising a first edge node and child nodes thereof for the data, the first node set comprising a first ring of nodes at a first level in an arrangement of multiple hash rings; and
in response to a failure in finding the data in the first node set, using the hash value of the data to search for the data in a second node set comprising a second edge node and child nodes thereof, the first edge node being a child node of the second edge node;
wherein the second node set comprises a second ring of nodes at a second level in the arrangement of multiple hash rings, the first ring of nodes at the first level being arranged within the second ring of nodes at the second level in the arrangement of multiple hash rings;
wherein searching the first node set for the data comprises:
determining a first node in the first node set based on a comparison between hash values of nodes in the first node set and the hash value of the data; and
using the hash value of the data to search the first node for the data; and
wherein the first ring of nodes at the first level comprises at least one node corresponding to a far edge node based on distance relative to a specified cloud and the second ring of nodes at the second level comprises at least one node corresponding to a near edge node based on distance relative to the specified cloud, the near edge node being closer to the specified cloud than the far edge node.

8. The method according to claim 7 , further comprising:
receiving the searching from one of the child nodes of the first edge node.

9. The method according to claim 7 , further comprising:
in response to a failure in finding the data in the first node, determining a second node in the second node set via the first node and based on a comparison between nodes in the second node set and the hash value; and
searching the second node for the data.

10. The method according to claim 7 , further comprising:
in response to a failure in finding the data in the first node, searching the first edge node in the first node set for the data.

11. The method according to claim 7 , wherein the data is metadata of another piece of data and at least comprises a storage location of the other piece of data.

12. An electronic device, comprising:
at least one processing unit; and
at least one memory that is coupled to the at least one processing unit and stores instructions for execution by the at least one processing unit, wherein the instructions, when executed by the at least one processing unit, cause the electronic device to perform a method for storing data, the method comprising:
storing data in a first node, the first node being selected from a first node set comprising a first edge node and child nodes thereof, the first node set comprising a first ring of nodes at a first level in an arrangement of multiple hash rings;
selecting, from a second node set comprising a second edge node and child nodes thereof, a second node for storing the data, the first edge node being a child node of the second edge node; and
storing the data in the second node;
the method further comprising:
using a hash value of the data to search the first node set for the data; and
in response to a failure in finding the data in the first node set, using the hash value of the data to search for the data in the second node set;
wherein the second node set comprises a second ring of nodes at a second level in the arrangement of multiple hash rings, the first ring of nodes at the first level being arranged within the second ring of nodes at the second level in the arrangement of multiple hash rings;
wherein the first node is determined based on a comparison between hash values of nodes in the first node set and the hash value of the data;
wherein the second node is determined based on a comparison between hash values of nodes of the second node set and the hash value of the data; and
wherein the first ring of nodes at the first level comprises at least one node corresponding to a far edge node based on distance relative to a specified cloud and the second ring of nodes at the second level comprises at least one node corresponding to a near edge node based on distance relative to the specified cloud, the near edge node being closer to the specified cloud than the far edge node.

13. The electronic device according to claim 12 , further comprising:
selecting, from a third node set comprising a third edge node and child nodes thereof, a third node for storing the data, the second edge node being a child node of the third edge node; and
storing the data in the third node.

14. The electronic device according to claim 12 , further comprising:
in response to a failure in storing the data in the first node, storing the data in the first edge node; and
in response to a failure in storing the data in the second node, storing the

Assignees

• Emc Ip Holding Co Llc

Inventors

• Lin Zhenzhen
• Chen Si
• Chen Qiang
• He Bin

Classifications

• G06F3/067 Primary

  Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS] · CPC title

• G06F16/322

  Trees · CPC title

• G06F16/2255 Primary

  Hash tables · CPC title

• G06F3/0646

  Horizontal data movement in storage systems, i.e. moving data in between storage devices or systems · CPC title

• G06F16/245

  Query processing · CPC title