8

我的工作是为以下问题开发和实施解决方案：

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

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

批处理作业步骤：

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

步骤 2.遍历所有 '' 目录并将它们的块文件合并为一个分组相同的值。由于这些值是按顺序存储的，因此对于 O(n * log k) 复杂度而言，将它们合并是微不足道的，其中“n”是块文件中的值的数量，“k”是块的初始数量。

步骤 3.对于每个合并文件（即每个键），使用PriorityQueue顺序读取其值以维护前 5000 个值，而不将所有值加载到内存中。将队列内容写入数据库。

我在这个任务上花了大约一周的时间，主要是因为我以前没有使用过 Spring-Batch，并且因为我试图强调需要准确实现多线程部分的可伸缩性。

问题是我的经理认为这项任务太容易了，无法在上面花费那么多时间。

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

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

先感谢您！

UPD：我想我没有清楚地表达我的问题。让我换个方式问：

鉴于问题并作为项目经理或至少是任务审阅者，您会接受我的解决方案吗？你会花多少时间来完成这项任务？

4

4 回答 4

1

您确定这种方法比对 XML 文件进行预扫描以提取所有键，然后为每个键一遍又一遍地解析 XML 文件更快吗？你在这个解决方案中做了很多文件管理任务，这绝对不是免费的。

由于您有三个核心，您可以同时解析三个键（只要文件系统可以处理负载）。

于 2012-10-15T10:42:53.837 回答
1

您的解决方案似乎合理且有效，但是我可能会使用 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
于 2012-10-15T15:18:50.327 回答
0

哎呀，尝试仅在内存中进行的老式方法似乎并不需要太多工作。

我会先尝试这样做，然后如果内存不足，请尝试每次运行一个键（根据@Storstamp 的回答）。

于 2012-10-15T15:49:01.630 回答
0

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

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

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

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

于 2012-10-15T18:53:39.180 回答