关系数据库从灵活性中受益匪浅。它们在一组不断变化的硬件资源中实施，这些资源配置以满足其存储和处理的要求。

这种灵活性对科学数据库特别有吸引力，因为它们的用户通常有不可覆盖的存储模型，只有在可用空间耗尽时才能删除数据。这导致数据库定期增长，并按比例扩展其硬件。此外，科学数据库经常将其数据存储为空间查询优化的多维数组。这给弹性无共享数据库上的集群和倾斜数据放置带来了几个新的挑战。

在这项工作中，我们设计并实现了阵列数据库的灵活性。我们从两个方面解决了这一挑战：

• 确定何时扩展数据库集群
• 如何确定如何数据

在这两个步骤中，我们都提出了增量方法，对数据和节点集的影响最小，同时保持高性能。我们介绍了使用闭环控制系统逐渐增加阵列数据库硬件的算法。在集群中添加节点后，我们进行了优化 n 维数组的数据放置。许多弹性分区器通过增量重新组织阵列，只将数据重新分配到新节点。

科学数据库结合这两种工具，可以高效无缝地管理其单调增加的硬件资源。

在本节中，我们将简要描述我们实现和评估数据库弹性的架构。这个架构的原型是为SciDB设计的。它在无共享架构上执行以数组为中心的分布式查询。

阵列数据库针对复杂分析进行了优化。除了select-project-join查询之外，该系统还使用众所周知的数学密集型运算和用户定义的函数来满足科学工作负载。 奇异值分解、矩阵乘法和快速傅立叶变换是此类查询的示例。 他们的数据访问模式是迭代的和空间的，而不是索引查找和顺序扫描。

SciDB拥有无共享架构，它支持分布式数据存储的扩展。这种松散耦合（coupled）的结构对于高可用性和灵活的数据库管理至关重要。 该方法是弹性的自然选择——这样的系统可以简单地横向扩展以满足工作负载需求，并且开销有限。

• 科学家更喜欢无覆盖存储模型。 他们想让他们的实验易于重现。 因此，他们保留了所有之前的工作，即使它是错误的，从而导致数据存储单调增长。

SciDB 中的存储和查询处理完全建立在数组数据模型之上。 每个数组都有维度和属性，它们一起定义了这个数据结构的逻辑布局。 例如，用户可以定义 (x, y) 点的二维数组来描述图像。

数组具有一个或多个命名维度。 维度指定一个连续的数组空间，可以是声明的范围，也可以是无界的，就像在时间序列中一样。 维度值的组合指定包含任意数量的标量属性的单元格的位置。 数组的声明列出了一组命名属性及其类型，就像在关系表声明中一样。

单个数组单元格可能是空的或被占用的，只有非空的单元格存储在数据库中。 因此，数组在磁盘上的占用空间是它包含的单元数的函数，而不是声明的数组大小。

科学家们经常在空间上查询他们的数据，根据它们在阵列空间中的位置来利用单元格之间的关系。 因此，块或 n 维子数组是该数据库的 I/O 和内存分配单元。 在每个数组维度中，用户定义一个块间隔或步幅。 这指定逻辑单元中块的长度。 物理块大小是可变的，并且对应于它存储的非空单元的数量。 单个块的大小约为数十兆字节 。

SciDB 在磁盘上垂直分区其阵列； 每个物理块只存储一个属性。 该组织已被证明可以为关系分析实现一到两个数量级的加速。 数组数据库利用相同的原理； 他们的查询通常会访问数组属性的一小部分。

数组内的数据分布要么倾斜，要么不倾斜。 后者在其每个块中具有大致相同数量的单元格。 相比之下，倾斜数组有一些数据块密集，而另一些数据块很少或没有数据。 图 1 显示了该数据库中的一个数组示例。

它的SciDB 架构是： A < i : i n t 32   , j : f l o a t > [ 1 : 4 , 2 , y = 1 : 4 , 2 ] A<i:int32\ , j:float>[1:4,2,y=1:4,2] A<i:int32 ,j:float>[1:4,2,y=1:4,2] 数组 A 是一个 4x4 数组，每个维度的块间隔为 2。 该数组有两个维度：x 和 y，每个维度的范围为 1..4，包括 1,4。

此模式有两个属性：

• 一个整数 i
• 一个浮点数j

它存储 6 个非空单元格，第一个包含 (1, 1.3)。 由于垂直分区，属性被单独存储。

这个数组是倾斜的——数据主要位于中心，其边缘是稀疏的。 为了在两个节点之间平衡这个数组，数据库可能会将第一个块分配给一个主机，并将剩余的三个存储在另一个主机上。 因此，每个分区将正好为三个单元提供服务。

总之，数组数据模型旨在服务于多维数据结构。 它的垂直分区、n 维分块针对复杂分析进行了优化，这些分析通常在空间上查询数据。 其无共享架构使 SciDB 可扩展用于分布式阵列存储和并行查询处理。 在下一节中，我们将讨论这个数据库如何服务于两个真正的科学工作。

在本节中，我们研究了弹性科学数据库的两个激励用例，并为每个用例提供了一个基准。

• 第一个包括用于模拟地球表面的卫星图像。
• 第二个使用海洋船舶轨迹为海洋学服务。

我们还介绍了源自用例的循环工作负载模型。 该模型使我们能够评估我们的弹性阵列分区器并评估竞争供应计划的优点。

MODIS（中分辨率成像光谱仪）是美国宇航局卫星上的一种仪器，每 1-2 天记录一次整个地球表面的图像。它测量了 36 个光谱带，科学家们用这些光谱带来模拟大气、陆地和海洋。

我们专注于 MODIS 数据的前两个波段，因为模拟可见光的查询经常引用它们，例如计算土地的植被指数。 每个数组（或“带”）具有以下模式：

Band<si_value:int, radiance:double, reflectance:double, uncertainty_idx:int, uncertainty_pct:float, platform_id:int, resolution_id:int>[time=0,*,1440, longitude=-180,180,12, latitude=-90,90,12]

Band有三个维度：纬度、经度和时间。 时间以分钟为单位，并以一天为间隔进行分块；经纬度则以12°为间隔进行分块。

我们选择这个模式是因为它的块的平均磁盘占用空间为 50 MB； 此块大小针对高 I/O 性能进行了优化。该阵列包括测量值（ s i s_i si​ 值、辐射度、反射率）、来源（平台 ID、分辨率）和来自传感器的不确定性信息。 总之，它们提供了进行地球表面建模实验所需的所有原始信息。 在我们的实验中，每天插入一次记录，这是根据 MODIS 收集数据的速率而设计的。

MODIS 具有均匀的数据分布。 如果我们将 lat/long 空间划分为 8 个大小相等的子数组，则块的平均集合大小为 80 GB，标准偏差为 8 GB。 数据非常稀疏，只有不到 1% 的单元被占用。 之所以会出现这种稀疏性，是因为科学家为数组的维度选择了较高的固定精度，这些维度由整数索引。

我们的第二个案例研究涉及使用美国海岸警卫队的自动识别系统的船舶航迹。 我们从美国国家海洋和大气管理局的海洋地籍库中研究了 2009-2012 年； 美国政府将这些数据用于沿海科学和管理。 国际海事组织要求所有大型船舶将配备一个 AIS 转发器，该转发器以设定的频率发射广播。 这些消息由附近的船只、监听站和卫星接收。 海岸警卫队从美国各地海岸、湖泊和河流的哨所监控 AIS。 船轨数组定义为：

Broadcast<speed:int, course:int, heading:int, ROT:int, status:int, voyageId:int, ship_id:int, receiverType:char, receiverId:string, provenance:string>[time=0,*,43200, longitude=-180,-66,4, latitude=0,90,4]

Broadcast存储在纬度、经度和时间的 3D 数组中，其中时间分为 30 天间隔，并以分钟为单位记录。 纬度和经度维度包括美国和周边水域。 每个广播都会发布船舶的位置、速度、航向、转弯率、状态（例如，在港口、在航）、船舶 ID 和航次 ID。 广播阵列是 AIS 的大部分数据，但它也有一个支持船只阵列。 该数据结构只有一个维度：容器 ID。 它识别船舶类型、尺寸（即长度和宽度）以及是否载有危险材料。 容器阵列很小 (25 MB)，并在所有集群节点上复制。

AIS数据被分块为 4°×4°×30 days的子数组，它们存储的大小极度偏斜。这些块的中值大小为 924 字节，标准偏差为 232 兆字节。 近 85% 的数据仅位于 5% 的块中。 这种偏斜是船舶聚集在主要港口附近的产物。 相比之下，MODIS 只有轻微的偏斜； 前 5% 的块仅占数据的 10%。 AIS 每 30 天向数据库注入一次新航迹，反映 NOAA 每月报告此数据的速率。

我们的工作负载有两个基准：

• 一个测试传统分析。第一个是 Select-Project-Join，评估数据库在以单元为中心的查询上的性能，这代表了数据的子集化。
• 另一个测试面向科学的操作。 科学基准测量每个工作负载的特定领域处理的数据库性能，这些工作负载通常在空间上访问数据。

两个基准测试都更频繁地引用最新数据，将测量结果“烹饪”成数据产品。 单个基准查询可在 [4] 中找到。

MODIS 基准扩展了 MODBASE 研究，该研究基于对环境科学家的采访。 它的工作量首先询问阵列空间和其单元格的内容，生成派生阵列，例如归一化差异植被指数（NDVI）。 然后，它构建了几个地球科学特定的预测，包括森林砍伐模型和将稀疏数据重新网格化为更粗糙、更密集的图像。

海洋管理局使用 AIS 来研究环境。 他们的研究包括海岸线侵蚀建模和估计鲸鱼迁徙路径中的噪音水平。 我们通过研究按地理区域分组的船舶密度、生成发出消息的船舶类型的地图以及提供不同船舶的最新列表来评估他们的用例。

MODIS 选择测试返回其纬度/经度空间的第 1/16 部分，位于波段 1 阵列的左下角。 该实验测试了数据库在执行高度可并行化的运算符时的效率。

AIS 从广播阵列中提取数据，将其过滤到休斯顿港周围的交通密集区域，以评估数据库应对偏差的能力。

对于 MODIS，我们的基准基于统一的随机样本计算波段 1 的辐射属性的分位数； 这是一种并行排序，它总结了阵列光测量的分布。

AIS 计算来自广播数组的不同船舶标识符的排序日志。 这两个操作都测试了集群对非平凡聚合的反应。

MODIS 通过连接两个波段来计算植被指数，这两个波段在阵列空间中具有相同位置的单元。 它在最近一天的数据中执行。

AIS 生成最近船舶 ID 及其类型（例如，商业、军事）的 3D 地图。 它通过 ship id 属性将 Broadcast 与 Vessel 数组连接起来。

MODIS 的基准测试采用过去几天极地冰盖波段 1 的光照水平的滚动平均值进行环境监测。

AIS 计算船舶运动轨迹的粗粒度地图，以识别易受海岸侵蚀的位置。 两者都旨在评估维度空间上的分组聚合。

遥感用例在亚马逊雨林的纬度/经度和 NDVI 上执行 k-means 聚类，以识别森林砍伐区域。

船舶跟踪工作负载使用非参数密度估计对船舶航行模式进行建模； 它为随机选择的船舶样本识别 k 最近邻，标记高流量区域以供进一步探索。

卫星图像工作负载执行最近一天植被指数的窗口聚合，即 MODBASE 查询。 该聚合通过评估每个像素周围的窗口来生成图像就绪投影，其中其样本空间与其他像素的样本空间部分重叠，从而生成平滑的图片。

海上交通工作量通过根据每艘船的最新轨迹和速度绘制未来几分钟的每艘船的位置来预测船舶碰撞。

正如我们所见，弹性阵列数据库随着时间的推移单调增长。 科学家定期收集新的测量值，将它们插入数据库，并执行查询以继续他们的实验。 为了捕捉这个过程，我们的工作负载模型由三个阶段组成：数据摄取、重组和处理。 我们将此模型的每次迭代称为工作负载周期。

每个工作负载都从一个空的数据存储开始，然后逐渐填充新的块。 两种工作负载都会定期插入数据，促使数据库定期向外扩展。 尽管系统会定期接收新的块，但由于 SciDB 的无覆盖存储模型，它永远不会更新先前存在的块。

在第一阶段，数据是分批接收的，每次插入都是可变大小的。 例如，航运有季节性模式； 它在假期达到顶峰。 大量数据加载在科学数据管理中很常见 [12]，因为科学家经常以固定的时间间隔从传感器收集测量值，例如当卫星经过其基站时。 插入被提交给一个协调节点，它将传入的块分布在整个集群上。

在这个阶段，数据库首先确定它是否为传入的插入配置不足，即它的负载是否超过了它的容量。 如果是这样，provisioner 使用第 5 节中的算法计算要添加的节点数量。然后重新分配预先存在的块，最后使用第 4 节中的算法插入新的块。

在确定何时以及如何向外扩展时，系统使用存储作为负载的替代品。 磁盘大小近似于每个工作负载查询使用的 I/O 和网络带宽，因为两者都是其输入大小的函数。 此外，存储偏差强烈影响数据库执行的并行度，使其成为工作负载资源需求和性能的可靠指标。

摄取新数据后，数据库将执行查询工作负载。 在这一步中，科学家们继续他们的实验，查询新数据和先前的结果，他们可能会存储他们的发现以供将来参考，进一步扩大数据库的存储空间。

第五部分的弹性规划器(elasticity planner)既为数据库分配了足够的存储容量，又试图最小化与弹性相关的开销。我们以节点小时为单位评估供应计划的成本。

考虑数据库已经执行了 Φ \Phi Φ个工作负载循环，在第 i i i次循环有： N i N_i Ni​个节点提供服务，插入时间为 I i I_i Ii​,重组时间为 r i r_i ri​，查询负载延迟为 w i w_i wi​。因此这种配置的成本是： c o s t = ∑ i = 1 ϕ N i ( I i + r i + w i ) cost = \sum^\phi_{i=1}N_i(I_i+r_i+w_i) cost=i=1∑ϕ​Ni​(Ii​+ri​+wi​) 该指标将每次迭代的时间相加，并将其乘以集群节点的数量，从而计算出此工作负载使用的有效时间。 通过估计此成本，供应商可以估算出正在进行的工作负载的硬件要求。

精心设计的数据放置对于有效管理弹性阵列数据库集群至关重要。 一个好的分区器可以在其节点之间均匀地平衡存储负载，同时最小化在集群扩展时重新分配块的成本。 在本节中，我们将介绍几种算法来管理不断增长的数据集合在无共享集群上的分布。

在这项工作中，我们提出并评估了各种范围和哈希分区器。 范围分区将数组存储在维度空间中，这加快了分组聚合查询和连续访问数据的查询，这在线性代数中很常见。 此外，许多科学工作负载在空间上查询数据，并从保留其输入的逻辑布局中受益匪浅。 哈希分区非常适合细粒度的存储规划。 它一次放置一个块，而不必在数组空间中细分平面。 因此，等连接（equal-join）和大多数“令人尴尬的并行”操作最好由散列分区提供。

弹性和全局分区器揭示了本地和全局最优分区计划之间的权衡。

• 大多数全局分区器保证将相同数量的块分配给每个节点，但是它们这样做的重组成本很高，因为它们在大多数或所有集群节点之间转移数据。 此外，这类方法没有倾斜感知； 它们只考虑逻辑块，而不是物理存储大小。
• 弹性数据放置动态地修改如何将块分配给扩展集群中的节点。 它还可以有效利用网络带宽，因为数据在集群中的一小部分节点之间移动。

表 1 确定了多维数组的弹性数据放置的四个特征。 这些特性中的每一个都加速了数据库的集群横向扩展、查询执行或两者兼而有之。 4.2 节中的分区方案实现了这些特征的一个子集。

具有增量横向扩展的分区器在数据库扩展时对其阵列执行本地化重组。 在这里，数据仅从先前存在的节点传输到新节点，而不是全局重新平衡。 我们所有的算法，除了Uniform Range，都具有这个特性。

细粒度分区，其中分区器一次分配一个块给每个主机，用于分散存储倾斜，这通常跨越相邻的块。 哈希算法以块级粒度细分其分区空间，以实现更好的负载平衡。 然而，这种方法是有代价的，因为它们不会在每个节点上保留数组空间以进行空间查询。

许多弹性分区器也具有倾斜感知能力，这意味着它们使用当前的数据分布来指导每次横向扩展时的重新分区计划。 倾斜数组的块的大小差异很大。 因此，当需要重组时，弹性分区器会识别负载最重的节点并将它们拆分，将大约一半的内容传递给新的集群添加。 这种重新平衡是抗倾斜的，因为它会根据每个主机上的存储空间来评估在哪里拆分数据的分区表。

具有 n 维分区的方案根据其逻辑空间对数组进行细分。 在同一主机上存储连续块减少了空间操作的查询执行时间。 然而，这种效率通常以负载平衡为代价，因为分区器将阵列空间划分为较宽的范围。

我们现在介绍几个用于弹性阵列的分区器，每个分区器都具有表 1 中的一个或多个特性。这些分区器针对各种工作负载进行了优化，从对均匀分布数据的简单逐点访问到对倾斜阵列的空间查询 。

使用有效负载平衡对数组进行范围分区的一种方法是仅追加策略。 在插入期间，分区器将每个新块发送到第一个未满容量的节点。 协调器维护在接收主机上分配的存储总和，当其当前目标已满时溢出到下一个。 Append 类似于传统的范围分区，因为它存储按插入顺序排序的块。 该分区器同样适用于偏斜和均匀的数据分布，因为它根据存储大小而不是逻辑块计数调整其分区表。

Append 的分区表由一个范围列表组成，每个节点一个。 插入新数据时，数据库会在现有数组的末尾生成块。 添加新节点对于 Append 来说是一个常数时间的操作； 它在第一次写入时在分区表中创建一个新的范围条目。

这种方法很有吸引力，因为它对数据重组的开销最小。

• 优势：当添加一个新节点时，它会从前一个节点停止的地方开始，这对于频繁扩展的集群来说是一个有效的选择。
• 劣势：如果集群一次添加多个节点，Append 的性能会很差，因为它只是逐渐使用新主机。 此外，它仅按一个可能的维度（时间）进行分组，使用插入顺序，因此任何其他维度都不太可能并置。 并且，如果更频繁地访问新数据，附加分区器的查询性能可能会很差，例如将原始测量值转换为数据产品的“烹饪”操作。 第 3.3 节中的植被指数就是这样一个例子。

对于在整个数组中均匀分布的数据，一致哈希 [24] 是一种有益的分区策略。 这个哈希图分布在一个圆的圆周上。 节点和块被散列为一个整数，该整数表示它们在圆边缘上的位置。 分区器通过从 c i c_i ci​ 的散列位置开始跟踪边缘来确定块 c i c_i ci​ 的目标节点。 该块被分配给它遇到的第一个节点。

当插入一个新节点时，它会在循环哈希映射上对自己进行哈希处理。 然后分区器跟踪它的映射，将块从几个预先存在的节点重新分配给新添加的节点。 这会产生一个分区布局，每个节点的块数大致相等。 它在恒定时间内执行查找和插入操作，与散列操作的持续时间成正比。

一致性哈希力求向每个节点发送相同数量的块。 但是，它不能解决存储偏差。 它的块到节点分配独立于数组的数据分布。 它也不适合空间查询，因为它的分区使用哈希函数，而不是数据在数组空间中的位置。

可扩展哈希被设计用于分布偏斜数据以进行点查询。 该算法从一组哈希桶开始，每个节点一个。 当集群向外扩展时，分区器会拆分负担最重的节点的哈希桶，将它们的内容部分重新分配给新主机。

该算法通过评估其哈希值的位（从最低到最高有效）来确定块的主机分配。 如果分区器有两台服务器，则第一台主机为所有具有最后一位等于零的散列的块提供服务，而剩余的块存储在另一个节点上。 随后的重新分区将哈希空间按越来越重要的位切分。

这种方法使用当前的数据分布来计划其重新分区操作，因此它是倾斜感知的。 因为它指的是一个平面分区表，增量哈希没有考虑到数组的多维结构。 这以牺牲空间查询性能为代价，使数据分布更加均匀。

对于点倾斜，数组空间的小片段具有大部分数据，我们提出了一个基于希尔伯特空间填充曲线的分区器。 这条连续曲线序列化了数组的块顺序，使得曲线上相邻块之间的欧几里德距离最小化。 该算法基于此顺序将块范围分配给每个节点，因此它以比接近维度范围切片的方法更精细的粒度进行分区。

希尔伯特曲线最基本的形式只适用于二维正方形； 我们的分区器对矩形使用它的通用实现。 与可扩展散列一样，当集群达到容量时，它会在其范围的中位数处拆分负担最重的节点。 该方案以块的粒度执行此操作，这可能会导致比维度范围更好的负载平衡。 这种方法针对倾斜进行了优化，因为它一次拆分一个最热的分区，并且它只通过重新组织最需要的节点来增量地这样做。 它通过沿空间填充曲线序列化块来促进空间查询。

四叉树是一种树数据结构，它递归地将二维空间细分为 n 维范围。 之所以如此命名，是因为在每次重新分区时，它都会对过载的分区进行四等分。 该方案表示为一棵树，其中每个非叶节点正好有四个孩子[20]。 四叉树是更通用的二进制空间分区器的一个例子，它可以容纳任意数量的维度。 如果四叉树分区器为其每个叶节点分配一个主机，则该算法将无法进行增量横向扩展。 每次节点达到容量时，数据库都需要将其内容重新分配到四个节点上，其中三个是新节点。

如果分裂主机是四叉树中的单个叶子节点，则分区是四等分的。 然后，该算法识别总大小最接近主机存储一半的四分之一或相邻四分之一对，并将该子阵列标记为新分区。 如果主机已经被分割，那么最接近减半存储的相邻对将成为一个新分区。 这种方法使每个节点的分区恰好位于四叉树的一个级别，从而使连续块更有可能存储在一起。 它还直接对偏斜区域做出反应，在负担最重的维度上分裂。

增量四叉树具有高效的横向扩展操作，因为在每次重新分区中，它仅根据其拆分将数据发送到新配置的节点。 它针对空间查询进行了优化，因为它根据块在数组空间中的位置移动块。 这种方案是倾斜感知的，因为在每次横向扩展操作时，它都会细分具有最大存储负载的主机

K-d 也是对倾斜的多维数据进行范围划分的有效策略。 当将新机器添加到集群时，该算法会拆分负担最重的主机。 一开始，分裂服务器沿着阵列的第一个维度找到其存储的中点，表示一个平面，其两侧有相同数量的单元。 拆分器将其范围削减到中间值，将其一半内容重新分配给新主机。 在随后的拆分中，分区器循环遍历数组的维度，使得每个平面被拆分的次数大致相等。

K-d 树将其分区表存储为二叉树。每个主机由一个叶子节点表示，非叶子节点是数组空间中的分区点。 为了定位一个块，该算法从根节点遍历树。 如果根不是叶子，则分区器将块的位置与其分割点进行比较，然后前进到分割点一侧的子节点。 查找继续，直到它到达叶节点。 此操作以相对于集群节点数的对数时间完成。

图 2 展示了一个 K-d 树，它首先将一个数组划分为两个节点； 它在x轴维度的中点 5 上被分割。左侧以比右侧更快的速度积累细胞，促使分区器在第二次分割时切割其 y 轴（以y=2为分界线）。接下来，随着 N 3 N_3 N3​ 加入集群，K-d 树再返回垂直切割（x轴）。

• 优势：这种倾斜感知方案限制了不受最近插入影响的节点的数据移动。 它只拆分最完整的节点，使重组变得简单并限制网络拥塞。 这种方法以及所有其他“拆分”算法确实对未倾斜数据有限制。

• 劣势：如果集群的节点数不是 2 的幂，则分区器会遭受存储倾斜，因为它的某些分区将是较少拆分的结果。 例如，一个具有 6 个节点的数据库均匀分布 200 GB 的数据将有两个节点托管 50 GB，四个节点托管 25 GB。 下一个算法Uniform Range，解决了这个缺点。

我们提出了一个 n 维范围划分的替代公式，以服务于未倾斜的数组。 该算法首先构建一个高大的平衡二叉树来描述数组的维度空间。 数据结构与图 2 中的相同，但要求每个叶节点距树根的深度相等。 如果分区器的高度为 h，则它有$ l = 2^h$ 个叶节点，其中 l l l 远大于预期的集群大小。 当然，可以根据需要增加 h h h，并且分区器通过更高的 h h h 值提供更好的负载平衡。

对于由 n 个主机组成的集群，Uniform Range 将其 l l l 个叶节点分配在大小为 l / n l/n l/n 的块中，其中叶节点按其在树中的遍历顺序进行排序。 这可以维护多维集群访问，而不会影响负载平衡。 当集群向外扩展时，它会重新平衡，为每个主机计算一个新的 l / n l/n l/n 切片。

当一个节点被添加到分区器时，它会遍历所有的叶子节点，并根据新的 l / n l/n l/n 更新每个节点的目标节点。 这是一个线性时间运算，与 l 成正比。

与增量方法相比，这种方法具有较高的重组成本，因为它在每次横向扩展时执行全局重组。 新节点可能会创建级联移动，尤其是在将多个主机添加在一起时。 Uniform Range 为其数组维护 n 维聚类，尽管它不支持倾斜感知。

回顾一下，我们检查了我们为弹性数组数据库扩展的几种分区算法。 每个都针对空间或点查询进行了优化。 几乎都是增量的； 因此，他们只通过向新添加的主机发送块来本地化他们的重新分配。

在本节中，我们研究了一种为扩展阵列数据库配置机器的方法。弹性规划器旨在为用户提供一致的服务水平，因为他们查询不断增长的数据体。我们首先引入一个控制循环来确定何时扩展出，以及多少节点。随后解决了该算法对特定工作负载的调整。

为阵列数据库及其查询确定正确的硬件资源是一项重要挑战。 集群需要足够大以保持高性能，同时又不能不必要地过度配置。如果分布式数据库急切地扩展，在每次横向扩展时添加多个节点，系统将节省重组时间，并以更高的供应成本获得更好的吞吐量。 相反，如果规划器一次注入一个节点，它将更频繁地重新平衡数据，尽管使用的服务器更少。 供应商通过最小化第 3 节中公式 2 定义的运营成本来量化这种权衡。

为了应对这一挑战，我们提出了一种领先的楼梯算法，如图 3 所示。它的名称是指观察到弹性阵列数据库以一系列离散步骤扩展其集群大小，就像在攀爬时的高度折痕。 当需求曲线和供应曲线首次相交时，集群已达到容量。 供应商现在对其下一步进行建模。 计划者通过比例微分 (PD) 控制环 根据最后 s 工作负载周期预测未来需求。 使用这个预计的需求，它增加了 k 个节点，从而提高了数据库服务下 p 个工作负载迭代的容量。

这种方法模拟扩展数据库以满足当前需求以及预测的负载增加的速率。通过稳定地增加集群，数据库享有稳定的服务质量。系统从不合并节点，因为它的资源需求单调增长。这背离了事务性工作负载的弹性管理，并且在硬件的波峰和波谷之间摇摆不定。

供应商使用 PD 控制器的扩展来建模需求，它在每批插入时评估该扩展。 该控制回路是一种通用反馈机制，用于调节系统，例如家用恒温器和汽车巡航控制。 PD 回路围绕一个设定点旋转，该设定点定义了其所需的系统状态。 对于弹性数据库，这是一个为接下来的 p 个工作负载周期提供足够资源的供应级别。 其过程变量为监管机构提供反馈，而工作负载的当前存储需求提供了这一指导。

PD控制器根据两个因素——比例和导数来计算下一步的高度 k k k。比例项 π \pi π表示当前的配置错误（provisioning error），通过将传入插入后的存储需求减去集群的当前容量之间的差异进行量化。在该模型中，数据库由 N 个同构节点组成，每个节点的容量为 c GB。然而，这种方法很容易通过将单个容量分配给节点来推广到异构集群