Retention time based consistent hash ring

Patent metadata

Field	Value
Publication number	US-11372728-B2
Application number	US-202016986564-A
Country	US
Kind code	B2
Filing date	Aug 6, 2020
Priority date	Aug 6, 2020
Publication date	Jun 28, 2022
Grant date	Jun 28, 2022

Abstract

A retention-based consistent hash ring process defines each file name in the system to include its expiration date (or time) as a prefix or suffix that is stored and indexed as metadata. The process uses a virtual node to represent adjacent expiration days to create virtual nodes based on individual days of the week. Each physical node contains the same number of labeled virtual nodes, and the consistent hash ring process is used to move files with the same expiration day to different physical nodes by looking for next labeled virtual nodes on the hash ring. This provides a way to locate the virtual node storage location by specifying a file's expiration date as part of the key used in the hash ring process, and distributes files that may otherwise be assigned to the same physical node through a backup policy.

First claim

What is claimed is:

1. A method of balancing a consistent hash ring having a number of physical nodes representing storage resources in a client-server computer network, comprising:
defining a file name for each file used in a file system to include an expiration day of a corresponding file;
creating a plurality of virtual nodes for each of the physical nodes, wherein each virtual node is labeled with a different day of the week as a label;
creating a key for each file by hashing the corresponding file name including the expiration day; and
using the key to locate a physical node storage location for a respective file by identifying corresponding virtual nodes having a same label as the expiration day of the respective file.

2. The method of claim 1 wherein the network implements a distributed file system storing files in one or more centralized storage resources by access by a plurality of clients.

3. The method of claim 2 wherein the network comprises backup server executing a deduplication backup system.

4. The method of claim 3 wherein at least part of the network comprises a virtualized network, and further comprises virtual storage implemented one or more virtual machines in the network.

5. The method of claim 3 wherein the expiration day is defined by a retention time corresponding to a file deletion frequency set in a backup policy.

6. The method of claim 5 further comprising:
defining a plurality of backup policies for the file system, each backup policy applied to one or more files of the file system; and
applying a frequency and retention policy to the plurality of backup policies to derive the retention time.

7. The method of claim 1 further comprising determining a first entry point of the file into the consistent hash ring by determining physical node corresponding to a nearest match of the key based on a hash value of the file name compared to a calculated hash value for each physical node.

8. The method of claim 7 further comprising:
comparing the key after the first entry point to a next label of a virtual node in the physical node; and if there is no match
comparing the key to virtual nodes in a next physical node adjacent to the physical node to identify a first virtual node matching the key.

9. The method of claim 7 wherein the hash value for each physical node comprises a hash of a processor identifier and network address of the physical node.

10. A method of balancing storage of files in a distributed file based computer network, comprising:
defining a consistent hash ring having a number of physical nodes representing storage resources of the network;
defining, for each physical node, a plurality of virtual nodes, each labeled with a different day of the week;
defining an expanded file name for each file to include a directory path and name of the file and an expiration date of the file appended as a prefix or suffix;
deriving a key for each file comprising a hash value of the expanded file name of the file; and
using the key to find a nearest matching virtual node in a physical node based on a match of the day of week label of the virtual node and the expiration date of the key hash value.

11. The method of claim 10 further comprising determining a first entry point of the file into the consistent hash ring by determining physical node corresponding to a nearest match of the key based on a hash value of the file name compared to a calculated hash value for each physical node.

12. The method of claim 11 further comprising:
comparing the key after the first entry point to a next label of a virtual node in the physical node; and if there is no match
comparing the key to virtual nodes in a next physical node adjacent to the physical node to identify a first virtual node matching the key.

13. The method of claim 10 wherein the hash value for each physical node comprises a hash of a processor identifier and network address of the physical node.

14. The method of claim 10 wherein the network implements a distributed file system storing files in one or more centralized storage resources by access by a plurality of clients, and comprises backup server executing a deduplication backup system.

15. The method of claim 14 wherein the expiration day is defined by a retention time corresponding to a file deletion frequency set in a backup policy.

16. The method of claim 15 further comprising:
defining a plurality of backup policies for the file system, each backup policy applied to one or more files of the file system; and
applying a frequency and retention policy to the plurality of backup policies to derive the retention time.

17. A system for balancing storage of files in a distributed file based computer network comprising: a processor; and memory configured to store one or more sequences of instructions which, when executed by the processor, cause the processor to carry out the steps of:
defining a consistent hash ring having a number of physical nodes representing storage resources of the network;
defining, for each physical node, a plurality of virtual nodes, each labeled with a different day of the week;
defining an expanded file name for each file to include a directory path and name of the file and an expiration date of the file appended as a prefix or suffix;
deriving a key for each file comprising a hash value of the expanded file name of the file; and
using the key to find a nearest matching virtual node in a physical node based on a match of the day of week label of the virtual node and the expiration date of the key hash value.

18. The system of claim 17 wherein the method further comprises:
determining a first entry point of the file into the consistent hash ring by determining physical node corresponding to a nearest match of the key based on a hash value of the file name compared to a calculated hash value for each physical node;
comparing the key after the first entry point to a next label of a virtual node in the physical node; and if there is no match
comparing the key to virtual nodes in a next physical node adjacent to the physical node to identify a first virtual node matching the key.

19. The system of claim 18 wherein the hash value for each physical node comprises a hash of a processor identifier and network address of the physical node, and wherein the network implements a distributed file system storing files in one or more centralized storage resources by access by a plurality of clients, and comprises backup server executing a deduplication backup system.

20. The system of claim 19 wherein the expiration day is defined by a retention time corresponding to a file deletion frequency set in a backup policy, and the method further comprises:
defining a plurality of backup policies for the file system, each backup policy applied to one or more files of the file system; and
applying a frequency and retention policy to the plurality of backup policies to derive the retention time.

Assignees

• Emc Ip Holding Co Llc

Inventors

• Liao mengze
• Su Lihui
• Murti Arun
• Che Roger Hongyi
• Lin Zhenzhen
• Hu Xiaolei

Classifications

• G06F16/162

  Delete operations (erasing in storage systems G06F3/0652) · CPC title

• G06F16/137 Primary

  Hash-based (content-based indexing of textual data G06F16/31) · CPC title

• G06F11/1464 Primary

  for networked environments · CPC title

• G06F11/1484

  involving virtual machines · CPC title

• G06F11/1469

  Backup restoration techniques · CPC title