-1-
分布式数据库数据分配策略研究
李想，王秀坤，安奕星
大连理工大学电子与信息工程学院，辽宁大连 (116024)
摘 要：本文提出用遗传算法来解决数据分配问题，在本文的遗传算法中，主要统计了数据
库信息、应用信息和网络通信代价等，采用以事务处理代价为主的代价公式。算法通过代价
公式进行个体适应性评价，采用适应度比例方法和精英选择方法相结合的策略进行个体选
择，采用自适应交叉算子和自适应变异算子。实验结果表明，本文分配策略得到的分配方案
更接近最优分配方案。
关键词：数据分配；分布式数据库；遗传算法
中图分类号：TP311
1 引 言
数据分配问题对整个分布式数据库应用系统的改进、数据的可用性、分布式数据库的效
率和可靠性有很大影响。国内外学者希望找到一个使远程访问通信代价和局部事务处理代价
总和最小的数据分配方法，但由于其复杂性，尚未找到一个兼顾代价和性能最优的通用数据
分配方法。目前常用的分配方法有分组局部优化法[1]、启发式添加副本法[2]、启发式试消副
本法[2]和基于数据片段访问特性分配方法[3]等。
分组局部优化法代价公式过于复杂，可操作性差；启发式添加副本法考虑到了数据副本
之间的影响，以及随着副本增多带来的费用上升问题，但随着已分配片段的增多，计算量会
越来越大，算法效率较低；启发式试消副本法效率较高，但只适用于事务的检索更新比普遍
较大的系统；基于数据片段访问特性的分配方法结合了添加副本法和试消副本法的优点，但
得到的解与最佳分配方案仍有一定差距。
本文提出应用遗传算法来解决数据分配问题，来改进上述方法中的不足。遗传算法的基
本思想简单，易于实现，具有很高的并行性和鲁棒性，能在对解空间进行深度搜索和广度搜
索中维持很好的平衡，具有更强的搜索全局最优解的能力，得到的结果更接近最优分配方案。
2 分布式数据库与遗传算法简介
分布式数据库简介
分布式数据库系统是计算机网络技术与数据库技术互相渗透和有机结合的产物，通俗地
说，是物理上分散而逻辑上集中的数据库系统[4]，具有数据独立性、集中与自制相结合的控
制机制、适当增加数据冗余、事务管理的分布性等特点。系统强调节点的自治性而不强调系
统的集中控制，且系统保持数据的分布透明性。
遗传算法简介
遗传算法维持由一群个体组成的种群。每一个体均代表问题的一个潜在解，被评价优劣
并得到其适应值。根据适应值，按照一定的选择策略，选择某些个体进行交叉和变异操作：
变异的方法是将一个个体改变从而获得新的个体；交叉的方法是将两个个体的有关部分组合
起来形成新的个体。新产生的个体继续被评价优劣。从父代种群和子代种群中选择比较优秀
的个体就形成了新的种群，在若干代以后，算法收敛到一个最优个体，该个体很有可能代表
着问题的最优或次优解。
中国科技论文在线
-2-
3 基于遗传算法的数据分配策略
首先，对分布式数据库中的数据分配问题表述如下：设有一个由站点集
( )mSSSS ,,, 21 "= 构成的网络，该网络上运行一个事务集 ( )qTTTT ,,, 21 "= ，存储着一个
片段集 ( )nFFFF ,,, 21 "= 。按照一定的方式将每个片段 iF 的不同副本分配到不同的站点
kS 上的分配方案，表示为 TSFA ,, ，就是所谓的数据分配问题。
统计信息分析
在分布式数据库系统中，与数据、应用及环境相关的统计信息可以分为四类：数据库信
息、应用信息、站点信息和网络信息。将所有统计信息全部考虑到一个代价函数内是不现实
的，在实际的应用环境中，要对不同统计信息的重要程度要有一个恰当的评估，本文以下述
三条原则作为选择统计信息的依据[2]：统计信息本身的重要性，获取统计信息的代价，以及
统计信息对代价公式的复杂性的影响。基于以上三条原则，本文考虑以下统计信息：
(1) 数据库信息。该信息用数据片段大小来衡量。检索和更新代价都与数据量直接相关，
而片段大小是数据量的决定因素之一，该信息可以直接从数据库中获得。
(2) 应用信息。应用信息包括以下三种：第一，对数据片段的访问需求。该需求表示了
哪些事务要访问哪些数据片段。第二，各个事务在各个站点上的执行频率。该信息表明了哪
些事务是由哪些站点发出的，以及各个事务在各个站点上执行的频率。第三，每个事务对片
段的访问百分比。
(3) 网络信息。在网络信息中，我们考虑任意两个站点之间的通信代价权值，用通信代
价系数 ( )ji SSVtran , 表示。将本地访问代价系数设为 1，远程访问以本地访问为参照，各个
站点间的通信代价系数按照估算或统计的平均值得出。
代价公式
本文采用的代价公式主要是参照参考文献[3]，因为该文献中的代价公式目前采用较为
普遍，而且采用相同的代价公式也便于将本文算法求得的结果与其作比较。代价度量的标准
仍是代价优化目标函数，目标函数为 Min(TotalCost)。如果假设各个站点的处理能力基本相
同，那么可以用操作的总数据量来表示代价公式，所以本文采用的代价公式为
)1(UQ TTTotalCost +=
其中， QT 表示所有事务的检索数据量， UT 表示所有事务的更新数据量。对于所有站点
上发生的所有事务，其总的检索数据量 QT 为
)2()(),(_),(_),(tran jjik
S T F
ifkQ FSizeFTQSELSTQFRESSVT ∑∑∑=
其中， iT 为事务， jF 为数据片段， kS 为站点。 fS 为在站点 kS 上的事务 iT 所访问的数
据片段 jF 的副本所在的站点，若站点 kS 本地有数据片段 jF 的副本,则 fS 等于 kS ，否则 fS
为使 ( )fk SSVtran , 达到最小值的站点。 ( )fk SSVtran , 为站点 kS 与站点 fS 间的通信代价系
数， ( )ki STQFRE ,_ 为由站点 kS 发出的事务 iT 执行检索操作的频率， ( )ji FTQSEL ,_ 为事
务 iT 对数据片段 jF 的检索访问百分比， ( )jFSize 为数据片段 jF 的大小。
中国科技论文在线
-3-
对于所有站点上发生的所有事务，其总的更新数据量 UT 为
)3()(),(_),(_),(tran jjik
S T F
ifkU FSizeFTUSELSTUFRESSVT ∑∑∑=
其中， fS 为在站点 kS 上的事务 iT 所访问的数据片段 jF 的任一副本所在站点，即所有
拥有数据片段 jF 副本的站点。 ( )ki STUFRE ,_ 为由站点 kS 发出的事务 iT 执行更新操作的
频率， ( )ji FTUSEL ,_ 为事务 iT 对数据片段 jF 的更新访问百分比。 iT 、 jF 、 kS 、
( )fk SSVtran , 和 ( )jFSize 的含义与公式(2)中相同。
基于遗传算法的数据分配策略的步骤
在本文的数据分配策略中，针对每个数据片段，应用遗传算法得到该数据片段的分配方
案，从而得到最终的整体分配方案。下面详细介绍用遗传算法对某个数据片段进行分配的步
骤。
(1) 对参数集进行编码。每个数据片段可有多种分配方案，我们用种群中的一个个体表
示一种分配方案。我们对每个个体采用二进制编码，编码长度等于站点的个数，编码顺序与
站点顺序相对应，1表示将该数据片段分配给相应位置的站点，0则相反。
(2) 基于数据片段的更新检索比来初始化群体。群体规模越大，群体中个体的多样性越
高，算法陷入局部解的危险就越小。但是随着群体规模增大，计算量也显著增加。在本文的
遗传算法中，群体个数选为与站点数相当，为了使算法的搜索过程能更快地接近最优解，我
们根据数据片段的更新检索比来初始化群体。
对于某个数据片段，根据其片段大小、检索该片段的各事务在各站点上的执行频率、以
及对该片段的选择百分比，可以计算出该片段在所有事务中的检索访问量。同理可得某片段
在所有事务中的更新访问量，某片段的更新（用 U表示）检索（用 Q表示）比也就随之得
到了。
对于 U/Q<1 的数据片段，应尽量设置副本，以减少远程查询和提高数据的存取速度；
对于 U/Q>1 的数据片段，应尽量集中管理，以减少为保持多个副本之间的一致性而付出的
巨大更新代价。也就是说，在初始化群体时，对于 U/Q<1 的数据片段，应该在个体的染色
体位串中多设置 1；对于 U/Q>1的数据片段，应该在染色体位串中多设置 0。以这种方式初
始化得到的群体质量更高，将会提高算法的搜索速度，降低搜索陷入局部最优解的可能性。
(3) 适应度评价。在初始化群体后，要对群体中的每个个体进行适应度评价，选择适应
度高的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。适应度反映了
个体所代表的分配方案的优良程度，分配方案的更新检索总代价越小，个体的适应度就越高。
检索代价计算公式为
( ) ( ) ( ) ( ) )4(,_,_,∑∑=
S T
jjikifkQ FSizeFTQSELSTQFRESSVtranT
更新代价公式为
( ) ( ) ( ) ( ) )5(,_,_,∑∑=
S T
jjikifkU FSizeFTUSELSTUFRESSVtranT
将公式(4)和公式（5）计算得到的值相加就是个体的更新检索总代价，这里要注意的是，
总代价越大表示其适应度越小。
(4) 选择。本文的遗传算法采用适应度比例和精英选择[5]相结合的策略进行选择。适应
中国科技论文在线
-4-
度比例选择是最基本的选择方法，其中每个个体被选择的期望数量与其适应度和群体平均适
应度的比例有关。这种方式首先计算每个个体的适应度，然后计算出适应度在群体适应度总
和中所占的比例，表示该个体在选择过程中被选中的概率。设群体大小为 n，其中个体 i适
应度值为 if ，则 i被选择的概率 siP 为[6]
)6(/
1
∑
=
=
n
i
iisi ffP
精英选择策略。从遗传算法的整个选择策略来讲，精英保留是群体收敛到优化问题最优
解的一种基本保障。在本文算法中，如果下一代群体的最佳个体适应度小于当前群体最佳个
体的适应度，则将当前群体最佳个体直接复制到下一代，替换掉下一代中适应度最差的个体。
(5) 交叉和变异。交叉操作是模仿自然界有性繁殖的基因重组过程，其作用在于将原有
的优良基因遗传给下一代个体，并生成包含更复杂基因结构的新个体。交叉概率越高，群体
中新结构的引入越快，已获得的优良基因结构的丢失速度也相应升高。而交叉概率太低则可
能导致搜索阻滞。为了维持算法搜索速度和优良基因保留二者之间的平衡，本文算法采用自
适应交叉算子[7]，交叉概率 cP 为
( )( )
)7(max
21
c ⎪⎩
⎪⎨
⎧
<
≥−
−−−=
avgcc
avgc
avg
avgccc
c
FFP
FF
FF
FFPP
P
P
其中， 1cP =， 2cP =， maxF 和 avgF 分别是上一代群体中最大适应度和平均适应度，
cF 是参与交叉操作的两个个体中较大的适应度。
变异操作是保持群体多样性的有效手段，交叉结束后，群体中的全部个体位串上的每位
等位基因按变异概率 mP 改变。变异概率太小，可能使某些基因位过早丢失的信息无法恢复；
而变异概率过高，则遗传搜索将变成随机搜索。为了维持群体多样性和算法搜索随机性二者
之间的平衡，本文算法采用自适应变异算子[7]，变异概率 mP 为
( )( )
)8(max
max21
m ⎪⎩
⎪⎨
⎧
<
≥−
−−−=
avgmm
avgm
avg
mmm
m
FFP
FF
FF
FFPPP
P
其中， 1mP =， 2mP =， maxF 和 avgF 是上一代群体中最大适应度和平均适应度， mF
是变异个体的适应度。
经过选择、交叉和变异操作后，就产生了新一代群体。重新对新一代群体进行适应度评
价，并将新一代群体中个体的最高适应度与上一代群体中的最高适应度进行比较，若误差在
允许范围内，则该数据片段处理完毕；否则返回到步骤(4)。
(6) 重复步骤(1)、(2)、(3)、(4)、(5)，直到将所有数据片段都处理完为止。
分配策略复杂度分析与比较
代价公式复杂度
在本文分配策略的代价公式中，考虑了数据片段大小、更新检索需求、更新检索选择性
需求、更新检索应用在站点上的执行频率，及网络通信代价系数等统计信息，所有这些信息
中国科技论文在线
-5-
都是比较容易精确获得或者可以通过统计方法得到的，相对于有些方法考虑网络延迟、网络
拓扑结构等很难精确获得或者很不稳定的统计信息来说，显然本文策略中的统计信息更加简
单实用，从而使得代价公式的复杂度更低。
时间复杂度分析与比较
假设有 m个数据片段，n个事务，q个站点。那么在遗传算法中，个体适应度评价的时
间复杂度为O( 2mnq )，选择操作的时间复杂度为O(mq)，交叉操作的时间复杂度为O( 2mq )，
因为变异概率很小，变异操作的时间复杂度可以忽略不计。综上，本文算法的时间复杂度为
O( 2mnq )。
在启发式添加副本法中，因为初始分配采用的是非冗余最佳适应法，所以随着已分配的
数据片段的增多，每次的计算量会越来越大，导致算法的时间复杂度很大。启发式试消副本
法的时间复杂度是 O( 2mnq )，但只适用于事务的检索更新比普遍较大的系统，对于检索更
新比普遍较小的系统，由于初始副本过多，导致消除副本这一步的时间复杂度随着更新比重
的增加而增加。基于数据片段访问特性的数据分配策略的时间复杂度是 O( 2mnq )，与本文
算法相当。但遗传算法在每一代对群体规模为 n的个体进行操作时，实际上处理了大约O( 3n )
个模式，具有很高的并行性，因此效率更高。而且，本文分配策略得到的结果要优于基于数
据片段访问特性的数据分配策略，更接近最佳分配方案，这点将在第 4章中通过实验来说明。
另外，遗传算法还具有以下特有的优点：遗传算法具有很高的并行性和鲁棒性，具有较
好的全局最优解求解能力，搜索过程既不受优化函数连续性的约束，也没有优化函数导数必
须存在的要求，运行方式和实现步骤规范，便于具体使用。
4 分配策略结果验证与比较
本章用实验来验证本文提出的分配策略，并与基于数据片段访问特性的分配策略[3]进行
比较（该策略是启发式添加副本法和启发式试消副本法的结合，优于二者单独使用）。
实验中采取假定的多种不同的分布式环境,进行了多次测试，下面列出其中一种环境下
的测试结果。假定有 3个数据片段，3个事务，4个站点。在该环境下随机生成 5组统计信
息，然后分别使用本文的分配策略、基于数据片段访问特性的分配方法来进行数据分配，并
将二者得到的检索更新总代价进行比较。
在该环境下，5组统计信息分别如下。
表 1 第 1组统计信息
The first group statistical information
统计信息名 统计信息数据
片段大小 (5,1,4)
检索百分比 (1,0,0;7,5,0;6,0,2)
更新百分比 (6,4,8;0,1,1;0,6,6)
检索频率 (0,0,4,0;0,0,3,0;5,0,3,2)
更新频率 (2,0,0,2;2,0,5,3;0,5,0,0)
通信代价系数 (1,24,72,65;24,1,37,67;72,37,1,25;65,67,25,1)
中国科技论文在线
-6-
表 2 第 2组统计信息
The second group statistical information
统计信息名 统计信息数据
片段大小 (2,2,5)
检索百分比 (1,2,0;0,5,0;2,6,3)
更新百分比 (0,3,7;0,0,5;0,3,3)
检索频率 (5,3,0,1;4,4,0,4;0,4,2,1)
更新频率 (0,0,0,4;0,4,4,1;0,2,3,2)
通信代价系数 (1,83,74,90;83,1,57,87;74,57,1,44;90,87,44,1)
表 3 第 3组统计信息
The third group statistical information
统计信息名 统计信息数据
片段大小 (3,2,2)
检索百分比 (7,5,0;3,2,0;0,0,1)
更新百分比 (6,2,1;3,1,0;0,0,4)
检索频率 (2,0,0,7;1,2,4,1;3,4,3,0)
更新频率 (5,0,2,3;3,4,3,0;2,5,1,0)
通信代价系数 (1,74,58,31;74,1,90,23;58,90,1,11;31,23,11,1)
表 4 第 4组统计信息
The fourth group statistical information
统计信息名 统计信息数据
片段大小 (2,4,1)
检索百分比 (0,5,7;6,0,0;0,0,1)
更新百分比 (0,8,5;3,0,0;6,0,0)
检索频率 (5,5,5,4;3,0,5,0;3,0,1,4)
更新频率 (0,1,0,3;5,0,3,0;0,5,5,0)
通信代价系数 (1,16,39,13;16,1,79,72;39,79,1,34;13,72,34,1)
表 5 第 5组统计信息
The fifth group statistical information
统计信息名 统计信息数据
片段大小 (2,5,5)
检索百分比 (0,0,0;8,0,0;8,6,5)
更新百分比 (4,6,0;7,0,7;0,1,0)
检索频率 (0,0,0,0;4,0,0,3;3,4,0,5)
更新频率 (0,2,2,1;4,2,0,2;2,3,1,4)
通信代价系数 (1,44,54,32;44,1,55,36;54,55,1,69;32,36,69,1)
实验结果见表 6，表 6列出了在两种分配策略下分别得到的检索更新总代价。实验结果
表明，应用本文分配策略得到的分配方案总代价更小，更接近最优解。
表 6 实验结果
Experiment result
组号 最优分配代价 本文分配策略代价 基于数据片段访问特性分配策略代价
1 23992 23992 23992
2 32525 33173 37368
3 12383 12383 22924
4 17029 17969 27509
5 38632 38632 38632
5 结论
实验结果表明，本文分配策略得到的数据分配方案更接近最优解，总体性能要优于基于
数据片段访问特性的分配策略、启发式添加副本法和启发式试消副本法等。
中国科技论文在线
-7-
参考文献
[1] 王于同.一种分布式数据分布的启发式算法[J].计算机时代,1995,4:18-20
[2] 杨艺. 分布式数据库中数据分配方法的研究[D].重庆: 重庆大学，2004.
[3] 杨洲. 分布式数据库中数据分配策略的研究[D].哈尔滨: 哈尔滨工程大学，2007.
[4] 邵佩英. 分布式数据库系统及其应用[M].北京: 科学出版社，2000: 7.
[5] 李敏强，寇纪松，林丹，等. 遗传算法的基本理论与应用[M].北京: 科学出版社，2002: 35-38.
[6] 陈国良，王煦法，庄镇泉等.遗传算法及其应用[M].北京:人民邮电出版社,1999.
[7] 陈晓东，王宏宇. 一种基于改进遗传算法的组卷算法[J].哈尔滨工程大学学报，2005,37(9): 1175-1176.
Research of Data Allocation Strategy in Distributed
Database
Li Xiang, Wang Xiukun, An Yixing
School of Electronic and Information Engineering, Dalian University of Technology,
Dalian (116024)
Abstract
This paper proposes to use genetic algorithms to solve the problem of data distribution. Genetic
algorithm of this paper mainly adds up the database information, the application information and the
cost of network communication and so on, adopts a cost formula which mainly considers cost of
transaction processing. The algorithm evaluates fitness of individuals according to the cost formula.
The algorithm adopts the strategy which combines fitness-proportionate selection and elitist selection
to choose individuals. The algorithm adopts adaptive crossover operator and adaptive mutation
operator. Experimental results show that the allocation strategy of this paper gets closer to the optimal
allocation.
Keywords: Data Allocation, Distributed Database, Genetic Algorithms
作者简介：
李想(1984-)，男，大连理工大学电信学院硕士研究生，研究方向为分布式数据库；
王秀坤(1945-)，女，教授，博士生导师，研究方向为数据库系统与决策支持系统；
安奕星(1984-)，男，大连理工大学电信学院硕士研究生，研究方向为数据库技术及应用。
中国科技论文在线
