들어가며

네이버 부스트캠프에서 팀 프로젝트로 Moyo를 개발했다. Moyo는 부스트캠퍼를 비롯한 개발 팀이 사용할 수 있는 2D 가상 공간 기반 협업 플랫폼이다. 아바타를 이동하며 화상회의·코드 편집·화이트보드·채팅을 하나의 공간에서 제공한다.

로비는 핵심 공간이었다. "통화 걸기" 같은 UI 없이 아바타가 물리적으로 가까워지면 자동으로 화상 연결된다. 우리가 목표로 한 경험은 단순했다.

가까이 있는 사람들끼리 자연스럽게 대화가 시작되게 하자.

이 경험을 구현하기 위한 핵심 요구사항이 있었다.

같은 바운더리 안에 있는 모든 참여자는 동일한 음성 스트림을 수신해야 한다.

하지만 구현 과정에서 "근접"이라는 개념이 단순 거리 판정이 아니라 대화 범위 정의 문제라는 것을 깨닫게 되었다. 이 요구사항이 이후 모든 설계 판단의 기준이 됐다.

기존 구조와 한계

1-hop 방식의 구조적 한계

내 타일에서 8방향으로 1칸 이내에 있는 사용자를 찾아 그룹으로 묶는 방식이다.

function getAdjacentUsers(users: User[], me: User): User[] {
  return users.filter((user) => {
    const dx = Math.abs(user.tileX - me.tileX);
    const dy = Math.abs(user.tileY - me.tileY);
    return dx <= 1 && dy <= 1 && user.id !== me.id;
  });
}

팀 내 테스트에서 5~6명이 일렬로 서는 시나리오로 이 문제를 재현했다.

A — B — C — D — E

1-hop 기준으로 A-B, B-C, C-D, D-E는 각각 연결된다. 그러나 A-C, A-D처럼 거리가 2칸 이상이면 직접 연결이 없다.

화상회의에서 누군가 발화할 때 그룹의 모든 참여자가 동시에 수신해야 한다. A가 말하는데 E가 못 듣는다면, 물리적으로 같은 공간에 있다는 경험 자체가 깨진다.

1-hop 방식에서는 A의 음성이 B에게, B의 음성이 C에게 전달될 수 있다. 그러나 이건 연결성(connectivity) 이 아니라 전파(propagation) 다. A→B→C→D→E로 정보가 단계적으로 흘러가는 구조이며, A와 E가 동일한 대화를 공유한다는 보장이 없다.

연속된 사용자 집합이 하나의 대화 공간으로 동작하려면, "누가 누구와 붙어 있는가"가 아니라 "전체 집합이 하나로 이어져 있는가" 를 판단해야 한다.

즉, 1-hop 모델은 구조적으로 이 요구사항을 만족할 수 없었다.

그룹 식별자 미갱신

초기 설계에서 boundary 그룹의 식별자(contactId)는 한 번 생성되면 가능한 한 재사용하도록 했다. 그룹 구성이 크게 변하지 않는다면 기존 연결 세션을 유지하는 것이 효율적이라고 판단했기 때문이다.

그러나 contactId가 그룹의 현재 상태가 아닌 과거 상태를 반영하고 있었고, 첨부한 영상과 같이 기존 그룹에서 이탈했음에도 같은 그룹으로 처리되거나 그룹 분리가 지연되는 문제가 발생했다.

이 문제를 해결하기 위해 boundary를 매 틱 새로 갱신하도록 수정했다.

하지만 갱신 방식만 바꾸는 것으로는 충분하지 않았다. 계산 주기의 문제가 아니라 대화 단위를 정의하는 모델 자체가 잘못되어 있었기 때문이다.

모델을 다시 정의하다

두 문제는 하나의 원인에서 비롯됐다. 두 개념이 뒤섞여 있었다.

• proximity: 두 사용자가 인접해 있는가 → 간선 생성 조건
• contactId: 어떤 사용자들이 같은 대화 공간에 속하는가 → 연결 컴포넌트

1-hop 방식은 proximity 판정은 하지만 연결 컴포넌트를 계산하지 않는다. A-B-C-D-E가 하나의 연결된 집합인지, 두 개의 분리된 집합인지 알 수 없다.

요구사항을 이렇게 재정의했다.

proximity는 그룹을 형성하기 위한 조건이다. 대화 단위는 proximity 그래프의 연결 컴포넌트다.

이 관점에서 공간을 그래프로 모델링했다.

• 사용자 = 노드
• 사용자 간 거리 ≤ 1 = 간선
• 연결 컴포넌트 = contactId 단위 바운더리 그룹

proximity와 contactId가 분리되자 알고리즘 선택도 명확해졌다.

설계 선택과 트레이드오프

이 방향이 기술적으로는 명확했지만, 팀 내 합의 과정이 필요했다. Discussion #89에서 세 가지 방향을 검토했다.

선택지 1: contactId + BFS

• 그래프 이론으로 연결 컴포넌트를 계산한다.
• 대화 범위가 명확하고, 모든 참여자가 동일한 음성을 수신한다.
• 사용자 수에 따라 서버 계산 비용이 증가한다.

선택지 2: 1-hop 이웃 관리만 유지

• contactId 없이 직접 이웃만 관리한다.
• 계산이 단순하고 서버 부하가 적다.
• 대화 범위가 불명확하고, 음성 전달 범위를 예측할 수 없다.

선택지 3: 느슨한 분리

• TTL이나 주기적 정리로 지연 처리한다.
• 서버 부하와 정확도 사이의 트레이드오프다.

핵심 질문은 오디오 전달 범위였다. A-B-C-D-E가 하나의 공간을 공유한다면, A가 발화할 때 E도 들어야 한다. 1-hop 이웃 관리에서는 이 보장이 불가능하다.

서버 계산 비용은 트레이드오프가 존재하더라도 예측 가능한 대화 범위를 제공하는 것이 더 중요하다.

따라서 BFS 기반 연결 컴포넌트 방식을 선택했다.

BFS로 전환하다

function findBoundaryGroups(users: User[]): User[][] {
  const visited = new Set<string>();
  const groups: User[][] = [];
 
  for (const start of users) {
    if (visited.has(start.id)) continue;
 
    const group: User[] = [];
    const queue = [start];
    let head = 0;
 
    while (head < queue.length) {
      const current = queue[head++];
      if (visited.has(current.id)) continue;
      visited.add(current.id);
      group.push(current);
 
      for (const neighbor of users) {
        if (!visited.has(neighbor.id) && isAdjacent(current, neighbor)) {
          queue.push(neighbor);
        }
      }
    }
 
    groups.push(group);
  }
 
  return groups;
}

A-B-C-D-E는 하나의 연결 컴포넌트로 탐색되어 단일 contactId를 부여받는다. 그룹 정의가 "국소 인접"이 아닌 "연결된 집합"으로 명확해졌다.

왜 Chebyshev 거리였는가

isAdjacent 구현에서 어떤 거리 모델을 쓸지 결정해야 했다. 타일 맵은 8방향 이동을 허용한다. 대각선 이동도 1칸으로 취급한다.

후보 세 가지를 비교했다.

체비쇼프 거리는 두 점의 좌표 차이 중 최댓값으로, 수학적 간결성 때문이 아닌 타일 이동 규칙 자체와 동일한 모델을 사용하기 위해 선택했다.

function chebyshevDistance(a: TilePos, b: TilePos): number {
  return Math.max(Math.abs(a.x - b.x), Math.abs(a.y - b.y));
}
 
function isAdjacent(a: User, b: User): boolean {
  return (
    chebyshevDistance({ x: a.tileX, y: a.tileY }, { x: b.tileX, y: b.tileY }) <=
    BOUNDARY_RANGE
  ); // BOUNDARY_RANGE = 1
}

이 내용은 팀 위키에도 정리해 공유했다.

바운더리 범위: 2칸에서 1칸으로

BFS와 Chebyshev 거리를 기반으로 boundary 모델을 새로 설계했지만 범위 설정은 별도로 조율이 필요했다.

초기 BOUNDARY_RANGE는 2였다. 조금 더 넉넉한 대화 반경을 제공하려는 의도였다.

실제 적용하니 문제가 생겼다.

• 그룹이 지나치게 크게 형성됐다.
• 화면상 거리가 꽤 떨어진 사용자도 같은 그룹에 묶였다.
• 사용자가 느끼는 "가까운 거리"와 실제 그룹 범위가 달랐다.

공간 체감과 대화 단위가 일치하지 않는 것이었다. 공간에서 느끼는 근접감과 대화 단위를 맞추기 위해 BOUNDARY_RANGE를 1로 줄이고, 8방향 인접 칸만 같은 그룹으로 묶이도록 했다.

다른 문제 발생: 가만히 있는데 화면이 깜빡인다

BFS와 범위 조정으로 그룹 탐색은 정확해졌다. 그런데 PR #93을 머지한 뒤, 아무도 움직이지 않는 상황에서 비디오 썸네일이 계속 깜빡이는 문제가 발견됐다. React Profiler로 확인하니 초당 10~15회씩 리렌더링이 반복되고 있었다.

원인: 식별자를 문자열로 만들다

문제는 contactId 생성 방식에 있었다.

// 서버에서 contactId 생성
const contactId = members
  .map((u) => u.id)
  .sort()
  .join("-");

멤버가 ["A", "B", "C"]면 "A-B-C"가 contactId가 된다. 의도는 동일 멤버 조합을 동일 그룹으로 처리하는 것이었다.

그런데 BFS 탐색은 매 틱마다 사용자 목록 순서에 영향을 받는다. 소켓 이벤트 처리 순서, 입장 타이밍 등 외부 요인으로 멤버 배열 구성이 달라지면, .sort() 결과가 같아 보여도 같은 그룹임에도 다른 문자열이 만들어졌다.

클라이언트는 contactId가 바뀌면 새 그룹으로 인식해 스토어를 업데이트한다. 비디오 컴포넌트는 이 업데이트를 구독하고 있어 매 변경마다 리렌더링됐다. 멤버 구성은 그대로인데 식별자 문자열만 바뀌어 화면이 깜빡이는 것이었다.

즉, 기존 식별자는 멤버를 표현하는 값일 뿐 그룹의 정체성을 보장하는 ID가 아니었다.

해결: UUID 기반 contactId 재사용

서버의 contactId 발급 방식을 바꿨다.

// BoundaryTracker: contactId 세션 관리
const contactIdMap = new Map<string, string>(); // memberKey → contactId
 
function getContactId(members: string[]): string {
  const key = [...members].sort().join(",");
 
  if (!contactIdMap.has(key)) {
    contactIdMap.set(key, crypto.randomUUID());
  }
 
  return contactIdMap.get(key)!;
}
 
function onMemberLeave(members: string[], leftId: string): void {
  const oldKey = [...members].sort().join(",");
  contactIdMap.delete(oldKey); // 멤버 이탈 시 기존 세션 종료
 
  const newMembers = members.filter((id) => id !== leftId);
  if (newMembers.length > 0) {
    getContactId(newMembers); // 남은 멤버로 새 세션 시작
  }
}

동일 멤버 조합이면 항상 같은 UUID를 반환한다. 멤버가 이탈할 때만 기존 세션을 종료하고 새 UUID를 발급한다.

클라이언트는 UUID를 캐시 키로 사용해 참조 동등성을 유지하고, 가시 사용자 Set이 바뀌지 않으면 비디오 컴포넌트를 갱신하지 않도록 처리했다. 트랙 구독 갱신 범위도 발화자 변경 이벤트로만 제한했다.

바운더리 내부에서 이동해도 contactId가 유지되어 리렌더링이 사라졌다. 관련 작업은 PR #133에서 확인할 수 있다.

성능 최적화

인접 리스트의 시간 복잡도를 O(n²)에서 O(n)으로

contactId 문제를 해결하고 나서 BFS의 또 다른 병목이 보였다. 인접 리스트를 만들 때 모든 사용자 쌍을 비교하고 있었다.

// 이전: O(n²) — 모든 쌍 비교
for (const a of users) {
  for (const b of users) {
    if (isAdjacent(a, b)) {
      adjacency.get(a.id)!.push(b.id);
    }
  }
}

서버는 약 100ms 간격으로 틱을 처리한다. 로비에 50명이 있다면 매 틱마다 2,500번의 chebyshevDistance 호출이 필요하고, 초당 25,000번의 거리 계산이 발생하는 셈이다.

타일 해시맵으로 전환

체비쇼프 거리 1 이내라면 최대 3×3=9개 타일 안에 있는 사람하고만 인접할 수 있다. 타일 좌표를 키로 한 해시맵을 만들면 모든 쌍 비교 없이 주변 9개 타일의 사용자만 확인하면 된다.

// 개선: O(n) — 타일 해시맵으로 후보 이웃만 탐색
const tileMap = new Map<string, string[]>();
 
for (const user of users) {
  const key = `${user.tileX},${user.tileY}`;
  if (!tileMap.has(key)) tileMap.set(key, []);
  tileMap.get(key)!.push(user.id);
}
 
for (const user of users) {
  for (let dx = -1; dx <= 1; dx++) {
    for (let dy = -1; dy <= 1; dy++) {
      const neighbors =
        tileMap.get(`${user.tileX + dx},${user.tileY + dy}`) ?? [];
      for (const neighborId of neighbors) {
        if (neighborId !== user.id) {
          adjacency.get(user.id)!.push(neighborId);
        }
      }
    }
  }
}

50명 기준으로 비교 횟수가 2,500번에서 최대 450번(50 × 9)으로 줄어든다. 사용자가 균등하게 분포된다면 실제 비교 횟수는 이보다 훨씬 적다. tileMap 구성과 adjacency 초기화도 루프 하나로 합쳤다.

BFS queue도 O(n)에서 O(1)으로

BFS 내부에도 숨어 있는 O(n) 연산이 있었다.

// 이전: queue.shift() — 앞 요소 제거 시 나머지 전체 재인덱싱 O(n)
while (queue.length > 0) {
  const current = queue.shift()!;
  ...
}
 
// 개선: 인덱스 포인터 — O(1)
let head = 0;
while (head < queue.length) {
  const current = queue[head++];
  ...
}

queue.shift()는 첫 요소를 제거하면서 나머지를 모두 한 칸씩 앞으로 이동시킨다. n개 요소를 처리하면 O(n²)이 된다. 인덱스 포인터는 배열을 수정하지 않고 포인터만 증가시켜 O(1)로 처리한다.

관련 작업은 PR #277에서 확인할 수 있다.

모든 수정을 적용한 뒤 바운더리 시스템이 의도한 대로 동작하는 모습이다.

마치며

이 작업은 단순히 1-hop 알고리즘을 BFS로 교체한 것이 아니다.
근접(proximity) 판정을 대화 단위로 오해했던 구조를 재정의하고, boundary를 연결 요소 기반 모델로 전환했으며, contactId를 “현재 연결 구조의 정체성”으로 재설계한 과정이었다.

그 결과 대화 범위는 인접 관계가 아니라 연결성 기준으로 정의되었고, 하나의 contactId 내부에서는 모든 참여자가 동일한 음성을 수신하는 구조를 확립할 수 있었다. 이는 UX 요구사항과 시스템 모델을 일치시키기 위한 설계 선택이었다.

본문에 포함된 코드는 이해를 돕기 위해 일부 발췌 및 단순화한 예시이며 이후 리팩토링 및 다른 작업으로 인해 실제 구현과 일부 차이가 있을 수 있다.

서버 쪽 바운더리 계산이 안정화된 뒤 클라이언트에서 드러난 문제는 이후 2편과 3편에서 이어서 정리한다.

참고

• Discussion #89 — contactId 기반 vs 근접 이웃 기반 설계 논의
• PR #93 — 바운더리 감지 및 시각화
• PR #133 — contactId 미갱신 문제 수정
• PR #277 — 바운더리 시스템 인접 리스트 생성 최적화
• Wiki — 체비쇼프 거리와 아바타 바운더리 계산