对同一大数据集的查询

Question

假设我有一个非常大的数据集(数十亿条记录)，一个不适合一台机器的数据集，我想有多个未知的查询(这是一个服务，用户可以选择数据集的某个子集，我需要返回该子集的最大值)。

对于计算本身，我在考虑Spark或类似的东西，问题是我将有大量的IO/网络活动，因为Spark将不得不不断从磁盘重新读取数据集并将其分发给worker，而不是，例如，当集群启动时，Spark在worker之间划分数据，然后请求每个worker对某些记录(例如，按其编号)进行工作。

那么，对于这里的大数据人员，你们通常会做什么？只是让Spark为每个请求重做读取和分发？如果我想做我上面所说的，我别无选择，只能写一些我自己的东西？

Answer 1

如果查询是已知的，但子集是未知的，则可以预先计算许多较小的数据窗口/切片的最大值(或其他运算符)。这为您提供了一个小的、易于查询的排序索引，它可能允许您计算任意子集的最大值。如果子集没有在切片的开始和结束位置整齐地开始和结束，您只需要处理“最外层”的部分切片就可以得到结果。

如果查询是未知的，您可能需要考虑将数据存储在MPP数据库中或使用OLAP多维数据集(Kylin，Druid?)根据具体情况而定；或者您可以将数据存储为列格式，如Parquet，以便进行有效的查询。

Answer 2

以下是基于OP对我的另一个答案的评论中的问题描述的预先计算的解决方案：

百万个条目，每个条目有3k个名称->数字对。给定百万个条目的子集和名称的子集，您需要该子集中所有条目的每个名称的平均值。因此，百万个条目的每个可能子集(每个可能大小)都太多，无法计算和保存。

预计算

首先，我们将数据拆分成更小的“窗口”(分片、页面、分区)。

假设每个窗口包含大约10k行，每行包含大约20k个不同的名称和3k (名称，值)对(选择窗口大小可能会影响性能，并且您可能更适合使用较小的窗口)。

假设每个名称约24字节，值为2字节，则每个窗口包含10k*3k*(24+2字节)=780MB的数据，外加一些我们可以忽略的开销。

对于每个窗口，我们预先计算每个名称的出现次数，以及该名称的值的总和。有了这两个值，我们可以计算任意一组窗口中名称的平均值：

Average for name N = (sum of sums for N)/(sum of counts for N)

下面是一个包含更少数据的小示例：

Window 1
{'aaa':20,'abcd':25,'bb':10,'caca':25,'ddddd':50,'bada':30}
{'aaa':12,'abcd':31,'bb':15,'caca':24,'ddddd':48,'bada':43}

Window 2
{'abcd':34,'bb':8,'caca':22,'ddddd':67,'bada':9,'rara':36}
{'aaa':21,'bb':11,'caca':25,'ddddd':56,'bada':17,'rara':22}

Window 3
{'caca':20,'ddddd':66,'bada':23,'rara':29,'tutu':4}
{'aaa':10,'abcd':30,'bb':8,'caca':42,'ddddd':38,'bada':19,'tutu':6}

预先计算的窗口1 'index‘，包含总数和计数：

{'aaa':[32,2],'abcd':[56,2],'bb':[25,2],'caca':[49,2],'ddddd':[98,2],'bada':[73,2]}

这个“索引”将包含大约20k个不同的名称和每个名称的两个值，或20k*(24+2+2字节)=560KB的数据。这比数据本身少了一千倍。

查询中

现在让我们将其付诸实践:给定一个跨越100万行的输入，您将需要加载(1M/10k)=100个索引或56MB，这很容易放入一台机器的内存中(见鬼，它将放入您的智能手机的内存中)。

但是，由于您正在聚合结果，因此您可以做得更好；您甚至不需要一次加载所有索引，您可以一次加载一个索引，对值进行过滤和求和，然后在加载下一个索引之前丢弃索引。那样的话，你只需要几兆字节的内存就可以做到。

更重要的是，对于任何一组窗口和名称，计算时间不应超过几秒钟。如果名字按字母顺序排序(另一个有价值的预优化)，你会得到最好的性能，但即使是没有排序的列表，它的运行速度也应该足够快。

转角案例

剩下的唯一要做的就是处理输入跨度与预计算窗口不完全对齐的情况。这需要对输入跨度的两个“末端”进行一点逻辑处理，但是可以很容易地将其构建到代码中。

假设每个窗口包含从星期一到星期日的恰好一周的数据，但是您的输入指定了一个从星期三开始的周期。在这种情况下，您必须加载从第一周的周三到周日的实际原始数据(如上所述的几百兆字节)，以便首先计算每个名称的(count，sum)元组，然后在其余的输入跨度中使用索引。

这确实增加了计算的一些处理时间，但由于上限为2*780MB，它仍然非常适合在一台机器上运行。

至少我会这么做。