Дэвид Линч: главный инженер Soundwave
Soundwave — это приложение для смартфонов, которое отслеживает музыку так же быстро, как и воспроизводится. Soundwave отслеживает музыкальные привычки каждого пользователя на разных платформах и в потоковых сервисах 1 , создавая профиль прослушивания. Пользователи следуют друг за другом, облегчая прослушивание, обмен, обнаружение и обсуждение музыки старой и новой, популярной и нишевой.
MongoDB является нашей базой данных выбора. Мы отслеживаем около 250 000 прослушиваний в день от пользовательской базы, которая выросла до 1 миллиона за последние 13 месяцев. Soundwave имеет пользователей во всех часовых поясах, что делает доступность критической. Наборы реплик MongoDB обеспечивают нам отказоустойчивость и избыточность, что позволяет нам выполнять плановое обслуживание, не затрагивая пользователей.
Мы считаем, что отзывчивость является ключевой частью пользовательского интерфейса Soundwave, поэтому мы используем изолированную конфигурацию, которая позволяет нам добавлять вычислительные ресурсы и ресурсы хранения по мере необходимости.
Мы широко используем индексы, а шаблоны использования приложений требуют поддержки достаточно большого рабочего набора в памяти. Sharding позволяет нам развертывать большее количество сравнительно небольших и непропорционально дешевых экземпляров AWS 2 , сохраняя при этом быстрый пользовательский интерфейс, который нам необходим.
Объем данных, которые мы обрабатываем сегодня, значителен, но не огромен. Для нас было важно с самого начала спроектировать систему, которая бы легко и экономично масштабировалась.
Сложность извлечения данных умеренная, но хорошо подходит для MongoDB. Наше приложение было представлено несколько раз как Apple, так и Google. При нашей максимальной скорости мы обрабатываем 30 000 новых регистраций в день. Наша конфигурация MongoDB легко справляется с этой нагрузкой. На самом деле, с точки зрения масштаба и схемы, наше развертывание довольно скучно и по книге.
Музыкальная карта
Одна из наиболее привлекательных особенностей Soundwaves — это Music Map. Наши пользователи могут нарисовать произвольный многоугольник на карте Google в любой области с любым уровнем масштабирования и посмотреть, какая музыка недавно воспроизводилась в этой области. Это запечатлено на скриншоте ниже. Эти ограничения требовали некоторого интересного конструирования, выходящего за рамки книги MongoDB.
Мы отчасти гордимся нашей реализацией. Многие приложения, учитывающие местоположение, с похожими функциями уменьшают взаимодействие с пользователем до некоторой формы круговой $ geoNear вокруг точки. На наш взгляд, это не так интересно, как случайным образом нарисованный многоугольник, и при этом это не очень хороший пользовательский интерфейс, чтобы обещать многоугольники и возвращать какое-то другое приближение того, что хотел пользователь.
Ограничения
Мы установили целевую максимальную задержку 95-го процентиля в 1,5 секунды для объекта карты. С точки зрения клиента, мы решили, что все это время ожидания просто скучно для пользователя. Мы обнаружили, что пользователи выполняют поиски, которые либо уменьшены, как в Ирландии, либо уменьшены, как в Landsdowne Road.
По многим причинам у нас есть кластеры данных вокруг определенных областей. В больших городах обычно много точек с высокой плотностью данных, но некоторые города представлены лучше, чем другие. Это затрудняет количественное определение довольно увеличенного и довольно увеличенного. Из этого также следует, что уровень масштабирования карты несколько бесполезен в качестве данных для оптимизации. Мы хотели, чтобы все наши данные о местоположении были доступны пользователю — в Антарктиде есть несколько пьес, но они произошли некоторое время назад — было бы стыдно сократить время поиска по времени и пропустить это.
Схема Дизайн
Наше развертывание содержит около 90 миллионов игровых действий, каждое из которых представлено одним документом. Для любого взаимодействия с приложением, например, для захвата игры, существует связанная гео-координата и документ. Наша первая реализация этой функции использовала двухмерный индексный тип с устаревшей точкой данных местоположения, связанной с каждым документом действия.
{
actionType : "PLAY",
..
location : { lon : Double , lat : Double },
time : ISODate(..)
}
Таким образом, наш гео-запрос принял форму оператора $ inside с использованием многоугольника, построенного из точек в произвольной форме перетаскиванием пальца.
db.action.find({ location: { $geoWithin: { $polygon:
[ [ -5.577327758073807, 53.92722913826002 ],
[ -5.628384947776794, 53.94341400538505 ],
..
[ -7.603911347687244, 53.48786460176994 ] ] }
}
}).limit(1000).sort( "time": 1});
Индекс поддержки был построен следующим образом.
db.location.ensureIndex({ location : "2d", time : 1 })
Это на самом деле работало довольно хорошо из коробки. Для устаревших запросов MongoDB $ в пределах не слишком суетлив относительно самопересекающихся, и при этом это не заботится об уникальности каждой точки, или полноте многоугольника.
Запрос, однако, был собачьим. Для плотных областей с масштабированием по размеру города мы не могли получить время ответа меньше нескольких секунд для наших запросов. Для областей, где происходило значительное количество игр, намеки на индекс времени действия выполнялись намного лучше, чем 2d во всех случаях.
Для областей с низкой активностью эта стратегия не сработала особенно хорошо. Поиск по шкале страны или континента не завершился за разумное время — 10 секунд — и начал влиять на задержку в других частях приложения. Объяснение MongoDB показало сканирование более половины, если не больше, записей в коллекции для поиска по размеру города, но также подтвердило, что использовался двумерный индекс. Это привело нас к выводу, что 2-й индекс может быть недостаточно мощным для наших нужд.
Миграция в GeoJSON & 2dsphere
После некоторых советов от сообщества MongoDB и перехода на MongoDB 2.4 мы решили перейти к индексу 2dsphere. Это потребовало переделки нашей схемы и доработки нашего механизма запросов. Во-первых, нам были нужны очки GeoJSON.
{
"location" : {
"type" : "Point",
"coordinates" : [ Double, Double ]
}
}
Следующий индекс
db.action_loc.ensureIndex({ location : "2dsphere", time : 1 })
Оповещения читателей заметят появление новой коллекции action_loc, в нашей схеме. Индексы 2dsphere версии 2.4 не учитывают свойство разреженности, но это было изменено в версии 2.6 . Примерно 65% нашей коллекции действий состоит из документов, которые не имеют соответствующего местоположения.
Создание индекса 2dsphere для actionколлекции приводит к 57 миллионам документов, индексируемых на месте без каких-либо преимуществ. На практике это привело к индексу размером примерно 10 ГБ. Перемещение в коллекцию, где все записи имели местоположения, привело к уменьшению размера индекса на 7,3 ГБ. Учитывая, что чтения доминируют над записями в нашем приложении, мы были рады взять на себя задержку одной дополнительной записи за игру в action_locколлекцию, когда местоположение доступно для определенных действий.
Поддержка GeoJSON имеет некоторые более жесткие ограничения для запросов. Не может быть повторяющихся точек. Полигоны должны образовывать замкнутое линейное кольцо. На практике наше клиентское приложение иногда создавало несколько точек, т. Е. Когда многоугольник сам пересекался, и никогда не обеспечивало замкнутого линейного кольца. Наконец, самопересекающиеся многоугольники, которые являются обычным побочным эффектом рисования в свободной форме и интересного случайного поиска, не принимаются. Технически, самопересекающийся многоугольник можно рассматривать как геометрию, содержащую n различных непересекающихся многоугольников, множественные геометрии многоугольников не поддерживаются в MongoDB 2.4, но были добавлены в 2.5.1 .
Библиотека JTS Java помогла нам исправить все это на уровне приложений. Дедупликация и замыкание линейных колец было тривиальным, однако поддерживать самопересекающиеся многоугольники было немного сложнее. Окончательное решение заключалось в вычислении выпуклой оболочки поискового многоугольника. Это гарантировало замкнутое линейное кольцо вокруг любой геометрии многоугольника, что исключало возможность самопересечения. Однако, как показано на рисунке выше, это приводит к большему набору результатов, чем предполагалось.
Вместо того, чтобы показывать эти моменты и вводить пользователя в заблуждение, мы отбираем их из ответа. Это сохраняет опыт пользователей ограничивающего прямоугольника, к которому мы стремились. Другими словами, пользователи получают то, что ожидают. Что касается потерянных ресурсов, это не идеально в теории, но хорошо работает на практике. Пользователи обычно рисуют самопересекающиеся многоугольники случайно 3 . 2-й многоугольник обычно на порядок меньше, чем больший из двух образующихся многоугольников. Следовательно, потраченное впустую пространство поиска обычно невелико.
После миграции поиски на уровне города и улицы были на порядок быстрее при получении результатов. Мы связываем это с индексом 2dsphere и курсором s2. Тем не менее, все еще оставалось то, что поиск с низким уровнем масштабирования на уровне штатов и стран увеличил задержку 95-го процентиля в среднем до 1,5 секунд и часто был крайне медленным для пользователя.
оптимизация
Мы ограничиваем результаты поиска музыкальной карты до 100 пьес. Если их более 100, мы показываем 100 самых последних.
В запросах с низким уровнем масштабирования обычно преобладают игры, которые произошли недавно. Тесты показали, что для глобальных поисков с низким уровнем масштабирования обратный индекс времени был намного быстрее при поиске записей, чем индекс 2dsphere. Поэтому мы создали два индекса местоположения, один из которых основан на времени, а другой — 2dsphere.
Однако, по нашему опыту, планировщик запросов MongoDB всегда выбирал индекс 2dsphere по сравнению с основанным на времени индексом для запросов $ geoWithin, даже когда тесты показали, что основанный на времени индекс обеспечит более быстрые результаты в конкретном случае.
Планировщик запросов MongoDB работает, периодически используя несколько индексов параллельно и выясняя, какой из них возвращается быстрее. Проблема в том, что в большинстве случаев правильный ответ — использовать индекс 2dsphere, а MongoDB только периодически переоценивает этот выбор. Если лучший выбор индекса варьируется для двух запросов, имеющих одинаковую подпись, MongoDB будет делать неправильный выбор в течение определенного процента времени. MongoDB делает выбор индекса, который работает чаще, чем нет, но оставляет оставшиеся случаи неприемлемо медленными.
Некоторое соединение полигональной области и предварительно сгенерированных метрик плотности точек данных для этой области было изучено, но было быстро отменено из-за сложности реализации.
Наконец была использована простая стратегия параллельного выполнения. Мы выполняем запрос двумя способами, параллельно: один запрос указывает на индекс 2dsphere, другой — на временной индекс. Победителем является запрос, который возвращает результаты быстрее всего. Если проигравший работает дольше 10 секунд, он принудительно убивается, чтобы сохранить потраченные впустую ресурсы.
В процессе работы мы обнаружили, что если мы не уничтожим длительные спекулятивные запросы, результирующая нагрузка на базу данных отрицательно скажется на задержке чтения для других запросов и, следовательно, на восприятии пользователем.
В MongoDB 2.6 можно установить пользовательский лимит времени для запросов, поэтому этого шага можно избежать. На момент написания этой статьи мы не использовали эту функцию в производственном процессе, и нам был нужен рабочий Javascript, который периодически прерывал запросы к коллекции, выполняющейся в течение 10 секунд. Функция ниже.
function cleanUpLong(max_running_secs) {
var currentOps = db.currentOp({
$and: [{ op: "query" },
{ msg: { $exists: false } }, // not a sharding operation!
{
secs_running: { $gt: max_running_secs }
},
{"ns": "backstage.action_loc" }]
});
currentOps.inprog.forEach(function (op) {
db.killOp(op.opid)
})
}
Некоторое внимание необходимо уделить тому, чтобы длительные операции над коллекцией не были связаны с перераспределением фрагментов по частям.
Объясняя результаты
В процессе производства наш обратный временной индекс превосходит наш 2dsphere примерно в третью часть времени, как правило, для довольно масштабных поисков. Интуитивно это имеет смысл, поскольку континент большой и охватывает значительную часть географического пространства. Например, если вы оцениваете 1000 самых последних элементов, 100 из них, вероятно, также будут соответствовать вашему географическому ограничению, если ваше географическое ограничение равно размеру континента.
Использование $ geoWithin при очень небольшом уменьшении работает плохо. Опять же, глядя на пример континента, по крайней мере, 10% всех игр, вероятно, находятся на континенте, но, поскольку мы хотим возвращать только самые последние данные, мы будем отбрасывать почти все данные, которые мы извлекаем из базы данных при поиске. для самых последних данных с континента.
В первом примере [Табл. 1], индекс 2dsphere выигрывает с огромным отрывом. Ячейки, охватываемые областями, которые рассматриваются в запросе, не имеют очень много недавних воспроизведений по сравнению с глобальным набором последних воспроизведений. Следовательно, потоку, использующему индекс времени, нужно работать намного больше, чтобы заполнить 100-контактный сегмент с глобальной точки зрения, сканируя в 40 раз больше записей для выполнения той же работы. Между тем, запрос, использующий индекс 2dsphere, обнаруживает, что относительно высокая доля воспроизведения, которая удовлетворяет географическому ограничению, также удовлетворяет ограничению по времени.
Во втором примере [Табл. 2], вероятность того, что недавняя игра также географически совместима, высока, в результате чего индекс, основанный на времени, удобно выигрывает, сканируя половину записей 2dsphere и возвращая нас к нашему желаемому пределу задержки.
Повторим, мы всегда используем результат более быстрого запроса. Результат более медленного запроса отбрасывается, если он возвращается до уничтожения. Спекулятивно идя по пути обоих запросов, мы можем вернуть результат пользователю в рамках наших требований без анализа запроса и его параметров. Нам не нужно понимать, уменьшен ли он или увеличен.
Параллельное использование индекса
На рисунке ниже показаны запросы за несколько дней и соответствующий индекс. Точки данных были построены как для выигрышных, так и для проигрышных запросов. Для многих из показанных точек результаты не использовались в ответах пользователей, но в любом случае измерялась задержка.
График служит для того, чтобы показать, что именно комбинация индексов, то есть красная и зеленая точки, ответственны за задержку p95, показанную на рисунке ниже. Более того, он примерно показывает, как может повлиять p95, если мы используем только один из рассматриваемых индексов. Кроме того, соотношение поисков 2dsphere и поисков по времени может быть получено более грубо.
Мы обрабатываем примерно 0,4 поиска карт в среднем за секунду. Время отклика p95 значительно меньше 1,5 секунд. Мы можем достичь этих результатов, хотя каждый запрос мы выполняем двумя способами, до 10 секунд. График, показанный ниже, показывает эти результаты за неделю в марте.
Вывод
Функция гео-поиска MongoDB обеспечивает одну из самых уникальных функций Soundwave: Music Maps. Музыкальная карта является одной из основных причин, по которой мы выбрали MongoDB в качестве основного хранилища данных.
По сравнению со старыми функциями, такими как автоматическая перегруппировка и агрегирование сегментированных кластеров, гео-поиск и вспомогательная документация все еще несколько незрелы. Тем не менее, с некоторой дополнительной работой нам удалось создать довольно сложную функцию поиска без необходимости развертывания отдельного стека ГИС.
Более того, стратегия MongoDB по включению библиотеки S2 и большего количества геометрий GeoJSON дает нам уверенность в том, что мы можем легко использовать нашу карту, сейчас и в будущем. Это позволяет нам сохранять осознание местоположения спереди и по центру в качестве функции нашего приложения. Надеемся, что эта статья прояснит некоторые болевые точки для пользователей, реализующих аналогичные функции.
сноски
1. Soundwave доступен для iOS и Android. Подробности установки на http://www.soundwave.com
2. Используем большие экземпляры r3.4. 3. Мы наблюдали запросы на самопересекающихся многоугольниках примерно половину времени. Это в основном случайность; трудно нарисовать точное линейное кольцо пальцем. Однако иногда люди просто хотят нарисовать цифры 8.