Как вы знаете, Badoo — сервис для поиска новых людей. Кроме всего прочего, мы позволяем искать людей вокруг и в «игре» тоже показываем людей, которые находятся недалеко от вас. Эта часть «вокруг» очень и очень важна. Ведь молодому человеку из Новосибирска гораздо интереснее познакомиться с девушкой, которая живет в пяти минутах ходьбы от него, а не во Владивостоке. ![][1] Мы до сих пор не рассказывали публично о том, как мы это делаем. Но [новое открытие][2] австрийских ученых настолько нас обрадовало, что мы решились это сделать. Перейдем же к делу. Badoo работает по всему миру и наш поиск работает абсолютно одинаково, вне зависимости от того, в какой точке земного шара вы находитесь. Как же эффективно искать людей вокруг среди всех 200+ миллионов пользователей? Решение нетривиально, честно говоря. Нам нужен какой-то индекс, какой-то способ сразу же сузить область поиска. В случае с земным шаром, самым простым разбиением является сетка географических широт и долгот. Однако проблема с этой сеткой в ее неравномерности. Ячейка у северного полюса и ячейка у экватора имеют совсем разные формы. Такое несимметричное разбиение вносит большие проблемы, если мы хотим равномерно распределить нагрузку по поисковому кластеру. [Читать дальше →][3]

[1]: //habrastorage.org/files/b7b/4f4/f74/b7b4f4f7453444958c56bbf655d71d5a.png
[2]: http://pub.ist.ac.at/~edels/hexasphere/
[3]: http://habrahabr.ru/post/254643/#habracut