LongLong's Blog

21 May 2016

在实际应用中经常会遇到需要对给定的文本进行关键词搜索的操作，而在关键词较少时，通常的做法是将文本对每一个关键词都进行一次匹配，而随着关键词数量的增加此种算法的效率下降会非常明显。而这里将给出一种给予TrieTree（字典树）的检索算法，能够达到对于关键词个数O(1)的检索效率。

1. TrieTree数据结构

TrieTree可以像字典一样进行数据的存储，例如对于PHP Perl Pear三个单词，用TrieTree进行存储的结果大致如下

<?php
$trie_tree = array(
    'P' => array(
        'H' => array(
            'P' => array(
            ),
        ),
        'e' => array(
            'r' => array(
                'l' => array(
                ),
            ),
            'a' => array(
                'r' => array(
                ),
            ),
        ),
    ),
);

多于多字节组成的编码，如GBK或UTF-8，这里也只需要按照其单子节的编码进行处理即可，因此算法并不依赖于文本的编码，只要保证关键词列表与待检索文本的编码一致即可。另外对于每一个节点还需要标注其是否是某个关键词的结尾，例如PHP和PHP5都是关键词，如果不进行结尾标记，在生成TrieTree时PHP这个关键词就相当于不存在了，当文本中只还有PHP关键词时将不能够匹配成功。

2. TrieTree生成和匹配算法

TrieTree节点包含两部分——子节点散列表和自身是否是某个词的结尾，生成算法是对每一个词，将其按字节插入到TrieTree的每一层中，并在结尾处做标记。匹配时是将文本从第一个字节开始按子节匹配，如果能够匹配到则返回(如果需要匹配到全部，则这里对匹配结果进行记录而不返回)，未能匹配到时，如果第一个字节就没有匹配到则将下一个字节做为开头进行递归匹配，不是第一个字节没有匹配到，则将此位置做为开头进行递归匹配。

<?php
class TrieTreeNode {
    public $h = array();
    public $b = false;    
}

class TrieTree {
    private $root;

    public function __construct() {
        $this->root = new TrieTreeNode();
    }

    public function init($file) {
        $fp = fopen($file, 'r');
        while (($buffer = fgets($fp)) != null) {
            //插入一个词
            $node = $this->root;
            $w = trim($buffer);
            $len = strlen($w);
            for ($i = 0; $i < $len; $i++) {
                //插入每一个字节
                $c = $w[$i];
                //如果不存在对应的节点则进行插入
                if (!array_key_exists($c, $node->h)) {
                    $next = new TrieTreeNode();
                    $node->h[$c] = $next;
                    $node = $next;
                } else {
                    $node = $node->h[$c];
                }
            }
            $node->b = true;
        }
    }

    protected function _match($text, $pos) {
        $len = strlen($text);
        //如果匹配位置已超过文本长度，则匹配失败
        if ($pos >= $len) {
            return false;
        }
        $node = $this->root;
        $match = '';
        for ($i = $pos; $i < $len; $i++) {
            $c = $text[$i];
            if (array_key_exists($c, $node->h)) {
                $match .= $c;
                $next = $node->h[$c];
                $node = $next;
                //匹配到结束为止，返回结果
                if ($next->b) {
                    //匹配的词和匹配的位置
                    return array('w' => $match, 'p' => $pos);
                }
            } else {
                //已到达TrieTree末端还未完成匹配，则退出后重新开始匹配
                break;
            }
        }
        //递归匹配
        return $this->_match($text, $i > $pos ? $i : $pos + 1);
    }

    public function match($text) {
        return $this->_match($text, 0);
    }
}

其时间复杂度只与关键词长（TrieTree高度）和待匹配的文本长度有关，与关键词的个数无关，在关键词非常多时仍能保持较好的性能。但TrieTree的生成过程与关键词的个数有关，如果每次匹配都重新生成TrieTree会丧失TrieTree算法的优势，因此通常可以将生成的TrieTree保持住，可以使用服务化或是将TrieTree结构进行序列化来避免每次重新生成。

3. 服务化

对于此类功能单一的业务逻辑，可以将其作为一种服务单独进行维护，其好处是服务可以在不同的业务之间进行共享。最简单的服务化是将其作为一个HTTP服务，这里使用PHP的swoole扩展进行实现，测试证明其能够提供较好的性能

<?php
$tree = new TrieTree();
$tree->init($argv[1]);

$http = new swoole_http_server("0.0.0.0", 9501);
$http->on('request', function ($request, $response) use($tree) {
    $args = $request->get;
    $match = $tree->match($args['c']);
    $response->end(json_encode($match));
});
$http->start();

使用时将待匹配的文本通过URL参数c进行传递，如果文本较长则可以使用POST来实现。

curl "http://127.0.0.1:9501/?c=%E4%BD%9C%E5%BC%8A%E5%99%A8" -v

HTTP/1.1 200 OK
Server: swoole-http-server
Content-Type: text/html
Connection: keep-alive
Date: Sat, 21 May 2016 05:45:57 GMT
Content-Length: 32

{"w":"\u4f5c\u5f0a\u5668","p":0}

对1000左右数量的关键词进行压力测试，发现性能还是不错的

Server Software:        swoole-http-server
Server Hostname:        127.0.0.1
Server Port:            9501

Document Path:          /?c=%E4%BD%9C%E5%BC%8A%E5%99%A8
Document Length:        32 bytes

Concurrency Level:      20
Time taken for tests:   11.601 seconds
Complete requests:      100000
Failed requests:        0
Total transferred:      18000000 bytes
HTML transferred:       3200000 bytes
Requests per second:    8619.72 [#/sec] (mean)
Time per request:       2.320 [ms] (mean)
Time per request:       0.116 [ms] (mean, across all concurrent requests)
Transfer rate:          1515.18 [Kbytes/sec] received

08 April 2016

目前的HTTP服务器都能够支持对响应内容的gzip处理，即当请求头中含有Accept-Encoding: gzip时，会返回gzip压缩过的响应，并且响应头中包含Content-Encoding: gzip，例如以下的请求和响应头

GET / HTTP/1.1
User-Agent: curl/7.39.0
Host: localhost
Accept: */*
Accept-Encoding: gzip

HTTP/1.1 200 OK
Date: Fri, 08 Apr 2016 14:34:39 GMT
Server: Apache/2.4.18 (Unix) PHP/7.0.5
X-Powered-By: PHP/7.0.5
Vary: Accept-Encoding
Content-Encoding: gzip
Content-Length: 22578
Content-Type: text/html; charset=UTF-8

1. 对请求发送内容进行gzip

而有时候我们希望在请求中发送的内容也使用gzip压缩，虽然浏览器都不支持这一特性，但在手机App中可以使用gzip压缩提交的数据来提高速度也帮助用户节约数据流量。同时我们又希望这一压缩过程对于服务器端的代码是透明的，即Web服务器对收到的内容进行解压。

POST / HTTP/1.1
User-Agent: curl/7.39.0
Host: localhost
Accept: */*
Content-Encoding: gzip
Content-Length: 32
Content-Type: application/x-www-form-urlencoded

HTTP/1.1 200 OK
Date: Fri, 08 Apr 2016 14:43:09 GMT
Server: Apache/2.4.18 (Unix) PHP/7.0.5
X-Powered-By: PHP/7.0.5
Content-Length: 14
Content-Type: text/html; charset=UTF-8

在Apache中只需要增加SetInputFilter deflate，即可实现这一效果。而Nginx中并没有实现这一功能的模块，需要借助Lua来实现这一功能。 在需要使用请求压缩的位置增加以下配置

--开始处加入
init_by_lua '
	zlib = require("zlib");
';

--需要接受压缩请求的位置加入
rewrite_by_lua '
local content_encoding = ngx.req.get_headers()["Content-Encoding"];
if content_encoding == "gzip" then
    ngx.req.read_body();
    local data = ngx.req.get_body_data();
    if data ~= nil then
        local inflated = zlib.inflate()(data);
        ngx.req.clear_header("Content-Encoding");
        ngx.req.clear_header("Content-Length");
        ngx.req.set_body_data(inflated);
    end
end
';

另外需要对Lua的zlib模块进行简单的修改，当发送的内容不是gzip格式时，zlib模块会直接报错退出导致Nginx出现服务器错误，解决方式是取消模块中的报错退出

diff --git a/lua_zlib.c b/lua_zlib.c
index 84d1721..6ebfa47 100644
--- a/lua_zlib.c
+++ b/lua_zlib.c
@@ -92,7 +92,7 @@ static int lz_assert(lua_State *L, int result, const z_stream* stream, const cha
         lua_pushfstring(L, "ZLibError: unknown code %d (%s) at %s line %d",
                         result, stream->msg, file, line);
     }
-    lua_error(L);
+    //lua_error(L);
     return result;
 }

2. 缓存中对gzip的处理

在对HTTP内容的缓存过程中，对于压缩的处理方式一般是保存两份，或是保存一份不要缩的内容然后根据客户端的情况来选择进行压缩或者不进行压缩，然而如今一般的客户端都是支持压缩的，如果能够只缓存一份压缩的内容然后只对不支持压缩的客户端进行内容的解压缩，则能够节约不少的缓存空间。

传统的Nginx＋Memcache缓存的配置如下，其中通过gzip hack强制后段换回不压缩的内容，然后再根据客户端的情况进行压缩

location / {
    gzip on;
    set $key $host$request_uri;
    srcache_fetch GET /memc $key;
    srcache_store PUT /memc $key;
    proxy_set_header Accept-Encoding "";
    proxy_pass http://127.0.0.1:8080;
}   

location /memc {
    internal;
    memc_connect_timeout 100ms;
    memc_send_timeout 100ms;
    memc_read_timeout 100ms;
    memc_ignore_client_abort on; 
    set $memc_key $query_string;
    set $memc_exptime 300;
    memc_pass 127.0.0.1:11211;
}

而实际可以通过Nginx gunzip模块实现根据客户端的情况将保存的压缩内容进行解压处理，其配置和上面非常相似，具体如下

location / {
    gunzip on;
    set $key $host$request_uri;
    srcache_fetch GET /memc $key;
    srcache_store PUT /memc $key;
    proxy_set_header Accept-Encoding "gzip";
    proxy_pass http://127.0.0.1:8080;
}   

location /memc {
    internal;
    memc_connect_timeout 100ms;
    memc_send_timeout 100ms;
    memc_read_timeout 100ms;
    memc_ignore_client_abort on; 
    set $memc_key $query_string;
    set $memc_exptime 300;
    memc_pass 127.0.0.1:11211;
}

这里还需要处理一个问题，srcache模块对于返回带有Content-Encoding响应头的内容会强制不予缓存，需要在其代码中去掉这一逻辑

diff --git a/src/ngx_http_srcache_store.c b/src/ngx_http_srcache_store.c
index ed96ff2..27f78db 100644
--- a/src/ngx_http_srcache_store.c
+++ b/src/ngx_http_srcache_store.c
@@ -150,7 +150,7 @@ ngx_http_srcache_header_filter(ngx_http_request_t *r)
         return ngx_http_srcache_next_header_filter(r);
     }
 #endif
-
+    /*
     if (!slcf->ignore_content_encoding
         && r->headers_out.content_encoding
         && r->headers_out.content_encoding->value.len)
@@ -162,7 +162,7 @@ ngx_http_srcache_header_filter(ngx_http_request_t *r)
                       &r->headers_out.content_encoding->value);

         return ngx_http_srcache_next_header_filter(r);
-    }
+    }*/

     if (slcf->resp_cache_control
         && ngx_http_srcache_response_no_cache(r, slcf, ctx) == NGX_OK)