DynamoDB 인접 리스트 패턴

그래프는 결국 노드와 엣지일 뿐이며, 인접 리스트 패턴은 둘 다 하나의 테이블에 평범한 아이템으로 저장합니다. 각 엣지는 파티션 키가 소스 노드이고 정렬 키가 타깃인 하나의 행이 됩니다. 파티션을 조회하면 모든 이웃이 나열됩니다 — 조인 테이블에 대한 JOIN을 대신하는 DynamoDB의 방식이죠.

DynamoDB 인접 리스트 패턴이란 무엇인가요?

인접 리스트 패턴은 그래프를 하나의 테이블에 담긴 엣지 아이템으로 모델링합니다. 각 관계(A가 B를 팔로우)는 소스를 파티션 키에, 타깃을 정렬 키에 두는 하나의 행입니다. 파티션을 조회하면 모든 이웃이 나열되고, 뒤집힌 GSI가 관계를 역전시킵니다 — 조인도, 스캔도 없이 양방향을 단일 쿼리로 처리합니다.

• 엣지가 곧 아이템입니다. 각 관계(사용자 A가 사용자 B를 팔로우)를 소스를 파티션 키에, 타깃을 정렬 키에 두는 자체 아이템으로 모델링합니다.
• 한 방향은 거저, 다른 방향은 GSI가 필요합니다. 베이스 테이블은 "A가 누구를 팔로우하는가?"에 답합니다. 뒤집힌 인덱스는 "누가 A를 팔로우하는가?"에 답합니다.
• 조인도, 스캔도 없습니다. 양방향 모두 알려진 파티션에 대한 단일 Query입니다 — 절대 전체 테이블 Scan이 아닙니다.
• 그것은 다대다의 기본 요소입니다. 팔로우, 멤버십, 좋아요, 친구 관계 — 하나의 엔티티가 여럿과 연결되는 어떤 그래프든 이 형태에 맞습니다.

액세스 패턴으로 틀 잡기

SQL에서 넘어왔다면 팔로우 그래프는 조인 테이블입니다: follows(follower_id, followee_id). 누군가의 팔로워를 나열하려면 한 컬럼을 인덱싱하고, 그가 누구를 팔로우하는지 나열하려면 다른 컬럼을 인덱싱합니다. DynamoDB에는 조인이 없으므로, 각 읽기를 직접 처리하도록 키를 설계합니다.

읽기를 먼저 적으세요. 소셜 팔로우 그래프의 경우:

• 사용자 A는 누구를 팔로우하는가? (그의 팔로잉 목록)
• 누가 사용자 A를 팔로우하는가? (그의 팔로워 목록)
• A는 B를 팔로우하는가? (단일 포인트 조회)

키는 오직 그 목록에 답하기 위해 존재합니다. 키를 제대로 잡으면 모든 읽기가 하나의 Query 또는 GetItem입니다.

엣지를 아이템으로 모델링하기

테이블이 둘 이상의 엔티티 유형을 담을 수 있도록 일반적인 키 이름을 쓰고, 노드 유형을 값에 인코딩하세요. 팔로우 엣지는 이렇게 생겼습니다:

PK = ACTOR#alice는 엣지의 소스이고, SK = TARGET#bob는 그녀가 팔로우하는 대상입니다. 하나의 Query PK = "ACTOR#alice"가 Alice가 팔로우하는 모든 계정을 단일 과금 읽기로 반환합니다 — 그녀의 팔로잉 목록 전체를, 조인 없이.

각 엣지는 "내가 팔로우하는 사람" 방향으로 한 번 쓰입니다. 역방향("나를 팔로우하는 사람")은 베이스 테이블이 아직 답할 수 없는 부분입니다.

GSI로 다른 방향 순회하기

베이스 테이블은 소스 우선으로 키가 지정되어 있어, 스캔 없이는 "누가 Bob을 팔로우하는가?"에 답할 수 없습니다. 키를 뒤집는 글로벌 보조 인덱스를 추가하세요. 타깃을 인덱스 파티션 키에, 소스를 인덱스 정렬 키에 투영합니다.

이제 Query GSI1 WHERE GSI1PK = "TARGET#bob"는 Bob을 팔로우하는 모든 사람 — alice와 dave — 을 한 번의 읽기로 나열합니다. 같은 엣지 아이템이 양방향을 모두 처리합니다. 베이스 테이블은 팔로잉, 인덱스는 팔로워입니다. 각 엣지를 한 번 쓰고 두 쿼리를 모두 거저 얻습니다.

이것은 AWS가 다대다 관계와 그래프 데이터 모델링에 대한 DynamoDB 모범 사례 가이드에서 문서화하는 바로 그 패턴입니다 — 엣지를 아이템으로 저장한 다음, GSI로 관계를 뒤집는 것이죠.

단일 엣지를 저렴하게 확인하기

"Alice가 Bob을 팔로우하는가?"는 어느 목록도 필요로 하지 않습니다. 엣지가 PK = ACTOR#alice, SK = TARGET#bob으로 키가 지정되어 있으므로, 직접 GetItem입니다 — DynamoDB가 제공하는 가장 저렴한 읽기, Query도 인덱스도 없습니다.

팔로우를 멱등하게 쓰고 중복 카운트를 피하려면, 엣지가 아직 존재하지 않는다는 조건으로 PutItem에 가드를 거세요:

attribute_not_exists(PK)

그 조건 — 그리고 marshalled된 키 값 — 을 ConditionExpression과 ExpressionAttributeValues를 직접 손으로 쓰는 대신 DynamoDB expression builder로 조립할 수 있습니다.

DynoTable에서 해보기

테이블을 둘러보면, 한 액터의 엣지가 단일 파티션 키 아래 하나의 아이템 컬렉션으로 쌓이고, GSI 뷰로 전환하면 뒤집힌 팔로워 목록이 보입니다 — 관계의 두 절반이 나란히.

함정

유명인 파티션. 수백만 팔로워를 가진 사용자는 모든 팔로워 엣지를 하나의 GSI1PK = TARGET#<star> 파티션 아래에 집중시킵니다. 그 컬렉션의 읽기는 페이지로 나뉘고 뜨겁게 달궈질 수 있습니다. 팬아웃이 많은 그래프라면, 핫 키를 샤딩하거나 (예: TARGET#bob#0..N) 카운트를 비정규화해 목록 전체를 다시 읽지 않도록 하세요.

엣지에 카운트를 저장하기. 팔로워 수는 엣지가 아닙니다 — 프로필을 볼 때마다 파티션 전체를 읽고 세어서 도출하지 마세요. 사용자 아이템에 카운터 속성을 유지하고 엣지와 함께 트랜잭션으로 업데이트하세요.

여기서는 역방향 쓰기가 필요 없음을 잊지 마세요. 고전적인 인접 리스트 변형은 ID를 바꿔 엣지를 두 번 씁니다. 키를 뒤집는 GSI를 쓰면 한 번 쓰고 인덱스가 역방향을 구체화하게 합니다 — 더 적은 쓰기, 두 복사본 사이의 어긋남 없음.

다음 단계

인접 리스트는 단일 테이블 설계의 관계 구성 요소입니다. 뒤집는 인덱스는 파티션 키가 바뀌므로 LSI가 아니라 GSI입니다. 그리고 여기의 모든 읽기는 알려진 키에 대한 Query 또는 GetItem입니다 — 절대 Scan 지뢰가 아닙니다.

DynamoDB expression builder로 조건과 키 표현식을 만들고, DynoTable을 다운로드하여 자신의 테이블에 팔로우 그래프를 모델링하고 양방향이 한 번의 읽기로 풀려나는 모습을 지켜보세요.