2020年南方电网招聘考试笔试真题:布隆过滤器

布隆过滤器（Bloom Filter）
Bigtable向用户提供了一种称为布隆过滤器的数学工具。布隆过滤器是巴顿·布隆在1970年提出的，实际上它是一个很长的二进制向量和一系列随机映射函数，在读操作中确定子表的位置时非常有用。布隆过滤器的速度块，省空间。而且它有一个最大的好处是它绝不会将一个存在的子表判定为不存在。不过布隆过滤器也有一个缺点，那就是在某些情况下它会将不存在的子表判断为存在。不过这种情况出现的概率非常小，跟他带来的巨大好处相比这个缺点是可以忍受的。
目前包括Google Analytics、Google Earth、个性化搜索、Orkut和RSS阅读器在内的十几个项目都是用了Bigtable。这些应用对Bigtable的要求以及使用的集群机数量都是各不相同的，但是从实际运行来看，Bigtable完全可以满足这些不同需求的应用，而这一切都得益于其优良的架构以及恰当的技术选择。与此同时Google还在不断的对Bigtable进行一系列的改进，通过技术改良和新特性的加入提高系统运行效率及稳定性。