Как объединить списки, полученные от 2 REST API с параметрами `limit` и `offset`, и вернуть его, согласно параметрам `limit` и `offset`?

Question

[uhamurad]

Коротко

Как объединить списки, полученные от двух REST API с параметрами `limit` и `offset`, и вернуть объединенный список в результате вызова 3-го REST API также с параметрами `limit` и `offset`?

Подробно

Есть эндпоинты 2 REST API:

GET api-1/events? limit=10 & offset=20
GET api-2/events? limit=10 & offset=20

Которые возвращают упорядоченные по дате списки, например:

api-1:
[
    { "date": "2024-02-11", "text": "magna aliqua" },    
    { "date": "2024-02-10", "text": "enim ad minim" },
    ...    
    { "date": "2024-02-01", "text": "quis nostrud" }  
]

api-2:
[
    { "date": "2024-02-11", "text": "exercitation ullamco" },    
    { "date": "2024-01-11", "text": "laboris nisi" },
    ...    
    { "date": "2023-04-11", "text": "aliquip ex" }  
]

Нужно написать эндпоинт для 3-го REST API:

GET api-3/events? limit=10 & offset=20

Который возвращает упорядоченный по дате список - объединиение результатов вызовов "GET api-1/events" и "GET api-2/events".

Проблема имеет простое решение для первой страницы (когда `offset=0`), но для последующих страниц приходится делать много запросов к `api-1` и `api-2`.

Вопросы

1. Есть ли у проблемы общеизвестное название? Я бы погуглил его, чтобы приблизится к правильному решению.
2. Как разработать `api-3`, чтобы он работал достаточно оптимально:
- оставалась возможность отправлять запросы API к `api-1` и `api-2` параллельно

У меня есть доступ и возможность изменить порядок работы `api-1`, `api-2` и `api-3`. Например, я склоняюсь к тому, чтобы заменить параметры "order" и "offset" параметрами "dateFrom" и "dateTo". Это решит проблему слияния, но появятся другие проблемы - уже на стороне клиента API, чего не хотелось бы.

Answer 1

[Rsa97]

Разобраться в коде двух уже существующих методов и написать третий, работающий самостоятельно, без обращения к двум первым.

Comments

[uhamurad]

Хорошо бы, но они работают на 2 разных серверах со своими бизнес-правилами и отращаются к двум разным БД

[Rsa97]

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

Answer 2

[Wataru]

Согласен с Rsa97, лучше всего написать новый метод без обращения к этим АПИ, а напрямую работающий с их источниками.

Но, если вам надо обязательно вот так извращатся, то это практически задача с leetcode: https://leetcode.com/problems/median-of-two-sorted...

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

У вас же тут надо не медиану найти, а k-ый элемент.
У вас тут фактически дано 2 массива API1 и API2. Чтобы прочитать один (или несколько) элементов вам надо сделать запрос к АПИ.

Вам надо найти offset-ый, offset+1 и т.д элементы в объедененном массиве.
Для начала просто найдите offset-ый элемент. Зная его позиции в обоих массивах сделайте 2 запроса с этих
позиций и данным limit. Потом как в задаче о слиянии двух массивов выведите первые limit.

Во время бинпоиска делайте запросы с limit=1, а offset = индекс в массиве.

Update:
Забыл написать, тут у вас будет что-то около 2*log(offer+limit) запросов с limit=1 к разным апи, и потом еще 2 запроса с limit=limit из общего запроса.

Comments

[uhamurad]

Большое спасибо за подробное разъяснение!

Боюсь такой подход будет слишком дорогим по запросам. Буду искать обходные пути.

Скорее всего, переведу работу с АПИ на запросы по датам "от-до"

[Wataru]

uhamurad, всмысле, долгим по запросам? Там логарифм же! Для offset=1024 будет 20 запросов. Если подумать, то можно в конце вместо кучи запосов с limit=1 сделать один с limit=100. Тогда для offset=1000 будет всего 8 запосов. Для offset=100000 - всего 20 запросов.

Так-то, если у вас offset небольшие, то просто спросите оба api с offset=0, limit=limit+offset. И потом руками в памяти сливайте 2 отсортированных массива.

Если переведете на даты, то можете в запросе сдучайно всю базу данных за раз запросить.

[uhamurad]

Wataru, добавлю немного контекста:

• Конечный клиент api-1 и api-2 - мобильное приложение, у которого список сущностей реализован как бесконечная лента, которую нужно "тянуть пальцем вверх". Т. е. запросы на порции данных идут от клиента последовательно.
  
• api-3 - это предполагаемое посредническое звено между клиентом и api-1 с api-2. Я пока не рашил, стоит ли его писать или нет
  
• База api-1 пополняется записями в среднем в 10 раз чаще, чем база api-2 (хотя для каждого конкретного пользователя соотношение может быть разным)
  

В варианте с датами мне больше нравится то, что в этом случае необязательно создавать api-3 (минус расходы на написание, поддержку, дополнительные зависимости) - со слиянием результатов запросов мобильное приложение справится само и без дополнительных запросов.

А варинт с бинпоиском без написания api-3 (который будет отправлять запросы не через интернет, а хотя бы по локальной сети), не обойтись. Ну, или можно обойтись, но будут проблемы со временени исполнения запросов.

По поводу опасности вернуть всю базу - да, согласен, тут надо будет придумать какое-то разумное ограничение. Либо вместо варианта "dateFrom + dateTo" использовать вариант "dateFrom + limit". Но тут появляются свои минусы.

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

[Wataru]

uhamurad, Ну раз запросы идут последовательно, то никаких других вариантов, кроме как делать их кучу - нет. Как будто сливаете 2 отсортированных массива: сделали запросы к обоим API с offset=0. Из полученных данных понадергали минимальных по дате, пока один из кусков не кончится. У того API сделали следующий запрос с offset= конец предыдущего куска. Как только набрали нужный offset, записываем данные в ответ. Когда набрали offset+limit- останавливаемся.