HeadHunter corporate blog
Search engines
Concurrent computing
28 November 2013

Как мы ускорили поиск на hh.ru

image
Некоторое время назад наш поиск стал работать быстрее. Особенно это заметно на сложных для движка запросах, в которых используется минимум фильтров и высокочастотные слова, что требует построить фасеты по результатам и отсортировать максимальные объёмы документов. Но и запросы средней сложности, где в выдаче немного документов, стали обрабатываться заметно быстрее. Почему возникла необходимость что-то ускорять и как мы это делали?

Поиск на hh.ru – это:
  • 400 запросов в секунду;
  • 26 гигабайт обновляющегося в realtime индекса;
  • 3-кратный коэффициент репликации (резервирование отказоустойчивости);
  • 5-кратный запас по производительности.

И вся эта прелесть при общей загрузке системы в 15% на некоторых запросах работала непростительно медленно. Ввиду того, что «активный» индекс резюме значительно больше остальных, особенно это было критично для работодателей.
В основе поиска hh.ru лежит Lucene, поверх которой у нас за много лет написано достаточно много кода. Ранее мы решали частные задачи по оптимизации, в рамках которых пришли к пониманию, что производительность поиска упирается в производительность Lucene. Точнее в то, как мы её используем.

Известно, что то, что нельзя ускорить «в лоб», часто можно распараллелить. В Lucene с версии 3.1.0 имелась возможность делить каждый запрос на несколько потоков по числу сегментов. Но рядом имелся (и в 4.3 версии имеется) комментарий «TODO: should we make this threaded…? the Collector could be sync’d? always use single thread».

А коллекторы (механизм, получающий «по одному» все найденные документы в сегменте) у нас используются повсеместно: на них основан наш код фасетов и сортировок.

В факультативном порядке мы провели эксперимент, в рамках которого был изолирован код, завязанный на коллекторах, данные разбиты на некоторое число сегментов, и произведено сравнение с линейным и параллельным поиском. Он подтвердил возможность ускорения, поэтому мы спланировали задачу, и работа закипела.

Общий план выглядел так:
  • добавляем коллекторам возможность сбора и объединения результатов из нескольких сегментов;
  • реализуем/включаем параллельный обход сегментов;
  • разбиваем индекс на N равных по размеру сегментов;
  • PROFIT.


Пункт 1. Коллекторы


Получилось, что первый пункт плана был реализован в результате рефакторинга в задаче, не имевшей прямого отношения к распараллеливанию. В результате мы получили механизм, позволяющий объединять дерево результатов поиска на скольких угодно уровнях (сейчас у нас четыре уровня: индексы по типам документов, индексов, реплики, сегменты).


Пункт 2. Параллельный обход сегментов


На нём остановлюсь подробнее.

Нам крайне важен был следующий метод IndexSearcher’а:

  public void search(Weight weight, Filter filter, Collector collector)
      throws IOException {

    // TODO: should we make this
    // threaded...?  the Collector could be sync'd?

    // always use single thread:
    for (int i = 0; i < subReaders.length; i++) { // search each subreader
      collector.setNextReader(subReaders[i], docBase + docStarts[i]);
      final Scorer scorer = (filter == null) ?
        weight.scorer(subReaders[i], !collector.acceptsDocsOutOfOrder(), true) :
        FilteredQuery.getFilteredScorer(subReaders[i], getSimilarity(), weight, weight, filter);
      if (scorer != null) {
        scorer.score(collector);
      }
    }
  }

Здесь в цикле по сегментам коллектор переключается на очередной из списка collector.setNextReader(…), а затем scorer «скармливает» найденные документы в коллектор. Именно переключение на сегмент и лишает нас всей прелести многопоточности: при параллельном поиске коллектор не будет знать, к какому сегменту относится тот или иной документ. Решение оказалось достаточно простым: сделать суперколлектор, который будет создавать работников на каждый сегмент:

public interface ParallelCollector {

  /**

   * creates per-segment collector

   */

  Collector createPartialCollector();

}

С таким подходом модификация IndexSearcher’а вышла простой:
  • передаём наш «коллектор»;
  • цикл по subReaders;
  • получаем и инициализируем выделенный коллектор:
        Collector collector = parallelCollector.createPartialCollector();

        collector.setNextReader(subReader, subreaderDocBase);
    
  • уже в Runnable выполняем имеющийся старый код и submit’им его в имеющийся executor;
  • отлавливаем ошибки. В нашем случае – отлавливаем и возвращаем наружу первое полученное исключение.


 public void search(final Weight weight, final Filter filter, final ParallelCollector parallelCollector) throws IOException {
    final CountDownLatch latch = new CountDownLatch(subReaders.length);
    final AtomicReference<Throwable> exceptionReference = new AtomicReference<Throwable>();
    for (int i = 0; i < subReaders.length; i++) {
      final int subreaderDocBase = docStarts[i];
      final IndexReader subReader = subReaders[i];
      executor.submit(new Runnable() {
        @Override
        public void run() {
          try {
            Collector collector = parallelCollector.createPartialCollector();
            collector.setNextReader(subReader, subreaderDocBase);
            Scorer scorer = (filter == null) ?
                                  weight.scorer(subReader, !collector.acceptsDocsOutOfOrder(), true) :
                                  FilteredQuery.getFilteredScorer(subReader, getSimilarity(), weight, weight, filter);
            if (scorer != null) {
              scorer.score(collector);
            }
          } catch (Throwable t) {
            exceptionReference.compareAndSet(null, t);
            throw new RuntimeException(t);
          } finally {
            latch.countDown();
          }
        }
      });
    }
    try {
      latch.await();
    } catch (InterruptedException e) {
      throw new RuntimeException(e);
    }
    Throwable possibleException = exceptionReference.get();
    if (possibleException != null) {
      if (possibleException instanceof RuntimeException) {
        throw (RuntimeException) possibleException;
      } else
      if (possibleException instanceof IOException) {
        throw (IOException) possibleException;
      } else {
        throw new RuntimeException(possibleException);
      }
    }
  }


Пункт 3. Разбивка сегментов


В Lucene по умолчанию предполагается, что сегмент должен быть один. Точнее, к этому Люсина стремится. На самом деле, на каждый flush данных на диск создаётся новый маленький сегмент, который дальше, в соответствии с MergePolicy, автоматически объединяется с другими маленькими сегментами в более крупные, и так по нарастающей. При работающем обновлении индекса «хвост» из мелких сегментов присутствует всегда.

Но разработчики молодцы: они дали средство для ограничения максимального размера сегмента, чем мы и воспользовались — setMaxMergeMB + setMaxMergeMBForForcedMerge решило задачу на ура.

Бонусом решения 3-го пункта стало избавление от механизма оптимизации индекса. В Lucene документы в индекс дописываются. Если требуется документ переиндексировать, старый помечается удалённым, а новая его версия дописывается в конец индекса. В результате со временем появляется много «дыр», индекс раздувается, из-за чего сильно снижается производительность.

Бороться с этим можно периодическими mergeDeletes (ранее expungeDeletes) и forceMerge (ранее optimize), которые копируют «живые» документы из старого (возможно, нескольких) в новый сегмент. Операции эта довольно дорогие в плане дискового ввода/вывода и расхода памяти.

Сегменты малого размера заметно снижают затраты ввиду того, что для обновления/удаления документов приходится переписывать меньше соседних документов.

Результат


Итак, за почти месяц разработки мы получили параллельный поиск и много небольших сегментов. В чем ценность этого?
  • Более быстрый поиск. Теперь результат 95 % поисковых запросов по вакансиям выдается за 10 миллисекунд, а по резюме – за 70 миллисекунд. Для сравнения, еще несколько месяцев назад это было 30 и 270 соответственно.
  • Возможность предложить патч в Lucene (уже вот-вот, но хочется «причесать код»).
  • Избавление от дополнительного механизма оптимизации индекса.


Наглядный результат


Интервал – 2 недели.
Красная линия – было, синяя – стало, ось Y – время отклика.

50-я квантиль, поисковые запросы средней сложности:


И 95-я квантиль, сложные для поиска запросы с максимальным числом результатов:

+24
15.2k 61
Comments 28