论文部分内容阅读
摘要：内存数据库在最近几年迅速发展，并在应用中得到越来越广泛的实践。分布式数据分布算法具有广泛的研究和讨论，本文参照启发式添加和删除副本的数据分布算法，结合分布式内存数据库的特点并限制副本数，设计了一个实用的分布式内存数据库的数据分布方案。
关键词：内存数据库；分布式；数据分配；启发式算法
中图分类号：TP311.13 文献标识码：A 文章编号：1007-9599 （2012） 23-0000-02
随着信息化进度的加速，越来越多的数据库系统使用分布式架构。一系列的商用和开源数据库产品都支持分布式应用。数据分布是分布式数据库一个研究的重点方向，国内外很多学者研究并提出了一系列的数据分布方法[1][2][3][4]。然而这些方法大都是基于传统的磁盘数据库，很少对分布式内存数据库的数据分布进行探讨。内存数据库一个重要特点就是受物理内存限制，本文分析分布式内存数据库的特点，考虑数据节点物理内存的影响，对传统的启发式算法进行一定的限制和修改，设计了一个适合分布式内存数据库的数据分布策略。
1 内存数据库
数据库经过30多年的发展，在信息应用中越来越广泛。根据数据存储的介质不同，可以分为磁盘数据库和内存数据库。磁盘数据将数据保存在硬盘中，数据操作需要进行磁盘扫描和数据加载，磁盘处理成为影响数据库性能的瓶颈。内存数据库将数据放在内存中，不需要进行磁盘操作，内存操作速度远远快要磁盘操作。为了实现海量信息的快速响应，大型分布式内存数据库系受到广泛的探讨和应用。Key-value是一种快速的数据访问方式，在应用中也越来越多。关系型数据库依然还是数据库应用的主导应用，对于稍复杂的应用，key-value是不能够处理的或处理代价昂贵。本文针对传统的关系型数据库进行其分布式的内存数据分布探讨和设计。
2 分布式内存数据库数据分布的分析
数据冗余是分布式的特点，保证了数据的高可用性。冗余是高可用性的保证，同时也增加了数据维护的工作。在考虑分布式数据的分布时，大多采用代价最小算法实现。对于只有一个副本的数据分布计算相对简单，但是当系统允许多个副本存在时，数据分布的计算是一个NP复杂度的问题。目前对于NP问题的求解多采用启发式算法，当目标达到一定的误差范围即可。
使用启发算法进行数据分布计算时，需要一系列的统计值作为参考依据，收集统计信息进行目标模型的建立和数据分布的计算。影响数据分布的因素很多，但是在众多统计信息中，有些参考值是很难获取并且对代价影响不大的，有的是至关重要的。选取恰当的统计信息对算法的实现具有重要意义。本文主要关心数据在有限内存中的分配，弱化难获取的次重要的影响因素。在本文中关心的主要因素有：数据节点处理能力，数据节点允许使用最大内存，数据库分片大小，事务查询更新次数比，节点间通信代价。
3 分布式内存数据库数据分布设计
应用于数据分布的启发式算法有启发式添加副本算法和启发式删除副本算法，常根据具体应用的数据特点进行选取。
启发式添加副本算法适用查询多于更新的应用，其首先采用一定方法获得一个无冗余的数据分布并计算其代价，然后计算在添加一个新副本时系统的最小代价，当其代价小于增加副本前的代价则添加该副本。启发式删除副本算法适用更新多于查询的应用，其初始分布时将所有数据分布到各个节点再进行调整，当删除一个副本可能实现整体代价减少则进行副本删除。启发算法都需要经过迭代去控制其运算，通常设定一个比较小的误差值，在迭代得到的代价差小于误差值时认为分布已经达到一个满意的结果并结束迭代。
完成数据分布需要进行数据分布初始化和调整。使用启发式添加算法进行初始化分布时需要进行大量计算，本文重点放在分布式数据分布调整上，使用启发式添加算法进行数据初始化分布。对于数据调整，在数据节点的查询更新比大于1时，使用启发式添加副本算法，查询更新比小于1时，使用启发式删除副本方法。在数据调整时，先判断是否达到副本设定的上限或下限，当副本已经达到了其限定值，将不再进行调整，直接退出算法。当算法中需要添加副本的数据节点内存不能再容纳副本时，也结束本次调整计算。通过节点内存容量的限制和数据副本的控制，加快了数据分布的调整，虽然不是最优的分布方案，但提高了数据分布计算的效率。
本文将添加副本的上限设置为3，删除副本的下限设置为2，因此在完成分布后的调整中最多只进行一个副本的添加和删除，不需要进行迭代运算，节约了计算时间。通过设计一张维护数据片段的分布表去记录片段已经分布次数，在试探副本的添加和删除时需要参照分片数据分配表。副本限制在2和3之间，系统运行一定时间，将趋于一个优化的分布，并且副本的添加和删除将相对较少，可快速的进行数据分布调整，具有一定的实用性。
假设 表示将添加的分片， 表示第 个数据节点当前容量， 表示第 个数据节点最大容量，由于内存的限制，必须满足下面公式。
（1）
假设所有的节点能够容纳3份完整的数据，数据分片为n个，节点个数为w个，调整后的数据分布算法如下。
（1）初始化数据分布完成无冗余的数据分布。
（2）取 分片，判断节点 是否拥有和能够容纳 ，如果 不拥有并且能够容纳 ，计算添加 到 的代价，否则记代价为无穷大。
（3）按照步骤（2）的判断条件，计算将 添加到 （2，…w）的代价，选取最小的代价并进行分配。
（4）取 （2，…n），按照步骤2，3进行计算，完成冗余度为2的分布。
（5）再运行步骤2，3，4完成3个冗余度分布。
（6）判断应用的查询更新比，当查询更新比小于1时，试着删除 （1，…w）上的 （1，..n），判断新的代价，若代价小于删除前则进行相应数据分片的删除。当查询更新比大于1时，试着计算在 （1，…w）上添加 （1，..n）的代价，按照最小代价进行分配。
4 结论
启发式添加删除副本方法是一种简单有效的数据分布算法，为了达到最优的数据分布，其算法的计算量较大。在启发算法中加入内存使用限制因素，并限制副本数量，能够减少算法计算量，能够得到一个有效的分布式内存数据库数据的分布方案。
参考文献：
[1]YIN FU HUANG，JYH HER CHEN “Fragment Allocation in Distributed Database Design”，JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 17，491-506（2001）
[2]Ajit M，Tamhankar，Sudha Ram，“Database Fragmentation and Allocation： An Integrated Methodology and Case Study”， IEEE TRANSACTIONS ON SYSTEMS， MAN， AND CYBERNETICS-PART A： SYSTEM AND HUMANS， VOL.28， NO. 3， pp. 288-305， MAY 1998.
[3]王同于，陈临强.一种优化的分布式数据库数据分布模型[J].杭州电子工业学报，1994.12第4期 43-50.
[4]王同于.一种分布式数据分布的启发式算法[J].计算机时代，1995，（4）.
本文得到国家科技支撑计划课题支持：2011BAH21B02，2011BAH21B03
关键词：内存数据库；分布式；数据分配；启发式算法
中图分类号：TP311.13 文献标识码：A 文章编号：1007-9599 （2012） 23-0000-02
随着信息化进度的加速，越来越多的数据库系统使用分布式架构。一系列的商用和开源数据库产品都支持分布式应用。数据分布是分布式数据库一个研究的重点方向，国内外很多学者研究并提出了一系列的数据分布方法[1][2][3][4]。然而这些方法大都是基于传统的磁盘数据库，很少对分布式内存数据库的数据分布进行探讨。内存数据库一个重要特点就是受物理内存限制，本文分析分布式内存数据库的特点，考虑数据节点物理内存的影响，对传统的启发式算法进行一定的限制和修改，设计了一个适合分布式内存数据库的数据分布策略。
1 内存数据库
数据库经过30多年的发展，在信息应用中越来越广泛。根据数据存储的介质不同，可以分为磁盘数据库和内存数据库。磁盘数据将数据保存在硬盘中，数据操作需要进行磁盘扫描和数据加载，磁盘处理成为影响数据库性能的瓶颈。内存数据库将数据放在内存中，不需要进行磁盘操作，内存操作速度远远快要磁盘操作。为了实现海量信息的快速响应，大型分布式内存数据库系受到广泛的探讨和应用。Key-value是一种快速的数据访问方式，在应用中也越来越多。关系型数据库依然还是数据库应用的主导应用，对于稍复杂的应用，key-value是不能够处理的或处理代价昂贵。本文针对传统的关系型数据库进行其分布式的内存数据分布探讨和设计。
2 分布式内存数据库数据分布的分析
数据冗余是分布式的特点，保证了数据的高可用性。冗余是高可用性的保证，同时也增加了数据维护的工作。在考虑分布式数据的分布时，大多采用代价最小算法实现。对于只有一个副本的数据分布计算相对简单，但是当系统允许多个副本存在时，数据分布的计算是一个NP复杂度的问题。目前对于NP问题的求解多采用启发式算法，当目标达到一定的误差范围即可。
使用启发算法进行数据分布计算时，需要一系列的统计值作为参考依据，收集统计信息进行目标模型的建立和数据分布的计算。影响数据分布的因素很多，但是在众多统计信息中，有些参考值是很难获取并且对代价影响不大的，有的是至关重要的。选取恰当的统计信息对算法的实现具有重要意义。本文主要关心数据在有限内存中的分配，弱化难获取的次重要的影响因素。在本文中关心的主要因素有：数据节点处理能力，数据节点允许使用最大内存，数据库分片大小，事务查询更新次数比，节点间通信代价。
3 分布式内存数据库数据分布设计
应用于数据分布的启发式算法有启发式添加副本算法和启发式删除副本算法，常根据具体应用的数据特点进行选取。
启发式添加副本算法适用查询多于更新的应用，其首先采用一定方法获得一个无冗余的数据分布并计算其代价，然后计算在添加一个新副本时系统的最小代价，当其代价小于增加副本前的代价则添加该副本。启发式删除副本算法适用更新多于查询的应用，其初始分布时将所有数据分布到各个节点再进行调整，当删除一个副本可能实现整体代价减少则进行副本删除。启发算法都需要经过迭代去控制其运算，通常设定一个比较小的误差值，在迭代得到的代价差小于误差值时认为分布已经达到一个满意的结果并结束迭代。
完成数据分布需要进行数据分布初始化和调整。使用启发式添加算法进行初始化分布时需要进行大量计算，本文重点放在分布式数据分布调整上，使用启发式添加算法进行数据初始化分布。对于数据调整，在数据节点的查询更新比大于1时，使用启发式添加副本算法，查询更新比小于1时，使用启发式删除副本方法。在数据调整时，先判断是否达到副本设定的上限或下限，当副本已经达到了其限定值，将不再进行调整，直接退出算法。当算法中需要添加副本的数据节点内存不能再容纳副本时，也结束本次调整计算。通过节点内存容量的限制和数据副本的控制，加快了数据分布的调整，虽然不是最优的分布方案，但提高了数据分布计算的效率。
本文将添加副本的上限设置为3，删除副本的下限设置为2，因此在完成分布后的调整中最多只进行一个副本的添加和删除，不需要进行迭代运算，节约了计算时间。通过设计一张维护数据片段的分布表去记录片段已经分布次数，在试探副本的添加和删除时需要参照分片数据分配表。副本限制在2和3之间，系统运行一定时间，将趋于一个优化的分布，并且副本的添加和删除将相对较少，可快速的进行数据分布调整，具有一定的实用性。
假设 表示将添加的分片， 表示第 个数据节点当前容量， 表示第 个数据节点最大容量，由于内存的限制，必须满足下面公式。
（1）
假设所有的节点能够容纳3份完整的数据，数据分片为n个，节点个数为w个，调整后的数据分布算法如下。
（1）初始化数据分布完成无冗余的数据分布。
（2）取 分片，判断节点 是否拥有和能够容纳 ，如果 不拥有并且能够容纳 ，计算添加 到 的代价，否则记代价为无穷大。
（3）按照步骤（2）的判断条件，计算将 添加到 （2，…w）的代价，选取最小的代价并进行分配。
（4）取 （2，…n），按照步骤2，3进行计算，完成冗余度为2的分布。
（5）再运行步骤2，3，4完成3个冗余度分布。
（6）判断应用的查询更新比，当查询更新比小于1时，试着删除 （1，…w）上的 （1，..n），判断新的代价，若代价小于删除前则进行相应数据分片的删除。当查询更新比大于1时，试着计算在 （1，…w）上添加 （1，..n）的代价，按照最小代价进行分配。
4 结论
启发式添加删除副本方法是一种简单有效的数据分布算法，为了达到最优的数据分布，其算法的计算量较大。在启发算法中加入内存使用限制因素，并限制副本数量，能够减少算法计算量，能够得到一个有效的分布式内存数据库数据的分布方案。
参考文献：
[1]YIN FU HUANG，JYH HER CHEN “Fragment Allocation in Distributed Database Design”，JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 17，491-506（2001）
[2]Ajit M，Tamhankar，Sudha Ram，“Database Fragmentation and Allocation： An Integrated Methodology and Case Study”， IEEE TRANSACTIONS ON SYSTEMS， MAN， AND CYBERNETICS-PART A： SYSTEM AND HUMANS， VOL.28， NO. 3， pp. 288-305， MAY 1998.
[3]王同于，陈临强.一种优化的分布式数据库数据分布模型[J].杭州电子工业学报，1994.12第4期 43-50.
[4]王同于.一种分布式数据分布的启发式算法[J].计算机时代，1995，（4）.
本文得到国家科技支撑计划课题支持：2011BAH21B02，2011BAH21B03