Более быстрый и умный Quick Switcher

Авторы Диоген Брито, Патрик Кейн, Джонни Роджерс и Кайл Стетц.

Начать разговор в Slack должно быть легко. И это должно быть быстро. Типа, очень быстро. Когда мы впервые выпустили Quick Switcher в начале 2014 года, мы стремились предоставить способ быстрого и легкого переключения на любой канал или прямое сообщение, которое вы хотите. Он был доступен с клавиатуры (просто нажмите ⌘ + k на Mac или ctrl + k в Windows и Linux), и он порадовал опытных пользователей.

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

Когда мы обратили внимание на решение этих проблем, перед нами стояли две ключевые цели. Новый Quick Switcher должен:

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

Имея это в виду, мы приступили к работе.

Представление

Мы проанализировали производительность Quick Switcher, чтобы выяснить, где мы проводим больше всего времени. Было три основных виновника:

Создание и отображение длинных списков
Неэффективное построение HTML
Никакой предварительной выборки данных и дорогостоящей сортировки

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

Для решения 2 мы создали шаблон нашего HTML и сократили количество элементов DOM для элементов контейнера и списка, упростив разметку и согласовав представление каждого типа.

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

По завершении мы могли регулярно открывать Quick Switcher в среднем за 7 миллисекунд и отображать результаты за 12 миллисекунд. Для сравнения: в исходной реализации для открытия требовалось 85 миллисекунд, а для визуализации результатов - 100 миллисекунд. Мы измеряем эти и множество других данных о производительности с помощью нашего настраиваемого кода времени на стороне клиента, который мы регистрируем в LogStash и визуализируем с помощью Kibana. Данные собираются по всем командам и размерам команд.

Частота: сортировка по частоте + давность

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

Сначала мы сформулировали общую проблему: «В нашей команде два Грэма, и я разговариваю только с одним из них, поэтому этот Грэм всегда должен стоять первым в списке». Идея «частости» - комбинации частоты и новизны - возникла как потенциальное решение. Насколько мы можем судить, термин «частота вращения» был придуман командой Mozilla в 2008 году, когда они выпустили Firefox 3 Awesome Bar, адресную строку для браузера, которая предлагала результаты на основе вашей истории просмотров. (1)

Получив запрос (например, «Мэтт») и список результатов, Frecency пытается ответить на вопрос «какого Мэтта вы имели в виду?» Он хранит историю того, какие запросы вы ввели и куда они вас привели, используя эту информацию для изменения порядка в списке.

Как это работает

Прежде чем мы сможем повторно отсортировать список, нам нужно записать хотя бы один успешный запрос и куда он пошел, что составляет основу нашей истории. Когда вы вводите «Сара» и выбираете Сару, которую искали, мы сохраняем запрос «Сара» с идентификатором выбранного вами объекта и отметкой времени, когда вы туда пришли. Мы храним до десяти отметок времени, представляющих последние десять посещений. Мы также сохраняем счетчик, который увеличиваем каждый раз, когда записываем попадание.

Теперь у нас есть данные для работы! В следующий раз, когда вы откроете Быстрый переключатель и начнете вводить текст (например, «Сар»), мы примем ваш ввод и выполним поиск по нему. Мы возвращаем некоторые результаты - объективные результаты прямо из нашего алгоритма поиска по умолчанию - и передаем этот список в Frecency вместе с вводимым вами запросом. Мы просматриваем объект истории посещений в поисках запроса, соответствующего «Sar», и записываем все совпадения, которые мы находим. Затем мы просматриваем исходный список и подсчитываем балл для каждого элемента, который равен нулю, если мы не нашли попадание, указывающее на рассматриваемый элемент.

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

Вот что у нас получилось:

Within the past 4 hours: 100 points
Within the past day: 80 points
Within the past 3 days: 60 points
Within the past week: 40 points
Within the past month: 20 points
Within the past 90 days: 10 points
Beyond 90 days: 0 points

Для иллюстрации предположим, что наш запрос «Сара» был записан три раза: только сейчас, вчера и примерно неделю назад.

Just now: +100
Yesterday: +80
About a week ago: +40

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

Final score = Total Count * Score / Number of Timestamps recorded (up to 10)

Этот обманчиво простой расчет описывает тонкий баланс между недавними обращениями (оценка / количество меток времени, которое не может превышать 100) и безграничным общим счетом, который способствует тому, что вы много использовали в течение более длительных периодов времени. Больше всего нас волнует то, что если вы решите начать регулярно болтать с другим Мэттом, этот результат будет выше предыдущего лидера уже после нескольких использований!

Дальнейшее развитие

Хотя эта реализация дала нам 90% пути, она оставила нам неприятный крайний случай. Если я буду разговаривать с Ферлой Хаски на регулярной основе, набрав «Ферла» в Quick Switcher, она наберет высокий балл и появится первой в списке результатов. Однако, если я наберу «Хаски», она может оказаться в самом конце списка. Все, что мы научили Quick Switcher, - это то, что существует связь между запросом «Ферла» и пользователем Ферла Хаски, поэтому запрос «Хаски» представляет собой отдельный сценарий без записанной истории.

Мы исправили это, сохранив как запрос «Ферла», так и идентификатор Ферлы в нашем кэше истории. Когда мы присваиваем баллы каждому элементу, ID Ферлы получает половину обычной оценки и добавляется к оценке запроса в качестве бонуса. Это означает, что Ferla Husky будет занимать более высокое место в поисковом запросе «Хаски», но его не будет достаточно, чтобы переопределить ваш обычный запрос «Хаски». Аккуратный. (2)

Вот более реалистичное представление нашего кеша с учетом повторного использования запросов:

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

Умный поиск

Прежде чем переходить к частым занятиям, быстрому переключателю необходимо выяснить, какие каналы и участники соответствуют тому, что вы набрали. Он использует несколько эвристик, которые хорошо послужили нам с тех пор, как был впервые представлен Quick Switcher. Например, в названиях каналов для разделения слов часто используются дефисы или подчеркивания. Быстрый переключатель будет сопоставлять любую из этих подстрок, предпочитая совпадения, которые начинаются с начала, для целей сортировки. Вы также можете полностью опустить разделитель в своем запросе.

Чтобы улучшить эти простые правила, новый Quick Switcher теперь позволяет вам комбинировать и переупорядочивать эти подстроки в ваших запросах. Например, «devweb» теперь соответствует «# devel-webapp». Вам не нужно запоминать, будет ли это «# design-team» или «# team-design»: «design team» будет соответствовать оба. При вводе чьих-либо инициалов они также будут найдены, поэтому «dh» вернет «Duretti Hirpa» (если вам повезло, что она в вашей команде).

Эти умные правила сопоставления было бы трудно реализовать с помощью того же подхода на основе регулярных выражений, что и в старом Quick Switcher, поэтому запросы теперь моделируются как поиск по графу. Каждая буква в имени канала или элемента является узлом в графе с взвешенными ребрами до следующей буквы и до начала других подстрок. Ребра, которые переходят на другие подстроки, имеют больший вес, чем ребра между соседними узлами. Затем мы ищем путь через граф, используя буквы в запросе. Веса ребер суммируются и используются для сортировки. Такой подход дает нам много возможностей для настройки «размытости» быстрого переключателя с течением времени.

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

Немного лучше с каждым днем

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

1) Алгоритм Mozilla задокументирован на MDN.

2) Мы слушали, Рам.

Хотите помочь Slack решить сложные проблемы и присоединиться к нашей растущей команде? Ознакомьтесь со всеми нашими инженерными работами и подайте заявку сегодня.

Более быстрый и умный Quick Switcher