![](https://csdnimg.cn/release/download_crawler_static/88503693/bg6.jpg)
ACM Transactions on Storage
,
Vol.
号
184
、第三十一条。出版日期:
2022
年
11
月
我们遵循以前的工作,目标是在卷之间均匀分配容量
负载
[18,22]。平衡容量在经过重复数据
消除的系统中尤为重要,因为这些系统会将传入文件路由到已包含类似文件的卷。在这样的设
计中,存储占用
率略高于其他卷的卷可能会由于其更大量的数据“吸引”更多的新文件而迅速过
载,等等。 容量负载平衡可以
提高网络利用率,并防止特定卷成为瓶颈或耗尽其容量。虽然性
能负载平衡不是我们的主要目标,但我们希望通过分配容量来提高我们所有的方法都可以扩展到
明确地解决它
。
在这项工作中,我们使用
平衡
度量来捕获系统中的负载平衡,这
类似于常用的
公平性
度量
[27]-
系统中最小卷的大小与最大卷的大小例如,图1(a)中初始系统的平衡是V
1
/V
2
=
1
/5。
备选方案1(图1(b))是完全平衡的,
平衡
=
1,而备选方案2(图1(c))的平衡最差:
V
1
/V
2
=0。
问题陈述。在复杂的优化系统中,有各种方法处理相互冲突的目标。这些包括搜索帕累托边界
[59]或定义加权个体目标的复合目标函数。我们选择将系统的大小作为主要目标,并将迁移流量和
负载平衡作为迁移计划的约束。 我们通过扩展[ 43 ]中的播种问题
来定义一般迁移问题;因此,为
了兼容性,我们重用了他们的一些符号。
对于具有一组卷V
的存储系统
S,设B = b
0
,b
1
,. 是存储在系统中的唯一块的集合,并且令
size(b)是块b的大小。设F
=
f
0
,f
1
,
.
,是S中的文件的集合,并且令I
S
B F V是包含关系,
其中(b,f,v)I
S
意味着文件f
被映射到卷
V
的
块包含存储在该卷中的块B我们用b
v
来表示对于某个文件f,(b,f,v)I
S
。
卷的大小是存储在其中的块的总大小,也就是说,
大小
(v)=
10bv
大小
(b)。系统的大小
是其体积的总大小,即
大小
(S)=
大小
(V)
=
大小
(V)。
一般
的迁移问题是找到一组要迁移的文件F
M
F、每个文件要
迁移到
的卷、可以从每个卷
删除的块以及应该复制到每个卷的块。应用迁移计划导致新系统
SJ
。迁移的
目标
是
最小化S j
的大小。 这相当于最大化迁移期间可以删除的所有数据块
的大小减去必须复制的所有数据块的
大小。
流量约束
指定
Tmax
-迁移期间允许的最大流量。 它要求添加到卷中的块的总大小不大于
T
max
。
负载平衡约束
决定了容量在卷之间的分布有多均匀。它指定了一个
余量
0≤
μ
1,并要求新系统中
每个卷的大小在平均卷大小的
μ
范围内
<
量系统|
V
|这就相当于
要求
所有
的
bala
n
c
e
[
(
尺 寸
e
(
S
J
)
/
|
V
|
)
×
(
1
−
μ
)
]
/
[
(
siz
e
(
S
J
)
/
|
V
|
)
×
(
1
+
μ
)
]
,
或
s
i
m
p
l
y
,
bal
an
c
e
(
1
−
μ
)
/
(
1
+
μ
)
。
例如,对于图1(a)中的初始系统,备选方案1(图1(b))是唯一满足负载平衡约束(对于
任何
μ
)的迁移计划当
Tmax
低于
2
/9
时,不可能发生迁移 另一方面,如果我们去除负载平衡约束,
则最佳迁移计划仅取决于流量约束:例如,备选方案2(图1(c))对于
Tmax
=
0
是最佳的,备选
方案3(图1(d))对于
Tmax
= 3是最佳的。
精炼。这个一般化的问题可以用几种简单的方法来细化。例如,我们可以限制可以包括在
F
M
中的文件集
、可以从中删除文件的卷集
或可以将文件重新映射到的卷集。类似地,我们可以
要求
从系统中删除一个特定的卷(强制其所有文件被重新映射)
,或者添加一个空卷我们在评估
中展示了其中的一些案例