如同磁铁吸引四周的铁粉,热情也能吸引周围的人,改变周围的情况。

Lucene里面的bloom过滤

Lucene | 作者 Charele | 发布于2024年03月21日 | 阅读数:1869

Lucene里面,有一个bloom过滤功能的格式。
它就是包装了一个老的格式(老格式还是起原来的作用)。
1111.PNG

 
结果就是额外生成了一个bloom格式的文件,
其它没有任何变化。

2222.PNG
已邀请:

Charele - Cisco4321

赞同来自:

这样在执行比如termQuery时,如果bloom告诉你没有,就实现fast-fail
否则还是会用老办法去找。因为bloom不能告诉你有。
1111.PNG

Charele - Cisco4321

赞同来自:

新版本中的ES有了bloom功能(ES8.12.2截图),
它并没有直接用Lucene中那个现成的,而是自己“山寨”了一个。
 
看起来比Lucene那个实现要更简洁明了一些。
1111.PNG

Charele - Cisco4321

赞同来自:

说上面这个bloom过滤只是小case,
 
来看一个Lucene里面革新性的东西。
这个东西不是主流,缺省还是用现在的。
 
只是做了改变,做了些改变,可能会有对查询优化 
这个新的格式叫BlockTreeOrdsPostingsFormat
(不管什么样子,都是PostingsFormat的子类实现)
 
1111.PNG

这是老的现有的格式,
 
2222.PNG

像doc,pos这些没有变化,因为还是用原来的东东去写去读。
 
原来的词索引,词字典文件tmd,tip,tim变成了tio, tipo(不要看前面的名字,看扩展名)
 
本质上就是FST表内容发生了变化。
下面说说发生了什么变化
(假设你已大致了解了现有格式,网上很多资源可以看)

Charele - Cisco4321

赞同来自:

关于FST的内容,比如,它内部如何写,如何读,
其中的细节,相当的复杂。可以不管。
 
但FST里面存的是什么,以及get出来的东西代表什么意思,
这是肯定要知道的。不然你说你理解查询,跟本无从谈起。
 
 先看看代码实现上的一个小异:
1111.PNG

2222.PNG

 
红色的代码,就是在建FST的时候,所有的词都搞完了,最后的步骤。
即形成“空块”,即前缀为空的block。
老格式,先会推两个空词(new BytesRef())进去,
(就像new String("aaa"),是一个实串,而new String()就认为是一个空串)
 而新格式,不会这么做。
 
这两种做法,结果的区别是什么呢? 
 
 

Charele - Cisco4321

赞同来自:

现在我们有这么些词,在现有的格式下,会这么形成块。
(假设min = 2, max = 3, 缺省这两值太大了,不好表述)
 
min = 2表示,块里最少得有2个条目,才能形成block
max =3 表示,一个块里最多只能有3个条目
这些感念不明白的可以看下大神的波客:
https://amazingkoala.com.cn/Lu ... Btip/
 
1111.PNG
 
1  首先aaa开头的有3个,会形成block["aaa"] ("aaa"表示这个块的前缀)
2  “bbb"这个词,只有一个,它就不能形成块,所以是term
3 最后两个,形成block["ccc"]
4 最后,生成根块(我自己习惯叫空块,就是前缀是""的块)
 
上面,"ccc1", "ccc2"这两个词在最后,它们能形成块的原因就是,
系统会最后push两个空词进去,终结它们(见上楼),所以形成一个block
 
如果我不push空词,情况是什么样子的呢

Charele - Cisco4321

赞同来自:

1111.PNG

如果不推最后空词,它会这样分,最后的"ccc1, "ccc2"就不会形成块,
它会跟"bbb"一样,以term的方式存在于空块中(就是最大的那个块)
 
因为空块里有4个条目(一个block + 3个term),超过了max=3的限制,
所以这个空块是个"地板块“, floor block,会分地板0,地板1
(是不是地板块,对于现在说的不重要,所以不细说了)
 
上面两种划分方式,不管如何,不会对结果产生影响。每个词还是能查到。
至于它为什么要这么改,,,

Charele - Cisco4321

赞同来自:

http://examples.mikemccandless.com/fst.py
很多人都会拿这个来说明FST的样子,
比如我要找"aa",沿着蓝线,把一路上找到的50+150=200就是aa的结果了
如果把这个FST看成一个map,    那就是Map<String, Long>类型的
1111.PNG

 
这东西容易让人产生误解。
刚开始,我看这个东东,以为Lucene的FST就是这么存的。
里面存的是一个一个的词,查询时就这么来找。
后来发现跟本不是这样子的。
 
如果存的key是词,那get出来的是什么呢,文档号吗?还是什么别的?

Charele - Cisco4321

赞同来自:

FST可以看成一个map, 
实际中,其中的key,不是一个一个的词,而是块的前缀。
比如上面的"aaa", "ccc"。一个前缀就代表了一个块。 
 
PS: 空前缀""(空块)逻辑上包括了所有的块,是所有其它块的root
它的key / value也能从map中取到,不过它并不存在这里。
 
value是什么呢,如果是普通块,
里面有3个指标(绿色的)(合在一个long数字里面)
1 fp
就是这个块,在tim文件里的地址
 
2 hasTerms
块如果按里面包含的东西来分,分为:
A 里只有term
B 里面既有term又有块
C 里面只有block
在A,B两种情况下,hasTerms=true
 
3 isFloor
是不是地板块,,,
1234.png
块可以分为普通块和地板块,
紫色是说如果这个块是地板块,还会再存一些其它东西。 
这是现有的版本的FST里面存的东西

Charele - Cisco4321

赞同来自:

如果认真看过楼上大佬的博客和Lucene代码
就明白了FST是存在tip里面的(词索引),而每个词的统计信息是存在tim里的(词字典)
(tmd文件可以忽略,它存的是字段的统计信息)
 
在Lucene90BlockTreeTermsReader类里面
 
下面这个方法就是执行term查询的方法,如果返回true,它们会拿这个词的统计信息,从而算出打分,,,
1111.PNG

 
这个类还有一个方法
public BytesRef next() throws IOException {
作用是取出这个字段的每个词,比如name字段,
它会得到"张三", "李四", "王小明",,,
开始想不明白有什么用,我要所有词做啥?后来才发现这是merge时用的

Charele - Cisco4321

赞同来自:

上面就是现有版本FST的一些实际用途了。
 
现在说说变种格式,相对现有格式的改进,
1234.png

 
FST里面key没有变化。
写进FST的value发生了变化。
紫色的,是原来的value(和原来一模一样)
它增加了两个long值,
开始位置和结束位置
 

要回复问题请先登录注册