分布式数据库技术：并行索引支持

2023-10-28 理论教育版权反馈

【摘要】：参考文献［4］中详细讨论了并行数据库系统中的索引问题。讨论并行数据库系统数据的安置问题，下面几个方面是不可忽视的。并行数据库系统有物理资源级和操作级两个负载均衡问题。图14.25倒排文件的结构在并行系统里，分割一个倒排文件可以提高负载均衡和检索效率。

索引在数据库系统里扮演了重要角色。索引文件是一种在数据库系统里影响性能的重要数据结构。为了得到并行数据库的高性能（如较短的响应时间和高的吞吐量），索引文件需要有效地进行分割，并将一个个的文件分配到各个节点上。为了分割索引，考虑负载、兼顾不同的性能，有多种技术可用。参考文献［4］中详细讨论了并行数据库系统中的索引问题。

为了提高I/O的性能，数据的分割与分配很重要。如前所述，数据片的分配可以通过一些策略（如round-robin、hash、range）来实现。从性能方面考虑，数据分割与分配（称为declustering）的主要目标有如下两个。

●响应时间最短：查询执行期间并行实施的独立I/O数目越多，查询响应时间越短。

●吞吐量最高：如果每个查询的I/O操作可以并行实施，则吞吐量会增加。

讨论并行数据库系统数据的安置问题，下面几个方面是不可忽视的。

●分割和分配单元的数据类型：取决于使用了declustering的应用环境，而其中的数据类型和使用方式多种多样。分割和分配单元可以是关系（即记录集合）、文件或其他特定数据结构（如B树索引、多媒体文件）。按照特定数据类型的不同，分割和分配单元也可以是不同的。如果是关系，则可以基于键属性分片。文件则可以按连续数据块分割。B树索引文件的索引节点也可用作索引的分割和分配单元。

●数据分割和分配的程度：如何确定关系或文件分割和分配的磁盘数目是一个与性能相关的重要问题。小文件（例如小于一个磁道的文件）最好将整个文件分配到一个磁盘上。对于大文件来说，declustering程度越高，I/O并行性越高，当然也增加了服务于读/写请求时磁盘上的最长寻道时间和最大旋转延迟。随着declustering程度的提高，负载均衡会得到改善。不过，对于涉及复杂连接的事务来说，继续declustering会降低吞吐量，因为通信和启动/终止开销会增加。

●分割和分配策略：最简单的分割策略是采用round-robin方法分发元组。如果数据库应用为每个查询访问关系都顺序扫描其所有元组，则采用round-robin方法分割显得十分优秀。此时，会获得很好的负载均衡。哈希分割按照对每个元组的属性施加哈希函数来分配元组。哈希分割适合用于数据顺序存取和关联存取（associative access）的那些应用，将元组按特定属性的关联存取，可以直接定位到单个磁盘。范围（range）分割按照分割属性的范围分配元组。这对于按属性范围存取元组十分有利。

●负载均衡：负载均衡是并行数据库系统中的一个重要因素。并行数据库系统有物理资源级和操作级两个负载均衡问题。物理资源级负载均衡处理系统运行时物理资源的均衡使用问题（如CPU、I/O设备和通信网络）。操作级负载均衡按照分割数据将操作划分为子操作。扭曲的数据分布会引起严重问题，导致分割不平衡和破坏负载均衡。

●高可用性：在处理被分割的并行数据库系统中的数据时，高可用性是影响数据定位策略的一个重要因素。获得高可用性的常用途径是在各个处理器的磁盘上复制数据。一个副本出故障，其他副本仍可用。

倒排文件（inverted file）是数据库系统中常用的一种索引数据结构。倒排文件类似书后的索引表，针对每个关键词会给出其出现的页码，一个关键词对应一个或多个页码。在数据库系统里，倒排文件常用来描述一个属性对应于哪些主键。这在查询非主键属性时会提高效率。例如，在关系Student里，利用倒排文件为年龄属性建立索引，当查询age=20的学生时无需逐个扫描关系里的记录，无需比较每个学生记录里的age是否为20，而是先查询索引表，找到20就可找到相应记录的主键，借助这些主键就可找到相应的记录。

问题是，并行处理系统中如何存放倒排文件才合适呢？

我们来看两类并行系统：在无共享（shared-nothing）模型里，每个处理器都有自己的内存和外存。处理器间借助消息交换进行通信。在全共享（shared-everything）模型里，每个处理器可以同时访问公共存储和任意硬盘。处理器也可以有私有内存。(www.chuimin.cn)

在单台机器上使用倒排文件实现信息检索是常用的方法。当然，在多处理器上使用倒排文件实现信息检索也是很有用的。

倒排文件系统一般由索引文件（index file）、定位文件（posting file）和文档文件（document file）三个文件构成，如图14.25所示。

索引文件一般是关键词的有序列表，索引指向一个文档集合，即文档文件记录。索引文件里的条目由一个存取词项和两个字段构成。这两个字段，一个是该存取词项在定位文件里条目的定位和距定位点的位移。定位文件由一组记录构成，每个记录关联索引文件的一个存取词项和文档文件里含有该存取词项的记录。除此之外，还有权重（weight），权重用于描述该存取词项在文档中的地位。文档文件包含用户真正需要的文档记录。

pagenumber_ebook=309,pagenumber_book=294

图14.25　倒排文件的结构

在并行系统里，分割一个倒排文件可以提高负载均衡和检索效率。

参考文献［4］中提出了一种并行倒排文件的设计方案。

下面先讨论倒排文件的分割问题。

在一个全共享多处理器系统里，常使用磁盘阵列。构造多磁盘I/O系统的方法很多，有同步磁盘阵列，也有异步磁盘阵列。在同步磁盘阵列里，所有磁盘的转速和机械臂运动是同步的，因此可以采用同步方式为I/O请求提供服务。异步磁盘阵列与同步磁盘阵列类似，除了硬件上不支持同步旋转以外。无论如何，磁盘阵列可以作为一个整体为单个I/O请求提供服务。当然，所有的磁盘也可以独立响应于多个请求。这样，在应用级软件，独立的磁盘阵列可以提供I/O并行性。

参考文献［4］提出了索引文件和文档文件各自按其记录id分割的方案。而对其中间文件，即定位文件，文献中讨论和分析了分别按词项（term）和按文档标识（doc id）分割定位文件的情况。

参考文献［4］得出的结论：全共享体系结构适合中等规模的信息检索系统，或者使用无共享体系结构的若干节点。如果词项分布均匀，则按词项id分割，如果词项分布不均匀，则选文档id分割。

分布式数据库技术：并行索引支持

相关推荐