在大型数据集中对相同值进行分组的java高效解决方案

Question

在我的工作中，我负责制定并实施以下问题的解决方案：

给定一个包含30M条记录的数据集，从特定的数据集字段中提取（键，值）元组，按键和值对它们进行分组，存储每个键相同值的数量。将每个键的前5000个最频繁值写入数据库。每个数据集行以序列化XML的形式包含多达100个（键、值）元组

我提出了这样的解决方案（使用Spring-Batch）：

批处理作业步骤：

第1步迭代数据集行并提取（键、值）元组。在获得固定数量的元组后，将它们转储到磁盘上。每个元组都指向一个名为“/chunk-”的文件，因此指定键的所有值都存储在一个目录中。在一个文件中，值按顺序存储

第2步迭代所有“”目录，并将它们的区块文件合并为一组相同的值。由于这些值是按顺序存储的，因此合并它们的复杂度为O（n*logk）很简单，其中“n”是块文件中的值的数量，“k”是块的初始数量

第3步对于每个合并文件（换句话说，对于每个键），使用PriorityQueue顺序读取其值，以保持前5000个值，而不将所有值加载到内存中。将队列内容写入数据库

我花了大约一周的时间完成这项任务，主要是因为我以前没有使用过SpringBatch，而且我试图强调需要准确实现多线程部分的可伸缩性

问题是，我的经理认为这项任务太容易花太多时间。强>

问题是-您是否知道更有效的解决方案，或者更容易实施的效率更低？您需要多少时间来实施我的解决方案

我知道类似MapReduce的框架，但我不能使用它们，因为应用程序应该运行在一台简单的PC上，有3个内核和1GB的Java堆

提前谢谢你

UPD：我想我没有把我的问题说清楚。让我以另一种方式问：

考虑到这个问题，作为项目经理或至少是任务评审员，您会接受我的解决方案吗？你会花多少时间来完成这项任务

Answer 1

如果由于数据的大小，使用“简单”解决方案不是一个选项，那么我的下一个选择将是使用SQL数据库。然而，由于其中大多数都需要相当多的内存（并且在RAM中严重过载时会导致爬行），也许您应该将搜索重定向到类似NoSQL数据库（如MongoDB）的地方，这样即使在大部分基于磁盘的情况下也可以非常有效。（这是您的环境基本上需要的，只有1GB的堆可用）

NoSQL数据库将为您完成所有基本的簿记（存储数据、跟踪所有索引、排序），并且可能比您的解决方案更高效，因为所有数据在插入时都可能已被排序和索引，从而消除了对/chunk-文件中的行进行排序的额外步骤，合并它们等等

您将得到一个可能更易于管理的解决方案，它还允许您设置不同类型的查询，而不是仅针对这种特定情况进行优化

作为一名项目经理，我不会反对你目前的解决方案。它已经很快解决了问题。然而，作为一名架构师，我会反对，因为这个解决方案有点难以维护，并且没有使用经过验证的技术，这些技术基本上与您自己编写的代码部分相同。很难打败现代数据库的树和散列实现

Answer 2

哎呀，试着用旧式的方式在记忆中做这件事似乎没什么大不了的

我会先尝试这样做，然后如果内存不足，每次尝试一个键（按照@Storstamp的回答）

Answer 3

您的解决方案似乎合理有效，但我可能会使用SQL

在解析键/值对时，我将插入/更新到SQL表中。 然后我会查询表中的顶级记录

下面是一个仅使用T-SQL的示例（SQL 2008，但这个概念在大多数现代rdbms中都应该是可行的）

/START/和/END/之间的SQL将是您需要在代码中执行的语句

BEGIN
-- database table
DECLARE @tbl TABLE (
    k INT -- key
    , v INT -- value
    , c INT -- count
    , UNIQUE CLUSTERED (k, v)
)
-- insertion loop (for testing)
DECLARE @x INT
SET @x = 0
SET NOCOUNT OFF
WHILE (@x < 1000000)
    BEGIN
    --
    SET @x = @x + 1
    DECLARE @k INT
    DECLARE @v INT
    SET @k = CAST(RAND() * 10 as INT)
    SET @v = CAST(RAND() * 100 as INT)
    -- the INSERT / UPDATE code
    /* START this is the sql you'd run for each row */
    UPDATE @tbl SET c = c + 1 WHERE k = @k AND v = @v
    IF @@ROWCOUNT = 0
        INSERT INTO @tbl VALUES (@k, @v, 1) 
    /* END */
    --
    END
SET NOCOUNT ON
-- final select
DECLARE @topN INT
SET @topN = 50
/* START this is the sql you'd run once at the end */
SELECT 
    a.k
    , a.v 
FROM (
    SELECT 
        ROW_NUMBER() OVER (PARTITION BY k ORDER BY k ASC, c DESC) [rid]
        , k
        , v
    FROM @tbl
) a
WHERE a.rid < @topN
/* END */
END

Answer 4

您确定这种方法比预扫描XML文件提取所有密钥，然后为每个密钥反复解析XML文件更快吗？您在这个解决方案中执行了很多文件管理任务，这绝对不是免费的

由于您有三个内核，因此可以同时解析三个键（只要文件系统能够处理负载）