Skip to content

Latest commit

 

History

History
72 lines (39 loc) · 5.32 KB

find-common-urls.md

File metadata and controls

72 lines (39 loc) · 5.32 KB
Raw

如何从大量的 URL 中找出相同的 URL？

题目描述

给定 a、b 两个文件，各存放 50 亿个 URL，每个 URL 各占 64B，内存限制是 4G。请找出 a、b 两个文件共同的 URL。

解答思路

1. 分治策略

每个 URL 占 64B，那么 50 亿个 URL 占用的空间大小约为 320GB。

5, 000, 000, 000 _ 64B ≈ 5GB _ 64 = 320GB

由于内存大小只有 4G，因此，我们不可能一次性把所有 URL 加载到内存中处理。对于这种类型的题目，一般采用分治策略，即：把一个文件中的 URL 按照某个特征划分为多个小文件，使得每个小文件大小不超过 4G，这样就可以把这个小文件读到内存中进行处理了。

思路如下：

首先遍历文件 a，对遍历到的 URL 求 hash(URL) % 1000 ，根据计算结果把遍历到的 URL 存储到 a0, a1, a2, ..., a999，这样每个大小约为 300MB。使用同样的方法遍历文件 b，把文件 b 中的 URL 分别存储到文件 b0, b1, b2, ..., b999 中。这样处理过后，所有可能相同的 URL 都在对应的小文件中，即 a0 对应 b0, ..., a999 对应 b999，不对应的小文件不可能有相同的 URL。那么接下来，我们只需要求出这 1000 对小文件中相同的 URL 就好了。

接着遍历 ai( i∈[0,999] )，把 URL 存储到一个 HashSet 集合中。然后遍历 bi 中每个 URL，看在 HashSet 集合中是否存在，若存在，说明这就是共同的 URL，可以把这个 URL 保存到一个单独的文件中。

2. 前缀树是否可行？

一般而言，URL 的长度差距不会不大，而且前面几个字符，绝大部分相同。这种情况下，非常适合使用字典树（trie tree） 这种数据结构来进行存储，降低存储成本的同时，提高查询效率。

由 @ChunelFeng 反馈。#212

有 issue 提到是否可以直接使用 trie 树，我们来推算一下方案是否可行。

Background：4G 的机器，解析 320G 的数据。

首先题目提到 64B 大小，按一个字符一个字节来算的话就是 64 位，也就是 64 个字符组成（这里考虑极端情况）。Trie 树的定义这里就不提了，见字典树。

  • 树高：URL 的长度就是最后的树的能达到的高度，及最高 64 层树。

  • 节点下的子节点数量：因为是 URL，除了数字和字符之外还有%, /, :etc。这里为了简化计算和方便理解只使用英文字符+数字总数=62+10=72。也就是说一个结点下的子节点最多有 72 个，及占 72B。

  • 节点总大小：因为样本 320G 足够大，我们考虑坏情况下，最后的树是 64 层高的满 72 叉树。最后的内存占用为节点数量*节点大小：

    • 节点数量：满 N = 64 层，K = 72 叉，树节点数量计算公式（等比数列求和）为：1 * (1-72^64)/ (1 - 72) = (72^64 - 1)/ (71)，估算为71^63个节点。

    • 节点大小：每个节点占用大小为 1B

      • 当前字符 1B
      • 当前位置是否存在值 1b（常见 Bool 值大小），这里按最小大小来。

所以总大小为：71^63 * 1B/ 1000 ≈ 71^60 KB ≈ 71 ^ 63 GB，这个值已经很大了，况且在方案推算过程中按照最小原则考虑。

写到这里有些读者可能就被吓到了，怎么出来这么多数据，trie 树不是有压缩的作用嘛？

这里得到的结果是不正确的，因为 320G 的数据，生成的节点数也最多只会是 320G（路径完全不重复），因为无法构成上面讨论的满 N 叉树的情况，填满了其中一点而已。但是对于单机来说此部分数据单机已无法解析，并且方案不具有扩展性和稳定性 。所以单纯的 trie 树太依赖数据分布，如果你的大部分 URL 是相同的压缩度很高，单机 4G 解析 320G 有可能，但是对于面试官想听到的应用场景来说这个概率太小了。所以还是得借助分治法的方式降低内存。

在方案一上进行优化：在上一个方法中使用 HaseSet 来判重，hash 效率比访问 trie 树，hash 效率更高，trie 可以降低内存。

所以在面试中可以提到 trie 方案，在这个场景中解析 320G 离线数据为时间不敏感类型，所以可以牺牲速度来换取空间。

  • 方案一提到单文件大小为 300MB+，使用 trie 树之后这 300MB+会有所压缩比如到 200MB+，考虑到机器性能利用率，在一些 CPU 充足的场景中可以考虑引入并发，因为压缩率 1/3，其余空间可以腾出来加载更多文件做并发提升处理速度。

  • 如果 CPU 不充足比如单核，可以考虑增加切分的文件大小，原先的 1000 个文件，降为 200 个也就是文件大小扩大两倍，之前 300MB，现在 300*5 = 1.5G，在 4G 的机器上可以打满内存，减少 IO 次数，减少内核态到用户态的拷贝，也可以提一嘴 DMA。

方法总结

分治策略

  1. 分而治之，进行哈希取余；
  2. 对每个子文件进行 HashSet 统计。

前缀树

  1. 利用字符串的公共前缀牺牲速度，来降低内存占用。