Как редактору журнала Хакер, мне часто приходится писать о взломах. Все подобные случаи обычно связаны с хищением приватной информации, денег, либо и того и другого сразу. Очень редко хакер преследует какие-то иные цели: заявить о себе, отомстить бывшему работодателю или устроить акт вандализма по политическим мотивам. И вот недавно издание Wired поведало читателям об одной удивительной истории: 35-летний математик из Калифорнии взломал алгоритм сайта знакомств, чтобы найти себе идеальную девушку, причем это ему, как ни странно, удалось. И хотя речь здесь идет не о взломе в классическом понимании, а, скорее, о Data Mining, эта история заслуживает подробного рассказа.

Крис МакКинли (Chris McKinlay) родился в пригороде Бостона, и в 2001 году окончил колледж Миддлбери по специальности китайский язык. В августе того же года он устроился на полставки переводчиком с китайского в нью-йоркскую компанию, снимавшую офис на 91-м этаже северной башни Всемирного Торгового Центра. Спустя пять недель, 11 сентября 2001 года, Крис должен был явиться на работу к двум часам дня. Он еще крепко спал, когда в 8:46 утра первый самолет врезался в небоскреб, где располагался офис его компании. Увидев по телевизору, как здание Всемирного Торгового Центра падает и оседает на землю в клубах дыма и пыли, Крис крепко задумался о скоротечности нашего земного существования о том, чем он на самом деле хотел бы заниматься в своей жизни.


Крис МакКинли

Старый приятель, учившийся когда-то в Колумбийском университете, заинтересовал Криса блэкджеком именно в этой карточной игре впервые проявились математические и аналитические способности МакКинли. Бросив переводы, он присоединился к команде профессиональных игроков, и в течение нескольких лет мотался между Нью-Йорком и Лас-Вегасом, считая карты в казино и зарабатывая этим занятием порядка 60 000 долларов в год. Увлекаясь блэкджеком и покером, МакКинли строил математические модели для выработки оптимальных стратегий игры: это занятие приносило ему не только деньги, но и удовольствие.

Пробудившийся благодаря азартным играм глубокий интерес к точным наукам вновь направил Криса в учебную аудиторию: он поступил в магистратуру Калифорнийского университета в Лос-Анжелесе, а позже получил степень Ph.D. по прикладной математике. Однако еще в процессе написания диссертации по теме Крупномасштабная обработка данных и параллельные численные методы МакКинли пришел к выводу, что его по-прежнему устраивает в собственной жизни далеко не все. Главной причиной тревог 35-летнего математика было одиночество.

А не спеть ли мне песню о любви?

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

В отличие от знаменитого Тиндера, появившийся в 2004 году OkCupid (который принадлежит, к слову, тем же самым владельцам) претендует на научный подход в вопросах строительства отношений как раз то, что нужно ученым, программистам, хакерам и прочим нердам. Сайт, разработанный четырьмя студентами-математиками из Гарвардкого университета, быстро набрал небывалую популярность в США, попав в ТОП-10 лучших служб знакомств по версии журнала Time за 2007 год. Его основное отличие от других аналогичных площадок заключается в том, что после бесплатной регистрации пользователю предлагается ответить на вопросы нескольких довольно-таки подробных анкет, с помощью которых составляется его психологический портрет. Алгоритмы OkCupid подбирают пары исходя из общих предпочтений, интересов и сходства анкетных данных. Соответственно, чем более подробно заполнен профиль, тем более подходящую кандидатуру способен отыскать сайт знакомств, но тем меньше математических шансов на удачное совпадение.

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


>Типичная анкета пользователя на OkCupid.com

Личный опыт Криса МакКинли показал, что с сайтом OkCupid отношения у него как-то не складываются. При наличии миллионов активных пользователей, из которых примерно 80 000 женщины из Лос-Анжелеса, его профиль совершенно не привлекал внимания противоположного пола. Сайт учитывает совпадения только в том случае, если оба пользователя ответили на одни и те же вопросы анкеты, а выбранные Крисом варианты не пользовались популярностью у девушек. Более того: из предложенных бездушными алгоритмами пары десятков потенциальных невест на сообщения Криса откликнулись лишь несколько. Шесть состоявшихся свиданий подтвердили опасения МакКинли о том, что подобная методика знакомств пустая трата времени. А раз она не приносит должного результата, нужно менять алгоритм: этот принцип прекрасно работал в мире карточных игр. Почему бы для налаживания личной жизни одно конкретно взятого человека, то есть своей собственной, не воспользоваться достижениями современной науки? подумал Крис. И решил вооружиться математикой с благородной целью: найти на OkCupid идеальную девушку, построить с ней отношения и обрести, наконец, счастье, о котором он так долго мечтал.

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

Взломай это!

Для начала Крис собрал полный ассортимент вопросов, которые задает своим пользователям OkCupid, и рассортировал их по тематике. Всего получилось семь групп. Теперь нужно было извлечь данные из анкет пользователей, которые подходили ему в качестве потенциального партнера: гетеросексуальные и бисексуальные женщины в возрасте от 25 до 45 лет. OkCupid дает возможность просмотреть ответы других юзеров, но только на те вопросы, на которые ответил ты сам. Чтобы обойти это ограничение, Крис создал 12 фейковых учетных записей и написал скрипты на Python для управления этими аккаунтами. Поддельные пользователи случайным образом отвечали на определенный блок вопросов в анкете, а затем посещали профайлы девушек, подходивших Крису по возрастным критериям, и собирали их варианты ответов в специально созданную базу данных.

С нескрываемым удовольствием Крис наблюдал, как его детище принялось шерстить сайт знакомств. Однако вскоре после того, как база наполнилась информацией о первой тысяче аккаунтов, МакКинли столкнулся с серьезной технической проблемой: механизмы безопасности OkCupid зафиксировали подозрительную активность на сайте и принялись банить его ботов одного за другим. За решением этой задачи ученый обратился к своему приятелю нейробиологу Сэму Торриси, который преподавал ему теорию музыки в обмен на уроки математики. Торриси и сам был завсегдатаем OkCupid. Проникшись идеей, он согласился на предложение Криса установить на собственном компьютере программу, которая фиксировала все его действия при просмотре анкет. Заполучив в свое распоряжение трекинг движений мыши Сэма Торриси, сведения о переходах по ссылкам и данные о скорости нажатия клавиш, МакКинли перепрограммировал ботов таким образом, чтобы они имитировали действия живого пользователя. В результате администрация сайта перестала банить его фейковые аккаунты, и Крис сумел собрать данные 20 000 анкет, содержащих более 6 млн ответов на вопросы. Диссертация была временно заброшена: МакКинли фактически поселился в своей каморке, расположенной в одном из кампусов Калифорнийского университета, и притащил из дома матрац, который раскладывал прямо на столе, когда ему хотелось спать. Изучение данных с сайта знакомств захватило его полностью, превратившись в своего рода маниакальную идею.


То самое здание Калифорнийского университета в Лос-Анжелесе

Собранную информацию предстояло проанализировать, выявив закономерности среди десятков тысяч анкет. Для этого МакКинли использовал модифицированный алгоритм кластеризации под названием K-modes, готовая реализация которого имеется в каталоге PyPi для Python. Алгоритм K-modes, разработанный когда-то исследователями из компании Bell Labs, использует принцип категоризации сущностей на основе заданных параметров. Экспериментируя с этими параметрами, Крис сумел разделить 20 000 наиболее релевантных его запросам анкет на семь отдельных групп в соответствии с результатами анкетирования. Получились выборки, с которыми можно было работать дальше. С помощью ботов МакКинли собрал данные еще 5000 анкет женщин из Лос-Анжелеса и Сан-Франциско, заходивших на OkCupid в течение последнего месяца. Обработка этой выборки с помощью алгоритма K-modes дала похожий результат: анкеты отсортировались в аналогичных пропорциях. Методика сработала!

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


В Калифорнийском университете, как и во многих учебных заведениях США, есть своя бейсбольная команда и учатся симпатичные чирлидеры

Осталось сделать следующий шаг к успеху. Крис зарегистрировал на OkCupid два профиля и оптимизировал каждый под соответствующую целевую группу. На странице одного из них он разместил собственное фото в образе спортсмена-верхолаза, сделанное на ближайшем скалодроме, в другом профиле Крис предстал в романтичном образе музыканта, исполняющего на вечеринке песню под гитару. Затем МакКинли подготовил собственную биографию в соответствии с предпочтениями, которые указывали в своих анкетах интересующие его девушки, и выбрал 500 вопросов, пользовавшихся наибольшей популярностью в обеих группах профайлов. На вопросы Крис решил отвечать честно, поскольку от его ответов напрямую зависела релевантность поиска потенциальных партнерш.

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

Закончив с анкетами, Крис решил посмотреть, сколько вариантов знакомств предложит ему OkCupid и не поверил своим глазам. По умолчанию сайт сортирует выдачу по уменьшению степени совпадения психологического профиля и интересов. МакКинли торопливо пролистал несколько страниц, но подходящие ему с точки зрения OkCupid девушки, ответы которых совпали с его собственными более чем на более 90%, все не заканчивались в выборке оказалось более 10 000 красавиц со всей Америки.

Сайт OkCupid автоматически уведомляет пользователя, когда кто-то просматривает его профиль. Чтобы привлечь к себе внимание, МакКинли написал еще один скрипт, который от имени его аккаунта автоматически открывал анкеты женщин из Лос-Анжелеса разных возрастных групп: 1000 анкет дам в возрасте 41 года, затем еще 1000 на год помладше, и так до 25-летних девушек. Скрипт обрабатывал строго определенное количество строк собранной Крисом базы в сутки, чтобы избежать возможной блокировки. И женщины стали заглядывать в профиль МакКинли, а потом посыпались первые сообщения. Ты действительно знаешь китайский?, писали ему заинтригованные девушки. Возможно, у нас много общего, пусть не в области математики, но наверняка в других интересных вещах. Твоя страничка выглядит интригующей!. Это был полный и безоговорочный успех. По крайней мере, Крису так казалось поначалу.

Встреча с реальностью

30 июня МакКинли принял душ в спортзале Калифорнийского университета в Лос-Анджелесе и проехал на своем потрепанном Nissan через весь город на первое свидание, рассказывает об этой истории Wired. Однако практическая часть эксперимента оказалась гораздо менее продуктивной, чем теоретическая. Первые три встречи с потенциальными претендентками на роль спутницы жизни закончились ничем: вопреки ожиданиям, у Криса не возникало взаимной симпатии с откликнувшимися на его анкету девушками. На третий раз он и вовсе накидался вместе с новой знакомой пивом в корейском ресторане, а наутро проснулся в гордом одиночестве, зато с жутким похмельем. Немного придя в себя, МакКинли зашел на OkCupid и отправил ей личное сообщение, но девушка не ответила. Реальная жизнь и реальное общение за пределами университетского кампуса оказались немного сложнее программирования и математики, в которых Крис, как выяснилось, разбирался намного лучше.

Этот случай, безусловно, расстроил математика, но не обескуражил его, ведь он по-прежнему получал порядка 20 сообщений ежедневно. Теперь у него появилась возможность выбирать: он игнорировал послания с пошлостями и глупыми шутками, и наоборот, вступал в переписку только с теми девушками, которые подробно рассказывали о себе, обладали чувством юмора или казались ему интересными. Если поначалу он вдумчиво готовился к каждому свиданию, репетировал собственные речи и тщательно продумывал интересные темы для бесед, то вскоре стал относиться к этому проще, устраивая по две встречи в день или просто договариваясь с девушкой пересечься где-нибудь в кафе или на пляже во время обеденного перерыва. В самом начале эксперимента он вступал в длительную переписку, сочиняя для потенциальных избранниц развернутые и подробные письма. Позже стал ограничиваться короткими сообщениями из разряда Ты классно выглядишь. Хочешь встретиться?. Это работало.

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

С ростом количества встреч аналитический ум МакКинли стал подмечать в происходящем кое-какие закономерности. Большинство юных девушек из группы 25+ проживали в восточной части Лос-Анжелеса и имели, как правило, более двух татуировок. Эту группу Крис назвал Tatoo. Одинокие женщины старшего возраста часто оказывались обладательницами целого выводка собак среднего размера, которых они обожали. Таких кандидаток он решил называть Dog. Некоторые девчонки знакомились только с новичками на сайте OkCupid, этих он отнес к группе Зеленые. Другие были склонны к приключениям, их он окрестил по имени одной яркой представительницы данной категории Саманты. Всего подобных групп набралось семь.


Точный расчет и математический анализ залог счастливой любви. Или нет? Иллюстрация Wired

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

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


Счастливая парочка Крис МакКинли и Кристин Тьен Ван

Однажды утром в строке номер 88 лабораторного журнала Криса МакКинли появилась очередная запись: Кристин Тьен Ван, 28 лет, художница, студентка магистратуры факультета изящных искусств Калифорнийского университета Лос-Анжелеса, активистка, борющаяся за отмену тюрем. Совпадение их анкет составляло 91%. Они встретились в саду университетского кампуса и отправились в суши-бар, расположенный на территории колледжа. Там Кристин призналась своему спутнику, что внесла кое-какие изменения в собственный профиль и ответы на сайте знакомств, чтобы найти с помощью OkCupid как можно больше интересных парней. В порыве откровенности Крис поведал ей в ответ свою историю всю как есть, ничего не скрывая. Он рассказал ей о том, что девушка стала очередной невольной участницей его математического эксперимента. Это звучало ужасно цинично, призналась потом Тьен Ван изданию Wired, настолько, что мне все это чертовски понравилось!. За первой встречей последовала вторая, затем третья, а спустя две недели молодые люди удалили свои анкеты на сайте OkCupid.

Happy End

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

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

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

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

Неотъемлемой частью сайта для знакомств OkCupid являются рекомендации потенциальных партнёров. Они основаны на совпадении множества предпочтений, которые указали вы и ваши потенциальные партнёры. Как вы можете себе представить, существует множество вариантов оптимизации этой задачи.

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

Мы должны выдавать наилучшие результаты и практически бесконечный список рекомендаций. В других приложениях, где контент меняется не так часто, это можно сделать периодически обновляя рекомендации. Например, при использовании функции Spotify Discover Weekly вы наслаждаетесь набором рекомендуемых треков, этот набор не меняется до следующей недели. На OkCupid пользователи бесконечно просматривают свои рекомендации в режиме реального времени. Рекомендуемый контент очень динамичен по своей природе (например, пользователь может изменить свои предпочтения, данные профиля, местоположение, деактивироваться в любое время и т.д.). Пользователь может изменить, кому и как его можно рекомендовать, поэтому мы хотим убедиться, что потенциальные совпадения лучшие на данный момент времени.

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

Какие проблемы у существующей системы поиска совпадений

OkCupid уже много лет использует собственную внутреннюю систему поиска совпадений. Не будем вдаваться в детали, но на высоком уровне абстракции она представляет собой фреймворк map-reduce над шардами пользовательского пространства, где каждый шард содержит в памяти некоторую часть релевантных пользовательских данных, которые используются при включении различных фильтров и сортировок на лету. Поисковые запросы расходятся на все шарды, и в конечном счете результаты объединяются, чтобы вернуть k лучших кандидатов. Эта написанная нами система поиска пар работала хорошо, так почему сейчас мы решили изменить её?

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

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

Сегодня в OkCupid многие из этих подсистем обслуживаются более надёжными и дружественными к облакам опциями OSS, и команда за последние два года с большим успехом внедрила различные технологии. Не будем здесь рассказывать об этих проектах, а вместо этого сосредоточимся на действиях, которые мы предприняли для решения вышеуказанных проблем, перейдя к более удобной для разработчиков и масштабируемой поисковой системе для наших рекомендаций: Vespa.

Это совпадение! Почему OkCupid подружился с Vespa

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

Elasticsearch

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

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

Vespa

Исходные коды открыты всего несколько лет назад. Разработчики заявили поддержку хранения, поиска, ранжирования и организации Big Data в реальном времени. Функции, которые поддерживает Vespa:

• высокая производительность выдачи благодаря реальным частичным обновлениям в памяти без необходимости переиндексировать весь документ (как сообщается, до 40-50тыс. обновлений в секунду на узел)
  
• обеспечивает гибкую структуру ранжирования, позволяющую обрабатывать данные во время запроса
  
• непосредственно поддерживает в ранжировании интеграцию с моделями машинного обучения (например, TensorFlow)
  
• запросы можно выполнять с помощью выразительного YQL (Yahoo Query Language) в вызовах REST
  
• возможность настройки логики с помощью Java-компонентов

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

В целом Vespa, видимо, лучше всего подходила для наших вариантов использования. OkCupid включает в себя множество различной информации о пользователях, чтобы помочь им найти лучшие пары с точки зрения просто фильтров и сортировок там более сотни параметров! Мы всегда будем добавлять фильтры и сортировки, поэтому очень важно поддерживать этот рабочий процесс. Что касается записей и запросов, Vespa больше всего похожа на нашу существующую систему; то есть наша система также требовала обработки быстрых частичных обновлений в памяти и обработки в реальном времени во время запроса на поиск совпадений. У Vespa также гораздо более гибкая и простая структура ранжирования. Ещё одним приятным бонусом стала возможность выражать запросы в YQL, в отличие от неудобной структуры для запросов в Elasticsearch. Что касается масштабирования и обслуживания, то возможности автоматического распределения данных в Vespa оказались очень привлекательны для нашей относительно небольшой команды. В целом выяснилось, что Vespa лучшие поддерживает наши варианты использования и требования к производительности, будучи при этом проще в обслуживании по сравнению с Elasticsearch.

Elasticsearch более известный движок, и мы могли бы воспользоваться опытом его использования в Tinder, но любой вариант потребует тонны предварительных исследований. В то же время Vespa обслуживает множество систем в продакшне, таких как Zedge, Flickr с миллиардами картинок, рекламная платформа Yahoo Gemini Ads с более чем ста тысячами запросов в секунду для выдачи рекламы миллиарду активных пользователей в месяц. Это дало нам уверенность в том, что это проверенный в боях, эффективный и надёжный вариант на самом деле Vespa появилась даже раньше, чем Elasticsearch.

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

Как работает Vespa и как выглядит поиск в OkCupid

Прежде чем погрузиться в наш пример использования Vespa, вот краткий обзор того, как она работает. Vespa это набор многочисленных служб, но каждый контейнер Docker можно сконфигурировать на роль узла admin/config, узла контейнера Java, не зависящего от состояния (stateless) и/или узла контента C++, зависящего от состояния (stateful). Пакет приложения с конфигурацией, компонентами, моделью ML и т.д. может быть развернут через State API в конфигурационном кластере, который обрабатывает применение изменений к контейнеру и кластеру содержимого. Запросы фида и остальные запросы проходят через stateless-контейнер Java (который позволяет настроить обработку) по HTTP, прежде чем обновления фида поступают в кластер контента или запросы разветвляются на уровень контента, где происходит распределённое выполнение запросов. По большей части развёртывание нового пакета приложений занимает всего несколько секунд, и Vespa обрабатывает эти изменения в реальном времени в контейнере и кластере контента, так что вам редко приходится что-либо перезапускать.

Как выглядит поиск?

Документы в кластере Vespa содержат множество атрибутов, относящихся к данному пользователю. Определение схемы определяет поля типа документа, а также профили ранжирования, содержащие набор применимых выражений ранжирования. Предположим, у нас есть определение схемы, представляющее пользователя следующим образом:

search user {    document user {        field userId type long {            indexing: summary | attribute            attribute: fast-search            rank: filter        }        field latLong type position {            indexing: attribute        }        # UNIX timestamp        field lastOnline type long {            indexing: attribute            attribute: fast-search        }        # Contains the users that this user document has liked        # and the corresponding weights are UNIX timestamps when that like happened         field likedUserSet type weightedset<long> {            indexing: attribute            attribute: fast-search        }           }    rank-profile myRankProfile inherits default {        rank-properties {            query(lastOnlineWeight): 0            query(incomingLikeWeight): 0        }        function lastOnlineScore() {            expression: query(lastOnlineWeight) * freshness(lastOnline)        }        function incomingLikeTimestamp() {            expression: rawScore(likedUserSet)        }        function hasLikedMe() {            expression:  if (incomingLikeTimestamp > 0, 1, 0)        }         function incomingLikeScore() {            expression: query(incomingLikeWeight) * hasLikedMe        }        first-phase {            expression {                lastOnlineScore + incomingLikeScore            }        }        summary-features {            lastOnlineScore incomingLikeScore        }    }    }

Обозначение indexing: attribute указывает на то, что эти поля должны храниться в памяти, чтобы обеспечить наилучшую производительность записи и чтения этих полей.

Предположим, мы заполнили кластер такими пользовательскими документами. Затем мы могли бы выполнить фильтрацию и ранжирование по любому из вышеперечисленных полей. Например, сделать POST-запрос к обработчику поиска по умолчанию http://localhost:8080/search/, чтобы найти пользователей, за исключением нашего собственного пользователя 777, в пределах 50 миль от нашего местоположения, которые были онлайн с момента отметки времени 1592486978, с ранжированием по последней активности и сохраняя двух лучших кандидатов. Давайте также выберем summaryfeatures, чтобы увидеть вклад каждого выражения ранжирования в нашем профиле ранжирования:

{    "yql": "select userId, summaryfeatures from user where lastOnline > 1592486978 and !(userId contains \"777\") limit 2;",    "ranking": {        "profile": "myRankProfile",        "features": {            "query(lastOnlineWeight)": "50"        }    },    "pos": {        "radius": "50mi",        "ll": "N40o44'22;W74o0'2",        "attribute": "latLong"    },    "presentation": {        "summary": "default"    }}

Мы могли бы получить такой результат:

{    "root": {        "id": "toplevel",        "relevance": 1.0,        "fields": {            "totalCount": 317        },        "coverage": {            "coverage": 100,            "documents": 958,            "full": true,            "nodes": 1,            "results": 1,            "resultsFull": 1        },        "children": [            {                "id": "index:user/0/bde9bd654f1d5ae17fd9abc3",                "relevance": 48.99315843621399,                "source": "user",                "fields": {                    "userId": -5800469520557156329,                    "summaryfeatures": {                        "rankingExpression(incomingLikeScore)": 0.0,                        "rankingExpression(lastOnlineScore)": 48.99315843621399,                        "vespa.summaryFeatures.cached": 0.0                    }                }            },            {                "id": "index:user/0/e8aa37df0832905c3fa1dbbd",                "relevance": 48.99041280864198,                "source": "user",                "fields": {                    "userId": 6888497210242094612,                    "summaryfeatures": {                        "rankingExpression(incomingLikeScore)": 0.0,                        "rankingExpression(lastOnlineScore)": 48.99041280864198,                        "vespa.summaryFeatures.cached": 0.0                    }                }            }        ]    }}

После фильтрации по совпадающим попаданиям вычисляются выражения ранжирования первой фазы (first-phase) для ранжирования попаданий. Возвращаемая релевантность (relevance) это общая оценка как результат выполнения всех функций ранжирования первой фазы в профиле ранжирования (rank-profile), который мы указали в нашем запросе, то есть ranking.profile myRankProfile. В списке ranking.features мы определили query(lastOnlineWeight) как 50, на неё затем ссылается единственное используемое нами выражение ранжирования lastOnlineScore. Оно использует встроенную функцию ранжирования freshness, которая представляет собой число, близкое к 1, если временная метка в атрибуте является недавней по сравнению с текущей временной меткой. Пока всё идет хорошо, здесь ничего сложного.

В отличие от статического контента, этот контент может влиять на то, показывать его пользователю или нет. Например, они могут вас лайкнуть! Мы могли бы индексировать взвешенное поле likedUserSet для каждого пользовательского документа, который содержит в качестве ключей идентификаторы пользователей, которых они лайкнули, и в качестве значений метку времени, когда подобное произошло. Тогда было бы просто отфильтровать тех, кто вас лайкнул (например, добавлениес выражения likedUserSet contains \777\ в YQL), но как включить эту информацию во время ранжирования? Как повысить в результатах тогр пользователя, который лайкнул нашего человека?

В предыдущих результатах выражение ранжирования incomingLikeScore было равно 0 для обоих этих попаданий. Пользователь 6888497210242094612 на самом деле лайкнул пользователя 777, но в настоящее время он недоступен в рейтинге, даже если бы мы поставили "query(incomingLikeWeight)": 50. Мы можем использовать функцию rank в YQL (первый и только первый аргумент функции rank() определяет, является ли документ совпадением, но все аргументы используются для вычисления оценки ранжирования), а затем использовать dotProduct в нашем выражении ранжирования YQL для хранения и извлечения необработанных оценок (в данном случае метки времени, когда пользователь нас лайкнул), например, таким образом:

{    "yql": "select userId,summaryfeatures from user where !(userId contains \"777\") and rank(lastOnline > 1592486978, dotProduct(likedUserSet, {\"777\":1})) limit 2;",    "ranking": {        "profile": "myRankProfile",        "features": {            "query(lastOnlineWeight)": "50",            "query(incomingLikeWeight)": "50"        }    },    "pos": {        "radius": "50mi",        "ll": "N40o44'22;W74o0'2",        "attribute": "latLong"    },    "presentation": {        "summary": "default"    }}

{    "root": {        "id": "toplevel",        "relevance": 1.0,        "fields": {            "totalCount": 317        },        "coverage": {            "coverage": 100,            "documents": 958,            "full": true,            "nodes": 1,            "results": 1,            "resultsFull": 1        },        "children": [            {                "id": "index:user/0/e8aa37df0832905c3fa1dbbd",                "relevance": 98.97595807613169,                "source": "user",                "fields": {                    "userId": 6888497210242094612,                    "summaryfeatures": {                        "rankingExpression(incomingLikeScore)": 50.0,                        "rankingExpression(lastOnlineScore)": 48.97595807613169,                        "vespa.summaryFeatures.cached": 0.0                    }                }            },            {                "id": "index:user/0/bde9bd654f1d5ae17fd9abc3",                "relevance": 48.9787037037037,                "source": "user",                "fields": {                    "userId": -5800469520557156329,                    "summaryfeatures": {                        "rankingExpression(incomingLikeScore)": 0.0,                        "rankingExpression(lastOnlineScore)": 48.9787037037037,                        "vespa.summaryFeatures.cached": 0.0                    }                }            }        ]    }}

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

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

Настройка промежуточного уровня middleware в Java

Что, если бы мы хотели пойти другим путём и сделать это выражение dotProduct неявно частью каждого запроса? Вот где появляется настраиваемый уровень контейнера Java мы можем написать пользовательский компонент Searcher. Это позволяет обрабатывать произвольные параметры, переписывать запрос и обрабатывать результаты определённым образом. Вот пример на Kotlin:

@After(PhaseNames.TRANSFORMED_QUERY)class MatchSearcher : Searcher() {    companion object {        // HTTP query parameter        val USERID_QUERY_PARAM = "userid"        val ATTRIBUTE_FIELD_LIKED_USER_SET = likedUserSet    }    override fun search(query: Query, execution: Execution): Result {        val userId = query.properties().getString(USERID_QUERY_PARAM)?.toLong()        // Add the dotProduct clause        If (userId != null) {            val rankItem = query.model.queryTree.getRankItem()            val likedUserSetClause = DotProductItem(ATTRIBUTE_FIELD_LIKED_USER_SET)            likedUserSetClause.addToken(userId, 1)            rankItem.addItem(likedUserSetClause)               }        // Execute the query        query.trace("YQL after is: ${query.yqlRepresentation()}", 2)        return  execution.search(query)    }}

Потом в нашем файле services.xml мы можем настроить этот компонент следующим образом:

...                <search>            <chain id="default" inherits="vespa">                <searcher id="com.okcupid.match.MatchSearcher" bundle="match-searcher"/>            </chain>        </search>        <handler id="default" bundle="match-searcher">            <binding>http://*:8080/match</binding>        </handler>...

Затем мы просто создаём и развёртываем пакет приложения и делаем запрос к пользовательскому обработчику http://localhost:8080/match-что?userid=777:

{    "yql": "select userId,summaryfeatures from user where !(userId contains \"777\") and rank(lastOnline > 1592486978) limit 2;",    "ranking": {        "profile": "myRankProfile",        "features": {            "query(lastOnlineWeight)": "50",            "query(incomingLikeWeight)": "50"        }    },    "pos": {        "radius": "50mi",        "ll": "N40o44'22;W74o0'2",        "attribute": "latLong"    },    "presentation": {        "summary": "default"    }}

Мы получаем те же результаты, что и раньше! Обратите внимание, что в коде Kotlin мы добавили трассировку для выдачи представления YQL после изменения, поэтому, если установить tracelevel=2 в параметрах URL, ответ также будет показан:

...                    {                        "message": "YQL after is: select userId, summaryfeatures from user where ((rank(lastOnline > 1592486978, dotProduct(likedUserSet, {\"777\": 1})) AND !(userId contains \"777\") limit 2;"                    },...

Контейнер промежуточного слоя Java является мощным средством, чтобы добавить пользовательскую логику обработки через Searcher или собственную генерацию результатов с помощью Renderer. Мы настраиваем наши компоненты Searcher для обработки случаев, подобных приведённым выше, и других аспектов, которые мы хотим сделать неявными в наших поисках. Например, одной из концепций продукта, которую мы поддерживаем, является идея взаимной подгонки вы можете искать пользователей с определёнными критериями (например, возрастной диапазон и расстояние), но вы также должны соответствовать критериям поиска кандидатов. Чтобы поддержать такой вариант в нашем компоненте Searcher, мы могли бы извлечь документ пользователя, который выполняет поиск, чтобы предоставить некоторые из его атрибутов в последующем разветвлённом запросе для фильтрации и ранжирования. Структура ранжирования и кастомный промежуточный слой вместе обеспечивают гибкий способ поддержки многочисленных вариантов использования. В этих примерах мы рассмотрели только несколько аспектов, но здесь вы можете найти подробную документацию.

Как мы построили кластер Vespa и запустили его в продакшн

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

Первые этапы прототипирования

Системы бэкенда OkCupid написаны на Golang и C++. Чтобы написать кастомные логические компоненты Vespa, а также обеспечить высокую скорость подачи фида с помощью Java Vespa HTTP feed client API, нам пришлось немного познакомиться со средой JVM мы в конечном итоге использовали Kotlin при настройке компонентов Vespa и в наших конвейерах подачи.

Несколько лет занял портирование прикладной логики и раскрытие функций Vespa, консультации с командой Vespa по мере необходимости. Большая часть системной логики движка поиска соответствий написано в C++, поэтому мы также добавили логику для перевода нашей текущей модели данных фильтров и сортировок в эквивалентные запросы YQL, которые мы выдаем через REST кластеру Vespa. На раннем этапе мы также позаботились о создании хорошего конвейера для повторного заполнения кластера полной пользовательской базой документов; прототипирование должно включать в себя множество изменений для определения правильных типов полей для использования, а также непреднамеренно требует повторной подачи фида с документами.

Мониторинг и нагрузочное тестирование

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

Перед нагрузочными тестами мы везде добавили метрики Prometheus. Vespa-exporter предоставляет массу статистических данных, а сама Vespa также предоставляет небольшой набор дополнительных метрик. Исходя из этого, мы создали различные информационные панели Grafana по запросам в секунду, задержкам, использованию ресурсов процессами Vespa и т.д. Мы также запустили vespa-fbench для тестирования производительности запросов. С помощью разработчиков Vespa мы определили, что из-за относительно высокой стоимости статических запросов наш сгруппированный готовый макет обеспечит более скоростную выдачу. В плоском макете добавление большего количества узлов в основном только сокращает стоимость динамического запроса (то есть той части запроса, которая зависит от количества проиндексированных документов). Сгруппированный макет означает, что каждая настроенная группа узлов будет содержать полный набор документов, и поэтому одна группа может обслужить запрос. Из-за высокой стоимости статических запросов, сохраняя количество узлов одинаковым, мы значительно увеличили пропускную способность, увеличив количество с одной группы с плоской компоновкой до трёх. Наконец, мы также провели тестирование неучтённого теневого трафика в реальном времени, когда стали уверены в надёжности статических бенчмарков.

Оптимизация производительности

Производительность выдачи стала одним из самых больших препятствий, с которым мы столкнулись на ранней стадии. В самом начале у нас появились проблемы с обработкой обновлений даже на 1000 QPS (запросов в секунду). Мы активно использовали поля из взвешенного множества (weighted set fields), но поначалу они не были эффективными. К счастью, разработчики Vespa быстро помогли решить эти проблемы, а также другие, связанные с распространением данных. Позже они также добавили обширную документацию по калибровке фидов, которую мы в какой-то степени используем: целочисленные поля в больших взвешенных множествах, когда это возможно, позволяют дозировать, устанавливая visibility-delay, используя несколько условных обновлений и полагаясь на поля атрибутов (то есть в памяти), а также сокращая количество пакетов туда-обратно от клиентов за счёт уплотнения и слияния операций в наших конвейерах фмдов. Теперь конвейеры спокойно обрабатывают 3000 QPS в устойчивом состоянии, и наш скромный кластер обрабатывает обновления на 11тыс.QPS, когда такой всплеск возникает по какой-то причине.

Качество рекомендаций

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

Схема системы

В упрощённом виде итоговая схема архитектуры новой системы выглядит так:

Как Vespa работает сейчас и что будет дальше

Давайте сравним состояние системы поиска пар Vespa, с прошлой системой:

• Обновления схемы
  
  • Раньше: неделя с сотнями новых строк кода, тщательно скоординированное развёртывание с несколькими подсистемами
    
  • Теперь: за пару часов добавляете простое поле в определение схемы и развёртываете пакет приложения
• Добавление новой сортировки/ранжирования
  
  • Раньше: полдня на развёртывание
    
  • Теперь: выражения ранжирования сами по себе являются обновлением определения схемы и могут быть развёрнуты в рабочей системе. Таким образом, их включение занимает всего несколько секунд!
• Масштабирование и поддержка
  
  • Раньше: многонедельные усилия по ручному распределению шардов и размещению файлов обслуживания продакшна, чтобы добиться высокой доступности
    
  • Теперь: просто добавляем новый узел в конфигурационный файл, и Vespa автоматически распределит данные для желаемых уровней избыточности. Основная часть операций не требует ручного вмешательства или перезапуска каких-либо узлов с отслеживанием состояния

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

Что дальше?

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

Кроме того, Vespa недавно объявила о поддержке многомерных приближённых индексов ближайших соседей (nearest neighbor index), которые работают полностью в реальном времени, одновременно доступны для поиска и динамически обновляются. Нам очень интересно изучить другие варианты использования поиска с индексом ближайших соседей в режиме реального времени.

OkCupid и Vespa. Поехали!

Многие слышали или работали с Elasticsearch, но вокруг Vespa нет такого большого сообщества. Мы считаем, что много других приложений на Elasticsearch лучше бы работали на Vespa. Она отлично подходит для OkCupid, и мы рады, что перешли на неё. Эта новая архитектура позволила нам гораздо быстрее развиваться и разрабатывать новые функции. Мы относительно небольшая компания, так что это здорово особо не беспокоиться о сложностях обслуживания. Теперь мы гораздо лучше готовы к горизонтальному масштабированию нашего поисковика. Без Vespa мы, конечно, не смогли бы добиться того прогресса, которого достигли за последний год. Для получения дополнительной информации о технических возможностях Vespa обязательно ознакомьтесь с рекомендациями по Vespa AI в электронной коммерции от @jobergum.

Мы сделали первый шаг и лайкнули разработчиков Vespa. Они послали нам ответное сообщение, и это оказалось совпадение! Мы не смогли бы сделать это без помощи команды Vespa. Особая благодарность @jobergum и @geirst за рекомендации по ранжированию и обработке запросов, а также @kkraune и @vekterli за их поддержку. Уровень поддержки и усилий, которые оказала нам команда Vespa, был поистине потрясающим от глубокого изучения нашего варианта использования до диагностики проблем производительности и мгновенного внесения улучшений в движок Vespa. Товарищ @vekterli даже прилетел в наш офис в Нью-Йорке и в течение недели работал непосредственно с нами, чтобы помочь в интеграции движка. Большое спасибо команде Vespa!

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