无锋高级搜索演化之路
无锋高级搜索演化之路
**关键字**: `技术方案`、`编译原理`、`ElasticSearch`、`Django ORM`
本文主要介绍无锋再对 web 类资产实现类似 fofa 的查询方式实现过程的思考、尝试、总结和 bug 处理。
背景介绍
`无锋`服务中的一条 Web 资产字段主要包含以下内容：
| 参数 | 字段名 | 类型 |
| ----------- | -------- | ------ |
| id | 序号 | int |
| domain | 域名 | string |
| ip | IP | string |
| port | 端口 | int |
| title | Title | string |
| body-len | body-len | int |
| fingerprint | 指纹 | string |
| code | 响应码 | int |
| is_cdn | 是否 CDN | Bool |
| is_cloud | 是否云 | Bool |
搜索需求无非就是对这些字段的模糊匹配、精确匹配、范围查询、比较查询。一般常见的搜索情况是再界面上选择某几个条件将数据一步步筛选出来，对筛选条件之间的组合支持不是很灵活。而无锋的高级搜索(我们定义查询规则的一个字符串，以下简称高级搜索)希望能够根据提供出来的字段交由用户自行组合筛选条件。
希望最终实现效果示例:
```python
# Python
domain contains ".qq.com" and \
ip!="203.205.253.183" or \
port in (80, 443) and \
(title contains "腾讯" or \
body-len > 8581) and \
fingerprint=="jQuery" and \
code==200 and \
is_cdn==False and \
is_cloud==False
```- 支持常见比较运算：`>, <, >=, <=, !=, in, not in, contains`
- 支持常见逻辑运算: `and, or, not`
- 支持括号优先级: `()`
有了上面的目标后下面就是该考虑怎么一步步的实现了高级搜索 To Django ORM
无锋中数据库查询使用的是 Django ORM 框架，那么要实现的其实就是将高级搜索的语法转成 django orm 的查询语句，从示例中可以知道最终的搜索语法需要支持逻辑运算 and、or、not 括号优先级，根据经常使用 Django 的经验，很容易想到其中的 Q 对象恰好可以满足这些需求，所以任务进一步精确下来，最终需要做的事情就是将高级搜索字符串解析成 Q 对象查询语法
```python
# Django Q对象使用示例:
# ADN 查询
Q(name__contains="a") & Q(age=20)
# OR 查询
Q(name__contains="a") | Q(age=20)
# NOT 查询
~Q(name__contains="a")
# OR, AND, NOT 多条件查询
Q(name__contains="a") & Q(age=20) | Q(group__contains="b") & ~Q(id=1)
```
那么第一个问题，如何将高级搜索解析成 Django Q 查询语法？
这个过程不难看出很像一个编译器，需要对高级搜索字符串中的语法进行分析提取出其中的逻辑和比较关系最终“编译”成 Q 查询语句。说到编译，上学时候没有好好听编译原理的课不会词法分析、语法分析也不用紧张，这里并没有真正的编译器那么复杂，而且也不需要亲自下场去处理底层的词法分析和语义分析，因为已经有人造好了轮子 Python 的 Ply 库具有强大的 lex (Lexical Analyzar 词法分析器)和 yacc (yet another compiler compiler 编译器代码生成器）的实现，提供了大多数标准 lex/yacc 特性。有了 Ply 后可以将高级搜索语句拆解一下：
- **第一步** 将字符串通过正则匹配解析成有意义的**Token**:
根据需求，定义了一下几种 Token 类型，高级搜索字符串都可以被解析成以下 Token 的组合 - 查询字段 - 数值数组 - 字符串数组 - 数字 - 字符串 - bool 值 - 逻辑运算符(and|or|not) - 比较运算符(>|<|=|contains|...) - 左括号 - 右括号
> 简单解释一下如何将一个完整的字符串解析成上面有意义的 Token
**查询字段**: 如domain, title前传入ply, 完全匹配上其中一个就认为该部分是一个*查询字段*
**数字**: 正则匹配[0-9]成功就认为是一个数字，其他Token同理, 大多数Token都能通过正则匹配出来
- **第二步** 通过 Token 组合成最小**查询因子**
- `domain == "baidu.com" ` (查询字段 + 比较运算符 + 字符串)
- `is_cdn == True` (查询字段 + 比较运算符 + bool 值)
- `port > 8000` (查询字段 + 比较运算符 + 数字)
- **第三步**将查询因子与逻辑运算符组合成一个**表达式**
- `domain == "baidu.com" and is_cdn == True` (查询因子 + 逻辑运算符 + 查询因子)
- `domain == "baidu.com" and (is_cdn == True or port in [80, 443])` (查询因子 + 逻辑运算符 + 表达式)
ply 帮我处理的是我只需要告诉它怎样 Token 组合在一起是一个**查询因子**, 参见第二步例子。怎样的**查询因子**和**Token**组合在一起是一个**表达式**或怎样的**查询因子**、**Token**和**表达式**组合是一个新的**表达式**，参见第三步例子
通过 ply 的处理后，高级搜索字符串从一个普通字符串变成了程序可以读懂的有意义的字符串了，接下来就是在这三步语法分析过程中分别将字符串内容转化成 Q 查询语句的内容
第一步中的 Token 只是为了识别出字符串中最小单位，还不需要进行转化
第二步中的查询因子正好对应一个 Q 对象：
```python
# Python
# domain == "baidu.com"
Q(domain=”baidu.com”)
# is_cdn == True
Q(is_cdn=True)
# port > 8000
Q(port__gt=8000)
```
第三步表达式对应 Q 对象中的逻辑运算:
```python
# domain == "baidu.com" and is_cdn == True and port > 8000
Q(domain="baidu.com") & is_cdn == True & Q(is_cdn=True)
```只需在每一步中完成对应转换逻辑编写，组合起来就完成了高级搜索到 Django ORM 查询语句的转换， 看下实际效果：
```python
# 高级搜索语法:
domain contains "baidu.com"
# 转换后的Q查询语法:
(AND: ('domain__icontains', 'baidu.com'))
# 高级搜索语法:
domain contains "baidu.com" and \
ip == "127.0.0.1" or port in (80,443)
# 转换后的Q查询语法:
(OR: (AND: ('domain__icontains', 'baidu.com'), \
('ip', '127.0.0.1')), ('port__in', [80, 443]))
# 高级搜索语法:
domain contains "baidu.com" and \
ip == "127.0.0.1" or \
(port in (80,443) and title contains "Welcome")
# 转换后的Q查询语法:
(OR: (AND: ('domain__icontains', 'baidu.com'), ('ip', '127.0.0.1')), \
(AND: ('port__in', [80, 443]), ('title__icontains', 'Welcome')))
```这里想提一下的是语法设计兼容性一定要强，因为用户的输入总是很难把握，各种符号要考虑同时支持中英文输入，特别是经常容易导致问题的中文引号，中文括号。字符串也要适当考虑大小写支持，不管是大写开头还是大写结尾哪怕中间大写也要能正确识别
高级搜索 To ElasticSearch query_string
之所以继续转成 ElasticSearch 中的 query_string 是因为在前期的时候我们 web 资产中的数据并没有 body、证书等信息，而这些信息数据量比较大，往往这一个字段所占的空间就是其他字段所占空间的几十上百倍不止，继续存储在数据库中需要占用大量的空间自不必说，也很容易影响查询性能。团队中开始规划 web 数据存储两套的方案，一份存在数据库支持数据库的关联查询，一份存在 ElasticSearch，是全量的数据包含 body、cert 等数据量大的字段，支持高级搜索
所以我需要把第一版高级搜索转数据库查询的实现改为转成 ElasticSearch 的查询，为了快速实现功能，我选择了将查询语法转成了 ElasticSearch query_string 的查询，因为 query_string 的语法实在是跟我定义的高级搜索语法十分相似，转换过来成本比较低。再加上前面已经写过一次词法分析转换的逻辑，再次写也是轻车熟路了
```python
es query_string查询例子
{
"query": {
"query_string": {
"query": "(title:*404* AND (port:443 OR port:80) \
AND body:htm AND NOT status_code:404 \
OR body_length:(159 OR 200 OR 300) AND port:>=81) \
OR port:80 OR fingerprints.name:jquery"
}
},
"from": 0,
"size": 1000
}
```再对比一下高级搜索语法
```python
domain contains ".qq.com" and \
ip!="203.205.253.183" or \
port in (80, 443) and \
(title contains "腾讯" or body-len > 8581) and \
fingerprint=="jQuery" and \
code==200 and \
is_cdn==False and \
is_cloud==False
```
整体结构看起来是比较相似的，甚至于不用词法分析只是单纯字符串替换应该都可以实现转换。但好景不长很快因为对 qeury_string 特性的不够了解踩了高级搜索实现路上最大的一个坑，query_string 并不能很好的满足查询需求，例如常见的模糊搜索:
query_string 中查询"中国软件", "软件中国"这种情况也会命中，这是因为在 es 中"中国软件"会被分词成为"中国", "软件"两个词，而"软件中国"也是能命中目标的，query_string 查询 text 类型字段时并不要求连续，顺序还可以调换。这就会导致查出大量非预期数据。
这也是在使用了大概一周后才发现的，继而导致需要再次重新实现一套高级搜索转换方案，这也警醒我下回做方案一定要调研足够充分，这样才能避免返工，非常遗憾的是因为这个方案的生命周期太短，代码都找不到了，没有办法在这里展示最终效果。
### 高级搜索 To ElasticSearch DSL
前面提到 query_string 并不能很好的满足需求，这里来到了第三次高级搜索转换方案的实现，也是目前无锋一直在用的高级搜索，使用时间最长的一个方案。
将高级搜索转换成常规的 ElasticSearch DSL(查询表达式)，一开始没有选择它是因为转换过程实现起来相对要复杂一些，时间成本也更大一些，但实现主要原理过程都是一样的，差别一些细的点的处理上
高级搜索语法
```python
domain contains "baidu.com" and ip == "127.0.0.1" or port in [80,443]
```经过转换后的 es 查询语法
```json
{
"bool": {
"must": [
{ "bool": { "must": [{ "match_phrase": { "domain": "baidu.com" } }] } },
{
"bool": {
"should": [
{ "bool": { "must": [{ "term": { "ip.keyword": "127.0.0.1" } }] } },
{ "bool": { "must": [{ "terms": { "port": [80, 443] } }] } }
]
}
}
]
}
}
```从例子中可以看到非常短的一个高级搜索语法转换成 es 查询语法后就会变得比较复杂，这是是为什么一开始没有选择它的原因之一。因为三套方案主体语法分析转化逻辑基本一样，这里只贴一下高级搜索转 es 查询语句的核心部分代码。
```python
# 解析查询表达式因子
def p_compare_expression_compare_number_string_boolean(p):
"""compare_expression : QUERY_FIELD COMPARE_OPERATOR NUMBER
| QUERY_FIELD COMPARE_OPERATOR STRING
| QUERY_FIELD COMPARE_OPERATOR BOOLEAN
| QUERY_FIELD COMPARE_OPERATOR STRING_LIST
| QUERY_FIELD COMPARE_OPERATOR NUMBER_LIST"""
field = fields.get(p[1], p[1]) # 将输入字段转成数据库字段
operator = p[2]
data = p[3]
if operator == ">":
p[0] = {"range": {field: {"gt": data}}}
elif operator == "<":
p[0] = {"range": {field: {"lt": data}}}
elif operator == ">=":
p[0] = {"range": {field: {"gte": data}}}
elif operator == "<=":
p[0] = {"range": {field: {"lte": data}}}
```
```python
elif operator == "==":
# 此为特殊处理: str类型，es同时存储分词和不分词两种模式字段
if isinstance(data, str):
field = f"{field}.keyword"
p[0] = {"term": {field: data}}
elif operator == "!=":
# 此为特殊处理: str类型，es同时存储分词和不分词两种模式字段
if isinstance(data, str):
field = f"{field}.keyword"
p[0] = {"bool": {"must_not": {"term": {f"{field}": data}}}}
elif operator == "contains":
p[0] = {"match_phrase": {field: data}}
elif operator == "not contains":
p[0] = {"bool": {"must_not": {"match_phrase": {field: data}}}}
elif operator == "in":
# 此为特殊处理: str类型，es同时存储分词和不分词两种模式字段
if isinstance(data, str):
field = f"{field}.keyword"
p[0] = {"terms": {field: data}}
elif operator == "not in":
# 此为特殊处理: str类型，es同时存储分词和不分词两种模式字段
if isinstance(data, str):
field = f"{field}.keyword"
p[0] = {"bool": {"must_not": {"terms": {field: data}}}}
```
写在最后
实际实现过程遇到的问题还是挺多的，但因为没有有效的记录，很多都忘了没能拿出来分享，所以在以后的工作过程中及时的记录问题即及如何解决的还是非常重要的。后期其实语法分析的这部分已经非常稳定了，后期容易出现问题的还是 es 查询本身，因为一些分词的特性时不时发现一些非预期查询效果，这里也非常欢迎与熟悉 es 的师傅来交流。
---
**无锋团队** 陈少波
