之前我在社区里写过 《ElasticSearch集群故障案例分析: 警惕通配符查询》一文，讲的是关于通配符查询可能引起ES集群负载过高的问题。 当时提到wildcard query构造的non-deterministic automaton要经历一个determinize的过程，其间如果生成的状态数量过高，可能引起集群负载彪高，影响对外服务。 但因为determinize的过程中，Lucene对生成的状态数量做了限制，因此在问题查询过去以后，集群还是可以恢复常态。   然而近期我们线上的另外一起故障，使我意识到，Prefix/Regex/Fuzzy一类的模糊查询可能直接让整个集群直接挂掉。   问题出现时，ES服务端日志有如下报错:

[2017-06-14T21:06:39,330][ERROR][o.e.b.ElasticsearchUncaughtExceptionHandler] [xx.xx.xx.xx] fatal error in thread [elasticsearch[xx.xx.xx.xx][search][T#29]], exiting java.lang.StackOverflowError         at org.apache.lucene.util.automaton.Operations.isFinite(Operations.java:1053) ~[lucene-core-6.2.1.jar:6.2.1 43ab70147eb494324a1410f7a9f16a896a59bc6f - shalin - 2016-09-15 05:15:20]         at org.apache.lucene.util.automaton.Operations.isFinite(Operations.java:1053) ~[lucene-core-6.2.1.jar:6.2.1 43ab70147eb494324a1410f7a9f16a896a59bc6f - shalin - 2016-09-15 05:15:20]         at org.apache.lucene.util.automaton.Operations.isFinite(Operations.java:1053) ~[lucene-core-6.2.1.jar:6.2.1 43ab70147eb494324a1410f7a9f16a896a59bc6f - shalin - 2016-09-15 05:15:20]         at org.apache.lucene.util.automaton.Operations.isFinite(Operations.java:1053) ~[lucene-core-6.2.1.jar:6.2.1 43ab70147eb494324a1410f7a9f16a896a59bc6f - shalin - 2016-09-15 05:15:20]

调查后发现，Prefix/Regex/Fuzzy一类的Query，是直接构造的deterministic automaton，如果查询字符串过长，或者pattern本身过于复杂，构造出来的状态过多，之后一个isFinite的Lucene方法调用可能产生堆栈溢出。   一个可以复现问题的regex query如下:

POST /test/_search
{
  "query": {
    "regexp": {
      "test": "t{1,9500}"
    }
  }
}

Github上的issue链接： issues/24553。  对于我们这次特定的问题，是因为prefix Query里没有限制用户输入的长度。 看ES的源码，PrefixQuery继承自Lucene的AutomatonQuery，在实例化的时候，maxDeterminizedStates传的是Integer.MAX_VALUE, 并且生成automaton之前，prefix的长度也没有做限制。 个人认为这里可能应该限制一下大小，避免产生过多的状态:

public class PrefixQuery extends AutomatonQuery {

  /** Constructs a query for terms starting with <code>prefix</code>. */
  public PrefixQuery(Term prefix) {
    // It's OK to pass unlimited maxDeterminizedStates: the automaton is born small and determinized:
    super(prefix, toAutomaton(prefix.bytes()), Integer.MAX_VALUE, true);
    if (prefix == null) {
      throw new NullPointerException("prefix must not be null");
    }

 最终抛出异常的代码是 org.apache.lucene.util.automaton.Operations.isFinite，   可以看到这段代码里用了递归，递归的深度取决于状态转移的数量。根据注释的说明，这是一段待完善的代码，因为使用了递归，可能导致堆栈溢出:

  // TODO: not great that this is recursive... in theory a
  // large automata could exceed java's stack
  private static boolean isFinite(Transition scratch, Automaton a, int state, BitSet path, BitSet visited) {
    path.set(state);
    int numTransitions = a.initTransition(state, scratch);
    for(int t=0;t<numTransitions;t++) {
      a.getTransition(state, t, scratch);
      if (path.get(scratch.dest) || (!visited.get(scratch.dest) && !isFinite(scratch, a, scratch.dest, path, visited))) {
        return false;
      }
    }
    path.clear(state);
    visited.set(state);
    return true;
  }

由此可见，在项目里使用了模糊查询的同学，一定一定要注意限制用户输入长度，否则可能导致集群负载过高或者整个挂掉。    虽然Lucene/Elasticsearch应该在代码层面做一些限制，确保有问题的query不会导致stack overflow，但是当用到这类查询的时候，程序员的思维方式还局限在RDBMS开发的时代。 我们应该多在数据索引阶段下功夫，确保尽量用最高效的term query来完成绝大多数的查询。 

[携程旅行网： 吴晓刚]  许多有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来加速字符串匹配速度的。