그래프는 점과 선을 다루는 수학 문제가 아니다

vx_developer·약 12시간 전
개발그래프기초알고리즘자료구조

코테보다가

목록 보기
29/29
post-thumbnail

그래프를 처음 배우면 정점과 간선으로 이루어진 자료구조라고 설명한다.

const graph = {
  chris: ["alex", "victoria"],
  alex: ["chris"],
  victoria: ["chris"]
};

chris, alex, victoria는 정점이고, 배열에 들어 있는 사용자 이름은 서로 연결된 관계를 나타낸다. 크리스와 알렉스가 연결되어 있고 크리스와 빅토리아도 연결되어 있다는 뜻이다.

이 설명은 그래프의 기본 모양을 이해하는 데 유용하다. 하지만 실제 전문가 네트워킹 서비스를 개발한다면 객체에 사용자 이름을 연결하는 것만으로는 충분하지 않다. 팔로우와 일촌 관계는 같은 연결일까? 연결 요청을 보낸 상태와 수락된 상태는 어떻게 구분할까? 차단한 사용자는 추천 후보에서 어떻게 제외할까? 친구의 친구를 계속 따라가면 어디까지 탐색해야 할까? 두 사용자가 동시에 연결 요청을 보내면 관계가 두 개 만들어지지 않을까?

실제 서비스에서 그래프는 점과 선을 저장하는 모양이 아니라, 서로 독립적으로 존재하는 대상 사이의 다양한 관계를 표현하고 필요한 연결 범위를 탐색하기 위한 구조다.

사용자 목록만 있으면 관계를 표현할 수 있을까?

크리스가 사용하는 전문가 네트워킹 서비스에 다음과 같은 사용자 목록이 있다고 해보자.

const users = [
  { id: "user-1", name: "Chris" },
  { id: "user-2", name: "Alex" },
  { id: "user-3", name: "Victoria" }
];

이 배열은 어떤 사용자가 서비스에 가입했는지는 보여준다. 하지만 크리스가 누구와 연결되어 있는지는 알려주지 않는다.

관계를 사용자 객체 안에 직접 저장할 수도 있다.

const chris = {
  id: "user-1",
  name: "Chris",
  connectionIds: ["user-2", "user-3"]
};

데이터가 작고 메모리 안에서만 사용된다면 충분히 이해하기 쉬운 표현이다. 하지만 알렉스의 객체에도 크리스의 ID를 넣어야 한다면 같은 관계가 두 곳에 저장된다.

const alex = {
  id: "user-2",
  name: "Alex",
  connectionIds: ["user-1"]
};

크리스의 목록에서는 알렉스가 연결되어 있지만 알렉스의 목록에서는 크리스가 빠지는 불일치가 생길 수 있다. 사용자 객체가 커질수록 프로필 하나를 읽기 위해 필요하지 않은 관계까지 함께 불러올 가능성도 커진다.

사용자와 관계를 분리하면 각각의 책임이 명확해진다.

const users = [
  { id: "user-1", name: "Chris" },
  { id: "user-2", name: "Alex" }
];

const connections = [
  {
    userAId: "user-1",
    userBId: "user-2",
    status: "accepted"
  }
];

사용자는 정점이고 연결 정보는 두 사용자를 잇는 간선이다. 사용자 프로필이 변경되어도 관계를 다시 만들 필요가 없고, 관계 상태가 변경되어도 사용자 데이터를 복제하지 않아도 된다.

현실의 연결 관계는 다음과 같이 코드의 입력·상태·출력으로 변환된다.

입력
연결 요청을 보내는 사용자와 대상 사용자

상태
요청자, 수신자, 연결 상태, 생성 시각, 수락 시각

출력
연결 요청 결과와 두 사용자의 현재 관계

사용자가 화면에서 Connect 버튼을 누르는 것은 하나의 이벤트다. 서버는 그 이벤트를 받아 두 사용자의 현재 관계를 확인하고, 허용된 상태 전이가 무엇인지 판단한 뒤 관계를 저장한다.

그래프는 단순히 연결을 보여주는 결과가 아니다. 관계가 만들어지고 변경되고 탐색되는 서비스 상태를 표현한다.

모든 연결은 같은 방향을 가질까?

전문가 네트워킹 서비스에는 서로 다른 종류의 연결이 존재할 수 있다.

크리스가 알렉스를 팔로우한다고 해서 알렉스가 자동으로 크리스를 팔로우하는 것은 아니다.

Chris → Alex

팔로우는 방향이 있는 관계다.

반면 크리스와 빅토리아가 연결 요청을 수락하여 일촌이 되었다면 두 사람 모두 서로의 연결 목록에 나타난다.

Chris ↔ Victoria

이 관계는 양방향처럼 동작한다.

두 관계를 모두 같은 배열에 저장하면 의미가 사라진다.

// Bad: 연결의 종류와 방향을 알 수 없다.
const relationships = [
  ["user-1", "user-2"],
  ["user-1", "user-3"]
];

이 데이터만으로는 크리스가 알렉스를 팔로우하는 것인지, 두 사용자가 서로 연결된 것인지 판단할 수 없다.

관계의 종류와 방향을 명시해야 한다.

type Relationship =
  | {
      type: "follow";
      fromUserId: string;
      toUserId: string;
    }
  | {
      type: "connection";
      userAId: string;
      userBId: string;
      status: "pending" | "accepted" | "rejected";
    };

follow는 fromUserId에서 toUserId로 향하는 방향성 관계다. connection은 수락된 이후 두 사용자에게 동일한 의미를 가지지만, 요청 처리 과정에서는 누가 요청했는지도 별도로 필요할 수 있다.

type Connection = {
  requesterId: string;
  recipientId: string;
  status: "pending" | "accepted" | "rejected";
  requestedAt: Date;
  respondedAt: Date | null;
};

관계의 방향은 코드 구현 방식이 아니라 비즈니스 의미로 결정해야 한다.

  • 팔로우는 한 사용자가 다른 사용자의 게시물을 받아보는 단방향 관계다.
  • 연결 요청은 요청자와 수신자가 구분되는 단방향 이벤트다.
  • 수락된 연결은 두 사용자에게 동일하게 보이는 양방향 관계다.
  • 차단은 차단한 사용자와 차단당한 사용자가 구분되는 단방향 관계다.

화면에서 두 사용자를 선으로 연결해 보여준다는 이유만으로 모든 관계를 동일하게 저장해서는 안 된다. 선이 어떤 의미를 가지며 어느 방향으로 효력이 발생하는지 먼저 정의해야 한다.

연결 요청을 받으면 바로 관계를 추가해도 될까?

크리스가 알렉스에게 연결 요청을 보낸다고 해보자.

async function requestConnection(
  requesterId: string,
  recipientId: string
) {
  return connectionRepository.create({
    requesterId,
    recipientId,
    status: "pending"
  });
}

이 코드는 요청에 들어온 두 사용자 ID를 그대로 저장한다. 하지만 실제 서비스에서는 여러 조건을 먼저 확인해야 한다.

  • 요청자와 수신자가 실제로 존재하는가?
  • 크리스가 자기 자신에게 요청을 보내고 있지 않은가?
  • 두 사용자 사이에 이미 수락된 연결이 존재하지 않는가?
  • 같은 방향이나 반대 방향의 대기 중인 요청이 존재하지 않는가?
  • 어느 한쪽이 다른 사용자를 차단하지 않았는가?
  • 요청자가 연결 요청 제한을 초과하지 않았는가?
  • 대상 사용자가 연결 요청을 받을 수 있도록 설정했는가?

외부에서 받은 사용자 ID는 관계를 만들 권한까지 증명하지 않는다.

async function requestConnection(
  actorId: string,
  recipientId: string
) {
  if (actorId === recipientId) {
    throw new Error(
      "You cannot connect with yourself"
    );
  }

  const recipient =
    await userRepository.findActiveById(recipientId);

  if (!recipient) {
    throw new Error("User not found");
  }

  const isBlocked =
    await blockRepository.existsBetween(
      actorId,
      recipientId
    );

  if (isBlocked) {
    throw new Error("Connection is not allowed");
  }

  const existing =
    await connectionRepository.findBetween(
      actorId,
      recipientId
    );

  if (existing) {
    return existing;
  }

  return connectionRepository.create({
    requesterId: actorId,
    recipientId,
    status: "pending",
    requestedAt: new Date()
  });
}

서버는 인증된 사용자 ID인 actorId를 사용한다. 클라이언트가 요청 본문에 보낸 요청자 ID를 신뢰하지 않는다. 대상 사용자의 상태와 두 사용자 사이의 기존 관계도 확인한다.

이 검증은 단순한 입력 형식 검사가 아니다. 그래프에 새로운 간선을 추가해도 되는지를 판단하는 비즈니스 규칙이다.

두 사용자가 동시에 요청하면 관계가 두 개 생기지 않을까?

크리스와 알렉스가 거의 동시에 서로에게 연결 요청을 보낼 수 있다.

Chris → Alex
Alex → Chris

두 요청이 각각 기존 관계를 조회했을 때 아직 아무것도 저장되지 않았다면 두 요청 모두 새 관계를 생성할 수 있다.

const existing =
  await connectionRepository.findBetween(
    requesterId,
    recipientId
  );

if (!existing) {
  await connectionRepository.create({
    requesterId,
    recipientId,
    status: "pending"
  });
}

조회 후 생성하는 두 작업은 하나의 원자적인 작업이 아니다. 두 서버가 동시에 실행하면 같은 사용자 쌍에 관계가 여러 개 만들어질 수 있다.

양방향 연결을 하나의 행으로 저장한다면 사용자 ID의 순서를 정규화할 수 있다.

function normalizeUserPair(
  firstUserId: string,
  secondUserId: string
) {
  return firstUserId < secondUserId
    ? [firstUserId, secondUserId]
    : [secondUserId, firstUserId];
}

Chris-Alex와 Alex-Chris를 항상 동일한 순서로 바꾸는 것이다.

const [userAId, userBId] = normalizeUserPair(
  requesterId,
  recipientId
);

데이터베이스에는 정규화된 사용자 쌍이 한 번만 존재하도록 제약을 둔다.

CREATE TABLE connections (
  id UUID PRIMARY KEY,
  user_a_id UUID NOT NULL REFERENCES users(id),
  user_b_id UUID NOT NULL REFERENCES users(id),
  requester_id UUID NOT NULL REFERENCES users(id),
  status VARCHAR(20) NOT NULL,
  requested_at TIMESTAMPTZ NOT NULL,
  responded_at TIMESTAMPTZ NULL,
  CHECK (user_a_id <> user_b_id),
  UNIQUE (user_a_id, user_b_id)
);

이제 두 요청이 동시에 실행되어도 데이터베이스는 동일한 사용자 쌍의 두 번째 관계 생성을 거부한다.

애플리케이션은 충돌을 서비스 의미에 맞게 처리할 수 있다.

async function requestConnection(
  actorId: string,
  recipientId: string
) {
  const [userAId, userBId] = normalizeUserPair(
    actorId,
    recipientId
  );

  try {
    return await connectionRepository.create({
      userAId,
      userBId,
      requesterId: actorId,
      status: "pending"
    });
  } catch (error) {
    if (isUniqueConstraintError(error)) {
      return connectionRepository.findByPair(
        userAId,
        userBId
      );
    }

    throw error;
  }
}

그래프에서는 간선을 추가하는 코드가 짧아 보이지만 실제 서비스에서는 중복 관계와 동시 요청을 통제해야 한다. 애플리케이션의 사전 조회는 사용자에게 적절한 메시지를 제공하고, 데이터베이스 제약은 마지막 순간의 경쟁 상태에서도 데이터 무결성을 지킨다.

친구의 친구를 찾으면 추천이 완성될까?

크리스에게 새로운 연결을 추천하기 위해 연결된 사람의 연결을 조회할 수 있다.

Chris ─ Alex ─ Victoria

크리스와 알렉스가 연결되어 있고 알렉스와 빅토리아가 연결되어 있다면 빅토리아는 크리스의 2단계 연결이다.

메모리에서는 다음과 같이 찾을 수 있다.

function findSecondDegreeConnections(
  userId: string,
  graph: Map<string, string[]>
) {
  const direct = new Set(graph.get(userId) ?? []);
  const candidates = new Set<string>();

  for (const connectionId of direct) {
    for (
      const candidateId
      of graph.get(connectionId) ?? []
    ) {
      if (
        candidateId !== userId &&
        !direct.has(candidateId)
      ) {
        candidates.add(candidateId);
      }
    }
  }

  return [...candidates];
}

이 코드는 직접 연결된 사용자를 한 번 확인하고, 그 사용자의 연결을 다시 확인한다. 자기 자신과 이미 연결된 사용자는 제외한다.

하지만 2단계 연결이라는 이유만으로 바로 화면에 보여주면 안 된다.

const visibleCandidates = candidates.filter(
  (candidate) =>
    !candidate.isDeactivated &&
    !candidate.isBlocked &&
    candidate.allowsRecommendations
);

실제 추천에서는 다음과 같은 조건이 추가된다.

  • 차단하거나 차단당한 사용자는 제외한다.
  • 탈퇴하거나 정지된 사용자는 제외한다.
  • 이미 대기 중인 연결 요청이 있는 사용자는 제외한다.
  • 추천 노출을 허용하지 않은 사용자는 제외한다.
  • 같은 사용자에게 너무 자주 노출한 후보는 제외할 수 있다.
  • 공통 연결 수, 같은 회사와 관심 분야에 따라 순위를 계산할 수 있다.

따라서 추천 과정은 하나의 탐색으로 끝나지 않는다.

후보 수집
2단계 연결에서 가능한 사용자 찾기

후보 제외
차단, 탈퇴, 기존 연결, 대기 요청 제거

점수 계산
공통 연결, 관심 분야, 활동 상태 반영

정렬과 제한
점수가 높은 후보 일부만 반환

그래프 탐색은 추천 후보를 만드는 과정 중 하나다. 추천 여부를 결정하는 전체 비즈니스 규칙은 아니다.

탐색을 계속 넓히면 더 좋은 후보를 찾을 수 있을까?

2단계 연결에서 후보가 부족하다면 3단계, 4단계 관계까지 탐색하고 싶을 수 있다. 하지만 연결 수가 많은 서비스에서는 탐색 범위가 빠르게 커진다.

한 사용자가 평균 100명과 연결되어 있다고 단순하게 가정해보자.

1단계 후보: 최대 100명
2단계 후보: 최대 10,000명
3단계 후보: 최대 1,000,000명

실제로는 중복 연결이 많아 이보다 줄어들 수 있지만, 깊이가 한 단계 늘어날 때 확인해야 할 관계 수가 크게 증가할 수 있다는 문제는 남는다.

아무 제한 없이 관계를 따라가는 코드는 위험하다.

// Bad: 깊이와 방문 수 제한이 없다.
async function exploreConnections(userId: string) {
  const connections =
    await connectionRepository.findByUserId(userId);

  return Promise.all(
    connections.map((connection) =>
      exploreConnections(connection.userId)
    )
  );
}

순환 관계가 있으면 이미 확인한 사용자를 반복해서 방문한다. 소셜 관계에는 다음과 같은 순환이 자연스럽게 존재한다.

Chris → Alex → Victoria → Chris

그래프에서 순환은 잘못된 데이터가 아닐 수 있다. 트리와 달리 여러 경로를 통해 같은 정점으로 돌아오는 관계가 자연스럽게 존재한다.

따라서 탐색할 때 방문한 사용자를 기록해야 한다.

async function findReachableUsers(
  startUserId: string,
  maxDepth: number
) {
  const visited = new Set([startUserId]);
  let currentLevel = [startUserId];
  const result: string[] = [];

  for (
    let depth = 0;
    depth < maxDepth;
    depth += 1
  ) {
    const nextLevel: string[] = [];

    for (const userId of currentLevel) {
      const connectionIds =
        await connectionRepository.findAcceptedIds(
          userId
        );

      for (const connectionId of connectionIds) {
        if (visited.has(connectionId)) {
          continue;
        }

        visited.add(connectionId);
        result.push(connectionId);
        nextLevel.push(connectionId);
      }
    }

    currentLevel = nextLevel;
  }

  return result;
}

visited는 같은 사용자를 여러 경로에서 다시 발견하더라도 한 번만 처리하게 한다. maxDepth는 서비스가 필요로 하는 범위까지만 탐색하도록 제한한다.

하지만 이 코드를 그대로 사용하면 사용자마다 데이터베이스를 반복 조회하는 문제가 생길 수 있다. 후보가 많아질수록 쿼리 수도 함께 증가한다.

사용자 한 명 조회
→ 연결된 사용자마다 다시 조회
→ 그 사용자의 연결마다 다시 조회

실제 서비스에서는 한 단계의 관계를 묶어서 조회하거나, 탐색 전용 인덱스와 미리 계산된 후보를 사용할 수 있다.

const nextConnectionIds =
  await connectionRepository.findAcceptedIdsForUsers(
    currentLevel
  );

알고리즘의 방문 순서만 생각해서는 부족하다. 탐색 과정에서 데이터가 어디에 저장되어 있고, 각 단계가 몇 번의 데이터베이스 또는 네트워크 요청을 만드는지도 함께 계산해야 한다.

최단 연결 경로가 실제로 가장 좋은 관계일까?

크리스가 빅토리아와 몇 단계 떨어져 있는지 보여주고 싶다고 해보자.

Chris ─ Alex ─ Victoria

이 경로의 거리는 간선 두 개이므로 2다. 모든 연결을 같은 비용으로 본다면 가까운 사용자부터 탐색하는 BFS를 사용할 수 있다.

type QueueItem = {
  userId: string;
  path: string[];
};

function findShortestConnectionPath(
  graph: Map<string, string[]>,
  startUserId: string,
  targetUserId: string
) {
  const queue: QueueItem[] = [
    {
      userId: startUserId,
      path: [startUserId]
    }
  ];

  const visited = new Set([startUserId]);

  while (queue.length > 0) {
    const current = queue.shift()!;

    if (current.userId === targetUserId) {
      return current.path;
    }

    for (
      const nextUserId
      of graph.get(current.userId) ?? []
    ) {
      if (visited.has(nextUserId)) {
        continue;
      }

      visited.add(nextUserId);
      queue.push({
        userId: nextUserId,
        path: [...current.path, nextUserId]
      });
    }
  }

  return null;
}

이 코드는 시작점에서 가까운 사용자부터 확인하므로 간선 수가 가장 적은 경로를 찾는다.

하지만 서비스에서 연결 단계가 짧다는 사실이 관계의 품질까지 보장하지는 않는다.

경로 A
Chris → 같은 팀 동료 → Victoria

경로 B
Chris → 거의 모르는 사용자 → Victoria

두 경로 모두 두 단계지만 첫 번째 경로가 소개 요청에 더 적합할 수 있다.

관계에 의미 있는 비용이나 점수를 추가할 수 있다.

type ConnectionEdge = {
  userId: string;
  collaborationCount: number;
  lastInteractionAt: Date | null;
};

함께 일한 횟수나 최근 상호작용을 이용해 관계 강도를 계산할 수 있다.

function calculateConnectionStrength(
  edge: ConnectionEdge
) {
  const collaborationScore =
    Math.min(edge.collaborationCount * 10, 50);

  const recencyScore = edge.lastInteractionAt
    ? calculateRecencyScore(edge.lastInteractionAt)
    : 0;

  return collaborationScore + recencyScore;
}

다만 이 점수는 객관적인 진실이 아니다. 서비스가 특정 목적을 위해 만든 계산 결과다. 협업 횟수가 많다고 반드시 친밀한 관계는 아니며, 오래된 연결도 여전히 중요할 수 있다.

따라서 다음 데이터를 구분해야 한다.

원본 데이터
연결 상태, 협업 기록, 상호작용 시각

계산 데이터
관계 강도 점수, 추천 점수, 예상 연결 품질

출력 데이터
사용자에게 노출할 추천 후보와 설명

점수 계산 규칙이 바뀌면 원본 데이터에서 다시 계산할 수 있어야 한다. 계산된 점수를 유일한 관계 정보로 저장하면 점수의 근거를 확인하거나 새로운 기준으로 재평가하기 어렵다.

차단은 연결을 삭제하는 것과 같을까?

크리스가 알렉스를 차단하면 기존 연결을 삭제하는 것만으로 충분해 보일 수 있다.

await connectionRepository.deleteBetween(
  chrisId,
  alexId
);

하지만 연결 삭제와 차단은 의미가 다르다.

연결을 삭제하면 두 사용자는 현재 연결되어 있지 않다는 뜻이다. 차단은 특정 사용자가 다른 사용자와 상호작용하지 않겠다는 별도의 관계다.

type Block = {
  blockerId: string;
  blockedUserId: string;
  createdAt: Date;
};

차단은 여러 기능에 영향을 준다.

  • 연결 요청을 보낼 수 없어야 한다.
  • 사용자 검색 결과에서 제외될 수 있다.
  • 추천 후보에 나타나지 않아야 한다.
  • 프로필과 게시물 접근이 제한될 수 있다.
  • 메시지를 보낼 수 없어야 한다.
  • 공통 연결 정보에서 존재가 노출되지 않아야 할 수 있다.

따라서 추천 후보를 조회한 뒤에만 차단 사용자를 제거하면 부족할 수 있다.

// Bad: 후보를 모두 가져온 뒤 화면에서만 제거한다.
const candidates =
  await recommendationRepository.findCandidates(userId);

return candidates.filter(
  (candidate) => !blockedIds.has(candidate.id)
);

후보 조회 과정에서 차단 관계가 고려되지 않으면 차단된 사용자의 프로필 정보를 이미 불러왔거나 로그와 캐시에 남겼을 수 있다. 다른 API가 같은 필터를 빠뜨리면 정보가 다시 노출될 수도 있다.

접근 제어와 후보 제외 규칙을 공통 정책으로 관리하는 편이 안전하다.

async function canUsersInteract(
  firstUserId: string,
  secondUserId: string
) {
  const blocked =
    await blockRepository.existsBetween(
      firstUserId,
      secondUserId
    );

  return !blocked;
}

다만 모든 요청에서 이 함수를 개별 호출하면 데이터베이스 조회가 지나치게 늘어날 수 있다. 중요한 것은 검증을 생략하는 것이 아니라 여러 후보의 차단 관계를 한 번에 조회하거나, 안전하게 갱신되는 차단 인덱스를 사용하는 것이다.

const blockedCandidateIds =
  await blockRepository.findBlockedIdsAmong(
    userId,
    candidateIds
  );

그래프의 간선은 단순한 탐색 경로가 아니다. 어떤 간선은 접근을 허용하고, 어떤 간선은 접근을 금지하며, 다른 간선의 효력을 바꾸기도 한다.

관계형 데이터베이스에서도 그래프를 저장할 수 있을까?

그래프를 사용한다고 반드시 그래프 전용 데이터베이스가 필요한 것은 아니다. 사용자 관계는 관계형 데이터베이스의 테이블로도 저장할 수 있다.

CREATE TABLE follows (
  follower_id UUID NOT NULL REFERENCES users(id),
  followed_id UUID NOT NULL REFERENCES users(id),
  created_at TIMESTAMPTZ NOT NULL,
  PRIMARY KEY (follower_id, followed_id),
  CHECK (follower_id <> followed_id)
);

특정 사용자가 팔로우하는 사람을 찾는 조회는 단순하다.

SELECT followed_id
FROM follows
WHERE follower_id = $1;

반대 방향 조회도 자주 사용한다면 별도 인덱스가 필요하다.

CREATE INDEX idx_follows_followed_id
ON follows(followed_id);

연결 관계는 사용자 쌍을 정규화하여 저장할 수 있다.

CREATE TABLE connections (
  user_a_id UUID NOT NULL REFERENCES users(id),
  user_b_id UUID NOT NULL REFERENCES users(id),
  status VARCHAR(20) NOT NULL,
  requested_at TIMESTAMPTZ NOT NULL,
  accepted_at TIMESTAMPTZ NULL,
  PRIMARY KEY (user_a_id, user_b_id),
  CHECK (user_a_id < user_b_id)
);

1단계 관계 조회와 간단한 2단계 후보 조회, 트랜잭션과 데이터 무결성이 중요하다면 관계형 데이터베이스만으로 충분할 수 있다.

반면 여러 종류의 관계를 여러 단계에 걸쳐 자주 탐색하고 경로 자체가 중요한 서비스라면 그래프 전용 저장소나 탐색 인덱스를 검토할 수 있다.

관계형 데이터베이스가 잘 맞는 경우
- 관계 종류가 비교적 단순하다.
- 한두 단계 조회가 대부분이다.
- 사용자와 관계 상태의 트랜잭션이 중요하다.
- 기존 운영 환경과 도구를 재사용하고 싶다.

그래프 전용 저장소를 검토할 경우
- 다양한 관계를 여러 단계로 자주 탐색한다.
- 연결 경로와 패턴 검색이 핵심 기능이다.
- 관계를 따라가는 복잡한 질의가 지속적으로 증가한다.
- 측정 결과 현재 저장 방식이 실제 병목이다.

데이터베이스 종류는 데이터가 그래프처럼 보인다는 이유만으로 결정하지 않는다. 서비스가 자주 수행하는 조회와 변경, 필요한 일관성, 운영 역량을 함께 판단해야 한다.

원본 관계와 추천 그래프는 같은 데이터일까?

사용자가 많아지면 요청마다 전체 관계를 따라 추천 후보를 계산하기 어려울 수 있다. 백그라운드 작업이 미리 후보와 점수를 계산하도록 만들 수 있다.

type Recommendation = {
  userId: string;
  candidateUserId: string;
  score: number;
  reason: "mutual_connections" | "same_company";
  calculatedAt: Date;
};

화면 요청에서는 계산된 결과 일부만 읽는다.

const recommendations =
  await recommendationRepository.findTopCandidates({
    userId,
    limit: 20
  });

이 방식은 응답 시간을 줄일 수 있지만 추천 데이터가 현재 관계보다 늦게 갱신될 수 있다. 크리스가 알렉스를 차단한 직후 오래된 추천 데이터에 알렉스가 남아 있을 수 있다.

따라서 계산된 후보를 그대로 반환하기 전에 현재의 중요한 상태를 다시 확인해야 한다.

const safeRecommendations =
  await recommendationService.removeUnavailableUsers({
    userId,
    recommendations
  });

데이터의 책임을 구분하면 다음과 같다.

Source of Truth
사용자 상태, 수락된 연결, 팔로우, 차단 관계

계산 데이터
2단계 연결 후보, 공통 연결 수, 관계 강도와 추천 점수

임시 데이터
캐시된 연결 목록, 추천 응답 캐시, 탐색용 인덱스

추천 결과는 원본 관계에서 다시 만들 수 있어야 한다. 차단과 계정 정지처럼 즉시 반영되어야 하는 상태는 오래된 추천 데이터보다 우선해야 한다.

모든 데이터를 실시간으로 계산하는 것도 비용이 크고, 모든 결과를 미리 계산하는 것도 변경 반영이 늦어진다. 어떤 데이터가 즉시 정확해야 하고 어떤 결과가 잠시 오래되어도 되는지 구분하는 것이 중요하다.

연결 수를 사용자 테이블에 저장하면 더 빠르지 않을까?

프로필마다 연결 수를 반복해서 계산하면 비용이 커질 수 있다.

SELECT COUNT(*)
FROM connections
WHERE
  status = 'accepted'
  AND (
    user_a_id = $1 OR
    user_b_id = $1
  );

조회 속도를 높이기 위해 사용자 통계에 연결 수를 저장할 수 있다.

type UserStats = {
  userId: string;
  connectionCount: number;
};

연결이 수락되면 두 사용자의 연결 수를 증가시킨다.

await database.transaction(async (tx) => {
  await tx.connections.accept(connectionId);

  await tx.userStats.incrementConnectionCount(
    userAId
  );

  await tx.userStats.incrementConnectionCount(
    userBId
  );
});

동일한 트랜잭션에서 처리하면 관계 상태와 카운트를 함께 변경할 수 있다. 하지만 통계가 별도 분석 시스템이나 캐시에 있다면 즉시 일치시키기 어려울 수 있다.

이때 연결 행은 원본이고 connectionCount는 계산 데이터다. 값이 어긋났을 때 원본 관계를 기준으로 다시 계산할 수 있어야 한다.

async function rebuildConnectionCount(
  userId: string
) {
  const count =
    await connectionRepository.countAcceptedByUserId(
      userId
    );

  await userStatsRepository.setConnectionCount(
    userId,
    count
  );
}

빠른 조회를 위해 값을 중복 저장하는 것은 가능하다. 다만 어느 값이 원본인지, 언제 갱신하는지, 실패했을 때 어떻게 복구하는지를 함께 설계해야 한다.

모든 관계를 API 응답에 포함해야 할까?

사용자 프로필을 조회할 때 연결 목록 전체를 함께 반환하는 API를 만들 수 있다.

async function getProfile(userId: string) {
  const user = await userRepository.findById(userId);
  const connections =
    await connectionRepository.findAllByUserId(userId);

  return {
    ...user,
    connections
  };
}

연결이 열 명뿐이라면 문제가 없을 수 있다. 하지만 수만 명과 연결된 사용자의 프로필을 조회하면 응답 크기와 데이터베이스 부하가 크게 증가한다.

프로필과 관계 목록의 생명주기는 다르다.

프로필
이름, 소개, 현재 직무

관계 요약
연결 수, 현재 사용자와의 관계

관계 목록
페이지 단위로 조회할 연결 사용자

필요한 데이터만 분리해 반환할 수 있다.

async function getProfile(
  viewerId: string,
  profileUserId: string
) {
  const [user, relationship, stats] =
    await Promise.all([
      userRepository.findVisibleProfile(
        viewerId,
        profileUserId
      ),
      relationshipRepository.findBetween(
        viewerId,
        profileUserId
      ),
      userStatsRepository.findByUserId(
        profileUserId
      )
    ]);

  return {
    user,
    relationship,
    connectionCount:
      stats?.connectionCount ?? 0
  };
}

연결 목록은 별도의 페이지네이션 API로 제공한다.

async function getConnections(
  viewerId: string,
  profileUserId: string,
  cursor?: string
) {
  await profilePolicy.assertCanViewConnections(
    viewerId,
    profileUserId
  );

  return connectionRepository.findPage({
    userId: profileUserId,
    cursor,
    limit: 30
  });
}

그래프가 연결된 구조라고 해서 한 번의 응답에서 연결된 모든 데이터를 따라가야 하는 것은 아니다. API는 화면이 필요로 하는 탐색 범위와 접근 권한에 맞춰 경계를 정해야 한다.

그래프 관계를 설계하기 전에 확인할 질문

  1. 서비스에서 정점으로 표현할 대상은 무엇이며 각각 독립적인 생명주기를 가지는가?
  2. 간선은 어떤 현실의 관계를 의미하며 단순한 참조와 어떻게 다른가?
  3. 관계는 단방향인가, 양방향인가?
  4. 연결 요청과 수락된 연결처럼 하나의 관계가 여러 상태를 가지는가?
  5. 누가 관계를 생성하고 변경하고 삭제할 권한을 가지는가?
  6. 외부에서 받은 사용자 ID를 인증된 사용자 정보와 구분하는가?
  7. 자기 자신과 연결하는 관계를 허용해야 하는가?
  8. 같은 사용자 쌍에 중복 관계가 만들어지지 않도록 데이터베이스 제약이 있는가?
  9. 반대 방향의 동시 요청도 같은 관계로 판단해야 하는가?
  10. 관계의 상태 전이가 pending → accepted처럼 허용된 순서를 따르는가?
  11. 차단 관계가 검색, 추천, 메시지와 프로필 공개 범위에 모두 반영되는가?
  12. 연결을 탐색할 때 이미 방문한 정점을 기록하여 반복 탐색을 막는가?
  13. 탐색 깊이, 최대 방문 수와 응답 시간을 제한하는가?
  14. 한 단계가 늘어날 때 후보 수와 데이터베이스 조회 수가 얼마나 증가하는가?
  15. 반복적인 개별 조회가 발생한다면 여러 정점의 관계를 묶어서 조회할 수 있는가?
  16. 추천 후보 수집, 제외, 점수 계산과 정렬의 책임이 구분되어 있는가?
  17. 연결 단계가 짧다는 사실과 관계 품질이 높다는 판단을 혼동하지 않는가?
  18. 관계에 가중치를 부여한다면 그 값의 근거와 갱신 주기가 명확한가?
  19. 원본 관계와 추천 점수, 연결 수, 캐시를 구분했는가?
  20. 계산 데이터가 잘못되었을 때 원본 관계에서 다시 만들 수 있는가?
  21. 차단, 계정 정지와 탈퇴처럼 즉시 반영해야 하는 상태는 오래된 캐시보다 우선하는가?
  22. 관계 삭제가 관련 추천, 알림, 메시지 권한과 캐시에 어떤 영향을 주는가?
  23. 연결 목록 전체를 한 번에 반환하지 않고 필요한 범위만 페이지 단위로 조회하는가?
  24. 관계를 저장하는 필드에 양방향 조회를 위한 적절한 인덱스가 있는가?
  25. 관계형 데이터베이스로 충분한 문제에 운영 비용이 큰 별도 저장소를 추가하고 있지 않은가?
  26. 반대로 여러 단계의 경로 탐색이 핵심인데 매 요청마다 복잡한 조인과 개별 조회를 반복하고 있지 않은가?
  27. 관계 데이터에 개인정보나 접근 권한 정보가 포함된다면 조회 경로마다 권한을 검증하는가?
  28. 사용자 탈퇴 시 연결과 차단, 추천 데이터와 캐시를 어떻게 처리할지 정했는가?
  29. 관계 변경과 통계 갱신 사이에 실패가 발생했을 때 복구할 수 있는가?
  30. 그래프 탐색 결과가 비즈니스 결정의 후보인지, 최종 결과인지 구분했는가?

그래프는 연결을 저장하는 구조가 아니라 관계를 해석하는 경계다

그래프의 기본 모양은 정점과 간선이다. 하지만 실제 전문가 네트워킹 서비스에서 중요한 것은 사용자를 점으로 그리고 선으로 연결하는 일이 아니다. 팔로우, 연결, 요청과 차단이 각각 어떤 의미와 방향을 가지는지 정의하고, 필요한 관계 범위만 안전하게 탐색하는 것이다.

관계를 추가할 때는 사용자 ID를 그대로 신뢰해서는 안 된다. 자기 자신과의 연결, 중복 요청, 차단 상태와 권한을 검증해야 한다. 동시에 실행되는 요청이 같은 관계를 두 번 만들지 않도록 데이터베이스 제약과 트랜잭션도 필요하다.

연결을 탐색할 때는 이미 방문한 사용자를 기록하고 탐색 깊이와 후보 수를 제한해야 한다. 그래프에서는 순환이 자연스러울 수 있으므로 같은 사용자를 반복해서 처리하지 않아야 한다. 알고리즘의 실행 횟수뿐 아니라 탐색 과정이 만드는 데이터베이스와 네트워크 요청도 함께 판단해야 한다.

추천 점수, 관계 강도와 연결 수는 원본 관계에서 만들어진 계산 데이터다. 빠른 응답을 위해 캐시하거나 미리 계산할 수 있지만, 차단과 계정 상태처럼 즉시 정확해야 하는 정보는 현재 원본을 기준으로 다시 검증해야 한다.

관계형 데이터베이스와 그래프 전용 저장소 중 무엇을 사용할지도 데이터의 모양만으로 결정하지 않는다. 자주 실행되는 조회의 깊이, 관계 변경 빈도, 일관성 요구와 운영 비용을 기준으로 선택해야 한다.

결국 그래프를 선택한다는 것은 대상을 선으로 연결하겠다는 뜻이 아니다. 서비스 안의 대상들이 어떤 의미로 연결되고, 그 연결을 어디까지 탐색하며, 관계의 변화가 다른 기능에 어떤 영향을 주는지를 명시적으로 설계하겠다는 판단이다.

다음 글에서는 자료구조 선택이 알고리즘을 구현하기 전에 한 번 결정하고 끝나는 일이 아니라, 데이터의 저장 위치와 접근 방식에 따라 계속 달라지는 이유를 살펴본다.

profile
vx_developer
Vision eXperience Developer
이전 포스트

트리는 부모와 자식으로 데이터를 연결하는 구조가 아니다

0개의 댓글