理解ES搜索引擎的原理

倒排索引

普通索引

拿唐诗“静夜思”举例： 窗前明月光，疑似地上霜。 举头望明月，低头思故乡。

普通的索引，以诗名作为key，诗的内容作为value。这样去查找的。

输入“静夜思”，直接找到“诗的内容”。

但是现在让你说出带“前”字的诗句，由于没有索引，只能遍历所有诗词了，短时间内很难得到结果。

反向索引（倒排索引）

倒排索引，以“前”作为索引，诗句内容作为value。再搜索带“前”字的诗句，可以很快找到结果。 这就是倒排索引，以诗句内容中的一些关键字作为索引，来找到诗句。

索引量爆炸

“床”，“明”，“月” 是不是都可以建立索引，那一句诗就是 10 个索引，包砸性增长 内容越长，索引可能越多，索引的数据量也越大。

换个思路：“前”索引key，value改存诗名，不再存诗内容，数据量确实减少一些了。

再比如“望庐山瀑布”诗句中，也有“前”字，那“前”可以指向“静夜思”+“望庐山瀑布”

搜索引擎原理

百度输入“带前的诗句”，就可以出来结果了，响应很快。

但是百度、谷歌流程复杂一点，包括网页爬取，停顿词过滤等等。

停顿词就是没有意义的词，这些词没有必要建立索引，比如“的”，“而”等等，这些词本身没有意义。

分词，搜索引擎是对内容分词后，再根据关键词建立倒排索引。

搜索引擎三步：网页爬取，进行内容、建立反向索引。

Elasticsearch 简介

业界有一个叫 lucene 的库，用它可以方便的建立倒排索引。 但是需要懂搜素引擎原理的，才能用好 lecene，所以又有人基于该库进行封装。

Elasticsearch 将对搜索引擎的操作都封装成了 restful 的 api，通过 http 请求就能对其进行操作。 同时它还考虑了海量数据，实现了分布式，是一个可以存储海量数据的分布式搜索引擎。 与Hadoop分布式文件系统(HDFS)不一样。

Elasticsearch 基本概念

基本概念

  • 索引，这里索引不是“倒排索引”，而是存放数据的地方，可以理解为mysql中的一个数据库；
  • 类型，用来定义数据结构的，可以认为mysql中的一张表；
  • 文档，就是最终的数据，一个文档相当于一条记录。

还是以前面提到的唐诗为例：一首诗，有诗题、作者、朝代、字数，诗内容等字段， 那可以先建一个名叫 poems 的索引。

类型 poem
  • properties
    • title
      • “type”:“keyword”
    • author
      • “type”:“keyword”
    • words
      • “type”:“integer”
    • content
      • “type”:“text”

注意：keyword 是不分词的，直接建立反向索引； text是先分词，后建立反向索引。

文档 以 JSON串 形式描述一行数据
  • “title”:“静夜思”
  • “poems”:“李白”
  • “words”:“20”
  • “content”:“窗前明月光，疑似地上霜。举头望明月，低头思故乡。”
用户检索过程

先分词，再找到每个item对应的list，最后进行集合求交集的过程。

有序集合求交集方法
  • 二重for循环，时间复杂度 O(n*n)
  • 拉链法，时间复杂度 O(n)
  • 水平分桶，多线程并行
  • bitmap，大大提高运算并行度，时间复杂度 O(n)
  • 跳表，时间复杂度为 O(log(n))

Elasticsearch 分布式原理

在 Elasticsearch 中，节点是对等的，节点间会通过自己的一些规则选举集群的 master，master会负责集群状态信息的改变，并同步给其他节点。 也会对数据进行切分，同时每一个分片会保存多个副本，其原理和 HDFS 是一样的，都是为了保证分布式环境下的高可用。

注意：只有建立索引和类型需要经过master，数据的写入有一个简单的 Routing 规则，可以 Route 到集群中的任意节点，所以数据写入压力是分散在整个集群的。

选举是ZenDiscovery模块负责，要设置过半机制，防止脑裂。

保证数据一致性

需要满足的特性

  • 持久性：数据写入成功后，数据持久化存在，不会发生回滚或丢失。
  • 一致性：数据写入成功后，查询时要保证读取到最新版本的数据，不能读取到旧数据。
  • 原子性：一个写入或更新操作，要么成功，要么失败，不允许出现中间状态。
  • 隔离性：多个写入并发操作而互不影响。

集群数据同步机制

数据并发冲突时乐观锁和版本号控制的。

ES 采用一组多副复制方式，没有采用节点级别的主从复制，而是基于分片。 Index 又多个 Shard 组成，每个 Shard 又一个主节点和多个副本节点。数据写入时，首先根据 路由规则对路由参数进行 Hash 确定要写入的 Shard，最后从集群的 Meta 中找出该 Shard 的 Primary 节点写入数据，Primary Shard 成功写入数据后，Primary Shard 成功写入数据后，将请求同时发给多个 Replacation Shard， 请求再全部的 副本分片 上执行成功并响应 Primary Shard 后，Primary Shard 返回结果给客户端。

该模式，Primary要等所有 Replication 返回才能返回给客户端，那么延迟就会收到最慢的 Replication 影响，写入操作延迟等于Primary Write 延迟+ Max(Replication Write) 延迟。副本的存在，降低了写入效率，但可以避免单机或磁盘故障导致数据丢失。

Replication写入失败，Primary会执行一些重试，尽可能保障Replication中写入成功，如果一个Replication最终写入失败，Primary会将Replication节点报告给Master, 然后Master更新Meta中Index的InSyncAllocations配置，将Replication从中移除，移除后它就不再承担读请求。 在Meta更新到各个Node之前，用户可能还会读到Replication的数据，但是更新Meta后就不会了。

通过设置TransLog每隔一端事件Flush一次，一般每5秒或1分钟Flush一次，间隔时间越长，可靠性越低。

一致性保障

  • 持久性：通过Replication和TransLog两种机制来共同保障。
  • 一致性：数据写入成功后，需完成Refresh操作之后才可读，由于无法保证Primary和Replica可同时refresh，所以会出现查询不稳定的情况，这里只能实现最终一致性。
  • 原子性：Add和Delete直接调用Lucene的接口，进行原子操作。 update操作通过Delete-Then-Add完成，在Delete操作之前会加Refresh Lock，禁止Refresh操作， 等Add操作完成后释放Refresh Lock后才能被Refresh，这样就保证了Delete-Then-Add的原子性。
  • 隔离性：采用Version和局部锁来保证更新的是特定版本的数据。

要保证数据写入到ElasticSerach是安全的，高可靠的，需要如下的配置：（可靠性和可用性之间进行折中）

  • 设置wait_for_active_shards参数大于等于2。
  • 设置TransLog的Flush策略为每个请求都要Flush。

实时搜索引擎系统架构要点

大数据量、高并发量情况下的搜索引擎为了保证实时性，架构设计上的两个要点：

  • 索引分级
  • dump & merge

在数据量非常大的情况下，为了保证倒排索引的高效检索效率，任何对数据的更新，并不会实时修改索引。 否则一旦产生碎片，会大大降低检索效率。

索引分级

  • 全量库 300亿数据
  • 日增量库 1000万数据
  • 小时增量库 50万数据 当有修改请求发生时，指挥操作最低级别的索引，如 小时库。 当有查询请求发生时，会同时查询各个级别的索引，将结果合并，得到最新数据。
  1. 全量库是紧密存储的索引，无碎片，速度快；
  2. 天库是紧密存储，速度快；
  3. 小时库数据量小，速度也快。

索引到处与合并

小时库数据如何反应到天库中，天库中的数据何时反映到全量库中呢？

  • dumper：将在线的数据导出。
  • merger：将离线的数据合并到高一级别的索引中去。 小时库，一小时一次，合并到天库中去； 天库，一天一次，合并到全量库中去； 这样可保证小时库和天库的数据量都不会特别大； 如果数据量和并发量更大，还能增加星期库，月库来缓冲。

在业务、流量、并发量逐步递增的各个阶段，应该如何实现检索需求？

  • 原始阶段 like 模糊匹配
  • 初级阶段：全文索引
  • 中级阶段：开源外置索引 ES
  • 高级阶段：自研搜索引擎

日志分析系统 ELK

系统运行过程中出现了异常，在日志中就能及时反馈，日志进入 ELK 系统中，通过 Kibana 就能看到日志情况。 如果再接入一些实时计算模块，还能做实时报警功能。