布隆过滤器解析

  • Hbase文件存储特点:
    • 同一个region的文件按照列族存储,而不是按行存储;
    • 也就导致了在一个Hfile文件中,存储的是一个列族的多行数据。
  • Hbase系统读取数据特点:
    • 通常是读取一行数据,或者是读取单个cell数据;
    • 当region中存储大量数据后,列族目录下就会有大量的Hfile文件;
    • 而不论是读取一行数据还是单个cell数据,首先都要通过行键在对应的region目录下查找包含有该行键信息的Hfile文件。
  • 需求分析:
    • 通过对上述Hbase文件存储特点和读取数据特点的分析,发现一个关键数据—行键;
    • 只要能快速确认Hfile中是否包含要找的行键,就能极大提高搜索效率;
    • 那么可不可以在存入数据的时候,在Hfile中创建一个集合,将每个存入的数据的行键都放入集合中,在搜索数据时,根基要找的行键遍历集合,即可知道该Hfile中是否包含需要的数据;
    • 但是这样效率依然不够高,并且占用的内存也较大,故引入—>布隆过滤器;
  • 布隆过滤器原理:
    • 在Hfile中开辟出一个连续的1M大小的空间,以字节为单位作为分隔
    • 所有字节默认值为0,形成一个长度为8,388,608的标记队列(临时叫法)
    • 在Hbase写入数据时,通过存入的数据的行键,计算出其对应的hashcode值,在队列中找到该值对应的字节位置,将字节的值改为1
    • 在Hbase读取数据时,将要查找的行键通过相同的hashcode算法求得hashcode值,查看每个Hfile文件的标记队列的相应位置的值
      • 如果值为0,说明该Hfile文件中不包含要查找的行键的信息
      • 如果值为1,则有极大可能,该Hfile文件中包含该行键的信息(哈希冲突)
  • 布隆过滤器缺点:
    • 哈希冲突:
      • 原因:如果两个不同的行键,恰好hashcode值相同,在读取查找时,可能会造成误判
      • 分析:可不做处理,在后续的读取过程中,自然会根据行键进行遍历查找,对取出的结果影响不大;如果要处理,个人人为,可以设置两个标记队列,使用不同的hashcode算法,进行标记,两个不同算法同时重复的概率非常低
    • hashcode超出:
      • 原因:通过行键计算出的hashcode值超出了1M队列的最大值:8388608
      • 分析:在录入数据时,限制行键长度;优化hashcode算法;在队列中查找前,先做判断是否大于8388608,如果大于,把行键存到一个独立的集合中
  • 布隆过滤器核心思想:
    • 利用机器处理2进制数据的优势,机器可以通过2>>hashcode,快速找到队列的对应位置,提高效率
    • 充分利用字节的特性,0为无,1为有;又利用hashcode的独特性,用最少的空间,存储了关键信息的有无信息。
上一篇:Hbase深入理解


下一篇:C++ 查看当前占用该文件的进程