Question: How do you store a graph in DynamoDB?

Answer

Use the adjacency list pattern, which AWS documents for many-to-many relationships. Store every node and every edge as an item in one table: the partition key holds the source node, and the sort key holds either the node itself or the target of an edge. One Query on a node's partition key then returns the node and all of its outgoing edges.

Example items for a "follows" graph:

• PK = USER#alice, SK = USER#alice: the node, with attributes such as displayName
• PK = USER#alice, SK = FOLLOWS#bob: an edge, with attributes such as since
• PK = USER#alice, SK = FOLLOWS#carol: another edge

Add a global secondary index that swaps the keys (partition key SK, sort key PK), often called an inverted index. Querying it for SK = FOLLOWS#bob returns everyone who follows bob, so you get incoming edges without writing every edge twice.

import { DynamoDBClient } from "@aws-sdk/client-dynamodb";
import { DynamoDBDocumentClient, QueryCommand } from "@aws-sdk/lib-dynamodb";

const ddb = DynamoDBDocumentClient.from(new DynamoDBClient({}));

// Who does alice follow?
const following = await ddb.send(
  new QueryCommand({
    TableName: "Graph",
    KeyConditionExpression: "PK = :node AND begins_with(SK, :edge)",
    ExpressionAttributeValues: { ":node": "USER#alice", ":edge": "FOLLOWS#" },
  })
);

// Who follows bob? (inverted GSI)
const followers = await ddb.send(
  new QueryCommand({
    TableName: "Graph",
    IndexName: "InvertedIndex",
    KeyConditionExpression: "SK = :edge",
    ExpressionAttributeValues: { ":edge": "FOLLOWS#bob" },
  })
);

Each query above returns one page. Continue with ExclusiveStartKey while LastEvaluatedKey is present to retrieve every matching edge.

Limits of the pattern:

• Each hop is a separate request. "Friends of friends" means querying every friend's partition from your code, and each extra hop multiplies the requests again.
• Very popular nodes with millions of edges concentrate traffic on one partition key. Shard them, for example USER#celebrity#3.
• There's no graph query language, shortest-path search or pattern matching.

If your core queries are multi-hop traversals, recommendations or fraud rings, use a graph database: Amazon Neptune (Gremlin, openCypher and SPARQL) or Neo4j. See DynamoDB vs Amazon Neptune and DynamoDB vs Neo4j.

Source: AWS DynamoDB documentation.