3

我们有大数据集（大约 1.91 亿条记录，将会增长），每条记录都包含过滤器的值（11 个过滤器 - 日期时间和整数值），以及一些额外的数据（成本）。例如：

Depature City = 1
Arrival City = 5
Country Id = 7
Check In Date = 2013-05-05
    ... etc

Cost 1250
    ... etc

我们有一个带有 11 个过滤器的搜索界面。在每个过滤器中，用户可以选择：一个值、一组值、所有值。

每个过滤器都有不同的可能值集，它可以从 4 到 5000 个值不等。

搜索结果必须按成本升序排序，有分页（每页50个结果）

每个搜索查询必须在 100 毫秒内完成，通常预计为 50-70 个请求/秒（最多 200 个）。

数据会经常变化，但数据变化的速度优先级较低，比搜索这个过程可能慢。

组织此类搜索引擎的最佳方式是什么？内存中的数据（我们尝试了一些树算法）、Map-Reduce（Hadoop？）、OLAP？

更新。您如何看待一些内存解决方案？记录可以以某种有利于搜索和排序的结构加载到操作内存中。什么结构最好？

在生产环境中，客户将能够提供合适的硬件以获得良好的解决方案。

一般来说，我们有一个 .NET 解决方案——所以，这个模块必须与它兼容。

4

5 回答 5

4

[TrollModeOn] 我有一个问题....试图用 no-sql 解决方案解决它，现在我有 2 个问题 [/TrollModeOff]。

在我看来，no-sql 解决方案不适合处理这么多过滤器的东西。我将从基于 sql 的解决方案开始。例如，如果我们有 ms sql server，我们可以将用户定义的表类型用于过滤器，例如：

CREATE TYPE [FilterTable] AS TABLE(
    [id] [int] NOT NULL   --or any datatype needed
)

之后，您可以将表类型作为参数传递给过滤存储过程（或使用 sql 查询），例如：

CREATE PROCEDURE [SomeFilterProcedureName]
    @Filter1 FilterTable READONLY,
    @Filter2 FilterTable READONLY
    ....

你的查询会是这样的：

SELECT
    field1,
    field2,
    field3
FROM MyTable t
WHERE
    (@Filter1 IS NULL OR t.field1 IN (SELECT id FROM @Filter1))
    AND (@Filter2 IS NULL OR t.field2 IN (SELECT id FROM @Filter2))
    ....
ORDER BY
    whatever

所以基本上你检查你的参数是否包含一些值，如果是的话 - 你根据过滤器参数数据过滤掉列值。

RDBMS 在存储、查找、过滤和排序大量数据方面做得非常出色，但是您需要以正确的方式对其进行调整以使其更快地工作，例如您需要正确设置索引。您也可以缓存数据一段时间，但请确保根据不同的参数构建正确的缓存键。

如果您的数据库服务器不足以每秒处理 200 个查询，您可能需要创建一个集群或保持多个数据库服务器具有相同的数据并使用某种数据库平衡器。

更新：它太大了，不能放在评论中

It the worst case he can select "All" for every 11 filter and we have to sort 192 million records to find 20-100 with the lowest cost

全过滤器，成本最低？是不是和以下一样： Select top(20) * from someTableName order by cost。

  1. Db Locks. 更好地处理索引和查询
  2. Sorting. 好的，您有 1 亿条适合过滤器的记录。你打算如何对它们进行排序？QSort、MergeSort、BubbleSort？或者也许是stackoverflowSort？你知道你必须选择哪种算法吗？但首先——DBMS 知道，它为案例选择了最佳算法，因为它有统计信息，其次——当然数据是预先排序存储在索引中的。所以每 100m 记录排序操作都会杀死 no-sql 解决方案，但会在 rdbms 上完美运行
  3. High load. 不是我们说的吗？在您的情况下，那里并不是真正的高负载。有些公司每月有 100-1.5 亿活跃用户，拥有巨大的数据库，每秒有数千次查询，是的，他们使用 rdbms。数十台服务器，分片，平衡，完美运行。
于 2013-07-11T15:02:48.860 回答
3

内存解决方案可能是可行的。由于您需要存储 12 个值 x 200M 记录，因此您需要大约 20GB 的 RAM 网络（假设每个值 8 个字节）。您需要优化（尽可能存储 1/2/4 字节值并禁用内存对齐）。实际上，您可能需要 64GB 或更大容量的机器。

一种认为您负担不起的是使用需要大量小内存分配的数据结构。即使您将数据存储在一个巨大的缓冲区中，您也可能需要为树结构索引分配许多小块。

树不适合您的问题还有另一个原因：由于用户可能为每个过滤器选择一组值，因此您需要遍历树以搜索任何组合。这可能是大量的树遍历。

一个更简单的解决方案怎么样？选择将数据集划分为最大组数的 2 个过滤器（这可能是具有约 5000 个值的过滤器）。使用二维数组。在每个单元格中，如果它不为空，则存储所有剩余 10 个值（9 个过滤器 + 成本）的结构数组。您可以按第三个最主要的过滤器对这些数组进行排序。

在用户查询时，确定 2D 数组中的相关单元格，并根据相关单元格中的每个值检查您的输入（按第三个最主要的过滤器排序）。对于大多数单元格，您要检查的值远少于 1000 个。

根据您的数据分布，您可以通过使用稀疏矩阵而不是二维数组来节省一些内存。一些 .NET 稀疏矩阵实现可在线获得。

于 2013-07-15T05:17:35.473 回答
2

我认为HBase我们符合您的要求，对于 .net 兼容性，hadoop .netSDK 可从Horton：LINK获取更多信息

于 2013-07-09T04:10:04.750 回答
2

这正是 SQL 设计的场景

现代系统上的 SQL Server（例如，具有 8 GB RAM 的四核 CPU）可以在您需要的时间跨度内轻松处理所有过滤器，或者根本不处理过滤器，前提是您在要过滤的每个字段上创建一个 INDEX。

您可以使用 Sergio 的存储过程来实现过滤器；但这是概率。就像直接在 C#（或 VB.NET）中生成正确的 SQL 语句一样容易。

简介，简介，简介

在寻找 Map-Reduce 或其他 (b) 前沿技术之前，请尝试 SQL。创建表和索引可以在大约 15 分钟内完成，您可以对查询进行计时。如果它接近您的要求，那么您可以开始编写代码以根据过滤器生成正确的 SQL SELECT。如果 SQL 查询比您的要求慢，您可以决定是否要优化它，或者寻找其他地方。 但在您进行分析之前，绝对没有理由尝试其他任何事情。

于 2013-07-14T06:49:15.463 回答
2

有一个你可以使用的库。这是索尔。Solr 在使用 Java 开发应用程序时经常使用。但是您也可以从 .net 调用 Solr。这 是一种解决方案，这是另一种解决方案。它专为大数据而设计。内存中的解决方案可能会导致问题，尤其是在我们谈论生产时。

于 2013-07-15T19:58:58.263 回答