Source: http://www.google.com/patents/US7853770?dq=mezick
Timestamp: 2015-05-06 12:07:53
Document Index: 550575720

Matched Legal Cases: ['art 12', 'art 12', 'art 13', 'art 13', 'art 19', 'art 14', 'art 15', 'art 16', 'art 17', 'art 15', 'art 15', 'art 14', 'art 16', 'art 17']

Patent US7853770 - Storage system, data relocation method thereof, and recording medium that ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsThere is a need to improve access speed for a file in a storage system that is provided with multiple storage units having different access speeds. The storage system (10) includes an access frequency acquiring part (14) that divides a past constant accessed data acquisition period into multiple unit...http://www.google.com/patents/US7853770?utm_source=gb-gplus-sharePatent US7853770 - Storage system, data relocation method thereof, and recording medium that records data relocation programAdvanced Patent SearchPublication numberUS7853770 B2Publication typeGrantApplication numberUS 11/744,907Publication dateDec 14, 2010Filing dateMay 7, 2007Priority dateSep 1, 2006Fee statusPaidAlso published asUS8356154, US20080059718, US20110202741Publication number11744907, 744907, US 7853770 B2, US 7853770B2, US-B2-7853770, US7853770 B2, US7853770B2InventorsSachie Tajima, Ryoichi UedaOriginal AssigneeHitachi, Ltd.Export CitationBiBTeX, EndNote, RefManPatent Citations (12), Referenced by (3), Classifications (9), Legal Events (2) External Links: USPTO, USPTO Assignment, EspacenetStorage system, data relocation method thereof, and recording medium that records data relocation program
Considering the above discussed point, Japanese Patent Laid-open Publication No. H05-12077 (hereinafter, referred to as �Patent Document 1�), for instance, discloses the following technique.
In order to solve the above problem, Japanese Patent Laid-open Publication No. H08-263335 (hereinafter, referred to as �Patent Document 2�) discloses a technique as follows: When the other data item is accessed within a certain period of time after the particular data item is accessed, it is assumed that the particular data item and the other data item are belonging to an identical group, and when any of the data within the group is accessed, the other data within the group are placed in the high-speed storage unit.
As mentioned above, the file information table 21 is a table that stores information of each file acquired by the file information acquisition part 12. As shown in FIG. 2, this file information table 21 includes a file ID field 21 a where a file ID is stored, and a file path field 21 b where a path to specify a location of a file with respect to each file ID is stored. By way of example, in the file ID field 21 a, a file ID �1� is stored, and in the file path field 21 b �/fruit/apple.jpg� is stored as a file path corresponding to the file ID �1�. The file information stored in this file information table 21 is continually kept up to date by the file information acquisition part 12.
The access date and time table 22 is a table that stores a date and time when each of the files is accessed, which is acquired by the access date and time managing part 13. As shown in FIG. 3, the access date and time table 22 includes an access date and time field 22 b which stores the date and time when the file is accessed, and a file ID field 22 a in which a file ID of the file that has been accessed is stored. For example, if a file having the file ID �5� is accessed at �2005/10/01 09:12:10�, �5� is stored in the file ID field 22 a, and �2005/10/01 09:12:10� is stored in the access date and time field 22 b. In this example here, only the date and time relating to accessing are stored. However, it is further possible to store attribute information such as indicating whether the access is a write access or a read access. This access date and time table 22 is updated by the access date and time managing part 13, every time the access processing part 19 accesses a file.
The access frequency table 23 is a table that stores the number of times of access, i.e., access frequency, with respect to each file during the accessed data acquisition period, which is obtained by the access frequency calculation part 14. The accessed data acquisition period is a period necessary for data relocation described below, and it is predetermined by a user. Here, as shown in FIG. 4, the accessed data acquisition period is assumed as being one week from 2005/10/1 to 2005/10/7 (i.e., Oct. 1 to 7, 2005). This accessed data acquisition period may be divided into multiple unit periods, which are predetermined by the user. In this particular example, this unit period is one day. The access frequency table 23 includes a file ID field 23 a to store a file ID of each file stored in each of the storage units 30 and 31, an access frequency field 23 b to store the access frequency for each unit period during the accessed data acquisition period, with respect to each file ID, and a total field 23 c to store a total access frequency during the accessed data acquisition period with respect to each file ID. This particular example illustrates that �1� is stored in the file ID field 23 a and the access frequency field 23 b associated with this file ID �1� stores 0 times for �2005/10/1�, 0 times for �10/2�, three times for �10/3�, five times for �10/4�, two times for �10/5�, one time for �10/6�, and 0 times for �10/7�. It is to be noted that in this example, the access frequency is stored without distinguishing between write access and read access. However, it is possible to differentiate the write access and the read access when each access frequency is stored.
The calibrated access degree table 24 is a table to store a calibrated access degree that is obtained by the access degree calculation part 15 by using the access frequency, for each unit period with respect to each file ID. Definitions of the calibrated access degree, the access degree to obtain the calibrated access degree, and a calculation method thereof will be described in detail below. Basically, both the access degree and the calibrated access degree are values indicating a degree of access frequency of the file during a unit period, relative to the total access frequency of the file during the accessed data acquisition period. Therefore, if the access degree or the calibrated access degree is high for a certain file during a constant unit period, this indicates that the number of times of access for this file is large during this unit period. This calibrated access degree table 24 includes a file ID field 24 a to store the entire file IDs stored in the file ID field 23 a of the access frequency table 23, and a calibrated access degree field 24 b that stores a calibrated access degree for each unit period during the accessed data acquisition period with respect to each file ID. This particular example illustrates that �1� is stored in the file ID field 24 a, and in the calibrated access degree fields 24 b associated with this file ID �1�, the calibrated access degrees are respectively stored, i.e., �0� for �2005/10/1�, �0� for �2005/10/2�, �0.68� for �10/3�, �0.91� for �10/4�, �0.36� for �10/5�, �0.18� for �10/6�, and �0� for �10/7�.
The file similarity degree table 25 is a table where the file similarity degree calculation part 16 stores a similarity degree indicating a similarity degree between the access frequency for one file within the unit period and the access frequency for other files within the unit period, with respect to each file ID. Definitions of the similarity degree and a calculation method thereof will be described in detail below. The higher the value is, the higher the possibility is that the two files are accessed within an identical unit period. The file similarity degree table 25 includes a file ID field 25 a to store all the file IDs stored in the file ID field 23 a of the access frequency table 23, and a similarity degree field 25 b that stores a similarity degree relative to another file, with respect to each file ID and the other file ID. This particular example illustrates that �1� is stored in the file ID field 25 a, and, in the similarity degree fields 25 b associated with the file ID �1�, the similarity degrees are respectively stored, i.e., a similarity degree �0.43� for a file having a file ID �2�, a similarity degree �1.15� for a file having a file ID �3�, a similarity degree �0.36� for a file having a file ID �4�, a similarity degree �0.66� for a file having a file ID �5�, a similarity degree �0� for a file having a file ID �6�, a similarity degree �0� for a file having a file ID �7�, a similarity degree �0.42� for a file having a file ID �8�, a similarity degree �0.30� for a file having a file ID �9�, and a similarity degree �0.53� for a file having a file ID �10�.
The file group table 26 is a table where the grouping process part 17 stores, with respect to each file ID, a second file ID that is assumed as belonging to a group that is the same as the file having the file ID. The group processing method will be described below. As shown in FIG. 7, the file group table 26 includes a file ID field 26 a storing all the file IDs stored in the file ID field 23 a of the access frequency table 23, and a field 26 b of file IDs included in the same group storing a file ID belonging to the same group as the file, for each file ID. This particular example illustrates that �1� is stored in the file ID field 26 a, and �3� is stored in the field of file IDs included in the same group 26 b, which is associated with the filed ID �1�. In other words, this example indicates that the file having the file ID �1� and the file having the file ID �3� belong to the same group. Therefore, �3� is stored in the file ID field 26 a, and, clearly, �1� is stored in the associated field of file IDs included in the same group 26 b. However, this is not the case if this grouping is performed while distinguishing between reading access and writing access, as described below.
The access degree calculation part 15 firstly determines whether or not the all the unit periods set in the access frequency table 23 are selected (S41). If all the unit periods are selected, the processing continues to step 45. If the entire unit periods are not selected, a non-selected unit period t is selected (S42), and the access degree calculation part 15 obtains the number of files that have been accessed during the unit period t, in other words, access frequency N(t) of all the files (S43). Subsequently, a grouping degree Y(t) (=N/N(t)) is calculated, which is a ratio between the number of all the files N stored in the file information table, and the access frequency N(t) to all the files within the unit period t (S44). For example, the number of all the files N is 10 (ten) having the file IDs �1� to �10�, and 5 (five) files are accessed during the unit period of October 1, which is the access frequency N (10/1) to all the files. Therefore, the grouping degree Y (10/1) of the unit period of October 1 is equal to two (=10/5). In addition, the grouping degree in the unit period of October 3 (10/3) is equal to 2.5 (=10/4). The grouping degree Y(t) is a value having a role of assigning weights to the access degree described below, and when the access frequency N(t) within the unit period t becomes larger, the value of the grouping degree Y(t) becomes smaller. The significance of the grouping degree will be explained later.
When the grouping degree Y(t) for a constant unit period t is calculated, the processing returns to step 41, and again it is determined whether or not all the unit periods have been selected. If all the unit periods are selected, it is determined whether or not all the files stored in the access frequency table 23 have been selected (S45). If all the files are selected, the process for calculating the calibrated access degree (S40) is terminated. If all the files have not been selected, file a, which has not been selected yet, is selected (S46). Then, the total access frequency C(a) to this file a during the accessed data acquisition period is obtained from the access frequency table 23 (S47). For example, the total access frequency C(1) to the file having the file ID �1� is �11� according to the access frequency table 23 (FIG. 4).
Subsequently, the access frequency calculation part 14 determines whether or not all the unit periods within the accessed data acquisition period have already been selected (S48), and if they have already been selected, the processing returns to step 45. Otherwise, the unit period t that has not been selected yet is selected (S49). Then, the access frequency C to the file a, during the unit period t (a, t), is obtained from the access frequency table 23 (S50). Thereafter, the access degree X(a, t) (=C(a, t)/C(a)) is obtained, which is a ratio of the access frequency C(a, t) to the file a during the unit period t, relative to the total access frequency C(a) to the file a during the accessed data acquisition period (S51). For example, C(1, 10/3) is �3�, which is the access frequency to the file �1� during the unit period of October 3, according to the access frequency table 23 (FIG. 4). The total access frequency C(1) to the file �1� is �11� as described above. Therefore, X(1, 10/3) is 0.27 (=3/11), which is the access degree of the file �1� during the unit period of October 3.
Next, the access degree X(a, t) to the file a during the unit period t is multiplied by the grouping degree Y(t) during the same unit period, which is obtained in step 44, and a calibrated access degree W(a, t) is calculated. Then, this calibrated access degree is stored in a corresponding field in the calibrated access degree table 24 (FIG. 5) (S52). For example, the access degree X (1, 10/3) at the unit period of October 3 for the file �1� is �0.27� as described above, and the grouping degree Y (10/3) at the unit period of October 3 is �2.5� as described above. Therefore, the calibrated access degree W(1, 10/3) at the unit period of October 3 for the file �1� is equal to 0.68 (=0.27�2.5).
When the file similarity degree calculation part 16 selects the non-selected file b within the set F, it is determined whether or not the entire unit periods within the accessed data acquisition period have been selected (S67). If all the unit periods have already been selected, the process returns to step 65, and if all the unit periods have not been selected yet, a non-selected unit period t within the accessed data acquisition period is selected (S68). Next, from the calibrated access degree table 24, the calibrated access degree W(a, t) of the file a and the calibrated access degree W(b, t) of the file b during this unit period t are extracted, and these are multiplied by each other, and an obtained value is set as a temporary similarity degree R(a, b) (S69). When the temporary similarity degree is obtained, the process returns to step 67. In step 68, a non-selected unit period is selected, and the calibrated access degree of the file a and the calibrated access degree of the file b during this unit period are multiplied by each other, and to this obtained value, the temporary similarity degree R(a, b) previously obtained is added (S69). Again, the process returns to step 67, and the step 67 to step 69 are repeated until selection of all the unit periods is completed. In other words, a value obtained by multiplying the calibrated access degree of the file a and the calibrated access degree of the file b with respect to each unit period within the accessed data acquisition period is summed, and an obtained total is set as a similarity degree R(a, b) between the file a and the file b. This similarity degree R(a, b) is stored in a corresponding field of the file similarity degree table 25 (FIG. 6). For example, the similarity degree R(1, 2) between the file �1� and the file �2� in the calibrated access degree table 24 as shown in FIG. 5 is expressed as the following.
This similarity degree R(1, 2)=0.43 is stored in the field of similarity degree of the file �2� being associated with the file �1�, in the file similarity degree table 25 as shown in FIG. 6.
When the process of calculating the file similarity degree (S60) is terminated, as shown in the flowchart of FIG. 8, the grouping process part 17 puts more than one file into some groups (S70), by using the similarity degree obtained in the process of calculating the file similarity degree (S60). Here, in the file similarity degree table 25 (FIG. 6), two files having the similarity degree equal to 1 or more therebetween are determined as having a high access relevance ratio between the files, and they are treated as belonging to the same group. For example, the similarity degree between the file �1� and the file �3� is �1.15� according to the file similarity degree table 25. Therefore, both files are treated as being belonging to the same group and this result is stored in the file group table 26 (FIG. 7).
Here, it is assumed that by using a computer of 10 GFLOPS, the processing as described above is carried out under the condition that a total number of files is �one million�, designated acquisition period is �one year�, and an acquisition unit period is �one day�. In this case, a rough calculation as follows can be done: According to the above description, the computing number of times required for obtaining W(a, t) of all the files is equal to 134�109, and the time for computing is equal to 13.4 seconds. When the similarity degree of each combination of all the files is calculated in advance, the required number of computations is equal to 365067�109, and the time for computing is equal to 36506.7 seconds≈10 hours. When only the similarity degree is obtained as to an accessed file after the file accessing is performed, the required number of computations is equal to 0.73�109, and the time for computation is equal to 0.073 seconds.
In the above examples, when a similarity degree between the files is obtained, an access degree and a calibrated access degree of this file are obtained according to the access frequency of the file, and by using this calibrated access degree, a similarity degree is obtained. However, there is another method that is capable of directly obtaining the similarity degree based on the access frequency, without acquiring the access degree and the calibrated access degree. By way of example, when a similarity degree between a file �1� and a file �2� is obtained, the access frequency of the file �1� and the access frequency of the file �2� are multiplied with respect to each unit period, and a value obtained by calculating the sum of those multiplied values may be assumed as the similarity degree between the file �1� and the file �2�. In other words, the similarity degree R(1, 2) between the file �1� and the file �2� may be obtained as in the following.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS5893139 *Jul 30, 1996Apr 6, 1999Kabushiki Kaisha ToshibaData storage device and storage method in which algorithms are provided for calculating access frequencies of dataUS6032224 *Dec 3, 1996Feb 29, 2000Emc CorporationHierarchical performance system for managing a plurality of storage units with different access speedsUS6640285 *Oct 26, 2000Oct 28, 2003Emc CorporationMethod and apparatus for improving the efficiency of cache memories using stored activity measuresUS6691136 *Dec 22, 2000Feb 10, 2004Fair Issac CorporationFast data retrieval based upon contiguous consolidation of records according to frequency of accessUS6785767 *Dec 26, 2000Aug 31, 2004Intel CorporationHybrid mass storage system and method with two different types of storage mediumUS6842876 *Apr 14, 1998Jan 11, 2005Fuji Xerox Co., Ltd.Document cache replacement policy for automatically generating groups of documents based on similarity of contentUS6948042 *Jan 17, 2003Sep 20, 2005Hitachi, Ltd.Hierarchical storage apparatus and control apparatus thereofUS7356660 *May 5, 2005Apr 8, 2008Hitachi, Ltd.Storage deviceUS7506012 *Jun 16, 2005Mar 17, 2009Hitachi, Ltd.Method and computer system for allocating database data based on access frequencyUS20050273638 *Mar 24, 2005Dec 8, 2005Fujitsu LimitedPower saving control system and power saving control methodJPH0512077A Title not availableJPH08263335A Title not available* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS8495013Dec 23, 2011Jul 23, 2013Kt CorporationDistributed storage system and method for storing objects based on locationsUS8775870Dec 22, 2011Jul 8, 2014Kt CorporationMethod and apparatus for recovering errors in a storage systemUS8849756Apr 13, 2012Sep 30, 2014Kt CorporationSelecting data nodes in distributed storage systemClassifications U.S. Classification711/165, 711/167International ClassificationG06F12/02Cooperative ClassificationG06F3/0649, G06F3/061, G06F3/0689European ClassificationG06F3/06A6L4R, G06F3/06A4H2L, G06F3/06A2PLegal EventsDateCodeEventDescriptionMay 14, 2014FPAYFee paymentYear of fee payment: 4May 17, 2007ASAssignmentOwner name: HITACHI, LTD., JAPANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:TAJIMA, SACHIE;UEDA, RYOICHI;REEL/FRAME:019307/0427Effective date: 20070416RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services