搜索客，搜索人自己的社区

关于ElasticSearch查询的一个问题，以下逻辑查询如何用bool query或是其他query表示

贡献

Elasticsearch • Xargin 回复了问题 • 4 人关注 • 2 个回复 • 7099 次浏览 • 2017-05-17 21:28 • 来自相关话题

Elasticsearch有没有 .net core 的客户端？

Elasticsearch • Eviltuzki 发起了问题 • 1 人关注 • 0 个回复 • 4721 次浏览 • 2017-05-12 14:22 • 来自相关话题

基于ElasticSearch的亿级实时日志系统实践

资料分享 • mindhacking 发表了文章 • 0 个评论 • 8434 次浏览 • 2017-05-12 11:36 • 来自相关话题

看得出来是踩了不少坑总结出来的，推荐下：基于ElasticSearch的亿级实时日志系统实践

es 是否支持自定义的算分插件？

贡献

Elasticsearch • kennywu76 回复了问题 • 3 人关注 • 1 个回复 • 4360 次浏览 • 2017-05-13 08:53 • 来自相关话题

拔了一条内存，es启不来

贡献

Elasticsearch • wyntergreg 回复了问题 • 2 人关注 • 2 个回复 • 3460 次浏览 • 2017-05-12 12:15 • 来自相关话题

elasticsearch如何使用REST request URI 多条件方式获取数据？

贡献

Elasticsearch • Jea 回复了问题 • 2 人关注 • 1 个回复 • 4927 次浏览 • 2017-05-12 13:59 • 来自相关话题

[原创] ElasticSearch集群故障案例分析: 警惕通配符查询

Elasticsearch • kennywu76 发表了文章 • 12 个评论 • 24785 次浏览 • 2017-05-11 19:23 • 来自相关话题

[携程旅行网：吴晓刚]
许多有RDBMS/SQL背景的开发者，在初次踏入ElasticSearch世界的时候，很容易就想到使用(Wildcard Query)来实现模糊查询（比如用户输入补全)，因为这是和SQL里like操作最相似的查询方式，用起来感觉非常舒适。然而近期我们线上一个搜索集群的故障揭示了，滥用wildcard query可能带来灾难性的后果。

故障经过
线上有一个10来台机器组成的集群，用于某个产品线的产品搜索。数据量并不大，实时更新量也不高，并发搜索量在几百次/s。通常业务高峰期cpu利用率不超过10%，系统负载看起来很低。但最近这个集群不定期（1天或者隔几天)会出现CPU冲高到100%的问题，持续时间从1分钟到几分钟不等。最严重的一次持续了20来分钟，导致大量的用户搜索请无求响应，从而造成生产事故。

问题排查
细节太多，此处略过，直接给出CPU无故飙高的原因: 研发在搜索实现上，根据用户输入的关键词，在首尾加上通配符，使用wildcard query来实现模糊搜索，例如使用"*迪士尼*"来搜索含有“迪士尼”关键字的产品。然而用户输入的字符串长度没有做限制，导致首尾通配符中间可能是很长的一个字符串。后果就是对应的wildcard Query执行非常慢，非常消耗CPU。

复现方法
1. 创建一个只有一条文档的索引

POST test_index/type1/?refresh=true

{

  "foo": "bar"

}

2. 使用wildcard query执行一个首尾带有通配符*的长字符串查询

POST /test_index/_search

{

  "query": {

    "wildcard": {

      "foo": {

        "value": "*在迪士尼乐园，点亮心中奇梦。它是一个充满创造力、冒险精神与无穷精彩的快地。您可在此游览全球最大的迪士尼城堡——奇幻童话城堡，探索别具一格又令人难忘的六大主题园区——米奇大街、奇想花园、梦幻世界、探险岛、宝藏湾和明日世界，和米奇朋友在一起，感觉欢乐时光开业于2016年上海国际旅游度假区秀沿路亚朵酒店位于上海市浦东新区沪南公路（沪南公路与秀沿路交汇处），临近周浦万达广场、地铁11号线秀沿路站，距离上海南站、人民广场约20公里，距离迪线距*"

      }

    }

  }

}

3. 查看结果

{

  "took": 3445,

  "timed_out": false,

  "_shards": {

    "total": 5,

    "successful": 5,

    "failed": 0

  },

  "hits": {

    "total": 0,

    "max_score": null,

    "hits": 

  }

}

即使no hits，耗时却是惊人的3.4秒 (测试机是macbook pro, i7 CPU)，并且执行过程中，CPU有一个很高的尖峰。

线上的查询比我这个范例要复杂得多，会同时查几个字段，实际测试下来，一个查询可能会执行十几秒钟。在有比较多长字符串查询的时候，集群可能就DOS了。

探查深层次根源
为什么对只有一条数据的索引做这个查询开销这么高？直觉上应该是瞬间返回结果才对!

回答这个问题前，可以再做个测试，如果继续加大查询字符串的长度，到了一定长度后，ES直接抛异常了，服务器ES里异常给出的cause如下:

Caused by: org.apache.lucene.util.automaton.TooComplexToDeterminizeException: Determinizing automaton with 22082 states and 34182 transitions would result in more than 10000 states. at org.apache.lucene.util.automaton.Operations.determinize(Operations.java:741) ~[lucene-core-6.4.1.jar:6.4.1

该异常来自org.apache.lucene.util.automaton这个包，异常原因的字面含义是说“自动机过于复杂而无法确定状态：由于状态和转换太多，确定一个自动机需要生成的状态超过10000个上限"

网上查找了大量资料后，终于搞清楚了问题的来龙去脉。为了加速通配符和正则表达式的匹配速度，Lucene4.0开始会将输入的字符串模式构建成一个DFA (Deterministic Finite Automaton)，带有通配符的pattern构造出来的DFA可能会很复杂，开销很大。这个链接的博客using-dfa-for-wildcard-matching-problem比较形象的介绍了如何为一个带有通配符的pattern构建DFA。借用博客里的范例，a*bc构造出来的DFA如下图:

Lucene构造DFA的实现
看了一下Lucene的里相关的代码，构建过程大致如下:
1. org.apache.lucene.search.WildcardQuery里的toAutomaton方法，遍历输入的通配符pattern，将每个字符变成一个自动机(automaton)，然后将每个字符的自动机链接起来生成一个新的自动机

public static Automaton toAutomaton(Term wildcardquery) {

    List<Automaton> automata = new ArrayList<>();

    

    String wildcardText = wildcardquery.text();

    

    for (int i = 0; i < wildcardText.length();) {

      final int c = wildcardText.codePointAt(i);

      int length = Character.charCount(c);

      switch(c) {

        case WILDCARD_STRING: 

          automata.add(Automata.makeAnyString());

          break;

        case WILDCARD_CHAR:

          automata.add(Automata.makeAnyChar());

          break;

        case WILDCARD_ESCAPE:

          // add the next codepoint instead, if it exists

          if (i + length < wildcardText.length()) {

            final int nextChar = wildcardText.codePointAt(i + length);

            length += Character.charCount(nextChar);

            automata.add(Automata.makeChar(nextChar));

            break;

          } // else fallthru, lenient parsing with a trailing \

        default:

          automata.add(Automata.makeChar(c));

      }

      i += length;

    }

    

    return Operations.concatenate(automata);

  }

2. 此时生成的状态机是不确定状态机，也就是Non-deterministic Finite Automaton（NFA)。
3. org.apache.lucene.util.automaton.Operations类里的determinize方法则会将NFA转换为DFA

/**

   * Determinizes the given automaton.

   * <p>

   * Worst case complexity: exponential in number of states.

   * @param maxDeterminizedStates Maximum number of states created when

   *   determinizing.  Higher numbers allow this operation to consume more

   *   memory but allow more complex automatons.  Use

   *   DEFAULT_MAX_DETERMINIZED_STATES as a decent default if you don't know

   *   how many to allow.

   * @throws TooComplexToDeterminizeException if determinizing a creates an

   *   automaton with more than maxDeterminizedStates

   */

  public static Automaton determinize(Automaton a, int maxDeterminizedStates) {

代码注释里说这个过程的时间复杂度最差情况下是状态数量的指数级别！为防止产生的状态过多，消耗过多的内存和CPU，类里面对最大状态数量做了限制

  /**

   * Default maximum number of states that {@link Operations#determinize} should create.

   */

  public static final int DEFAULT_MAX_DETERMINIZED_STATES = 10000;

在有首尾通配符，并且字符串很长的情况下，这个determinize过程会产生大量的state，甚至会超过上限。

至于NFA和DFA的区别是什么？如何相互转换？网上有很多数学层面的资料和论文，限于鄙人算法方面有限的知识，无精力去深入探究。但是一个粗浅的理解是: NFA在输入一个条件的情况下，可以从一个状态转移到多种状态，而DFA只会有一个确定的状态可以转移，因此DFA在字符串匹配时速度更快。 DFA虽然搜索的时候快，但是构造方面的时间复杂度可能比较高，特别是带有首部通配符+长字符串的时候。

回想Elasticsearch官方文档里对于wildcard query有特别说明，要避免使用通配符开头的term。

" Note that this query can be slow, as it needs to iterate over many terms. In order to prevent extremely slow wildcard queries, a wildcard term should not start with one of the wildcards * or ?."

结合对上面wildcard query底层实现的探究，也就不难理解这句话的含义了！

总结： wildcard query应杜绝使用通配符打头，实在不得已要这么做，就一定需要限制用户输入的字符串长度。最好换一种实现方式，通过在index time做文章，选用合适的分词器，比如nGram tokenizer预处理数据，然后使用更廉价的term query来实现同等的模糊搜索功能。对于部分输入即提示的应用场景，可以考虑优先使用completion suggester, phrase/term suggeter一类性能更好,模糊程度略差的方式查询，待suggester没有匹配结果的时候，再fall back到更模糊但性能较差的wildcard, regex, fuzzy一类的查询。

-----------
补记：有同学问regex, fuzzy query是否有同样的问题，答案是有，原因在于他们底层和wildcard一样，都是通过将pattern构造成DFA来加速字符串匹配速度的。

[杭州活动][2017年5月13日] Open Talk 美联集团（蘑菇街）技术专场

活动 • suweibei 发表了文章 • 0 个评论 • 3626 次浏览 • 2017-05-11 17:39 • 来自相关话题

活动时间
2017年5月13日14：00-17：00

活动场地
杭州市拱墅区丰潭路430号丰元国际大厦A座B1楼硬趣空间（城西银泰对面）

报名链接
http://t.cn/RX8xsh6

活动流程
13:30-14:00 签到

14:00-14:10 开场

14:10-15:00 无相蘑菇街稳定性 & 性能工作负责人《蘑菇街稳定性实践》

15:00-15:50 民达美丽联合集团图像算法技术专家《电商中的图像算法与应用》

15:50-16:00 茶歇

16:00-16:50 吴邪美丽联合集团无线应用团队工程师《无线端面向数据设计实践与可视化编程语言Dson》

16:50-17:30 自由交流

讲师介绍
无相蘑菇街稳定性&性能工作负责人
2014年底加入蘑菇街，一直参与稳定性工具和平台的开发与建设，包括全链路监控和压测系统的设计和开发。
《蘑菇街稳定性实践》
本次分享主要介绍：蘑菇街大促保障流程，稳定性平台和工具支持：开关预案系统、限流降级系统、全链路监控系统、强弱依赖系统、全链路压测系统、单机压测系统、容量规划系统、业务全息监控系统、java性能在线分析系统等内容。

民达美丽联合集团图像算法技术专家
2015年加入蘑菇街，现任美丽联合集团（美丽说X蘑菇街）图像算法技术专家，负责图像技术研发工作，带领算法团队与工程和业务团队合作，为集团提供图像技术支持。主要工作包括：图像搜索、图像识别、商品图像内容分析等；业务涉及电商导购、直播等场景。在加入蘑菇街之前，分别在NEC中国研究院、阿里巴巴集团，从事图像技术和机器学习的研究和应用。
《电商中的图像算法与应用》
本次分享主要介绍从电商业务中发现图像算法的价值和利用图像算法，提升电商业务中的用户体验。

吴邪，美丽联合集团无线应用团队工程师
2013年毕业于浙江大学，并加入淘宝从事服务端相关开发工作，后加入阿里云rds团队从事数据库云平台建设。2016年加入美丽联合集团，目前主要负责无线网关数据聚合层。对服务端高性能、高可用设计与编码比较感兴趣。
《无线端面向数据设计实践与可视化编程语言Dson》
本次分享主要介绍mwp-dsl、无线领域前后端开发现状、业界相关内容、mwp-dsl目标、dsl的挑战与核心设计（业务建模，性能与稳定性、安全、易用性）、数据可视化语言Dson、周边配套（开发、测试、管理、运维后台，相关运维体系）、适合的业务场景、后续工作等内容。

往期讲稿/视频回顾
https://opentalk.upyun.com