Привет, меня зовут Надежда и я 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. Это хорошо работает на небольших объемах данных, но когда у вас миллионы записей и миллионный сдвиг, это может быть накладно и долго, что уже большой минус для аудиостриминга. А если полученный ответ придётся ещё и фильтровать в другом сервисе?

Проблема, с которой столкнулись

Итак, дано: два сервиса, один из которых отдаёт мета-информацию релизов, второй фильтрует полученный результат по огромному количеству критериев, индивидуальных для каждого пользователя. Помните, я в начале писала про фильтрацию? Порядок вызовов следующий:

1. Клиенты (дальше под клиентами я буду иметь в виду web, iOS, Android)  отправляют запрос на получение N релизов.

2. Сервисы с метой достаёт из БД N релизов.

3. Сервис с фильтрацией отфильтровывает часть релизов и отдаёт M релизов, где M <= N.

4. Клиенты получают M релизов.

А что же происходит дальше?

Пришедшие M релизов — это все релизы, которые есть в базе? Или клиентам необходимо запросить ещё сколько-то релизов? А как понять, сколько? А если делать ещё один запрос, то как рассчитать, какой offset ставить?

В итоге получалось плохо всем: клиенты не могли понять, когда им стоит дозапрашивать данные, поддержка страдала от запросов пользователя «не хватает релизов, в поиске их больше», Backend и QA регулярно отбивались от свежезаведённых багов и были вынуждены тратить время, чтобы объяснить коллегам, что функционал работает корректно. Однажды терпение нашей команды кончилось и мы сели думать.

Варианты решения

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

Но это требовало бы переписать всю архитектуру Звука, ведь вокруг сервиса фильтрации и сервиса мета-информации существует огромное количество других сервисов.

Поэтому нам пришлось искать другие решения.

Вариант 1

Первым решением была идея забирать из БД бОльшее количество релизов, чем указано в limit, например, limit * 2. Затем сравнивать, сколько релизов было запрошено и сколько осталось после фильтрации. После этого либо снова идти в базу, если релизов недостаточно, либо отсекать ненужное. 

Проблема этого решения в том, что уследить за параметром offset (на сколько мы сдвинулись относительно начала) невозможно.

Поэтому мы перешли ко второму варианту.

Вариант 2

Если после первой фильтрации релизов у нас отобралось что-то лишнее, мы забываем про то, что уже ходили в базу и берём limit * K релизов. С каждой итерацией цикла планировалось, что K будет увеличиваться, пока наконец мы не наберём нужное количество отфильтрованных релизов.

Здесь всё также упиралось в то, что offset вычислить невозможно.

На этом этапе работ я закопалась в статьи по пагинации и принесла в команду на обсуждение одну идею.

Вариант 3

Этот подход кардинально отличался от всех предыдущих. Мы запоминали, какой id релиза отдали последним, и при запросе следующей страницы отталкивались от него. 

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

Работа с курсорной пагинацией

Что такое курсорная пагинация в БД?

Представьте себе запрос

SELECT * FROM releases WHERE id > 1000 LIMIT 10 ORDER BY popularity, id;

Чтобы выполнить этот запрос, нам не понадобиться вычислять и держать в памяти все 1010 записей, как с limit/offset. Благодаря фильтрации по первичному ключу запрос выполняется намного быстрее.

Чтобы получить следующую страницу, мы запоминаем id последней записи и начинаем фильтровать запрос с этого id. 

Поскольку в запросе мы отдавали отсортированные по популярности данные, этот метод выглядел интересно. Да, мы по-прежнему отдавали бы меньшее количество релизов, чем от нас ждали, но уже могли решить проблему «откуда стартовать при следующем запросе».

А почему бы не совместить два способа?

Мы можем запрашивать N*2 релизов, отфильтровывать их, возвращать в качестве результата id последнего релиза. 

Но это не отменяет того, что нам очень хотелось отдавать клиентам именно запрошенное число релизов. Идея дополнительных запросов витала в воздухе. В итоге после коллективного мозгового штурма мы решили рискнуть.

Окончательный вариант, который должен был уехать на нагрузочное тестирование, выглядел так: 

1. Клиенты запрашивают N релизов.

2. Мы делаем в базу запрос N*2 релизов.

3. Запоминаем последний id релиза, отправляем на фильтрацию.

4. Смотрим, сколько треков нам приходит. Если их число меньше нужного, то снова идем в базу и вытаскиваем N*2 релизов, начиная с запомненного id.

5. Снова отфильтровываем и повторяем цикл, пока не наберем нужное количество + 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

Итоговая реализация:

Response Time Statistics

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

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

В итоге так и было сделано, а мобилки и веб успешно переехали на новую ручку.

Конечно, у этого решения есть и минусы:

• Время ответа ручки складывается из быстрых, но всё-таки нескольких запросов в базу.

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

Спустя какое-то время мы обнаружили, что коллеги в других командах Backend-разработок нашей компании начали использовать этот же подход. Тут мы поняли, что пришли к одному из лучших решений этой проблемы.

А вам приходилось сталкиваться с динамической фильтрацией? Какими способами вы решали похожие проблемы? Буду рада, если поделитесь своим опытом в комментариях!