现代机器学习（ML）系统通常使用随机梯度下降（SGD）来训练模型。然而，SGD依赖于随机的数据顺序来收敛，通常需要进行完整的数据洗牌。对于在数据库内存储的ML系统和使用HDD和SSD等块寻址二级存储的大型数据集的深度学习系统来说，这种完整的数据洗牌会导致I/O性能低下，数据洗牌的时间甚至可能比训练本身还长。为了平衡SGD的收敛速率和其I/O性能，现有的研究提出了几种数据洗牌策略，但是这些策略的性能或收敛速率不够理想。本次为大家带来VLDBJ 2024的论文《Stochastic gradient descent without full data shuffle:
with applications to in-database machine learning and deep learning systems》。
随机梯度下降（SGD）是一种常用的迭代优化算法，在机器学习系统中被广泛使用，对于内存数据库ML和深度学习系统来说，SGD需要随机的数据顺序才能收敛，但通常数据存储的顺序并不能保证是随机的。目前的研究发现当数据以聚类顺序（如正负标签聚类）存储时，直接对数据运行顺序扫描会大大减慢SGD的收敛速度。一个常见的解决方案是在原始数据上进行完整的数据洗牌。然而，当数据存储在HDD和SSD等块寻址的二级存储设备上时，要么在SGD期间进行大量的随机访问，要么将数据随机访问一次并在洗牌后进行SGD运行都是非常耗时的，例如，在本文的实验中，使用'ORDER BY
RANDOM()'对50GB数据集进行洗牌大约需要50分钟；而在数据库中进行扩展性数据集的洗牌甚至在一天之内也无法完成。此外，有时在数据库中进行数据洗牌是不可行的，原地洗牌可能会影响其他索引，而在数据副本上进行洗牌会导致两倍的存储开销。同样，诸如HDFS和Lustre等分布式文件系统不支持随机访问小数据元组，这将严重降低I/O性能。为了解决SGD的数据洗牌问题，目前的研究已经在内存数据库ML或深度学习系统的背景下提出了几种数据洗牌策略。TensorFlow采用了一种基于Sliding-Window
Shuffle的洗牌策略，不断将数据加载到缓冲区，并从缓冲区中随机获取数据进行SGD。Bismarck提出了一种“多路径蓄水池取样”（MRS）的洗牌策略，利用两个线程同时更新模型。一个线程使用蓄水池取样顺序地读取数据，而另一个线程从填充了抽样数据的小型内存缓冲区中读取数据。尽管这些策略提高了I/O性能，但它们在收敛方面存在缺陷。如图1所示，Bismarck和TensorFlow提出的两种策略在面对聚簇数据时都存在较低的准确性。相比之下，对数据进行训练前进行一次Shuffle，即与“MADlib/Bismarck（洗牌一次）”对应的曲线，可以解决这种收敛问题，但是如图1所示，会引入显著的开销。
图1 SVM在不同标签聚类的希格斯数据集上的收敛速度和性能“Shuffle once” and “Epoch shuffle”：Shuffle Once策略对所有数据元组执行洗牌，要么就地进行，要么将经过洗牌的元组存储为副本。然后在这个洗牌副本上执行SGD。对于Epoch Shuffle，它在每个训练Epoch之前对训练数据集进行洗牌。“ No Shuffle” ：No Shuffle策略不执行任何数据洗牌，也就是说，SGD算法在每个epoch中运行给定的数据顺序。“Sliding-Window
Shuffle Shuffle”：Sliding-Window
Shuffle策略利用Sliding-Window
Shuffle 来执行部分数据洗牌，TensorFlow使用了这种策略。它包括以下步骤:（1）分配一个Sliding-Window，并在扫描元组时将其填充到窗口中。（2）从窗口中随机选择一个元组，并将其用于SGD计算。窗口中所选元组的槽然后由下一个传入的元组填充。“Multiplexed
reservoir sampling shuffle”：使用两个并发线程读取元组并更新共享模型。第一个线程依次扫描数据集并执行储层采样。采样的元组存储在缓冲区B1中，丢弃的元组用于SGD。第二个线程循环遍历来自另一个缓冲区B2的元组，用于SGD，其中B2中的元组简单地从B1复制。PyTorch的洗牌策略使用纯储层采样，这是MRS Shuffle的弱版本(即收敛速度低于MRS Shuffle)，因此，文章使用MSR Shuffle代替储层采样作为基线。
图2 对于标签聚类和特征有序数据集，使用相同缓冲大小(数据集大小的10%)的MRS和Sliding-Window
Shuffle，使用不同数据洗牌策略的SGD的收敛率。现有的数据洗牌策略虽然较基线相比已经有了很大的进步，但仍有很大的改进空间，论文提出了一种简单而新颖的数据洗牌策略：CorgiPile，关键思想是以下的两级分层洗牌机制：首先随机选择一组块，并将它们放入内存缓冲区中:然后随机洗牌缓冲区中的所有元组，并将它们用于SGD计算。
算法1说明了CorgiPile的细节。在每个epoch，CorgiPile运行以下步骤：1. (采样)从n个数据块中随机抽取n个块，不进行替换，并将n个块加载到缓冲区中。注意：作者使用不进行替换的抽样(sample without
replacement是为了避免每个epoch多次访问同一个元组，这样可以更快收敛，是大多数ML系统中的标准做法。2. (Shuffle)对缓冲区中的所有元组进行洗牌。作者用u表示一个有序集合，它的元素是被洗牌元组在第s个epoch的下标。ψs的大小是bn，其中b是每个块中元组的个数。ψs(k)是ψs中的第k个元素。
3. (更新)通过使用ψs,中的洗牌索引扫描每个元组来执行梯度下降，从而产生更新规则：其中∇fψs(k)(·) 是与指数为ψs(k)的数据样本相关的函数的梯度，ηs是在历元s处梯度下降的学习率。文章初始化
，并在一个epoch里对所有k = 1,…,bn进行参数更新。性能：相较于只需要顺序的I/O的无Shuffle，CorgiPile要复杂一些，需要随机访问块，将这些块中的所有元组复制到缓冲区中，对缓冲区内的元组进行Shuffle。如果块大小足够大，则随机存取和顺序存取的I/O性能接近，如图3。CorgiPile会在缓冲区复制和内存洗牌时产生额外的开销。然而，这些IO开销可以通过双缓冲等标准技术隐藏起来。正如本文将在PostgreSOL上的实验中所展示的那样，与最有效的Shuffle Once基线相比，优化版本的CorgiPile仅产生11.7%的额外开销。
如3.2所述，CorgiPile包括三个部分：块级Shuffle、元组级Shuffle、SGD计算，相应地，论文设计了三个物理运算符：BlockShuffle、TupleShuffle、SGD。运算符的实现如图4所示。(1)BlockShuffle（随机访问区块的运算符）: 该操作符首先通过PostgreSQL的内部函数RelationGetNumberOfBlocks()获得总页数。然后通过BN=page_num*page_size/block_size计算BN块的数量。之后，它对区块索引[0，…，BN-1]进行洗牌，并得到洗牌块id，其中每个块对应一批连续的表页。对于每个打乱的块id，它使用heapgetpage()读取相应的页面，并将每个获取的元组返回给TupleShuffle操作符。BlockShuffle操作符类似于PostgreSQL的Scan操作符，不过Scan操作符是顺序读取页面而不是随机读取。(2)TupleShuffle（用于缓冲一批块并对其元组进行Shuffle）: 它首先分配一个缓冲区，然后通过调用其ExecTupleShuffe,即getNextO，从BlockShumle操作符中逐个提取元组。每个拉出的元组都会被转换成SGDTuple对象，然后复制到缓冲区中。一旦缓冲区被填满，它就会打乱被缓冲的元组，这类似于PostgreSQL中的Sort操作符的工作方式。之后，将打乱的元组一个接一个地返回给SGD运算符。(3)SGD（用于SGD计算地运算符）: 首先在ExecInitSGD0中初始化ML模型，然后在ExecSGD0中执行SGD计算。在每个epoch,ExecSGDO)逐个从TupleShuffle中提取元组，并运行SGD计算。一旦处理完所有元组，一个epoch就结束了。然后它必须重新洗牌并重新读取元组使用PostgreSQL的重新扫描机制，为下一个epoch创建元组。具体来说，在每个epoch之后，SGD调用TupleShuffle的ExecReScan()来重置缓冲区的I/O状态。它进一步调用BlockShuffe的ExecReScan()来重新Shuffle块id。在此之后，SGD运算符可以通过ExecSGD()为下一个历元重新读取封隔元组。这类似于PostgreSOL的NestedLoopJoin中多个表/索引扫描的行为。
图4 PostgreSQL中的CorgiPile，其中包含三个新的操作符和“双缓冲”优化为了减少缓冲区复制和洗牌引入了额外的开销，论文使用双缓冲策略，如图三所示，为具有两个缓冲区的TupleShuffle启动两个并发线程。一个写线程负责从BlockShuffle中提取元组到一个缓冲区中，并对缓冲的元组进行洗牌,另一个读线程负责从另一个缓冲区读取元组，并将它们返回给SGD。一旦一个缓冲区满了，另一个缓冲区被SGD占用,这两个缓冲区就会交换。因此，数据加载(即块级和元组级改组)和SGD计算可以并发执行，从而减少了开销。论文已经将CorgiPile集成到PostgreSQL中，用户可以使用以下的SQL语句进行查询。SELECT * FROM table TRAIN BY model
WITH params参数包括learning_rate=0.1、max_epoch_num=20、block_size=10MB，在每一轮运行结束后输出各种度量，包括训练损失、准确度、训练时间。3.2 PyTorch中的多进程CorgiPile论文已经在PyTorch中实现了多进程CorgiPile作为一个新的CorgiPileDataset API：train_dataset = CorgiPile
Dataset(dataset_path, block_index, other_args)Train_loader =
torch.utils.data.DataLoader(train_dataset, other_args)Train(train_loader, model,
other_args)与使用初始数据集类似，用户只需要使用必要的参数初始化CorgiPileDataset，然后在PyTorch提供的DataLoader API中像往常一样使用它。train()方法不断地从DataLoader中提取一批元组，然后执行小批量SGD。多进程CorgiPile可以实现与单进程CorgiPile类似的随机数据排序。（1）块分区:作者首先将数据集分区成块。在并行/分布式环境中，通常将数据集存储在基于块的并行/分布式文件系统上，如HDFS、AmazonEBS和Lustre。例如，ETH Euler集群使用Lustre，它以块(默认为4Mb)读取/写入数据，并且不允许用户存储/读取大量小文件，如原始图像日录中。因此，对于使用130万张原始图像训练150GB的ImageNet，这些图像无法放入内存，需要将这些图像转换为二进制数据文件，如广泛使用的可迭代数据集TFRecords，并在训练前将其存储在Lustre中。此外，作者使用文件系统或索引工具(如PyTorch-TFRecord)提供的块信息，构建块索引来标识每个块的开始/结束。如果数据集本身包含元组索引(例如，PyTorch中的map风格的数据集)，也可以根据元组索引将数据集划分为块。（2)块Shuffle:每个进程随机抽取BN/PN块，其中BN为块数，PN为进程数。作者在CorgiPileDataset AP中实现了块Shuffle。在每个epoch的开始，它首先洗牌块索引，然后将指数分成PN部分。第i个进程只读取第i部分中有索引的块。(3)元组Shuffle:每个进程首先在内存中分配一个小缓冲区,然后不断地将块读入缓冲区。一旦缓冲区满了。进程就会对被缓冲的元组进行Shuffle。这是在CorgiPileDataset中作为iter()方法实现的，该方法将块读入缓冲区，打乱它们的元组，并逐个返回打乱后的元组。这里的缓冲区大小比单进程CorgiPile中使用的要小得多——如果在单进程CorgiPile中设置bufer size= BS，则可以为多进程CorgiPile中的每个本地缓冲区选择buffer size= BS/PN。(4)SGD计算:经过块Shuffle和元组Shuffle后，每个进程对洗牌后的元组执行小批量SGD。与单进程CorgiPile在batch size=bs的情况下对整个数据集执行小批量SGD不同，多进程CorgiPile中的每个进程对批大小较小(bs/PN)的部分数据集执行小批量SGD，并在每批中使用梯度同步更新模型。如图5所示，在每批处理之后，进程将使用通信协议(例如，AllReduce)同步/聚合梯度:然后，每个进程更新其ML模型的本地副本。这个过程被封装在train()方法中，该方法每次从CorgiPileDataset读取一批元组后自动执行梯度计算/通信/同步和模型更新。
数据集：对于in-DB ML，论文采用以下7个数据集；对于深度学习，论文采用具有10个类的cifar-10数据集和具有100个类的ImageNet进行数图像分类。
模型及参数：对于in-DB ML系统的评价，作者主要训练了两种流行的广义线性模型，逻辑回归(LR)和支持向量机(SVM)；对于深度学习系统进行评估，作者在cifar-10数据集上使用了经典的VGG19和ResNet18模型，在ImageNet数据集上使用了更复杂的ResNet50模。模型参数包括学习率、衰减因子和最大epoch数。作者使用0.95的指数学习率衰减，将in-DB ML的epoch数设置为20，深度学习模型的epoch数设置为50，仅对于mageNet上的ResNet50，将epoch的数量设置为100，并按照官方的PyTorch-ImageNet代码每30个epoch衰减学习率。CorgiPile参数：缓冲区大小和块大小。作者在{1%，2%，5%，10%}中实验了不同范围的缓冲区大小，块大小为选择{2 MB，10 MB，50 MB}。PostgreSQL参数：将work mem设置为最大RAM大小并调整shared buffers。4.2 in-DB ML系统对CorgiPile评估图6显示了CorgiPile在所有系统中收敛速度最快，并且同时到达与最佳Shuffle Once基线的收敛精度相当，通常在1-3个epoch内，因为数据元组的数量很大。特别是CorgiPile比MADlib快2.9~12.8倍，比Bismarck快2.0~4.7倍，当数据存储在HDD和SSD上时收敛到相同的精度。
图6 在PostgreSQL中，对于HDD和SSD上的集群数据集，采用不同数据变换策略的SGD的端到端执行时间对于所有被检查的数据集，Shuffle Once和CorgiPile之间的最终测试准确率差距低于1%，如表3所示。
表3 Shuffle Once和CorgiPile的最终测试准确率
图7显示了所有策略在聚类数据集上的收敛率，其中Sliding-Window Shuffle、MRS和CorgiPile都使用相同的缓冲区大小(整个数据集的10%)。如图7所示，Sliding-Window Shuffle的精度较低，而MRS Shuffle仅在epsilon和yfcc上达到与Shuffle Once相当的精度，但在其他数据集上受到影响。作者进一步在特征排序数据集上执行这些策略，结果如图8所示。尽管No Shuffle、MRS和Sliding-Window Shuffle在特征有序数据集上实现了更高的精度，但它们与Shuffle Once和CorgiPile在higgs、susy和criteo数据集上仍然存在差距。仅对于具有合成特征的epsilon[59]和具有图像提取特征的yfcc，它们可以达到与Shuffle Once和CorgiPile相似的收敛速度。
图8 LR和SVM在不同变换策略下对特征排序数据集的收敛速度(1)对于具有内存I/0带宽的小数据集，CorgiPile的平均每历元时间与No Shuffle相当。(2)对于具有磁盘I/0带宽的大型数据集，CorgiPile的平均每历元时间比No Shuffle慢1.1倍，也就是说，由于缓冲区复制和元组Shuffle，它最多会产生11.7%的额外开销。(3)通过使用双缓冲优化，与单缓冲版本相比，CorgiPile每个epoch的执行时间可以缩短23.6%。上述结果表明，与最佳的无Shuffle基线相比，具有双缓冲优化的CorgiPile可以引入有限的开销(每个epoch的执行时间延长11.7%)。
图9 在PostgreSQL中，使用Bismarck (No
Shuffle)， CorgiPile和CorgiPile使用单个缓冲区的SGD的平均每个epoch时间图10a报告了CorgiPile在两个最大的数据集上的收敛行为，这些数据集具有不同的缓冲大小:数据集大小的1%，2%和5%。可以看到，CorgiPile只需要2%的缓冲区大小来维持与Shuffle一次相同的收敛速度。在1%缓冲的情况下，它的收敛速度只比Shuffle Once稍微慢一点,但达到了同样的final accuracy。图10b显示，由于更高的I/O带宽(吞吐量)，当块大小从2MB增加到50 MB时，每个epoch的时间会减少。然而，10MB和50 MB之间的时间差是有限的(小于10%)，因为使用10 MB已经实现了可能的最高I/O带宽(HDD上的130 MB/s)。
图10 缓冲区大小和块大小对CorgiPile的影响作者使用小批量SGD对聚类数据集执行LR和SVM，图11展示了这两种模型在SSD上的PostgreSQL中的端到端执行时间。其结果与标准SGD相似。CorgiPile实现了与Shuffle Once相当的收敛速度和准确性，但收敛速度比Shuffle once快1.7-3.3倍。其他策略，如No Shuffle和仅块Shuffle，要么收敛精度较低，要么收敛速度较慢。
图11 在PostgreSQL中使用mini-batch SGD
(batch_size = 128)对SSD上的集群数据集进行LR和SVM的端到端执行时间与其他Shuffle策略相比，图12和13分别展示了batchsize=128时不同Shuffle策略对聚类数据集和特征有序数据集的收敛率。观察到，在聚类和特征有序数据集上，CorgiPile(以及最好的Shuffle Once基线)在收敛速度和/或模型精度方面通常显著优于Sliding-Window ShuffleShuffle和MRS Shuffle。这个结果表明，CorgiPile也适用于小批量SGD，而其他Shuffle策略则不是最优的。
图12 对于聚类数据集，使用小批SGD (batch_size =
128)的LR和SVM的收敛速度
图13 对于特征有序数据集，使用mini-batch SGD (bs
= 128)的LR和SVM的收敛速度图14显示了连续YearPredictionMSD聚类数据集的线性回归和10类mini8m聚类数据集的sofmax回归的端到端执行时间，SSD上的批处理大小不同。CorgiPile再次实现了与Shuffle Once相似的收敛速度和模型精度，但收敛速度快1.6-2.1倍。
图14 在不同批大小(bs = 1和bs = 128)的情况下，对于SSD上的集群数据集，PostgreSQL中线性和softmax回归的端到端时间论文在集群中使用8个gpu和16个CPU内核的多进程CorgiPile在ImageNet上训练ResNet50模型。论文评估了两种不同的块大小(5 MB和10 MB)，批大小设置为512张图像，所有进程的总缓冲区大小为整个数据集的10%，将每个进程的数据加载线程数设置为两个，学习率初始化为0.1，每30个epoch衰减一次，乘法因子为0.1。从图15a、b可以看出，CorgiPile的收敛速度比Shuffle Once快1.5倍，CorgiPile的收敛精度与Shuffle Once相似。可以看到5 MB/10 MB块大小的CorgiPile的收敛速度与Shuffle Once相当。虽然块大小为10 MB的CorgiPile在前30个epoch的收敛速度低于Shuffle Once，但在随后的epoch中可以赶上并收敛到相似的精度。
图15 ResNet50在不同数据变换策略下对聚类ImageNet数据集的收敛速度论文使用单个GPU在cifar-10图像数据集上运行深度学习（VGG19和ResNet18）模型，同时设置缓冲区大小为整个数据集的10%，块大小设置为每个块100张图像。如图16所示，CorgiPile达到了和Shuffle
Once基线一样的收敛速度和准确度，而其他的策略的准确度都较低。
图16 对集群的10类cifar-10图像数据集，具有不同数据变换策略和批处理大小的深度学习模型的收敛速度作者在特征有序的cifar-10数据集上进一步重复实验，结果如图17所示，CorgiPile的收敛速度与Shuffle Once相当，而No Shuffle和MRS Shuffle的准确率较低或收敛速度较慢。与Shuffle Once和CorgiPie相比，只有Sliding-Window Shuffle可以达到相似的收敛速度。
图17 对于特征排序的10类cifar-10图像数据集，具有不同数据变换策略和批大小的深度学习模型的收敛速度论文提出了CorgiPile数据Shuffle策略，用于在基于块寻址的二级存储系统上进行高效的随机梯度下降（SGD）计算。它采用了两级分层的Shuffle机制，避免了完整数据Shuffle的计算和存储开销，同时保留了类似完整数据Shuffle的SGD收敛速度。论文对CorgiPile的收敛行为进行了理论分析，并将其集成到了PostgreSQL和PyTorch中。实验评估表明，与最先进的基于数据库的机器学习和深度学习系统相比，CorgiPile在统计和硬件效率方面都表现出了显著优势。| 重庆大学计算机科学与技术专业2022级本科生，重庆大学Start Lab团队成员。主要研究方向：时空数据查询、数据压缩 | 
|
重庆大学时空实验室（Spatio-Temporal Art Lab，简称Start Lab），旨在发挥企业和高校的优势，深入探索时空数据收集、存储、管理、挖掘、可视化相关技术，并积极推进学术成果在产业界的落地！年度有3~5名研究生名额，欢迎计算机、GIS等相关专业的学生报考！
图文｜刘明星
编辑｜徐小龙
审核｜李瑞远
审核｜杨广超
