Self-contained placement of data objects in a data storage system
View Patent ↗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.
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 1 , w 2 , . . . 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:
∑
i
=
1
K
∑
∀
u
,
v
∈
V
[
w
(
uv
i
)
x
(
uv
i
)
-
p
(
u
)
y
(
u
i
)
-
p
(
v
)
y
(
v
i
)
]
Variables:
x
(
uv
i
)
=
{
1
if
the
edge
uv
is
selected
in
storage
container
i
0
otherwise
}
Constraints:
the sum of the data object sizes in container i, is not larger than the given size of storage container i which is denoted SCi;
∑
∀
u
∈
V
s
(
u
)
y
(
u
i
)
≤
SCi
for
i
=
1
,
…
,
K
for storage containers, one edge between nodes u and v is selected, so there is no attempt to add profit by adding already used edges instead of unused edges, the used edges are unique;
∑
i
=
1
K
x
(
uv
i
)
≤
1
for
all
u
,
v
∈
V
for
which
w
(
uv
)
>
0
if an edge is selected in storage container i, then so are the nodes connected to that edge (incident vertices);
2
x
(
uv
i
)
-
y
(
u
i
)
-
y
(
v
i
)
≤
0
for
i
=
1
…
K
and
for
all
u
,
v
∈
V
number of copies of an object is at least 1 and doesn't exceed the defined maximum number of copies UL;
1
≤
∑
i
=
1
K
y
(
u
i
)
≤
u
L
for
all
u
∈
V
variables x and y have binary values; and
wherein if an object u′ is placed in a specific storage container i′, add a constraint that y(u′i′)=1;
x ( uv i ), y ( u i )ε{0,1}
for all u, vεV.
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:
x
j
(
uv
i
)
=
{
1
if
there
is
a
directed
path
of
length
j
in
storage
container
i
0
otherwise
}
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:
maximize
∑
i
=
1
K
∑
∀
u
,
v
∈
V
[
∑
j
=
1
M
w
j
(
uv
i
)
x
j
(
uv
i
)
-
p
(
u
)
y
(
u
i
)
-
p
(
v
)
y
(
v
i
)
]
.
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
∑
i
=
1
K
∑
j
=
1
M
x
j
(
uv
i
)
≤
1
for
all
u
,
v
∈
V
for
which
w
j
(
uv
)
>
0.
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)
2
x
1
(
uv
i
)
-
y
(
u
i
)
-
y
(
v
i
)
≤
0
for
i
=
1
,
…
,
K
and
for
all
u
,
v
∈
V
.
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
3
x
2
(
uv
i
)
-
y
(
u
i
)
-
y
(
w
i
1
)
-
y
(
v
i
)
≤
0
for
i
=
1
,
…
,
K
and
for
all
u
,
v
∈
V
if a path of length M is selected in storage container i, then so are all the nodes in this path
( M+ 1) x M ( uv i )− y ( u i )− . . . − y ( w M-1 i )− y ( v i )≦0.
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 1 , w 2 , . . . , 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 1 , w 2 , . . . , 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.