Мы до сих пор не рассказывали публично о том, как мы это делаем. Но новое открытие австрийских ученых настолько нас обрадовало, что мы решились это сделать. Перейдем же к делу.Badoo работает по всему миру и наш поиск работает абсолютно одинаково, вне зависимости от того, в какой точке земного шара вы находитесь. Как же эффективно искать людей вокруг среди всех 200+ миллионов пользователей?
Решение нетривиально, честно говоря. Нам нужен какой-то индекс, какой-то способ сразу же сузить область поиска. В случае с земным шаром, самым простым разбиением является сетка географических широт и долгот. Однако проблема с этой сеткой в ее неравномерности. Ячейка у северного полюса и ячейка у экватора имеют совсем разные формы. Такое несимметричное разбиение вносит большие проблемы, если мы хотим равномерно распределить нагрузку по поисковому кластеру.
Каким же образом разбить поверхность земного шара так, чтобы ячейки были равны друг другу? Хотя бы примерно. Мы в Badoo вспомнили про один из правильных многоугольников, а именно икосаэдр. Его грани представляют из себя равные правильные треугольники. Граней у икосаэдра всего 20, что слишком мало для эффективного расшардивания нагрузки по поисковому кластеру. Но ведь его грани тоже можно разбить на треугольники.Спроецируем вершины и ребра икосаэдра на сферу Земли. Разобьем рекурсивно треугольники задаваемые икосаэдром на 4 более мелких треугольника. И так два раза. Получим в итоге 320 граней. К сожалению, уже не равных. Далее — программкой на питоне сгенерируем ~100000 строк кода на C, которые умеют делать трансформацию lon/lat -> треугольник.
Таким образом мы можем любую координату на земном шаре сопоставить с треугольником или, другими словами, с шардой кластера, которая содержит в себе всех пользователей, живущих в данной области земного шара.
Такой «большой» треугольник, в зависимости от желаемой точности поиска, мы можем и дальше разбивать на треугольники, все более и более «мелкие». Когда треугольники становятся достаточно мелкими по сравнению с радиусом земли — можно уже считать их «плоскими» и строить расстояния в «высотах треугольников», а не метрах.
Каждый из таких «маленьких» треугольников однозначно задается тройкой (a, b, c), где a, b, c являются номерами пересекающихся линий.
Как эффективно искать людей в маленьком треугольнике, используя нашу систему координат мы обязательно расскажем в будущем, если вам интересно, но мы бы хотели сегодня вернуться и более подробно поговорить о «больших» треугольниках.
Предложенное нами решение по разбиению земного шара имеет недостатки, связанные как с неравномерностью, так и с точностью. Несмотря на 320 шард, мы зачастую сталкиваемся с перекосами в нагрузке.
И вот, пару неделю назад, с нами связались наши друзья — сотрудники Австрийского Института Науки и Технологий и рассказали об их открытии.
Используя разработанную ими технику поиска симметричных сечений многомерных решеток и ресурсоемкие компьютерные вычисления им удалось построить новое симметричное разбиение сферы на шестиугольники с достаточно большим количеством вершин. Полученные дизайн они назвали «Гексасфера». На сайте с анонсом статьи выложена интерактивная модель данного разбиения. Вставить ее сюда мы не смогли, так что перейдите по ссылке, чтобы поиграться с ней.
В течение прошлой недели мы плотно поработали вместе с австрийцами, доработали наш алгоритм, и добились абсолютно равномерного распределения нагрузки по шардам.
Badoo для своих пользователей стал точнее, для нас система стала более предсказуемой и устойчивой к нагрузкам, а ученые из Австрии, надеемся, увидели интересное применение для своих идей.
В следующей статье мы обязательно более подробно расскажем как работает этот алгоритм и покажем на графиках те улучшения, которых нам удалось добиться.
Марко Кевац, разработчик-исследователь
Комментарии (31)
dovg
01.04.2015 15:55+1В течение прошлой недели мы плотно поработали вместе с австрийцами, доработали наш алгоритм, и добились абсолютно равномерного распределения нагрузки по шардам.
Нарезка земли на равны кусочки ведет к равномерности нагрузки? Но ведь кусочек, содержащий условный Дели будет гораздо более нагружен, чем кусочек с условной Антарктидой.
Мы в подобной задаче просто брали проекцию Меркатора, да там искажения на полюсах, но ведь на полюсах и пользователей сильно меньше, не так ли?
mkevac Автор
01.04.2015 16:26Будет гораздо более нагружен. Вы правы. Смотрите ответ на этот комментарий: habrahabr.ru/company/badoo/blog/254643/#comment_8356027
Geckelberryfinn
01.04.2015 16:08Круто! А вот предлагать знакомых рядом с учетом языка вы так и не научились. Живу в Париже и в Лионе и мне постоянно чернокожих красавиц предлагают. Спасибо, но пока нет)
mkevac Автор
01.04.2015 16:09Вам бы русских русых красавиц в Париже отыскать? :-)
Geckelberryfinn
01.04.2015 16:18Именно! Французские девушки не такие интересные. Кроме того, тут много русских, ищущих именно русских. И это стандартное желание среди эмигрантов.
И еще: а нужно ли равномерное разбиение сферы? Ведь наверняка нагрузка там больше, где плотность населения больше? Может имеет смысл сгущать сетку в густонаселенных районах? Это представит возможности по более детальному поиску. Например, в мегаполисах как Москва и Мехико можно делить по районам.mkevac Автор
01.04.2015 16:24-1Имеет. Вы правы.
Но разве можно отказаться от такого революционного открытия, как гексасфера? Можно ее просто сделать гуще! Равномерно гуще! :-)
Walas
01.04.2015 16:28+1В веб-версии (badoo.com), в People Nearby (Люди рядом) есть настройки поиска, в которых есть advanced search. Там можно искать девушек всяко-разно. Можно найти рыжеволосую, зелёноглазую, без вредных привычек, выше 170 сантиметров, не занятую, живущую отдельно, говорящую по-русски девушку за секунду. Если повезёт, и не одну. =) Удачи!
Geckelberryfinn
01.04.2015 16:35В мобильной веб-версии есть только мальчик/девочка, разброс возрастов и цель знакомства. А настольной версией неудобно на телефоне пользоваться.
yojick
01.04.2015 16:28+18Сидят в гримерке два клоуна — молодой и старый, выдумывают репризу. Молодой говорит: давайте вы выйдете на манеж, уроните кошелек, нагнетесь, а я выбегу из-за кулисы и дам вам сапогом по ж*пе. Старый печально отвечает: не годится. Слишком тонкая шутка для нашего цирка…
m1el
01.04.2015 19:05+6Если никто не заметил, это разбиение невозможно. :)
TimsTims
02.04.2015 14:09Вопрос — а если граница такого треугольника/шестиугольника проходит ну допустим прямо по середине города, значит поиск будет произведен только в одном шарде, и живущие, например прямо возле её границы никогда не найдут свою вторую половину из соседней улицы только потому что шарды так разбиты? Прямо как Берлинская стена…
mkevac Автор
02.04.2015 16:28Штуки в сторону, такие ситуации у нас обходятся таким образом, что треугольники пересекаются, накладываются друг на друга. Т.е. пользователи в какой-то области будут дублироваться в накладывающихся треугольниках.
kemsky
02.04.2015 17:01А почему вы решили использовать свое, вместо уже известных R-деревьев (и вагона других spatial индексов)?
forgotten
Если это на первое апреля, то могли бы что-нибудь позабавнее придумать.