User-driving Based Storage and Organization Strategy for Spatial Data

用户在访问地理信息系统时，其访问行为蕴涵了地理空间数据相互之间的关系^[5]，算法的目的是利用用户访问行为关系对空间数据文件进行两次分布存储组织：①通过计算空间数据相互之间的访问相关性，将热点数据均匀分布存储在不同的服务器上，即同时访问的数据分布到不同的存储节点，以实现用户访问服务时的负载均衡性；②对存储在同一个存储服务器上的数据，按照其访问相关性将连续访问的空间数据存储在同一个磁盘分区，以实现合并、存储和读取，减少磁盘移动距离，提高磁盘访问效率。

考察一般性，设F= {f₁, f₂…f_N}为系统存储的空间数据所有文件的集合，F中的元素分别通过自然数1, 2…N进行标识，其中N为空间数据文件的总个数，若分布式地理信息系统中，{f_a1, f_a2…f_aM }为存储系统记录的按访问时间先后顺序排列的空间数据文件访问序列，则A= {a₁a₂…a_M }称为空间数据文件访问序列向量, 其中M为对F中所有空间数据文件访问的总次数; 1≤a_i≤N表示地理信息系统中第i次用户请求的空间数据文件标识值，即a_i=k表示第i次请求的空间数据文件为f_k(i= 1，2…m; k=1, 2…N)。

若设S={ S₁, S₂…S_C}为分布式网络地理信息系统的所有服务器集合，其中C是总的服务器数量，考虑空间数据文件分布问题，将A按原顺序以C个元素一组分割为若干子向量，此时A表示为：A= {A₁ A₂…A_K}，其中A_i= {a_i1 a_i2…a_iC }，a_ij∈[1, N](1≤j≤C)为长度为C的子向量; K为子向量的总数量。考察任意子向量A_i，若任意空间数据文件f_m和f_n在子向量中出现的次数分别为r_im和r_in次，则定义空间数据文件f_m和f_n在子向量A_i上的相关性为：

显然，空间数据文件f_m和f_n在子向量A_i上出现的次数越多，两者的相关性越强；当r_im=0或r_in=0时，两者的相关性为0，即在子向量A_i上没有相关性。为此，任意两个空间数据文件f_m和f_n在总访问序列向量A上的总平均相关性为：

从式(2)可知，空间数据文件f_m和f_n在一定时间间隔内被访问的次数越多(1个子向量内)或在不同时间间隔内被同时访问的次数越多(同时出现在多个子向量中)，则两者的相关性越强。

为实现各个服务器在用户访问服务时的负载均衡(第1次分布存储组织)，需要将相关性高的数据均匀地分布存储到不同服务器上。不失一般性，对∀S_i∈S(i∈[1, C])，共存储C_i个空间数据，设S′_i为存储在服务器S_i上的所有空间数据集合，同时定义P_i=(p_i(m, n))_N×N为服务器S_i存储空间数据的指示矩阵，其中当且仅当空间数据文件f_m和f_n都存储在服务器S_i上时，p_i(m, n)=1, 否则p_i(m, n)=0(m, n∈[1, N])。显然，指示矩阵P_i是一个对称矩阵，且矩阵中非零元素的个数‖P_i‖₀=C_i×(C_i-1)。

为此，基于以上指示矩阵给出的数据布置策略将所有空间数据分布存储在不同服务器上，进而可计算服务器S_i存储的所有空间数据的总相关度为：

式中， Ξ =(ξ(m, n))_N×N为所有空间数据的相关度矩阵。

同样，设P={P₁, P₂…P_C}为所有服务器的空间数据分布存储组织的指示矩阵集合，则根据空间数据分布P可得到空间数据在所有服务器上存储分布后的总相关度为：

更进一步，若所有的空间数据都均匀分布在不同的服务器上(事实上，非均匀分布可以通过创建一些合适的副本数据，并将所创建的副本数据赋予一个新的数据编号，从而实现均匀分布)，有${C_i} = {C_j} = N/C, {\left\| {{\mathit{\boldsymbol{P}}_i}} \right\|_0} = {\left\| {{\mathit{\boldsymbol{P}}_j}} \right\|_0} = \frac{N}{C} \times \left( {\frac{N}{C} - 1} \right)$(1≤i, j≤C)，则式(3)、式(4)可简化为：

式中，$\omega = \frac{{{C^2}}}{{N\left( {N - C} \right)}};\mathit{\boldsymbol{H}} = \sum\limits_{i = 1}^C {{\mathit{\boldsymbol{P}}_i}} $。显然H矩阵同样为对称矩阵，且其中有且只有C×‖P_i‖₀= N×(N/C-1)个元素为1，其余元素为0。

根据均匀分布的基本原理，若设Ψ(P)为根据空间数据在不同服务器上的一个布置策略P所得到的相关度数学期望，则负载均衡的要求就是实现各个服务器上所分布的空间数据相关度差最小，即：

即算法的目标是根据空间数据相关度矩阵Ξ找到一个合适的布局策略P，使得存储在不同服务器上的空间数据总相关度均匀分布。显然，根据式(7)求解结果所得到的布局策略P，并按照P将数据分布存储到不同服务器上，即可实现用户访问地理信息系统的负载均衡目的。

一方面，通过式(7)求解得到全部空间数据在不同服务器中的分布存储布局策略P，并根据该策略将空间数据分布存储到不同的服务器，可以实现各服务器访问服务的负载均衡。另一方面，由于磁盘访问速度较低，通过连续多空间数据从存储节点到高速缓存的读取，可有效减少磁盘访问延迟对服务性能的影响。

不失一般性，设并发读取长度为μ，对∀S′=S_i∈S(1≤i≤C)，将存储在服务节点S′上的空间数据子集标签重新排序，并定义为F′= {f₁, f₂…f_N′}。相应地得到一个只包含空间数据子集F′的访问向量A′= [a₁ a₂…a_M′]，其中M′为基于空间数据集F′得到的空间数据文件访问序列向量长度，N′为存储在服务器节点S′上的空间数据文件数量。类似的，根据式(2)可计算得到任意空间数据文件f_m和f_n在总访问序列向量A′上的总平均相关性为：

式中，K′为将总访问序列向量A′=[A′₁ A′₂…A′_K′]按照读取长度为μ划分得到的子向量的总数量。

同理，设空间数据文件f_m和f_n在子向量A′_i中的平均访问间隔距离为d_i(m, n)，显然有：d_i(m, n)=d_i(n, m)，则f_m和f_n在总访问序列向量A′上的总平均访问距离为：

由于相关度高的数据有较高的概率在某时间窗口内一起被访问，基于磁盘I/O效率，将这些相关的数据顺序存放在磁盘上可以优化存储性能^[12], 即访问相关性高和访问间隔距离短的数据有较高概率被连续访问。为此，定义空间数据文件f_m和f_n总被连续访问的连续度为：

由式(10)可计算得到任意空间数据文件f_m和其他数据文件之间的访问连续度为：

根据式(11)以及读取长度μ，从Γ(m)中选择μ-1个最大元素对应的空间数据和f_m一起连续存储，保证有较高访问连续度的数据合并读取，以改善磁盘I/O性能。显然，根据式(11)计算结果排序所得到的空间数据合并存储策略，并按照顺序将数据合并存储到服务器的连续磁盘上，即可实现地理信息系统数据的高效并发读取目的。

选择SRTM 90全球数据作为实验数据集，每个空间数据文件大小约44 kB^[4]，按照512 kB的小文件标准^[13]，选择最大读取长度为μ=12。同时利用GlobeSIGht作为实验平台并依据Zipf-like分布对实验数据集进行模拟访问^[14]，以得到所有空间数据文件的访问序列A，序列长度包含约2 000万条记录(即M的大小)。

利用访问序列A的前半部分记录，并根据本文提出的算法计算各个数据的相关度，以及按照不同分布式服务器节点数量和不同算法及其参数条件，按照算法模型将数据分布存储在不同服务节点上；同时计算各个数据的连续度，并对存储在同一个服务节点的数据按照其连续度进行连续存储和访问时合并读取。

仿真实验平台由多台服务器组成分布式网络, 每个服务器通过千兆网络连接本地存储器, 分布式系统之间通过100 MB网络共享远程存储资源, 每个服务器提供不少于10 Mbps的用户访问服务带宽, 最后以访问序列A的后半部分记录对地理信息系统进行仿真访问，并记录系统的平均访问请求时间(服务器准备数据的时间)和不同服务器节点间的负载均衡性，通过比较本文所提出的算法(CSDL)与单纯的数据分布算法(data placement，DP)和传统地理信息系统基于地理位置的数据分布(data placement based on location，DL)算法进行比较, 以检验算法的性能。

按照实验方案，图 1给出了不同算法在不同分布式网络规模条件下单个数据平均访问请求时间对比实验结果。CSDL算法采用两步分布存储组织策略将数据分布存储到不同服务器，并采用连续读取策略对所请求的数据进行合并读取，以便提前将相关性高的数据预取到缓存区中，降低磁盘I/O次数，减少平均访问请求时间，提高服务响应速度；DP算法采用单纯的数据分布算法，将数据分布存储，但不考虑数据的连续读取，也没有合并预取；DL算法同样没有连续读取和合并预取，且其数据分布策略依赖数据的位置等固定属性信息。

Figure 1.  Comparison of Different Algorithms in Average Access Time

从图 1可以看出，随服务器数量增加，所有算法的平均访问请求时间会缓慢下降。显然，在相同数据规模下，服务器数量的增加可更好地保证热点数据被分布存储到不同的服务器上，以实现用户访问并行服务，减少了跨服务器调度数据的次数。同时，由于CSDL算法采用数据合并读取策略，其不但减少了磁盘I/O次数，而且部分数据进入缓存区，也提高了访问请求的响应时间。因此，本文的CSDL算法在不同服务器规模条件下都能取得较快的单数据平均访问请求时间。在给定实验条件下，总的平均请求响应时间性能比DP算法快约45.2%；比DL算法快约245.3%。

更进一步，由于用户对地理数据的访问存在极度的不平衡，部分热点区域吸引的用户访问数量可达到总访问量的80%以上^[12]，因此，基于地理位置的数据分布可导致部分服务器访问请求排队，从而整体上影响系统的平均访问请求时间。图 2给出的不同算法在不同分布式网络规模条件下的服务器间负载偏差对比实验可进一步说明算法的负载均衡性能。

Figure 2.  Comparison of Different Algorithms in Load Balance

平均负载偏差是指不同时刻各个服务器的负载和理论平均负载之间差异的平均值。平均负载偏差越大，表明系统的负载均衡性能越差。从图 2可以看出，分布式系统规模扩大时，不同算法条件下的平均负载偏差相应的增大；但在不同系统规模条件下，CSDL算法和DP算法的平均负载偏差基本都在10%以内，而DL算法的平均负载偏差达到了65%以上，表明由于地理数据存在局部访问热度问题，根据地理位置将热点数据同时分布存储在同一个服务器将带来负载的极度不均衡。从图 2可知，本文的CSDL算法都能取得最好的负载均衡性能，其平均负载偏差性能比DP算法低约0.5%，比DL算法低约440.9%。

由于用户访问行为的不同，地理信息系统中的数据相互之间表现出不同的相关性，其关系可以用Zipf-like分布模型表示^[12]，对应的分布参数α∈[0.6, 1.03]，为验证算法的适应性, 分别在不同分布参数条件下对CSDL算法进行对比实验，图 3为不同分布参数条件下CSDL算法的平均响应时间测试结果。

Figure 3.  Adaptability Test for Different Access Distributed Parameter

由图 3可知，访问分布参数α越大，用户对地理信息系统数据的访问越集中，热点数据相互之间的相关性越强^[12]，因此对数据进行合并读取的有效性越高，磁盘的I/O次数越少，相应的单数据平均响应时间就越短。从图 3可以看出，当分布参数α扩大10%时，单数据平均响应时间就能相应地降低约5.8%。

分布式地理信息系统下，空间数据的存储规模较大，为验证算法对大规模分布式环境应用的适应性, 分别在不同数据规模条件下对CSDL算法进行实验，图 4为4种不同数据规模条件下CSDL算法的平均负载偏差测试结果。

Figure 4.  Adaptability Test for Different Data Scale

与图 2的测试结果类似，不同数据规模下，平均负载偏差都随分布式系统的服务器数量增加而扩大，但平均负载偏差的扩大速度远小于分布式系统服务器数量的增长速度。从图 4可以看出，服务器数量规模扩大10倍时，平均负载偏差只扩大了约4倍；同时，数据规模越大(其中N为空间数据总数量)，平均负载偏差越小，且平均负载偏差随服务器数量增加而扩大的速度也越小，这是因为数据规模越大，用户对空间数据的访问分布越分散，利用本文算法更容易将同时访问的数据分布存储，因此本文方法对大规模分布式环境的应用有效。

针对分布式地理信息系统访问中数据存储要求和用户访问特征，从磁盘存储性能以及用户访问的负载均衡需求两个方面综合考虑空间数据文件在不同服务器节点和同一个服务器节点内部的存储分布需求，通过挖掘用户访问行为，对所有空间数据进行相关性和连续度度量，并据此完成空间数据存储的合理配置，以提高分布式地理信息系统的综合服务性能。对比实验表明，所提出的算法可有效提高约45.2%~245.3%的平均请求响应时间；通过负载均衡分布，分布式服务器节点的负载均衡度可提高约0.5%~440.9%，且模型能满足大规模分布式环境的应用需求。

未来进一步的研究将包括如何在用户行为变化时对用户访问行为的时效性进行度量，避免无效用户访问行为对空间数据相关性计算的影响以及快速实现空间数据分布策略的动态调整，以跟踪空间数据相关性的变化等；同时，地理信息系统在面向计算密集型应用时，需要考虑计算任务需求对数据进行分布存储等。