xiaobaoqiu Blog

Think More, Code Less

Memcached安全性

1.Memcached -l参数

最近整理了组内使用的Memcached。发现很多问题,其中一个问题就是开发机器测试机器可以直连线上的Memcached。这也是memcached公认的问题:memcached 是一种很简单、有效的协议,但也有其缺点,就是 memcached 自身没有 ACL 控制(或者相当弱)。

Memcache服务器端都是直接通过客户端连接后直接操作,没有任何的验证过程,这样如果服务器是直接暴露在互联网上的话是比较危险,轻则数据泄露被其他无关人员查看,重则服务器被入侵。

乌云也爆料过很多网站的memcached的安全性问题: http://www.wooyun.org/bugs/wooyun-2010-0790 http://www.wooyun.org/bugs/wooyun-2013-023891 http://www.wooyun.org/bugs/wooyun-2013-037301

通过-l参数可以再已定成都上做到安全的限制:

  1. 如果限定只要自己能够使用本机的Memcached,可以直接将-l参数绑定到回路地址127.0.0.1.
  2. 如果是后台系统且有自己的私有IP,最好将-l参数绑定到私有IP上(比如192.168.0.200).

如果Memcached非要挂在公网IP上,就需要做防火量限制,如下面说道的iptables。

2.使用iptable

ACL 最简单的设置方法就是在网络层,直接拒绝掉你的访问,通过iptable可以实现这个功能。

假如我们的一台 memcached 的机器,想拒绝除了自身之外的访问,假如机器自己IP是:XX.XX.XX.184,那么我们可以以root身份用下面几条命令来达到我们的目的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
[baoqiu.xiao@... ~]sudo iptables -A INPUT -p tcp -s 127.0.0.1 --dport 6666 -j ACCEPT
[baoqiu.xiao@... ~]sudo iptables -A INPUT -p tcp -s XX.XX.XX.184 --dport 6666 -j ACCEPT
[baoqiu.xiao@... ~]sudo iptables -A INPUT -p tcp --dport 6666 -j REJECT

[baoqiu.xiao@... ~]sudo iptables -L -n --line-number
Chain INPUT (policy ACCEPT)
num  target     prot opt source               destination         
1    ACCEPT     tcp  --  127.0.0.1            0.0.0.0/0           tcp dpt:6666 
2    ACCEPT     tcp  --  XX.XX.XX.184         0.0.0.0/0           tcp dpt:6666 
3    REJECT     tcp  --  0.0.0.0/0            0.0.0.0/0           tcp dpt:6666 reject-with icmp-port-unreachable 

Chain FORWARD (policy ACCEPT)
num  target     prot opt source               destination         

Chain OUTPUT (policy ACCEPT)
num  target     prot opt source               destination

这里使用的是iptables的filter功能,其filter是一种链式结构且有从前往后依次执行。满足某一条filter规则就不往下走了。因此基于这个原则,我们需要将最严格的规则放在最前面。

删除某一条规则,其中的1就是iptables -L -n –line-number中的num号。如下会删除Chain INPUT中的编号为1的规则:

1
[baoqiu.xiao@... ~]sudo iptables -D INPUT 1

可以使用iptables -F 清空所有规则.

3.不需要Root权限

启动Memcached不需要Root权限,这样能避免Memcached被入侵而造成更大的危害。

参考: http://blog.couchbase.com/memcached-security http://serverfault.com/questions/424324/how-to-secure-memcached

Libphonenumber

1.简介

最近项目中做短信发送相关的工作.涉及到国内手机和国际手机.因此第一步需要解析电话获取国家码.

使用的库是Google提供的著名开源库libphonenumber.有的App的手机号码归属地等功能就是使用这个实现的。支持Java, C++ 和 JavaScript。

libphonenumber是一个手机号码工具类,提供了手机号码的格式化,解析,校验等功能.典型的比如:

  1. 解析手机号码,获取国际码;
  2. 根据国家代码和手机号,判断手机号是否有效;
  3. 根据国家代码和手机号,判断手机运营商
  4. 根据国家代码和手机号,手机归属地

Git地址: https://github.com/googlei18n/libphonenumber

国家码参考:http://country-code.cl/

2.使用Demo

Maven引入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    <!--手机号解析-->
    <dependency>
        <groupId>com.googlecode.libphonenumber</groupId>
        <artifactId>libphonenumber</artifactId>
        <version>7.2.1</version>
    </dependency>
    <!--手机归属地定位相关-->
    <dependency>
        <groupId>com.googlecode.libphonenumber</groupId>
        <artifactId>geocoder</artifactId>
        <version>2.9</version>
    </dependency>
    <!-- 手机运营商相关 -->
    <dependency>
        <groupId>com.googlecode.libphonenumber</groupId>
        <artifactId>carrier</artifactId>
        <version>1.21</version>
    </dependency>

简单代码如下

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
public class LibphonenumberUsage {

    private static final PhoneNumberUtil phoneNumberUtil = PhoneNumberUtil.getInstance();

    private static PhoneNumberToCarrierMapper carrier = PhoneNumberToCarrierMapper.getInstance();

    private static PhoneNumberOfflineGeocoder geocoder = PhoneNumberOfflineGeocoder.getInstance();

    private static final String DEFAULT_COUNTRY = "CN";

    private static final String[] phoneCases = new String[] {
            "00861861****515",  //中国
            "008869****7718",   //台湾
            "00658****994",     //新加坡
            "1591****718",      //中国
            "00820****704546",  //Korea
            "1709****155"       //中国170
    };

    private static final String[] countryCodes = new String[]{
            "886",      //台湾
            "65",       //新加坡
            "86",       //中国
            "82",       //Korea
            "86"        //中国170
    };
    private static final String[] phones = new String[]{
            "972****718",        //台湾
            "82****94",         //新加坡
            "1591****718",      //中国
            "1074****46",       //Korea
            "1709****155"       //中国170
    };

    public static final Map<String, String> CHINESE_CARRIER_MAPPER = Maps.newHashMap();
    static {
        CHINESE_CARRIER_MAPPER.put("China Mobile", "中国移动");
        CHINESE_CARRIER_MAPPER.put("China Unicom", "中国联通");
        CHINESE_CARRIER_MAPPER.put("China Telecom", "中国电信");
    }

    public static void main(String[] args) {
//        parsePhone();

//        validPhone();

//        phoneCarrierCase();

        phoneGeoCase();
    }

    /**
     * 电话解析case
     */
    private static void parsePhone() {


        for(String phone : phoneCases) {
            Phonenumber.PhoneNumber pn = doParse(phone);
            System.out.println(phone + " --> " + pn.getCountryCode() + ", " + pn.getNationalNumber());
        }
    }

    /**
     * 解析逻辑
     */
    private static final Phonenumber.PhoneNumber doParse(String phone) {
        try {
            return phoneNumberUtil.parse(phone, DEFAULT_COUNTRY);
        } catch (NumberParseException e) {
            throw new NumberFormatException("invalid phone number: " + phone);
        }
    }

    /**
     * 电话解析case
     */
    private static void validPhone() {
        for (int i = 0; i < countryCodes.length; i++) {
            boolean valid = doValid(countryCodes[i], phones[i]);
            System.out.println(countryCodes[i] + " , " + phones[i] + " --> " + valid);
        }
    }

    /**
     * 手机校验逻辑
     */
    private static boolean doValid(String countryCode, String phoneNumber){
        int ccode = Integer.parseInt(countryCode);
        long phone = Long.parseLong(phoneNumber);

        Phonenumber.PhoneNumber pn = new Phonenumber.PhoneNumber();
        pn.setCountryCode(ccode);
        pn.setNationalNumber(phone);

        return phoneNumberUtil.isValidNumber(pn);
    }

    private static void phoneCarrierCase() {
        for (int i = 0; i < countryCodes.length; i++) {
            String carrier = doCarrier(countryCodes[i], phones[i]);
            System.out.println(countryCodes[i] + " , " + phones[i] + " --> " + (CHINESE_CARRIER_MAPPER.containsKey(carrier)?CHINESE_CARRIER_MAPPER.get(carrier):carrier));
        }
    }

    /**
     * 手机运营商
     */
    private static String doCarrier(String countryCode, String phoneNumber){
        int ccode = Integer.parseInt(countryCode);
        long phone = Long.parseLong(phoneNumber);

        Phonenumber.PhoneNumber pn = new Phonenumber.PhoneNumber();
        pn.setCountryCode(ccode);
        pn.setNationalNumber(phone);

        //返回结果只有英文,自己转成成中文
        return carrier.getNameForNumber(pn, Locale.ENGLISH);
    }

    private static void phoneGeoCase() {
        for (int i = 0; i < countryCodes.length; i++) {
            String geo = doGeo(countryCodes[i], phones[i]);
            System.out.println(countryCodes[i] + " , " + phones[i] + " --> " + geo);
        }
    }

    /**
     * 手机归属地
     */
    public static String doGeo(String countryCode, String phoneNumber){
        int ccode = Integer.parseInt(countryCode);
        long phone = Long.parseLong(phoneNumber);

        Phonenumber.PhoneNumber pn = new Phonenumber.PhoneNumber();
        pn.setCountryCode(ccode);
        pn.setNationalNumber(phone);

        return geocoder.getDescriptionForNumber(pn, Locale.CHINESE);
    }
}

3.注意点

  1. 电话解析的时候需要加上00前缀才能解析成功,比如008615912345678能解析,但是8615912345678不能解析成功;

  2. libphonenumber的基础信息库也是不断更新,比如libphonenumber的7.0.2版本不能解析170号段的电话,7.0.3以后就支持了;

Lucene整体架构

根据上篇文章,我们大致知道Lucene创建索引和搜索的一个过程:

这里主要分析一下Lucene的代码结构,包括理由Lucene API实现一个简单建立索引和搜索的小例子.

由于我们的服务器上crate是基于Lucene 4.10.3版本.所以我这里采用的Lucene版本也是4.10版本,小版本是4.10.4,是Lucene 4的最后一个版本,大约2014年9月推出,还比较新鲜.目前已经到了5.3版本.

1.源码结构

首先看一下Lucene的源码结构,Lucene-core主要代码包结构如下:

每个包下面都有package.html文件介绍包的作用.各个包的作用如下:

1.analysis
分词模块,包含将文本转化为可索引化/可搜索化的词元(convert text into indexable/searchable tokens)的API和实现.包括org.apache.lucene.analysis.Analyzer和其相关类.
2.codecs
包含自定义底层索引的编码和索引结构的模块,还包括索引的压缩,索引版本管理等.
3.document
定义了被索引和搜索内容的用户层面的逻辑定义,就是我们熟悉的Document,各种类型的Filed及其属性定义等.同事也提供了一下org.apache.lucene.document.Document和org.apache.lucene.index.IndexableField相关的工具类.
4.index
包含了索引维护(创建,更新,删除)和访问(读)的逻辑.包括我们熟悉的IndexReader,IndexWriter等.
5.search
索引的搜索.包括相似度的定义(similarities包),权重计算,文档评分计算,布尔模型,搜索结果搜集等逻辑.
6.store
索引底层二进制数据的读写,包括索引文件的Buffered的流的实现等,还包括一些限流策略的实现(RateLimiter)等.
7.util
工具类,如排序器,数学工具类,优先级队列等工具的实现等.

包基本上和本文开头的图对应起来,其中的QueryParser再Lucene4中是一个单独的jar包:

2.Lucene使用Demo

首先上一个Lucene的简单的Demo,基本上是参考官网提供的Demo,自己手动修改了点,作用就是索引一个目录下的文本文件,在此基础上提供搜索服务.其中Indexer用于创建索引,Searcher作为搜索入口,接受用户输入的Query词并执行搜索.

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
/**
 * 创建索引
 *
 * @author: xiaobaoqiu  Date: 15-9-8 Time: 下午4:04
 */
public final class Indexer {

    public static void main(String[] args) {
        indexDocs(CommonConfig.SOURCE_FILE_DIR, CommonConfig.INDEX_FILE_DIR, true);
    }

    /**
     * 构建磁盘索引
     *
     * @param dirPath 原始文件
     * @param indexPath 索引文件存放路径
     * @param create    创建or更新
     */
    public static void indexDocs(String dirPath, String indexPath, boolean create) {
        try {
            Directory dir = FSDirectory.open(new File(indexPath));
            Analyzer analyzer = new StandardAnalyzer(Version.LUCENE_4_10_0);
            IndexWriterConfig iwc = new IndexWriterConfig(Version.LUCENE_4_10_0, analyzer);

            if (create) {
                iwc.setOpenMode(IndexWriterConfig.OpenMode.CREATE);
            } else {
                iwc.setOpenMode(IndexWriterConfig.OpenMode.CREATE_OR_APPEND);
            }

            IndexWriter writer = new IndexWriter(dir, iwc);
            doIndexDocs(writer, new File(dirPath));

            System.out.println("Build index finished...");
            writer.close();
        }catch (IOException ioe) {
            //do something...
        }
    }

    static void doIndexDocs(IndexWriter writer, File file) throws IOException {
        if (!file.canRead()) {
            System.out.println("文件不可读:" + file.getAbsolutePath());
            return;
        }

        //文件夹则索引文件夹下的索引文件
        if (file.isDirectory()) {
            String[] files = file.list();
            if (files != null) {
                for (int i = 0; i < files.length; i++) {
                    doIndexDocs(writer, new File(file, files[i]));
                }
            }
        } else {
            doIndexFile(writer, file);
        }
    }

    /**
     * 索引一个文件
     *
     * @param writer
     * @param file
     */
    private static void doIndexFile(IndexWriter writer, File file) throws IOException{
        //单个文件
        FileInputStream fis;
        try {
            fis = new FileInputStream(file);
        } catch (FileNotFoundException fnfe) {
            //do nothing
            return;
        }

        try {
            // 创建一个新的空的Document
            Document doc = new Document();

            //文件路径字段
            doc.add(new StringField(CommonConfig.PATH_FIELD_NAME, file.getPath(), Field.Store.YES));
            //文件最后修改时间字段
            doc.add(new LongField(CommonConfig.MODIFIED_FIELD_NAME, file.lastModified(), Field.Store.NO));
            //文件内容,不存储原始串
            doc.add(new TextField(CommonConfig.CONTENTS_FIELD_NAME, new BufferedReader(new InputStreamReader(fis, StandardCharsets.UTF_8))));

            //新建索引 or 更新索引
            if (writer.getConfig().getOpenMode() == IndexWriterConfig.OpenMode.CREATE) {
                writer.addDocument(doc);
            } else {
                writer.updateDocument(new Term("path", file.getPath()), doc);
            }
        } finally {
            fis.close();
        }
    }
}

/**
 * 查询索引
 * 接受用户输入作为Query词
 *
 * @author: xiaobaoqiu  Date: 15-9-8 Time: 下午4:09
 */
public final class Searcher {

    public static void main(String[] args) throws Exception {
        search(CommonConfig.INDEX_FILE_DIR, CommonConfig.CONTENTS_FIELD_NAME);
    }

    public static void search(String indexPath, String field) throws Exception {
        IndexReader reader = DirectoryReader.open(FSDirectory.open(new File(indexPath)));
        IndexSearcher searcher = new IndexSearcher(reader);
        Analyzer analyzer = new StandardAnalyzer(Version.LUCENE_4_10_0);
        QueryParser parser = new QueryParser(Version.LUCENE_4_10_0, field, analyzer);

        //接受用户输入
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in, StandardCharsets.UTF_8));
        String queryString = null;
        while (StringUtils.isNotEmpty(queryString = in.readLine())) {
            Query query = parser.parse(queryString.trim());

            doSearch(searcher, query);
        }
        reader.close();
    }

    public static void doSearch(IndexSearcher searcher, Query query) throws IOException {
        // 搜索 CommonConfig.SEARCH_MAX_ITEM_COUNT 个数据
        TopDocs results = searcher.search(query, CommonConfig.SEARCH_MAX_ITEM_COUNT);
        ScoreDoc[] hits = results.scoreDocs;
        int numTotalHits = results.totalHits;
        System.out.println(numTotalHits + " total matching documents");

        if (ArrayUtils.isEmpty(hits)) return;

        for (ScoreDoc hit : hits) {
            System.out.println();
            Document hitDoc = searcher.doc(hit.doc);
            System.out.println(CommonConfig.PATH_FIELD_NAME + " = " + hitDoc.get(CommonConfig.PATH_FIELD_NAME) +
                    "\n" + CommonConfig.MODIFIED_FIELD_NAME + " = " + hitDoc.get(CommonConfig.MODIFIED_FIELD_NAME) +
                    "\n" + CommonConfig.CONTENTS_FIELD_NAME + " = " + hitDoc.get(CommonConfig.CONTENTS_FIELD_NAME));
        }
    }
}

输入的文件及生成的索引:

建立索引的基本过程如下:

1.FSDirectory定义索引文件存放目录
2.选择分词使用的Analyzer.
3.选择索引文件版本信息Version,将其和Analyzer组成IndexWriterConfig.
4.利用IndexWriterConfig生成一个IndexWriter,用于索引文件的变更;
5.根据原始文件生成一些列的Document,每个文档中包含多个Field,设置每个Field是否分词,释放存储等属性;
6.使用IndexWriter将文档写入索引文件.

搜索的基本过程如下:

1.根据索引文件的目录生成一个IndexReader,将索引文件读到内存中.
2.生成一个IndexSearcher用于搜索;
3.选择一个分词器;
4.定义用户输入Query的解析器QueryParser;
5.接受用户输入,执行搜索过程,得到搜索结果用TopDocs表示,其中包含了命中文档的数目以及命中文档的id集合;
6.根据文档id获取对应的文档,从文档中获取各个Field信息;

2.1 主要类

首先介绍一下其中涉及到的主要的类:

  • FSDirectory Lucene文件操作都是通过Directory实现,其中有一个比较特殊的方法sync,用来保证任何对文件的写都能够得到永久保存。Lucene使用这个来保证正确提交索引数据变更,也能够防止机器或者操作系统级别的错误影响(corrupting)索引数据.

  • Analyzer,StandardAnalyzer

  • Version
  • IndexWriterConfig
  • IndexWriter
  • Document
  • StringField,LongField,TextField
  • IndexReader,DirectoryReader
  • IndexSearcher
  • QueryParser
  • Query
  • TopDocs
  • ScoreDoc

3.建立索引流程

4.搜索流程

Lucene入门

Crate再项目中扮演越来越重要的角色.但是很多时候我对Crate,包括其下层的ElasticSearch以及Lucene都是一知半解,甚至可以说是完全不懂.因为没看过源代码.所以这段时间会集中学习一下Lucene和ElasticSearch的源码.

从Lucene开始.会包含以下内容:

1.Lucene简介;
2.Lunece整体架构;
3.Lucene的存储;
4.Lucene的搜索;
5.Lucene其他功能,如高亮等;

这里从Lucene简介开始.第一次使用Lucene已经是两年前入职的时候,写了个简单的爬虫,抓取999网的疾病信息并提供一个简单的搜索入口.这里主要弄懂以下几个问题:

1.信息检索
2.Lucene是什么;
3.Lucene建立索引的大致过程;
4.Lucene搜索的大致过程;

Lucene官网: http://lucene.apache.org/

在Lucene基础上衍生出很多搜索框架,下面是这些框架的对比:http://stackoverflow.com/questions/2271600/elasticsearch-sphinx-lucene-solr-xapian-which-fits-for-which-usage

1.信息检索

信息检索简单讲就是从一堆数据中找到你需要的数据,数据的来源可能是文本或者网络,甚至别人说的话或者声波等等.比如:

  • 从一个Excel表格中找到你的名字;
  • 从学生成绩标表中找到不及格的学生;
  • 从图书馆里面找Java编程相关的书籍;
  • 从网络搜索Lucene相关知识;
  • 老师点名时候喊到;

人类信息检索也是一个不断发展的过程,下面这个例子简单的诠释了信息检索的改善过程:

  1. 一个书生想从书屋(假设1000本书)里找一本书他能做的就是,从第一本书开始一本一本的往后找,直到找到他要的那本书.如果很不幸,书屋里面每这本书,那么他就必须翻遍所以的书,很可能他找一遍需要10个小时;
  2. 经历过几次这样痛苦的找书经历之后,书生开始想招了,将书分类(假设10个分类),文学类在第一个书架子,史学类再第二个书架子…从此以后,他找书比以前方便多了.找一本书最多只需要翻一个架子,时间缩短到1个小时;但是带来的成本是:必须将书正确的放在其正确的架子上;
  3. 每次翻遍一个架子,书生觉得还是比较麻烦,于是他给每本书加了一个编号,将书按照编号排列好,并将所以的书名和编号的对应关系记录到一个单独的册子上.下次他找书只需要在册子上找就可以了(只需要看册子上的1000个书名),找到书名对应的编号,然后就能快速的找到书,时间只需要10分钟.成本是书必须按照需要排列;
  4. 10分钟还是有点长,书生于是决定再改善,结合2和3的改进措施.书按照各种类型放在不同的架子,每个架子的书单独编号,比如文学1,文学2….册子上也按照书种类进行分开登记.这样找一本书只需要看一个分类下的书名(100个),只需要1分钟.

我们生活中的数据分为:结构化数据和非结构化数据.结构化数据指具有固定格式或有限长度的数据,如数据库或者Excel表等.非结构化数据指不定长或无固定格式的数据,如邮件,word文档等.

计算机的产生对信息检索产生了质的变化,帮我们做了很多简单却耗时的工作.在计算机检索的世界里面我们已知了很多技术:

1.对链表的搜索,我们采用从头到位逐项比较,O(N)的时间复杂度;
2.对于有序数组,我们可以采用二分搜索(其实就是二叉树,通常称之为二叉查找树),能够达到O(logN),底数是2;
3.多叉数的查找比二叉树更快,参考Tire树,B树等数据结构,O(logN),底数大于2;
4.Hash表的查找理论上是O(1)的时间复杂度;

除了顺序查找,其他几种检索都非常的快,但是这种快都是有维护成本的,比如二分搜索需要保证数据有序,因此新来的数据的插入成本会很高,包括删除数据的成本也会很高.但是其带来的检索效率的提升是非常大的.针对结构化数据,我们往往很简单的实现数据的快速搜索,比如数据库就是使用B树来达到快速搜索的目的.

但是现实中99%以上的原始数据都是混乱无须的非结构化数据.当数据量很大的时候,检索成为一个极其困难的问题(量变导致质变),即使对于计算很快的计算机而言.比如一个简单的字符串查找,假设在1页书的内容(约1000字)中查找一个单词可能需要1毫秒,那么在一本书的内容中(约50W词)中查找一个名字可能需要0.5秒,在1W本书(约50亿个单词)中查找这个单词需要5000秒,也就是接近1个半小时;假设每分钟要找一次呢?不敢想象.

在当今网络及其发达的今天,已经很多的公司的数据量超过了1W本书的信息量.这时候无序信息的全文检索显得极其重要.因此也催生了诸如Google,Yahoo和Baidu这些搜索巨头.

索引是全文搜索的基础,也是现代搜索引擎的核心,建立索引的过程就是把源数据处理成非常方便查询的索引文件的过程.你可以把索引想象成这样一种数据结构,他能够使你快速的随机访问存储在索引中的关键词,进而找到该关键词所关联的文档.

还是以书的例子来说,假设书前三页的内容:

1
2
3
4
5
6
7
8
9
10
11
//page1:
如何使用Lucene完善搜索

//page2
Lucene数据如何存储

//page3
Lucene如何实现搜索

//page4
作者:肖宝秋

我们首先使用分词软件见这四页的内容分词,得到以下结果:

1
2
3
4
5
6
7
8
9
//page1:
如何, 使用, Lucene, 完善, 搜索

//page2
Lucene, 数据, 如何, 存储

//page3
Lucene, 如何, 实现, 搜索
作者, 肖宝秋

建立词–>文档的映射关系:

1
2
3
4
5
6
7
8
9
10
如何 --> page1, page2, page3
使用 --> page1
Lucene --> page1, page2, page3
完善 --> page1
搜索 --> page1, page3
数据 --> page2
存储 --> page2
实现 --> page3
作者 --> page4
肖宝秋 --> page4

现在搜索"Lucene"的时候,我知道在page1,page2,page3中出现了.搜索"作者"的时候,我知道在page4出现了.

另外一个支撑现代搜索理论的既定现实是:词的数量是有限的,而且非常有限.比如常用的中文词就几万个.

2.Lucene是什么

简单讲,Lucene是一个高效的,基于Java的全文检索工具包,它不是一个完整的搜索应用程序,而是为你的应用程序提供索引和搜索功能.Lucene是Apache家族中的一个开源项目.也是目前最为流行的基于 Java 开源全文检索工具包.

Lucene 能够为文本类型的数据建立索引,所以你只要能把你要索引的数据格式转化的文本的,Lucene 就能对你的文档进行索引和搜索.比如你要对一些 HTML 文档,PDF 文档进行索引的话你只需要把 HTML 文档和 PDF 文档转化成文本格式的,然后将转化后的内容交给Lucene进行索引,然后把创建好的索引文件保存到磁盘或者内存中,最后根据用户输入的查询条件在索引文件上进行查询.不指定要索引的文档的格式也使Lucene能够几乎适用于所有的搜索应用程序.

下图展示搜索应用程序和Lucene之间的关系,也描述了Lucene的两个核心过程:建立索引和通过索引检索

2.1 Lucene优点

Lucene作为一个全文搜索引擎,其具有如下突出的优点:

  • 1.索引文件格式独立于应用平台.Lucene定义了一套以八字节为基础的索引文件格式,使得兼容系统和不同平台的应用能够共享建立的索引文件.
  • 2.在传统全文检索引擎的倒序索引的基础上实现了分块索引,能够针对新的文件建立小文件索引,提升索引速度.然后通过与原有的索引的合并,达到优化的目的.
  • 3.优秀的面向对象的系统架构,使得对于Lucene扩展的学习难度降低,方便加入新功能.
  • 4.设计了独立于语言和文件格式的文本分析接口,索引器通过接受token流完成索引文件的创立,用户扩展新的语言和文件格式,只需要实现文本分析的接口.
  • 5.已经默认实现了一套强大的查询引擎,用户无须自己编写代码即可使系统获得强大的查询能力,Lucene的查询实现中默认实现了布尔操作、模糊查询、分组查询.

参考: http://lucene.apache.org/core/index.html

2.2 倒排索引

现代搜索引擎基本都是基于倒排索引(反向索引).因为搜索问题本质就是求解"哪文档包含搜索词"这个问题.

简单讲一下什么是倒排索引,简单讲就是字符串到文件的映射关系.假设我的文档集合里面有100篇文档,为了方便表示,我们为文档编号从1到100,得到下面的结构:

左边保存的是一系列字符串,称为词典.每个字符串都指向包含此字符串的文档(Document)链表,此文档链表称为倒排表.

有了索引,便使保存的信息和要搜索的信息一致,可以大大加快搜索的速度.比如说,我们要寻找既包含字符串“lucene”又包含字符串“solr”的文档,我们只需要以下几步:

  1. 取出包含字符串lucene的文档链表.
  2. 取出包含字符串solr的文档链表.
  3. 通过合并链表,找出既包含lucene又包含solr的文件.

3.Lucene建立索引

Lucene的建立索引包括以下几个过程:

3.1.原始文档

一些要索引的原文档(Document).包括Html文档,PDF文档,MC Word文档等.而Lucene是只能处理文本文档.

庆幸的是现在很多工具帮我们处理这些问题.如Apache的Tika, 官网:http://tika.apache.org/

3.2.分词

确定输入的文本之后首先将文本传递给分词组件,分词组件(Tokenizer)会做以下几件事情(此过程称为Tokenize):

1. 将文档分成一个一个单独的单词;
2. 去除标点符号;
3. 去除停词(Stop word);

停词(Stop word)就是一种语言中最普通的一些单词,由于没有特别的意义,因而大多数情况下不能成为搜索的关键词,因而创建索引时,这种词会被去掉而减少索引的大小.英语中挺词(Stop word)如:the,a,this,is等.对于每一种语言的分词组件(Tokenizer),都有一个停词(stop word)集合.经过分词(Tokenizer)后得到的结果称为词元(Token).

3.3 语言处理

分词之后将词元传递给语言处理模块,语言处理组件(linguistic processor)主要是对得到的词元(Token)做一些同语言相关的处理.

比如对于英语,语言处理组件(Linguistic Processor)一般做以下几点:

1. 变为小写(Lowercase).
2. 将单词缩减为词根形式,如cars到car等.这种操作称为:stemming.
3. 将单词转变为词根形式,如“drove”到“drive”等.这种操作称为:lemmatization.

语言处理组件(linguistic processor)的结果称为词(Term).

3.4 索引

语言处理之后将词给索引模块,索引模块主要做以下几个事情:

1. 利用得到的词(Term)创建一个字典.
即Term1-->doc1, Term2-->doc1这种映射关系
2. 对字典按字母顺序进行排序.
3. 合并相同的词(Term)成为文档倒排链表.

倒排链表的格式如下:

1
Term1,Document Frequency  --> Doc1,Frequency1 ; Doc2,Frequency2

Document Frequency 即文档频次,表示总共有多少文件包含此词(Term),即链表中文档数目. Frequency 即词频率,表示此文件中包含了几个此词(Term).

下面是一个建立索引的例子,输入文本如下:

1
2
文件一:Students should be allowed to go out with their friends, but not allowed to drink beer.
文件二:My friend Jerry went to school to see his students but found them drunk which is not allowed.

经过分词(Tokenizer)后得到的结果称为词元(Token):

1
Students,allowed,go,their,friends,allowed,drink,beer,My,friend,Jerry,went,school,see,his,students,found,them,drunk,allowed

经过语言处理,得到的词(Term)如下:

1
student,allow,go,their,friend,allow,drink,beer,my,friend,jerry,go,school,see,his,student,find,them,drink,allow

最后得到的倒排索引表如下:

所以对词allow来讲,总共有两篇文档包含此词(Term),从而词(Term)后面的文档链表总共有两项,第一项表示包含allow的第一篇文档,即1号文档,此文档中,allow出现了2次,第二项表示包含allow的第二个文档,是2号文档,此文档中,allow出现了1次.

4.Lucene搜索

有了倒排索引,我们就可以做搜索了,但是事实上Lucene的搜索过程也不简单.

简单来讲,搜索解决的问题是:找到和搜索词相关性最好的文档.细分的这个问题:

1.找到相关文档;
2.评价搜索词和文档的相关性;

Lucene的搜索包括以下几个过程.

3.1.用户输入

查询语句同我们普通的语言一样,也是有一定语法的.查询语句的语法根据全文检索系统的实现而不同.最基本的有比如:AND, OR, NOT等.举个例子,用户输入语句:lucene AND learned NOT hadoop.说明用户想找一个包含lucene和learned然而不包括hadoop的文档.

目前看来,Google和Baidu都不支出这种语法:

3.2.词法分析,语法分析,语言处理

由于查询语句有语法,因而也要进行语法分析,语法分析及语言处理.

  • 词法分析主要用来切词,识别单词和关键字.通常建立索引的切词组件和对搜索词的切词组件一致.

  • 语法分析主要是根据查询语句的语法规则来形成一棵语法树.比如例子:lucene AND learned NOT hadoop形成的语法树如下:

  • 语言处理同索引过程中的语言处理几乎相同.如learned变成learn等.经过第三步,我们得到一棵经过语言处理的语法树.

3.3 搜索索引

此步骤有分几小步:

  • 在反向索引表中,分别找出包含lucene,learn,hadoop的文档链表.
  • 对包含lucene,learn的链表进行合并操作,得到既包含lucene又包含learn的文档链表.
  • 将此链表与hadoop的文档链表进行差操作,去除包含hadoop的文档,从而得到既包含lucene又包含learn而且不包含hadoop的文档链表.此文档链表就是我们要找的文档.

3.4 结果文档排序

虽然在上一步,我们得到了想要的文档,然而对于查询结果应该按照与查询语句的相关性进行排序,越相关者越靠前.

通常会把查询语句看作一片短小的文档,对文档与文档之间的相关性(relevance)进行打分(scoring),分数高的相关性好,就应该排在前面.

对于文档之间的关系,不同的Term重要性不同,比如对于本篇文档,search, Lucene, full-text就相对重要一些,this, a , what可能相对不重要一些.所以如果两篇文档都包含search, Lucene,fulltext,这两篇文档的相关性好一些,然而就算一篇文档包含this, a, what,另一篇文档不包含this, a, what,也不能影响两篇文档的相关性.

找出词(Term)对文档的重要性的过程称为计算词的权重(Term weight)的过程.计算词的权重(term weight)有两个参数,第一个是词(Term),第二个是文档(Document).词的权重(Term weight)表示此词(Term)在此文档中的重要程度,越重要的词(Term)有越大的权重(Term weight),因而在计算文档之间的相关性中将发挥更大的作用.

下面分析这两个过程:

  • 计算权重(Term weight).

影响一个词(Term)在一篇文档中的重要性主要有两个因素:

1.Term Frequency (tf):即此Term在此文档中出现了多少次. tf越大说明越重要.
2.Document Frequency (df):即有多少文档包含次Term. df越大说明越不重要.

很容易理解,词(Term)在文档中出现的次数越多,说明此词(Term)对该文档越重要,如“搜索”这个词,在本文档中出现的次数很多,说明本文档主要就是讲这方面的事的.然而在一篇英语文档中,this出现的次数更多,就说明越重要吗?不是的,这是由第二个因素进行调整,第二个因素说明,有越多的文档包含此词(Term), 说明此词(Term)太普通,不足以区分这些文档,因而重要性越低.

简单公式如下:

  • 根据Term之间的关系得到文档相关性.

我们把文档看作一系列词(Term),每一个词(Term)都有一个权重(Term weight),不同的词(Term)根据自己在文档中的权重来影响文档相关性的打分计算.

于是我们把所有此文档中词(term)的权重(term weight) 看作一个向量.

1
2
Document = {term1, term2, …… ,term N}
Document Vector = {weight1, weight2, …… ,weight N}

同样我们把查询语句看作一个简单的文档,也用向量来表示.

1
2
Query = {term1, term 2, …… , term N}
Query Vector = {weight1, weight2, …… , weight N}

我们把所有搜索出的文档向量及查询向量放到一个N维空间中,每个词(term)是一维:

我们认为两个向量之间的夹角越小,相关性越大.所以我们计算夹角的余弦值作为相关性的打分,夹角越小,余弦值越大,打分越高,相关性越大.

需要注意的是,查询语句一般是很短的,包含的词(Term)是很少的,因而查询向量的维数很小,而文档很长,包含词(Term)很多,文档向量维数很大, 但是需要放到相同的向量空间,因此要保证二者维数是相同的.处理方式很简单,维数不同时,取二者的并集,如果不含某个词(Term)时,则权重(Term Weight)为0.

相关性打分公式如下:

举个例子,查询语句有11个Term,共有三篇文档搜索出来.其中各自的权重(Term weight),如下:

于是计算,三篇文档同查询语句的相关性打分分别为:

于是文档二相关性最高,先返回,其次是文档一,最后是文档三.到此为止,我们可以找到我们最想要的文档了.

Mysql Join

join 用于多表中字段之间的关联,语法如下:

1
... FROM table1 INNER|LEFT|RIGHT JOIN table2 ON conditiona

JOIN实际上是两个表的的乘积(即笛卡尔积).假设集合A={a,b},集合B={0,1,2},则两个集合的笛卡尔积为{(a,0),(a,1),(a,2),(b,0),(b,1), (b,2)}.

JOIN按照功能大致分为如下三类:

INNER JOIN: 取得两个表中存在连接匹配关系的记录;
LEFT JOIN: 取得左表完全记录,即使右表并无对应匹配记录,如果没有匹配,右侧将包含null;
RIGHT JOIN: 与 LEFT JOIN 相反,取得右表完全记录,即使左表并无匹配对应记录;

. 1.显示join和隐式join

另外,写join语句有所谓的显示join和隐式join的写法:

1
2
3
4
5
6
7
8
9
-- 显示join
select * from
table1 inner join table2
on table1.name = table2.name;

-- 隐式join
select table1.*, table2.*
from table1, table2
where table1.name = table2.name;

这两种写法性能上基本没有差异,参考stackoverflow: http://stackoverflow.com/questions/44917/explicit-vs-implicit-sql-joins

. 2.ON条件和WHERE条件

在执行顺序上需要注意的是on条件和where条件执行顺序: 首先使用on条件产生初始笛卡尔积集合,再在这个集合上使用where条件筛选.所以join的时候应该首先好的on条件保证笛卡尔积集合尽可能小,从而减少Where的执行.

比如下面两种写法,方案2写法保证产生的笛卡尔积集合很小,因而从执行性能来看第二个显然更加省时。

1
2
3
4
5
6
7
8
9
10
11
12
-- 方案1
select * from A
inner join B on B.name = A.name
left join C on C.name = B.name
left join D on D.id = C.id
where C.status>1 and D.status=1;

-- 方案2
select * from A
inner join B on B.name = A.name
left join C on C.name = B.name and C.status>1
left join D on D.id = C.id and D.status=1

. 3.STRAIGHT_JOIN和NATURAL JOIN

. 3.1 STRAIGHT_JOIN

再Join的时候,MySQL优化器要确定以谁为驱动表,也就是说以哪个表为基准,在处理此类问题时,MySQL优化器采用了简单粗暴的解决方法:哪个表的结果集小,就以哪个表为驱动表,当然MySQL优化器实际的处理方式会复杂许多,具体可以参考:http://www.orczhou.com/index.php/2013/04/how-mysql-choose-index-in-a-join/

说明:在EXPLAIN结果中,第一行出现的表就是驱动表。

但是这个由的时候比较愚蠢,比如我们order by的字段在大结果集的表上,也就是说排序字段不在驱动表里,于是乎不可避免的出现了Using filesort和Using temporary.

上面这种场景,我们就可以通过使用STRAIGHT_JOIN显示的指定驱动表

参考: http://huoding.com/2013/06/04/261

. 3.2 NATURAL

MySQL将表中具有相同名称的字段自动进行记录匹配,而这些同名字段类型可以不同。因此,NATURAL JOIN 不用指定匹配条件。

同样包含NATURAL LEFT JOIN和NATURAL RIGHT JOIN.

1
SELECT article.aid,article.title,user.username FROM article NATURAL JOIN user