CN105574153A - Transcript placement method based on file heat analysis and K-means - Google Patents

Abstract

The present invention provides a copy placement method based on file heat analysis and K-means. Firstly, the file access heat is calculated by analyzing the file access frequency within a given time. Utilize the access popularity of files, combined with the K-means algorithm, predict possible high-access popularity files in the next period, comprehensively consider various factors such as statistical cycle, file size, and working environment, and dynamically adjust the number and placement of file copies as needed Location. The invention can effectively reduce the average response time of file access and improve data service performance.

Description

A Copy Placement Method Based on File Heat Analysis and K-means

technical field

The invention belongs to the field of cloud computing, and specifically relates to a method for dynamically adjusting and placing copies of high-hot files in a cloud environment by using heat statistical analysis and K-means algorithm.

Background technique

With the development of society and the improvement of computer storage and data processing capabilities, the explosive growth of data has become an important feature of today's era. According to the estimate of data growth by International Data Corporation (IDC), by 2020 there will be 40ZB (1ZB=1.1805916207174113×10 ²¹ B) of data, which is equivalent to 5247GB per capita on the earth (http://datacenter.watchstor.com/ infra-143421.htm). Facing the ever-increasing mass of data, the subsequent storage and management of massive data has also received more and more attention.

In order to improve the reliability and access efficiency of the system, the commonly used copy technology copies data items into multiple copies and stores them on multiple nodes of the distributed file system respectively. Aiming at the different access requirements for data in various historical stages, people have proposed a variety of copy management strategies, mainly including master-slave, hierarchical, peer-to-peer computing (PeertoPeer, P2P) and graph-based.

Replica management strategies usually need to make decisions on the number of replicas and storage locations, and can be divided into static and dynamic according to the timing of making decisions. In 2001, IanForster and Kavitha Ranganathan proposed six replica creation strategies in the hierarchical network topology: no replica strategy, best customer strategy, waterfall strategy, common cache strategy, cache waterfall strategy, rapid expansion strategy (data grid Research and implementation of copy optimization strategy based on economic model in environment Li Lin.). These strategies can reduce access latency in most cases, but the waterfall strategy, caching waterfall strategy, and rapid expansion strategy are only applicable to data grids where data is stored on the top-level nodes, and the best client strategy and common cache strategy do not take into account Topological structure, data distribution, network bandwidth, node storage capacity and other characteristics (based on the two-layer dynamic copy creation strategy of the storage alliance - SADDERS Sun Haiyan, Wang Xiaodong, Zhou Bin, etc.), did not take into account the impact of file size and network bandwidth on access delay.

The invention calculates the access heat of the file according to the heat calculation formula by analyzing the access frequency of the file within the preset time period. Use the access popularity of files, combined with the K-means algorithm, to predict possible high-access popularity files in the next cycle (dynamic copy creation algorithm based on popularity analysis Rao Lei, Yang Fande, Li Xinming, Liu Dong.), and comprehensively consider the statistical cycle , file size, working environment and other factors, dynamically adjust the number and location of file copies.

Contents of the invention

The technical problem to be solved in the present invention is the copy placement problem in the distributed system or cloud computing platform. A copy placement method based on file heat analysis and K-means is proposed, and the maximum value is selected as the time period according to the execution time of the task. Calculate the access popularity of files within a time period. Utilize the access popularity of files, combined with the K-means algorithm, predict possible high-access popularity files in the next period, comprehensively consider various factors such as statistical cycle, file size, and working environment, and dynamically adjust the number and placement of file copies as needed Location. The invention can effectively reduce the average response time of file access and improve data service performance.

Technical solutions:

A copy placement method based on file heat analysis and K-means, comprising the following steps:

Step 1), according to the execution time of the task, select the minimum value as the time period of heat analysis, and analyze the access frequency of the file in this time period;

Step 2), according to the file access frequency obtained in step 1), calculate the access popularity value of the file;

Step 3), according to the file access heat value that step 2) obtains, obtains the information of the file of high heat value, by K-means algorithm, calculates and predicts the high heat file of next running cycle;

Step 4), according to the high-heat file information obtained in step 3), dynamically adjust the number of copies of the files and the placement location by comprehensively considering many factors such as file size, file quantity, file location, and working environment;

Further, a copy placement method based on file heat analysis and K-means of the present invention, step 1) according to the execution time of the task, select the maximum value as the time period of heat analysis, and analyze the access frequency of the file within this time period . The present invention uses a file access times counter and a statistics period timer. At initialization, the default number of file accesses is 1. In each statistical cycle, the counter is incremented by 1 each time the file is accessed, and the counter is decremented by 1 when the file is not accessed. If the number of visits is already 1, the counter will no longer perform decrement operation. If the file access timeout is not completed, the access counter is incremented by 1. The access frequency f _k =n/t of a file in the kth statistical period, where n is the number of times the file is accessed in the statistical period, and t is the sum of the duration of visits in the statistical period;

Further, in the method of copy placement based on file heat analysis and K-means of the present invention, step 2) uses the formula h _ij =α·F _j /(S _i +1) according to the file access frequency obtained in step 1) , calculate the access popularity value of file i at time j. In the formula, α is a constant used to normalize the data; F _j represents the influence of frequency on file access popularity, and S _i represents the influence of file size on file access popularity. in,

Further, in a copy placement method based on file heat analysis and K-means of the present invention, step 3) obtains information on files with high heat values according to the file access heat value obtained in step 2), and selects k files as initialization center, calculates the distance of each file to the center file, and assigns each file to the closest cluster. The foregoing process is repeatedly calculated according to the existing cluster relationship until the termination condition is met. Termination conditions include:

(1) No (or a minimum number) of documents are reassigned to different clusters;

(2) No (or minimum number) cluster centers change;

(3) The sum of squared errors (SSE) is locally minimized, Where x represents the file, m _j represents the cluster center of cluster C _j , and dist(x, m _j ) represents the distance between file x and cluster center m _j ;

Further, a copy placement method based on file heat analysis and K-means of the present invention, step 4) according to the clustering information obtained in step 3), according to the access heat of each cluster center, the file size and the number of files are comprehensively considered , File location, working environment and many other factors dynamically adjust the number and location of file copies, increase the number of copies appropriately for clusters with high popularity, and appropriately reduce the number of copies for clusters with low popularity.

Beneficial effect

The present invention aims at copy placement in a distributed system or a cloud computing platform, and conducts a comprehensive analysis in combination with file access heat and K-means algorithm, which helps to realize reasonable placement of copies in a system with high access volume. This method makes up for the previous method of placing copies simply through file heat analysis, and simply places copies based on the heat of files in this statistical cycle; at the same time, in order to improve the response time of access in subsequent statistical cycles, the K-means clustering algorithm is adopted , predict possible high-heat files in the next cycle, and adjust file copies in advance. The combination of the two aspects can not only improve the rationality of the copy, reduce the response time, but also reduce IO congestion.

Description of drawings

Figure 1 is a flowchart of a copy placement method based on file heat analysis and K-means.

detailed description

Below in conjunction with accompanying drawing, the implementation of technical scheme is described in further detail:

A copy placement method based on file heat analysis and K-means according to the present invention will be further described in detail in conjunction with the flow chart and the implementation case.

This implementation case uses file heat analysis and K-means algorithm to adjust and place copies in distributed systems or cloud environments. As shown in Figure 1, this method includes the following steps:

Step 1), according to the execution time of the task, select the minimum value as the time period of heat analysis, and analyze the access frequency of the file in this time period;

Step 101), in a distributed system or cloud environment, the execution time of different tasks is different. When performing file heat analysis, when a task is completed, a copy adjustment can be performed, and the last task execution will be generated in a timely manner. information to be used in subsequent applications. The execution time of the task can be obtained by simulation or experience value. ;

Step 102), according to the formula f _k =n/t, within a preset time period, calculate the access frequency of the acquired file.

Step 2), calculate the access popularity value of the file according to the file access frequency obtained in the previous step;

Step 201), after obtaining the file access frequency, the impact of the file access frequency on its popularity can be calculated, which is determined by the file's access frequency and weight in the last 1 statistical period.

Step 202), calculate the impact of file size on file access heat, determined by the file size s _i and the data block size in the distributed system;

Step 203), according to the formula h _ij =α·F _j /(S _i +1), combined with the response values obtained in the previous two steps, and performing normalization processing, the access popularity value of file i at time j can be calculated ,.

Step 3), according to the file access heat value obtained in the previous step, obtain the information of the file with high heat value, and calculate and predict the high heat file in the next operation cycle through the K-means algorithm;

Step 301), according to the calculation result of the previous step, the files with high heat value can be obtained, so as to obtain the information of these files from the system.

Step 302), select K files from the high-heat files as the center files, calculate the distances from all files to each center file, and assign each file to the nearest cluster center according to the calculation results;

Step 303), repeating the previous step until the termination condition is met;

Step 4), according to the clustering information obtained in the previous step, according to the visit popularity of each clustering center, and comprehensively considering factors such as file size, file quantity, and working environment, adjust the number of copies of each file and the placement location. The clusters corresponding to the cluster centers with high access heat will increase the number of copies appropriately; the clusters with low access heat will reduce the number of copies accordingly.

Claims (5)

1. A copy placement method based on file heat analysis and K-means, characterized in that, comprising the following steps: Step 1), according to the execution time of the task, select the minimum value as the time period of heat analysis, and analyze the access frequency of the file in this time period; Step 2), according to the file access frequency obtained in step 1), calculate the access popularity value of the file; Step 3), according to the file access heat value that step 2) obtains, obtains the information of the file of high heat value, by K-means algorithm, calculates and predicts the high heat file of next running cycle; In step 4), according to the information of high-profile files obtained in step 3), the number of copies of the files and the placement locations are dynamically adjusted in consideration of many factors such as file size, number of files, file locations, and working environment. 2. The method according to claim 1, wherein, in step 1), a file access times counter and a statistical cycle timer are used; during initialization, the default file access times is 1, and in each statistical cycle, the file is accessed every time The visited counter is incremented by 1, and the counter is decremented by 1 if it is not visited; if the number of visits is already 1, the counter will no longer perform the decrement operation. If the file access timeout is not completed, the access counter is increased by 1; if the file access frequency f _k =n/t in the k statistical cycle, where n is the number of times the file is accessed in the statistical cycle, t is the statistical cycle The sum of the duration of the visit. 3. The method according to claim 1, characterized in that, in step 2) according to the file access frequency obtained in step 1), use the formula h _ij =α·F _j /(S _i +1) to calculate the file i in The access heat value at time j; in the formula, α is a constant used to normalize the data; F _j represents the impact of frequency on file access heat, and S _i represents the impact of file size on file access heat; among them, 4. The method according to claim 1, characterized in that, step 3) obtains the information of files with high heat value according to the file access heat value obtained in step 2), selects k files as the initialization center, and calculates each file The distance to the central file, assigning each file to the closest cluster. Repeat the calculation of the preceding process according to the existing cluster relationship until the termination condition is met; the termination condition includes: (1) No (or a minimum number) of documents are reassigned to different clusters; (2) No (or minimum number) cluster centers change; (3) The sum of squared errors (SSE) is locally minimized, Where x represents the file, m _j represents the cluster center of cluster C _j , and dist(x, m _j ) represents the distance between file x and cluster center m _j . 5. The method according to claim 1, characterized in that, according to the clustering information obtained in step 3) in step 4), according to the visit popularity of each clustering center, comprehensively consider file size, file quantity, file location, work Many factors such as the environment dynamically adjust the number and location of file copies. High-heat clusters increase the number of copies appropriately, and low-heat clusters appropriately reduce the number of copies.