Page a Feed With Cursors
The mobile apps page through a home feed of hundreds of millions of posts, and the cursors they hold come back days later. The README has the rules and the operational stakes. Build feed.py with the assistant, and weigh each suggestion against the table's size and the fact that cursors are client input.
feed.py1 of 3
Files
feed.py
Python · Editableimport base64
import json
class InvalidCursor(Exception):
"""The client sent a cursor we didn't issue. Answer 400."""
MAX_LIMIT = 100
def create_schema(conn):
conn.execute("CREATE TABLE posts (id INTEGER PRIMARY KEY, created_at INTEGER NOT NULL, body TEXT NOT NULL)")
def encode_cursor(created_at, post_id):
raise NotImplementedError
def decode_cursor(cursor):
"""Returns (created_at, post_id). Raises InvalidCursor for anything we didn't issue."""
raise NotImplementedError
def list_posts(conn, limit=20, cursor=None):
"""Newest first. Returns (post ids, next_cursor), and next_cursor is None on the last page."""
where, params = "", []
if cursor is not None:
created_at, post_id = decode_cursor(cursor)
raise NotImplementedError
rows = conn.execute(
f"SELECT id, created_at FROM posts {where} ORDER BY created_at DESC, id DESC LIMIT ?",
params + [limit + 1],
).fetchall()
raise NotImplementedError
import base64
import json
import sqlite3
import pytest
from feed import InvalidCursor, create_schema, list_posts
# (id, created_at). Posts 2, 3, and 4 share a second, as bulk imports do.
POSTS = [(1, 100), (2, 105), (3, 105), (4, 105), (5, 110), (6, 120)]
def make():
conn = sqlite3.connect(":memory:")
create_schema(conn)
conn.executemany("INSERT INTO posts (id, created_at, body) VALUES (?, ?, 'hi')", POSTS)
return conn
def all_pages(conn, limit):
pages, cursor = [], None
for _ in range(10):
ids, cursor = list_posts(conn, limit, cursor)
pages.append(ids)
if cursor is None:
break
return pages
def test_first_page_is_newest_first():
ids, cursor = list_posts(make(), 2)
assert ids == [6, 5]
assert cursor is not None
def test_pages_cover_every_post_once():
assert all_pages(make(), 2) == [[6, 5], [4, 3], [2, 1]]
def test_ties_on_created_at_are_not_skipped():
assert sum(all_pages(make(), 1), []) == [6, 5, 4, 3, 2, 1]
def test_last_page_has_no_cursor():
ids, cursor = list_posts(make(), 6)
assert ids == [6, 5, 4, 3, 2, 1]
assert cursor is None
def test_rejects_a_cursor_we_did_not_issue():
forged = base64.urlsafe_b64encode(json.dumps([105, "3 OR 1=1"]).encode()).decode()
for cursor in ["not-a-cursor", forged]:
with pytest.raises(InvalidCursor):
list_posts(make(), 2, cursor)
def test_rejects_a_limit_outside_1_to_100():
for limit in [0, 101]:
with pytest.raises(ValueError):
list_posts(make(), limit)
def test_feed_query_uses_the_index():
plan = make().execute(
"EXPLAIN QUERY PLAN SELECT id FROM posts WHERE (created_at, id) < (?, ?) ORDER BY created_at DESC, id DESC LIMIT 21",
(105, 3),
).fetchall()
assert any("posts_feed" in row[-1] for row in plan)
# Home Feed Pages
The mobile apps page through the home feed with list_posts (feed.py): newest first, a page at a time, with an opaque cursor for the next page. The feed table holds about 400 million posts.
## Rules
- Posts are ordered by created_at, then id, both descending. created_at is whole seconds, and bulk imports create thousands of posts in the same second.
- Paging through the feed returns every post exactly once. The last page has no cursor, so the app knows to stop.
- limit is 1 to 100. Anything else is a 400.
- A cursor is opaque to clients. A cursor we didn't issue raises InvalidCursor, which the API answers with a 400.
## Operational Stakes
- Cursors come back from the apps, so they are untrusted input. The apps also keep them for days, so the format has to survive deploys.
- An offset scan gets slower with every page on a table this size. Each page should be one index range read.
The tests in test_feed.py use an in-memory SQLite database.
Test Output
No runs yet.