Hot data management method based on hit counter

This application claims priority under 35 U.S.C. §119 to Korean Patent Application No. 10-2008-0131277, filed on Dec. 22, 2008, in the Korean Intellectual Property Office, the disclosure of which is incorporated herein by reference in its entirety.

The following disclosure relates to an asymmetric storage system, and in particular, to a hot data management method based on hit counter, which prevents loads from being concentrated on a specific data server due to hot data by efficiently managing the hot data in the asymmetric storage system.

For ensuring high expandability, most large scale storage systems adopt an asymmetric structure, where metadata is extracted from actual data and stored separately, and a metadata server and a data server manage the metadata and the actual data respectively. Herein, the metadata means the address information of the data server storing the actual data of files.

The data server storing and managing each data provides actual data, which is stored in a disk, upon user's request over networks. However, there exist limitations in service performance provided by one data server due to the disk performance of the data server or the transmission performance of the network.

For example, in case that a large scale video service such as User Created Contents (UCC) is provided, many read requests occur in a specific data server storing and managing corresponding data when many accesses occur in a specific video file for a certain time interval. However, since data services can only be provided up to the highest performance of the disk or the network, a failure (for example, the interruption of a video service) might occur in an additional data service or even the video service for existing users.

In the asymmetric storage system, when intensive read requests from many users for a certain time interval occur for a specific file (hereinafter, which is referred to as “hot data”), data services cannot be provided smoothly due to limitations in the physical performances (that is, the performances of the disk and the network) of the data server storing and managing the data of the specific file. If metadata hit counter of a single metadata server instead of the data server is used to sense the hot data to solve this problem, the number of file read requests, which is the actual load of data, cannot be traced. Moreover, since the hit counter value should be updated each time the metadata is accessed, a lot of loads occur in the system.

Meanwhile, hot data may not be the hot data any more with the passage of time. If it is not considered, copies of the data made to solve the hot data problem waste storage.

In one general aspect of the present invention, a hot data management method based on hit counter includes: checking, by each data server of an asymmetric storage system, hit counter for data stored in the data server to maintain hit counter information on the data to a latest state; transmitting, by the data server, the hit counter information to a metadata server at predetermined intervals; and performing, by the data server, making or deletion of a copy of the data according to a determination of the metadata server.

In another general aspect, a hot data management method based on hit counter includes: configuring a hot data management table including a hit counter field for each data; collecting hit counter information on data from at least one of the data servers, where the corresponding data is stored; updating the hot data management table on the basis of the hit counter information; checking the hot data management table at a predetermined interval to determine whether a data file is hot data; making a copy of the data file, which is determined as the hot data, in a new data server; and deleting a copy of the data file which is no longer the hot data according to a result of the determination.

In another general aspect, a hot data management method includes: maintaining, by a plurality of data servers, data hit counter for data stored and managed by the corresponding data servers for a certain duration; transmitting, by the data servers, the data hit counter of the stored data to a management server at certain intervals; collecting and storing, by the management server, the transmitted data hit counter; and recognizing, by the management server, data, where hit counter for the data server is more than a predetermined threshold value within each interval, as a hot data, and making an additional copy of the hot data in at least one of the data servers, at certain intervals.

Other features and aspects will be apparent from the following detailed description, the drawings, and the claims.

FIG. 1 is a block diagram of an asymmetric storage system which is applied to exemplary embodiments of the present invention.

FIG. 2 is a diagram illustrating the configuration of a data hit counter entry according to en exemplary embodiment.

FIG. 3 is a flowchart illustrating a method for processing data hit counter according to an exemplary embodiment.

FIG. 4 is a flowchart illustrating a method for changing the rank of data hit counter according to an exemplary embodiment.

FIG. 5 is a flowchart illustrating a method for transmitting data hit counter according to an exemplary embodiment.

FIG. 6 is a diagram illustrating the configuration of a hot data management table which is included in a metadata server receiving hit counter information according to an exemplary embodiment.

FIG. 7 is a flowchart illustrating a method for storing data hit counter information according to an exemplary embodiment.

FIG. 8 is a flowchart illustrating a method for updating a hit counter field according to an exemplary embodiment.

FIG. 9 is a flowchart illustrating a method for sensing and copying hot data according to an exemplary embodiment.

FIG. 10 is a flowchart illustrating a method for withdrawring the additional copies of a file according to an exemplary embodiment.

Hereinafter, exemplary embodiments will be described in detail with reference to the accompanying drawings. Throughout the drawings and the detailed description, unless otherwise described, the same drawing reference numerals will be understood to refer to the same elements, features, and structures. The relative size and depiction of these elements may be exaggerated for clarity, illustration, and convenience. The following detailed description is provided to assist the reader in gaining a comprehensive understanding of the methods, apparatuses, and/or systems described herein. Accordingly, various changes, modifications, and equivalents of the methods, apparatuses, and/of systems described herein will be suggested to those of ordinary skill in the art. Also, descriptions of well-known functions and constructions may be omitted for increased clarity and conciseness.

FIG. 1 is a block diagram of an asymmetric storage system which is applied to exemplary embodiments of the present invention.

Referring to FIG. 1 , an asymmetric storage system applied to exemplary embodiments includes the n units of user file systems 110 - 1 to 110 -n (n is a natural number larger than 1), a metadata server 120 , and the m units of data servers 130 - 1 to 130 -m (m is a natural number larger than 1).

The user file systems 110 - 1 to 110 -n receive a file-related user's request. At this point, the user file systems 110 - 1 to 110 -n request metadata to the metadata server 120 according to the user's request, and request the actual data of a file to the data servers 130 - 1 to 130 -m

The metadata server 120 , which manages address information of the actual data of the file, checks whether the request of the specific user file system of the user file systems 110 - 1 to 110 -n is suitable, and transmits the requested metadata (i.e., the address information of a file data) to the specific user file system over a network.

The data servers 130 - 1 to 130 -m, which manage the actual data of the file, transfer the data of a disk to the specific user file system according to its request.

To collect information on the occurrence of a read load, the data servers 130 - 1 to 130 -m maintain data hit counter for the data read request of the user as shown in FIG. 2 .

Each of data hit counter entries 210 to 212 includes a data identifier field and a disk identifier field for discriminating data, a hit counter field for recording hit counter, a hash list field, and a top list field, and a hash function 201 and a hash table 202 including the MAX units of hash heads are used to search data hit counter entry rapidly according to the user's read request.

The hash function 201 has the data identifier of a user request, and receives a result value which is obtained by dividing the data identifier by MAX (data identifier % MAX). The hash result value is the value of one entry in the hash table 202 .

When the same hash result value as a result value of other data identifier divided by the MAX is obtained, data hit counter entries are connected as a chain through a hash list field including previous entry information and next entry information, like the data hit counter entries 210 and 211 of FIG. 2 .

To maintain the rank of the hit counter for data, the data hit counter entries 210 to 212 form a connection using a top list field which includes the previous entry information and the next entry information of the data hit counter entries, with a top list head as a starter.

In FIG. 2 , the data hit counter entry 211 is disposed next to the top list head, and thereafter the data hit counter entry 212 and the data hit counter entry 210 are sequentially chained. Herein, as a data hit counter entry is nearer to the top list head, it may be configured to be a data hit counter entry for a file having high priority, i.e., many hit counters. For example, the data hit counter entry 211 may be configured to be a data hit counter entry for a file having high priority, i.e., many hit counters.

FIG. 3 is a flowchart illustrating a method for processing data hit counter according to an exemplary embodiment. Hereinafter, a data server is any one of the data servers 130 - 1 to 130 -m in FIG. 1 .

Referring to FIG. 3 , when the data server is driven, it initializes the hash table in operation S 301 , and waits a user's request in operation S 302 . At this point, when the user's request on read or deletion is received in operation S 310 , data hit counter is updated through the following process.

The data server substitutes the data identifier for the hash function to obtain a hash result value in operation S 311 . Subsequently, the data server obtains the entry of a hash table, i.e., a hash list head as the hash result value in operation S 312 , and adds a next entry in a temporary entry in operation S 313 .

The data server determines whether the temporary entry is the same as the hash list head in operation S 320 . When the determination result shows that the temporary entry is the same as the hash list head, the data server determines whether a data identifier is the same as a disk identifier based on a user's request in operation S 330 . When the determination result shows that the data identifier is the same as the disk identifier, the data server determines whether the user request is a deletion request or a read request in operation S 340 .

When the determination result shows that the user request is the deletion request, the data server removes a corresponding data hit counter entry from the hash list in operation S 341 , and also removes the corresponding data hit counter entry from the top list in operation S 342 . The data server removes the corresponding data hit counter entry in operation S 343 .

When the determination result in operation S 340 shows that the user request is the read request, the data server increases the hit counter of the corresponding data hit counter entry once in operation S 351 , and updates the top list of the corresponding data hit counter entry in operation S 352 .

When the determination result in operation S 320 shows that the temporary entry is the same as the hash list head, the data server generates a new data hit counter entry, adds the disk identifier and the data identifier in the new data hit counter entry, and initializes the hit counter of the new data hit counter entry to ‘1’ in operation S 361 . Subsequently, the data server adds the hash list of the new data hit counter entry in the hash list head in operation S 362 , and adds the top list of the new data hit counter entry in the last portion of the top list head in operation S 363 .

When the determination result in operation S 330 shows that the disk identifier is the same as the data identifier, the data server adds a next entry in a temporary data hit counter entry in operation S 371 , and returns to operation S 320 .

When a data read request or a data deletion request is received, the data server adds a data identifier in the hash function to obtain a result value, and checks whether a data hit counter entry including a corresponding data identifier exists in the entry of the hash table, i.e., the hash list head. When the data hit counter entry exists and a user request is the read request, the data server increases a hit counter field by one and updates the top list of the entry. When the data hit counter entry does not exist, the data server generates a new data hit counter entry to initialize it, and add the initialized entry in the hash list head. When the data hit counter entry exists and the user request is the deletion request, the data server removes a corresponding data hit counter entry.

FIG. 4 is a flowchart illustrating a method for changing the rank of data hit counter according to an exemplary embodiment.

Referring to FIG. 4 , the data server fetches a previous entry from the top list of a corresponding data hit counter entry having the increased data hit counter in operation S 401 , and adds the previous entry in a temporary entry in operation S 402 .

The data server determines whether the temporary entry is the same as the top list head in operation S 410 . When the determination result shows that the temporary entry is not the same as the top list head, the data server determines whether the hit counter of the temporary entry is equal to or more than the hit counter of the data hit counter entry in operation S 420 .

When a temporary entry having hit counter (which is equal to or more than the hit counter of the data hit counter entry) is found as a result of the determination, a corresponding data hit counter entry is designated next to the top list of the temporary entry (which is a data hit counter entry added in a current temporary entry) in operation S 423 . Furthermore, the temporary entry is designated previous to the corresponding data hit counter entry. Through these processes, the ranks of the data hit counter entries may be changed.

When the temporary entry having hit counter (which is equal to or more than the hit counter of the data hit counter entry) is not found as a result of the determination in operation S 420 , the data server fetches a previous entry from the top list of the temporary entry in operation S 421 , and adds the fetched previous entry in the temporary entry in operation S 422 . In these processes, the data server searches entries having high priority, i.e., more hit counters.

When an entry having hit counter (which is equal to or more than that of a corresponding data hit counter entry) is not found to the top list head, since the corresponding data hit counter entry is an entry having the highest priority, the data server removes the current contents of the top list of the data hit counter entry in operation S 431 . Moreover, the data server designates the top list of the data hit counter entry as the next entry of the top list head in operation S 432 .

FIG. 5 is a flowchart illustrating a method for transmitting data hit counter according to an exemplary embodiment.

Referring to FIG. 5 , each of the data servers collects data hit counter in operation S 510 , and determines whether it arrives at a predetermined interval in operation S 520 . When the determination result shows that the predetermined interval arrives, the data server checks the maximum number of transmission in operation S 530 , and transmits hit counter information by the checked number to a metadata server in operation S 540 . Subsequently, the data server initializes a hit counter entry in operation S 550 .

Operation S 530 for checking the maximum number of transmission need not be performed every time.

FIG. 6 is a diagram illustrating the configuration of a hot data management table which is included in a metadata server receiving hit counter information according to an exemplary embodiment.

As shown in FIG. 6 , the hot data management table to be stored in a database (DB) included in the metadata server includes a file (i-node) identifier field 601 , a latest hit time field 602 , a hit counter field 603 , and an additional copy presence field 604 .

The file identifier field 601 is a value for discriminating a file, and is an i-node identifier in a Virtual File System (VFS).

The latest hit time field 602 maintains latest time information where the hit counter value of file data received from the data servers is updated.

The additional copy presence field 604 is for tracing and managing hot data, and represents an additional copy for solving the hot data.

A reference number 620 represents the configuration of the hit counter field 603 . min[0] to min[59] (which are fields 621 - 1 to 621 - 60 ) represent a file hit counter value on a minute-by-minute basis from the time of last_min (which is a field 621 ). hour[0] to hour[23] (which are fields 631 - 1 to 631 - 24 ) represent a file hit counter value on an hourly basis from the time of last_hour (which is a field 631 ). day[0] to day[364] (which are fields 641 - 1 to 641 - 365 ) represent a file hit counter value on a daily basis from the time of last_day (which is a field 641 ).

FIG. 7 is a flowchart illustrating a method for storing data hit counter information according to an exemplary embodiment. That is, FIG. 7 illustrates a process for storing data hit counter information (for example, a disk identifier, a data identifier, and hit counter) received from the data servers in the hot data management table. Hereinafter, a metadata server is the same as the metadata server 120 in FIG. 1 , and a data server is any one of the data servers 130 - 1 to 130 -m in FIG. 1 .

Referring to FIG. 7 , the metadata server receives a data hit counter value from the data server in operation S 701 , and obtains a file identifier including a disk identifier and a data identifier in operation S 702 .

The metadata server determines whether a file identifier corresponding to the disk identifier and the data identifier exists in operation S 710 . When the determination result shows that the file identifier does not exist, the metadata server recognizes a corresponding file as a deleted file. The metadata server returns to operation S 701 and obtains other data hit counter information.

When the determination result shows that the file identifier exists, the metadata server determines whether a data hit counter entry having the file identifier exists in a preset hot data management table in operation S 720 .

When the determination result shows that the data hit counter entry having the file identifier exists in the preset hot data management table, the metadata server fetches the hit counter field of the hot data management table in operation S 721 , and increases the specific fields of the hit counter field, for example, the value of the min[0], the value of the hour[0] and the value of the day[0], by a data hit counter value in operation S 722 . The metadata server updates a latest hit counter to the current time in operation S 723 , thereby updating the hit counter field.

When the determination result in operation S 720 shows that the data hit counter entry having the file identifier does not exist in the preset hot data management table, the metadata server adds a new data hit counter entry having the file identifier in the hot data management table in operation S 731 . The metadata server initializes all the fields of the hit counter filed of the new data hit counter entry, i.e., the min[0] to min[63], the hour[0] to hour[23] and the day[0] to day[364], to “0” in operation S 732 . Subsequently, the metadata server sets the last_min, last_hour and last_day of the hit counter field of the new data hit counter entry to the current time in operation S 733 , and proceeds to operation S 722 of increasing the fields.

FIG. 8 is a flowchart illustrating a method for updating a hit counter field according to an exemplary embodiment. That is, FIG. 8 illustrates a process for updating the hit counter field (i.e., the min[0] to min[59], the hour[0] to hour[23] and the day[0] to day[364]) of the hot data management table based on the current time. Hereinafter, a metadata server is the same as the metadata server 120 in FIG. 1 .

Referring to FIG. 8 , the metadata server compares the current time with the last_day of the hit counter field to determine whether the last_day has exceeded one day in operation S 810 .

When the determination result shows that the last_day has exceeded one day, the metadata server shifts the day[0] to day[364] of the hit counter field to the right by the exceeded day in operation S 811 , and initializes the fields from the day[0] to the day[exceeded day-1] to “0” in operation S 812 . The metadata server initializes the min[0] to min[59] and hour[0] to hour[23] of the hit counter field to “0” in operation S 813 , and updates the last_min, last_hour and last_day to the current time in operation S 814 .

When the determination result in operation S 810 shows that the last_day has not exceeded one day, the metadata server compares the current time with the last_hour of the hit counter field to determine whether the last_hour has exceeded one hour in operation S 820 .

When the determination result in operation S 820 shows that the last_hour has exceeded one hour, the metadata server shifts the hour[0] to hour[23] of the hit counter field to the right by the exceeded hour in operation S 821 , and initializes the fields from the hour[0] to the hour[exceeded hour-1] to “0” in operation S 822 . The metadata server initializes the min[0] to min[59] of the hit counter field to “0” in operation S 823 , and updates the last_min and last_hour to the current time in operation S 824 .

When the determination result in operation S 820 shows that the last_hour has not exceeded one hour, the metadata server compares the current time with the last_min of the hit counter field to determine whether the last_min has exceeded one minute in operation S 830 . When the determination result shows that the last_min has not exceeded one minute, the metadata server terminates the update of the hit counter field.

When the determination result in operation S 830 shows that the last_min has exceeded one minute, the metadata server shifts the min[0] to min[59] of the hit counter field to the right by the exceeded minute in operation S 831 , and initializes the fields from the min[0] to the min[exceeded minute-1] to “0” in operation S 832 . The metadata server updates the last_min to the current time in operation S 833 .

FIG. 9 is a flowchart illustrating a method for sensing and copying hot data according to an exemplary embodiment. Hereinafter, the metadata server is the same as the metadata server 120 of FIG. 1 .

Referring to FIG. 9 , the metadata server fetches a verification execution interval from the hot data management table in operation S 901 , and fetches a verification interval and a hit counter threshold value from the hot data management table in operation S 902 . The metadata server fetches all entries, in which a latest hit time is within the verification interval from the current time, from the hot data management table in operation S 903 . The metadata server checks the fetched entries one by one to determine whether the fetched entries are the hot data in operations S 904 and S 910 . When the determination result shows that the fetched entries are not the hot data, the metadata server maintains a sleep mode for the verification execution interval in operation S 920 , and returns to operation S 903 of fetching the entry.

When the determination result shows that the fetched entries are the hot data, the metadata server fetches the hit counter field of the hot data management table in operation S 911 , and changes the hit counter field based on the current time in operation S 912 . The metadata server determines whether the verification interval is a unit of a day in operation S 930 . When the determination result shows that the 25 verification interval is a day unit, the metadata server sums the values of the day[0] to day[verification interval] of the hit counter field and thereby adds the sum value in a hit counter variable in operation S 931 . The metadata server obtains the number of current copies of the file an entry in the hot data management table in operation S 960 , and determines whether the value of the hit counter divided by the number of the current copies is more than a threshold value in operation S 970 . When the determination result shows that the divided value is not more than the threshold value, the metadata server returns to operation S 904 of checking the entry.

When the determination result in operation S 970 shows that the divided value is more than the threshold value, the metadata server recognizes the hit counter value of the file as the hot data, and makes a copy of the file in a new data server in operation S 971 . The metadata server increases the number of copies of the file by one in operation S 972 . Afterwards, the metadata server updates the additional copy presence field of the entry of the hot data management table to “true” in operation S 973 .

When the determination result in operation S 930 shows that the verification interval is not a day unit, the metadata server determines whether the verification interval of the hot data is a unit of an hour in operation S 940 . When the results shows that the interval is an hour unit, the metadata server sums the values of the hour[0] to hour[verification interval] of the hit counter field and thereby adds the sum value in the hit counter variable in operation S 941 , and thereafter performs the processes next to operation S 960 of obtaining the number of the current copies.

When the determination result in operation S 940 shows that the verification interval of the hot data is not an hour unit, the metadata server determines whether the verification interval of the hot data is a unit of a minute in operation S 950 . When the results shows that the interval is a minute unit, the metadata server sums the values of the minute[0] to minute[verification interval] of the hit counter field and thereby adds the sum value in the hit counter variable in operation S 951 , and thereafter performs the processes next to operation S 960 of obtaining the number of the current copies.

When the determination result in operation S 950 shows that the verification interval of the hot data is not a minute unit, the metadata server outputs the fact that an error occurs in the verification interval value of the hot data in operation S 980 .

FIG. 10 is a flowchart illustrating a method for withdrawing the additional copies of a file according to an exemplary embodiment. Hereinafter, the metadata server is the same as the metadata server 120 of FIG. 1 .

Referring to FIG. 10 , the metadata server fetches a verification execution interval from the hot data management table in operation S 1001 , and fetches a verification interval value from the hot data management table for sensing the hot data in operation S 1002 . The metadata server fetches all entries, in which a latest hit time is not within the verification interval from the current time, from the hot data management table in operation S 1003 . The metadata server checks the fetched entries one by one to determine whether the fetched entries are represented as the hot data in operations S 1004 and S 1010 . When it turned out to be not the hot data, the metadata server maintains a sleep mode by the verification execution interval in operation S 1050 , and returns to operation S 1003 of fetching the entry.

When the determination result shows that the fetched entries are the hot data, the metadata server determines whether the additional copy field is set in the hot data management table in operation S 1020 .

When the determination result in operation S 1020 shows that the additional copy field is set in the hot data management table, the metadata server decreases the number of copies of the file in the entry by one in operation S 1021 , and deletes any one of the copies which are stored in the data server in operation S 1022 .

The metadata server determines whether the number of copies of the file in the entry is the same as the number of predetermined reference copies in operation S 1030 . When the determination result shows that the number of copies of the file is the same as the number of the predetermined reference copies, the metadata server initializes the additional copy field value of the entry in operation S 1031 , and returns to operation S 1004 of checking the entry. When the determination result shows that the number of copies of the file is not the same as the number of the predetermined reference copies, the metadata server returns to operation S 1004 of checking the entry.

When the determination result in operation S 1020 shows that the additional copy field is not set in the hot data management table, the metadata server removes the entry from the hot data management table in operation S 1040 , and returns to operation S 1004 of checking the entry.

The metadata server fetches the entries having no hit from the current time to the verification interval when fetching the entries in operation S 1003 . Thus, when the fetched entry is determined as an entry associated with the hot data in operations S 1004 to S 1040 next to operation S 1003 , the metadata server determines that the fetched entry is not the hot data at present although the fetched entry was the hot data in the past, and performs the above-described processes.

In FIG. 10 , the metadata server detects data which is no longer the hot data at present although the data were the hot data in the past, and removes the copy of the data, leading to decrease in waste of a storage.

A number of exemplary embodiments have been described above. Nevertheless, it will be understood that various modifications may be made. For example, suitable results may be achieved if the described techniques are performed in a different order and/or if components in a described system, architecture, device, or circuit are combined in a different manner and/or replaced or supplemented by other components or their equivalents. Accordingly, other implementations are within the scope of the following claims.