그래프를 여러 대로 나누기
한 대에 담기 어려운 그래프를 여러 서버로 나눌 때 생기는 비용, 엣지 컷을 동아리 네트워크로 계산해 봅니다.
이번 회차, 내 속도로.
기초를 더 짚거나 궁금한 주제로 잠깐 넓혀 보세요. 최대 3단계를 거쳐 DAY 47로 돌아옵니다.
난이도·관심 주제 고르기
1/2개 선택 · 새 보충·심화 수업과 본과정 다시 읽기를 선택할 수 있어요.
이렇게 다녀와요 1단계 · 약 12분
- 출발 · DAY 47분할·엣지 컷
- 1. 관심 주제ACID·격리 수준추가 19 · 새 추가 수업
- 복귀 · DAY 47원래 회차 이어가기
- ACID·격리 수준 · DAY 49에서 트랜잭션 순회(OLTP) 워크로드를 봤다면, 그 ‘트랜잭션’이 무엇을 보장하고 무엇을 보장하지 않는지 확인하러 옵니다.
선택과 경로 기록은 이 브라우저에 저장됩니다. 본과정의 회차 완료와는 별도입니다.
핵심 개념
그래프가 한 서버의 메모리나 처리량을 넘으면 노드를 여러 서버에 나눠 담습니다(분할, partitioning). 양 끝 노드가 서로 다른 서버에 있는 엣지를 잘린 엣지라 하고, 그 수를 엣지 컷(edge cut)이라고 합니다. 순회가 잘린 엣지를 지날 때마다 서버 사이의 네트워크 왕복이 생기며, 이는 같은 서버의 메모리 안에서 이동하는 것보다 훨씬 느립니다.
동아리 네트워크(8명, 엣지 11개)는 {민수, 지아, 서준, 하린}과 {도윤, 유나, 태오, 보라} 두 무리를 하린–도윤이 잇습니다. 무리대로 서버 2대에 나누면 잘린 엣지는 하린–도윤 하나뿐입니다. 좋은 분할은 서버마다 크기가 비슷하면서 엣지 컷이 작은 분할이며, 이는 DAY 22의 모듈러리티처럼 커뮤니티를 덜 자르는 문제와 닮았습니다.
현실은 더 어렵습니다. 크기 균형을 맞추며 엣지 컷을 최소화하는 문제는 일반적으로 NP-난해라 실무 도구는 휴리스틱을 씁니다. 그래프는 계속 바뀌어 분할이 낡고, 차수가 매우 큰 허브는 어디에 두어도 많은 엣지를 자릅니다. 그래서 PowerGraph(Gonzalez 외 2012)처럼 허브의 엣지를 여러 서버에 나누고 정점을 복제하는 정점 분할(vertex cut) 방식도 제안되었습니다.
분할은 꼭 필요할 때 하는 선택입니다. Stonebraker와 Pavlo(2024)는 통신 비용 때문에 분산 그래프 알고리즘이 단일 노드 구현보다 빠른 경우가 드물다는 연구를 소개하며, 가장 큰 그래프가 아니라면 압축해 한 대의 메모리에 올리는 편이 낫다고 봅니다. 먼저 한 대로 충분한지 확인하고, 나눠야 한다면 질의가 자주 지나는 경로를 덜 자르는 분할을 고릅니다.
작은 예제로 따라가기
무리대로 나누면(서버 1={민수, 지아, 서준, 하린}, 서버 2={도윤, 유나, 태오, 보라}) 엣지 컷은 하린–도윤 1개입니다.
서버 1={민수, 서준, 도윤, 태오}, 서버 2={지아, 하린, 유나, 보라}로 번갈아 나누면 민수–지아, 지아–서준, 서준–하린, 하린–도윤, 도윤–유나, 유나–태오, 태오–보라가 잘려 엣지 컷은 7개입니다.
민수에서 BFS 한 단계: 무리대로 나누면 이웃 지아·서준이 같은 서버라 왕복 0번, 번갈아 나누면 지아가 다른 서버라 왕복이 1번 생깁니다.
직접 실험해 보기
프리셋 ‘커뮤니티대로’와 ‘번갈아’를 차례로 적용해 엣지 컷 수와 서버 간 왕복 수를 비교하고, 노드 하나를 다른 서버로 옮겨 엣지 컷이 어떻게 변하는지 확인하세요.
그래프를 서버 두 대로 나누고 엣지 컷 세기
노드를 누르면 서버 1↔2가 바뀐다. 학습용 단순 모델: BFS는 엣지를 한 번씩 확인하고, 다른 서버에 있는 이웃을 확인할 때마다 네트워크 왕복 1회가 든다. 위 방문 순서에서 ⇢는 탐색이 다른 서버로 넘어간 곳이다. 좋은 분할은 커뮤니티를 덜 자르면서 서버 균형도 맞춘다.
이번에는 직접 풀어 보세요
정답을 보기 전에 계산과 이유를 적어 보세요. 해설과 비교하고 확인 표시를 남기면 완료할 수 있습니다.
힌트 보기
양 끝이 다른 서버에 있는 엣지만 셉니다.
풀이와 비교하기
지아–하린, 서준–하린 2개입니다. 무리대로 나눈 분할(엣지 컷 1)보다 1개 많고, 서버 크기도 3 대 5로 기울어 있습니다.
풀이와 확인 표시는 이 브라우저에 저장됩니다.
오늘 이해한 것과 다시 볼 것
계산이 달라진 이유, 헷갈린 개념, 다음에 확인할 질문을 남겨 보세요.
메모는 이 브라우저에 저장됩니다. 홈에서 전체 기록을 내려받을 수 있습니다.오늘의 이해 확인
그래프를 서버 여러 대로 나눌 때 좋은 분할의 기준으로 가장 알맞은 것은?
완료 조건: 확인 퀴즈 정답 · / 직접 풀기 0/1
더 깊이 읽기
예제와 실험 데이터는 이 과정을 위해 만든 것입니다. 원문은 선택 자료이며, 강의와 직접 풀기만으로도 다음 회차를 이어갈 수 있습니다.
PowerGraph: Distributed Graph-Parallel Computation on Natural GraphsGonzalez et al. (2012), OSDIWhat Goes Around Comes Around... And Around...Stonebraker & Pavlo (2024), SIGMOD RecordModularity and community structure in networksNewman (2006)이 자료는 개념 학습용입니다. 실제 데이터베이스·라이브러리·플랫폼의 동작과 설정은 제품과 버전마다 다를 수 있습니다.