Java 项目 : Make HashMap (including Load-Store) Performance Better

Question

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

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

对于 1 亿，我们所做的是:

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

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

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

1) 构建两个/三个独立的 HashTable，并加载和存储它(在一般文件系统上)以查找 URL 被访问的次数。

现在，问题是，

1) 尽管 HashTable 性能非常好，但代码在加载/存储 HashTable 时需要更多时间(我们使用文件 channel ，加载/存储 HashTable 需要 16-19 秒 - 2 亿个条目 - 因为加载因子为 0.5)

我们想问的是:

1) 对如何解决这个问题有什么意见吗？

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

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 数据库，例如 TokyoCabinet，但根据我们的经验，自定义 HashTable 在 1 亿个键值对上提供比它更好的性能。

2) 磁盘缓存的预读数据是不可能的，因为当系统启动时，我们的应用程序将在第二天系统启动时开始工作。

我们忘记提及的是:

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

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

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

Edit: code of our hashmap can be found here.

Answer 1

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

在该文件中，如果您非常确定散列冲突不是问题，则散列映射将起作用。否则我会去 B+ tree在那里，节点的大小与您的硬盘页面大小有关。这样，每次磁盘访问都会产生比单个 key 更多的可用数据，从而导致更浅的树和更少的单独磁盘操作。

我想其他人会实现这样的东西，但如果您更喜欢自己的 HashMap 实现，您可能更愿意编写自己的内存映射 B+ 树。