Advanced8 min read

The DynamoDB Adjacency List Pattern

A graph is nodes and edges, and the adjacency list pattern stores both as plain items in one table. Each edge is an item keyed by its source on the and its target on the sort key.

This guide covers the mechanics: the edge item, the index that reads it backwards, and what each costs. For the same pattern applied to two entity types with data on the edge (students, courses, grades), see many-to-many relationships.

What is the DynamoDB adjacency list pattern?

It models a graph as edge items, one per relationship (A follows B). A Query on the source's partition lists who it points at, and a that swaps the two keys lists who points at it.

  • Edges are items. Each follow is its own item, so it carries its own data (createdAt) and is written or deleted on its own.
  • The table answers one direction, a GSI the other. The base table answers "who does A follow?". An index keyed target-first answers "who follows A?".
  • Both reads are a Query on a known partition key. Neither direction needs a full-table Scan.
  • Each read is one hop. Follows, memberships, likes and friendships fit. A friends-of-friends walk is 1 + N Query calls (one per friend), merged in your code. For deep traversals at millisecond latency, AWS points to Amazon Neptune.

Frame it as access patterns

Coming from SQL, a follow graph is a join table: follows(follower_id, followee_id). To list someone's followers you index one column; to list who they follow you index the other.

DynamoDB has no joins, so you design the keys to serve each read directly.

Write down the reads first. For a social follow graph:

  • Who does user A follow? (their following list)
  • Who follows user A? (their followers list)
  • Does A follow B? (a single point lookup)
  • How many followers does A have? (a number on the profile screen)

Get the keys right and each read is one Query or GetItem.

Model edges as items

Use generic key names so the table can hold more than one entity type, and encode the node type in the value. A follow edge carries the base-table keys plus the GSI1PK/GSI1SK pair the next section indexes; your code sets all four:

PKSKGSI1PKGSI1SKattributes
ACTOR#aliceTARGET#bobTARGET#bobACTOR#alicecreatedAt=1718900000
ACTOR#aliceTARGET#carolTARGET#carolACTOR#alicecreatedAt=1718900100
ACTOR#daveTARGET#bobTARGET#bobACTOR#davecreatedAt=1718900200
USER#bobMETA--displayName, followerCount

PK = ACTOR#alice is the source of the edge; SK = TARGET#bob is who she follows. One Query PK = "ACTOR#alice" returns Alice's whole following list, one 1 MB page at a time (follow LastEvaluatedKey for the next page).

The USER#bob / META item is Bob's profile. It holds the follower count, so the profile screen never counts edges.

Traverse the other direction with a GSI

The base table is keyed source-first, so it can't answer "who follows Bob?" without scanning.

Add a global secondary index, GSI1, with GSI1PK as its partition key and GSI1SK as its sort key. On each edge those hold the target and the source, so the index stores the edge flipped:

GSI1PKGSI1SKbase item
TARGET#bobACTOR#aliceACTOR#alice to TARGET#bob
TARGET#bobACTOR#daveACTOR#dave to TARGET#bob
TARGET#carolACTOR#aliceACTOR#alice to TARGET#carol

Now Query GSI1 WHERE GSI1PK = "TARGET#bob" lists everyone who follows Bob (alice and dave). The index only holds items that have its key attributes, which is why the profile item, with no GSI1PK, stays out of it.

GSI1: GSI1PK = TARGET#bobGSI1SK: ACTOR#aliceGSI1SK: ACTOR#daveBase table: PK = ACTOR#aliceSK: TARGET#bobSK: TARGET#carolQuery base: who alice followsQuery GSI1: who follows bob

You make one write call per edge, and DynamoDB maintains the index copy. That copy is billed: the write cost is the base-table write plus the index write, and the index adds its own storage.

The older variant writes the edge twice with ids swapped. The GSI does that second write for you, and its copy can't drift from the first.

The followers direction is . A GSI rejects ConsistentRead, and a new follow usually reaches it within a fraction of a second.

When the user who just followed must see it at once, read the base edge with GetItem and ConsistentRead: true.

This is the pattern AWS documents in its many-to-many modeling guide: store edges as items, then use a GSI to invert the relationship.

Run the access patterns
Query PK = "ACTOR#alice"

2 of 4 items read — one Query, one partition. The key condition filters before any data leaves it, so you pay only for the matches.

Base table, in stored order
#PKSKGSI1PKGSI1SKAttributes
1ACTOR#aliceTARGET#bobTARGET#bobACTOR#alicecreatedAt=1718900000
2ACTOR#aliceTARGET#carolTARGET#carolACTOR#alicecreatedAt=1718900100
ACTOR#daveTARGET#bobTARGET#bobACTOR#davecreatedAt=1718900200
USER#bobMETAdisplayName, followerCount

The items and keys are this guide’s own example. Highlighted rows are what the one call above touches; the numbers show the order they come back in. “Items read” counts items, not read units — real billing rounds each read up to 4 KB blocks.

Check a single edge, and write it once

"Does Alice follow Bob?" doesn't need either list. The edge is keyed PK = ACTOR#alice, SK = TARGET#bob, so it's a single-item GetItem against the base table: 0.5 RCU eventually consistent for an item up to 4 KB.

The follow itself is two writes that must agree: the edge, and +1 on Bob's followerCount. Put both in one TransactWriteItems, and guard the edge Put with a condition that it doesn't already exist:

attribute_not_exists(PK)

A repeated follow then fails that condition, DynamoDB cancels the whole transaction, and the count isn't bumped twice. Reference counts walks through this transaction, the unfollow mirror and how to handle the cancellation.

You can assemble that condition and the marshalled key values with the DynamoDB expression builder instead of hand-writing the ConditionExpression and ExpressionAttributeValues.

Do it in DynoTable

When you browse the table, the edges for one actor stack under a single partition key as one . Pick GSI1 in the index picker and query GSI1PK = TARGET#bob to see the inverted followers list.

DynoTable showing one actor's follow-edge items under a single partition, with the GSI key attributes visible as columns.
DynoTable showing one actor's follow-edge items under a single partition, with the GSI key attributes visible as columns.

Pitfalls

The celebrity partition. A user with millions of followers puts every follower edge under one GSI1PK = TARGET#<star> value. Reads of that list page through 1 MB at a time, and every new follower writes to the same index partition.

That write side is the dangerous one. An index short of write capacity throttles writes on the base table, so one star's follow storm can slow every write to the table.

The way out is a shard suffix on the index key: write GSI1PK = TARGET#bob#<n>, with n a hash of the follower id modulo N. "Who follows Bob" becomes N Query calls, one per suffix, merged in your code.

"Does Alice follow Bob" stays a single GetItem on the base table, which the suffix never touches.

Size N from your peak. An edge under 1 KB is one write unit, and one index partition takes about 1,000 a second, so N is a star's peak follows per second ÷ 1,000, rounded up with headroom.

Hot partitions covers the random-vs-calculated choice.

Keep the follower count on the user item. Don't derive it by reading and counting the whole partition on every profile view. Bump followerCount in the same transaction as the edge (above).

A star's count is one item too, so past roughly 500 follows a second it needs the sharded counter from atomic counters.

Fetching full profiles. An edge holds ids, not profiles. To show the people Alice follows, take the TARGET# ids from her page and fetch their USER#<id> / META items with one BatchGetItem (up to 100 keys per call).

Or copy the display name onto the edge when you write it, and accept updating every edge on a rename.

Next steps

The adjacency list is the relationship building block of single-table design; the inverting index is a GSI, not an LSI, because the partition key changes. Every read here is a Query or GetItem on a known key, never the Scan footgun.

To draft this shape from your own edge list, the free Single-Table Design tool turns the access patterns into a PK/SK/GSI plan with example items.

Build the condition and key expressions with the DynamoDB expression builder, and download DynoTable to model a follow graph against your own table and watch each direction come back from its own Query.

By Dmitriy · Updated

Try this design interactively

Sketch your entities and access patterns in the free DynamoDB Single-Table Design tool — it suggests PK/SK key templates, previews the item collections, and shows which patterns need a GSI.

Open the Single-Table Design tool