CN107357659A - Towards the group technology and querying method of Storm successive ranges inquiry GSLB - Google Patents

Abstract

The invention discloses a kind of group technology and querying method towards Storm successive ranges inquiry GSLB, successive range under grid index is inquired about, incorporation range query semantics, stored using Redis and be responsible for updating mobile object quantity in grid, using the mobile object quantity in query context as assessment cost, range query task is assigned to corresponding group according to Query Cost, it is distributed to downstream worker range query task poll in same group, poll counter device is safeguarded by Redis, realize the grouping strategy of global packet poll, system load balancing degree can be effectively improved according to grouping strategy, so as to improve the resource utilization of system.

Description

Grouping method and query for global load balancing of Storm continuous range query method

technical field

The invention relates to the technical field of communication networks, in particular to a grouping method and a query method for querying global load balancing in a continuous range of Storm.

Background technique

With the diversification of positioning methods, the popularization of mobile terminals and the completion of communication infrastructure, mobile applications represented by Location Based Service (LBS) have entered the era of mobile big data. In the mobile big data environment, the data scale is larger, the transmission speed is faster, and the diversity is more extensive, showing distinct streaming characteristics. Traditional LBS technology faces many new challenges. Continuous range query based on location services has the characteristics of high concurrency and low latency, so more efficient processing capabilities for mobile big data with streaming characteristics are required. Data processing in the era of mobile big data requires not only a computing platform with stronger and more flexible storage and processing capabilities, but also processing and optimization technologies based on the computing platform.

However, there is a well-known "short board theory" in distributed systems. If a system has a load imbalance problem, the node with the largest load will often become the bottleneck and short board that affects the overall performance of the system. Due to factors such as economic development and geographical location, the population density is different in different regions, and correspondingly, the geographical distribution of mobile objects corresponding to LBS applications is also uneven. As a distributed stream processing system, ApacheStorm itself does not provide an effective load balancing mechanism, and Storm's own grouping strategies such as Shuffle Grouping and FieldsGrouping are grouping strategies designed based on a general idea without considering the processing The semantics contained in the task, such as continuous range query has time and space semantics such as query range, moving object density, range overlap, etc., moving objects are not evenly distributed geographically, so the cost of range query is also different, which can easily lead to The load between computing units that process range queries is unbalanced and the performance is degraded. Therefore, Storm's own grouping strategy cannot meet the needs of system load balancing. This is undoubtedly a challenge to the performance of the entire system. For cloud computing environments There are relatively few load balancing studies on online stream processing, and traditional and batch-oriented load balancing techniques cannot be directly applied to stream processing systems.

Contents of the invention

In view of the above problems, the object of the present invention is to provide a grouping method and a query method for querying global load balancing in the continuous range of Storm.

In order to solve the existing problems in the background technology, the technical solution of the present invention is:

A grouping method for global load balancing of Storm continuous range queries, including:

1), obtaining range query information, the range query information includes query range and grid overlap;

2), according to the query range and grid overlap, the range query is divided into multiple sub-queries, and the query range of each sub-query only overlaps with one grid;

3), read the density of moving objects in the grid overlapping with the subquery query range stored in Redis, and calculate the cost of the subquery according to the query range of the subquery and the density of moving objects in the grid;

4), according to the query cost, map the subquery to the corresponding group, and then obtain the value of the group counter from the polling counter table;

5) Take the modulus of the number of downstream workers according to the value of the counter to obtain the target worker id, and send the target worker id to the downstream.

In the step 2), according to the query range and grid overlap, the range query is divided into multiple sub-queries specifically including:

2.1. Set the number of groups, and calculate the first grouping granularity according to the number of groups;

2.2. Set the number of secondary groups, and calculate the granularity of the secondary group according to the granularity of the first group and the number of secondary groups. The calculation formula is:

minGrain=grain/minGroup

Wherein, the minGrain is the granularity of the secondary grouping, the grain is the granularity of the first grouping, and minGroup is the quantity of the secondary grouping.

The cost formula of the subquery is:

C(q)=r×d

Wherein, the r is the size of the query range of the sub-query, and d is the density of moving objects in the grid.

The specific steps of mapping subqueries to corresponding groups according to the query cost are as follows:

4.1. Set the query cost threshold range, determine the query cost and the size of the query cost threshold range, if the query cost is greater than or less than the query cost threshold range, directly calculate the group according to the query cost and the first grouping granularity;

4.2. For other range sub-queries, because there are too many of them, they are grouped at a finer granularity, and the group is calculated according to the query cost, the granularity of the first grouping and the granularity of the second grouping.

The polling calculator is stored in Redis.

A query method for global load balancing for continuous range query in Storm, including:

1), obtain the range query information, the range query information includes the query range and grid overlap; the range query is divided into corresponding sub-queries according to the query range and grid overlap, and the sub-query is divided into corresponding sub-queries according to the global grouping round The grouping strategy of the query is distributed to the downstream target worker;

2) Execute the subquery of the range query, and use the timestamp of the range query as the key, and distribute it to downstream workers according to the grouping strategy of Fields Grouping, so as to ensure that the subqueries belonging to the same range query are distributed to the same worker;

3) Combine the query results of the subqueries belonging to the same range query to obtain the final query result, and finally distribute the final query result to the downstream Bolt in the grouping mode of Shuffle Grouping;

4) Publish the range query results to Kafka and subscribe to them by the client.

The distributing the subquery to the downstream target worker according to the grouping strategy of global grouping polling specifically includes:

1.1. Obtain range query information, the range query information includes query range and grid overlap;

1.2. According to the query range and grid overlap, the range query is divided into multiple subqueries, and the query range of each subquery only overlaps with one grid;

1.3. Read the density of moving objects stored in Redis in the grid overlapping with the subquery query range, and calculate the cost of the subquery according to the query range of the subquery and the density of moving objects in the grid;

1.4. According to the query cost, map the subquery to the corresponding group, and then obtain the value of the group counter from the polling counter table;

1.5. Take the modulus of the number of downstream workers according to the value of the counter, obtain the target worker id, and send the target worker id to the downstream.

Compared with prior art, the beneficial effects of the present invention are:

The present invention provides a grouping method for global load balancing of Storm's continuous range query. For the continuous range query under the grid index, combined with the range query semantics, Redis is used to store and update the number of moving objects in the grid. The number of moving objects is used as the evaluation cost, and the range query tasks are divided into corresponding groups according to the query cost. The range query tasks in the same group are distributed to the downstream workers in a round-robin manner. The polling counter is maintained by Redis to realize global group polling. The grouping strategy can effectively improve the system load balance according to the grouping strategy, thereby improving the resource utilization rate of the system.

The present invention provides a query method for global load balancing of continuous range query in Storm, aiming at the problem that the load balance degree of the service system is not high when processing range query, combined with the semantics of range query, a grouping strategy of global group polling is proposed, Combined with the system characteristics of Storm, it is applied to the service system, and the continuous range query tasks are grouped according to this strategy, so that the load difference between workers processing range query tasks is as small as possible, and the load balance of the service system is improved. .

Description of drawings

Fig. 1 is the flow chart of the grouping method of the present invention's graph-oriented Storm continuous range query global load balancing;

Fig. 2 is a block diagram of the grouping policy execution process of the global grouping polling of the present invention;

Fig. 3 is a process block diagram of the query method of the present invention for querying global load balancing in the continuous range of Storm.

detailed description

The present invention will be described in detail below in conjunction with the accompanying drawings.

The unbalanced load of the continuous range query of the mobile object continuous query service system in the cloud environment directly affects the resource utilization and performance of the system. Therefore, it is necessary to customize the grouping strategy according to the characteristics of the continuous range query to ensure the load balance of the system. . The present invention proposes a global grouping polling grouping strategy (Global GroupingShuffle Grouping, GGSG) for the continuous range query under the grid index, combined with the range query semantics, using Redis to store and update the number of moving objects in the grid, and query The number of moving objects in the range is used as the evaluation cost, and the range query tasks are divided into corresponding groups according to the query cost. The range query tasks in the same group are distributed to the downstream workers in a round-robin manner. The polling counter is maintained by Redis to realize the global grouping round query grouping strategy.

As shown in Figures 1 and 2, the present invention provides a grouping method for querying global load balancing in the continuous range of Storm, including:

1), obtaining range query information, the range query information includes query range and grid overlap;

2), according to the query range and grid overlap, the range query is divided into multiple sub-queries, and the query range of each sub-query only overlaps with one grid;

According to the query range and the amount of grid overlap, the range query is divided into multiple subqueries, including:

2.1. Set the number of groups, and calculate the first grouping granularity according to the number of groups;

2.2. Set the number of secondary groups, and calculate the granularity of the secondary group according to the granularity of the first group and the number of secondary groups. The calculation formula is:

minGrain=grain/minGroup

Wherein, the minGrain is the granularity of the secondary grouping, the grain is the granularity of the first grouping, and minGroup is the quantity of the secondary grouping.

1) The larger the number of groups, the smaller the grouping granularity, and the smaller the cost difference between the range queries contained in each group. In this case, when the total amount of range queries can reach a certain number, the range queries contained in each group The number is sufficient. Each group distributes range query tasks according to the polling grouping strategy, which can ensure that the load difference between workers is small, and the system has a high degree of load balance. When the total amount of range queries does not reach a certain number Sometimes, the number of range queries contained in each group is small, and the number of range queries distributed to each worker may vary greatly during the polling grouping process, which may easily lead to low load balance of the system;

2) The smaller the number of groups, the larger the grouping granularity, and the larger the cost difference between the range queries contained in each group. When the number of groups is 1, it is equivalent to Shuffle Grouping. To sum up, simply having too many or too few groups is not an appropriate choice, but selecting the appropriate group according to the total amount of continuous range queries or the speed at which continuous range queries arrive can better improve the load balance of the system Spend.

3), read the density of moving objects stored in Redis overlapping with the subquery query range, and calculate the cost of the subquery according to the query range of the subquery and the density of the moving objects in the grid; the cost formula of the subquery for:

C(q)=r×d

Wherein, the r is the size of the query range of the sub-query, and d is the density of moving objects in the grid;

4) According to the query cost, the subquery is mapped to the corresponding group, and then the value of the group counter is obtained from the polling counter table; the polling calculator is stored in Redis.

The specific steps of mapping subqueries to corresponding groups according to the query cost are as follows:

4.1. Set the query cost threshold range, determine the query cost and the size of the query cost threshold range, if the query cost is greater than or less than the query cost threshold range, directly calculate the group according to the query cost and the first grouping granularity;

4.2. For other range sub-queries, because there are too many of them, they are grouped at a finer granularity, and the group is calculated according to the query cost, the granularity of the first grouping and the granularity of the second grouping.

For the mapping function, since the query cost conforms to the normal distribution, the number of range subquery tasks with relatively high cost and relatively small cost is small, so for the range subquery with relatively large cost and relatively small cost, the group is directly calculated according to its query cost, and for other Due to the large number of range subqueries, they can be grouped into finer-grained groups, which can make the downstream load more balanced.

5) Take the modulus of the number of downstream workers according to the value of the counter to obtain the target worker id, and send the target worker id to the downstream.

Finally, the operation worker_j=(counter_i++) mod n is performed on the counters of the group to obtain the downstream target worker of the subquery. Polling counters are stored in Redis and atomic update operations can be performed on the counter's value.

As shown in Figure 2, the global polling group grouping strategy (GGSG) is used between GetCoveredCellsBolt and CellScanBolt, and the specific execution process of GGSG.

The present invention also provides a query method for querying global load balancing facing the continuous range of Storm, as shown in Figure 3, including:

1), obtain the range query information, the range query information includes the query range and grid overlap; the range query is divided into corresponding sub-queries according to the query range and grid overlap, and the sub-query is divided into corresponding sub-queries according to the global grouping round The grouping strategy (GGSG) of the query is distributed to the downstream target worker;

2) Execute the subquery of the range query, and use the timestamp of the range query as the key, and distribute it to downstream workers according to the grouping strategy of Fields Grouping, so as to ensure that the subqueries belonging to the same range query are distributed to the same worker;

3) Combine the query results of the subqueries belonging to the same range query to obtain the final query result, and finally distribute the final query result to the downstream Bolt in the grouping mode of Shuffle Grouping;

4) Publish the range query results to Kafka and subscribe to them by the client.

The distributing the subquery to the downstream target worker according to the grouping strategy of global grouping polling specifically includes:

1.1. Obtain range query information, the range query information includes query range and grid overlap;

1.2. According to the query range and grid overlap, the range query is divided into multiple subqueries, and the query range of each subquery only overlaps with one grid;

1.3. Read the density of moving objects stored in Redis in the grid overlapping with the subquery query range, and calculate the cost of the subquery according to the query range of the subquery and the density of moving objects in the grid;

1.4. According to the query cost, map the subquery to the corresponding group, and then obtain the value of the group counter from the polling counter table;

1.5. Take the modulus of the number of downstream workers according to the value of the counter, obtain the target worker id, and send the target worker id to the downstream.

First, GetCoveredCellsBolt divides an incoming range query into multiple sub-queries according to its overlap with the grid. The size of the query range of the sub-query is represented by r, and the query range of each sub-query only overlaps with one grid. Then read the density d of moving objects in the grid that overlaps the query scope of the subquery stored in Redis, calculate the cost of the subquery with formula 3.1, and map the subquery to the corresponding group according to the query cost. For the mapping function, since the query cost conforms to the normal distribution, the number of range subquery tasks with relatively high cost and relatively small cost is small, so for the range subquery with relatively large cost and relatively small cost, the group is directly calculated according to its query cost, and for other Due to the large number of range subqueries, they can be grouped into finer-grained groups, which can make the downstream load more balanced.

And finally perform an operation on the group's counter:

worker_j = (counter_i++) mod n,

That is, the downstream target worker of the subquery. Polling counters are stored in Redis and atomic update operations can be performed on the counter's value.

Finally, experiments show that the grouping strategy of global group polling has a better balance than Fields Grouping and ShuffleGrouping, which can effectively improve system resource utilization and system throughput.

For those skilled in the art, it is obvious that the above-mentioned specific embodiments are only preferred solutions of the present invention, so those skilled in the art may make improvements and changes to some parts of the present invention, which still reflect the present invention The principle of the present invention is still the object of the present invention, and all belong to the protection scope of the present invention.

Claims (7)

1. A kind of 1. group technology towards Storm successive ranges inquiry GSLB, it is characterised in that including：

   1) range query information, is obtained, the range query information includes query context and mesh overlay amount；

   2), according to query context and mesh overlay amount, range query is divided into multiple subqueries, the query context of each subquery Only and a mesh overlay；

   3) density of mobile object in the grid overlapping with subquery query context stored in Redis, is read, and according to subquery Query context and grid in mobile object density, calculate the cost of subquery；

   4), according to Query Cost, subquery is mapped to corresponding group, then obtains this group of counter from poll counter device table Value；

   5), the quantity modulus according to the value of counter to downstream worker, obtains target worker id, and by target worker Id is issued to downstream.
2. 2. according to claim 1 inquire about the overall situation towards Storm successive ranges according to the grouping strategy of global packet poll The group technology of load balancing, it is characterised in that according to query context and mesh overlay amount in the step 2), by range query It is divided into multiple subqueries to specifically include：

   2.1st, number of packet is set, first time Packet granularity is calculated according to number of packet；

   2.2nd, secondary number of packet is set, the granularity of secondary packet is calculated according to first time Packet granularity and secondary number of packet, Calculation formula is：

   MinGrain=grain/minGroup

   Wherein, the minGrain is secondary Packet granularity, and grain is first time Packet granularity, and minGroup is secondary packet Quantity.
3. 3. the group technology according to claim 1 towards Storm successive ranges inquiry GSLB, its feature exists In the cost formula of the subquery is：

   C (q)=r × d

   Wherein, the r is the query context size of subquery, and d is the density of mobile object in grid.
4. 4. the group technology according to claim 1 towards Storm successive ranges inquiry GSLB, its feature exists In, it is described according to Query Cost, subquery is mapped to concretely comprising the following steps of organizing accordingly：

   4.1st, Query Cost threshold range is set, the size of Query Cost and Query Cost threshold range is judged, if Query Cost More than or less than Query Cost threshold range, then place group is directly calculated according to Query Cost and first time Packet granularity；

   4.2nd, for other scope subqueries, because its quantity is excessive, so being done more fine-grained packet, then basis is looked into Ask group where cost, first time Packet granularity and second of Packet granularity calculate.
5. 5. the group technology according to claim 1 towards Storm successive ranges inquiry GSLB, its feature exists In the poll calculator is stored in Redis.
6. A kind of 6. querying method towards Storm successive ranges inquiry GSLB, it is characterised in that including：

   1) range query information, is obtained, the range query information includes query context and mesh overlay amount；Range query is pressed According to query context and mesh overlay situation, corresponding subquery is divided into, point by the subquery according to global packet poll Group policy is distributed to downstream targets worker；

   2) subquery of range query, is performed, and using the timestamp of range query as key, according to FieldsGrouping point Group policy is distributed to downstream worker, it is ensured that the subquery for belonging to same range query is distributed to same worker；

   3) Query Result that, will belong to the subquery of same range query merges, and obtains final Query Result, finally will most Whole Query Result is distributed to downstream Bolt with Shuffle Grouping packet mode；

   4) range query result, is published to Kafka, by client subscription.
7. 7. the querying method according to claim 6 towards Storm successive ranges inquiry GSLB, its feature exists In described the subquery is distributed into downstream targets worker according to the grouping strategy of global packet poll to specifically include：

   1.1st, range query information is obtained, the range query information includes query context and mesh overlay amount；

   1.2nd, according to query context and mesh overlay amount, range query is divided into multiple subqueries, the inquiry model of each subquery Enclose only and a mesh overlay；

   1.3rd, the density of mobile object in the grid overlapping with subquery query context stored in Redis is read, and is looked into according to son The density of mobile object in the query context and grid of inquiry, calculate the cost of subquery；

   1.4th, according to Query Cost, subquery is mapped to corresponding group, group counting is then obtained from poll counter device table The value of device；

   1.5th, the quantity modulus according to the value of counter to downstream worker, obtains target worker id, and by target worker Id is issued to downstream.