company_banner

Как мы ускорили поиск на 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-я квантиль, сложные для поиска запросы с максимальным числом результатов:
    HeadHunter
    142.36
    HR Digital
    Share post

    Comments 28

      +1
      WTF?
      final CountDownLatch latch = new CountDownLatch(subReaders.length);
      ...
      latch.countDown();
      ...
      latch.await();
      


      Вы меня, конечно, извините, но правильно вот так:

      List<Future<?>> futures = new ArrayList<Future<?>>();
      for (int i=0; i<subReaders.length; i++) {
          futures.add(executorService.submit(new Runnable() {
              @Override
              public void run() {
                  /// body
              }
          }));
      }
      
      for (Future<?> future : futures) {
          try {
              future.get();
          } catch (InterruptedException e) {
              ///
          } catch (ExecutionException e) {
              // Exception из метода run() - нет нужды в AtomicReference<Throwable> exceptionReference,
              // плюс так можно обработать ВСЕ исключения
          }
      }
      
      


        +5
        Да, Вы правы.
        И даже «submit(new Callable ...», чтобы пробрасывать checked-исключения.
        И модное «catch (InterruptedException | ExecutionException e)».
          0
          Ооо, в Java можно указыать несколько типов исключений в блоке catch. Давно мечтаю о такой фиче в C#.
          • UFO just landed and posted this here
              +1
              Начиная с Java 7.
                –2
                Это вы потроллить так решили?
                        try
                        {
                            string s = null;
                            ProcessString(s);
                        }
                        // Most specific:
                        catch (ArgumentNullException e)
                        {
                            Console.WriteLine("{0} First exception caught.", e);
                        }
                        // Least specific:
                        catch (Exception e)
                        {
                            Console.WriteLine("{0} Second exception caught.", e);
                        }
                
                  0
                  Имеется ввиду несколько типов в одном блоке catch, без дублирования.
                    0
                    Вовсе нет.
                    Вы видимо невнимательно смотрели на Java код?! Там судя по всему можно писать так:
                    try{

                    }
                    catch (InterruptedException | ExecutionException e)
                    {
                    }

                    То есть в одном блоке два типа исключения.
                      0
                      Теперь ясно. Действительно не понял сразу о чем речь.
              +4
              Кстати, вы не пробовали elastic search? Его, конечно, тоже надо настраивать, но там хотя бы нетривиальный многопоточный код писать самому не нужно. Да и интересно было бы сравнить производительность кластера из коробки и собственного решения.
                0
                Кратко: да, мы о нём знаем и о solr.
                Реального сравнения никто не проводил, но есть устоявшееся мнение, что коробочное решение будет медленней кастомного.
                А вообще, наша реализация поиска появилась в то время, когда и solr и elasticsearch были в зачаточном состоянии. С тех пор у нас появилось некоторое количество внутренних решений, которые «нельзя просто взять и перенести».
                Естественно, мы движемся в направлении универсализации и использования стандартных решений.
                  0
                  От Solr остались скорее негативные впечатления, т.к. конфигурировать его довольно неудобно. А вот ElasticSearch действительно понравился. Там довольно много всего сделано для удобства использования и диагностики.
                0
                Осталось только еще качество самого поиска улучшить. А то по запросу технический директор мне что только не вываливается
                  0
                  Ну вот вместо того, что бы загонять мне карму в минус, можно было бы просто принять во внимание замечание. Потому что поиск работает очень плохо.

                  Вот простой пример
                  hh.ru/applicant/searchvacancyresult.xml?areaId=1¬WithoutSalary=&orderBy=0&text=%D0%A2%D0%B5%D1%85%D0%BD%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9+%D0%B4%D0%B8%D1%80%D0%B5%D0%BA%D1%82%D0%BE%D1%80&professionalAreaId=1&desireableCompensation=&compensationCurrencyCode=RUR&specializationId=3

                  Как по запросу «Технический директор» в категории «Информационные технологии» вдруг мне предлагают внезапно: Системный администратор, Преподаватель по HTML, SEO специалист и тем более Тренер-консультант по обучению банковским продуктам.

                    0
                    Кто загонял выяснить не удастся, а за коммент спасибо. Все «плохо работает» мы записываем для последующих опытов.
                      0
                      А по конкретному примеру — в вакансии работодатель указал профобласть «CTO, CIO, Директор по IT»
                        0
                        Это понятно что бывают ситуации, что пользователь неправильно указал категорию. Но я же указал конкретную подстроку — «технический директор». Её нет в указанных вакансиях. Т.е. именно это и смущает. Если бы я просто запросил все вакансии в категории «CTO, CIO, Директор по IT» то претензий не было. А тут два условия и кактегория и подстрока — а как результат- прорываются такие вакансии.
                          0
                          Здесь сработал механизм синонимов. А с ним CTO = технический директор.
                          И указана не подстрока, а два слова (которые, являясь «устоявшимся словосочетанием» будут искаться как синоним).
                          Для самых хитрых у нас есть специальный язык запросов, описанный на hh.ru/article/1175
                          Например, для поиска «подстроки» нужно записать её в кавычках, а для исключения синонимов, указать перед словом восклицательный знак.
                          Ваш случай (строго 2 слова без синонимов стоящие рядом): !«технический директор»
                            0
                            Кавычки нужны обычные, не «ёлочка», ох уж этот хабр )
                    0
                    Фидбэк: на данный момент не работает «поиск по компаниям» (на всякий случай браузер Chrome 31.0.1650.57 m). Не работает поиск по ключевому слову, по клику на буквы. Всегда выводит 0 результатов найдено.
                      0
                      скиньте, плиз, ссылку, где это происходило. можно в личку. за сегодняшний день «на стороне поиска» по компаниям было <10 свалившихся запросов и все до обеда.
                        0
                        Написал в личку.
                      0
                      Быстрый поиск, быстрый поиск… Почему у вас находит по запросу 3000 вакансий, а дает просмотреть лишь 2000? Очень приятный сюрприз, когда доходишь до 20й страницы, получается.
                        +2
                        «Best practices». google по многим запросам тоже рисует миллионы найденных результатов, но просмотреть даёт лишь первые 1000.
                        А если серьёзно, Вы считаете, что это правильно глазами просматривать 2000+ найденных результатов? Не вернее ли подумать пару минут и сузить критерии поиска?
                        0
                        Я думаю, что HH двигается не в самом удачном направлении реализуя полнотекстовый поиск.

                        Возможно следует пересмотреть саму идею поиска? Сделать дерево всех должностей и вернуться к обычному числовому индексу?
                        Навыки для каждой области — реализовать в виде облака и глобальным обратных индексом как в LinkedIn для каждого направления?

                        Такой подход даст полное представление о рынке, а не результат работы Lucene с данными ключевыми словами. Часто сталкиваюсь с вакансиями в которых ненароком использовано конкретное ключевое слово.
                          0
                          После Вашего комментария у меня возникло подозрение, что Вы используете какой-то другой linkedin )
                          Отказываться же от полнотекстового поиска IMHO нельзя, т.к. то, что очевидно в использовании для IT-шников, не всегда настолько же удобно для остальной части аудитории.
                            0
                            > После Вашего комментария у меня возникло подозрение, что Вы используете какой-то другой linkedin )

                            Обратите внимание на блок: «Навыки и квалификация» именно про него я и говорил («реализовать в виде облака и глобальным обратных индексом»).

                            > Не всегда настолько же удобно для остальной части аудитории.

                            Хотелось бы пример…
                              0
                              Меня ввели в заблуждения слова «как в linkedin». Если Вы не пользуетесь мне недоступной beta-версией linkedin, то там я вижу просто текстовое поле и никаких тэгов. Мы ведь говорили о вакансиях.
                              В профилях пользователей да, у них есть скилы/тэги, и там же они здорово задействовали социальную составляющую сети.

                              Пример того как пользователи ищут вакансии? Не будет секретом что есть люди вводящие запросы вида «водитель в Москве от 50000». Поверьте, им не интересны тэги, а облака и деревья для них есть только на небе и в лесу.

                        Only users with full accounts can post comments. Log in, please.