开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 游戏开发 -> ArrayStore：A storage manager for complex parallel array processing -> 正文阅读

[游戏开发]ArrayStore：A storage manager for complex parallel array processing

标题：ArrayStore: A storage manager for complex parallel array processing

作者：Soroush E,Balazinska M,Wang D

Proceedings of the ACM SIGMOD International Conference on Management of Data (2011) 253-264

DOI: 10.1145/1989323.1989351

专业词汇：

array-processing：阵列处理

kd-tree（k-dimensional树的简称），是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。主要应用于多维空间关键数据的搜索（如：范围搜索和最近邻搜索）。K-D树是二进制空间分割树的特殊的情况。

canopy算法简介:Canopy算法是一种快速聚类技术，只需一次遍历数据即可得到结果，无法给出精确的簇结果，但能给出最优的簇数量。可为K均值算法优化超参数。

Abstract

我们介绍了 ArrayStore 的设计、实现和评估，这是一种用于复杂、并行阵列处理的新存储管理器。

ArrayStore 建立在多维数据存储领域的先前工作的基础上，但考虑了支持并行和更多样化工作负载的新问题，该工作负载不仅包括范围查询，还包括连接和复杂的用户定义函数等二元操作。

本文做出了两个关键贡献：

首先，本文检验了几个已存在的存储管理策略和阵列分区策略，并判断出哪种组合最适合阵列处理工作负载。
其次，本文提出了一种新的有效储存管理机制，使得允许满足以下条件的操作的并行处理：访问数据均在邻接分区

1. Introduction

当今的科学家正以前所未有的规模和速度生成数据。为了支持这些不断增长的数据管理需求，许多人主张应该摆脱关系模型并采用多维数组数据模型。主要原因是科学家通常使用数组数据，在关系之上模拟数组可能效率很低。

科学家也需要进行特定于数组的操作，如特征提取，smoothing和cross-matching。这些操作在关系数据库中都没有内置库。所以，许多支持多维阵列的引擎横空出世。为了管理今日大规模的数据集，阵列必须要被分片并且在互不包含的集群上进行操作。

本文将重点围绕以下问题展开：对一个并行阵列处理系统而言，合适的储存管理策略是什么？

与当今正在构建的大多数其他阵列处理系统不同，我们不是在关系 DBMS 之上构建阵列引擎，而是从头开始构建专门的存储管理器。

在本文我们考虑只读（read-only）阵列，并不考虑更新阵列的问题。

在存储和索引多维数据方面有很长的工作要做。存储数组的标准方法是将其划分为称为块的子数组，如图 1 所示。每个块通常是存储块的大小。对数组进行分块有助于缓解“维度依赖性”，其中从磁盘读取的块数取决于范围选择查询中涉及的维度，而不仅仅是范围大小。

Requirements

并行阵列储存管理器的设计必须回答以下的问题：

对于给定的工作负载，最有效的数组分块策略是什么？
存储管理器应如何在无共享集群中的机器上对块进行分区以支持并行处理？
在并行处理期间，如何有效地支持需要访问可能位于其他机器上的相邻块中的数据的数组操作？

先前的工作检查了其中一些问题，但仅在数组扫描和范围选择、最近邻居和其他“查找式”操作的背景下进行。

相比之下，我们的目标是支持科学界要求的更多样化的工作量。

特别是，我们旨在支持包含以下类型操作的工作负载：

（1）数组切片和切块（即提取数组子集的操作）

（2）数组扫描（例如，过滤器、regrids 和其他处理整个数组的操作）

（3）二进制数组操作（例如，连接、交叉匹配）

（4）需要访问的操作并行处理期间来自相邻分区的数据（例如，树冠聚类）

我们希望同时支持单线程和并行版本的以上操作。

Challenges

上述类型的操作对存储管理器提出了非常不同甚至矛盾的要求。事实上，小的、精细调整的块有利于阵列切割；但另一方面，当块太小并且并行处理时，用户定义的函数可能会产生开销（overhead），并且它们可能需要有效地访问相邻块中的数据。

不同的是，连接需要同时访问两个数组的对应部分，并且它们需要一种分块方法来促进这项任务。当并行处理时，所有这些操作也可能会受到倾斜的影响，其中某些组块的处理时间比其他组要长得多，从而减慢了整个操作。二元操作还需要将来自不同数组的匹配块放在同一位置，这可能会导致数据混洗（shuffle），从而增加 I/O 开销。

这些要求在稀疏矩阵上尤其难满足，因为数据在稀疏矩阵上不平均分布，这会造成糟糕的倾斜（skew）。

以坐标和值的无序列表形式的稀疏数组的表示形式也减慢了对数组块子集的访问，因为必须扫描所有数据点。因此，在本文中，我们专注于稀疏数组。我们假设这些数组上没有值索引。

Contributions

我们介绍了 ArrayStore 的设计、实现和评估，这是一种用于并行阵列处理的存储管理器。

ArrayStore 旨在支持对数组进行复杂而多样的操作，并在无共享集群中并行处理这些操作。 ArrayStore 以文献中的技术为基础，并引入了新技术。本文的主要贡献是回答了以下两个问题：

在不同的并行阵列处理工作负载下，分块和阵列分区策略的哪种组合可以实现最高性能？ （第 3.1 至 3.3 节）

与之前的工作一样，ArrayStore 将数组分成多维块，尽管我们认为块比之前的工作大得多（数百 KB 到数百 MB，而不是单个磁盘块）。

我们研究了四种不同的数组分块技术，如图 2 所示：常规块 (REG)、不规则块 (IREG) 和两级块（IREG-REG 和 REG-REG）。

在规则分块的情况下，每个数组索引的域被划分为统一规格的分区。对于不规则的块，我们创建块边界，以便每个块包含相同数量的数据（以字节为单位），从而减少并行处理数据块时可能出现的偏差。

图 3 说明了应用 REG 或 IREG 策略时每块数据分布的差异。最后，两级方法背后的基本思想是将数组拆分为规则或不规则块，然后将每个块进一步划分为更小的规则片段，我们称之为tile。
如何使算子能够在并行处理期间有效地访问相邻数组块中的数据？

我们开发了两种新技术，使操作符能够在并行处理期间有效地访问相邻块中的可变数量的数据。
- 第一种技术直接利用我们的两级 REG-REG 存储布局，使操作符能够根据需要有效地读取和处理尽可能多的重叠数据。
- 第二种技术为每个块存储越来越远的重叠数据的单独物化视图。

我们用第 4 节中介绍的一种简单但灵活的访问方法来包装上述技术。

我们用独立的C++系统实现了ArrayStore和一系列代表性操作，并且在两个科学领域的真实数据集上评估了这个系统。

对于第一个问题，我们展示了两级 REG-REG 策略在不同的工作负载下导致最佳的整体性能，并且需要最少的调整。实际上，它为我们工作负载中所有操作的单站点处理提供了高性能，并且可以进行组织以避免并行处理期间的倾斜和数据混洗。没有其他技术可以同时实现所有这些目标。
对于第二个问题，我们展示了 ArrayStore 的技术在不明确支持重叠数据或预定义数量的重叠数据存储在每个块中，甚至与每个块分开存储的情况下，ArrayStore 的技术的性能要高出 2 倍。

2. Problem statement

现在让我们从更一般的问题定义出发。

我们按以下的要求来定义一个数组：

给定一个离散的坐标集$S=S_1\times…\times S_d $,$ S_i,i\in [1,d]$是有限有序离散集合
该数组被定义在d维空间 $D=[I_1,..,I_d]$ ,其中 $I_i$ 是 $S_i$ 的子区间**（subinterval）**.
D 中的每个维度值组合定义一个单元格**（cell）**。
给定的数组中的所有的单元格具有相同的类型T，它是关系 DBMS 中的元组**（tuple）**。

ArrayStore 必须有效地支持第 1 节中概述的数组操作类型，我们通过为每种类型的操作提供一个或多个代表性运算符来形式化。我们在整篇论文中都使用这些运算符。

Array Scan（例如过滤器）

许多操作符处理数组的所有块chunk，在这种操作下，每个块可以独立处理。

过滤器filter， $A^{'} = F I L T E R (A, P)$ 是这种类型操作符的表示（假定没有基于值的索引）。这里，A是一个输入数组，P是一个谓词（predicate）

输出数组 $A^{'}$ 与 $A$ 具有相同维数，如果v是一个向量，那么 $\ contains \ A(v)\ if\ P(A(v))$ return true，否则A'包含null。一个并行的过滤器， $A' = P\_FILTER(A,P)$ ，可以使用一个分区策略R，通过将 A 划分为 N 组非重叠块来计算。

$FILTER(n_i,P)$ 被独立运用到每个分区 $n_i \in N$ . $A^{'}$ 是结果的集合。

Array Dicing（例如子样本）

我们也需要支持一元范围选择（或切块）运算符。

子样本（Subsample）, $A^{'} = S U B S A M P L E (A, P)$ ，是这种类型操作符的表示。这里，A是一个输入数组，P是一个谓词（predicate）

输出数组 $A^{'}$ 与 $A$ 具有相同维数，但是在维度的值方面要更少（就是某个维度取了其中一部分）

我们研究子样本，P以d维子区间的形式出现 $d = [i_1,...,i_d]$ ，选择所有单元格落在子区间上。

与过滤器类似，子样本可以彼此独立地处理数组的块，因此并行化是平凡（trivial）的。

Binary Array Operation（例如连接）

除了一元运算符外，我们需要支持二元操作比如JOIN.

连接(JOIN)， $B = J O I N (A, A^{'})$ ，其中A，A’，B都是定义在同样的d维域D上，并且每一个B的单元格都是A和A‘的拼接。

作为一个具体示例，这样的连接运算符可以将温度值数组与压力值数组相关联，输出包含每个维度值组合的两个值的元组。

例如，交叉匹配（cross-match）比较两个输入数组中彼此靠近的单元格值，而不是位于完全相同的位置。然而，将相应的数组块组合在一起并进行处理的关键要求仍然存在。这是我们要支持的关键操作类型。为了并行执行连接，我们采用的策略是对数组 A’ 重新分区，使得与 A 中的单元格对应的所有单元格在物理上位于同一位置。然后可以独立处理每对数组分区，并且可以合并结果。

Overlap Operation（例如聚类）

许多数组运算不能通过简单地对数组进行分区、独立处理其分区并合并结果来计算。相反，处理每个数组片段需要访问相邻片段中的数据。我们考虑了两种基于重叠的运算符：

（1）需要查看固定数量的相邻数据的运算符

（2）需要查看有界但不是固定数量的相邻数据的运算符。

我们使用树冠聚类作为前一类算子的代表，使用体积密度应用作为后者的代表。我们将在第 3.4 节和第 4 节中进一步描述它们。

Non-requirement

由于篇幅限制，在本文中，我们在我们的工作负载上不包括迭代操作，也不包括检查大量跨阵列延伸的输入单元以计算输出单元的值的操作：例如，数据聚类操作，其中一个簇可以跨越数组的很大一部分。

3. ArrayStore 存储管理

3.1 Basic Array Chunking

与先前关于多维数据存储管理的工作（参见第 6 节）一样，ArrayStore 采用将数组分解为称为块的片段并将这些块存储在磁盘上的方法。我们现在介绍文献中研究的两种类型的分块方案以及我们在 ArrayStore 中开发的两级策略。

Regular Chunks（REG)

将数组分成块的第一种方法是使用所谓的常规块 [13, 16]，其中所有块在坐标空间方面具有相同的大小。（可见图2）

Irregular Chunks（IREG）

现在已经提出了几种方案，其中阵列以较不规则的方式碎片化。

当块大小和形状被调整到工作负载时，不规则的块可以加速范围选择查询。虽然我们的目标不是针对此类特定查询调整存储，但我们会考虑不规则分块，因为它可能有助于减少并行数组处理中的偏差。

关键思想是对数组进行分块，使得每个块覆盖逻辑坐标空间的不同体积，但保存相同数量的数据 。现已提出用于创建此类块的一种方法是使用kd-tree，考虑数据分布，将多维空间分成越来越小的分区，以确保分区之间的负载平衡。如果块是不规则的，则必须对它们进行索引以支持对数组子集的有效访问。在我们的实现中，我们使用 R 树索引块。索引查找时间并非我们实验的瓶颈，故没有采用其它索引进行对比。

Two-level Chunks

对于上述任何一种策略，都会出现一个问题是适当的块大小。

大块有助于在从磁盘读取数据时分摊寻道时间。它们还有助于均摊开销与操作符处理数据块相关的任何潜在固定成本。然而，对于包含稀疏数据的数组，如果操作符只需要一个块的子集（例如，子样本或从相邻块访问数据的操作符），大块会增加所需的处理量，因为缺乏内部块结构会迫使运算符检查块内的所有数据点。

为了解决这些矛盾的要求，另一种方法是创建两级块。基本思想是将数组拆分成小的规则块，然后将它们组合在一起形成更大的块，这些块要么是规则的（REG-REG），要么是不规则的（IREG-REG），如图 2 所示。使用这种方法，较大的块是磁盘 I/O 的单位，而较小的块可以是阵列处理的单位。常规块和瓦片有效地支持单节点和跨节点的二元运算符，因为它们有助于跨两个阵列的匹配单元的协同定位和协同处理。相比之下，不规则块可以帮助消除并行处理期间的数据偏差。

在 [33, 38] 之前已经研究过两级分块，但仅作为将多个块放置在单个磁盘块上的容器。这种方法是 IREG-REG 的一种形式，因为规则的tile被分组为不规则的块。我们进一步推动了这个想法，不仅使用更大的块来分摊寻道时间开销（I/O 单位）和操作符开销，而且还通过利用这两者使操作符能够根据需要处理不同粒度的块（参见第 4 节）级结构来有效地支持重叠处理（参见第 3.4 节），并通过探索(REG-REG) 方法作为 IREG-REG 的替代方案。通过实验（见第 5 节），我们表明 REG-REG 不仅是两种策略中更简单的一种，而且在不同的工作负载下也能带来最高的性能。

3.2 Organizing Chunks on Disk

ArrayStore 中的每个数组都由一个数据文件和一个元数据文件表示。

数据文件包含实际的数组值。
元数据文件包含数组元信息，例如维度数、块总数，以及在常规分块的情况下沿每个维度的块数。元数据文件还包含重叠信息（参见第 3.4 节）。对于不规则的分块，块索引存储在单独的文件中。

在本文中，我们不研究磁盘上的块布局如何影响性能，因为它大多只对切块查询很重要[38]。对于稀疏数组，只有非空单元存储在块内，它们的顺序是任意的。因此，访问块中特定单元的唯一方法是顺序扫描块内的单元。这种方法避免了在每个块中创建索引的开销，我们展示了即使没有这样的索引，两级 REG-REG 存储管理也能实现高性能。

3.3 Organizing Chunks across Disks

为了支持并行阵列处理，ArrayStore可以在多个独立进程单元或节点（nodes，例如多个物理机或同一个机器上的多个进程）之间传递阵列块。

我们研究了几种阵列分区的性能策略包括

（1）随机（将每个块分配给随机选择的段）

（2）循环(round-robin)（以某种顺序迭代块并依次分配给每个段）

（3）范围（将数组拆分为 N块的不相交范围并将一个范围内的所有块分配给一个段）

（5）块循环（将数组分成M个规则块，每个块有N个块。以某种预定义的顺序迭代块的块并依次将它们分配给 N 个段中的每一个）。块循环类似于循环，但它有助于将密集阵列区域分布在更多节点（沿所有维度）。例如，考虑一个 2D 数组 $A_{4×4}$ ，它由 16 个块组成，按行主要顺序标记为 1 到 16（第一行包含块 {1,2,3,4}，第二行包含 {5,6,7,8 }，等等）。块循环在 4 个节点上对数组 $A_{4×4}$ 中的块进行分区，使得标记为 {1,3,9,11} 的块分配给第一个节点，而在round-robin中，该节点包含 {1,5,9 ,13}，第一个数组列中的所有块。我们不研究散列分区，因为它相当于随机或块循环分区的一种形式。

3.4 Overlap Data Support

在并行处理数组时，理想情况下，人们希望独立于其他数组段（甚至块或块）处理每个数组段，并简单地合并结果。然而，许多科学阵列操作无法使用这种简单的策略进行并行化。实际上，诸如回归或聚类之类的操作要求操作符考虑来自一系列相邻单元格的数据，以便生成每个输出单元格。为了说明这个问题和我们解决它的方法，我们使用树冠聚类 [1] 作为运行示例。在本节中，我们假设并行处理的单元是一个数组块。我们在第 4 节中回到基于tile和基于分段的处理。

Canopy 聚类是一种快速聚类方法，通常用于创建初步聚类，然后由更复杂的算法进一步处理。

Canopy 聚类可用于对稀疏阵列中的数据点进行聚类，例如 3D 天文学或 6D 流式细胞仪数据集。事实上，数据聚类在这两个领域都普遍使用。

Canopy算法流程

? （1）将数据集向量化得到一个list后放入内存，选择两个距离阈值：T1和T2，其中T1 > T2，对应示例图，实线圈为T1，虚线圈为T2，T1和T2的值可以用交叉校验来确定；

? （2）从list中任取一点P，用低计算成本方法快速计算点P与所有Canopy之间的距离（如果当前不存在Canopy，则把点P作为一个Canopy），如果点P与某个Canopy距离在T1以内，则将点P加入到这个Canopy（P点本身仍然在list上）；

? （3）如果点P与某个Canopy的距离在T2以内，则需要把点P从list中删除，这一步是认为点P此时与这个Canopy已经够近了，因此它不可以再做其它Canopy的中心了；

? （4）重复步骤2、3，直到list为空结束。

Problems with Ignoring Overlap Needs

为了并行运行树冠集群，一种方法是将阵列划分为块并独立处理块。问题在于，可能需要将块边界处的点添加到相邻块中的集群中，并且彼此在 T2 内的两个点（甚至来自不同的块）不应都产生新的冠层。解决这些问题的一种常见方法是执行后处理步骤。对于树冠聚类，第二步将在各个分区中发现的树冠中心进行聚类，并将点分配给这些最终的树冠。然而，正如我们在第 5 节中展示的那样，这样的后处理阶段会增加大量开销。

Single-Layer Overlap

为了避免后处理阶段，有些人建议为每个数组块从相邻块中提取一个重叠区域 $\epsilon$ ，将重叠部分与原始块一起存储，并在处理期间将两者提供给操作符。

在树冠聚类情形下，一个重叠大小 $T_1$ 可以帮助协调分区边界处的树冠。关键的见解是，与块大小相比，许多算法所需的重叠区域通常很小。

然而，这种方法的一个关键挑战是，即使是很小的重叠也会给多维数组带来很大的开销。例如，如果块沿每个维度增大 10%（每边仅 5%）以覆盖重叠区域，则 3D 块的总 I/O 和 CPU 开销为 33%，而 6D 块则超过 75%！

一个简单的优化是将重叠数据与核心数组分开存储，并按需提供给操作符。这种优化有助于不使用重叠数据的操作符。但是，需要重叠的算子仍然面临访问单个重叠区域的问题，该重叠区域必须足够大才能满足所有查询。

Multi-Layer Overlap Leveraging Two-level Storage

在 ArrayStore 中，我们提出了一种更有效的方法来支持重叠数据处理。我们在这里介绍我们的核心方法，并在下面介绍一个重要的优化。

算法一

ArrayStore 使操作符能够为块请求任意数量的重叠数据。无需提前配置最大重叠区域。每个算子可以使用不同数量的重叠数据。实际上，操作符可以为每个块使用不同数量的重叠数据。我们在第 5 节中表明，这种方法比上述所有策略都产生了显着的性能提升。

为了支持这种策略，ArrayStore 利用了它的两级数组布局。当操作符请求重叠数据时，它会在其当前块周围指定所需范围。在树冠聚类的情况下，给定一个块，该块覆盖沿每个维度 i 的区间 $a_i, b_i]$ ，操作符可以要求在区域 $a_i - T1, b_i + T1]$ 中重叠。为了满足请求，ArrayStore 查找与所需区域重叠的所有块（忽略操作符已经拥有的块）。它将它们加载到内存中，但只删除那些落在所需范围内的图块。它将所有图块组合成一个块并将其传递给操作符。算法 1 显示了相应的伪代码。

作为优化，操作符可以将所需的重叠指定为中间有孔的超立方体。例如，在图 4 中，树冠聚类首先请求范围 L1 内的所有数据，然后再请求 L2。对于其他块，它可能还需要 L3。

当将数组数据划分为段时（用于跨不同节点的并行处理），ArrayStore 会复制必要的块以提供预定义的重叠数据量。可以满足对额外重叠数据的请求，但需要节点之间的数据传输。

Multi-Layer Overlap through Materialized Overlap Views

虽然优于单层重叠，但上述方法存在两个低效率：

首先，当操作符请求相邻块内的重叠数据时，必须从磁盘读取整个块。
其次，重叠层是在tile的粒度上定义的。

为了解决这两个低效问题，ArrayStore 还支持物化重叠视图。物化重叠视图被定义为一组围绕块的洋葱皮层：例如，图 4 中的层 L1 到 L3。视图定义采用 $n,w_1,...,w_d)$ 形式，其中 n 是数字请求的层数，每个 $w_i$ 是沿维度 i 的层的厚度。单个数组可以存在多个视图。

为了处理重叠数据的请求，ArrayStore 首先选择覆盖整个请求数据范围的物化视图，并将导致读取和处理的额外数据量最少。从这个角度来看，ArrayStore 只加载那些覆盖请求区域的层，将它们组合成一个块并将该块传递给操作符。算法 2 显示了伪代码。

物化重叠视图会增加存储开销。如上所述，沿每个维度有 10% 的重叠会为 3D 阵列增加 33% 的总存储空间。重叠 20% 时，开销增长到 75%。在 6D 阵列中，相同的重叠分别增加了 75% 和 3X。然而，由于存储很便宜，我们认为这样的开销是合理的。我们将在 5.3 节进一步讨论物化重叠视图的选择。

4. ACCESS METHOD

ArrayStore 提供了一种单一的访问方法，它支持第 2 节中介绍的各种运算符类型，包括重叠数据访问。基本访问方法使操作符能够迭代数组块，但如何执行迭代是高度可配置的。

Array Iterator API

数组迭代器提供了表 4 中所示的五种方法。此 API 向操作符开发人员而非最终用户公开。我们的 API 为编程操作符假设基于块的模型，这有助于系统提供高性能。

访问方法

方法 open

在数组（或数组段）上打开一个迭代器。此方法将两个可选参数作为输入：数组维度上的范围谓词 (Range r)，它将迭代限制为与 r 重叠的那些数组块；第二个参数就是我们所说的打包率（PackRatio p）。它使操作符能够将迭代的粒度设置为“tiles”（默认）、“chunks”或“combined”。

tiles：非常适合受益于精细结构数据（例如子样本）的操作符。对于这个打包率，迭代器在每次调用 getNext() 时将单个tile作为块返回。
chunks：最适用于每个处理单元都会产生开销的运算符，例如处理重叠数据的运算符。
combined：将所有与 r 重叠的图块组合成一个块。如果 r 为“null”，则“combined”将底层数组（或数组段）的所有块作为一个块返回。如果数组段包含未连接或无法全部放入内存的块，则“combined”会迭代块而不组合它们。在下一节中，我们将展示诸如 join 之类的二元运算符如何从“组合”块的选项中受益匪浅。

方法 hasNext()、getNext() 和 close()

具有标准语义的功能，不再赘述。

方法 getOverlap(Range r)

作为单个块返回与给定区域重叠并围绕当前元素（平铺、块或组合）的所有单元格。

因为重叠数据仅在物化视图中指定的tile或重叠层的粒度上检索，所以可能会返回额外的单元格。可以为图块、块或一组图块/块请求重叠数据。但是，ArrayStore 仅在块或块组的粒度上支持物化重叠视图。这个设计决策背后的直觉是，在大多数情况下，需要处理重叠数据的操作符会为单个切片产生过多的开销，因此 ArrayStore 会针对整个块或更大块请求重叠的情况进行优化。

Example Operator Algotithms

我们通过展示如何实现几个有代表性的运算符（来自第 2 节）来说明 ArrayStore 的访问方法。

Filter

彼此独立地处理阵列单元。
给定一个数组段，过滤器操作符因此可以在没有任何参数的情况下调用open()，然后调用 getNext()，直到处理完所有图块。每个输入tile用于产生一个输出tile。

Subsample

给定一个数组段，子样本运算符可以调用 open?，其中 r 是数组上请求的范围，然后是一系列 getNext() 调用。每次调用 getNext() 都会返回一个图块。如果 tile 完全在 r 内，则可以将其原封不动地复制到输出，这是非常有效的。如果图块部分重叠范围，则必须对其进行处理以删除 r 之外的所有单元格。

Join

我们考虑结构连接, 其工作原理如下：对于输入数组中匹配位置的每对单元，根据两个输入单元元组计算输出单元元组。这种连接可以实现为一种嵌套循环连接（算法 3）。

算法3

连接迭代外部数组 array1 的块（它也可以一次处理整个外部数组段），最好是具有较大块的那个。对于每个块，它在内部数组 array2 中查找相应的图块，将它们全部检索为单个块（即选项“combined”），然后连接两个块。在我们的实验中，我们发现组合内部切片可以将缓存未命中减少一半，从而导致运行时间的类似减少。

上述所有三个运算符都可以使用相同的算法直接并行执行。唯一的要求是需要连接的两个阵列的块在物理上位于同一位置。因此，不同的数组分区策略会产生不同的连接性能结果（参见第 5 节）。

Canopy cluster

我们在 3.4 节中描述了树冠聚类算法。

在这里，我们展示了它在 ArrayStore 之上的实现。该算法迭代数组块。每个块都独立于其他块进行处理，并且将结果联合起来。对于每个块，当需要时，算法会递增地增长所考虑的区域（通过对 getOverlap() 的连续调用），以确保每次点 $x_i$ 开始一个新集群时，将 $x_i$ 的 T1 内的所有点都添加到集群中就像算法的集中式版本一样。因此，用于任何块的最大重叠区域为 T1。 T2 < T1 范围内的点不应同时产生新的树冠。在我们的实现中，为了避免重复报告跨分区边界的树冠，只返回质心在原始块内的树冠。

Volume-Density algorithm

体积密度算法最常用于在天文学中找到所谓的维里半径。它进一步证明了多层重叠的好处。给定多维空间中的一组点（即稀疏数组）和一组簇质心，体积密度算法找到每个质心周围的球体大小，使得球体的密度刚好低于某个阈值 T。在天文学模拟域中，数据点是粒子，球体密度由下式给出： $\frac{\sum mass(p_i)}{volume(r)}$ ， $p_i$ 是球中半径r内的一个点。这个算法受益于重叠：给定一个块内的质心 c，该算法可以围绕 c 增量增长球体，如果球体超出块边界，则请求越来越多的重叠数据。

5. Evaluation

5.1 Basic Performance of Two-Level Storage

table 2

总结：IREG 数组分块在数组切块查询上的性能并不优于 REG，并且在连接的情况下会显着降低性能。相比之下，两级分块策略，即使在两个级别上都有常规块，也可以提高某些运算符（切块查询）的性能，而不会损害其他运算符（选择查询和连接）。因此，后者似乎是单节点阵列处理的制胜策略。

5.2 Skew-Tolerance of Regular Chunks

5.3 Performance of Overlap Storage

6. Related work

MOLAP 系统将数据存储在多维数组中，但它们专注于一元聚合和选择查询，而我们考虑更广泛的操作集。当今的商业智能 (BI) 套件利用闭源专有 MOLAP 引擎解决方案，例如 Oracle Database OLAP Option 、Cognos PowerPlay 等来分析大型数据集。据我们所知，Palo是唯一一个开源的基于内存的 MOLAP 引擎，专门为电子表格数据存储和分析而开发。但是，Palo 并不是为大型数据库设计的。

许多现有的阵列处理系统使用常规平铺进行数据存储。其他支持用户定义的不规则tile 。然而，这些系统都没有研究不同切片策略对查询处理性能的影响，尽管它们确实考虑了磁盘和跨磁盘的不同切片布局以进行范围选择查询。

RasDaMan 是在关系 DBMS 之上实现的多维数组 DBMS。 Furtado 和 Baumann 研究了 RasDaMan 中不同平铺策略的性能（包括规则和不规则平铺）。然而，他们的研究仅限于扫描和不同类型的阵列切割操作。因此，他们的结论与我们的不同，因为他们发现调整到特定工作负载的任意切片优于常规切片。赖纳等人研究了 RasDaMan 中大规模多维数组的分层存储支持。他们的方法类似于两级 IREG-REG 分块策略。然而，他们的研究仅限于范围选择查询。

岛田等人提出了一种稀疏的分块方案数组，其中多个块被压缩并存储在单个物理页面中。这种方法类似于我们研究的两级 IREG-REG 存储系统。 Shimada 等人也引入了类似于 IREG 的“扩展块”。然而，这个早期的研究同样仅限于范围选择查询。

先前的工作研究了针对给定工作负载和常规分块的磁盘上的块形状、大小和布局的调整。这项工作与我们的工作是正交的，因为我们比较研究了常规 vs. 不规则 vs. 两级分块方案并支持重叠数据。

Seamons 和 Winslett 研究了定期平铺阵列的不同存储管理策略。特别是，他们建议将来自多个阵列的数据单独存储或交错存储在磁盘上。这种策略与我们在本文中研究的策略是正交的。他们还考虑了重叠数据的存储策略，提到了将重叠数据与核心数据一起或分开存储的选项。然而，他们的实施和评估只检查了同地场景，类似于 SciDB 。

存在许多用于索引多维数据的数据结构，包括 R-Tree 、KD-Tree 、KDB-Tree 、GammaSLK 、金字塔技术、Gamma 策略、RPST 等。所有这些索引将原始数据集组织成多维数据结构，以加速范围、包含和最近邻查询。相比之下，我们研究用于更多样化阵列操作的存储管理技术。

7. Conclusion

我们介绍了 ArrayStore 的设计、实现和评估，这是一种用于复杂并行阵列处理的存储管理器。为了高效处理，ArrayStore 将数组划分为块，我们展示了具有规则块和规则块 (REG-REG) 的两级分块策略可以为不同的操作集带来最佳和最一致的性能。单个节点和无共享集群中。 ArrayStore 还使操作符能够在并行处理期间访问来自相邻数组片段的数据。我们提出了两种新技术来支持这种需求：一种利用 ArrayStore 的两级存储布局，另一种使用额外的物化视图。这两种技术都显着优于不提供重叠或仅提供预定义的单个重叠层的方法。在来自两个科学领域的真实查询和真实数据上，整体性能提升高达 2 倍。

ArrayStore 的设计侧重于第 2 节中的工作负载。它不考虑迭代操作或数组更新，我们的常规平铺只读存储可能无法很好地提供这些服务。它也没有考虑检查数组中的输入单元以计算输出单元的值的操作。此类操作不会从重叠中受益，其中一些可能难以使用基于块的 API 进行编码。最后，我们没有研究在块内索引数据的影响，这可能会进一步加速一些操作。所有这些考虑都是有趣的未来工作。
的两级分块策略可以为不同的操作集带来最佳和最一致的性能。单个节点和无共享集群中。 ArrayStore 还使操作符能够在并行处理期间访问来自相邻数组片段的数据。我们提出了两种新技术来支持这种需求：一种利用 ArrayStore 的两级存储布局，另一种使用额外的物化视图。这两种技术都显着优于不提供重叠或仅提供预定义的单个重叠层的方法。在来自两个科学领域的真实查询和真实数据上，整体性能提升高达 2 倍。