JP6566822B2 - Load balancing method in cloud storage with range search - Google Patents

Description

  The present invention relates to a load distribution method in a range-searchable cloud storage that can increase the utilization rate of storage resources for key-value type data distributed and accumulated on the cloud.

  In recent years, cloud storage for big data processing has developed rapidly. In particular, cloud storage capable of range search for efficiently processing spatio-temporal data in social networks and Internet is attracting attention. However, in order to enable range search, it is necessary to maintain data locality (local reference), and low-cost and high-efficiency load distribution between physical nodes is a very difficult task.

In the prior art, a technique such as remote migration of adjacent nodes is often used. Remote migration of an adjacent node means that a lightly loaded node moves its own load to a node that is in charge of the neighboring node, and after it becomes an empty node, leaves its original position and the remote node is heavily loaded. It is a mechanism that migrates to the next and takes charge of the heavy node load.
The problem with the prior art is that the overhead is very large and the processing speed is slow.

  An example of this prior art is shown in FIG. FIG. 5 shows the loads on the nodes A to F and their assigned ranges. As a basic mechanism for rebalancing the workload among nodes, most of the conventional mechanisms use the reorder operation for remote migration. It is assumed that the second node is underloaded and the other overloaded nodes are relieved. In this case, first, all the workloads of the second node are moved to the adjacent direction. Since the second node becomes an empty node, it leaves the system and rejoins next to the overloaded node. The overloaded node moves its load to the next empty node. The movement cost in this case is obtained by adding α and β in FIG. Depending on this operation, the amount of data to be moved is large, but the balancing effect is limited.

In the present invention, a virtual node is managed by using a code # (CHORD #) algorithm as a search algorithm. The similarities and differences of this algorithm compared to the well-known code (CHORD) algorithm are as follows. The outline is as follows.
That is, in the code, a plurality of nodes are arranged in a ring with a logical arrangement, and a key as a search item is distributed and associated with each node by a hash function. The search is performed in the key space by the key. For this reason, each node is provided with a finger table for keys and addresses, in which the addresses of nodes that make the above-mentioned ring half a circle and a quarter of a cycle are sequentially written.
On the other hand, code # is similar in that a plurality of nodes are arranged in a ring with a logical arrangement, but items relating to data arranged in a one-dimensional manner have each node responsible for a predetermined range, And it is the structure arranged in order of the said data. The search is performed in the node space of the above nodes. Each node has a finger table similar to the above, but with respect to nodes and addresses.

  As described above, since the hash function is used in the case of the code, the distribution of the number of keys for each node is averaged. However, the relationship between the node position and the key order is dispersed, and range search is not easy. On the other hand, since the hash function is not used in the case of code #, the association between the node position and the key order can be simply associated. However, there is a bias in the distribution of the number of keys for each node.

H. C. Hsiao, H. Y. Chung, H. Shen, and Y. C. Chao, “Load Rebalancing for Distributed File Systems in Clouds,” IEEE Transactions on Paralleland Distributed Systems, vol. 24, no. 5, pp. 951-962, May. 2013.

  An object of the present invention is to make it possible to increase the utilization rate of storage resources for key-value type data distributed and accumulated on the cloud.

  For this reason, in the present invention, range search is performed in a cloud storage capable of range search, but the data allocated to the physical node that is the basis of the virtual node on the cloud storage is not unevenly distributed quantitatively. Therefore, load balancing is performed.

First, the cloud storage used in the load distribution method in the range searchable cloud storage according to the present invention is a network in which a plurality of physical nodes configured to include a plurality of storages, a processor and a memory combined with the storages are connected. Consists of above,
The range searchable cloud storage is formed on an overlay network to which a plurality of virtual nodes, each of which is composed of a virtual storage having a common capacity value by the storage and a virtual processor by a processor to which the virtual storage belongs, are connected. ,
In data storage, key-value type data is stored in cloud storage that can be searched in the above range,
In the search, the virtual node is searched for a predetermined key value.
Further, for load distribution of the physical nodes, a lower limit and an upper limit that is a predetermined multiple of the lower limit are provided for the data storage amount of each virtual node.
In order to distribute the load of physical nodes by adjusting the data storage amount of each virtual node in such a range searchable cloud storage, the following is performed.
(1) If new data is to be added to the first virtual node and the amount of added data is expected to exceed the upper limit, the added data amount is selected from the searchable cloud storage. With the empty virtual node as the second virtual node, the half of the upper limit data is distributed from the first virtual node to the second virtual node, and the arrangement of the virtual nodes on the overlay network is updated in a new order by this distribution. ,
(2) When the sum of the data amount of the first virtual node and the data amount of the second virtual node adjacent to each other in the arrangement of the key-value data is less than the upper limit, one of the first virtual node and the second virtual node And the other virtual node is made an empty virtual node, and the arrangement of the virtual nodes on the overlay network is updated.
(3) The sum of the data amount of each of the virtual storage and the second virtual node adjacent to each other in the arrangement of the key-value type data is not less than the above upper limit, and the data amount of one of the virtual nodes is If it is less than the lower limit, move the data from the other virtual node to the one virtual node, redistribute the data so that both of them exceed the lower limit, and arrange the virtual nodes on the overlay network. Update.

The present invention also relates to the first physical node and the second physical node selected from the physical nodes constituting the cloud storage.
The ratio of the number of non-empty virtual nodes of the physical node to the total number of virtual nodes is μ, and using a predetermined threshold parameter λ (∈ (0, 1)),
(1) and the virtual node number ratio mu ₁ belonging to the first physical node number of nodes is not empty in the virtual node belonging to the first physical node, the number of virtual nodes is not empty against the above number of virtual nodes which belong to the second physical node For the ratio μ ₂ , when μ ₁ (1 + λ) is larger than μ and μ ₂ (1−λ) is smaller than μ,
(2) Swap the retained data from the non-empty virtual node belonging to the first physical node to the empty virtual node belonging to the second physical node,
(3) updating the sequence of nodes on the overlay network;
It is characterized by that.

The search for the key value in the range searchable cloud storage is a search according to a code # algorithm.

Configuring an empty virtual node pool in which the entire empty virtual nodes occupy a continuous sequence of the overlay network in the overlay network;
The empty virtual node is selected from the empty virtual node pool.

  Further, the storage in each of the physical nodes is obtained by dividing the storage, and the division may be a division in which the same size area is the largest.

  The predetermined multiple is desirably more than 2 times and 2.08 times or less.

  Further, P2P (peer to peer) can be used for the overlay network.

  For example, by storing various measurement data in the cloud searchable range storage targeted by the present invention, the load on each physical node increases as data accumulation progresses, but this increase is often not uniform, The load of each physical node can be distributed using the load distribution method of the present invention, and the utilization rate of storage resources can be increased. In searching, for example, CHORD # can be used, so that searching can be performed efficiently.

It is a figure which shows the storage system structure based on the overlay proposed as an example of this invention. It is a schematic diagram of a physical node and a virtual node before and after swapping. (A) is a diagram illustrating split operations, (b) is a merge operation, and (c) is a redistribution operation. It is a figure which shows the example of load distribution operation. It is a figure which shows the example of the prior art which uses a reorder (Reorder) operation as a basic mechanism which rebalances a workload between nodes. It is a figure showing three patterns (A, B, C) of how to bias the initial load distribution in the simulation. (A), (b), (c) shows the comparison of the load distribution effect with respect to each said load. (A), (b), (c) represents the comparison of the data movement cost with respect to each said load. It is a figure which shows how data was deleted in each trial in a dynamic scenario. In a dynamic scenario, (a) shows a comparison of accumulated data movement costs, (b) shows a comparison of accumulated message transmission costs, and (c) shows a comparison of load distribution rates. is there. FIG. 6 is a diagram showing simulation results for data insertion in a dynamic scenario, where (a) shows a comparison of accumulated data movement costs, (b) shows a comparison of accumulated message transmission costs, and (c) ) Shows a comparison of load distribution rates. It is a figure which shows the simulation result in a heterogeneous environment, (a) shows the load distribution effect, (b) shows the data movement cost corresponding to it. It is a figure which shows the specific example which calculates | requires the total number m of a virtual node.

An example of applying the load distribution method in the cloud searchable range storage of the present invention is a cloud storage having a storage system architecture based on overlay.
Consider a set of large-scale distributed cloud storage consisting of N storage nodes. Let the radix up to N be n. Each physical node is divided into a plurality of virtual nodes, and a set of all virtual nodes is set to V (the number of virtual nodes of V is m). Let the capacity of the physical node p _{i be} c _i and the load of the virtual node v _{j be} l _j . The capacity of the physical node can be arbitrary, but the capacity of the virtual node is a predetermined value.

In order to perform a range search in a distributed state, a Chord # overlay is configured with all virtual nodes. In this specification, “overlay node” and “virtual node” are interchangeable. Chord # is a distributed data structure capable of range search. In the Chord # network, all overlay nodes are connected by a ring formed by connecting two links, and each position of the overlay node in the ring is determined by a range in which the node is responsible.
To expedite data retrieval, each overlay node has a finger table that provides a short circuit at multiple levels (levels in the skip list). In general, to calculate the i-th finger in its finger table, the overlay node asks the remote node of the (i-1) th finger and which (i-1) th finger is referring to. That is, the finger of level i is set to the finger pointer of the next lower level i-1 as in the following equation. As an initial value, the finger points to a direct successor.

In order to use Chord #, the key space of the data term is divided so as to be continuous, and each division is assigned to a virtual node. Here, the virtual node adopts the lower boundary of the division as the key, and adopts the lower boundary of the assigned range for the entire division. Also, not all virtual nodes are used to store data items. That is, some virtual nodes are left empty. Specifically, the set V of virtual nodes is divided into subsets V ^E and V ^NE , where subset V ^E includes all empty virtual nodes and subset V ^NE includes all non-empty virtual nodes.

In addition, empty virtual nodes are assigned keys and ranges that are never used for non-empty virtual nodes to distinguish them from non-empty virtual nodes. For example, assume that a real number between (-1, 0) is never used as a key for a data item or as a non-empty virtual node.
FIG. 1 shows a storage system configuration based on an overlay proposed as an example of the present invention. In the case of this example, all empty virtual nodes are arranged in adjacent areas. This area is called an empty virtual nodes pool (EVNP).
In FIG. 1, the drawing line width is changed so that the physical node to which the virtual node belongs can be distinguished. Virtual nodes having the same line width are stored in the same physical node. Each physical node includes a plurality of non-empty virtual nodes (circles) and empty virtual nodes (star polygons).

One method for realizing the object of the present invention is to design a load balancing algorithm for assigning data items to virtual nodes, so that any physical node Pi (i is from 1 to the number N of physical nodes). ) for, and is to manage the overall load on the data item in proportion to its capacity c _i. Formally, the subset V _{i of} virtual nodes belonging to the physical node Pi (∈V, V is the set of all virtual nodes) is the actual load for each virtual node so that the following equation 2 is minimized. Adjust. Here, the load of the virtual node v _j is assumed to be l _j . The capacity of the physical node can be arbitrary, but the capacity of the virtual node is a predetermined constant value. Here, Σ represents the sum of all the elements of the subscript.

The second term of the above formula can be regarded as the expected load of the physical node P _i . The basic idea of balancing the load between overloaded physical nodes and underloaded physical nodes is to move data from non-empty virtual nodes of overloaded physical nodes to empty virtual nodes of underloaded physical nodes Swap is performed.

However, if the load on the virtual node is arbitrary, the system can become very inefficient. Given a large number of virtual nodes that store only a few data items, moving data from an overloaded physical node to an underloaded physical node is a large number that moves through those few data items. It can be seen that one swap operation is required.
In addition, by storing only a few data items in a non-empty virtual node, the overlay network becomes inefficient use and wastes physical resources.

For these reasons, in the present invention, an allowable range is set for the load of the virtual node, and the load is always kept in an appropriate state. Specifically, the lower limit lb and the upper limit ub of the allowable range are introduced here. Therefore, although ub = 2 × lb + ε, ε (> 0) is a small real number.
The load on the virtual node v _i must always satisfy lb ≦ l _i <ub. Otherwise, an operation for adjusting the load described later is activated.
Given the range of virtual node loads, a practically convenient approximation of Equation 3 can be obtained as follows. The absolute value symbol represents the number of virtual nodes for the set, and the absolute value for the numerical value.

If | V ^NE | / | V | is μ, μ represents the ratio of the number of all non-empty virtual nodes to the number of all virtual nodes in the Chord # overlay network. For an arbitrary physical node P _i , the ratio of the number of non-empty virtual nodes to the number of all virtual nodes is μ _i .
Here, a threshold parameter λε (0, 1) is introduced. If μ _i is greater than μ (1 + λ), it is interpreted as an overload, and if μ _i is less than μ (1-λ), it is interpreted as an underload.
An underloaded physical node does not need to do anything, but waits for a request from an overloaded physical node.

Whether the physical node is underloaded, normal loaded or overloaded can be determined by comparing μ _i and μ. Before estimating μ, here we first introduce a method for calculating the total number m of virtual nodes. This is necessary to estimate μ. At this time, m is calculated by using the feature of Chord #.

Assume that any physical node contains the virtual node v _j . Further, it is assumed that v _j has an overlay node v _k of level-0 on the left side. The physical node is v _j and v _k . Send a key inquiry. This query is treated as a normal query and the intermediate overlay node forwards it exactly according to the Chord # protocol. The only difference between this query and a regular query is that it is in the query message and has an embedded segment that records which overlay level each intermediate node forwards the query to. The set in the segment is denoted LS. After the inquiry has been transferred to v _k, v _k is to simply transfer it to the v _j. After receiving the query, v _j calculates m according to the following equation:

An example is shown in FIG. Assume that virtual node 74 calculates m. Virtual node 74 sends a query for key 79, which is the key of the overlay node on the left at level 0. The query is forwarded to the next -0.5 node at level 3. The -0.5 node forwards the query to the adjacent node 92 at its level 2, and the node 92 forwards the query to the adjacent node 85 at its level 1. Since node 79 is level 0 and right next to node 85, the query is forwarded to level 0. In this example, LS = 3, 2, ^{1, 0} , and 16 with m = 2 ³ +2 ² +2 ¹ +2 ⁰ +1.

Once m is known, the physical node can estimate μ independently in a sampling-based manner. (1) Specifically, a physical node randomly selects a virtual node, adds a predetermined TTL (Time To Live) (at least O (log m)), and a sample-request message Is sent out. (2) All nodes that have received the packet randomly select an adjacent link from the finger table, forward the packet, and reduce TTL. (3) Every overlay node along the path will randomly pick the next link, forward it, and reduce TTL. (4) The node that has run out of TTL returns a sample.
In this way, the physical node sending the message can obtain a sampling of virtual nodes according to a uniform distribution.

The reason is as follows.
Since a topology such as Chord # is an expander, TTL in Chord # converges to a uniform distribution for a random walk of O (log m).
It is well known that if sampling follows a uniform distribution, estimating μ becomes a basic population ratio evaluation problem. A sampling set of virtual nodes is S (| S | = s), and a Boolean variable a _i is introduced as follows.

If the evaluation value of μ is μ ^ (^ is above μ),

The expected value is as follows.

Also, it is clear from this that μ で あ is an evaluation with no bias of μ.

When the physical node P _i is found to be overloaded, it starts the swap process. FIG. 2 shows the system before and after swapping.
In particular,
(A) First, a non-empty virtual node v _j is randomly selected.
(B) Then, the random number K in (−1, 0) is generated, and the Ch # overlay network is searched for K from the virtual node v _j . According to the Chord # search algorithm, if there is an empty virtual node with key K, that node responds to v _j . If there is no empty virtual node with key K, the empty virtual node with the key closest to key K replies to v _j .
(C) It is assumed that the empty virtual node to be returned is v _k . If v _k is in a normal node (a load that is neither underload nor overload) or an underloaded physical node, virtual node v _j passes all data items to virtual node v _k . Otherwise, the virtual node v _j generates a new Kε (−1, 0) and searches for K again.
(D) This process is repeated until virtual node v _j finds an empty virtual node from a normal or underloaded physical node.
(E) In addition to data transmission, the virtual node v _j and the virtual node v _k exchange information on the key, the assigned range, and adjacent nodes.
(F) Exchange the position in the overlay network with the information exchanged at the end of the swap operation.

Next, adjustment of the load of a non-empty virtual node will be described.
The key to understanding the load balancing framework is to keep the load of non-empty virtual nodes in the range [lb, ub). For this purpose, three operations are introduced: split, merge, and redistribute.
The split operation is triggered when the load l _j reaches the upper limit ub due to data input for the virtual node v _j . In order to perform the split operation, the virtual node v _j must first find an empty virtual node.
v If the same physical node _j an empty virtual node v _k, v _j sends a split request to the v _k. Otherwise, v _j generates a random number (denoted K) in (−1, 0). Search for K in the Chord # overlay network.
Regardless of whether there is an empty virtual node with key K, one of the empty virtual nodes replies to v _j . If the returned virtual node is v _k , v _j allocates half of its load (ie lb + ε / 2) to v _k .
In practice, v _j can move a larger key data item or a smaller key data item to v _k , but without loss of versatility, here v _j is a larger key data item. It can be moved to v _k .
In addition to the data item transmission, v _{j also} sends the right neighbor information to v _{k so} that it is level 0 in the Chord # overlay skip list and its right neighbor is v _k .

Since v _k is now a non-empty virtual node, it leaves the original position in the overlay network and rejoins the overlay network right next to v _j , using the lower bound of the data item's key as the key.

The merge and redistribution of other operations is triggered when l _j is less than lb due to data deletion. Whether merging and redistribution is triggered depends on the neighboring nodes on the two level 0 overlay networks of v _j .
(B) When either neighbor node, for example v _k , satisfies the condition l _j + l _k <ub, a merge operation is triggered and v _j absorbs all data items from v _k . Upon receiving this result, v _j becomes normal and v _k becomes empty. First, v _k leaves the overlay network, generates a random key during the interval (−1, 0), and joins the overlay network again. The new location on the overlay network is the EVNP.
(B) On the other hand, when the virtual nodes on both sides of v _{j in} the level 0 overlay network have the number of data items equal to or greater than ub−l _j , v _j indicates which of the lb−l _j data items. The next node can be requested to deliver until it reaches the lower limit lb. This is called redistribution. After redistribution, both two virtual nodes become normal load virtual nodes.
With split, merge, and redistribution, any non-empty virtual node load can be kept between lb and ub. All three of these operations are local collaborations and are performed without global information.

  First, the overlay network example in the present embodiment is configured as follows. Each physical node is partitioned so that a plurality of virtual nodes having the same capacity can be set, and a respective assigned range is assigned to each virtual node. Based on the assigned range, a P2P network capable of range search is configured with these virtual nodes. Specifically, each virtual node is connected to an adjacent node. Each virtual node is also provided with some long link to speed up the search. Not all virtual nodes are used to store data items. Some virtual nodes are used for data storage, and other virtual nodes are empty virtual nodes. Non-empty virtual nodes are assigned keys that are not used as data items. For example, when the data item is always positive, a value between the intervals (−1, 0) is assigned to an empty virtual node.

Each physical node has a plurality of non-empty virtual nodes and empty virtual nodes. At this time, the load balance between the overloaded physical node and the underloaded physical node can be readjusted as follows.
For example, assume that an overloaded physical node has a non-empty virtual node and an underloaded physical node has an empty virtual node. In this case, all the load is transferred from the non-empty virtual node to the empty virtual node. Then, the positional relationship is exchanged on the overlay network. This operation is equivalent to a swap.

  The local load adjustment is performed by three operations of split, merge, and redistribute. At this time, the upper limit ub and the lower limit lb of the data item are introduced to the non-empty virtual node. Also, ub is slightly more than twice lb, for example, 2.08. These ub and lb are indexes serving as triggers for load adjustment.

As shown in FIG. 3A, when the data item reaches ub by data insertion, for example, the split splits the virtual node into two (split). Specifically, in the same physical node, an empty virtual node heading and half of the data are moved to that direction. Now the empty virtual node is no longer empty. Then, the position is changed on the overlay network. If an empty virtual node is not found in the same physical node, a virtual node having a negative random number K as a key is searched as described above, and the virtual node responding to the search is searched for data as described above. Transfer half.
In the merge, as shown in FIG. 3B, when the sum of data items of two adjacent virtual nodes in the overlay network is less than ub, one virtual node absorbs data items of other virtual nodes. Then, the virtual node that has become empty leaves its position and rejoins the empty virtual node pool.
Further, as shown in FIG. 3C, the redistribution has both individual data items of two adjacent nodes smaller than ub, but when the sum of the data items is larger than ub, there are many data items. Move data items from one to the few.
With these three operations, data items can be kept between lb and ub in any virtual node.

  FIG. 4 is a diagram illustrating an example of a load equalization operation. In this example, the load is moved from the overload node to the underload node.

  FIG. 2 shows the swap operation from the viewpoint of the overlay network. In FIG. 2, it is assumed that the physical node A is overloaded and the physical node B is underloaded. Data is moved from the virtual node 11 in the physical node A to one of the empty virtual nodes in the physical node B. After the data movement, the adjacent node information, the search key, and the position in the overlay network are exchanged between the nodes.

In order to evaluate the performance of the present invention, a simulator was developed in Java (registered trademark). For comparison, in addition to the method of the present invention, LoReC (LOad REbalancing for distributed file systems in Clouds, Non-Patent Document 1) has a reputation in a uniform environment and (B) a heterogeneous environment. Was implemented.
In the computer simulation by the simulator, the load distribution effect, data movement cost, message transmission cost and load distribution speed were evaluated.

(A) Simulation in a uniform environment The first set of results, obtained from a uniform environment.
In a uniform environment, 1000 physical nodes were used with the same capacity of 1000. Each physical node contains 20 virtual nodes. The simulation was performed in the following two types of scenarios.
(A) In the static scenario, load distribution operations were performed assuming three patterns of uneven initial load distribution.
During the load balancing operation, no data insertion and deletion has occurred.
In the static scenario, splits, merges, and redistributions rarely occurred and could be concentrated on swaps.
(B) In dynamic scenarios, we continued to reduce (also increase) the load. During the data agitation, all load balancing operations were triggered, allowing us to evaluate the actual environment.

FIG. 6 shows three patterns of how the initial load distribution is biased. It represents CDF (Cumulative Distribution Function) with respect to load. The smallest load in a physical node is 200, and the largest load is 800. In the load B, most of the nodes are light loads, and only a small part of the nodes are heavily loaded. In the load C, most nodes are in a state where a great load is applied, and only a small part is lightly loaded. The position of the load A is between the load B and the load C. 7 (a), 7 (b) and 7 (c) show a comparison of the load distribution effect for each load.
In the method of the present invention, there are few overloaded nodes while there are a few underloaded nodes.
This is an advantage of the present invention in that the conventional method (LoReC) has several overloaded and underloaded nodes. The main reason for this difference is the difference in the use of REORDER. As with conventional methods, with REORDER, if a lightly loaded node rescues an overloaded node, all its data items must be moved to the next node before that. However, after receiving a data item from a lightly loaded node, a REORDER operation is meaningless if the adjacent lightly loaded node becomes more heavily loaded than the overloaded node to be assisted. In addition, no further load distribution is performed in this case.

  FIG. 8A shows a comparison of data movement costs. FIG. 8B shows a comparison of message transmission costs. FIG. 8C shows a comparison of load distribution rates. It is assumed that the method and LoReC of the present invention are performed periodically. Therefore, these speeds are compared with the number of load balancing operations. A smaller number of load balancing operations seems to be faster. From these figures, it can be seen that the method of the present invention can save significant data movement costs and messaging costs, and can finish faster than LoReC.

  In addition to the static scenario, simulations with mixed data were also performed. Assume that there are 600 data items in a load balanced range searchable system. Then, the data items were deleted from all nodes in a biased manner, but more data items were deleted from fewer nodes and fewer data items were deleted from more nodes. The deletion of data in each trial follows the function shown in FIG. FIG. 10A shows a comparison of accumulated data movement costs, and FIG. 10B shows a comparison of accumulated message transmission costs. FIG. 10C shows a comparison of load distribution rates.

As in the static scenario, the speed was compared with the number of load balancing operations. In LoReC, the number of “REORDER” was counted, and in the method of the present invention, the number of swaps was counted. Splits, merges, and redistributions are not counted. This is because they are triggered by load fluctuations.
Furthermore, the processing time of the above three operations seems to be much shorter than the swap period. Similar to the results in the static scenario, the method of the present invention shows a significant improvement over LoReC for data deletion.
Similarly, a simulation for data insertion was performed. Each node has 200 data items, and the range searchable system is set to load balance. Then, the data items were inserted into all nodes in a biased manner. The data insertion for each trial is a method according to FIG. FIGS. 11A, 11B, and 11C show the same results as in the case of data deletion.

(B) Simulation in a heterogeneous environment Based on virtual nodes, the method of the present invention supports an essentially heterogeneous environment and shows little difference from working in a uniform environment. For this reason, in order to simplify the description, only some results are shown below.
In the simulation, it is assumed that the capacity of the physical node is a Zipf distribution. The maximum and minimum capacity are 5000 and 500, respectively. The load to capacity ratio was assumed to follow another zip distribution between [0.2, 0.8]. FIG. 12 (a) shows the load distribution effect, and FIG. 12 (b) shows the corresponding data movement cost.
From these figures, it can be seen that the data movement cost is only 1% of the data movement cost by LoReC in order to obtain the same load distribution effect as LoReC according to the present invention.

The following examples can be given as specific examples of the present invention. First, when accumulating data, it is connected via various sensors that are connected to the Internet and arranged at distributed locations, such as sensors of IoT devices installed in each home, mobile networks or networks that are intermittently connected from vehicles. The measured data is stored in a cloud storage that can be searched by the present invention from the sensor that has been selected. As the accumulation of data proceeds, the load on each physical node increases. However, this increase is often not uniform, and therefore the load on each physical node is distributed using the load distribution method of the present invention. As a result, the utilization rate of storage resources can be increased. Further, since the search can be performed using, for example, CHORD #, the search can be performed efficiently.
Therefore, it is apparent that the present invention can be easily used in combination with any system as long as there is a system capable of storing data in a cloud storage capable of range search.

Claims (6)

A method for distributing the load of the physical nodes in a cloud storage that can be searched in a range configured on a network to which a plurality of physical nodes including a plurality of storages and a processor and a memory combined with the storages are connected. There,
The range searchable cloud storage is formed on an overlay network in which a virtual storage having a common capacity value by the storage, a virtual processor by a processor to which the virtual storage is associated, and a plurality of virtual nodes having a memory as a constituent element are connected. And
In data storage, key-value type data is stored in cloud storage that can be searched in the above range,
In the search, the virtual node is searched for a predetermined key value,
A lower limit for load distribution and an upper limit that becomes the capacity of the virtual node at a predetermined multiple of the lower limit are set in the data storage amount of each virtual node
(1) When adding new data to the first virtual node, if the amount of added data is greater than or equal to the upper limit, an empty virtual node selected from the searchable cloud storage for the added data amount As the second virtual node, the data of half the upper limit is distributed from the first virtual node to the second virtual node, and the arrangement of the virtual nodes on the overlay network is updated in a new order by this distribution. A load balancing method in cloud storage that allows range search. Regarding the first physical node and the second physical node selected from the physical nodes constituting the cloud storage,
The ratio of the number of non-empty virtual nodes of the physical node to the total number of virtual nodes is μ, and using a predetermined threshold parameter λ (∈ (0, 1)),
(1) and the virtual node number ratio mu ₁ belonging to the first physical node number of nodes is not empty in the virtual node belonging to the first physical node, the number of virtual nodes is not empty against the above number of virtual nodes which belong to the second physical node For the ratio μ ₂ , when μ ₁ (1 + λ) is larger than μ and μ ₂ (1−λ) is smaller than μ,
(2) Swap the retained data from the non-empty virtual node belonging to the first physical node to the empty virtual node belonging to the second physical node,
(3) The range distribution searchable cloud storage load distribution method according to claim 1, wherein the arrangement of nodes on the overlay network is updated. The load distribution method in the range searchable cloud storage according to claim 1 or 2, wherein the search for the key value in the range searchable cloud storage is a search according to a code # algorithm. Configuring an empty virtual node pool in which the entire empty virtual nodes occupy a continuous sequence of the overlay network in the overlay network;
4. The load distribution method in a range searchable cloud storage according to claim 1, wherein the empty virtual node is selected from the empty virtual node pool. 5.   The storage in each of the physical nodes is obtained by dividing the storage, and the division is a division in which the number of areas of the same size is the largest. Load balancing method in cloud storage that can be searched in any range.   6. The load distribution method in cloud storage capable of range search according to claim 1, wherein the predetermined multiple is more than two and not more than 2.08 times.