-
Notifications
You must be signed in to change notification settings - Fork 4
/
README
200 lines (183 loc) · 9.8 KB
/
README
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
看sphinx的文档
(1) 为什么要做这个东东
-1- 搜索产品内部需要
我们的相关搜索和搜索建议,本质上还是倒排结构。
-2- 搜索院对其他部门的技术支持
云城搜索/C2C搜索/积分商城搜索。。
(2) 架构愿景和应用前景
-1- 一张图,表示云搜索,叙述工作流程,小数据+大数据量扩展
-2- 应用前景,框架的应用 + 插件使用
(3) 特性
性能方面
-0- 实时索引
-1- 快速建库
-2- 快速查询
-3- 超大数据
功能方面
-4- 算法强大
-5- 功能全配
-6- 灵活配置
数据恢复
-7- 崩溃恢复
架构远景
-8- 云搜索化
二次开发
-9- 支持插件
(1) 倒排索引
-1- index_group = mem_indexer + disk_indexer
-2- mem_indexer = postinglist + creat_sign
#1# postinglist = (hash-bucket) + (headlist) + memblocks
-3- disk_indexer = 二级索引 + [1级索引cache] + fileblock + diskv
索引管理逻辑
-1- mem/disk的时间节点
-2- dump逻辑
-3- 修改和删除(bitmap+idmap)
(2) 文档属性
-1- bitlist + structmask
(3) 文档详细
-1- detaildb = fileblock + diskv
服务搭建
(1) 线程组成
-1- equeue + query_threads
-2- update_thread
-3- day_merger_thread
-4- his_merger_thread
-5- ontime_thread
(2) 通信协议
-1- xhead + json
===============================================================
(1) 概述
flexse目前是一个搜索的框架,提供了搜索引擎中数据的存储和访问,特别实现了倒排数据的实时索引。
-1- 倒排索引原理
倒排索引抽象成数据结构,可以理解为map<string, vector<index_t>>,string就是分词形成的每
个term,而vector<index_t>就是含有这个term的各个文档ID列表,index_t就是描述这个term属性
的结构,index_t中必须含有一个ID。通过flexse/utils/indexer/index_group/index_group.cpp
中的get_posting_list方法,可以获得一个term对应的postinglist,如果内存不够存储,则返回
最新的内存大小的postinglist,失败返回-1。postinglist按照ID降序排列。
-2- 如何做到实时索引和实时更新(插件开发者不需要知道)
每个文档都会有个外部ID和内部ID,外部ID都是连续的,内部ID也是连续的,一个外部ID对应于一
个最新的内部ID。通过flexse/utils/idmap来管理内部和外部ID,当插入或更新一个文档时,根据
该文档的外部ID,来检查是否已经为其分配过内部ID,如果不存在,则内部ID自增后,为其分配一
个内部ID;如果已经为其分配过内部ID,则把内部ID对应的bitmap对应位置设置为1,且为其分配一
个新内部ID。
这样,当失效的内部ID经过mod_bitset过滤时,就能去掉已经失效的文档了。
举个例子:
文档1含有term: a/b/c, 外部ID为1,插入后,为其分配内部ID为1;
文档1更新,term更新为: a/d/e,更新后,为其分配一个新的内部ID为2,同时把mod_bitset中,内
部ID为1的位置设置为1。当我们搜索a时,可以得到内部ID为1和2的文档,经过mod_bitset过滤后,
文档2得以保留,去掉了失效的文档1。
-3- 如何访问文档属性数据
文档属性数据存储于文件中,以mmap的方式load到内存中,以数组的方式访问,使用内部ID作为偏移
以structmask的机制来访问数据,structmask的原理见这个wiki
(2) 更新
-1- 如何更新倒排索引postinglist
输入: xhead+json-string,有固定的格式,解析过程详见代码flexse/plugin/flexse/
输出: xhead.
测试工具: flexse/flexse/test/update.py,与配置文件flexse/flexse/conf/plugin.config.json
相互对应,目前支持分词/前缀/数组前缀这三种方式
postinglist根据term形成的机制分为两种类型,NLP分词和前缀生成,视频搜索视需求来选择这两
个类型
a) NLP分词形成的term,在flexse/utils/nlp_processor/nlp_processor.cpp中可以设置分词形成
的各个term的描述信息,如tf/idf/offset/title_hit/tag_hit等等,需要注意的是,视频全网
搜索的offset计算,建议使用title即可,因为视频的描述信息在各大网站上看,基本都是空的
b) 前缀生成的term,比如"TAG^搞笑"等等,term的描述一般都为默认值
-2- 如何更新文档属性document-attribute
这部分代码已经完成,原理是根据配置中,迭代STRUCTMASK/document_attr中各个字段,把其中的
key<->value存入vector中,update_thread.cpp中对外部的doc_id进行内部ID分配,然后更新内部
ID对应的document_attribute属性
(3) 查询
输入为xhead+json-string,有固定的格式,解析过程详见代码flexse/plugin/flexse/
输出是xhead+struct数组(不使用json或其他序列化方案是为了性能考虑),返回值表示struct数组
的sizeof大小
查询操作在flexse/plugin/flexse/flexse_plugin.cpp中实现
测试工具: flexse/flexse/test/qquery.py,与配置文件flexse/flexse/conf/plugin.config.json
相互对应,目前支持分词/前缀/数组前缀这三种方式
查询的步骤一般可以分为
a) 根据termlist,读取对应的postinglist。
b) 把一组postinglist交给归并算法进行合并,目前已经支持按照term的权重进行归并(algo.cpp)。
c) 对归并结果postinglist进行过滤,目前已经支持按照某个字段执行(等于/小于/大于/大于小于
/集合这5种过滤)(algo.cpp)
d) 对过滤结果postinglist进行调权,目前已经支持按照某个字段执行(等于/小于/大于/大于小于
/集合这5种调权)(algo.cpp)
e) 按照权重返回top2000的结果,把每个ID的document-attribute带上
-----------------------------------------
(1) 对数据的抽象
-1- 倒排索引
-2- 文档属性
-3- 文档详细
(2) 对流程的抽象
-1- 更新流程
-2- 查询流程
-----------------------------------------
(1) 调权
-1- L0层, query与term的相关性(title_hit/anchor_hit/tag_hit/offset)
-2- L1层, 文档自身属性调权(等于/大于/小于/区间/集合)
-3- L2层, 用户个性化调权(点击调权+用户类型与文档分类切合度)
(2) 过滤
-1- 对文档属性进行(等于/大于/小于/区间/集合)几种过滤
-2- 实现标题内搜索
-3- 站内搜索(等于/集合)
-4- 标签搜索(tag索引)
(3) 排序
-1- 可以按照任意的field进行排序
-2- 可以实现"对信誉度最高的前30个商户按照最近销量排序"
(4) 聚类
-1- 可以根据某个字段进行group_count
-----------------------------------------
(1) query分析
-1- 纠错
-2- 同义词
-3- term的weight
(2) query语法树
-1- a&b&c, b->b|B, c->c|C, a&(b|B)&(c|C)
-2- 按照weight进行merge,实现模糊查询,不必要求每个关键词都命中(百度视频搜索),后续可以强制必须命中某些term
-----------------------------------------
(1) 搜索直达车
-1- SEU(标准实体单元)的资源建设,如电视剧电影->视频搜索,商品信息->电商
-----------------------------------------
(1) 数据的分片(Sharding)
-1- php-interface处对key进行滚动分区(建立一个监控机制)
-2- 如果key不是连续自增的外部ID,则需要对key进行签名,我们为其分配外部ID
-3- 文档详细的访问采用的key为分片时的key,或者是其他形式,如签名
-4- mongodb的sharding访问需要支持按照DB进行sharding
(2) 数据的复制(Repset)
-1- 通过消息队列复制消息,各个服务互不干扰
-2- 对消息队列的进度进行监控,发现异常队列,及时报警
-3- 每个app独占一个消息队列文件序列
-----------------------------------------
画个图来表明flexse是怎么构建的
shijing的wiki
(1) 如何提高可测性
-1- 模块化编程
a) 每个类或函数做简单的事情,一个4百行的函数和linux的管道
b) 性能考虑会打破规律
-2- 面向接口编程
a) 面向实现编程与面向接口编程,要对对象或函数的应用环境考虑清楚(需求),然后设计合适的接口。一句话就是想清楚再干。
b) 类的协作是通过接口来完成的,面向接口编程是复用性的前提,电脑的USB接口
c) 类之间通信简单易懂,扩展性好,提高复用性,扩展性,松耦合
c) 团队更应该使用面向接口编程
-3- 做好异常处理(fileblock的一个异常的例子,尽早的发现错误,测试也是调试,要得到有效的测试)
-4- 只要是接口,就可以执行单元测试(接口就是协议,就是预期,不想是电脑彩票)
(2) 单元测试角度
-1- offset by 1(我灌入了2800万term,测试出了一个bug)
-2- 临界值()
-3- 小数据集合(灯下黑)
-4- 大数据测试
-5- 压力测试(多线程并发)
(3) 单测之前
-1- 编译警告去除
-2- 静态代码检查工具pclint
-3- 运行时测试工具valgrind
-4- 冥思
a) 如果那陀代码很恶心,那他一定会出问题。(重构?: 经历就是财富,不要担心没人关注)
b) 小心代码copy,即使是自己的代码,copy也会出问题(周六的SB-bug)
c) 时常进行codereview
(4) 单元测试好处
-1- 回归测试(我的struct宏曾经几经变动,谢谢test.cpp,别人接手时,也会有信心)
-2- 增强信心(我的代码都是经过单元测试的,如果我现在放弃了,多可惜)
-3- 节奏欢快(把开发的焦点聚焦于当前任务,因为我对之前经过单元测试的代码有信心)
-4- 合作顺畅(我们的代码都是经过单元测试的,代码bug的数量可以得到控制,不会严重打击我们的合作心情)
-5- 大型软件系统中,BUG就像癌症一样,越早发现越好
-6- 专业习惯受益终审
(5) 覆盖率测试
(6) gtest测试