并行数据库系统：架构、数据放置与查询处理

### 并行数据库系统：架构、数据放置与查询处理 在当今数据爆炸的时代，并行数据库系统对于高效处理大规模数据至关重要。本文将深入探讨并行数据库系统的架构、数据放置策略以及并行查询处理的相关算法。 #### 1. 并行数据库系统架构 并行数据库系统主要有共享磁盘（Shared - disk）和无共享（Shared - nothing）两种架构。 ##### 1.1 共享磁盘架构 共享磁盘架构使用存储区域网络（SAN），它提供类似的功能，但具有更低级别的接口。SAN 使用基于块的协议，便于在块级别管理缓存一致性，从而提供高数据吞吐量，并且可以扩展到大量节点。 共享磁盘架构有三个主要优点： - **管理简单且成本低**：数据库管理员无需处理复杂的数据分区。 - **高可用性**：节点故障仅影响其缓存数据，磁盘上的数据仍可供其他节点使用。 - **良好的负载平衡**：任何请求都可由任何处理器 - 内存节点处理。 然而，它也存在缺点，主要是成本（由于使用 SAN）和可扩展性有限，对于非常大的数据库，缓存一致性协议可能导致潜在的瓶颈和开销。一种解决方案是像无共享架构那样进行数据分区，但这会增加管理的复杂性。 ##### 1.2 无共享架构 在无共享集群中，每个处理器使用直接连接存储（DAS），对其主内存和磁盘有独占访问权。每个处理器 - 内存 - 磁盘节点由自己的操作系统副本控制。 无共享架构具有以下特点： - **成本效益高**：能提供最佳的成本/性能比。 - **可扩展性强**：可以扩展到非常大的配置（数千个节点）。 - **可复用分布式数据库解决方案**：每个节点可视为分布式 DBMS 中的本地站点，许多为分布式系统设计的解决方案，如数据库分片、分布式事务管理和分布式查询处理都可复用。 不过，无共享架构也有挑战，它需要仔细对多个磁盘上的数据进行分区，添加新节点时可能需要重新组织和重新分区数据库以处理负载平衡问题，并且节点容错性较差，需要数据复制。 许多并行数据库系统原型都采用了无共享架构，如 Bubba、Gamma、Grace 和 Prisma/DB。一些主要的 DBMS 公司，如 IBM、Microsoft 和 Sybase，以及列存储 DBMS 供应商，如 MonetDB 和 Vertica，都为高端 OLAP 应用提供了无共享实现。此外，NoSQL DBMS 和大数据系统通常也使用无共享架构。 还可以采用混合架构，例如部分集群用于 OLAP 工作负载采用无共享架构，部分用于 OLTP 工作负载采用共享磁盘架构。例如，Teradata 在其无共享架构中支持“团簇”概念，即一组共享一组公共磁盘的节点，以提高可用性。 #### 2. 数据放置 数据放置在并行数据库系统中至关重要，它与分布式数据库中的数据分片有相似之处，但也有不同。 ##### 2.1 数据放置与分布式数据库的异同 - **相似点**： - **增加并行性**：分片可用于增加并行性，并行 DBMS 大多使用水平分区，垂直分片也可用于增加并行性和负载平衡。 - **数据本地化执行**：由于数据比程序大得多，执行应尽可能在数据所在的地方进行。 - **不同点**： - **无需最大化本地处理**：用户不与特定节点关联，因此无需在每个节点最大化本地处理。 - **负载平衡困难**：在大量节点的情况下，负载平衡更难实现，主要问题是避免资源争用，以免导致整个系统性能下降。 ##### 2.2 数据分区策略 并行 DBMS 中最常见的数据分区策略包括轮询（round - robin）、哈希（hashing）和范围分区（range - partitioning）。数据分区应随着数据库大小和负载的增加而扩展，分区程度（即关系分区的节点数）应是关系大小和访问频率的函数。增加分区程度可能导致数据放置重新组织。 在高度并行且进行数据分区的系统中，为了负载平衡，定期重新组织是必要的，除非工作负载相当稳定且更新较少。这种重新组织应对在数据库服务器上运行的编译查询保持透明，查询不应因重新组织而重新编译，并且应独立于数据位置。可以通过运行时系统支持对分布式数据的关联访问来实现这种独立性。 ##### 2.3 全局索引机制 一种实现关联访问的解决方案是在每个节点上复制全局索引机制。全局索引指示关系在一组节点上的放置位置，概念上是一个两级索引，主要按关系名聚类，次要按关系的某个属性聚类。 全局索引支持可变分区，每个关系可以有不同的分区程度。索引结构可以基于哈希或类似 B 树的组织。在这两种情况下，精确匹配查询可以通过单个节点访问高效处理。但使用哈希时，范围查询需要访问包含查询关系数据的所有节点；使用 B 树索引（通常比哈希索引大得多）可以更高效地处理范围查询，只访问包含指定范围内数据的节点。 例如，对于工程数据库中的关系 EMP(ENO, ENAME, TITLE)，通过全局索引和本地索引可以快速定位 ENO 值为“E50”的元素。 ##### 2.4 数据放置的问题及解决方案 - **数据分布倾斜**：数据分布倾斜可能导致不均匀分区，影响负载平衡。对于范围分区，可以进一步分割大分区；对于哈希分区，可以使用不同属性上的不同哈希函数。逻辑节点和物理节点的分离在此很有用，一个逻辑节点可以对应多个物理节点。 - **数据复制**：为了高可用性，需要进行数据复制。在并行 DBMS 中，可以采用一些简单的方法，如镜像磁盘架构，但节点故障时可能会影响负载平衡。为避免此问题，提出了几种高可用性数据复制策略，如 Teradata 的交错分区和 Gamma 的链式分区。 交错分区将备份副本进一步分区到多个节点，在故障模式下可以平衡主副本的负载，但如果两个节点故障，关系可能无法访问，并且重建主副本和维护副本一致性的成本较高。链式分区将主副本和备份副本存储在两个相邻节点，两个相邻节点同时故障的概率较低，在故障模式下可以平衡故障节点和备份节点的负载，并且维护副本一致性的成本较低。 #### 3. 并行查询处理 并行查询处理的目标是将查询转换为可以并行高效执行的执行计划，通过利用并行数据放置和高级查询提供的各种并行形式来实现。 ##### 3.1 并行数据处理算法 分区数据放置是数据库查询并行执行的基础。设计并行算法来高效处理数据库操作符（即关系代数操作符）和组合多个操作符的数据库查询是一个难题，需要在并行性和通信成本之间取得良好的平衡。 并行算法应最大化并行度，但根