3

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

现在,在一开始,我们看到每天有 1 亿个不同的 URL 被访问。现在,随着时间的推移,它每天有近 6 亿个不同的 URL。

对于 1 亿人,我们所做的如下:

1) 使用并行数组构建 HashMap,其键是 URL 的一部分(表示为 LONG),值是 URL 的另一部分(表示为 INT) - 键可以有多个值。

2) 然后搜索 HashMap 以查找 URL 访问了多少次。

现在,随着 HashTable 变大,我们所做的如下:

1)建立两个/三个单独的HashTable,并加载并存储它(在一般文件系统上)以查找URL访问了多少次。

现在,问题是,

1) 虽然 HashTable 性能相当不错,但代码在加载/存储 HashTable 时需要更多时间(我们使用文件通道,加载/存储 HashTable 需要 16-19 秒 - 2 亿条目 - 因为负载因子为 0.5)

我们想问的是:

1)任何评论如何解决这个问题?

2)如何减少加载/存储时间(我之前问过但似乎文件通道是最好的方法)?

3)存储一个大的HashTable(超过内存)并重复缓存它会是一个很好的解决方案吗?如果是这样,如何做到这一点(至少一些指针)。我们尝试使用

RandomAccessFile raf = new RandomAccessFile("array.dat", "rw");
IntBuffer map = raf.getChannel().map(FileChannel.MapMode.READ_WRITE, 0, 1 << 30).order(ByteOrder.nativeOrder()).asIntBuffer();

但是,提供比以前更差的性能。

谢谢。

注意:

1) 根据 Stack Overflow 之前的建议,我们使用一些 NoSQL DB,例如 TokyoCabinet,但根据我们的经验,自定义 HashTable 在 1 亿个键值对上的性能比它更好。

2) 无法为磁盘缓存预读数据,因为系统启动时,我们的应用程序将开始工作,而第二天系统启动时。

我们忘记提到的是:

1)由于我们的应用是项目的一部分,并且应用在一个小校园,所以我们假设访问的URL不超过8亿。所以,你可以认为 600/700 的数据值是固定的。

2)我们主要关心的是性能。

3)我们必须在本地运行我们的应用程序。

编辑:我们的 hashmap 的代码可以在这里找到。

4

12 回答 12

6

最好将表作为内存映射缓冲区访问。这样,您可以简单地实现对文件的随机访问,而不必担心加载和存储,并将缓存留给操作系统。我看到您当前的实现已经使用内存映射访问进行读取和写入,但它仍然将内容加载到两者之间的 java 堆中。避免这种数据重复和复制!将备份文件本身视为数据结构,仅在需要时才访问您实际需要的部分。

如果您确实确定哈希冲突不是问题,那么在该文件中,哈希映射将起作用。否则,我会在那里寻找B+ 树,其节点与硬盘页面的大小差不多。这样,每次磁盘访问将产生比单个键更多的可用数据,从而导致更浅的树和更少的单个磁盘操作。

我猜其他人会实现这样的东西,但是如果您更喜欢自己的哈希映射实现,您可能更喜欢编写自己的内存映射 B+ 树。

于 2012-07-11T14:44:31.687 回答
3

整个方法对我来说听起来很可笑。我收集到您真正想要实现的是每个不同 URL 的简单访问计数器。就其本质而言,这些数据经常被写入,但很少被读取。

为此,我只需要一个数据库表并为每次访问添加一个新条目(它也可以用作日志)。当您需要确定访问任何 URL 的频率时,可以使用表中的 SELECT COUNT 轻松完成(取决于您与 URL 条目一起存储的附加数据量,您甚至可以进行限制计数,例如昨天访问的频率,上周等)。

这将所有工作都放到了真正需要结果的地步。

顺便说一句,您也可以从 Web 服务器日志文件中检索访问计数,因此您可能不需要自己编写任何数据。先看看这个。

于 2012-07-10T10:44:27.210 回答
1

您可以使用像JCS这样的缓存框架。10 亿个键值对应该不是问题。

http://commons.apache.org/jcs/

于 2012-07-03T14:03:19.520 回答
0

似乎您有一个不适合内存的只读数据集,并且您需要快速键查找。恐怕这里没有灵丹妙药的解决方案,除了一些可能的权衡。

如果您在所有地方访问 600M 记录,无论您做什么,您都将受到磁盘随机访问速度(而不是顺序访问速度)的限制。用于FileChannel.map直接访问文件(不,不要读取内存中文件的内容,只需对MappedByteBuffer. 您的操作系统负责缓存)。投资 SSD 看起来是一种花钱的好方法(或者只是购买更多内存?)。

这是校园环境吧?也许您可以使用实验室中的计算机来制作 memcached/redis/etc。簇?也许你可以在下班时间使用它?

如果您同时访问一些可识别的数据片段(即现在我们分析域 a,然后分析域 b,等等),那么将数据分成桶是一个好主意。就像保持相关数据物理上接近,以帮助缓存。或者可能对 url 进行预排序,并以二进制搜索方式访问它们?

如果某些冲突概率是可以接受的,也许不存储完整的 url,而只存储 64 位的 url 哈希作为哈希键是可以接受的?通过一些体操你可能完全不存放钥匙?

这就是我目前的想法。

于 2012-07-16T19:38:05.637 回答
0

在内存数据库中使用开源sqlite 。

于 2012-07-16T07:11:03.130 回答
0

不清楚问题和后续讨论,但您的查询的性质是什么?
在a) 每个工作日处理所有约 7 亿个 URL 或
b) 访问这约 7 亿个 URL 中的一小部分时,您会遇到非常不同的情况。

那么:查询数与 URL 数的比率是多少?

根据您的描述,听起来您可能正在加载/卸载代表数组不同部分的不同文件......这表明随机查询,这表明(b)。

同样,我想您已经认识到“全内存”是不可行的(即您已经破坏了多个文件的阵列),因此最佳磁盘访问算法似乎是下一个业务顺序, 不?

您是否尝试过,每个查询,一个简单的查找(n * arrayElementSize)在文件中偏移并且只是将几页读入内存(您是否有/知道每个键的最大值数?)。您已经(计算)到数组中的基本索引,所以这应该很容易原型化。

于 2012-07-11T04:35:26.850 回答
0

绝对尝试redis,认为它胜过其他任何事情

于 2012-07-03T14:05:41.580 回答
0

您可以使用Berkeley DB,它基本上是一个用 C 语言编写的键/值存储,以实现终极性能。这是一个 Oracle 产品(尽管是开源的),所以我会认真对待。

于 2012-07-03T14:06:55.563 回答
0

我建议您使用Oracle Coherence Cache。您可以获得它的所有好处,HashTable它具有 Map 具有的所有方法。

性能方面,您可以根据需要存储数据。请看一下。

于 2012-07-12T08:55:25.583 回答
0

如果您的应用程序必须在不使用任何外部计算能力的情况下在本地运行,那么没有比直接内存访问性能更高的解决方案:唯一可以为您提供比 HashMap 更好的性能的数据结构是数组,其中每个元素的访问是 O(1)。然而,这需要提前知道您有多少项目,每个元素有一个唯一的寻址索引,并且还能够保留重要的相邻内存。

在数组之后,如所述适用于有限的情况,你有哈希表,但是随着数据大小的增长,冲突和动态调整大小的成本增加并且性能很差。

您可以参考 java.util.HashMap javadoc,也可以参考维基百科 http://en.wikipedia.org/wiki/Hash_table来了解以下内容:

  • 计算它有多昂贵?
  • 价值如何分布良好?
  • 您正在使用的负载因子是多少,即解决冲突的成本是多少?
  • 在完全包含所有数据之前,您需要多久调整一次 HashMap 的大小?

如果在构建 HashMap 时性能下降,我实际上认为它是 ConcurrentHashMap(如果您并行构建它,它必须是线程安全的),您可能想调查它发生的原因。

一个简单但容易的开始是将您的 HashMap 替换为 TreeMap,其性能是其大小的确定性函数,并比较两种性能。


如果另一方面我误解了你的问题,并且你有机会在多台机器上扩展计算,那么市场上有很多有趣的解决方案,正如有人已经指出的那样,我会添加 Cassandra。

这些解决方案通过在多个节点之间分配负载来提高性能,但在每个节点内部都使用众所周知的算法来实现快速高效的寻址。

于 2012-07-10T13:06:09.310 回答
0

如果我理解正确,您的数据结构并没有那么大

[(32 + 64) * 600 million] bits i.e. a 53.644 MB structure in memory

地图数据结构也会消耗一些空间。我发现 trove 是最节省内存的数据结构之一。我会使用TLongIntHashMap来存储长键和整数值。它存储原始原语,以便您绕过 Long 和 Integer 内存对象

于 2012-07-16T08:36:34.367 回答
0

您可以尝试HugeCollections,我认为它是为此目的而编写的

HugeCollections
Library 支持具有数百万或数十亿条目的集合。

具体来说HugeMap

于 2012-07-13T12:17:26.150 回答