CN104899250A - Graph calculation scaling method based on separation of graph structure information and data information - Google Patents
Graph calculation scaling method based on separation of graph structure information and data information Download PDFInfo
- Publication number
- CN104899250A CN104899250A CN201510229191.3A CN201510229191A CN104899250A CN 104899250 A CN104899250 A CN 104899250A CN 201510229191 A CN201510229191 A CN 201510229191A CN 104899250 A CN104899250 A CN 104899250A
- Authority
- CN
- China
- Prior art keywords
- server
- moving
- graph structure
- information
- data message
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/10—File systems; File servers
- G06F16/18—File system types
- G06F16/185—Hierarchical storage management [HSM] systems, e.g. file migration or policies thereof
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/10—File systems; File servers
- G06F16/18—File system types
- G06F16/182—Distributed file systems
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Data Mining & Analysis (AREA)
- Databases & Information Systems (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Information Transfer Between Computers (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
- Computer And Data Communications (AREA)
Abstract
The present invention provides a graph calculation scaling method based on separation of graph structure information and data information. The method is characterized by comprising: step 1: separately migrating graph structure information and data information; and step 2: performing optimizing and allocating for local sensitivity and load balancing. According to the present invention, the method of separately migrating graph structure information and data information is used, and the optimizing and allocating mechanism for local sensitivity and load balancing is used, so as to implementing scaling of a graph calculation system. Compared with the existing support for system-level flexible scaling (aided by technologies such as virtual machine migration), the present invention can reduce loss in performance of an upper-layer application service, and shorten the overall migration time and the out-of-service time during flexible migration of a calculation system. The invention increases the utilization rate of cloud computing cluster resources and the availability of upper-layer application services, and promotes deployment of key computing services, which require high throughput, in a cloud computing data center, thus achieving considerable social benefits and economic benefits.
Description
Technical field
The present invention relates to distributed computing technology field.Specifically, relate to the figure be separated with data message based on graph structure and calculate telescopic method
Background technology
Elastic calculation is speciality important in cloud platform, is directly connected to the execution efficiency that cloud platform is applied.Existing solution is based on system-level elastic calculation, and the support of application layer mainly contains the system of Map Reduce model, as Hadoop.The performance of computing application migration depends primarily on migration velocity, out of service time and recovers to calculate the performance of system later.Do not consider the demand that figure computing application is flexible in the elastic telescopic technology of current main-stream, the flexible loss caused system performance causing figure to calculate is larger.
Therefore, the feature of how to stretch for figure computing application, appropriate design migration strategy and scheme, reduce the Internet Transmission in telescopic process, schemes the locality calculated, become those skilled in the art's technical barrier urgently to be resolved hurrily in fact after raising transmission.
Summary of the invention
For defect of the prior art, the object of the invention is to, utilize the understanding to upper strata computing application, by graph structure and data message separated migrates, and locality is responsive and the optimization distribution mechanism of load balancing, shorten transit time and break period, promote the performance of flexible rear system.
Calculate telescopic method according to a kind of figure be separated with data message based on graph structure provided by the invention to comprise the steps:
Step 1: separated migrates is carried out to graph structure information and date information;
Step 2: locality optimization that is responsive and load balancing distributes.
Preferably, described step 1, comprises the steps:
Described graph structure information is separated with the described data message in computation process;
By target machine by described graph structure information constant in distributed file system direct access computation process, and by the described data message of source machine by producing in Internet Transmission computation process.
Preferably, described step 1, comprises the steps:
Be loaded into figure; In the process being loaded into figure, divide and build subgraph, the dividing mode of record figure, completing after subgraph builds and division information is stored to distributed file system;
When receiving migration instruction, the subgraph structure belonging to server of moving out directly is loaded into by distributed file system by the server of moving into as target machine, and merges with original subgraph on server of moving into; Server of moving out as source machine sends about the computing mode of subgraph of moving out to server of moving into;
Server of moving into receives computing mode, and to moving out, server sends acknowledgement information, server closing application process of moving out; Server of moving into is loaded into computing mode, recovers to calculate.
Preferably, described step 2 comprises the steps:
In the process being loaded into figure, according to the described locality of calculating data and the load balancing of system, server is divided, and division feature is extracted to the division result of server;
When receiving migration instruction, to move into the locality score of server to difference according to described division feature calculation subgraph structural transfer of moving out, the server selecting load the lightest according to the loading condition of server in multiple servers that the locality score selected is forward, as moving into server, performs migration;
After server of moving into completes the reconstruction of figure, recalculate the division feature on server.
Compared with prior art, the present invention has following beneficial effect:
1, the present invention mainly proposes a kind of elastic telescopic method utilizing the flexible strategy of optimization and algorithm realization figure to calculate.The method is by utilizing the optimization distribution mechanism of graph structure and data message separated migrates and locality sensitivity and load balancing, shorten bulk migration time and out of service time, and optimize the system performance after having stretched, promote data locality and the load balancing of having moved rear system.
2, the elasticity convergent-divergent of the relative existing system level of the present invention (as by technology such as virtual machine (vm) migrations) is supported, can reduce upper layer application service loss of energy, shortens the bulk migration time in computing system elastic moval process and out of service time.Promote the availability of cloud computing cluster resource utilization factor and upper layer application service, promotion has the deployment of crucial calculation services in cloud computation data center of high flux demand, and then can bring considerable social benefit and economic benefit.
3, the information that the problem that in telescopic process, transinformation is large is mainly derived from graph structure in figure calculating sends, and figure calculates the structure depending on figure, but the structure of figure does not change in computation process.Therefore the present invention proposes the method by the structural information of figure and data message separated migrates, reduces the Internet Transmission in transition process, shortens the bulk migration time.
What 4, figure had the greatest impact to calculated performance in calculating is the locality of data and the equally loaded of system.The feature that figure calculates is circulation, repeats, and good data locality can greatly reduce Internet Transmission, improves calculated performance.The present invention proposes the optimization distribution mechanism of the responsive and load balancing of locality, and according to moving into and the Data distribution8 of server of moving out in transition process, selection reasonably moves scheme.
Accompanying drawing explanation
By reading the detailed description done non-limiting example with reference to the following drawings, other features, objects and advantages of the present invention will become more obvious:
Fig. 1 is that the figure be separated with data message based on graph structure calculates dynamic elasticity and moves process flow diagram.
Fig. 2 be the figure be separated with data message based on graph structure calculate dynamic elasticity move after system state.
Embodiment
Below in conjunction with specific embodiment, the present invention is described in detail.Following examples will contribute to those skilled in the art and understand the present invention further, but not limit the present invention in any form.It should be pointed out that to those skilled in the art, without departing from the inventive concept of the premise, some changes and improvements can also be made.These all belong to protection scope of the present invention.
The present invention adopts the method for graph structure and data message separated migrates, and locality is responsive and the optimization distribution mechanism of load balancing, realizes the flexible of figure computing system.
Below will describe figure provided by the invention by concrete exemplifying embodiment and calculate flexible technology.
Fig. 1 is that the figure be separated with data message based on graph structure calculates dynamic elasticity and moves process flow diagram (to expand)
Step 0, system is loaded into raw data, divides and builds subgraph, after completing structure, division information being stored to distributed file system.
Step 1, system receives migration instruction (moving to server B of moving into, C by server A of moving out), A sends data message (as shown in 1a) to B, C simultaneously, and B, C read figure information (as shown in 1b) by distributed file system simultaneously.
Step 2, server B of moving into, C complete reception, and server A of moving out application is closed, and B, C rebuild graph structure and data message.
The state of final system is as Fig. 2.
Further particularly, based on the algorithm of the locality of figure and the optimization distribution mechanism of load balancing
In step 0, subgraph A that every station server processes according to it produces locality score evaluation function, and the input parameter of this function is a subgraph B, and this function exports the evaluation of the subgraph A that to move into subgraph B, and the score that locality is good is high.
In step 1, produce the scoring of every station server to subgraph respectively, choose 2 that score is the highest when server needs to move out, according to its load, the station server selecting load little is migration target.
In sum, the figure be separated with data message based on graph structure that the present invention proposes calculates flexible technology, adopt the method for graph structure and data message separated migrates, and locality is responsive and the optimization distribution mechanism of load balancing, the transit time in transition process and out of service time can be shortened, promote data locality and the load balancing of having moved rear system.
Wherein, described graph structure information is separated with the described data message in computation process, by target machine by described graph structure information constant in distributed file system direct access computation process, and by the described data message of source machine by producing in Internet Transmission computation process; Avoid transmitting the data do not changed in computation process, reducing the data to needing in transition process to transmit, shortening contraction time.
Above specific embodiments of the invention are described.It is to be appreciated that the present invention is not limited to above-mentioned particular implementation, those skilled in the art can make a variety of changes within the scope of the claims or revise, and this does not affect flesh and blood of the present invention.
Claims (4)
1. the figure be separated with data message based on graph structure calculates a telescopic method, it is characterized in that, comprises the steps:
Step 1: separated migrates is carried out to graph structure information and date information;
Step 2: locality optimization that is responsive and load balancing distributes.
2. the figure be separated with data message based on graph structure according to claim 1 calculates telescopic method, it is characterized in that, described step 1, comprises the steps:
Described graph structure information is separated with the described data message in computation process;
By target machine by described graph structure information constant in distributed file system direct access computation process, and by the described data message of source machine by producing in Internet Transmission computation process.
3. the figure be separated with data message based on graph structure according to claim 1 calculates telescopic method, it is characterized in that, described step 1, comprises the steps:
Be loaded into figure; In the process being loaded into figure, divide and build subgraph, the dividing mode of record figure, completing after subgraph builds and division information is stored to distributed file system;
When receiving migration instruction, the subgraph structure belonging to server of moving out directly is loaded into by distributed file system by the server of moving into as target machine, and merges with original subgraph on server of moving into; Server of moving out as source machine sends about the computing mode of subgraph of moving out to server of moving into;
Server of moving into receives computing mode, and to moving out, server sends acknowledgement information, server closing application process of moving out; Server of moving into is loaded into computing mode, recovers to calculate.
4. the figure be separated with data message based on graph structure according to claim 3 calculates telescopic method, it is characterized in that, described step 2 comprises the steps:
In the process being loaded into figure, according to the described locality of calculating data and the load balancing of system, server is divided, and division feature is extracted to the division result of server;
When receiving migration instruction, to move into the locality score of server to difference according to described division feature calculation subgraph structural transfer of moving out, the server selecting load the lightest according to the loading condition of server in multiple servers that the locality score selected is forward, as moving into server, performs migration;
After server of moving into completes the reconstruction of figure, recalculate the division feature on server.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201510229191.3A CN104899250B (en) | 2015-05-07 | 2015-05-07 | Telescopic method is calculated based on the figure that graph structure is detached with data information |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201510229191.3A CN104899250B (en) | 2015-05-07 | 2015-05-07 | Telescopic method is calculated based on the figure that graph structure is detached with data information |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN104899250A true CN104899250A (en) | 2015-09-09 |
| CN104899250B CN104899250B (en) | 2018-07-03 |
Family
ID=54031913
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201510229191.3A Active CN104899250B (en) | 2015-05-07 | 2015-05-07 | Telescopic method is calculated based on the figure that graph structure is detached with data information |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN104899250B (en) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN106294757A (en) * | 2016-08-11 | 2017-01-04 | 上海交通大学 | A kind of distributed data base divided based on hypergraph and clustered partition method thereof |
| CN107480254A (en) * | 2017-08-14 | 2017-12-15 | 上海交通大学 | Suitable for the online load-balancing method of distributed memory database |
Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101692239A (en) * | 2009-10-19 | 2010-04-07 | 浙江大学 | Method for distributing metadata of distributed type file system |
| US20120102550A1 (en) * | 2010-10-22 | 2012-04-26 | Newman David M | Wireless Device Network Association |
| CN103793525A (en) * | 2014-02-21 | 2014-05-14 | 江苏唯实科技有限公司 | MapReduce model graph node authority value calculation method based on local iteration |
-
2015
- 2015-05-07 CN CN201510229191.3A patent/CN104899250B/en active Active
Patent Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101692239A (en) * | 2009-10-19 | 2010-04-07 | 浙江大学 | Method for distributing metadata of distributed type file system |
| US20120102550A1 (en) * | 2010-10-22 | 2012-04-26 | Newman David M | Wireless Device Network Association |
| CN103793525A (en) * | 2014-02-21 | 2014-05-14 | 江苏唯实科技有限公司 | MapReduce model graph node authority value calculation method based on local iteration |
Non-Patent Citations (3)
| Title |
|---|
| CHEN R 等: "Bipartite-Oriented Distributed Graph Partitioning for Big Learning", 《JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY》 * |
| 丁鑫 等: "分布式图计算框架混合计算模式的研究", 《小型微型计算机系统》 * |
| 于戈 等: "云计算环境下的大规模图数据处理技术", 《计算机学报》 * |
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN106294757A (en) * | 2016-08-11 | 2017-01-04 | 上海交通大学 | A kind of distributed data base divided based on hypergraph and clustered partition method thereof |
| CN106294757B (en) * | 2016-08-11 | 2019-09-10 | 上海交通大学 | A kind of distributed data base and its clustered partition method divided based on hypergraph |
| CN107480254A (en) * | 2017-08-14 | 2017-12-15 | 上海交通大学 | Suitable for the online load-balancing method of distributed memory database |
| CN107480254B (en) * | 2017-08-14 | 2021-05-11 | 上海交通大学 | Online load balancing method suitable for distributed memory database |
Also Published As
| Publication number | Publication date |
|---|---|
| CN104899250B (en) | 2018-07-03 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US9053067B2 (en) | Distributed data scalable adaptive map-reduce framework | |
| CN109710374A (en) | The VM migration strategy of task unloading expense is minimized under mobile edge calculations environment | |
| CN103188521B (en) | Transcoding distribution method and device, code-transferring method and equipment | |
| CN103942308A (en) | Method and device for detecting large-scale social network communities | |
| CN103856548B (en) | Dynamic resource scheduling method and dynamic resource scheduling device | |
| US20190377606A1 (en) | Smart accelerator allocation and reclamation for deep learning jobs in a computing cluster | |
| CN105205154A (en) | Data migration method and device | |
| CN110419050A (en) | A kind of computer system of distributed machines study | |
| WO2023087893A1 (en) | Object processing method and apparatus, computer device, storage medium and program product | |
| CN105468439A (en) | Adaptive parallel algorithm for traversing neighbors in fixed radius under CPU-GPU (Central Processing Unit-Graphic Processing Unit) heterogeneous framework | |
| CN112153145A (en) | Method and device for unloading calculation tasks facing Internet of vehicles in 5G edge environment | |
| CN105808341A (en) | Method, apparatus and system for scheduling resources | |
| CN103150122A (en) | Method and device for managing disk cache space | |
| CN104468759A (en) | Method and device for achieving application migration in PaaS platform | |
| CN106775470B (en) | Data storage method and system | |
| Liang et al. | A Survey on Spatio-temporal Big Data Analytics Ecosystem: Resource Management, Processing Platform, and Applications | |
| CN104899250A (en) | Graph calculation scaling method based on separation of graph structure information and data information | |
| CN108512817A (en) | More video code conversion dispatching methods and device | |
| CN102427420B (en) | Virtual network mapping method and device based on graph pattern matching | |
| CN113014649B (en) | Cloud Internet of things load balancing method, device and equipment based on deep learning | |
| CN104866375B (en) | A kind of method and device for migrating virtual machine | |
| CN105426384A (en) | Proposed target location generation method and apparatus | |
| CN104468379B (en) | Virtual Hadoop clustered nodes system of selection and device based on most short logical reach | |
| CN105608046A (en) | Multi-core processor architecture based on MapReduce programming model | |
| KR101563808B1 (en) | System and method for providing distributed virtual cloud using mobile grid |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |