Автор: Цзяминчен,Команда разработчиков терминала WeChatчлен
Эта статья была впервые опубликована в сентябрьском выпуске журнала Programmer Magazine за 2017 год.
предисловие
Полнотекстовый поиск (FTS) на основе локальных данных играет важную роль в мобильных приложениях. В отличие от службы поиска, основанной на сервере, мобильный терминал ограничен аппаратными условиями, особенно в случае относительно большого объема данных проблема производительности поиска очень заметна. Взяв в качестве примера расширение SQLite FTS, широко используемое на мобильных платформах, в этой статье представлены основные принципы FTS на мобильных платформах.В сочетании с практикой клиента WeChat для Android она фокусируется на некотором опыте оптимизации производительности WeChat на FTS.
SQLite FTS Extension
Расширение SQLite FTS - это плагин, разработанный SQLite для полнотекстового поиска. Он встроен в стандартное распределение SQLite. Он имеет следующие характеристики:
Быстрый поиск:Используйте инвертированный индекс, чтобы ускорить процесс поиска
Хорошая стабильность:В настоящее время стабильность SQLite на мобильном терминале относительно хорошая, расширение FTS построено на базе SQLite.
Легкий доступ:Платформы Android и iOS сами поддерживают SQLITE, а использование расширения FTS такое же, как и при обычном использовании таблицы SQLite.
Хорошая совместимость:Благодаря хорошей совместимости самого SQLite, расширение SQLite FTS также имеет хорошую совместимость.
В настоящее время SQLiteFTSExtension выпустил 5 версий, и я кратко упомяну следующие три основные версии.
ФТС3:Базовая версия имеет полные функции FTS, поддерживает пользовательские токенизаторы, а библиотечные функции включают смещения и фрагменты.
ФТС4:На основе FTS3 значительно оптимизирована производительность, а также добавлена функция корреляции для расчета MatchInfo.
ФТС5:Существуют значительные изменения по сравнению с FTS4, и формат хранения был значительно улучшен.Наиболее очевидным является сегментированное хранилище Instance-List, которое может поддерживать хранение большего Instance-List, и открытый ExtensionApi для поддержки пользовательских вспомогательных функций. FTS5 был выпущен в середине 2015 года.
архитектура хранения
Полнотекстовый поиск WeChat был запущен в конце 2014 года и изначально обслуживал в основном бизнес-поиск контактов и записей чатов. В начале разработки схемы, чтобы сделать эту функцию удобной, и принимая во внимание увеличение количества услуг доступа в будущем, мы поставили перед собой следующие цели:
1. Высокая скорость поиска
Полнотекстовый поиск WeChat использует расширение SQLite FTS4 для повышения скорости поиска за счет инвертированного индекса.
2. Независимость бизнеса
Основным бизнесом WeChat являются контакты и сообщения, а полнотекстовый поиск WeChat должен обрабатывать большой объем данных при создании индекса, обновлении индекса или удалении индекса, чтобы полнотекстовый поиск не влиял на ядро бизнес WeChat, принята следующая архитектура хранения:
Независимая БД, разделение чтения-записи:Полнотекстовый поиск WeChat не зависит от основного бизнеса в общей структуре, а поисковая БД также независима от основного бизнес-БД; когда основные бизнес-данные обновляются, основной бизнес уведомляет о поиске соответствующий модуль обработки бизнес-данных через EventBus , и модуль обработки бизнес-данных будет передавать независимое соединение с базой данных только для чтения, которое напрямую обращается к основной бизнес-базе данных и не использует соединение с базой данных основного уровня бизнес-хранилища.
Сокращение операций с базой данных:В модуле поиска будет модуль, предназначенный для обработки бизнес-данных, а также для специальной обработки некоторых сложных структур данных. Например, для группового чата с 500 участниками, если 500 участников группы будут вставлены в базу данных поиска поэтапно, это вызовет слишком много операций с базой данных. Поэтому WeChat объединит всех членов группы в одну строку и вставит ее в базу данных поиска.
Отложенное обновление горячих данных:Для горячих данных с очень высокой частотой обновления принимаются стратегия задержки обновления. Все данные индекса разделены на нормальные данные и грязные данные. Когда данные обновляются, соответствующие данные маркируются как грязные данные, а затем есть таймер для обновления данных в указатель каждые 10 минут.
3. Высокая масштабируемость
Высокая масштабируемость требует разделения структуры таблицы поиска и бизнеса. Все примеры на официальном сайте SQLite FTS представлены в виде одной индексной таблицы.Каждый столбец соответствует определенному атрибуту бизнеса.При изменении соответствующего бизнеса необходимо изменить структуру индексной таблицы. Чтобы решить проблему изменения структуры таблицы, вызванную изменениями в бизнесе, WeChat оцифровывает бизнес-атрибуты и разрабатывает следующую структуру таблицы:
IndexTable отвечает за построение индекса полнотекстового поиска, к логике отношения не имеет, при поиске по ключевым словам нужно только найти соответствующий DocId. MetaTable отвечает за фильтрацию бизнес-логики, фильтрацию данных соответствующего бизнеса по типу и подтипу и, наконец, выводит BusItemId.
поисковая оптимизация
Полнотекстовый поиск WeChat был запущен в версии 5.4 26 января 2014 года. К версии 6.5.7 после Весеннего фестиваля в 2017 году общее количество пользователей увеличилось с 400 миллионов до 900 миллионов, а также увеличилось количество активных пользователей. Объем данных локального поиска WeChat также значительно увеличился, что привело к постоянному снижению скорости поиска и увеличению количества жалоб пользователей. Согласно нашей статистике, с версии WeChat 5.4 до 6.5.7 среднее время поиска каждой задачи в полнотекстовом поиске WeChat увеличилось более чем в 10 раз, что создает большие проблемы для полнотекстового поиска WeChat.
Для того, чтобы оптимизировать время поиска, сначала посмотрите на блок-схему поиска:
Из-за затрат времени на каждом этапе установлено, что на этапе поиска данных доля времени достигает более 80%, и чем больше объем данных в наборе результатов поиска, тем выше доля времени, и максимальная может достигать 95%. Этап выборки данных представляет собой циклический процесс, поэтому оптимизация цикла должна начинаться с двух аспектов: сокращения времени, затрачиваемого на один цикл, и уменьшения общего количества циклов.
Сокращение времени, затрачиваемого на выполнение одного цикла
Углубляясь в исходный код SQLite FTS4 Extension, обнаруживается, что библиотечная функция FTS4 Offsets занимает более 70% времени, затрачиваемого на выполнение одного цикла, и чем больше объем данных, тем больше времени это занимает.
Библиотечная функция FTS4 Смещения:Он используется для преобразования смещений слов в смещения байтов.В WeChat байты используются для сортировки и выделения результатов.
Вход функции:
Запрос: Ключевое слово, которое ищет пользователь
Hit Doc: документ, в который попало ключевое слово. Документ — это основная единица полнотекстового поиска, которая может быть веб-страницей, статьей или записью чата.
Смещение целевого слова: на этапе поиска смещение целевого слова можно получить путем поиска в индексе поиска по ключевым словам.
Выход функции:
- Целевое смещение в байтах: указывает смещение в байтах ключевого слова в хит-документе.
Например:
Query= яХит Док= Я ходил по магазинам с братомсмещение целевого слова =0, 2
После прохождения хитового Doc через токенизатор можно получить следующую таблицу:
Окончательный расчет может получить смещение целевого байта = 0, 6
На следующем рисунке показана зависимость между числом байтов попаданий Doc и временем, затраченным функцией Offsets:
Обработка функции Offsets включает сегментацию слов, поэтому первым шагом является оптимизация токенизатора.
Для оптимизации токенизатора главным приоритетом являются правила сегментации слов.Правила сегментации слов WeChatКомбинируйте слова для английского языка и цифры, отдельные слова для неанглийского языка и цифры. Например, для псевдонима «Hello520 China» результатами сегментации слов являются «Hello», «520», «中», «国». Причина этого правила сегментации слов заключается в том, что требования WeChat к сортировке результатов полнотекстового поиска в основном основаны на сортировке по другим атрибутам, а не на релевантности документов. То есть часть полнотекстового поиска должна находить только документы с ключевыми словами, и ее не волнует, сколько ключевых слов существует в документах. Более того, в большинстве случаев входной запрос пользователя не может состоять из слов, а существуют диалекты, поэтому в соответствии с требованиями разобрать все слова для создания индекса.
Полнотекстовый поиск WeChat был впервые разработан в конце 2013 г. FTS4 — это высшая версия SQLite FTS Extension, но токенизатор, поставляемый с FTS4, не очень хорошо поддерживает китайский язык, поэтому можно использовать только токенизатор ICU. доступ к токенизатору ICU был относительно простым, китайская поддержка лучше, поэтому используется токенизатор ICU.
Для выходного токенизатора псевдонима «Hello520 China» он начинается с кодировки UTF8, и токенизатор один раз преобразует его в кодировку Unicode, затем просматривает словарь и, наконец, выполняет постобработку, чтобы получить результат сегментации слова. Из ввода и вывода видно, что два шага преобразования кодировки и поиска в словаре на самом деле избыточны, поэтому WeChat отказался от токенизатора ICU и настроил токенизатор Simple.
Содержимое документа в кодировке UTF8, непосредственно обработанное простой сегментацией слов с помощью одного символа, определяет диапазон кодирования Unicode и длину кодирования Unicode текущего символа и выполняет различную обработку в зависимости от различных ситуаций.
После оптимизации токенизатора время, необходимое функцией смещения для обработки 100 000 байтов, уменьшается до 21М, но такая оптимизация недостаточно. При обработке более 10 докторов результатов 10 Вт он все еще превышает 200 мс, так что есть следующий оптимизация.,
Из-за ограничений экрана на мобильном терминале при окончательном отображении результатов поиска часто выделяется лишь небольшое количество найденных ключевых слов, а функция «Смещения» вычисляет смещение всех целевых слов в документе совпадений, поэтому «Смещения» функция должна быть изменена.
Сначала я пытался изменить исходный код функции Offsets напрямую. Я обнаружил, что инкапсуляция API FTS4 сложна в использовании, а функция Offsets имеет много зависимостей. Модифицированный код было трудно поддерживать, а читабельность была плохой, поэтому мне нужно было найти новые методы оптимизации. После некоторых исследований я обнаружил, что FTS5 поддерживает пользовательские вспомогательные функции и имеет лучшую инкапсуляцию API, поэтому я, наконец, использовал пользовательскую вспомогательную функцию FTS5 (MMHighLight) для повторной реализации функции функции Offsets и добавил логику оптимизации.
войти:Query= яХит Док= Я ходил по магазинам с братомсмещение целевого слова =0, 2количество возвращенных целей=1
Токенизатор вызывается обратно шаг за шагом.Когда токенизатор возвращает «I» в первый раз, он соответствует первому 0 смещения целевого слова, а целевой возвращаемый номер в это время равен 1, и функция напрямую возвращает цель смещение байта = 0 .
Уменьшить общее количество циклов
Чтобы уменьшить общее количество циклов на этапе выборки данных, проще думать о подкачке и возврате данных на уровне SQL.Сортировка по слоям БД, определяющим фактором для сортировки на уровне БД является фактор сортировки. Однако полнотекстовый поиск WeChat сталкивается со многими и сложными факторами бизнес-сортировки и не может напрямую использовать ORDER BY в SQL, поэтому ему необходимо пройтиПреобразование промежуточной функции, отразить все факторы сортировки через сопоставимое число и, наконец, использовать ORDER BY для сортировки.
Вот краткое описание, более сложные факторы сортировки следующие:
Сортировать по временному сегменту: Диапазон времени находится в пределах полугода, коэффициент сортировки зависит от фактора сортировки следующего уровня, а диапазон времени находится за пределами полугода, в зависимости от расстояния во времени.
упорядочение результатов функции: Коэффициент сортировки является результатом вычисления функции, а не прямого столбца базы данных, и результат вычисления функции не может напрямую использовать ORDER BY, например, число в виде строки.
Благодаря приведенному выше анализу основной целью сокращения общего количества циклов является перенос сортировки уровня Java на уровень SQL.Преимущества заключаются в следующем:
Уменьшить ввод-вывод
Сокращение копирования данных с уровня C на уровень Java
Поэтому ключевым моментом реализации здесь является реализация функции промежуточного преобразования, функция промежуточного преобразования WeChat, MMRank, реализуется через вспомогательную функцию FTS5.
Принцип реализации MMRank заключается в преобразовании всех факторов сортировки в 64-битное длинное значение, фактор сортировки с высоким приоритетом устанавливается в высокое положение, а фактор сортировки с низким приоритетом устанавливается в нижнее положение. Окончательный SQL выглядит следующим образом:
Специальная оптимизация - оптимизация поиска истории чата
Микроканальный полный текстовый поиск в более конкретной поисковой задаче - это общаться.
как показано на рисунке:
Число в красном кружке на рисунке представляет собой количество записей чата, содержащих ключевое слово «я» в этом разговоре, а правилом упорядочения разговора является активное время разговора.
Поиск истории чата WeChat имеет следующие две характеристики:
Имеет статистические свойства
Это число очень велико (по одному ключевому слову может достигать 200 000).
Из схемы поиска видно, что первоначальное решение, принятое WeChat, заключается в подсчете и сортировке на уровне Java, что нежелательно в случае больших данных. Ввиду предыдущего анализа, что уменьшение количества циклов может быть возвращено путем подкачки, основной момент заключается в переносе сортировки с уровня Java на уровень SQL, поэтому существует схема оптимизации 1.
Решение по оптимизации 1. Сгруппировать по
SQL для достижения следующего:
Это решение напрямую подсчитывает количество обращений к чату на уровне SQL через Group By и сортирует их в соответствии с самым последним временем, но оно также имеет очевидные недостатки:
Нельзя использовать ускорение индекса: когда GroupBy и OrderBy используются одновременно, OrderBy должен содержать поля GroupBy для попадания в индекс, поскольку использование GroupBy приведет к созданию промежуточных подтаблиц.
Полный расчет: GroupBy подсчитывает количество записей чата с обращениями на уровне SQL для подсчета всех сеансов.На приведенном выше рисунке необходимо подсчитать только 3 сеанса, что тратит много ресурсов.
Схема оптимизации 2: пошаговый расчет
Ввиду проблемы полного расчета схемы 1 принят пошаговый метод расчета.
Первый шаг: найти ближайший активной в трех сессиях
Получите сеансы conv1, conv2, conv3, а затем выполните следующий SQL, вы можете получить количество обращений для трех сеансов соответственно.
Однако с этим методом также возникают проблемы, и необходимо выполнить несколько SQL-запросов.
Третий план оптимизации: MessageCount
Ввиду проблемы, заключающейся в том, что для схемы 2 требуется несколько фрагментов SQL, одноразовую статистику можно получить с помощью пользовательских функций агрегирования. Этапы выполнения следующие:
Шаг 1. Найдите 3 последних активных сеанса
Получите сеансы conv1, conv2, conv3, затем выполните следующий SQL
Вы можете получить количество обращений сразу за три сеанса.
наконец
После оптимизации среднее время каждой задачи полнотекстового поиска WeChat составляет менее 50 мс, при этом среднее время поиска каждой задачи активных пользователей составляет менее 200 мс, а среднее время оптимизации составляет более 5 раз.
Есть еще много областей, которые стоит оптимизировать в будущем.Например, при вычислении выделения, если смещение в байтах добавляется непосредственно в структуру данных DocList, это также может сэкономить некоторое время.
Наконец, я надеюсь, что мой обмен может быть полезен для всех, добро пожаловать, чтобы оставить сообщение для обмена.
Связанное Чтение
Микробуквы "15 ........." входы и выходы
Применение Tencent на обслуживание, так что уровень заболеваемости в стране SMS-мошенничества упал на 74% ...
WeChat OCR (2): глубокое последовательное обучение помогает распознавать текст
Эта статья была разрешена автором для публикации в сообществе Tencent Cloud Technology Community, укажите это при перепечатке.Источник статьи
Исходная ссылка: https://cloud.tencent.com/community/article/381004