![](https://habrastorage.org/getpro/habr/upload_files/d92/a47/eca/d92a47eca05808186043b1db286cf8b3.png)
Привет, меня зовут Надежда и я Backend-разработчик в HiFi-стриминге Звук! Занимаюсь всем, что связано с подкастами и немузыкальным контентом (а вы знаете, что в Звуке есть аудиокниги? Разработка нашей команды! PodcaTS, привет!). Какое-то время я также техлидила сервисы, которые отвечали за отдачу мета-информации и всего, что связано с аудио (артисты, релизы, треки, подкасты, аудиокниги) в Звуке.
В процессе работы нашей команде пришлось споткнуться о проблему динамической фильтрации. Сначала мы получали данные, потом их фильтровали, но не знали, сколько отдадим в итоге. Для Звука и отдачи мета-информации эта проблема оказалась очень актуальной.
В русскоязычном сегменте IT то ли никому не приходилось сталкиваться с этой ситуацией, то ли никто не выносил её на обсуждение, поэтому это решили сделать мы. Хочется поделиться своим опытом, помочь кому-то с аналогичными проблемами, а, может, и похоливарить на тему того, как ещё эту проблему можно решить.
Рассмотрим продуктовую задачу: отобразить в мобильном приложении или на вебе на странице артиста все его релизы. Релизов может быть много: сотни и тысячи. Под капотом для выполнения этой задачи в Звуке есть множество сервисов, но нам важны два из них: один отдаёт мета-информацию о треках, релизах и артистах, а второй — фильтрует полученные данные.
Что чаще всего приходит в голову, когда мы слышим термин “фильтрация”? Фильтр для воды WHERE
в SQL, filter
в Django и SQLAlchemy, то есть фильтрация, напрямую связанная с sql-запросами.
Но фильтрация ведь бывает не только в запросах.
Иногда приходится выполнять фильтрацию данных, уже полученных из БД. А если данных много?
Тут я хочу сделать небольшое отступление и немного рассказать про Звук.
Звук — аудиостриминг, использующий микросервисную архитектуру. Контент доступен для стриминга в зависимости от наличия подписки: подкасты можно слушать без неё, а вот чтобы послушать треки полностью, подписка уже понадобится. Кроме наличия подписки на контент влияют ограничения от правообладателя.
Критериев для фильтрации много, очень много — их все нужно учитывать.
И контента тоже… много.
А раз контента много, то получать его одним запросом может быть тяжело и долго. Мы же не хотим, чтобы наши плейлисты, в которых может быть несколько сотен треков, грузились дольше пары секунд?
Поэтому для запросов контента мы используем пагинацию — разделение получения контента на отдельные страницы или постраничную выборку.
Работа с оффсетной пагинацией
Что такое постраничная выборка?
Чаще всего, когда мы делаем запрос в базу, мы используем параметры limit
и offset
. Limit
отвечает за то, сколько итоговых строк мы получим, offset
— за сдвиг строк относительно начала. То есть, когда мы выполняем запрос
SELECT * FROM releases LIMIT 10 OFFSET 1000 ORDER BY popularity, id;
базе необходимо отсортировать, вычислить эти 1010 строк и отдать последние 10. Это хорошо работает на небольших объемах данных, но когда у вас миллионы записей и миллионный сдвиг, это может быть накладно и долго, что уже большой минус для аудиостриминга. А если полученный ответ придётся ещё и фильтровать в другом сервисе?
Проблема, с которой столкнулись
Итак, дано: два сервиса, один из которых отдаёт мета-информацию релизов, второй фильтрует полученный результат по огромному количеству критериев, индивидуальных для каждого пользователя. Помните, я в начале писала про фильтрацию? Порядок вызовов следующий:
Клиенты (дальше под клиентами я буду иметь в виду web, iOS, Android) отправляют запрос на получение
N
релизов.Сервисы с метой достаёт из БД
N
релизов.Сервис с фильтрацией отфильтровывает часть релизов и отдаёт
M
релизов, гдеM <= N.
Клиенты получают M релизов.
А что же происходит дальше?
Пришедшие M
релизов — это все релизы, которые есть в базе? Или клиентам необходимо запросить ещё сколько-то релизов? А как понять, сколько? А если делать ещё один запрос, то как рассчитать, какой offset
ставить?
![](https://habrastorage.org/getpro/habr/upload_files/080/b8f/8cf/080b8f8cf92d2598787d5f1357ba3f8f.jpg)
В итоге получалось плохо всем: клиенты не могли понять, когда им стоит дозапрашивать данные, поддержка страдала от запросов пользователя «не хватает релизов, в поиске их больше», Backend и QA регулярно отбивались от свежезаведённых багов и были вынуждены тратить время, чтобы объяснить коллегам, что функционал работает корректно. Однажды терпение нашей команды кончилось и мы сели думать.
Варианты решения
Самым надежным и правильным способом было бы изменить порядок вызовов сервисов: сначала получать из сервиса фильтрации релизы, которые гарантировано подойдут текущему пользователю, а уже потом доставать для них мета-информацию.
![](https://habrastorage.org/getpro/habr/upload_files/1b6/1af/c8f/1b61afc8fd9bd35cc5b799dbf3636119.jpg)
Но это требовало бы переписать всю архитектуру Звука, ведь вокруг сервиса фильтрации и сервиса мета-информации существует огромное количество других сервисов.
Поэтому нам пришлось искать другие решения.
Вариант 1
Первым решением была идея забирать из БД бОльшее количество релизов, чем указано в limit
, например, limit * 2
. Затем сравнивать, сколько релизов было запрошено и сколько осталось после фильтрации. После этого либо снова идти в базу, если релизов недостаточно, либо отсекать ненужное.
Проблема этого решения в том, что уследить за параметром offset
(на сколько мы сдвинулись относительно начала) невозможно.
Поэтому мы перешли ко второму варианту.
Вариант 2
Если после первой фильтрации релизов у нас отобралось что-то лишнее, мы забываем про то, что уже ходили в базу и берём limit * K
релизов. С каждой итерацией цикла планировалось, что K
будет увеличиваться, пока наконец мы не наберём нужное количество отфильтрованных релизов.
Здесь всё также упиралось в то, что offset
вычислить невозможно.
На этом этапе работ я закопалась в статьи по пагинации и принесла в команду на обсуждение одну идею.
Вариант 3
Этот подход кардинально отличался от всех предыдущих. Мы запоминали, какой id
релиза отдали последним, и при запросе следующей страницы отталкивались от него.
Да, в основе этого метода лежит курсорная пагинация, которая часто применяется в запросах к базам данных. Но почему бы не распространить хорошую практику?
![](https://habrastorage.org/getpro/habr/upload_files/de2/70e/8ad/de270e8ad716b46a575024b0b96f945d.jpg)
Работа с курсорной пагинацией
Что такое курсорная пагинация в БД?
Представьте себе запрос
SELECT * FROM releases WHERE id > 1000 LIMIT 10 ORDER BY popularity, id;
Чтобы выполнить этот запрос, нам не понадобиться вычислять и держать в памяти все 1010 записей, как с limit/offset
. Благодаря фильтрации по первичному ключу запрос выполняется намного быстрее.
Чтобы получить следующую страницу, мы запоминаем id
последней записи и начинаем фильтровать запрос с этого id
.
Поскольку в запросе мы отдавали отсортированные по популярности данные, этот метод выглядел интересно. Да, мы по-прежнему отдавали бы меньшее количество релизов, чем от нас ждали, но уже могли решить проблему «откуда стартовать при следующем запросе».
А почему бы не совместить два способа?
Мы можем запрашивать N*2
релизов, отфильтровывать их, возвращать в качестве результата id
последнего релиза.
Но это не отменяет того, что нам очень хотелось отдавать клиентам именно запрошенное число релизов. Идея дополнительных запросов витала в воздухе. В итоге после коллективного мозгового штурма мы решили рискнуть.
Окончательный вариант, который должен был уехать на нагрузочное тестирование, выглядел так:
Клиенты запрашивают
N
релизов.
Мы делаем в базу запрос
N*2
релизов.
Запоминаем последний
id
релиза, отправляем на фильтрацию.
Смотрим, сколько треков нам приходит. Если их число меньше нужного, то снова идем в базу и вытаскиваем
N*2
релизов, начиная с запомненногоid
.
Снова отфильтровываем и повторяем цикл, пока не наберем нужное количество + 1 (почему +1 расскажу чуть ниже), либо пока не сходим за донабором пять раз. Количество попыток донабора было выбрано эмпирическим путем, потому что для большинства артистов этого должно было хватить.
Почему стали запрашивать на 1 релиз больше, чем нужно? Мы хотели выяснить, надо ли будет клиентам (web, iOS, Android) делать запрос, чтобы получить следующую страницу.
Если в БД есть хотя бы одна «лишняя» запись, то клиентам мы отдаём признак наличия следующей страницы has_next_page=True
, в противном случае — has_next_page=False
.
Окончательная структура ответа метода приняла следующий вид:
{
"page_info": {
"has_next_page": true,
"end_cursor": "eyJkYXRlIjoyMDIyMTExOCwicmVsZWFzjc2MDk2MTh9",
},
"releases": [
{
"release_id": 100,
"date": 20200102
},
{
"release_id": 101,
"date": 20200101
}
]
}
Обсудив с фронтами, мы реализовали этот способ на бэке, и с нетерпением стали ждать результатов нагрузочного тестирования.
Результаты НТ нас обнадежили. Много мелких запросов в базу переносились сервисом лучше, чем один тяжелый, а время ответа ручки оказалось даже быстрее исходного!
Как это было реализовано?
Исходная реализация, с недобором треков:
Response Time Statistics
50%ile (ms) |
95%ile (ms) |
99%ile (ms) |
100%ile (ms) |
|
Релизы для артистов (юзер из Франции) |
430 |
1000 |
2200 |
4500 |
Релизы для артистов (юзер из РФ) |
420 |
1000 |
2500 |
4300 |
Aggregated |
620 |
1700 |
3600 |
9500 |
Итоговая реализация:
Response Time Statistics
50%ile (ms) |
95%ile (ms) |
99%ile (ms) |
100%ile (ms) |
|
Релизы для артистов (юзер из Франции) |
320 |
760 |
1900 |
3400 |
Релизы для артистов (юзер из РФ) |
320 |
750 |
1900 |
3400 |
Aggregated |
390 |
980 |
2000 |
4300 |
Видно, что время выполнения запросов в новой реализации оказалось быстрее, чем в исходной. Мы не только решили проблему с недобором, но и немного ускорили получение мета-информации по релизам!
Основной проблемой оставалось то, что команда не могла внести изменения в уже имеющуюся ручку, потому что ломалась обратная совместимость: новый способ требовал от клиентов отправлять другой набор параметров, а от бэка, соответственно, менять структуру ответа. Но, поскольку мобилки тоже страдали от недобора, коллективным разумом было принято решение делать новый метод на бэке, а фронты и веб уже должны были перейти на него сами.
В итоге так и было сделано, а мобилки и веб успешно переехали на новую ручку.
Конечно, у этого решения есть и минусы:
Время ответа ручки складывается из быстрых, но всё-таки нескольких запросов в базу.
Мы всё равно можем недобрать релизы в случае, если у артиста есть большой блок идущих подряд релизов, которые будут отфильтрованы (например, 10 релизов прошли фильтрацию, 1000 нет, но за этой тысячей релизов есть ещё сколько-то, которые могут пройти фильтрацию. Однако, это редкий случай и осознанный риск, на который мы пошли).
Спустя какое-то время мы обнаружили, что коллеги в других командах Backend-разработок нашей компании начали использовать этот же подход. Тут мы поняли, что пришли к одному из лучших решений этой проблемы.
![](https://habrastorage.org/getpro/habr/upload_files/bef/c0a/b70/befc0ab70b4119eb72bf3f937069fc5b.png)
А вам приходилось сталкиваться с динамической фильтрацией? Какими способами вы решали похожие проблемы? Буду рада, если поделитесь своим опытом в комментариях!
Комментарии (12)
devlev
30.07.2024 07:17На самом деле проблемы оффсетной пагинации куда глобальнее чем кажутся на первый взгляд. Предположим мы уже отфильтровали данные и показали их клиенту. Пока клиент смотри на эти данные были добавлены новые записи в первую страницу. Тогда произойдет сдвиг данных и на второй странице возможно окажутся те же записи, что были и на первой. А если на UI стороне отображение реализовано в виде авто подгрузке по доскролу то клиент увидит задвоение некоторых данных. Курсорная пагинация не обладает подобной проблемой. Новые записи которые были добавлены на первую страницу вообще не попадут в выдачу клиента, до обновления первой страницы.
В одном из проектов как раз реализовывал подобную курсорную пагинацию правда она там была в обе стороны. Обычно при долгой прокрутке страницы, с доскролом, на странице начнет отображаться так много записей что сама страница начнет тормозить и подлагивать. Чтобы этого избежать курсорная подгрузка реализована в обе стороны: при подгрузке третей и более страницы верхние данные удаляются. И наоборот. При прокрутке на верх подгружаются записи которые были удалены ранее, а снизу записи стираются.
А как сделано у вас. Курсоры в обе стороны или только в одну?
jeroyle Автор
30.07.2024 07:17+1Сейчас у нас курсоры только в одну сторону, так как в обратную пока не было необходимости. Но технически мы это возможность для клиентов (веб, ios, android) рассматривали и учитывали, поэтому добавить её будет не сложно
krioz
30.07.2024 07:17Так в оффсете запомните id/прочее первого элемента и передавайте его в lte/gte фильтр. Проблема только если внутри выборки меняются данные что влияет на порядок сортировки
kacetal
30.07.2024 07:17+1Самое интересное в такой пагинации это составные индексы с указанием сортировки индекса. За счёт чего и получается быстро находить нужную точку. К сожалению об этом ничего не написано.
Andrey_Solomatin
30.07.2024 07:17Снова отфильтровываем и повторяем цикл, пока не наберем нужное количество + 1 (почему +1 расскажу чуть ниже), либо пока не сходим за донабором пять раз. Количество попыток донабора было выбрано эмпирическим путем, потому что для большинства артистов этого должно было хватить.
При этом в итоге можно получить 0 записей.
Решение которое будет идеально для пользователя это загнать всё в одну базу. Это может быть дополнительная база, которая хранит копию данных предназначенную именно для этих запросов. Если фильтры редко меняются, то можно посмотреть на nosql решения, где можно положить все поля для фильтрации в один документ например OpenSearch.
Для компании такое решение не бесплатное. Нужно много места и новый сервер(ы), проблемы поддержания данных в актуальном состоянии (новые треки найдутся не сразу), ну и работа разработчиков.
olivera507224
Довольно странно в статье, в названии которой прямо фигурирует курсорная пагинация, не найти ни одного упоминания курсорной пагинации.
Gromilo
Вы про курсоры в БД?
olivera507224
Да, из названия ожидаешь прочитать историю внедрения курсорной пагинации, но в тексте речь идёт о пагинации на основе упорядоченного набора ключей.
И совсем не ясно, какие фильтры вы применяете к полученным из БД данным, что эти фильтры нельзя применить на уровне самой БД. Вот это было бы действительно интересно.
Gromilo
Если честно, разницы всё равно не понял.
Вот курсорная пагинация в ларавел: на фронт отдаём строку с курсором, а по факту это тот же упорядоченных набор ключей:
where id > 15 order by id asc limit 15.
Можно пример чем курсорная пагинация отличается от "на основе упорядоченного набора ключей"?
P.S. я не автор и мне самому интересно почему фильтрация не в бд.
olivera507224
Возможно, у нас возникло недопонимание и расхождение в трактовании термина. Под курсором я однозначно понимаю поименованную область памяти, содержащую результирующий набор селект-запроса.
Просмотрел ссылку, которую вы скинули, и таки да - всё встало на свои места. Ларавель, похоже, называют курсорной пагинацией как раз пагинацию по упорядоченному набору ключей, просто в параметрах запроса вместо страницы нужно передавать зашифрованную строку, которую они называют курсором. Интересно, АпиПалтформа тоже под курсором понимают не курсор в БД?
Сорри, почему-то я решил что статься ваша :)
jeroyle Автор
Вы приводите ссылку на Laravel и курсорную пагинацию в нём же. Наша реализация сделала примерно по такому же принципу, но на Python (в силу языка мы не можем использовать Laravel). Насчет
К сожалению, фильтровать данные на уровне самой БД нам на текущий момент не позволяет архитектура приложения