海量数据题

[BruceChen7]

参考资料

• 十道海量数据处理面试题与十个方法总结【面试 + 提高】 - 云 + 社区 - 腾讯云 (tencent.com)
• 最新 | 10 道 BAT 大厂海量数据面试题（附题解 + 方法总结） (qq.com)
• 布隆过滤器
• Probabilistic Data structures: Bloom filter | Hacker Noon
• 布谷鸟过滤器的 Go 语言实现与解析 - 市场增长平台中心 - KM 平台 (oa.com)
• BloomFilter 与 Cuckoo Filter
• When Bloom filters don't bloom (cloudflare.com)
• Word-aligned Bloom filters – Daniel Lemire's blog
• 排序算法

求最大，最多的 top K

• 使用小根堆。

海量数据前 n 大，并且 n 比较小，堆能放入内存

• 基本原理及要点：最大堆求前 n 小，最小堆求前 n 大。
• 方法，比如求前 n 小，比较当前元素与最大堆里的最大元素，如果它小于最大元素，则应该替换那个最大元素。
  • 这样最后得到的 n 个元素就是最小的 n 个。
  • 适合大数据量，求前 n 小，n 的大小比较小的情况，这样能扫描一遍即可得到所有的前 n 元素，效率很高。
• 扩展：双堆，一个最大堆与一个最小堆结合，能用来维护中位数。

布隆过滤器

• 布隆过滤器能检查值是 可能在集合中 还是 “绝对不在集合中”。
• 可能表示有一定的概率，也就是说可能存在一定为误判率。

误判原因

• bloom filter 本质上是由长度为 m 的位向量或位列表（仅包含 0 或 1 位值的列表）组成，最初所有的值均设置为 0
• 
• 为了将数据项添加到布隆过滤器中，会提供 K 个不同的哈希函数，并将结果位置上对应位的值置为“1”。
• 在前面所提到的哈希表中，使用的是单个哈希函数，因此只能输出单个索引值。
• 而对于布隆过滤器来说，将使用多个哈希函数，这将会产生多个索引值。
• 
• 当输入 semlinker”时，预设的 3 个哈希函数将输出 2、4、6，把相应位置 1。
• 假设另一个输入 kakuqo，哈希函数输出 3、4 和 7。
• 可能已经注意到，索引位 4 已经被先前的“semlinker”标记了。
• 此时，已经使用 semlinker 和 kakuqo 两个输入值，填充了位向量。
• 位向量的标记状态为：
• 

误判率：

• 
• n 是已经添加元素的数量；
• k 哈希的次数；
• m 布隆过滤器的长度（如比特数组的大小）。

缺点：

• 字符串加入了，就不能删除。
• 有一定的误判率

应用

• 网页爬虫对 URL 去重，避免爬取相同的 URL 地址；
• 反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱；
• Google Chrome 使用布隆过滤器识别恶意 URL；
• Medium 使用布隆过滤器避免推荐给用户已经读过的文章；
• Google BigTable，Apache HBbase 和 Apache Cassandra 使用布隆过滤器减少对不存在的行和列的查找。
• 布隆过滤器还有一个应用场景就是解决缓存穿透的问题。
  • 所谓的缓存穿透就是服务调用方每次都是查询不在缓存中的数据，这样每次服务调用都会到数据库中进行查询，
  • 如果这类请求比较多的话，就会导致数据库压力增大，这样缓存就失去了意义。
  • 利用布隆过滤器能预先把数据查询的主键，比如用户 ID 或文章 ID 缓存到过滤器中。
  • 当根据 ID 进行数据查询的时候，先判断该 ID 是否存在，若存在的话，则进行下一步处理。
  • 若不存在的话，直接返回，这样就不会触发后续的数据库查询。
  • 需要注意的是缓存穿透不能完全解决，只能将其控制在一个能容忍的范围内。

布谷鸟哈希

• Bloom filter 存在一定的误报率，并且无法删除元素。
• 而布谷鸟哈希则是解决这两个问题
• Cuckoo 的哈希函数是成对的（具体的实现能根据需求设计），每一个元素都是两个，分别映射到两个位置，
  • 一个是记录的位置，
  • 另一个是备用位置，这个备用位置是处理碰撞时用的。
• 如下图，使用 hashA 和 hashB 计算对应 key x 的位置 a 和 b ：
  • 当两个哈希位置有一个为空时，则插入该空位置；
  • 当两个哈希位置均不为空时，随机选择两者之一的位置上 key y 踢出，并计算踢出的 key y 在另一个哈希值对应的位置，
    • 若为空直接插入，不为空踢出原元素插入，
    • 再对被踢出的元素重新计算，重复该过程，直到有空位置为止。
• 
• 比如待存储的 key=x，首先计算其指纹、以及两个 hash 函数的结果（对应存储位置）

  fp = fingerprint(x)
  p1 = hash1(x) % len
  p2 = hash2(x) % len

  • 如果 p1、p2 两个位置都已满，那么需要随机选择其中一个未知的元素进行踢出，并计算其另一个对位，
  • 但由于 cuckoo filter 存储的是指纹 fp，而非原始的 x 值，那么要如何计算其另一个位置呢？
• cuckoo filter 巧妙的设计另一个 hash 函数，使得能根据 p1 和 fp 直接计算出 p2（或者根据 p2 和 fp 直接计算出 p1），而不需要完整的 x 元素。

  fp = fingerprint(x)
  p1 = hash(x)
  p2 = p1 ^ hash(fp)  // 异或

• 同样的

  p1 = p2 ^ hash(fp)

• 根本不需要知道当前的位置是 p1 还是 p2，只需要将当前的位置和 hash(fp) 进行异或计算就能得到对偶位置。
• 而且只需要确保 hash(fp) != 0 就能确保 p1 != p2，如此就不会出现自己踢自己导致死循环的问题。
• cuckoo filter，简单起见，假定指纹占用一个字节（指纹范围 (0-255] ），每个位置有 4 个 座位：

  type bucket [4]byte  // 一个桶，4 个座位
  type cuckoo_filter struct {
    buckets [size]bucket // 一维数组
    nums int  // 容纳的元素的个数
    kick_max  // 最大挤兑次数
  }

• 插入算法，需要考虑到最坏的情况，那就是挤兑循环。所以需要设置一个最大的挤兑上限，当超过挤兑上限时，能进行扩容（rehash）。

  def insert(x):
    fp = fingerprint(x)
    p1 = hash(x)
    p2 = p1 ^ hash(fp) // 尝试加入第一个位置
    if !buckets[p1].full():
      buckets[p1].add(fp)
      nums++
      return true
    // 尝试加入第二个位置
    if !buckets[p2].full():
      buckets[p2].add(fp)
      nums++
      return true
    // 随机挤兑一个位置
    p = rand(p1, p2)
    c = 0
    while c < kick_max: // 挤兑
      old_fp = buckets[p].replace_with(fp)
      fp = old_fp // 计算对偶位置
      p = p ^ hash(fp) // 尝试加入对偶位置
      if !buckets[p].full():
        buckets[p].add(fp)
        nums++
        return true
    return false

查找算法

def contains(x):
  fp = fingerprint(x)
  p1 = hash(x)
  p2 = p1 ^ hash(fp) return buckets[p1].contains(fp) || buckets[p2].contains(fp)

删除算法

def delete(x):
  fp = fingerprint(x)
  p1 = hash(x)
  p2 = p1 ^ hash(fp)
  ok = buckets[p1].delete(fp) || buckets[p2].delete(fp) if ok:
  nums--
  return ok

#type/system #public