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/{ns}

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

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

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

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

GET /api/v1/items/in/{ns}?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 записей (поэтому точно уверены в отсутствии следующей страницы)
Поле prevCursor отсутствует в response после первого запроса (в нем cursor отсутствовал в request)

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

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

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

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

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

SELECT * FROM items
WHERE ...            -- apply search params
AND ((fieldName = :cursor.nextFieldName AND sequentialId > :cursor.nextId) OR 
fieldName > :cursor.nextFieldName)
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/{ns}?someParam=...&sortBy={sortingFieldName}&size={count}&
cursor=eyJmaWVsZE5hbWUiOiJuYW1lIiwiZmllbGRWYWx1ZSI6IkFUR3Jvd

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

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

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

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

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

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

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

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

Итоги

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

Автор: Андрей

Источник