检查数据密集型应用程序中的重复输入项

Question

我必须构建一个服务器端应用程序，它将接收数据流作为输入，它实际上将接收最多九位十进制数字的整数流，并且必须将它们中的每一个写入日志文件。输入数据是完全随机的，要求之一是应用程序不应将重复项写入日志文件，并应定期报告找到的重复项数。

考虑到性能是这个应用程序的一个关键方面，因为它应该能够处理高负载的工作（和并行工作），我想找到一个合适的解决方案来跟踪重复的条目，因为每次写入时检查整个日志（文本）文件肯定不是合适的解决方案。我可以想到一个解决方案，包括在内存中维护某种数据结构以跟踪到目前为止正在处理的整个数据流，但由于输入数据可能非常高，我认为这不是最好的方法它要么...

有什么想法吗？

Answer 1

假设随机整数流均匀分布。跟踪重复项的最有效方法是在内存中维护 100 亿位的 巨大位图 。然而，这需要大量 RAM：大约 1.2 Gio。但是，由于这个数据结构很大，内存访问可能会很慢（受限于内存层次结构的延迟）。

如果排序无所谓，可以使用多线程来减轻内存延迟的影响。可以使用逻辑 原子操作 安全地完成并行访问。要检查之前是否已经看到一个值，您可以检查位图中某个位的值然后设置它（如果并行完成则以原子方式设置）。

如果您知道您的流确实包含少于一百万个整数或者随机整数流分布不均匀，您可以使用 hash-set 数据结构，因为它以更紧凑的方式（按顺序）存储数据。

Bloom filters 可以帮助你在stream中的value数量比较大且重复很少的情况下加快过滤速度（这个方法必须结合如果你想获得 确定性 结果的另一种方法。

这是在 Python 中使用哈希集的示例：

seen = set()                 # List of duplicated values seen so far
for value in inputStream:    # Iterate over the stream value
    if value not in seen:    # O(1) lookup
        log.write(value)     # Value not duplicated here
        seen.add(value)      # O(1) appending

检查数据密集型应用程序中的重复输入项

Check for duplicate input items in a data-intensive application

algorithm

io

performance

duplicates

data-structures