Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-09-13
2003-05-27
Vu, Kim (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06571258
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to computer data storage systems and more particularly to systems for reconfiguration of data storage.
BACKGROUND
Computer data systems today are huge and complex. Examples are: data related banking records, the internet, data mining systems, libraries, and scientific applications like planning for weather forecasting. All of this data is now being stored on-line so that the data can be manipulated.
One major problem is efficient access to this stored data. An analogy would be data storage as a library, with the data as the books in the library, and the data storage devices as shelves for the books. Different data storage devices hold different blocks of data, just as in a library where different shelves hold different books. It is desired that data be arranged on storage devices, as books are arranged on shelves, for the most efficient access.
From a library perspective, it is most efficient for storage of all of the most frequently read books to be stored on one shelf. However, this is not the most efficient from a user perspective because all the users would be trying to access that one shelf. The same is true for data storage. If all of the most frequently used data is on one data storage device, it creates a bottleneck on the data storage device because it is possible to retrieve only a certain amount of data from a data storage device per unit of time. Thus, a way to configure data storage to optimize throughput of the data storage system is necessary.
However, it is difficult to determine optimum data storage system configurations. It is necessary to look at workload patterns, how data is accessed, and what is important to the user. There are thousands, if not millions of blocks of data which must be considered.
There are individuals employed in many companies who regularly reconfigure the data storage in the data storage systems, and this is currently all being done manually. At the present time, the experts try and partition the problem into easy pieces. The people who do this are highly skilled and rely primarily on past experience, but there is no formalism to the reconfiguration process. Thus, a long sought, but unattained, objective in the field of data storage is to formalize the process and to make it easy, quantifiable, and quick to optimize a data storage system.
However, even if it were possible to optimize each storage system, even automatically, the problem is that workloads change. Over time, the most frequently used data changes. There are different blocks of data in the storage system. The access patterns to these blocks of data changes over time. Further, devices may fail or be added or subtracted. Thus, the ultimate goal is a data storage system which is not only able to automatically configure itself, but to reconfigure itself ‘on-the-fly’; i.e. move stored data around based on changing access patterns.
Currently, it is necessary to take the whole data storage system down off-line, reconfigure it, and then bring it back up. This is an increasing problem because customers cannot really afford to take their systems down at all. For example, a bank needs to have its automated teller machine systems available twenty-four hours a day, seven days a week, fifty-two weeks a year.
In the past, it has been a major set of goals to automatically optimize data storage configurations, change data storage configurations during data system operation, and to minimize the time that it takes to reconfigure the data storage system.
DISCLOSURE OF THE INVENTION
The present invention provides a computer data storage system with a migration plan generator which includes a “Simple” migration planner which provides for making terminal moves until no further terminal moves are possible based on random, preset, or functional ordering. A terminal move is a move of data to a data storage device where it belongs in a goal configuration. The moves make up a migration plan which is further processed to parallelize moves where possible to speed up the migration plan.
The present invention further provides a computer data storage system with migration plan generator which includes a “Simple” migration planner which provides for making terminal moves until no further terminal moves are possible, then making “shunt” moves, or non-terminal moves, until further terminal moves can be made. The moves make up a migration plan which is further processed to parallelize moves where possible to speed up the migration plan.
The present invention further provides a computer data storage system with a migration plan generator which includes a “Greedy” migration planner which uses a “contention” metric. The “contention” of a data storage device is defined as the total size of the data stores that need to move onto such data storage device, divided by the amount of free space on such data storage device. The contention of the entire system is the sum of the contention over all the data storage devices. The migration plan generator develops a plan that leads to the lowest contention for the system.
The present invention further provides a computer data storage system with a migration plan generator which includes a “Cycle” migration planner which finds shunts by first trying to find cycles with small data stores in a Greedy fashion. Once the smallest data store is moved off a data storage device, the largest data store in the cycle is shunted to any data storage device that can accommodate it.
The present invention further provides a computer data storage system with a migration plan generator which includes a “Hillclimbing” migration planner which uses a global contention metric which seeks the closest local minimum for the contention metric.
The present invention further provides a computer data storage system with a migration plan generator which includes a “Simulated Annealing” migration planner which uses a probabilistic Hilldlimbing approach that will sometimes choose moves that do not improve the optimization metric.
The present invention further provides a computer data storage system with a migration plan generator which includes a “Meta” migration planner which shifts from one planner to another based on the planner's performance.
REFERENCES:
patent: 5214768 (1993-05-01), Martin et al.
patent: 5719983 (1998-02-01), Henderson et al.
patent: 5894560 (1999-04-01), Carmichael et al.
patent: 6108748 (2000-08-01), Ofek et al.
patent: 6279074 (2001-08-01), Pence
Borowsky Elizabeth Lynn
Golding Richard Andrew
Narayanan Dushyanth
Hewlett -Packard Development Company, L.P.
Truong Cam-Y T
Vu Kim
LandOfFree
Computer data storage system with parallelization migration... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Computer data storage system with parallelization migration..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computer data storage system with parallelization migration... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3017688