Поиск

Введение

Всем добрый день. Меня зовут Александр. Сейчас я работаю в Мегафон front-end разработчиком. Проблемы поиска данных всегда отличались особенной сложностью и зачастую нестандартностью в подходах. Сегодня я бы хотел остановиться на одной интересной задаче, которую мне пришлось решать совсем недавно во время разработки платформы Интернета вещей. Впрочем, такая задача, может встретиться и на любом другом проекте, где есть динамическая подгрузка данных по REST API. Будь то подгрузка во время пагинации, или во время скроллинга, или как то иначе

Проблематика

Казалось бы: в чем может быть трудность. Особенно когда речь касается только фронта? Ведь все алгоритмы поиска реализуются в основном на бэке. На самом деле и да, и нет. Давайте представим простую таблицу, у которой есть пагинация из нескольких страниц и фильтр на каждом столбце. См. ниже.

В данной табличке открыт фильтр по столбцу Номер БС. Простыми словами: вводя любые символы в поле ввода фильтра, вы получаете подходящие опции в дропдауне. Кликнув на любую из них, вы отфильтруете данные в таблице по этому элементу.

Каким образом можно вывести подобный дропдаун с нужными опциям?

Варианты решения

1. Составить массив из всех элементов столбца таблицы и с помощью методов filter и includes (или им подобных) показать нужные опции в дропдауне. Проблема в том, что компонент таблицы не знает о элементах, которые находятся на других страницах. Они подгружаются только при переходе на эти страницы. А значит поиск будет осуществляться не по всем элементам.

2. Сформировать массив как в 1-м варианте, но запрашивая его с бэка. Хороший вариант, но производительность такого подхода близится к 0. Что если записей 1 млн? В таблице именно для этого и используется пагинация.

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

   Отлично. Именно этот вариант мы и рассмотрим. На рисунке выше изображен именно он: мы ищем записи, которых нет на текущей странице, однако в дропдауне видим подходящие варианты со всех страниц.

Алгоритм

1. Для каждого столбца должен существовать запрос на бэк и поле, которое мы будем брать из ответа, чтобы заполнить опции. Нужен config.

2. После ввода данных их нужно отправлять на бэк. Можно по кнопке, но лучше использовать периодическую отправку в функции debounce.

3. Во время процесса отправки/получения данных показывать loader

4. Получения ответа от бэка и заполнение опций для дропдауна из заданного поля ответа

Решение

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

Итак, начнем по порядку. Как мы выяснили, для начала нужен конфиг для таблицы (для каждого столбца) и ее фильтров. Разделим его на 2 файла.

Пример конфига столбца таблицы:

{  id: 'address',  title: 'Адрес объекта',  filter: filters.address,  checked: true,  minWidth: 160}

Пример конфига фильтра:

address: {  type: 'includes',  name: 'addrFilter',  options: {    default: {      values: 'objectsList',      fetchFunc: 'fetchObjectsList',      calcFunc: 'address'    }  }}

Как можно заметить конфиги связаны по типу один-ко многим. То есть один и тот же фильтр может соответствовать нескольким столбцам таблицы.

Поле options содержит как раз поля для конфигурации опций фильтра. Например:

• fetchFunc - имя thunk функции, которая загружает данные для этого фильтра

• values - поле из ответа сервера, в котором содержатся опции

• calcFunc - имя функции для трансформирования опций

Остановимся подробнее на calcFunс. При таком алгоритме, что был описан в опции попадают данные из определенного поля ответа. Но что если поле составное, например в каждую опцию фильтра должно попасть сразу несколько полей. Пример с адресом: опция фильтра = город + улица + дом

В этом нам и поможет функция предварительного обсчета опции. Вот пример реализации:

//object includes calc functionsconst calculatedData = useMemo(() => (  {    default: (values) =>    {      //default calculate    },    address: (values) =>    {      //calculate with generateAddress function, for example    },    ...}), [...]);//using this object (calcFunc from config):const data = calculatedData[calcFunc || 'default'](values)

Далее. Как уже говорилось лучше всего отправлять запросы через определенный интервал задержки. То есть пользователь вводит данные в поле, приостановился на полсекунды - произошла отправка. Реализуется это примерно так:

// debounce functionconst debounce = (fn, ms = 0) => {  let timeoutId;  return function(...args) {    clearTimeout(timeoutId);    timeoutId = setTimeout(() => fn.apply(this, args), ms);  };};//debounceFetch functionconst debounceFetch = debounce(async (func, args) =>   typeof func === 'function' && (await func(args)), 500);//sending requestuseEffect(() => {  debounceFetch(actions[fetchFunc], {     filter: { [filterName]: filterValue || null }   });}, [filter]);

Продолжаем. В текущей задаче может понадобиться определить грузится ли в данный момент какой-либо фильтр, например, чтобы показать лоадер. У нас в команде приняты некоторые стандарты для именования переменных, например, все переменные, показывающие процесс загрузки начинаются с isLoading. Например, isLoadingObjects. Поэтому идеальным решением будет создать selector для kea, который = true если хотя бы в одном стейте, содержащем в названии isLoading, содержится значение true.

Если вы используете не kea, а обычный redux или какую-то другую библиотеку - уверен, вы адаптируете этот код под свои нужды. Если нет - пишите мне. А лучше используйте kea =)

Далее вы просто показываете лоадер пока anyLoading===true, все как обычно.

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

Всю логику лучше всего будет объединить в один хук и назвать его, скажем, useFiltersOptions.

Выводы

Используя рассмотренный алгоритм, мы решаем задачу поиска оптимальным путем: все сложные вычисления отдаем на бэк, делая это постепенно, следуя за вводом пользователя. Плюс к этому у нас появляются огромные возможности для расширения, используя конфиг таблицы, конфиг фильтров и функцию предварительной обработки ответа сервера.

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

Если вам нужно найти фотографию, сделанную на пикнике несколько лет назад, вряд ли вы помните имя, которое камера автоматически присвоила файлу в момент съёмки, например, 2017-07-04 12.37.54.jpg.Вы просматриваете всё подряд фотографии, их эскизы, пытаетесь определить объекты или признаки искомого и не важно, ищете ли вы потерянное фото или хотите подыскать в архивах приличный снимок для презентации нового проекта.

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

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

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

Наш метод

Формулируем задачу поиска изображений: необходимо найти функцию релевантности, которая принимала бы на входе (текстовый) запрос q и изображение j, а на выходе выдавала бы оценку релевантности s в баллах, показывающую, насколько точно изображение соответствует запросу:

s = f(q, j).

Если пользователю нужно найти какое-либо изображение, мы применяем эту функцию ко всем изображениям, и функция выдаёт отсортированный по степени приближения список изображений с балльной оценкой выше порогового значения. Мы создавали такую функцию на базе двух ключевых разработок в области машинного обучения: точной классификации изображений и векторов слов.

Классификация изображений

Классификатор изображений считывает изображение и выдаёт балльный список категорий, описывающих его содержание. Более высокие баллы указывают на большую вероятность того, что изображение относится к данной категории.

Категории могут быть следующими:

• конкретные объекты на изображении, например, дерево или человек;

• общие дескрипторы сцены, например, на улице или свадьба;

• характеристики самого изображения, например, чёрно-белое или крупный план.

За последнее десятилетие был сделан огромный шаг вперёд в области в классификации изображений с помощью свёрточных нейронных сетей достаточно упомянуть замечательную работу 2012 года. Krizhevsky и др. на турнире ImageNet Сhallenge. С тех пор, благодаря усовершенствованию архитектуры моделей, улучшению методов обучения, большим базам данных, например Open Images или ImageNet, и простым в использовании библиотекам, таким как TensorFlow и PyTorch, исследователи создали классификаторы изображений, способные распознавать тысячи категорий. Оцените, насколько качественно сегодня работает классификация изображений:

Классификация изображений хороша тем, что автоматически определяет объекты на изображении, но для эффективного поиска одной этой функции недостаточно. В самом деле, если пользователю нужно найти фото с пляжа, эта функция действительно может выдать фото с самыми высокими балльными оценками для этой категории, но что, если пользователь задаст поиск не пляжа, а берега? Что если пользователь задаст поиск не яблока, а фрукта или сорта яблок гренни смит?

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

Векторы слов

Давайте несколько переформулируем задачу. Выход классификатора изображений можно интерпретировать как вектор j_c балльных оценок по каждой категории. Данный вектор определяет содержание изображения как точку в C-мерном пространстве категорий, где C количество категорий (несколько тысяч). Если нам удастся извлечь осмысленное представление запроса в таком пространстве, мы сможем понять, насколько близко вектор изображения находится к вектору запроса, и принять это за меру соответствия изображения запросу.

Получение векторных представлений текста предмет большого количества исследований в области обработки с использованием естественного языка. Один из наиболее известных методов в этой области word2vec описан в статье Mikolov и др. в 2013 году. Каждому слову в словаре функция Word2vec присваивает собственный вектор, и, исходя из этого, слова имеющие сходные значения, будут иметь близкие друг к другу векторы. Эти векторы находятся в d-мерном векторном пространстве слов, где d обычно составляет несколько сотен.

Узнать векторное представление поискового запроса можно, просто просмотрев его вектор word2vec. Этот вектор не является частью пространства категорий векторов классификатора изображений, однако можно преобразовать его в пространство категорий, ссылаясь на названия категорий изображений следующим образом:

1. Для слова запроса q можно получить d-мерный вектор слов q_w, нормализованный к единичному вектору. Для векторов в пространстве слов будем использовать нижний индекс w, а для векторов в пространстве категорий нижний индекс c.

2. Для каждой категории получаем нормализованный вектор слов для названия категории cⁱ_w. Затем определяем значение mi = q_w - cⁱ_w косинусное сходство векторов запроса и i-й категории. Полученная оценка от -1 до 1 показывает, насколько близко слово запроса соответствует названию категории. Сводя отрицательные значения к нулю (то есть применяя функцию mi = max(0, mi)), получаем оценку в том же диапазоне, что и результаты классификатора изображений.

3. Таким образом, можно вычислить q_c = [m1 m2 ... mC], вектор в C-мерном пространстве категорий, показывающий, насколько близко запрос соответствует каждой из категорий аналогично тому, как вектор классификатора изображений для каждого изображения показывает, насколько близко изображение соответствует каждой из категорий.

Шаг 3 осуществляем обычное векторно-матричное умножение, q_c = q_wC, где C матрица со столбцами векторов слов категории cⁱ_w.

После сопоставления запроса с вектором пространства категорий q_c к вектору пространства категорий для каждого изображения можно применить косинусный коэффициент и получить таким образом окончательный балл релевантности для изображения s = q_cj_c.

Мы получили функцию релевантности. С её помощью мы ранжируем изображения побалльно и формируем список результатов запроса. Применение данной функции к набору изображений можно также выразить как векторно-матричное умножение, s = q_cJ, в котором каждый столбец J представляет собой выходной вектор классификатора j_c для изображения, а s вектор балльных оценок релевантности для всех изображений.

Пример

Рассмотрим пример с небольшим количеством измерений. В нём векторы слов имеют три измерения, а классификатор четыре категории: яблоко, пляж, одеяло и собака.

Предположим, пользователь искал берег. Просматриваем вектор слов, получаем [0,350,62 0,70], затем умножаем на матрицу векторов слов категорий и проецируем запрос на пространство категорий.

Поскольку вектор слова берег близок к вектору слова пляж, данная проекция имеет высокое значение в категории пляж.

Описание модели

Наш классификатор изображений представляет собой сеть EfficientNet, натренированную на наборе данных OpenImages. Классификатор выдаёт балльные оценки примерно по 8500 категориям. Мы выяснили, что данная архитектура и набор данных обеспечивают хорошую точность при разумных затратах. Это довольно важно, если приходится работать с клиентской базой Dropbox.

Для тренировки и запуска модели будем использовать TensorFlow и заранее обученные векторы слов ConceptNet Numberbatch. Полученные результаты оказались удовлетворительными, и, что важно для нас, модель способна работать с несколькими языками, возвращая сходные векторы для слов на разных языках со сходными значениями. Это упрощает процесс поиска изображений на разных языках: векторы слов dog на английском языке и chien на французском сходны, поэтому мы можем осуществлять поиск на обоих языках без перевода поискового запроса с одного языка на другой.

Для поиска по нескольким словам будем анализировать запрос как логическую операцию AND, применённую к отдельным словам. Мы также ведём перечень терминов, состоящих из нескольких слов, например beach ball, которые можно рассматривать как одно слово. Если запрос содержит один из таких терминов, мы делаем альтернативный синтаксический разбор и применяем операцию OR для двух разобранных запросов, после чего запрос beach ball принимает вид (beach AND ball) OR (beach ball). Этот термин будет подходить для поиска как больших разноцветных надувных мячей для игры на пляже, так и для теннисных мячей на песке.

Архитектура в производственной среде

Каждый раз, когда пользователь выполняет поиск, получать полную и актуальную матрицу J не вполне практично. Пользователь может иметь доступ к сотням тысяч или даже миллионам изображений, а наш классификатор способен работать с тысячами измерений, поэтому такая матрица может содержать миллиарды записей и должна обновляться каждый раз, когда пользователь добавляет, удаляет или изменяет изображение. Для сотен миллионов пользователей такой подход просто нереализуем (пока).

Поэтому вместо создания экземпляра J для каждого запроса мы используем описанный выше приближённый метод, который может быть эффективно реализован на поисковом движке Dropbox Nautilus.

По сути, Nautilus состоит из прямого индекса (forward index), сопоставляющего каждый файл с определёнными метаданными (например, именем файла) и полным текстом файла, и инвертированного индекса (inverted index), сопоставляющего каждое слово со списком публикаций (posting list) для всех файлов, содержащих это слово. При текстовом поиске содержимое индекса для нескольких файлов с рецептами может выглядеть примерно так:

Если пользователь ищет белое вино, мы ищем эти два слова в инвертированном индексе и обнаруживаем в doc_1 и doc_2 оба слова, поэтому мы должны включить их в результаты поиска. В doc_3 есть только одно из этих слов, поэтому мы должны либо опустить его, либо поставить последним в списке результатов.

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

Применение методов текстового поиска для поиска изображений

Систему текстового поиска можно использовать для реализации нашего алгоритма поиска изображений. В прямом индексе можно хранить вектор пространства категорий j_c каждого изображения. В инвертированном индексе для каждой категории будет храниться список публикаций изображений с положительными балльными оценками для данной категории.

Предположим, пользователь ищет слово пикник:

1. Находим вектор q_w для слова пикник и умножаем его на матрицу проекции пространства категорий C и получаем q_c, как описано выше. C это фиксированная матрица, одинаковая для всех пользователей, поэтому её можно хранить в памяти.

2. Для каждой категории, имеющей ненулевую запись в q_c, получаем список идентификаторов из инвертированного индекса. Объединение таких списков представляет собой набор совпадающих изображений, полученных в результате поиска, однако эти результаты ещё необходимо ранжировать.

3. Для каждого результата поиска возьмём вектор пространства категорий j_c из прямого индекса и умножим его на q_c, чтобы получить балльную оценку релевантности s. Получаем результаты с балльной оценкой выше порогового значения, ранжированные по этой балльной оценке.

Оптимизация для масштабируемости

Описанный подход по-прежнему связан со значительными затратами как с точки зрения пространства для хранения данных, так и с точки зрения времени обработки запросов. Для 10000 категорий в прямом индексе для каждого изображения необходимо хранить 10000 балльных оценок классификатора, что при использовании четырёхбайтовых значений с плавающей запятой составляет 40 КБ. А поскольку оценки классификатора редко когда бывают строго нулевыми, в большинство из таких 10000 списков идентификаторов будет добавлено стандартное изображение. Если для идентификаторов изображений использовать четырёхбайтовые целые числа, добавятся ещё 40 КБ и стоимость индексирования одного изображения составит 80 КБ. Другими словами, для многих изображений их индекс будет больше по размеру, чем сам файл изображения!

Что касается времени обработки запроса, под которым понимается задержка, с которой система выдаёт пользователю результаты поиска, мы можем ожидать, что около половины балльных оценок совпадения запроса и категории mi будут положительными, поэтому нам придётся прочитать около 5000 списков идентификаторов из инвертированного индекса. Если сравнивать с текстовыми запросами, то они обычно считывают всего около 10 списков публикаций.

К счастью, существует множество близких к нулю значений, которые вполне можно отбросить, и это не повлияет качество поиска. Оценка релевантности для каждого изображения была представлена выше как s = q_cj_c, где q_c балльная оценка соответствия между запросом и каждой из примерно 10000 категорий, а j_c балльные оценки приблизительно 10000 категорий, полученные с помощью классификатора. Оба вектора в основном состоят из близких к нулю значений, которые не вносят практически никакого вклада в s.

В нашем приближении мы определим значения всех записей q_c и j_cкак равные нулю, кроме нескольких самых больших. Экспериментально было выяснено, что сохранение 10 записей в q_c и 50 записей в j_c вполне достаточно для получения не менее содержательного итогового результата. Экономия на хранении и обработке данных получилась довольно существенной:

• В прямом индексе вместо 10000-мерных плотных векторов мы храним разрежённые векторы с 50 ненулевыми записями, то есть с 50 записями с наиболее высокими балльными оценками категорий для каждого изображения. В разрежённом представлении мы храним позицию и значение каждой ненулевой записи; 50 двухбайтовых позиций (записанных целыми числами) и 50 четырёхбайтовых значений (записанных в виде числа с плавающей точкой) требуют всего около 300 байт.

• В инвертированном индексе каждое изображение добавляется не в 10000, а в 50 списков идентификаторов, что обходится всего в 200 байт. Таким образом, общий размер индекса для каждого изображения составляет 500 байт вместо 80КБ.

• Во время запроса q_c имеет 10 ненулевых записей, поэтому нужно просканировать только 10 списков идентификаторов примерно такой же объём работы выполняется в текстовых запросах. Набор результатов сужается, и такой набор можно быстрее оценить.

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

Доступность функций

Функция поиска в изображениях в настоящее время доступна для всех наших пользователей профессионального и бизнес-уровня. Объединяя функции поиска в любых изображениях, OCR-поиска в изображениях и документах и полнотекстового поиска в текстовых документах, мы делаем большинство файлов пользователей доступными для поиска на основе содержимого.

Поиск в видео?

Естественно, мы работаем над функцией поиска содержимого в видеофайлах, хранящихся в Dropbox. Создание функции поиска изображений приближает нас к решению этой задачи. Со временем, мы надеемся, пользователи смогут осуществлять поиск данных и в видеофайлах. Методы поиска одного кадра в видео или индексирования всего клипа для поиска, возможно, посредством совершенствования техник работы с неподвижными изображениями, пока ещё находятся на стадии разработки, но вспомните, что всего несколько лет назад фраза "найти все фотографии, где я на пикнике со своей собакой" работала только в голливудских фильмах.

Искусственный интеллект сегодня экономит не только время, но и силы, которые направляются на решение всё более сложных задач. И если вам интересно решать задачи в области искусственного интеллекта, вы можете обратить внимание на наш курс "Machine Learning и Deep Learning", разработанный совместно с компанией NVIDIA.

Узнайте, как прокачаться и в других специальностях или освоить их с нуля:

• Профессия Data Scientist

• Профессия Data Analyst

• Курс по Data Engineering

Привет, меня зовут Евгений. Я разрабатываю инфраструктуру поиска Яндекс.Маркета. Хочу рассказать, как graceful degradation помогает нам обрабатывать больше запросов, чем физически могут выдержать наши сервера, и что происходит с поиском в Маркете, если один из дата-центров отключается.

Проблема

Все критичные сервисы в Яндексе должны переживать отключение одного из дата-центров (ДЦ), поэтому обычно они размещаются минимум в трёх ДЦ.

Но когда все ДЦ работают, каждый из них оказывается задействован лишь на 60%. Ещё 10% резервируются для экспериментов и непредвиденного роста, а оставшиеся 30% используются только в случае, если один из ДЦ отключается, и нужно перераспределить запросы.

Если сервис работает на сотнях серверов, 30% это огромное количество железа. А поскольку отключаются ДЦ очень редко, резервные мощности почти всегда простаивают.

Нам хотелось бы меньше греть воздух, ведь если сократить количество железа в каждом ДЦ хотя бы на 10%, речь уже шла бы о внушительных суммах. При этом, если просто вытащить часть железа, а затем при пиковой нагрузке какой-то из ДЦ отключится, оставшиеся мощности могут не справиться. Резко вырастет время ответа пользователю, а некоторые запросы будут вообще оставаться без ответа.

Применяем graceful degradation

Graceful degradation или изящная деградация это подход к построению систем, при котором система продолжает выполнять свою основную функцию, даже если отдельные её элементы вышли из строя.

Мой коллега из Яндекс.Такси уже рассказывал про graceful degradation в случае, когда ломается часть сервиса. Мы же применили этот подход на бэкендах для ситуации, когда у нас отключается значительное количество серверов.

Нашей целью было сделать так, чтобы сервис продолжал работать полностью, но нагрузка на него уменьшалась бы, а пользователи при этом не замечали бы разницы. Мы хотели научить наш поисковый сервис понижать среднюю нагрузку от одного запроса, что позволило бы обрабатывать большее количество запросов на меньшем количестве железа.

Чтобы запустить graceful degradation, нам надо было решить две задачи:

1. Разработать механизм уменьшения нагрузки.

2. Сделать автоматизацию включения механизма.

Механизм уменьшения нагрузки

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

Другой вариант использовать облегчённый алгоритм ранжирования. Минус в том, что это долго и сложно новый алгоритм надо обучить и потом постоянно переобучать. Кроме того, состояние нашей системы может быть только вкл. или выкл., а нам хотелось бы иметь механизм плавного уменьшения нагрузки.

Таким образом, мы выбрали третий вариант снижать качество. Основное преимущество этого подхода возможность уменьшать нагрузку на 5%, 10% и так далее.

Допустим, вы ищете себе новый телефон и заходите в категорию Смартфоны на Яндекс.Маркете. Я уже подробно описывал, как работает наш поиск: запрос отправляется во фронтенд, надо показать пользователю 48 лучших предложений из категории с телефонами для конкретного региона. Фронтенд делает свой запрос в поисковый бэкенд.

Бэкенд получает запрос и раcпределяет его на 8 серверов с шардами. В шардах хранятся предложения от магазинов.

На каждом шарде поиск проходит несколько стадий. На стадии фильтрации ищется примерно 50000 предложений, это число зависит от категории. На этапе ранжирования для каждого предложения вычисляется релевантность, учитывается цена, рейтинг товара, рейтинг магазина и ещё более 2000 факторов. ML по факторам вычисляет вес каждого предложения. Затем берётся только 48 лучших. Meta Search получает эти 48 предложений с каждого шарда, то есть всего 48*8=384 предложения. Предложения снова ранжируются, опять берётся 48 лучших. Последние 48 уже показываются пользователю. То есть чтобы показать нашим пользователям 48 телефонов, мы обрабатываем 400 000 предложений.

В случае с graceful degradation, когда надо уменьшить нагрузку, мы можем скомандовать: теперь обрабатывай 95% документов, а теперь 90% или 80%. Если обрабатывать 95%, то есть 400000*0.95=380 000 документов, то из них всё равно выбираются 48 лучших предложений для выдачи. И в среднем только 2 предложения будут отличаться от изначальной выдачи без снижения качества. При таком маленьком изменении большинство пользователей даже не заметят разницы.

Автоматизация включения механизма

Автоматизация работает за счёт постоянного мониторинга загрузки CPU. Если нагрузка становится выше 90%, автоматика начинает снижать качество. На 90% снижение небольшое, но если нагрузка продолжает расти, процент деградации повышается линейно и доходит до максимума при 100% загрузки CPU. Такой подход позволяет снижать качество минимально.

Общий алгоритм выглядит так:

При выключении ДЦ: балансеры перераспределяют запросы в оставшиеся ДЦ => нагрузка на CPU повышается => при превышении порогового значения происходит снижение качества по заданной формуле.

При включении ДЦ: балансеры перераспределяют запросы на все ДЦ => нагрузка на CPU снижается => понижение качества прекращается.

Внедрение

Для внедрения мы провели несколько экспериментов и понижали качество на небольшом проценте пользователей. В течение недели мы постоянно отслеживали уменьшение нагрузки и одновременно количество переходов на магазины-партнёры. Имея на руках цифры, мы договорились с бизнесом на максимальное снижение кликов в 1% при снижении качества. Исходя из этого мы посчитали, сколько серверов можем отдать другим проектам или выключить для резерва. У нас получилось 15% всех мощностей поиска.

В конце, когда всё было готово, мы провели эксперимент с отключением дата-центра, чтобы убедиться, что всё работает как надо.

Выводы

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

Возможно, те кто постарше, еще помнят price.ru. Вот и я еще помню те времена, когда Яндекс Маркета не было вообще. И даже был период, когда я пытался делать аналог price.ru для американского заказчика, и при этом amazon.com был у нас всего-лишь одним из многих сайтов - источников сведений о товарах (книгах, CD-ROM и т.п.), при том не самым крупным, и еще был живой yahoo... В общем, с тех пор многое изменилось.

Потом появился Яндекс Маркет, сильно вырос Амазон, и скажу прямо - много лет я использовал их как основной инструмент для поиска нужных мне товаров. А теперь вот подумываю, не уйти ли куда-то, на e-katalog скажем (шутка, там свои проблемы)? Или найти другое решение, получше?

Почему, спросите вы? Ну, в первую очередь потому, что поиск. Поиск категорически перестал меня устраивать.

Попробуем описать для начала, с какими проблемами я сталкивался при поиске. Яндекс Маркет тут будет как пример, но многое из описанного касается и других похожих сайтов (Амазон - первый же кто приходит на ум, и там все почти так же плохо).

Как выглядит поиск здорового человека? Ну, как-то вот так наверное :)

Если что, это реальный скришнот с мобильного приложения Маркета, сделанный с год назад. Сочетание страницы про IPhone и фото циркулярки от DeWalt сделало тогда мой день. Ну ок, это был баг, его исправили, так что забудем про это и вернемся к реальному поиску и его результатам.

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

Начнем с того, какие на мой взгляд, бывают интернет-магазины?

• Узко специализированные. В нашем случае это например магазин Рубанков, инструменты и прочие товары для столярки. Его отличает от прочих то, что там знают о существовании компаний-производителей японского ручного инструмента Silky, или известнейшей канадской инструментальной компании Veritas. И продукция этих производителей не просто есть на сайте, но и, как правило, в наличии. Специализация не значит, что тут вы найдете все - скажем, инструмент элитного уровня от производителя Bridge City вы вообще в РФ скорее всего не купите. Но тем не менее, тут есть многое.

• Просто специализированные. Это например Все Инструменты. Тут вы тоже сможете найти товары от той же Silky - но в наличии только одна пилка (из обширного ассортимента в десятки моделей).

• Не специализированные. Ну это просто Яндекс Маркет, и большинство тех, кто продает на нем. Магазины из двух предыдущих пунктов тут тоже представлены, но структура каталога - от Маркета. Так вот, в нашем конкретном случае Маркет вообще не знает о существовании таких производителей, как Silky или Veritas, и даже если товар (скажем пилу) вы сможете найти - то не через каталог и выбор производителя. А поиск по Veritas приведет вас в лучшем случае к швейным машинкам.

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

Во-первых, это отсутствие специалистов именно в узком сегменте, которые бы детально разбирались в товаре. При этом слово "узкий" не следует понимать буквально, потому что узкий сегмент инструмента, к примеру, это на самом деле широчайший ассортимент, которые растет и меняется каждый год. И который производят как известные солидные фирмы, так и мелкие (в основном китайские) фирмочки. Результат - неполные и неточные описания товаров.

Во-вторых, типовая, уже скорее техническая проблема - это отсутствие уникального идентификатора у товара. Очень часто один товар продается в разных комплектациях. Компьютер в памятью 8 или 16 гигабайт из коробки, инструмент в картонной коробке или кейсе, с теми или иными дополнительными приспособлениями либо расходкой. При этом в сущности, это одна и та же модель - но стоимость дополнительной расходки, кейсов, памяти и пр. вполне может составлять значительную часть цены. Эта проблема приводит к дублированию позиций в поиске, и затрудняет выбор лучшего предложения.

Ну и наверное третья - небольшая глубина и ширина каталога в специализированных разделах. Скажем, при том что в Яндекс Маркете есть 14 (sic!) типов ручных рубанков - там все равно нет например грунтубелей. Ну т.е. даже если у продавца такой появится - в поиске он все равно будет валяться в общей куче (то, что в Яндекс Маркете при этом в основном вообще одна китайская дешевка - это отдельная история, тут я бы винил скорее покупателей, что лучше берут - то и в продаже).

Таким образом, мы имеем, с одной стороны, объяснимый недостаток специалистов, которые разбирались бы в товаре, его пользовательской ценности, комплектации, отличиях моделей друг от друга, а с другой - кучу этих самых моделей, которые отличаются непойми чем. На выходе получается тоже довольно странно. Вот например это - фрагмент моих закладок:

Что мы тут видим? Яндекс Маркет знает, что был вот такой товар, Bosch Biturbo GKT 18V-52 GC бла-бла-бла (в конце концов, я же как-то его в закладки поместил, правда?). И он раньше продавался, а теперь (в этом магазине) не продается. Но он был, и Маркет знает про него достаточно, чтобы его найти. В теории... а попробуем найти реально?

Я не буду приводить вам полный скриншот результатов поиска, они длинные.

Что мы тут видим? Мы видим, что именно этого товара в списке результатов нет. А есть куча других, которые сюда попали не иначе, как по недоразумению. Ну то есть, с одной стороны - в списке куча пил, в названии которых встречается 18V или 18В. С другой - вот на третьей позиции пилка от Bosch на 12 вольт. С третьей - есть пилы сетевые. Есть Bosch PRO и Bosch DIY (несовместимые друг с другом). Есть вообще другие производители. Но самое смешное то, что в длиннющем списке есть лишь одна сетевая погружная пила, которая реально является аналогом искомого товара - на восьмом месте в списке. Ну т.е. на 99% результаты поиска - мусор.

Если вы вдруг не заметили: оно ищет по 18V. А по слову the в английском тексте они не пробовали искать? Нашли бы намного больше :) Где же ваш ИИ, в конце концов?

Решение?

Главный вопрос - что с этим можно сделать? Если бы директором был я (с), то я бы пошел по пути, который давно опробован (скажем, в картах), и пусть не идеально, но работает. Пусть у вас (а в данном случае у вас - это ни у кого) нет специалистов, которые глубоко разбирались бы в товарах, зато у вас есть сообщество. И это сообщество как раз разбирается - ну хотя бы настолько, насколько ему это нужно. Следует сделать так, чтобы каталог товаров был устроен наподобие wiki. И дать возможность пользователям самим расширять и исправлять характеристики товаров.

Сейчас некоторые карточки товаров уже отличаются от других. Вот конкретно эта - предложение магазина itUnite:

Вероятно, эти карточки заполняет продавец, а Маркет тут является платформой, позволяющей магазинам публиковать предложения. И все бы неплохо - кто публикует, тот и отвечает за качество описания. Но...

Если посмотреть внимательно, то ровно эта же пила есть и сама по себе, в виде обычной карточки. Т.е. эта часть товаров просто не занесены в каталог как следует, и поэтому они дублируют друг друга (а если предложений много - то это может быть и три карточки, и больше).

Одна из вещей, которые сообщество могло бы сделать - это как раз убрать это дублирование, т.е. отметить в каталоге, что вот эти карточки - это комплектации или предложения одного и того же товара. Вторая - это занести в каталог такие малоизвестные :) фирмы, как канадская Veritas, или Lee Nielsen, научить софт различать японские пилы катаба и дозуки, и учитывать многие другие тонкости. По сути - пополнять и исправлять каталог на постоянной основе.

Вернемся еще раз к нашей Bosch Biturbo GKT 18V-52 GC. Почему сегодня результаты поиска нерелевантны? Потому что они очевидно не учитывают один из признаков этой пилы - она погружная. Т.е. мы можем нажать на рукоятку, и погрузить диск в материал. Все пилки с префиксом GKS этого не умеют, так что аналогом не являются. С другой стороны, есть ли у найденных товаров что-то общее? Да, есть - у некоторых. Буковка G в обозначении пилы показывает, что пила умеет работать по направляющей шине. Т.е. GKT 18V-52 GC умеет, и GKS 18V-57 G тоже. И как ни странно, но умеет и GKS 12V-26 - хотя в обозначении этого признака в виде буковки тут G нет. Что-то из атрибутов можно было бы извлечь, применяя методы типа машинного обучения, NLP и т.п. Но проще всего - доверить это сообществу.

Дав конечному пользователю возможность редактировать атрибуты, можно было бы позволять ему добавить к некоторым из этих товаров аттрибут "погружная", или атрибут "работа по шине". Что характерно - если попробуете сейчас эти свойства найти в описании, то вы их не найдете. На самом деле все еще чуть сложнее, потому что есть разные типы шин, и лишь некоторые из них совместимы, так что работа по шине - это на самом деле тип поддерживаемой шины, от которого мы приходим к моделям самих шин, и уже к их атрибутам).

Ну и добавив атрибуты, нужно сделать возможным потом по ним искать, естественно. Понятно, что дать редактировать описания и заголовки тоже было бы неплохо. Тогда не было бы таких карточек товаров, как вот эта:

Проблема тут в том, что это не плитка. На ней нельзя готовить, ее даже нельзя поставить так, чтобы нагреваемая поверхность была горизонтальна. При этом в отзывах (год назад) это уже было явно написано. И что вы думаете, хоть кто-то озаботился тем, чтобы поправить заголовок? Только сообщество, на мой взгляд в состоянии такое привести в нормальный вид.

Что еще можно и нужно улучшить?

Стоит заметить, что редактировать сообществу нужно позволять не только атрибуты, но и метаданные о них (тип данных, по сути), потому что сегодня органы управления поиском - это отдельная боль. Скажем, как выглядит чекбокс курильщика? А вот он:

В чем тут проблема? В том, что выбор между аккумуляторным и сетевым инструментом не сводится к "покажите мне только аккумуляторные". На самом деле - это выбор из трех вариантов, только аккумуляторные, только сетевые, и мне все равно. Самое смешное, что зайдя в какой-нибудь соседний раздел вы имено такой набор из двух чекбоксов (или трех радио) и увидите. А почему тут иначе? А фиг его знает. Кто-то когда-то так решил - и все.

И это я еще на начал вспоминать о том, то бывают инструменты, умеющие работать как от сети, так и от аккумулятора. Скажем, из того что сразу пришло в голову - пылесос DeWALT DCV582.

Замечу так же, что если в основу разметки атрибутов положить что-то типа RDF, и некоторые атрибуты сделать URI, то можно было бы легко делать связи между товарами, скажем, принтером, и его расходниками, лобзиком и пилками для него, ну и так далее. Причем связи типизированные, не просто "см. также", а именно для этого инструмента подходят вот такие аккумуляторы.

В общем-то, такое решение это совсем не новость, его можно посмотреть, взглянув скажем на JIRA (я тут говорю не только про связи между страницами, но и про набор полей, и их вид). Ну то есть, в природе существуют продукты (правда, сделанные совсем для других целей), которые позволяют настраивать UI под себя, в зависимости от того, что именно мы показываем, и весьма гибко.

Выводы

Для начала, хочу отметить, что все что выше описано, не является проблемами, специфичными именно для Яндекс Маркета. Скажем, поиск Амазона в аналогичных ситуациях ведет себя ничуть не лучше, и знание Амазона о производителях тоже оставляет желать. Что с упомянутым e-katalog? Ну тут ситуация чуть другая, судя по всему (я вижу лишь то, что я вижу снаружи) тут за сайтом стоит именно и только пополняемый каким-то способом каталог моделей, поэтому части проблем либо нет, либо они иного сорта. Реально он меня больше устраивает в ряде специфических ситуаций, когда нужно найти не "что-то вроде вот этого", а "конкретно вот это, и если можно - подешевле". Но ассортимент, а в итоге объем и глубина каталога тут явно меньше, поэтому шансы найти что-то редкое вообще стремятся к нулю.

Понятно, что у меня нет готового решения. Это лишь предложения, основное из которых - отдать часть работы по поддержке каталога товаров сообществу, раз уж все равно поддержка того же Яндекс Маркета/Амазона с этой работой явно не справляется. Прекрасно представляю все сложности реализации такой идеи на готовом продукте. Но мне кажется, этот путь - чуть ли не единственно возможный путь реального наполнения интернет-каталога знаниями о реальных товарах.

Когда мы начали разрабатывать компонент Combobox для нашей библиотеки, мы столкнулись с вопросами, как правильно должен работать поиск:

1. Нужно ли выделять совпадения в выпадающем списке?

2. Совпадения должны быть по первым буквам или нет?

3. Если нет, нужно ли показывать выше то, что совпадает по первым буквам?

Мы стали смотреть, как ведет себя такой компонент в других дизайн-системах и в итоге решили разобраться, какие виды поиска бывают в интерфейсе.

Характеристики поиска

Место поиска

Поиск может находиться на странице, в модалке или в попапе.

Видим, по чему ищем

• сразу видим,

• не видим.

Начало поиска

1. По запросу поиск начнется только после нажатия на кнопку или Enter на клавиатуре.

2. На лету результат поиска обновляется с появлением каждого нового символа в поисковой строке.

Соответствие

1. Частичное означает, что в поле достаточно ввести несколько символов от желаемого запроса, и в результатах поиска будут все варианты, в которых есть эти символы.

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

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

Сортировка

1. Стандартная варианты в результате поиска сохраняют свою последовательность в сортировке.

2. По релевантности в этом случае сортировка меняется и выше показываются те варианты, которые наиболее близки к поисковому запросу.

Выделение совпадений

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

Комбинируем эти характеристики для разных кейсов в нашем интерфейсе

1. По странице

Место поиска: на странице

Видим, по чему ищем:сразу видим

Начало поиска:на лету

Соответствие:частичное

Сортировка:стандартная

Совпадения:без выделения

Используем, когда нужно найти что-то на конкретной странице сайта.

2. По всему сайту

Место поиска: в модалке

Видим, по чему ищем:не видим

Начало поиска:по запросу

Соответствие:частичное

Сортировка:по релевантности

Совпадения:с выделением

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

3. В справочнике по тексту

Место поиска: в попапе

Видим, по чему ищем:сразу видим / не видим

Начало поиска:на лету

Соответствие:частичное по первым символам

Сортировка:стандартная

Совпадения:с выделением

Используется в компонентах, например, в ComboBox. В нашей дизайн-системе выпадающий список является попапом, т.к. он не блокирует работу со страницей. Если значение в выпадающем списке состоит из нескольких слов, то проверяется на совпадение не только самое первое слово, проверка на совпадение идет через следующие разделители: пробел, точка, дефис. Пример: Urban Gorn; urban.gorn@mail.ru; Urban-Gorn. Во всех трех случаях поиск по слову "Gorn" сработает.

4. В справочнике по цифрам

Место поиска: в попапе

Видим, по чему ищем:сразу видим / не видим

Начало поиска:на лету

Соответствие:частичное

Сортировка:по релевантности

Совпадения:с выделением

Используется также в компонентах, разница лишь в том, что справочник должен состоять из числовых значений. Поэтому в данном случае соответствие частичное, потому что мы не знаем, как пользователь будет искать число - с начала, с конца или с середины.

Поиск фильтрация по названию

В нашем интерфейсе мы разделяем поиск и фильтрацию по названию. Поиском пользоваться проще, он понятнее, но с помощью фильтра можно решать более сложные задачи, например, искать через комбинации Содержит / Не содержит. В фильтре, в отличии от поиска, после ввода значения создается Chip, их может быть несколько и они могут дополнять друг друга.

На странице рекомендуется использовать что-то одно, в зависимости от того, какие задачи решает пользователь.

СпасибоСергею Токареву за помощь в подготовке материала.

Привет, Хабр!

В последнее время Яндекс изо всех сил пытается испортить свои мобильные приложения, превращая их в суперапп, будь это слово неладно. И одно из двух приложений компании, для которых такое направление развития наиболее заметно это такси.

Не так давно его переименовали в Яндекс Go, допихнув заодно внутрь Еду, Лавку, общественный транспорт, кучу рекламы. И здесь-то я вероломно, без объявления войны наткнулся на проблему, которая в конечном счёте послужила идеей для написания сией микростатьи.

У меня на iPhone довольно много разных приложений, и я привык запускать те, что не размещены на первой же странице, через системный поиск Spotlight тот, что на домашнем экране iOS. Беда в том, что с упомянутым переименованием Яндексовского приложения из его названия исчезло собственно главное ключевое слово такси. Найти Яндекс Go по нему теперь стало невозможно. Затрудняюсь предположить, насколько от этого могли пострадать статистика запусков или доходы приложения, но как минимум UX точно оказался в проигрыше, причём довольно глупом. К слову, точно так же вы не сможете найти такси Maxim по ключевому слову максим, а Delivery Club не ищется по запросу еда.

В то же время быстрый анализ проблемы показывает, что приложение VK нормально обнаруживается по запросу вконтакте, iOS предлагает запустить Инвестиции при вводе тинькофф, а Okko весьма уместно всплывает для ключевых слов кино, око и даже иви. Как же этого удалось добиться? На самом деле, очень просто...

Ключевые слова для Spotlight легко добавляются, если вы уже поддерживаете Handoff, то есть бесшовное переключение юзера между разными своими Apple-устройствами, или Siri Shortcuts. Достаточно лишь проставить свойство keywords для объекта NSUserActivity, с которым вы и так работаете.

let activity = NSUserActivity(activityType: typeID)activity.keywords = ["слово", "или даже ключевая фраза"]

Если же с Handoff и Siri вам по каким-то причинам не по пути либо хочется поддержать Spotlight на более серьёзном уровне, используйте CoreSpotlight.

import CoreSpotlightlet attributes = CSSearchableItemAttributeSet(contentType: .application)attributes.title = "Заказать пиццу"attributes.contentDescription = "Доставим в течение получаса"attributes.thumbnailData = image.pngData()attributes.keywords = ["еда", "закуски", "кушать"]let searchableItem = CSSearchableItem(uniqueIdentifier: "pizza", domainIdentifier: "readyMeal", attributeSet: attributes)CSSearchableIndex.default().indexSearchableItems([searchableItem]) { _ -> Void in }

Если всё сделали правильно, при вводе одного из переданных нами операционной системе ключевых слов получим примерно следующий результат...

Учитывайте, что чем больше ключевых слов вы скормите iOS, тем ниже она будет ранжировать ваше приложение, поэтому подбирать теги нужно аккуратно и с умом, стараясь обойтись минимально достаточным их набором.

Разумеется, хороший разработчик не просто скопирует приведённый выше код, а правильно обработает ошибки, заполнит дополнительные атрибуты и прокинет воспользовавшегося поиском юзера не просто в приложение, а непосредственно на экран заказа пиццы. Однако поскольку в Яндексе, видимо, не слышали даже о самом факте существования Spotlight, мы на сегодня пока закруглимся.

Спасибо за внимание!

Возможно у вас тоже есть друзья-нетехнари, которые терзают вас вопросами "где искать постоянную удаленную работу?" и "как попасть в айти?". У меня на этот случай есть заготовленный списочек ресурсов с вакансиями, который уже сэкономил мне много часов на таких вопросах. Хочу поделиться им с вами и попробую его обновлять, если Хабр позволяет обновлять публикации.

Тем, у кого уровень английского "London is the capital of Great Britain", я советую идти на всем известные российские ресурсы и искать там по фильтру "удаленная работа". А тем, чей уровень английского позволяет, кто хочет получать з/п в долларах и готов заморочиться с оформлением ИП или самозанятости, можно спокойно предлагать поискать иностранную компанию. Для технарей этот список тоже будет актуален.

Это, конечно, не исчерпывающий список, и будет круто, если вы дополните его в комментариях. Удачи в поиске!

• WeWorkRemotely
  Один из самых старых сайтов с удаленными вакансиями от создателей Basecamp
  Фильтры: Copywriting, Business & Management, Customer Support, Finance and Legal, Sales and Marketing

• AngleList
  Американские и канадские стартапы, здесь я нашла свою текущую работу
  Фильтры: Operations, Marketing, Sales, Management, Other

• F6s
  Европейские стартапы
  Фильтры: Operations, Marketing, Financial, Accounting

• Workable
  Сайт агрегатор, публикации напрямую от компаний

• NODESK
  Фильтр: "non-tech"

• Revolution Remote
  Только удаленные вакансии поддержки Support, Service, Helpdesk, Tech Support

• People-First Jobs
  Публикуют только вакансии от компаний, которые ценят своих сотрудников
  Фильтры: Business management, Copywriting, Customer success & support, Design, Finance & legal, Operations, Product, Project management, Sales & marketing, Others

• REMOTIVE
  фильтр: All Other

• RemoteOK
  Фильтр: Non-tech

• EU Remote Jobs
  Фильтры: Customer Support, Human Resources, Legal, Marketing, Sales

• Europe Remotely
  Фильтры: Marketing & Sales, Customer Support

• Workingтоmads
  Фильтры: Administration, Human Resources, Education, Legal, Sales, Writing, Sales filters

• Skip the Drive
  Фильтры: Administrative, Consulting, Editor, Entry Level, Human Resources

• Twitter
  Не самый очевидный ресурс, но именно в Твиттер дублируют вакансии как сами компании, так и сайты агрегаторы.
  Искать по "должность" или "скилл" + remote job

Фото: Jen Theodore on Unsplash