CN108416054A - Dynamic HDFS copy number calculating methods based on file access temperature - Google Patents

Abstract

The present invention provides a kind of dynamic HDFS copy number calculating methods based on file access temperature, is related to data analysis technique field.Dynamic HDFS copy number calculating methods based on file access temperature, the rule that the access temperature of hot spot file changes over time is obtained by improved Markovian model type analysis first, and according to the calculation formula of file access temperature, the access temperature of file is predicted.Then queueing theory algorithm is used, the calculation formula of copy number is provided, dynamic adjusts the copy number of hot spot file.Dynamic HDFS copy number calculating methods provided by the invention based on file access temperature, solve the problems, such as the access bottleneck to hot spot file, improve the efficiency of service of cluster.

Description

Calculation method of dynamic HDFS replica number based on file access heat

technical field

The invention relates to the technical field of data analysis, in particular to a method for calculating the number of dynamic HDFS copies based on file access heat.

Background technique

With the development of modern Internet technology and the advancement of science and technology, data has penetrated into various industries and fields of social development with the characteristics of large capacity, diversity, high speed and authenticity. With the increasing trend of massive data, reasonable management of data and resources and ensuring the reliability of data have become a key issue in the field of cloud computing.

The distributed system infrastructure Hadoop developed by the Apache Foundation implements a distributed file system (Hadoop Distributed File System), referred to as HDFS. HDFS has the characteristics of high fault tolerance and is designed to be deployed on low-cost (low-cost) hardware; and it provides high throughput (high throughput) to access application data, suitable for those with large data sets (large data set) applications. HDFS relaxes the requirements of (relax) POSIX, and can access (streaming access) data in the file system in the form of streams. In the copy management mechanism of HDFS, the cluster adopts the copy management mechanism that saves 3 copies for each data block of the file by default, but it cannot meet the access requirements of different users for different files. When the value is large, the default number of copies of data blocks cannot respond to a large number of access requests, resulting in bottlenecks in hot file access. At present, the relevant copy management methods have gradually shifted from static copy creation strategy to dynamic copy creation strategy, so that when the external environment changes, the overall performance of the cluster can be kept unchanged or can provide services to clients efficiently. However, there are still some factors that are not considered in the dynamic replica creation strategy but have an important impact on the working efficiency of the cluster.

In the prior art, the document "Research on Efficient Multi-Replica Management in Cloud Environment" proposes a dynamic replica creation method for the cost-effectiveness guarantee of large-scale cloud storage systems, which comprehensively considers the relationship between the number of replicas and availability, That is, the number of copies is adjusted under the premise of meeting the availability of the cloud storage system, but the relationship between the file access heat and the number of copies is not considered. The document "An Elastic Replication Management System for HDFS" proposes an active/standby storage model to achieve flexible management of HDFS copies. It uses a complex transaction engine to identify the amount of data accessed in real time, dynamically adjusts the number of copies, and introduces correction Erasure codes manage the number of copies. Although this system effectively improves the performance of HDFS, its implementation process is complicated, and the complexity is high when identifying real-time access data.

Contents of the invention

Aiming at the defects of the prior art, the present invention provides a method for calculating the number of dynamic HDFS copies based on file access heat, so as to realize the calculation of the number of dynamic copies.

A method for calculating the number of dynamic HDFS copies based on file access heat, comprising the following steps:

Step 1. According to the file access log table on the distributed file system HDFS and according to the calculation formula of file access heat, the access heat of each file in the statistical period is calculated, and the files are sorted in descending order according to the sum of the file access heat within the statistical period. Select the top 20% files in the sorted list as hot files, construct the hot file-access popularity sequence as the sequence to be predicted, and predict the access popularity;

The formula for calculating the file access popularity is as follows:

Among them, Hot(f) represents the access heat of file f, AF(f)=N/T represents the access frequency of file f, and N represents the number of visits of file f in the statistical period T, Indicates the data block size of file f, f _size indicates the size of file f, means not greater than the largest integer of That is, the number of data blocks of the file f is obtained;

Step 2. Use the hierarchical clustering algorithm to divide the state space of the hot file-access heat sequence. The specific method is:

The hotspot files-access heat sequence constitutes a data set with a length of N. The objects in the data set represent the access heat of hot files at different times. The process of hierarchical clustering of the hot file-access heat data set is as follows:

(1) Treat each object in the data set as a class, and obtain N classes in total, and the distance between classes is the median value of the square of the distance between each data point in the two classes;

(2) Merge the two closest classes into one class, reducing the total number of classes by one;

(3) Recalculate the distance between the new class and other classes;

(4) Repeat steps (2)-(3) until all data objects in the data set are finally merged into one class;

Based on the above steps, the clustering tree of the hotspot file-access heat sequence is obtained, and the state space divided by Markov is defined according to the clustering tree structure;

Step 3. Carry out the Markov property test on the hotspot file-access heat sequence that has divided the state space. If the Markov property is satisfied, use the sequence as the input sequence of the improved Markov model, otherwise the sequence cannot be used by the improved Markov model. model to handle;

Step 4. Use the hotspot file-access heat sequence that satisfies the Markov property as the input sequence of the improved Markov model, predict the access heat of the hot file at the next moment, and write the predicted access heat into the hot file-access heat In the database table, the specific method is:

Step 4.1: Based on the divided state space, calculate the one-step state transition probability matrix P according to the file-access heat sequence;

Step 4.2: Set the state corresponding to the current file access popularity value as the initial state distribution, denoted as p(0), and calculate the state probability distribution at the next moment p(1)=p(0) according to the one-step state transition probability matrix P )P;

Step 4.3: Take the state with the maximum distribution probability in the state probability distribution p(1) at the next moment as the state at the next moment, and take the sum of the standard deviation of the hotspot file-access heat sequence and the average value of the target state space as the next Predicted access popularity value at a moment;

Step 4.4: Remove the first value of the input sequence, and add the newly predicted access popularity value as the last value of the next prediction sequence to the sequence to be predicted, repeat the above steps, and predict the access popularity of hot files at the next moment;

Step 5. Model the copy access request based on the M/M/r single-queue multi-server queue model, and on this basis, set the throughput of the copy on the node to determine the number of copies. The specific method is:

Step 5.1: Obtain the average access request rate λ of the copy of the specified hot file in the next statistical period by querying the hot file-access heat database table statistics;

Step 5.2: Set the CPU utilization threshold U of the server where the replica is located. According to the CPU utility law, the CPU utilization is equal to the request arrival rate divided by the service rate. Using the following formula, the request service rate μ of a single server is calculated as:

Step 5.3: Set the total throughput constraint of the cluster to Q, based on the Little formula in queuing theory, the service residence time is equal to the service rate multiplied The reciprocal of the throughput is equal to the reciprocal of the service residence time; in a homogeneous cluster environment, the service rate of the server where multiple copies are located is the same, so the number of copies r is calculated by the following two formulas:

It can be seen from the above technical solution that the beneficial effect of the present invention is that the method for calculating the number of dynamic HDFS copies based on file access heat provided by the present invention can improve the accuracy of prediction by predicting the file access heat based on the improved Markov model. sex. At the same time, based on the calculation method of the number of copies based on queuing theory, considering the law of hot file access over time, the number of copies is dynamically adjusted to cope with the occurrence of high concurrent access to hot files. Using the method of queuing theory, the storage copy on the node is regarded as a service resource. By analyzing the request rate and response rate of hot file copies, the goal is to ensure the throughput and reliability of the cluster. The number of copies can be obtained through the copy calculation formula, as Subsequent dynamic adjustment of the number of copies as a foreshadowing.

Description of drawings

Fig. 1 is the flow chart of the method for calculating the number of dynamic HDFS copies based on file access heat provided by the embodiment of the present invention;

Fig. 2 is a schematic diagram of the prediction process of using the improved Markov model to predict the access popularity of hot files at the next moment provided by the embodiment of the present invention;

Fig. 3 is a comparison diagram between the predicted value of the Markov model provided by the embodiment of the present invention, the predicted value of the improved Markov model, and the real value;

FIG. 4 is a comparison diagram between the number of replicas calculated based on queuing theory and the number of replicas calculated based on actual replica throughput provided by an embodiment of the present invention.

Detailed ways

The specific implementation manners of the present invention will be further described in detail below in conjunction with the accompanying drawings and embodiments. The following examples are used to illustrate the present invention, but are not intended to limit the scope of the present invention.

In this embodiment, 3 racks are built, and 4 virtual machines are configured on each rack, and another three physical machines will be built, which are the namenode node in the active state and the namenode node in the standby state for Prevent namenode single point of failure. The third physical machine is used as a computing node to obtain file access logs, predict file access popularity, and calculate the number of copies. The configuration of the cluster is Hadoop version Hadoop-2.2.0, memory 32G, CPU Intel(R) Core(TM) i3-2120 CPU@3.30GHz, operating system CentOS-6.7, hard disk 2T, development language JAVA, R, Matlab.

The method for calculating the number of dynamic HDFS copies based on file access heat, as shown in Figure 1, includes the following steps:

Step 1. According to the file access log table on the distributed file system HDFS and according to the calculation formula of access heat, the access heat of each file in the statistical period is calculated, and the files are sorted in descending order according to the sum of the file access heat within the statistical period, and select The top 20% files in the sorting list are used as hot files, and the hot file-access popularity sequence is used as the sequence to be predicted to predict the access popularity;

The formula for calculating the file access popularity is as follows:

Among them, Hot(f) represents the access heat of file f, AF(f)=N/T represents the access frequency of file f, and N represents the number of visits of file f in the statistical period T, Indicates the data block size of file f, f _size indicates the size of file f, means not greater than the largest integer of That is, the number of data blocks of the file f is obtained.

In this embodiment, with 5 days as a statistical period, the access frequency of the flu.txt file within 5 periods is counted. According to the file access log table, the access heat information of flu.txt in the statistical period is calculated according to the calculation formula of access heat, as shown in Table 1.

Table 1 Access popularity information table of flu.txt file

interview time 2017-08-01 2017-08-02 2017-08-03 2017-08-04 2017-08-05 Access popularity 262 486 632 300 570 interview time 2017-08-06 … … 2017-10-02 … Access popularity 401 … … 382 …

Step 2. Use the hierarchical clustering algorithm to divide the state space of the hot file-access heat sequence. The specific method is:

The hotspot files-access heat sequence constitutes a data set with a length of N. The objects in the data set represent the access heat of hot files at different times. The process of hierarchical clustering of the hot file-access heat data set is as follows:

(1) Treat each object in the data set as a class, and obtain N classes in total, and the distance between classes is the median value of the square of the distance between each data point in the two classes;

(2) Merge the two closest classes into one class, reducing the total number of classes by one;

(3) Recalculate the distance between the new class and other classes;

(4) Repeat steps (2)-(3) until all data objects in the data set are finally merged into one class;

Based on the above steps, the clustering tree of the hotspot file-access heat sequence is obtained, and the state space divided by Markov is defined according to the clustering tree structure.

In this embodiment, the hierarchical clustering method is used to divide the spatial state of the historical access heat, the historical data is divided into five spatial states, and the data sets are marked with A, B, C, D and E.

Step 3. Carry out the Markov property test on the hotspot file-access heat sequence that has divided the state space. If the Markov property is satisfied, use the sequence as the input sequence of the improved Markov model, otherwise the sequence cannot be used by the improved Markov model. model to handle;

The specific method of Markov test is as follows:

For n possible state index sequence values X _n ={x ₁ , x ₂ ,...,x _n }, the value obtained by dividing the sum of the jth column of the transition frequency matrix by the sum of each row and each column, is called the marginal probability, as shown in the following formula:

Among them, f _ij represents the frequency in the index sequence X _n = {x ₁ , x ₂ , ..., x _n } from state i to state j after one step transfer, i, j∈E;

then statistic Take the ^χ2 distribution with (n-1) ² degrees of freedom as the limiting distribution, where,

Given a significance level α, if there is Then this sequence X _n conforms to the Markov property, otherwise the sequence cannot be processed by the Markov model.

In this embodiment, the one-step frequency transfer matrix f _ij and the probability transfer matrix p _ij shown in the following formula can be obtained by R language processing, as well as the marginal probability matrix p _.j shown in Table 2.

Table 2 Marginal probability table

state 1 2 3 4 5 _p.j 0.17021277 0.42553191 0.17021277 0.08510638 0.14893617

Statistics are calculated from the above values Get the χ ² statistics calculation table shown in Table 3.

Table 3 Calculation table of χ ² statistics

In the present embodiment, the significance level α=0.1, obtains the quantile according to the statistics calculation table of χ ² Among them, n=5. Therefore, the historical access heat of the file satisfies the Markov property, and the Markov model can be used to predict the file access heat.

Step 4. Use the hotspot file-access heat sequence that satisfies the Markov property as the input sequence of the improved Markov model, predict the access heat of the hot file at the next moment, and write the predicted access heat into the hot file-access heat In the database table, as shown in Figure 2, the specific method is:

Step 4.1: Based on the divided state space, calculate the one-step state transition probability matrix P according to the file-access heat sequence;

Step 4.2: Set the state corresponding to the current file access popularity value as the initial state distribution, denoted as p(0), and calculate the state probability distribution at the next moment p(1)=p(0) according to the one-step state transition probability matrix P )P;

Step 4.3: Take the state with the maximum distribution probability in the state probability distribution p(1) at the next moment as the state at the next moment, and take the sum of the standard deviation of the hotspot file-access heat sequence and the average value of the target state space as the next Predicted access popularity value at a moment;

Step 4.4: Remove the first value of the input sequence, and add the newly predicted access popularity value as the last value of the next prediction sequence to the sequence to be predicted, repeat the above steps, and predict the access popularity of hotspot files at the next moment.

In this embodiment, in order to verify the prediction accuracy of this method, the improved and unimproved Markov models were used to compare the flu.txt access popularity in five cycles. The comparison chart between the predicted value of the Markov model, the predicted value of the improved Markov model and the real value is shown in Figure 3. It can be seen from the figure that when predicting the visit popularity value at the next moment of the first period, since the visit popularity sequence is the same, the deviation between the visit popularity obtained by the improved and unimproved Markov models and the actual visit popularity value is the same , and there is not much difference between the visit popularity value predicted by the two methods and the actual value. However, when predicting the popularity of visits in the future, the improved Markov model adopts the continuously updated sequence to be predicted, so that the predicted visit popularity has little deviation from the actual one, while the unimproved Markov model, due to the Markov Due to the ergodicity and balanced distribution characteristics of the husband model itself, with the increase of the forecast frequency, the predicted result deviates greatly from the actual one. The results show that the access heat value predicted by the improved Markov model is relatively close to the actual value, and it also has a better prediction effect on the access trend of hot files.

Step 5. Model the copy access request based on the M/M/r single-queue multi-server queue model, and on this basis, set the throughput of the copy on the node to determine the number of copies. The specific method is:

Step 5.1: Obtain the average access request rate λ of the copy of the specified hot file in the next statistical period by querying the hot file-access heat database table statistics;

Step 5.2: Set the CPU utilization threshold U of the server where the replica is located. According to the CPU utility law, the CPU utilization is equal to the request arrival rate divided by the service rate. Thus, use the following formula to calculate the request service rate u of a single server:

Step 5.3: Set the total throughput constraint of the cluster to Q, based on the Little formula in queuing theory, the service residence time is equal to the service rate multiplied The reciprocal of the throughput is equal to the reciprocal of the service residence time; in a homogeneous cluster environment, the service rate of the server where multiple copies are located is the same, so the number of copies r is calculated by the following two formulas:

In this embodiment, after the access heat of the hot file is predicted by the improved Markov model, according to the access heat of the hot file, the CPU utilization threshold of the node is set to 0.5, and the throughput of the node copy is set to 100/s, then The average daily throughput is 100*11h*3600=4 million for 11 hours of access. The number of copies is calculated based on queuing theory, and compared with the number of copies calculated by the actual copy throughput. The comparison diagram As shown in Figure 4. It can be seen from the figure that considering the request access rate and response rate of the copy, the method of calculating the number of copies can adjust the number of copies according to the trend of access popularity. In the first cycle, the access popularity of hot files shows a downward trend. At this time , the number of copies obtained based on queuing theory is less than the actual number of copies. In the subsequent cycle time, the number of copies is dynamically adjusted considering the trend of hot file access, and is closer to the number of copies obtained by the actual throughput calculation. The effectiveness of this method was verified.

Finally, it should be noted that: the above embodiments are only used to illustrate the technical solutions of the present invention, rather than to limit them; although the present invention has been described in detail with reference to the foregoing embodiments, those of ordinary skill in the art should understand that: it can still be Modifications are made to the technical solutions described in the foregoing embodiments, or equivalent replacements are made to some or all of the technical features; these modifications or replacements do not make the essence of the corresponding technical solutions depart from the scope defined by the claims of the present invention.

Claims (5)

1. A method for calculating the number of dynamic HDFS copies based on file access heat, characterized in that: comprise the following steps: Step 1. According to the file access log table on the distributed file system HDFS and according to the calculation formula of file access heat, the access heat of each file in the statistical period is calculated, and the files are sorted in descending order according to the sum of the file access heat within the statistical period. Select the top 20% files in the sorted list as hot files, construct the hot file-access popularity sequence as the sequence to be predicted, and predict the access popularity; Step 2, using a hierarchical clustering algorithm to divide the state space of the hot file-access heat sequence; Step 3. Carry out the Markov property test on the hotspot file-access heat sequence that has divided the state space. If the Markov property is satisfied, use the sequence as the input sequence of the improved Markov model, otherwise the sequence cannot be used by the improved Markov model. model to handle; Step 4. Use the hotspot file-access heat sequence that satisfies the Markov property as the input sequence of the improved Markov model, predict the access heat of the hot file at the next moment, and write the predicted access heat into the hot file-access heat in the database table; Step 5: Model the copy access request based on the M/M/r single-queue multi-server queue model, and on this basis set the throughput of the copy on the node to determine the number of copies. 2. the method for calculating the number of dynamic HDFS copies based on file access heat according to claim 1, characterized in that: the calculation formula of file access heat described in step 1 is as follows: Among them, Hot(f) represents the access heat of file f, AF(f)=N/T represents the access frequency of file f, and N represents the number of visits of file f in the statistical period T, Indicates the data block size of file f, f _size indicates the size of file f, means not greater than the largest integer of That is, the number of data blocks of the file f is obtained. 3. the method for calculating the number of dynamic HDFS copies based on file access heat according to claim 1, is characterized in that: the concrete method of described step 2 is: The hotspot files-access heat sequence constitutes a data set with a length of N. The objects in the data set represent the access heat of hot files at different times. The process of hierarchical clustering of the hot file-access heat data set is as follows: (1) Treat each object in the data set as a class, and obtain N classes in total, and the distance between classes is the median value of the square of the distance between each data point in the two classes; (2) Merge the two closest classes into one class, reducing the total number of classes by one; (3) Recalculate the distance between the new class and other classes; (4) Repeat steps (2)-(3) until finally all data objects in the data set are merged into one class; Based on the above steps, the clustering tree of the hotspot file-access heat sequence is obtained, and the state space divided by Markov is defined according to the clustering tree structure. 4. the method for calculating the number of dynamic HDFS copies based on file access heat according to claim 1, is characterized in that: the concrete method of described step 4 is: Step 4.1: Based on the divided state space, calculate the one-step state transition probability matrix P according to the file-access heat sequence; Step 4.2: Set the state corresponding to the current file access popularity value as the initial state distribution, denoted as p(0), and calculate the state probability distribution at the next moment p(1)=p(0) according to the one-step state transition probability matrix P )P; Step 4.3: Take the state with the maximum distribution probability in the state probability distribution p(1) at the next moment as the state at the next moment, and take the sum of the standard deviation of the hotspot file-access heat sequence and the average value of the target state space as the next Predicted access popularity value at a moment; Step 4.4: Remove the first value of the input sequence, and add the newly predicted access popularity value as the last value of the next prediction sequence to the sequence to be predicted, repeat the above steps, and predict the access popularity of hotspot files at the next moment. 5. the method for calculating the number of dynamic HDFS copies based on file access heat according to claim 1, is characterized in that: the concrete method of described step 5 is: Step 5.1: obtain the access average request rate λ of the copy of specified hot file in the next statistical period by querying hot file-access heat database table statistics; Step 5.2: Set the CPU utilization threshold U of the server where the replica is located. According to the CPU utility law, the CPU utilization is equal to the request arrival rate divided by the service rate. Using the following formula, the request service rate μ of a single server is calculated as: Step 5.3: Set the total throughput constraint of the cluster to Q, based on the Little formula in queuing theory, the service residence time is equal to the service rate multiplied The reciprocal of the throughput is equal to the reciprocal of the service residence time; in a homogeneous cluster environment, the service rate of the server where multiple copies are located is the same, so the number of copies r is calculated by the following two formulas: .