Looyao's Blog

记录一些点滴

一个简单高效的搜索建议服务实现

| Comments

一个好的搜索建议服务,可以有效的提升搜索体验和搜索结果准确度。本文讲一下实现一个简单高效的搜索建议服务。

1、数据结构&算法准备

先google一番,发现有两个数据结构比较合适,ternary search treedouble-array trie,看了几篇相关的blog,感觉ternary search tree比较容易实现,效率对比貌似没有double-array trie高,但感觉基本已经足够。所以这里数据结构选择ternary search tree。这里就不在赘述ternary search tree,感兴趣的可以google,或者看本文下边参考资料链接。

由于ternary search tree是前缀树,只能进行前缀匹配,为了可以后缀匹配,这里使用的比较粗暴的办法,加入alias,将搜索热门词分解后缀,插入到ternary search tree里边,如字符串愤怒的小鸟,分解为:

怒的小鸟
的小鸟
小鸟
鸟

以上的字符串都是愤怒的小鸟的别名,也就是都对应愤怒的小鸟,搜小鸟也可以显示出愤怒的小鸟,这样的确是浪费了很多空间,但是可以简单解决后缀匹配问题。为了节省空间,可以只让热门词汇插入后缀,可以进行后缀匹配。什么是热门词汇?就是搜索频率较高的,可以根据实际情况来决定数值判定标准。

同理,拼音也是通过alias方案解决。如fennudexiaoniao就是愤怒的小鸟的别名,这样搜fen的时候,愤怒的小鸟就会出现。

结果排序,这个就比较简单,遍历到所有匹配串之后,根据热度(下载量或点击量)来排序,这里使用快速排序算法。

2、如何提供高效服务?

本计划用C或C++实现一个FastCGI服务,nginx调用然后提供WEB服务,后来想着为何不直接做到nginx里边呢,所以决定写一个nginx的扩展,使用nginx的共享内存来存储词典数据和结果缓存,nginx的worker进程间可以使用同一块内存。

项目地址:

https://github.com/looyao/ngx_auto_complete_module

感兴趣的可以下载。

3、安装 & 配置

编译nginx时加入

1
2
./configure --prefix=/path/to/nginx --add-module=/path/to/ngx_auto_complete_module
make && make install

nginx配置文件

1
2
3
4
5
6
7
8
9
10
11
12
http {
    ...
    server {
        listen 80;
        ...
        location /su {
            auto_complete_dict_path /path/to/dictionary.txt shm_zone=auto_complete:1024m;
        }
        ...
    }
    ...
}

配置命令: auto_complete_dict_path

参数1: `/path/to/dictionary.txt`,词典文件路径
参数2: `shm_zone=auto_complete:1024m`,表示共享内存名子`auto_complete`,共享内存大小为`1024m`,也就是1GB,具体可以根据实际情况修改。

字典文件格式说明

1
2
3
4
5
1000||愤怒的小鸟
0||fennudexiaoniao||愤怒的小鸟
512||真实赛车3
0||zhenshisaiche3||真实赛车3
512||real racing 3

||是分隔符,第一栏是热度(下载或者点击量等),目前策略是热度超过100会插入后缀。

如果有两栏,则第二栏就是正常待搜索字串。

如果有三栏,则第二栏是第三栏的别名,如搜索fennu,则会显示出来愤怒的小鸟。

1
2
[looyao@vm ~]$ curl localhost/su?s=fennu
["愤怒的小鸟"]

搜索建议匹配结果使用JSON格式输出。

如何生成字典文件呢?这个需要根据自己实际情况,将统计到的热门词或者其他需要提供搜索建议的词写入到字典文件,这里可以使用脚本语言来生成(perl,python,php等),包括汉字转拼音。

4、性能测试

目前只是简单的ab测试过,测试字典中有297960个词。

我的Mac机配置

CPU: Intel® Core™ i5-2435M CPU @ 2.40GHz

内存: 8GB

虚拟机只分配了1G内存

nginx配置: worker_processes设置为2,worker_connections设置为8192。

贴一下在Mac上的CentOS虚拟机中的测试结果(ab -n 4000 -c 4000)

命中缓存的ab测试结果

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
Server Software:        nginx/1.4.7
Server Hostname:        localhost
Server Port:            80

Document Path:          /su?s=q
Document Length:        1870 bytes

Concurrency Level:      4000
Time taken for tests:   0.357 seconds
Complete requests:      4000
Failed requests:        0
Write errors:           0
Total transferred:      8188000 bytes
HTML transferred:       7480000 bytes
Requests per second:    11210.95 [#/sec] (mean)
Time per request:       356.794 [ms] (mean)
Time per request:       0.089 [ms] (mean, across all concurrent requests)
Transfer rate:          22410.95 [Kbytes/sec] received

Connection Times (ms)
              min  mean[+/-sd] median   max
Connect:       73  110  25.6    105     160
Processing:    82  100  10.0    100     127
Waiting:       55   87  19.5     94     127
Total:        173  210  19.1    207     247

Percentage of the requests served within a certain time (ms)
  50%    207
  66%    219
  75%    226
  80%    231
  90%    240
  95%    243
  98%    245
  99%    246
 100%    247 (longest request)

没有命中缓存的测试结果

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
Server Software:        nginx/1.4.7
Server Hostname:        localhost
Server Port:            80

Document Path:          /su?s=angry
Document Length:        753 bytes

Concurrency Level:      4000
Time taken for tests:   0.846 seconds
Complete requests:      4000
Failed requests:        0
Write errors:           0
Total transferred:      3712000 bytes
HTML transferred:       3012000 bytes
Requests per second:    4727.55 [#/sec] (mean)
Time per request:       846.104 [ms] (mean)
Time per request:       0.212 [ms] (mean, across all concurrent requests)
Transfer rate:          4284.34 [Kbytes/sec] received

Connection Times (ms)
              min  mean[+/-sd] median   max
Connect:       86  115  17.7    114     155
Processing:    80  313 164.8    308     606
Waiting:       79  312 165.8    308     606
Total:        209  428 147.7    422     692

Percentage of the requests served within a certain time (ms)
  50%    422
  66%    509
  75%    556
  80%    585
  90%    639
  95%    666
  98%    681
  99%    687
 100%    692 (longest request)

是否命中缓存在HTTP响应头中有标识

X-AC-Cached: no

no表示没有缓存,yes表示有缓存。 可以用curl来测试是否有缓存,例如

curl -i http://localhost/su?s=q 

测试比较单一,可能不具备普遍性,但是可以看到基本可以处理比较高的并发请求数。

感兴趣可以试试,有bug或者其他建议的欢迎评论留言。

参考资料

1、http://igoro.com/archive/efficient-auto-complete-with-a-ternary-search-tree/ 2、http://www.drdobbs.com/database/ternary-search-trees/184410528 3、http://www.evanmiller.org/nginx-modules-guide-advanced.html 4、http://www.evanmiller.org/nginx-modules-guide.html

Comments