Selecting data nodes using multiple storage policies in cloud storage system

• US 9,158,460 B2
• Filed: 04/25/2012
• Issued: 10/13/2015
• Est. Priority Date: 04/25/2011
• Status: Active Grant

• Current Assignee: KT Corporation
• Original Assignee: KT Corporation
• Inventors: Park, Chang-Sik, Lee, Eo-Hyung, Hwang, Jin-Kyung
• Primary Examiner(s): Li, Aimee
• Assistant Examiner(s): Thammavong, Prasith
• Application Number:
  US13/455,269
• Publication Number:
  US 20120272025A1
• Time in Patent Office: 1,266 Days
• Field of Search: 711/162
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1446 Point-in-time backing up or restoration of persistent data
• CPC Class Codes: G06F 11/1448 Management of the data involved in backup or backup restore
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 2206/1012 Load balancing
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0614 Improving the reliability of storage systems
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

Provided are a method and a server for selecting data nodes for storing an object and replicas thereof in a cloud storage system having a plurality of data nodes grouped in a plurality of storage areas. The method may include selecting at least one storage area for storing the object and the replicas thereof sequentially with a locality policy, a low-cost policy, a load-balancing policy, and a space-balancing policy and selecting at least one data node from the selected at least one storage area sequentially using a load-balancing policy and a space-balancing policy.

Claims

1. A method for selecting data nodes for storing an object from received from a user terminal and replicas of the received object in a cloud storage system having a plurality of data nodes grouped in a plurality of storage areas, the method comprising:

selecting, by a server including at least one hardware processor, at least one storage area for storing the object and the replicas, wherein (i) a storage area for storing the object is selected as a storage area closest to a current location of the user terminal among the plurality of storage areas included in the cloud storage system, and (ii) storage areas for storing the replicas are selected by sequentially applying a low-cost policy, a first load-balancing policy, and a first space-balancing policy in a unit of storage area according to a first predetermined policy priority, among remaining storage areas excluding the storage area selected for the object, wherein in the first predetermined policy priority, the low-cost policy has a higher priority than the first load-balancing policy, and the first load-balancing policy has a higher priority than the first space-balancing policy; and

selecting, by the server, at least one data node from the selected at least one storage area by sequentially applying a second load-balancing policy and a second space-balancing policy in a unit of data node according to a second predetermined policy priority, wherein in the second predetermined policy priority, the second load-balancing policy has a higher priority than the second space-balancing policy.

2. The method of claim 1, wherein the selecting the storage area includes:

obtaining location information from the user terminal of a user request for the cloud storage system to store the object;

detecting the current location of the user terminal based on the obtained location information; and

selecting the storage area closest to the detected current location of the user terminal among the plurality of storage areas included in the cloud storage system.

3. The method of claim 1, wherein the selecting storage areas to store the replicas includes:

selecting first candidate storage areas, excluding the storage area selected for the object, from the plurality of storage areas included in the cloud storage system by applying the low-cost policy;

selecting second candidate storage areas from the first candidate storage area by applying the first load-balancing policy; and

then

selecting a final candidate storage from the second candidate storage area by applying the first space-balancing policy.

4. The method of claim 3, wherein the selecting the first candidate storage areas includes:

determining presence or absence of first storage areas having network latency lower than a related threshold in the cloud storage system excluding the storage area selected for the object;

determining the storage area of the first storage areas, when present, having network latency lower than the related threshold as the first candidate storage; and

selecting N storage areas having comparatively low network latency as the first candidate storage when the first storage areas are absent,

wherein N is an integer number equal to or greater than 1.

5. The method of claim 4, wherein the determining the presence or absence of first storage areas in the cloud storage system comprises:

measuring network latency of each storage area for a certain period time;

calculating average network latency of each storage area based on the measured network latencies;

comparing the average network latency of each storage area with a certain latency threshold; and

including a storage area having the average network latency lower than the certain latency threshold in the first storage areas based on the comparison result.

6. The method of claim 3, wherein the selecting the second candidate storage areas includes:

determining whether the first candidate storage areas include second storage areas having an area average processing load smaller than a related threshold;

detecting the second storage areas having the area average processing load smaller than the related threshold as the second candidate storage areas when the first candidate storage areas include the second storage areas;

otherwise, selecting N storage areas having comparatively low area average processing load as the second candidate storages,

wherein N is an integer number equal to or greater than 1.

7. The method of claim 6, wherein the determining whether the first storage areas include second storage areas includes:

measuring a processing load of each data in the first storage areas for a certain period time;

calculating an area average processing load of each one of the first storage areas based on the measured processing loads;

comparing the area average processing load of each storage area with a certain threshold; and

including a storage area having the area average processing load lower than the certain threshold in the second storage areas based on the comparison result.

8. The method of claim 3, wherein the selecting a final candidate storage from the second candidate storage areas includes:

selecting a storage area having a highest availability rate from the second candidate storage areas as the final storage area,

wherein an availability rate of a storage area denotes an available storage space with respect to a total storage space of the storage area.

9. The method of claim 1, wherein the selecting at least one data node from the selected at least one storage area includes:

selecting first candidate data nodes by applying the second load-balancing policy; and

selecting a final data node from the first candidate data nodes by applying the second space-balancing policy.

10. The method of claim 9, wherein the selecting first candidate data nodes includes:

determining whether the selected storage area includes first data nodes having an average processing load smaller than a related threshold;

setting the first data nodes having the average processing load smaller than the related threshold as the first candidate data nodes when the selected storage area includes the first data nodes; and

selecting N data nodes having comparatively low average processing load as the first candidate data nodes when the selected storage area excludes the first data nodes,

wherein N is an integer number equal to or greater than 1.

11. The method of claim 10, wherein the determining whether the selected storage area includes the first data nodes includes:

measuring a processing load of each one of the first data nodes for a certain period time;

calculating an average processing load of each one of the first data nodes based on the measured processing loads;

comparing the average processing load of each one of the first data nodes with a certain threshold; and

including a data node having the average processing load lower than the certain threshold in the first candidate data nodes based on the comparison result.

12. The method of claim 9, wherein selecting a final data node from the first candidate data nodes by applying the second space-balancing policy includes:

selecting a data node having a highest availability rate from the first candidate data node s as the final data node; and

storing one of the replicas in the final data node,

wherein an availability rate of a data node denotes an available storage space in respect to a total storage space of the data node.

13. A server for selecting data nodes for storing an object from received from a user terminal and replicas of the received object in a cloud storage system having a plurality of data nodes grouped in a plurality of storage areas, the server comprising at least one hardware processor that executes:

a storage area selection unit configured to select at least one storage area for storing the object and the replicas, wherein (i) a storage area for storing the object is selected as a storage area closest to a current location of the user terminal among the plurality of storage areas included in the cloud storage system, and (ii) storage areas for storing the replicas are selected by sequentially applying a low-cost policy, a first load-balancing policy, and a first space-balancing policy in a unit of storage area according to a first predetermined policy priority, among remaining storage areas excluding the storage area selected for the object, wherein in the first predetermined policy priority, the low-cost policy has a higher priority than the first load-balancing policy, and the first load-balancing policy has a higher priority than the first space-balancing policy; and

a data node selection unit configured to select at least one data node from the selected at least one storage area by sequentially applying a second load-balancing policy and a second space-balancing policy in a unit of data node according to a second predetermined policy priority, wherein in the second predetermined policy priority, the second load-balancing policy has a higher priority than the second space-balancing policy.

14. The server of claim 13, wherein the storage area selection unit is configured to:

obtain location information from the user terminal of a user request for the cloud storage system to store the object;

detect the current location of the user terminal based on the obtained location information; and

select the storage area closest to the detected current location of the user terminal among the plurality of storage areas included in the cloud storage system.

15. The server of claim 13, wherein the storage area selection unit is configured to perform:

a low-cost policy execution procedure which selects first candidate storage areas, excluding the storage area selected for the object, from the plurality of storage areas included in the cloud storage system by applying the low-cost policy;

an area load-balancing policy execution procedure which selects second candidate storage areas from the first candidate storage areas by applying the first load-balancing policy; and

an area space-balancing policy execution procedure which selects a final candidate storage from the second candidate storage areas by applying the first space-balancing policy.

16. The server of claim 15, wherein:

the low-cost policy execution procedure includes;

determining whether the cloud storage system includes, excluding the storage area selected for the object, first storage areas having network latency lower than a related threshold;

determining the storage area having network latency lower than the related threshold as the first candidate storages when the cloud storage system includes the first storage areas;

otherwise, selecting N storage areas having comparatively low network latency as the first candidate storage,

the area load-balancing policy execution procedure includes;

determining whether the first candidate storage areas include second storage areas having an area average processing load smaller than a related threshold;

determining the second storage areas having the area average processing load smaller than the related threshold as the second candidate storage areas when the first candidate storage areas include the second storage areas;

otherwise, selecting N storage areas having comparatively low area average processing load as the second candidate storages, and

the area space-balancing policy execution procedure includes;

selecting a storage area having a highest availability rate from the second candidate storage areas as the final storage area,

wherein N is an integer number equal to or greater than 1, and an availability rate of a storage area denotes an available storage space with respect to a total storage space of the storage area.

17. The server of claim 13, wherein the data node selection unit is configured to perform:

a load-balancing policy execution procedure which selects first candidate data nodes by applying the second load-balancing policy; and

a space-balancing policy execution procedure which selects a final data node from the first candidate data nodes by applying the second space-balancing policy.

18. The server of claim 17, wherein:

the load-balancing policy execution procedure includes;

determining whether the selected storage area includes first data nodes having an average processing load smaller than a related threshold;

setting the first data nodes having the average processing load smaller than the related threshold as the first candidate data nodes when the selected storage area includes the first data nodes;

otherwise, selecting N data nodes having comparatively low average processing load as the first candidate data nodes, and

the space-balancing policy execution procedure includes;

selecting a data node having a highest availability rate from the first candidate data node s as the final data node; and

storing one of the replicas in the final data node,

wherein N is an integer number equal to or greater than 1, and an availability rate of a data node denotes an available storage space in respect to a total storage space of the data node.