Примечание: ниже находится перевод заметки "Building a Fast People-Finder for Flickr with YUI AutoComplete", в которой рассказывается о методах построения быстрого автозаполнения для большой неоднородной базы данных. Мои комментарии далее курсивом.
Не так давно мы добавили на Flickr новый модуль поиска по людям, основанный на разработке YUI AutoComplete. Этот модуль позволяет зарегистрированным участникам искать отдельных людей по их списку контактов, в котором может быть до 20000 записей. В связи с большим объемом обрабатываемых данных классические методы извлечения и подготовки данных были не применимы из-за слишком большого времени обработки. В этой заметке мы рассмотрим некоторые альтернативные типы представления данных, которые были протестированы в поисках оптимального решения, и конфигурацию AutoComplete, которая оказалась наиболее быстрой в данном случае.
Для начала приведем видео-ролик, в котором показывается процесс поиска людей из контактного листа. Новый вариант модуля расположен справа:
Самой большой проблемой, с которой мы столкнулись, было найти подходящий формат передачи данных, который можно было бы как быстро загружать, так и быстро обрабатывать. И, кроме всего прочего, он еще обладал бы должной степенью безопасности (по моему мнению, здесь достаточно шифровать все данные — например, ссылки — сессионным ключом, объем данных или сложность обработки при этом не увеличивается). Сначала мы пробовали применить XML и Ajax, но разбор XML-документа осуществляется в браузерах слишком медленно: мы обнаружили, что на больших объемах данных это «вешает» браузер. Следующим по списку была комбинация JSON и Ajax; это оказалось существенно быстрее, но по-прежнему уходило 80 секунд для того, чтобы разобрать самый большой из возможных объемов данных (массив из 10700 объектов, каждый со своими собственными свойствами).
В конце концов, мы остановились на двух методах передачи и обработки информации, которые, по всей видимости, были достаточно быстрыми, чтобы их использовать:
script, создаваемых «на лету»;split(), данные приходят от Ajax-вызовов (используется YUI Connection Manager).После некоторого тестирования мы выбрали второй вариант (собственный формат передачи данных). Преобразование JSON в код скрипта, который мог быть динамически выполнен, было менее безопасно и прогрывало по производительности. При этом XHR позволял обеспечить более высокий уровень защищенности данных и хорошую производительность.
После того как мы разобрались с быстрым получением данных внутрь JavaScript, следующей проблемой был быстрый поиск внутри полученного списка контактов. Для ее преодоления мы обратились к разработке YUI AutoComplete. Это было как раз то, что нужно: исключительно быстрая и с большим количеством настроек. При использовании для разбора нашего массива данных мы создали свою собственную функцию вместо текущего экземпляра AutoComplete DataSource; каждое нажатие клавиши вызывало эту функцию осуществляло поиск по заданной строке. Внутри функции поиска мы пробегались по всем пользовательским контактам и пробовали найти соответствие запросу среди четырех различных полей. Для поиска соответствия между строками мы использовали регулярные выражения.
Даже при больших объемах данных этот метод отлично зарекомендовал себя. Ниже приведена базовая версия нашего скрипта:
function searchContacts(query) {
var matches = [],
queryRegEx = new RegExp(query, 'i'), // надо сначала проверить запрос
// перед его использованием
contact;
for (var n = 0, len = contacts.length; n < len; n++) {
contact = contacts[n];
if (contact.username.search(queryRegEx) !== -1 ||
contact.realname.search(queryRegEx) !== -1 ||
contact.emailAddress.search(queryRegEx) !== -1 ||
contact.alias.search(queryRegEx) !== -1) {
matches.push(contact);
}
}
return matches;
}(Тут сразу стоит отметить, что использование while, indexOf и более быстрого заполнения массивов (через ind++) позволило бы значительно ускорить и без того быструю технологию.)
Как только мы разобрались с получением данных внутри нашего модуля, мы сделали одно изменение в стандартной конфигурации AutoComplete: установили параметр queryDelay в 0 (по умолчанию это 200мс). Таким образом мы уменьшили задержку между нажатием клавиши и запуском поисковой функции. Естественно, у данного подхода есть и свои минусы: окно AutoComplete будет мигать, если вы слишком часто будете вводить символы, — но ля нас это оказалось наиболее существенным улучшением, превосходя даже все танцы с бубном вокруг функции поиска. Хотя queryDelay в 200мс (или более) лучше подходит для получения данных при помощи XHR или из других внешних источников, для нас использование DataSource, основанного на регулярных выражениях, сделало возможным поиск по произвольной строке ввода. AutoComplete кэширует результаты, поэтому мы получили выполнение любого поискового запроса не более одного раза.
Более детально описанные методы, включая все подробности о различных форматах данных и их профилировании, приведены в нашем блоге — code.flickr.