Multi-level distributed hash table for data storage in a hierarchically arranged network

• US 8,977,660 B1
• Filed: 02/22/2012
• Issued: 03/10/2015
• Est. Priority Date: 12/30/2011
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Xin, Qin, Zhang, Feng, Bao, Qi
• Primary Examiner(s): Jalil, Neveen Abel
• Assistant Examiner(s): Tamaru, Michael K
• Application Number:
  US13/402,329
• Time in Patent Office: 1,112 Days
• US Class Current: 707/827
• CPC Class Codes: H04N 21/23103 using load balancing strategies, e.g. by placing or distributing content on different disks, different memories or different servers storage management G06F3/0604; allocation of resources considering the load in multiprogramming arrangements G06F9/505; techniques for rebalancing the load in a distributed system G06F9/5083; access to distributed or replicated servers, e.g. load balancing, in data networks H04L67/1001

Abstract

An improved technique for distributed data storage employs multiple DHT (distributed hash table) rings provided at different levels of a network hierarchy. A computing node is identified for data storage by performing multiple hashing operations, one for each DHT ring. The hashing operations for the different rings are distinct in that they are performed using different hashing functions and/or are performed on different data sources. In one example, a 2-level DHT is formed from a group of LANs forming a first DHT ring and a group of computing nodes, within each LAN, forming a second DHT ring.

Claims

1. A method of storing data in a computing network, comprising:

acquiring live video data by a camera coupled to a computing node of the computing network;

dividing, by the computing node, the acquired live video data into multiple chunks, each chunk including a portion of the acquired live video data; and

for each chunk;

erasure coding the chunk to create erasure coded fragments;

performing a first hashing operation to generate a first key;

performing a second hashing operation to generate a second key;

applying the first key to a first logical ring of computing nodes of the computing network to identify a matching node that satisfies at least one criterion associated with the first key, the first logical ring of computing nodes organized according to a first level of a multi-level DHT (distributed hash table), such that each computing node in the first logical ring of computing nodes forms a respective node in the first level of the multi-level DHT;

applying the second key to a second logical ring of computing nodes of the computing network to identify a matching node of the second logical ring of computing nodes that satisfies at least one criterion associated with the second key, the second logical ring of computing nodes organized according to a second level of the multi-level DHT, such that each computing node in the second logical ring of computing nodes forms a respective node in the second level of the multi-level DHT, wherein the second logical ring of computing nodes includes the matching node of the first logical ring of computing nodes and a set of nodes that are distinct from the first logical ring of computing nodes; and

directing at least one of the erasure coded fragments to be stored on the matching node of the second logical ring of computing nodes,

wherein the computing node that is coupled to the camera is a computing node of the multi-level DHT, and

wherein the method further comprises directing metadata describing one or more storage locations of the erasure coded fragments to be stored in one more computing nodes of the second logical ring of computing nodes.

2. The method as recited in claim 1, wherein the computing network is arranged hierarchically with the first logical ring of computing nodes operating at a first network level of the computing network and the second logical ring of computing nodes operating at a second network level of the computing network that is lower than the first network level, and wherein the first logical ring of computing nodes includes multiple head nodes, each representing a different Local Area Network (LAN) of the computing network.

3. The method as recited in claim 2, wherein each head node in the first logical ring of computing nodes includes routing information pertaining to at least one other head node in the first logical ring of computing nodes.

4. The method as recited in claim 3, wherein each computing node in the second logical ring of computing nodes includes routing information pertaining to at least one other computing node in the second logical ring of computing nodes.

5. The method as recited in claim 2, wherein, when directing at least one of the erasure coded fragments to be stored on the matching node, the method further includes directing at least some of the erasure coded fragments to be stored on different computing nodes of the second logical ring of computing nodes.

6. The method as recited in claim 5, wherein the method further includes identifying a head node in the first logical ring of nodes other than the matching node and storing additional erasure coded fragments of the chunk in the LAN represented by the identified head node.

7. The method of claim 2, wherein each of the first ring of computing nodes represents a respective LAN and is also a member of a respective second ring of computing nodes within the respective LAN.

8. The method of claim 2, further comprising:

acquiring live video data by each of multiple cameras coupled to respective computing nodes of the multi-level DHT; and

storing, by each of the multiple computing nodes of the computing network, fragments of the respective live video data collected on multiple other computing nodes of the multi-level DHT.

9. The method of claim 8, wherein the multiple computing nodes of the computing network that collect video data include the computing node as recited in claim 1, wherein the method further comprises the first computing node:

performing a third hashing operation to generate a third key, wherein the third key is different from the first key and the second key and identifies a head node in the first ring of computing nodes,

wherein directing metadata includes directing the metadata to be stored on the LAN represented by the identified head node, the metadata indicating locations where fragments of video data acquired from the camera of the first computing node are stored.

10. The method of claim 9,

wherein, prior to performing the hashing operation to generate the third key, the method further comprises the first computing node generating a text value in a uniform naming format, the text value including a camera identifier of the camera of the first computing node and a date,

wherein performing the hashing operation to generate the third key is performed by applying the text value to a third hash function, and

wherein the method further comprises, after storing the metadata and by a computing node of the computing network other than the first computing node:

receiving entered values specifying (i) a camera identifier, identifying a camera from which video data is sought, and (ii) a date on which desired video data was acquired;

generating a text value in the uniform naming format based on the entered values;

performing the hashing operation on the generated text value using the third hash function to generate the third key;

identifying a head node in the first ring of computing nodes using the third key;

retrieving metadata from the LAN represented by the identified head node, the metadata indicating locations where fragments of video data acquired from the camera of the first node are stored; and

retrieving the fragments of video data acquired from the camera of the first node from the indicated locations.

11. The method of claim 2, further comprising each computing node of the first ring of computing nodes obtaining a LAN number from a registration server and hashing the LAN number to generate a LAN ID, wherein applying the first key to the first logical ring of computing nodes of the computing network includes comparing the first key with the LAN ID of at least one computing node of the first ring of computing nodes.

12. The method of claim 11, further comprising each computing node of the second ring of computing nodes hashing a MAC (Media Access Controller) address of the respective computing node to generate a node ID, wherein applying the second key to the second logical ring of computing nodes of the computing network includes comparing the second key with the node ID of at least one computing node of the second ring of computing nodes.

13. The method as recited in claim 2, further comprising selecting the first logical ring of computing nodes from a larger set of computing nodes on the computing network, wherein the computing nodes included in the first logical ring of computing nodes are selected based at least in part on physical proximity to one another.

14. The method as recited in claim 2, wherein the acquired live video data is associated with an identifier, and wherein the method further comprises:

performing a third hashing operation on the identifier to generate a third key; and

applying the third key to the first logical ring of computing nodes to identify a head node that satisfies at least one criterion associated with the third key,

wherein the act of directing the metadata includes directing metadata pertaining to a storage location of at least one of the erasure coded fragments to be stored in the LAN represented by the identified head node.

15. The method as recited in claim 1, wherein the first hashing operation and the second hashing operation are computed based on the same data source.

16. The method as recited in claim 15, wherein the first hashing operation generates the first key by applying a first hashing function to the data source, and the second hashing operation generates the second key by applying a second hashing function to the data source, the second hashing function being different from the first hashing function.

17. The method as recited in claim 15, wherein the second hashing operation is performed on the source data to generate the second key and the first hashing operation is performed on the second key to generate the first key.

18. The method as recited in claim 14, wherein the computing node that is coupled to the camera stores the acquired live video data in a file, and wherein the identifier includes at least a portion of a path name of the file.

19. The method as recited in claim 14, wherein the multiple chunks are obtained by dividing the file into the multiple chunks.

20. The method as recited in claim 19, wherein the path name of the file has a uniform naming format that includes at least one of location information and date information, and wherein the method further comprises:

creating a text value in the form of a path name according to the uniform naming format to specify a file based on at least one of location information and date information;

hashing the text value, when performing the hashing operation on the identifier, to generate the third key;

identifying the LAN on which metadata pertaining to the specified file is stored;

reading the metadata; and

obtaining a location from the metadata of at least one fragment of the file.

21. A computerized apparatus, comprising:

a set of processors; and

memory, coupled to the set of processors, the memory arranged to store instructions executable by the set of processors,

wherein the set of processors executing instructions from the memory forms a specialized circuit arranged to;

acquire live video by a camera coupled to a computing node of the computing network;

divide, by the computing node, the acquired live video into multiple chunks, each chunk including a portion of the acquired live video; and

for each chunk;

erasure code the chunk to create erasure coded fragments;

perform a first hashing operation to generate a first key;

perform a second hashing operation to generate a second key;

apply the first key to a first logical ring of computing nodes of a computing network to identify a matching node that satisfies at least one criterion associated with the first key, the first logical ring of computing nodes organized according to a first level of a multi-level DHT (distributed hash table), such that each computing node in the first logical ring of computing nodes forms a respective node in the first level of the multi-level DHT;

apply the second key to a second logical ring of computing nodes of the computing network to identify a matching node of the second logical ring of computing nodes that satisfies at least one criterion associated with the second key, the second logical ring of computing nodes organized according to a second level of the multi-level DHT, such that each computing node in the second logical ring of computing nodes forms a respective node in the second level of the multi-level DHT, wherein the second logical ring of computing nodes includes the matching node of the first logical ring of computing nodes and a set of nodes that are distinct from the first logical ring of computing nodes; and

direct a storing operation of at least one of the erasure coded fragments on the matching node of the second logical ring of computing nodes,

wherein the computing node that is coupled to the camera is a computing node of the multi-level DHT, and

wherein the specialized circuit is further arranged to direct metadata describing one or more storage locations of the erasure coded fragments to be stored in one more computing nodes of the second logical ring of computing nodes.

22. The computerized apparatus as recited in claim 21, wherein the computing network is arranged hierarchically with the first logical ring of computing nodes operating at a first network level of the computing network and the second logical ring of computing nodes operating at a second network level of the computing network that is lower than the first network level, and wherein the first logical ring of computing nodes includes multiple head nodes, each representing a different Local Area Network (LAN) of the computing network.

23. The computerized apparatus as recited in claim 22, wherein the acquired live video is associated with an identifier and wherein the specialized circuit is further arranged to:

perform a third hashing operation including a hashing function on the identifier to generate a third key; and

apply the third key to the first logical ring of computing nodes to identify a head node that satisfies at least one criterion associated with the third key,

wherein, when arranged to direct metadata, the specialized circuit is further arranged to direct metadata pertaining to a storage location of at least one of the erasure coded fragments to be stored in the LAN represented by the identified head node.

24. A computer program product including non-transitory computer readable medium having instructions which, when executed by a set of processors of a computerized apparatus, cause the set of processors to perform a method of storing data in a computing network, the method comprising:

acquiring live video by a camera coupled to a computing node of the computing network;

dividing, by the computing node, the acquired live video into multiple chunks, each chunk including a portion of the acquired live video; and

for each chunk;

erasure coding the chunk to create erasure coded fragments;

performing a first hashing operation to generate a first key;

performing a second hashing operation to generate a second key;

applying the first key to a first logical ring of computing nodes of the computing network to identify a matching node that satisfies at least one criterion associated with the first key, the first logical ring of computing nodes organized according to a first level of a multi-level DHT (distributed hash table), such that each computing node in the first logical ring of computing nodes forms a respective node in the first level of the multi-level DHT;

applying the second key to a second logical ring of computing nodes of the computing network to identify a matching node of the second logical ring of computing nodes that satisfies at least one criterion associated with the second key, the second logical ring of computing nodes organized according to a second level of the multi-level DHT, such that each computing node in the second logical ring of computing nodes forms a respective node in the second level of the multi-level DHT, wherein the second logical ring of computing nodes includes the matching node of the first logical ring of computing nodes and a set of nodes that are distinct from the first logical ring of computing nodes; and

directing at least one of the erasure coded fragments to be stored on the matching node of the second logical ring of computing nodes,

wherein the computing node that is coupled to the camera is a computing node of the multi-level DHT, and

wherein the method further comprises directing metadata describing one or more storage locations of the erasure coded fragments to be stored in one more computing nodes of the second logical ring of computing nodes.

25. The computer program product as recited in claim 24, wherein the acquired live video data is associated with an identifier, and wherein the method further comprises:

performing a third hashing operation including performing a hashing function on the identifier to generate a third key; and

applying the third key to the first logical ring of computing nodes to identify a node that satisfies at least one criterion associated with the third key,

wherein the act of directing metadata includes directing metadata pertaining to a storage location of at least one of the erasure coded fragments to be stored in a LAN of the identified node.