4

在之前的一些帖子中,我问过一些关于 java 中自定义哈希映射/表的编码的问题。现在由于我无法解决它,并且可能我忘记正确提及我真正想要的东西,我正在总结所有这些以使其清晰准确。

我要做什么:

我正在尝试为我们的服务器编写代码,我必须在其中通过 URL 查找用户访问类型。

现在,我有 11.1 亿个 URL(大约)。

所以,我们所做的,

1) 将数据库划分为 1.1 亿个 Url 中的 10 个部分。2)使用并行数组构建一个HashMap,其键是URL的一部分(表示为LONG),值是URL的另一部分(表示为INT)-键可以有多个值

3)然后在系统启动时每天在HashMap中搜索其他一些URL(一天保存数百万个URL)。

您尝试过的内容:

1) 我尝试了许多 NoSQL 数据库,但我们发现对我们的目的不太好。

2)我为此目的构建了我们的自定义哈希图(使用两个并行数组)。

那么,问题是什么:

当系统启动时,我们必须加载每个数据库的哈希表并搜索数百万个 url:

现在,问题是,

1) 虽然 HashTable 的性能相当不错,但代码在加载 HashTable 时需要更多时间(我们使用文件通道和内存映射缓冲区来加载它,加载 HashTable 需要 20 秒 - 2.2 亿个条目 - 因为加载因子是 0.5,我们发现它最快

因此,我们花费时间:(HashTable Load + HashTable Search)* DB 数量 = (5 + 20) * 10 = 250 秒。这对我们来说相当昂贵,而且大部分时间(250 秒中有 200 秒)用于加载哈希表。

你有没有想过其他方式:

一种方法可以是:

无需担心加载和存储,通过使用内存映射缓冲区将缓存留给操作系统。但是,由于我必须搜索数百万个键,它的性能比上面的要差。

当我们发现 HashTable 性能不错但加载时间很长时,我们想以另一种方式将其切断,例如:

1)创建一个大小为 Integer_MAX 的链表数组(我自己的自定义链表)。

2)将值(int's)插入到编号为键号的链接列表中(我们将键大小减小为INT)。

3)因此,我们必须只将链表存储到磁盘中。

现在,问题是,创建如此数量的链接列表需要花费大量时间,如果数据分布不均,创建如此大量的链接列表将毫无意义。

那么,您的要求是什么:

只是我的要求:

1) 具有多值插入和搜索的键。寻找良好的搜索性能。2)快速加载(特别)到内存的方法。

(密钥是 64 位 INT,值是 32 位 INT,一个密钥最多可以有 2-3 个值。我们也可以将密钥设为 32 位,但会产生更多冲突,但如果我们能做得更好,我们可以接受) .

任何人都可以帮助我,如何解决这个问题或任何评论如何解决这个问题?

谢谢。

注意:

1) 根据 Stack Overflow 之前的建议,无法为磁盘缓存预读数据,因为系统启动时,我们的应用程序将开始工作,并在系统启动的第二天开始工作。

2)我们还没有发现 NoSQL 数据库的扩展性很好,因为我们的要求很简单(意味着只需插入哈希表键值并加载和搜索(检索值))。

3)由于我们的应用程序是小项目的一部分,并且要应用在一个小校园里,我认为没有人会为此给我买一个SSD磁盘。那是我的局限。

4) 我们也使用 Guava/Trove,但他们也无法在 16 GB 中存储如此大量的数据(我们使用的是 32 GB 的 ubuntu 服务器。)

4

3 回答 3

0

我真的不明白您以什么形式将数据存储在磁盘上。如果您存储的内容由 url 和一些数字组成,您可以通过压缩数据来加快从磁盘加载的速度(除非您已经这样做了)。

创建一个在加载时解压缩的多线程加载程序可能会给您带来很大的提升。

于 2012-08-22T16:08:19.630 回答
0

如果您需要快速访问 11.1 亿个数据项,那么散列是您的最佳选择。但不要重新发明轮子,使用类似的东西:

于 2012-08-01T19:23:24.290 回答
0

在我看来(如果我正确理解您的问题)您正试图以一种复杂的方式解决问题。
我的意思是您尝试预加载的数据一开始就很大(比如说 2.2 亿 * 64 ~ 14GB)。您正在尝试为此进行内存映射等。
我认为这是一个典型的问题,可以通过在不同的机器上分配负载来解决。即,而不是试图定位链表索引,您应该尝试找出已加载地图特定部分的相应机器的索引,并从那里获取该机器的值(每台机器都加载了其中的一部分)数据库地图,您每次都从地图的适当部分(即机器)获取数据)。
也许我离这里很远,但我也怀疑你使用的是 32 位机器。
因此,如果您必须继续使用单机架构并且在经济上不可能改进您的硬件(如您所指出的,64 位机器和更多 RAM 或 SSD),我认为您无法做出任何显着的改进。

于 2012-08-01T20:24:05.430 回答