Як робився сервіс пошукових підказок на prom.ua

На prom.ua є сервіс, що пропонує підказки в міру введення тексту в рядок пошуку:

Кілька фактів про нього:

повнотекстовий пошук підказок здійснюється серед мільйона фраз;
індекс з мільйона фраз займає менш 100Мб оперативної пам'яті;
всі запити до сервісу, що йдуть з prom.ua , обслуговуються по черзі одним процесом в одному потоці;
сервіс написаний на Python.

Історія розвитку сервісу

Спочатку підказки зберігалися в таблиці БД (MongoDB ), проіндексованої за фразами, приведеним до канонічного виду. Під канонічним виглядом розуміється фраза в нижньому регістрі з віддаленими знаками пунктуації і без зайвих пробілів. Щоб показати підказки до введеного користувачем запит, цей запит наводився до канонічного виду, а потім виконувався запит до MongoDB, який можна представити у вигляді SQL:

SELECT suggestion
FROM search_suggestions
WHERE text_canonical LIKE 'search_query_canonical%'
ORDER BY weight DESC
LIMIT N

Таким чином, вибірка робилася тільки по початку пошукової фрази і виводилися перші N підказок c максимальною вагою. У цієї реалізації було дві проблеми:

Запит до БД міг гальмувати, якщо під фільтр text_canonical LIKE 'search_query_canonical%' потрапляло занадто багато фраз, які потрібно було впорядкувати за вагою і тільки потім вибрати перші N з них. Т.к. ця ж MongoDB використовувалася іншими сервісами, то у цих сервісів могли початися проблеми, якщо хтось вирішував заDoSіть сервіс пошукових підказок.
Пошук підказок проводився строго за повного збігу з початком пошукового запиту. Наприклад, за запитом «плаття» виводилися підказки «Платье жіноче», «плаття літній», але не виводилися підказки «жіноче плаття», «ніж червоне плаття краще білого?». За запитом «s4 gala» виводилися підказки «s4 Galaxy», «S4 GALAXY крутіше iphone5», але не виводилися підказки «samsung galaxy s4200», «s4 Samsung galaxy - копія s3?».

Одного разу було вирішено переписати сервіс пошукових підказок, щоб він задовольняв наступним умовам:

Повинен бути повністю автономним. Тобто не повинен залежати від зовнішніх сервісів типу БД, а також не повинен впливати на роботу інших сервісів.
Повинен шукати за збігом окремих слів пошукової фрази в будь-якому місці підказки, щоб за запитом «бетон оренда» перебували не тільки «бетон оренда дешево», а й «оренда бетономішалок», «бетононасос оренда», «оренда міксера з бетононасосом в Одесі ». Надалі будемо називати це повнотекстових пошуком по префіксам .
По можливості повинен повертати знайдені підказки з максимальною вагою. Тобто якщо за запитом «перфоратор» знайдено 100500 підказок, то потрібно повернути тільки N з них з максимальною вагою.
Повинен працювати швидше старого сервісу.
Повинен підтримувати пошук серед декількох мільйонів підказок.
Повинен підтримувати періодичне оновлення бази пошукових підказок.

Дивно, але було вирішено писати цей сервіс на Python. Щоб був супер-швидкісним :) Насправді, щоб всі наші програмісти, які знають python , могли швидко розібратися в коді цього сервісу. До того ж, розробка з нуля аналогічного сервісу на якому-небудь C зайняла б у кілька разів більше часу.

Т.к. до сервісу йдуть AJAX-запити, він повинен підтримувати http і робити це з мінімальними накладними витратами. Тому було вирішено використовувати перевірений часом gevent , який вже успішно використовувався в інших сервісах prom.ua .

Технічні деталі реалізації

Як зробити повнотекстовий пошук по префіксам? Правильно - за допомогою злегка модифікованого інвертованого індексу . Ось класичний алгоритм. Кожна фраза, серед яких здійснюється пошук, розбивається на окремі слова (токени). Для кожного токену створюється список фраз, що містять цей токен. Тепер, щоб знайти фрази, що містять заданий набір слів, достатньо знайти перетин списків для цих слів. Ось псевдокод на Python:

def get_suggestions (search_query):
    return frozenset.intersection (* (
        get_suggestions_for_token (token)
        for token in token_split (search_query)
    ))

Це алгоритм повнотекстового пошуку за точним збігом слів. Тобто за запитом «шило» будуть знайдені всі фрази з цим словом, але не буде знайдено фрази, що містять префікси цього слова - «прилад Шилова» або «шиловидний флокс». Для того, щоб можна було знаходити фрази по префіксам, потрібно для кожного слова з пошукового запиту знайти всі токени, що починаються з цього слова, після чого об'єднати пов'язані з цими токенами списки фраз. Потім потрібно знайти перетин одержані списків по кожному слову з пошукової фрази. Псевдокод на Python:

def get_suggestions_for_prefix (prefix):
    return frozenset.union (* (
        get_suggestions_for_token (token)
        for token in get_tokens_with_prefix (prefix)
    ))
def get_suggestions (search_query):
    return frozenset.intersection (* (
        get_suggestions_for_prefix (prefix)
        for prefix in token_split (search_query)
    ))

Перший робочий прототип класу, що реалізовує повнотекстовий пошук по префіксам, був написаний за півдня і займав близько 100 рядків коду на Python. Потім почалася робота з оптимізації споживання пам'яті і швидкості роботи, по захисту від DoS-атак і поліпшенню якості видачі.

Перше, що потрібно було виправляти - підвищене споживання пам'яті. Для побудови індексу по мільйону фраз було потрібно 3Гб пам'яті, а потрібно було вкластися хоча б в 500Мб. Спочатку список фраз для кожного токену був замінений списком індексів цих фраз в глобальному списку фраз під назвою keywords :

# якщо раніше get_suggestions_for_token ("foobar")
# Повертав frozenset (("foobar", "bar fooBar")),
# То тепер повертає frozenset ((+9000,100500)),
# Де 9000 і 100500 - індекси фраз "foobar" і "bar booBar"
# У глобальному списку фраз keywords.

Потім keywords був перетворений в один великий bytearray , де фрази відділялися один від одного за допомогою спеціального символу-роздільника. Псевдокод формування keywords :

def get_keywords_bytearray (keywords_list):
    keywords = bytearray ()
    for keyword in keywords_list:
        keywords.extend (keyword)
        keywords.extend (KEYWORDS_DELIMITER)
    return keywords

Потім списки індексів фраз були замінені списками зміщень в keywords , закодіровнних в бінарну рядок за допомогою struct.pack () . Тепер кожне зміщення займало рівно 4 байта. Потім списки зміщень для всіх токенів були об'єднані в один великий bytearray під назвою offsets . Потім відсортований за алфавітом список пар (токен, зміщення у offsets) був замінений на все той же bytearray під назвою tokens . У результаті ми отримали три великих bytearray'я:

keywords - список фраз, за ??якими проводиться повнотекстовий пошук.
offsets - список, що містить список зсувів у keywords для кожного токену.
tokens - відсортований за алфавітом список пар (токен, зміщення у offsets ).

Тепер індекс для мільйона пошукових фраз став займати менше 100Мб. Але для перестроюванні індексу все ще було потрібно 1Гб пам'яті - стільки займав список пар (токен, зміщення у keywords) для мільйона фраз, з якого потім будувався стиснений індекс. Була зроблена спроба покласти цей список у bytearray, зберігаючи зміщення кожної пари в array ('L') . Але це не дало істотного виграшу в споживанні пам'яті. Тому було вирішено розбити список фраз на підсписки меншої довжини - Шарден - і будувати індекс по кожному Шарден. Це трохи ускладнило індексацію і алгоритм пошуку, але дозволило знизити максимальне споживання пам'яті при побудові індексу. Наприклад, на Шарден розміром 500К фраз споживання пам'яті не виходило за межі 400Мб при побудові індексу для мільйона фраз. На цьому етапі оптимізація по споживанню пам'яті була закінчена і почалася оптимізація по швидкості.

Спершу розібралися з гальмами при пошуку часто зустрічаються префіксів (наприклад «про» чи «купити»). Такому запитом задовольняє приблизно 100500 фраз, з яких потрібно вибрати N з найбільшою вагою. Очевидно, що кожного разу вибирати і сортувати всі ці фрази за вагою було б дуже накладно. Тому список фраз для кожного токену заздалегідь сортувалося за вагою під час побудови індексу, а при пошуку вибиралися перші N фраз з цього списку. Постало питання - як вибирати фрази з найбільшою вагою, якщо кілька токенів починається з заданого префікса (наприклад, токени «проект» і «продати» для префікса «про»)? Спробували використовувати алгоритм об'єднання сортованих списків на основі heapq.merge () , щоб вибрати N фраз з найбільшою вагою. Але це виявилося занадто повільним при великій кількості токенів з заданим префіксом, тому було вирішено «схалтурити» і видавати поспіль перші зустрілися N фраз, які містять заданий префікс.

Далі потрібно було вирішити питання зі швидкістю пошуку по пошукових запитах, що містить кілька слів. Потрібно було знаходити перетин списків фраз, які містять кожне слово. Як вже відомо, такі списки могли виявитися занадто великими. Тому з метою оптимізації було вирішено знову «схалтурити» і вибирати не більше заданої кількості фраз (Nmax ) для кожного префікса перед тим, як знаходити їх перетин. Це погіршило якість підказок для пошукових запитів, які з кількох слів. Тому, щоб трохи згладити провину, в алгоритм пошуку були внесені зміни - якщо хоча б один зі списків містить менше, ніж Nmax фраз, то замість того, щоб знаходити перетин списків, сканувалися всі фрази з списку, що містить мінімальна кількість фраз, на предмет вмісту всіх слів з пошукового запиту.

Продуктивність і споживання пам'яті

Ось лог тестування швидкості пошуку серед мільйона фраз в інтерактивному режимі за допомогою ipython на моєму ноут:

$ ipython-i suggester.py
In [1]: s = Suggester ()
In [2]: s.update_keywords (
   ...: ('Keyword% d'% i, 'payload% d'% i)
   ...: For i in range (1000000)
   ...:)
In [3]: def bench_suggester (suggester, query, n):
   ...: Import time
   ...: Start_time = time.time ()
   ...: For i in range (n):
   ...: Suggester.suggest_keywords (query)
   ...: Print '% .0 f ops/s'% (
   ...: N/(time.time () - start_time)
   ...:)
   ...:
In [4]: ??bench_suggester (s, u'foobar ', 10000)
10009 ops/s
In [5]: bench_suggester (s, u'1234 ', 10000)
4654 ops/s
In [6]: bench_suggester (s, u'key ', 10000)
4702 ops/s
In [7]: bench_suggester (s, u'key 1234 ', 10000)
1077 ops/s
In [8]: bench_suggester (s, u'zkey 1234 ', 10000)
1226 ops/s
In [9]: bench_suggester (s, u'zkey z1234 ', 10000)
6416 ops/s

Навантажувальне тестування показало, що один сервіс пошукових підказок, що працює в одному потоці на одному процесорі, справляється з навантаженням у 2000 типових запитів в секунду. На даний момент один сервіс пошукових підказок спокійно справляється з трафіком prom.ua , споживаючи при цьому не більше 200 Мб пам'яті (для сервісу, що містить близько мільйона підказок, вистачило б і 100Мб - решта 100Мб потрібні для підказок, що використовуються в інших частинах сайту). На інших наших сайтах - tiu.ru , deal.by , satu.kz і prom.md - встановлені окремі копії сервісу пошукових підказок. Це зроблено не через те, що один сервіс не впорався б з навантаженням з усіх сайтів, а через те, що в різних країнах потрібно показувати різні пошукові підказки.

Висновок

Новий сервіс пошукових підказок досяг усіх поставлених цілей:

є повністю автономним - якщо він виходить з ладу або його починають DoS'іть, то інші частини сайту продовжують працювати як ні в чому не бувало;
швидко здійснює повнотекстовий пошук по префіксам серед мільйона підказок, враховуючи по можливості їх вага;
підтримує періодичне оновлення бази підказок.

Звичайно, він не є ідеальним. Існує море поліпшень, які можна було б реалізувати в цьому сервісі. Сподіваюся, ваші коментарі до цієї статті допоможуть поліпшити якість виведених підказок.

У даній статті описані лише деякі деталі розробки нашого сервісу пошукових підказок. Ця стаття є прикладом того, що на Python можна і потрібно розробляти високопродуктивні сервіси, оптимізовані за споживанням пам'яті. Gevent , struct , bytearray , array , heapq - найкращі друзі при розробці таких сервісів.

P.S. (Невеликий холіварчік)

У Python'а є перевага перед іншими популярними мовами програмування типу Java і C # - зазвичай код на Python пишеться швидше і виходить зрозуміліше і коротше. Наприклад, на даний момент весь код, відповідальний за індексацію і пошук підказок, займає 268 рядків , включаючи коментарі, порожні рядки і додаткові можливості, не описані в цій статті - прив'язка довільних даних до кожної фрази в індексі, запис і читання індексу в/з файлу, можливість пошуку за не повного збігу фраз, можливість завдання різних методів розбиття фраз на токени, розбиття списку фраз на Шарді з наступним об'єднанням результатів пошуку по кожному Шарді.

Бажаючі можуть ознайомитися з ісходникамі Suggester'а на github - головної складової сервісу пошукових підказок на . Якщо кому-небудь цікаві технічні деталі, упущені в цій статті, задавайте питання в коментарях - постараюся відповісти.

p: empty {display: none;}

Опубліковано: 22/08/13 @ 10:20
Розділ Пошуковики Сервіси

SEO Блог