## 引子 如何能实现全文检索的功能呢？ 可以使用SQL的like 数据量小的时候Like还凑合，但是数据量大了，效率就非常低了 那么可以使用inverted index ## Inverted Index Inverted Index被翻译成倒排索引 比如有两篇文档： * 文档1：A computer is a device that can execute operations * 文档2：Early computers are big devices 把这两篇文章中的单词都抽取出来，并且记录下这个单词出现在哪个文档中。  通过这个 “倒排索引”，只要给出一个单词，就可以迅速地定位到它在哪个文档中。 用来做全文搜素非常合适。 这个倒排索引有些粗糙，可以精化一下 1. 对于 a, is , to ,that ,can ,the,are 这些词对搜索来说没什么意义，用户几乎不会用他们搜索，可以过滤掉。 2. 用户搜索的时候虽然输入了 computer，但是也希望搜出 computers 出来，所以需要把复数单词，过去式单词等做还原。 3. 用户虽然输入了 device , 但是也希望搜索出 Device 出来，所以需要把大写都改成小写。 经过这番转换，文档 1 和文档 2 的关键字变成了这样： 文档 1：[computer] [device] [execute] [operation] 文档 2：[early] [computer] [big] [device]  为了更好的统计和高亮显示搜索结果，还可以记录关键词在文章中出现的次数和位置（例如：是第几个单词）  ## 架构 只要把那些书籍的标题，介绍，作者等信息给提取出来，形成 inverted index，不就可以做关键字检索了吗？ 这个需求应该是个通用的需求，不仅是图书馆有，很多互联网应用，例如网上商城也需要， 我完全可以设计一个类库出来  不管你是什么类型的文档，HTML， PDF， Word，甚至是数据库的数据，只要能从中抽取出文本，就可以当作我的数据源，对文本做了分析以后，就可以存入索引库。 用户可以发出各种查询，不仅仅是单个关键字，还支持关键字的组合： keyword1 AND keyword2 等，对索引库进行搜索以后，把结果返回给用户。 ## 抽象 接下来就是API设计了。 软件设计就是一个不断抽象的过程。既然有 HTML,PDF, Word 文档， 很自然，你可以做一个 Document 的抽象 但是如果数据源是数据库，怎么变成 Document，比如一行数据可以映射到一个Document，当然，这个转化必须得有程序员来完成。程序员决定什么东西是 Document Document有什么东西？ Document 可以有很多属性，每个属性都有名称和值， 我可以把属性叫做 Field。 比如一个 HTML 文档，可能有 path, title，content 等多个 Field，其中 path 可以唯一地标志这个文档, title 和 content 需要做进行分词，形成倒排索引，让用户搜索  用户创建了 Document 和 Field 以后，就可以进行分析了，原始的内容划分成一个个 Term，这样，我可以定义一个 Analyzer 的抽象类，让别的程序可以扩展它 分析的结果可以加入索引库，这个操作可以让一个单独的类，比如 IndexWriter 类来完成。 可是 IndexWriter 如何知道索引应该存在什么地方？ 内存？ 文件系统 那就再来一个抽象的概念：Directory，表示索引文件的存储  对于对于用户搜索来说，肯定得有个叫做 Query 的东西，用来表达用户的搜索要求。当然，这个 Query 也应该允许扩展。  但是这些类使用起来还是比较麻烦， 最好是支持用户输入字符串来表达搜索的意图：(computer or phone) and price 所以必须得有个解析器来完成从字符串到 Query 的转化，然后我们让 IndexSearcher 来接收 Query，就可以实现搜索的功能了  有个叫做 Lucene 的开源系统，和我们的设计很像啊，功能更加强大 ## 三年之后 人们发现Lucene用起来太低级了，比如想搜索一下我的商品描述，现在还得理解什么 “Directory”,"Analyzer","Query"，实在是太复杂了！ 还有我们的数据越来越多，索引也越来占的空间也越来越大，怎么才能实现分布式的存储啊 是时候对 Lucene 做一层封装，提供一个简单的 API 了...... ## Lucene的问题 * Lucene做搜索很强大，但是**API用起来太低级**，想搜索一下我的产品描述，现在还得理解什么 “Directory”,"Analyzer","IndexWriter" * 互联网的数据是海量的，仅仅是单机存储索引是远远不够的。 俗话说：软件开发中遇到的所有问题，都可以通过增加一层抽象而得以解决 ## Java API -> Web API Web 开发面对的都是领域模型，比如 User,Product, Blog，Account 之类。用户想做的无非就是搜索产品的描述， 搜索 Blog 的标题，内容等等 如果能围绕领域模型的概念进行搜索的各种操作就好了。 Web 时代中，程序员都喜欢采用 RESTful 的方式来描述一个 Web 资源， 对于搜索而言，完全可以借鉴一下 /coolspace/blog/1001 : 表示一个编号为 1001 的博客 /coolspace/user/u3876：表示一个 ID 为 u3876 的用户 * /coolspace 表示一个 “索引库” * /blog ,/user 表示 “索引的类型”（可以理解为编程中的领域模型）。 1001， u3876 表示数据的 ID，格式是 /<index>/<type>/<id> 如果和关系数据库做个类比的话： > 索引库 <---> 数据库 > 索引的类型 <---> 数据库的表 用户看到的就是领域模型， 当用户想去操作时候，用 HTTP 的 GET, PUT 等操作就好了，交互的数据可以使用 JSON 这个简单的格式。 ## 基本操作 * 把文档加入索引库 把一个 blog 的 “文档” 加入索引库，这个文档的数据是 JSON 格式，其中的每个字段将来都可以被搜索： ~~~ PUT /coolspace/blog/1001 { "title" : "xxxxxxx", "content" : "xxxxxxxxxxxx", "author" : "xxxxx", "create_date": "xxxxxx" ... } ~~~ * 把一个blog文档删除 ~~~ DELETE /coolspace/blog/1001 ~~~ * 用户搜索 用户想搜索的时候也很简单，发起一个这样的请求就行： ~~~ GET /coolspace/blog/_search ~~~ 但是如何表达查询的具体需求呢，这时候必须得定义一个规范了，例如：想查询一个内容字段（content) 包含 “java" 的 blog。 ~~~ GET /coolspace/blog/_search { "query" : { "match" : { "content" : "java" } } } ~~~ 也就是query可以增加更加复杂的条件，表示用户的查询需求，因为是JSON格式的，可以非常的灵活，返回值也是JSON  通过这样一个抽象层， Lucene 那些复杂的 API 全部被隐藏了 ## 分布式 如果索引太大，我们把它切割一下，分成一片一片的，存储到各个机器上不就得了  那么怎么要去保存索引和搜索索引呢？ 首先要保存每个分片(shard)和机器之间的对应关系， ~~~ 分片 1 ：node1 分片 2 ：node2 分片 3 ：node3 ~~~ 可以用余数算法来确定一个‘文档’到底保存在哪个 shard 中。 **shard 编号 = hash(文档的 ID) % shard 总数** 这样对于任意一个文档，对它的 ID 做 hash 计算，然后对总分片数量求余， 就可以得到 shard 的编号，然后就可以找到对应的机器了 但是如果用户想增加shard数的时候余数算法就不能用了。 比如原来 shard 总数是 3， hash 值是 100， shard 编号 = 100 % 3 = 1 假设用户又增加了两台机器，shard 总数变成了 5， 此时 shard 编号 = 100 % 5 = 0 ， 如果去 0 号机器上去找索引，肯定是找不到的。 要不采用分布式一致性算法， 嗯，它会减少出错的情况，还是无法避免，这该怎办 我们可以立下一个规矩： 用户在创建索引库的时候，必须要指定 shard 数量，并且一旦指定，就不能更改了 ~~~ PUT /coolspace { "settings" : { "number_of_shards" : 3 } } ~~~ 虽然对用户来说有点不爽， 但余数算法的高效和简单确实太吸引人了 索引数据分布了，如果某个节点坏掉了，数据就会丢失，我们得做个备份才行 可以用新的node来做replica，也可以为了节省空间，复用现有的node来做replica。 之前的分片叫做主分片，primary shard  ~~~ PUT /coolspace/_settings { "number_of_replicas" : 2 } ~~~ 虽然主分片的数目在创建 “索引库” 的时候已经确定，但是副本的数目是可以任意增减的，这依赖于硬件的情况：性能和数量。 “现在每个主分片都有两个副本， 如果某个节点挂了也不怕，比如节点 1 挂了，我们可以位于节点 3 上的副本 0 提升为 主分片 0， 只不过每个主分片的副本数不够两个了  等到节点1再次启动的时候，还可以恢复副本 ## 集群 现在我们建立了一个集群， 这个集群中可以包含若干 node ， 有数据的备份，能实现高可用性。 那么另一个问题出现了对于客户端来说，通过哪个 node 来读写‘文档’呢 可以让请求发送到集群的任意一个节点，每个节点都具备处理任何请求的能力 具体为： （1）假设用户把请求发给了节点 1 （2）系统通过余数算法得知这个'文档'应该属于主分片 2，于是请求被转发到保存该主分片的节点 3 （3）系统把文档保存在节点 3 的主分片 2 中，然后将请求转发至其他两个保存副本的节点。副本保存成功以后，节点 3 会得到通知，然后通知节点 1， 节点 1 再通知用户。  如果是做查询呢？ 比如说用户查询一个文档： GET /coolspace/blog/1001 查询的请求也可以分发到任意一个节点，然后该节点可以找到主分片或者任意一个副本，返回即可 （1） 请求被发给了节点 1 （2）节点 1 计算出该数据属于主分片 2，这时候，有三个选择，分别是位于节点 1 的副本 2， 节点 2 的副本 2，节点 3 的主分片 2， 假设节点 1 为了负载均衡，采用轮询的方式，选中了节点 2，把请求转发。 （3） 节点 2 把数据返回给节点 1， 节点 1 最后返回给客户端。  这种方式比较灵活，但是要求各个节点互通有无。 对于一个集群来说，还得有一个主节点（master node），这个主节点在处理数据请求上和其他节点是平等的，但是它还有更重要的工作，需要维护整个集群的状态，增加移除节点，创建 / 删除索引库，维护主分片和集群的关系等等 如果这个主节点挂了，就只好从剩下的节点中重新选举了 就涉及到分布式系统的各种问题了，什么一致性，脑裂 所以我们可以只选取一个Master， 比如一个Bully 的算法， 改进一下应该就可以用了