Method of instantiating data placement heuristic

• US 20050097286A1
• Filed: 10/30/2003
• Published: 05/05/2005
• Est. Priority Date: 10/30/2003
• Status: Abandoned Application

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Karlsson, Magnus, Karamanolis, Christos
• Application Number:
  US10/698,265
• Publication Number:
  US 20050097286A1
• Time in Patent Office: Days
• US Class Current: 711/159
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning

Abstract

A method of instantiating a data placement heuristic for a distributed storage system begins with a node of the distributed storage system receiving heuristic parameters. The method concludes with the node running an algorithm which instantiates a particular data placement heuristic selected from a range of data placement heuristics according to the heuristic parameters. According to an embodiment, the heuristic parameters comprise a placement constraint, a metric scope, an approximation technique, and an evaluation interval.

Claims

1. A method of instantiating a data placement heuristic for a distributed storage system comprising the steps of:

receiving heuristic parameters; and

running an algorithm on a node of the distributed storage system which instantiates a particular data placement heuristic selected from a range of data placement heuristics according to the heuristic parameters.

2. A method of instantiating a data placement heuristic for a distributed storage system comprising the steps of:

receiving heuristic parameters which comprise a cost function, a placement constraint, a metric scope, an approximation technique, and an evaluation interval; and

running an algorithm on a node of the distributed storage system which instantiates a particular data placement heuristic selected from a range of data placement heuristics according to the heuristic parameters.

3. The method of claim 2 wherein the heuristic parameters further comprise at least one additional placement constraint.

4. The method of claim 2 wherein the heuristic parameters further comprise a routing knowledge parameter.

5. The method of claim 2 wherein the heuristic parameters further comprise an activity history parameter.

6. The method of claim 2 wherein the metric scope comprises a node scope, which ranges from a single node of the distributed storage system to all nodes of the distributed storage system.

7. The method of claim 6 wherein the metric scope further comprises a client scope, which ranges from local clients accessing the single node to all clients accessing all of the nodes.

8. The method of claim 6 wherein the metric scope further comprises a data object scope, which ranges from local data objects stored on the single node to all data objects stored on all of the nodes.

9. The method of claim 2 wherein the heuristic parameters further comprise at least one additional approximation technique.

10. The method of claim 2 wherein the algorithm comprises a determination of costs for nodes and data objects within the metric scope according to the cost function.

11. The method of claim 10 wherein the algorithm further comprises a sort of the costs.

12. The method of claim 11 wherein the approximation technique comprises a ranking technique.

13. The method of claim 12 wherein the ranking technique comprises a greedy technique.

14. The method of claim 11 wherein the approximation technique comprises a threshold technique.

15. The method of claim 2 wherein the approximation technique comprises a random technique.

16. The method of claim 2 wherein the approximation techniques comprises an improvement technique.

17. The method of claim 2 wherein the approximation technique comprises a hierarchical technique.

18. The method of claim 2 wherein the approximation technique comprises a multiphase technique.

19. A method of instantiating a data placement heuristic for a distributed storage system comprising the steps of:

receiving heuristic parameters which comprise a cost function, a placement constraint, a metric scope, an approximation technique, and an evaluation interval; and

for each evaluation interval within an execution of the data placement heuristic, performing the steps of;

for data objects and nodes within the metric scope, determining a cost array which comprises cost elements determined from the cost function;

if the approximation technique comprises a ranking technique, placing the data objects according to the placement constraint in order of rank within a sorted cost array;

if the approximation technique comprises a greedy ranking technique, placing the data objects according to the placement constraint in order of the rank within the sorted cost array, and recomputing and resorting the cost array for remaining cost elements after each placement decision; and

if the approximation technique comprises a threshold technique, eliminating the cost elements of the cost array which violate a threshold, thereby forming a threshold limited cost array, and placing the data objects according to the placement constraint in order of rank within a sorted version of the threshold limited cost array.

20. The method of claim 19 wherein the cost function comprises a rate of read accesses by a client for a particular data object.

21. The method of claim 19 wherein the cost function comprises a rate of write accesses by a client for a particular data object.

22. The method of claim 19 wherein the cost function comprises a measure of a distance between a particular client and a particular node.

23. The method of claim 19 wherein the cost function comprises a storage cost for storing a particular data object on a particular node.

24. The method of claim 19 wherein the cost function comprises an access time comprising a timestamp indicating a most recent time when a particular data object was accessed at a particular node.

25. The method of claim 19 wherein the cost function comprises a load time comprising a timestamp indicating a time when a particular data object was stored on a particular node.

26. The method of claim 19 wherein the cost function comprises a hit ratio of transparent en route caches along a path from a client to a node.

27. The method of claim 19 wherein the placement constraint comprises a storage capacity constraint, which places an upper limit on a storage capacity for a node.

28. The method of claim 19 wherein the placement constraint comprises a load capacity constraint, which places an upper limit on a rate of requests for a node.

29. The method of claim 19 wherein the placement constraint comprises a node bandwidth capacity, which places an upper limit data transmission rate for a node.

30. The method of claim 19 wherein the placement constraint comprises a link capacity constraint, which places an upper limit on bandwidth between first and second nodes.

31. The method of claim 19 wherein the placement constraint comprises replica constraint, which places an upper limit on a number of replicas that can be placed on nodes of the distributed storage system.

32. The method of claim 19 wherein the placement constraint comprises a delay constraint, which places an upper limit on a response time for requests within the distributed storage system.

33. The method of claim 19 wherein the placement constraint comprises an availability constraint, which places a lower limit on availability of data objects within the distributed storage system.

34. The method of claim 19 wherein the approximation technique further comprises a hierarchical technique.

35. The method of claim 19 wherein the approximation technique further comprises a multiphase technique.

36. The method of claim 35 wherein the multiphase technique comprises an improvement technique.

37. A computer readable memory comprising computer code for implementing a method of instantiating a data placement heuristic for a distributed storage system, the method of instantiating the data placement heuristic comprising the steps of:

receiving heuristic parameters; and

running an algorithm on a node of the distributed storage system which instantiates a particular data placement heuristic selected from a range of data placement heuristics according to the heuristic parameters.

38. A computer readable memory comprising computer code for implementing a method of instantiating a data placement heuristic for a distributed storage system, the method of instantiating the data placement heuristic comprising the steps of:

receiving heuristic parameters which comprise a cost function, a placement constraint, a metric scope, an approximation technique, and an evaluation interval; and

running an algorithm on a node of the distributed storage system which instantiates a particular data placement heuristic selected from a range of data placement heuristics according to the heuristic parameters.

39. A computer readable memory comprising computer code for implementing a method of instantiating a data placement heuristic for a distributed storage system, the method of instantiating the data placement heuristic comprising the steps of:

receiving heuristic parameters which comprise a cost function, a placement constraint, a metric scope, an approximation technique, and an evaluation interval; and

for each evaluation interval within an execution of the data placement heuristic, performing the steps of;

for data objects and nodes within the metric scope, determining a cost array which comprises cost elements determined from the cost function;

if the approximation technique comprises a ranking technique, placing the data objects according to the placement constraint in order of rank within a sorted cost array;

if the approximation technique comprises a greedy ranking technique, placing the data objects according to the placement constraint in order of the rank within the sorted cost array, and recomputing and resorting the cost array for remaining cost elements after each placement decision; and

if the approximation technique comprises a threshold technique, eliminating the cost elements of the cost array which violate a threshold, thereby forming a threshold limited cost array, and placing the data objects according to the placement constraint in order of rank within a sorted version of the threshold limited cost array.