Cursor API как альтернатива стандартному Paging

Недостатки стандартного Paging API

Изначально мы должны понять, почему подход с offset pagination не годится для больших датасетов с помощью следующего примера:

Клиент предоставляет два параметра — LIMIT для ожидаемого максимального количества результатов и OFFSET для смещения страницы. Например, с OFFSET = 400, LIMIT = 20, мы возвращаем из БД 20 items, выбрасывая первых 400.

Использование LIMIT и OFFSET плохо работает на больших датасетах. По мере того, как OFFSET возрастает, БД по-прежнему должна прочитать данные вплоть до OFFSET + нужного кол-ва записей с диска, до того как отбросит OFFSET и вернет только ожидаемое количество записей

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

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

Cursor API

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

Предположим у нас есть следующая GET операция REST-сервиса:

GET /api/v1/items/in

Для каждого из возвращаемых записей нам необходимо иметь уникальное sequential ID, которое для вновь добавляемых записей будет иметь значение большее всех уже существующих. В некоторых БД это может быть уже существующее поле, например числовой первичный ключ. В случае использования цифробуквенного первичного ключа в качестве такого sequential ID может выступать дополнительное поле, например типа serial / bigserial в PostgreSQL.

Значение этого ID для последней из найденныйх записей будет использоваться для формирования прямого (forward) курсора, значение ID первой из найденных записей — для формирования обратного (backward) курсора.

Запрос первой порции данных клиентом

Когда клиент делает запрос первой порции данных, он использует запрос вида:

GET /api/v1/items/in?someParam=...&sortBy={sortingFieldName}&size={count}

Здесь мы для усложнения добавили еще сортировку по определенному полю с именем sortingFieldName.

При этом к БД выполняется запрос:

SELECT * FROM items WHERE ...            -- apply search params ORDER BY :sortingFieldName, :sequentialId LIMIT :count

Клиенту возвращается респонс следующего вида:

{     "elements" : [ {     "sortingFieldName" : "John",     "sequentialId" : 37,     ...   }, {     "sortingFieldName" : "John",     "sequentialId" : 38,     ...   } ],     "nextCursor" : "eyJmaWVsZE5hbWUiOiJuYW1lIiwiZmllbGRWYWx1ZSI6IkX0=" }

где в nextCursor закодировано посредством Base64 следующее содержимое:

{     "fieldName" : "sortingFieldName",     "fieldValue" : "John",     "sequentialId" : 38,     "forward" : true }

Указать просто, что мы остановились на значении sortingFieldName=John в предыдущей странице для формирования следующей — недостаточно, т.к. несколько последующих записей также могут иметь то же значение этого поля. Для этого нам и надо sequential ID.

Поле nextCursor отсутствует в response, если мы нашли меньше чем запрошенных count записей (поэтому точно уверены в отсутствии следующей страницы).
(UPD: либо nextCursor можно возвращать в любом случае, если при последнем запросе найдено любое ненулевое кол-во записей, сохраняя в курсоре информацию о последней записи найденного набора)

Поле prevCursor отсутствует в response после первого запроса (в нем cursor отсутствовал в request)

Запрос следующих порций данных клиентом

Когда клиент делает последующий запрос — ему нужно использовать курсор (прямой или обратный) из предыдущего response.

Прямой курсор:

GET /api/v1/items/in?someParam=...&sortBy={sortingFieldName}&size={count}& cursor=eyJmaWVsZE5hbWUiOiJuYW1lIiwiZmllbGRWYWx1ZSI6IkX0=

При этом к БД выполняется запрос:

SELECT * FROM items WHERE ...            -- apply search params AND ((fieldName = :nextCursor.fieldName AND sequentialId > :nextCursor.sequentialId) OR  fieldName > :nextCursor.fieldName) ORDER BY :sortingFieldName, :sequentialId LIMIT :count

А клиенту возвращается респонс:

{     "elements" : [ {     "sortingFieldName" : "Zeppelin",     "sequentialId" : 39,     ...   } ],     "nextCursor" : "eyJmaWVsZE5JuYW1lIiwiZmllbGRWYhbWUiOiWx1ZSI6IkFUR3Jvd",     "prevCursor" : "eyJmaWVsZE5hbWUiOiJuYW1lIiwiZmllbGRWYWx1ZSI6IkFUR3Jvd" }

Здесь prevCursor также представляет собой закодированный посредством Base64 объект:

{     "fieldName" : "sortingFieldName",     "fieldValue" : "Zeppelin",     "sequentialId" : 39,     "forward" : false }

Обратный курсор:

GET /api/v1/items/in?someParam=...&sortBy={sortingFieldName}&size={count}& cursor=eyJmaWVsZE5hbWUiOiJuYW1lIiwiZmllbGRWYWx1ZSI6IkFUR3Jvd

При этом к БД выполняется запрос:

SELECT * from items WHERE ...            -- apply search params AND ((fieldName = :prevCursor.fieldName AND seq_id < :prevCursor.sequentialId) OR  fieldName < :prevCursor.fieldName) ORDER BY :sortingFieldName DESC, :sequentialId DESC LIMIT :count

После этого нам надо обратить порядок записей в результате, чтобы отдать их клиенту с ожидаемым им ордерингом. Респонс имеет аналогичный вид:

{     "elements": [...],     "nextCursor" : "eyJmaWVsZE5hbWUiOiJuYW1lIiwiZmllbGRWYWx1ZSI6IkFUR3JvdXAtd0ZQ",     "prevCursor" : "eyJmaWVsZE5h4YW1lIiwiZmllbGRWYWx1ZSI6IkFUR3JvdXAtTGFtN0B1aR1l" }

Упаковка параметров запроса в сам курсор

В принципе мы можем упаковать параметры запроса (поля someParam и sortBy) в сам курсор, и тогда последующие запросы клиента будут иметь сходный вид для прямого и обратного курсоров:

GET /api/v1/items/in?size={count}&cursor={...}

А сам курсор иметь вид:

{     "someParam" : ...,     "sortBy" : ...,     "fieldName" : "sortingFieldName",     "fieldValue" : "Zeppelin",     "sequentialId" : 39,     "forward" : true/false }

Итоги

Мы спроектировали Cursor API, представляющее альтернативу стандартному Paging, лишенное некоторых его недостатков.
UPD: по совету в комментариях — добавляю ссылку на статью, где рассматривается аналогичная проблема.