Self-contained placement of data objects in a data storage system

• US 8,706,782 B2
• Filed: 06/12/2011
• Issued: 04/22/2014
• Est. Priority Date: 06/12/2011
• Status: Active Grant

• Current Assignee: JP Morgan Chase Bank, N.A. (JP Morgan Chase & Co)
• Original Assignee: International Business Machines Corporation
• Inventors: Cohen, Simona, Harpaz, Avraham
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): VU, THONG H
• Application Number:
  US13/158,421
• Publication Number:
  US 20120316846A1
• Time in Patent Office: 1,045 Days
• Field of Search: 707/1/1, 707/626, 707/737, 707/741, 707/688, 711/159
• US Class Current: 707/812
• CPC Class Codes: G11B 2220/41 Flat as opposed to hierarchical combination, e.g. library of tapes or discs, CD changer, or groups of record carriers that together store one title
• CPC Class Codes: G11B 27/002 Programmed access in sequence to a plurality of record carriers or indexed parts, e.g. tracks, thereof, e.g. for editing; transfer of record carriers from magazine G11B15/68, G11B17/10; G11B17/22
• CPC Class Codes: G11B 27/11 by using information not detectable on the record carrier

Abstract

Systems and methods for optimal data storage are provided. The method comprises storing data objects that are most closely related in a storage container by modeling a constraint satisfaction problem for placement of said data objects in one or more storage containers, wherein a weight is assigned to an edge connecting two data objects based on an association defining relationships between the two data objects connected by said edge, taking into account certain penalties for placing multiple copies of the same object in the one or more storage containers, and wherein a storage container comprises a logical or physical storage area as a unit of storage.

Claims

1. A method implemented for execution on one more processors for optimal data storage, the method comprising:

storing data objects that are most closely related in a storage container by modeling a constraint satisfaction problem for placement of said data objects in one or more storage containers,

wherein the constraint satisfaction problem defines a self-contained placement degree for placement of the data objects, and accounts for penalties for placing multiple copies of the same data object in the one or more storage containers,

wherein a weight is assigned to a path connecting two data objects u and v, and a self-contained placement degree M is defined for the data objects u and v where there is a storage container that includes u, v and M−

1 data objects w₁, w₂, . . . w_M-1 that create a directed path from u to v,

wherein output of a solver that solves the constraint satisfaction problem provides information about the data objects that are to be placed in the one or more storage containers,

wherein the constraint satisfaction problem is defined as follows;

Given;

a set of data objects with known sizes that have weight-directed links or weight-directed paths;

number of storage containers K and the size of each container (SCi);

maximum number of required copies u_L for each object u;

desired self-containment placement degree M;

Find a placement V1, . . . , VK of V for K storage containers, where;

sum of the object sizes in each container i doesn'"'"'t exceed the container size SCi;

number of copies for each object u doesn'"'"'t exceed u_L;

such that placement weight is optimized to the highest weight of a self-contained placement degree M.

2. The method of claim 1 wherein the storage container comprises at least one of a mountable data storage unit, a file system, a tape, a block device, a stream device, an object store, or a data bucket in a cloud storage.

3. The method of claim 1, wherein xj(UVi) represents a path of length “

j”

between objects U and V in a storage container i,

wherein output of a solver that solves the constraint satisfaction problem provides information about the data objects that are to be placed in the one or more storage containers,

wherein variable x(UVi) is a Boolean variable that indicates whether an edge UV is included in a storage container i and variable y(Ui) is a Boolean variable that indicates whether an object U is included in the storage container i, and

wherein the result of the solver includes multiple sets, where each set represents a storage container and values included in that set represent the data objects or copies of data objects that are to be placed in the one or more storage containers.

4. The method of claim 3 wherein the result of the solver is used to rearrange placement for the data objects in a data storage system so as to optimize data access and retrieval to improve data security and fault tolerance.

5. The method of claim 4 further comprising analyzing data previously placed in the one or more storage containers and using a placement model used for modeling the constraint satisfaction problem to rearrange placement of the data objects in the most optimal way based on one or more identified constraints in the constraint satisfaction problem.

6. The method of claim 5 further comprising making the most optimal placement possible once receiving new data objects for placement in the one or more storage containers, without changing the placement of objects that have been already stored and leaving it to a later time to perform a placement on the data objects placed in the one or more storage containers.

7. The method of claim 5 further comprising making the most optimal placement possible when new data objects are received for placement without changing the placement of data objects that have been already placed, other than instances when changing the placement of some data objects is highly desirable.

8. The method of claim 1 wherein the constraint satisfaction problem is utilized to maximize self-contained placement of related data objects in the one or more storage containers with known capacities, while minimizing the placement of multiple copies of the same data object, according to the following:

Objective Function;

Maximize;

9. The method of claim 8, where in a general degree M scenario, path between objects “

u” and

“

v”

of length “

j”

in container “

i”

may be defined as the variable;

10. The method of claim 9, wherein the weight of the path of length “

j”

from “

u”

to “

v”

in storage container “

i”

may be defined as coefficient;

wj(uvi)=a function of the weights on the edges in the path plus a factor that decreases the weight as the path gets longer.

11. The method of claim 10 wherein the objective function is defined as:

12. The method of claim 11 wherein the constraints in the degree M scenario include:

one directed path between nodes u and v is selected, so there is no attempt to add profit by adding already used directed paths instead of unused directed paths, the used directed paths are unique

13. The method of claim 12 wherein the constraints in the degree M scenario further include:

if an edge is selected in storage container i, then so are the nodes connected to that edge (incident vertices)

14. The method of claim 13 wherein the constraints in the degree M scenario further include:

if a path of length 2 is selected in storage container i, then so are all the nodes in this path

15. A computing system for optimal data storage, the system comprising:

one or more processors;

a logic unit for storing data objects that are most closely related in a storage container by modeling a constraint satisfaction problem for placement of said data objects in one or more storage containers,

wherein the constraint satisfaction problem defines a self-contained placement degree for placement of the data objects, and accounts for penalties for placing multiple copies of the same data object in the one or more storage containers,

wherein a weight is assigned to a path connecting two data objects u and v, and a self-contained placement degree M is defined for the objects u and v where there is a storage container that includes u, v and M−

1 objects w₁, w₂, . . . , w_M-1 that create a directed path from u to v,

wherein output of a solver that solves the constraint satisfaction problem provides information about the data objects that are to be placed in the one or more storage containers,

wherein the constraint satisfaction problem is defined as follows;

Given;

a set of data objects with known sizes that have weight-directed links or weight-directed paths;

number of storage containers K and the size of each container (SCi);

maximum number of required copies u_f for each object u;

desired self-containment placement degree M;

Find a placement V1, . . . , VK of V for K storage containers, where;

sum of the object sizes in each container i doesn'"'"'t exceed the container size SCi;

number of copies for each object u doesn'"'"'t exceed u_L;

such that placement weight is optimized to the highest weight of a self-contained placement degree M.

16. The system of claim 15 wherein the storage container comprises at least one of a mountable data storage unit, a file system, a tape, a block device, a stream device, an object store, or a data bucket in a cloud storage.

17. The system of claim 15, wherein xj(UVi) represents a path of length “

j”

between objects U and V in a storage container i, wherein output of a solver that solves the constraint satisfaction problem provides information about the data objects that are to be placed in the one or more storage containers, wherein variable x(UVi) is a Boolean variable that indicates whether an edge UV is included in a storage container i and variable y(Ui) is a Boolean variable that indicates whether an object U is included in the storage container i, and wherein the result of the solver includes multiple sets where each set represents a storage container and values included in that set represent the data objects or copies of data objects that are to be placed in the one or more storage containers.

18. A computer program product comprising a non-transient computer readable storage medium having a computer readable program, wherein the computer readable program when executed on a computer causes the computer to:

store data objects that are most closely related in a storage container by modeling a constraint satisfaction problem for placement of said data objects in one or more storage containers,

wherein the constraint satisfaction problem defines a self-contained placement degree for placement of the data objects, and accounts for penalties for placing multiple copies of the same data object in the one or more storage containers,

wherein a weight is assigned to a path connecting two data objects u and v, and a self-contained placement degree M is defined for the objects u and v where there is a storage container that includes u, v and M−

1 objects w₁, w₂, . . . , w_M-1 that create a directed path from u to v,

wherein output of a solver that solves the constraint satisfaction problem provides information about the data objects that are to be placed in the one or more storage containers,

wherein the constraint satisfaction problem is defined as follows;

Given;

a set of data objects with known sizes that have weight-directed links or weight-directed paths;

number of storage containers K and the size of each container (SCi);

maximum number of required copies u_L for each object u;

desired self-containment placement degree M;

Find a placement V1, . . . , VK of V for K storage containers, where;

sum of the object sizes in each container i doesn'"'"'t exceed the container size SCi;

number of copies for each object u doesn'"'"'t exceed u_L;

such that placement weight is optimized to the highest weight of a self-contained placement degree M.

19. The computer program product of claim 18 wherein the storage container comprises at least one of a mountable data storage unit, a file system, a tape, a block device, a stream device, an object store, or a data bucket in a cloud storage.

20. The system of claim 18, wherein xj(UVi) represents a path of length “

j”

between objects U and V in a storage container i, wherein output of a solver that solves the constraint satisfaction problem provides information about the data objects that are to be placed in the one or more storage containers, wherein variable x(UVi) is a Boolean variable that indicates whether an edge UV is included in a storage container i and variable y(Ui) is a Boolean variable that indicates whether an object U is included in the storage container i, and wherein the result of the solver includes multiple sets where each set represents a storage container and values included in that set represent the data objects or copies of data objects that are to be placed in the one or more storage containers.

21. The computer program product of claim 20 wherein the result of the solver is used to rearrange placement for the data objects in a data storage system so as to optimize data access and retrieval to improve data security and fault tolerance.