공간 복잡도는 메모리 사용량만 계산하는 개념이 아니다

vx_developer·2026년 9월 19일

코테보다가

목록 보기

18/25

알고리즘을 처음 배울 때 공간 복잡도는 입력 크기가 증가할수록 알고리즘이 사용하는 메모리가 얼마나 늘어나는지 나타내는 개념으로 배운다.

중복된 배달 기사 ID를 제거하는 코드를 생각해보자.

function uniqueDriverIds(driverIds) {
  const seen = new Set();

  for (const driverId of driverIds) {
    seen.add(driverId);
  }

  return [...seen];
}

기사 ID가 n개라면 seen에는 최대 n개의 값이 저장된다.

따라서 추가로 사용하는 공간은 O(n)이라고 설명할 수 있다.

배열, 객체, 재귀 호출과 임시 변수가 입력에 따라 얼마나 커지는지 이해하기에는 유용한 설명이다.

하지만 실제 배달 서비스에서 공간에 관한 판단은 함수 안에 생성된 배열의 크기로 끝나지 않는다.

주변 기사를 찾을 때마다 모든 기사의 위치를 탐색할 것인가?
빠른 조회를 위해 지역별 기사 목록을 미리 저장할 것인가?
미리 만든 목록은 서버 메모리, 원격 캐시와 데이터베이스 중 어디에 둘 것인가?
서버가 여러 대라면 같은 데이터를 몇 벌이나 보관하게 되는가?
기사가 이동하거나 배달을 수락하면 미리 저장한 목록을 어떻게 갱신할 것인가?
오래된 위치를 언제 제거할 것인가?
빠른 후보 조회 결과와 실제 배정 가능한 상태가 다르면 무엇을 신뢰할 것인가?
메모리를 더 사용해 줄인 시간이 실제로 사용자 경험이나 서버 비용을 개선하는가?
저장 공간이 부족할 때 어떤 데이터를 먼저 버릴 것인가?
추가 인덱스 때문에 위치 갱신이 느려지지는 않는가?

형식적인 공간 복잡도는 알고리즘이 사용하는 메모리의 증가를 분석한다.

서비스 설계에서는 그 사고를 한 단계 더 확장해야 한다.

실제 서비스에서 공간 복잡도를 생각한다는 것은 메모리 크기를 세는 데 그치지 않고, 처리 시간을 줄이기 위해 어떤 파생 데이터를 어느 저장소에 얼마나 보관하며 원본이 바뀔 때 언제 갱신하고 제거할지 결정하는 일이다.

같은 `O(n)` 공간이라도 무엇을 저장하는지 구분해야 한다

크리스가 음식 주문을 완료하면 서비스는 배달 가능한 기사 후보를 찾아야 한다.

먼저 모든 기사 중 주문 지역에 있는 기사를 찾을 수 있다.

function findAvailableDrivers(
  drivers,
  deliveryAreaId
) {
  const candidates = [];

  for (const driver of drivers) {
    if (
      driver.areaId === deliveryAreaId &&
      driver.status === "AVAILABLE"
    ) {
      candidates.push(driver);
    }
  }

  return candidates;
}

전체 기사 수를 n, 조건을 만족하는 기사 수를 k라고 하면 모든 기사를 확인하는 시간은 O(n)이다.

결과 배열에는 최대 k명의 기사가 저장되므로 결과 공간은 O(k)다.

이때 입력, 보조 상태와 출력을 구분해야 한다.

구분	이 함수에서의 의미
입력 공간	함수에 전달된 `drivers` 목록
보조 공간	반복 중 계산을 위해 추가로 사용하는 상태
출력 공간	반환할 `candidates` 배열
장기 저장 공간	요청이 끝난 뒤에도 유지하는 인덱스나 캐시

이 함수가 직접 추가한 계산용 상태는 많지 않다.

그러나 결과로 기사 목록을 반환해야 하므로 후보 수만큼의 공간은 필요하다.

출력 자체에 필요한 공간과 알고리즘이 선택적으로 사용하는 보조 공간을 섞으면 개선 가능성을 잘못 판단할 수 있다.

예를 들어 후보 기사 100명을 반환해야 한다면 그 100명을 표현할 공간은 필요하다. 반면 모든 기사 정보를 복사한 중간 배열은 제거할 수 있을지도 모른다.

function findAvailableDriverIds(
  drivers,
  deliveryAreaId
) {
  const candidateIds = [];

  for (const driver of drivers) {
    if (
      driver.areaId === deliveryAreaId &&
      driver.status === "AVAILABLE"
    ) {
      candidateIds.push(driver.id);
    }
  }

  return candidateIds;
}

이 코드는 후보 기사 객체 전체가 아니라 ID만 결과에 저장한다.

복잡도 표기는 여전히 O(k)지만 실제 메모리와 전송량은 줄어들 수 있다.

공간 복잡도는 증가 방식을 보여준다. 실제 공간의 크기를 판단하려면 항목 하나가 얼마나 큰지도 확인해야 한다.

시간을 줄이기 위해 공간을 사용할 수 있다

매칭 요청이 들어올 때마다 전체 기사를 탐색하면 구현은 단순하다.

하지만 기사 100만 명 중 특정 지역의 후보 20명을 찾기 위해 매번 100만 명을 확인하는 방식은 요청이 많아질수록 부담이 커진다.

지역별 기사 목록을 미리 만들 수 있다.

function buildDriversByArea(drivers) {
  const driversByArea = new Map();

  for (const driver of drivers) {
    if (driver.status !== "AVAILABLE") {
      continue;
    }

    const driverIds =
      driversByArea.get(driver.areaId) ??
      new Set();

    driverIds.add(driver.id);
    driversByArea.set(
      driver.areaId,
      driverIds
    );
  }

  return driversByArea;
}

이 함수는 사용 가능한 기사 ID를 지역별로 나눈다.

전체 기사를 한 번 확인하므로 구성 시간은 O(n)이고, 기사 ID를 추가로 보관하므로 공간은 O(n)이다.

인덱스가 만들어진 뒤에는 특정 지역의 후보를 바로 찾을 수 있다.

function findCandidateDriverIds(
  driversByArea,
  deliveryAreaId
) {
  return [
    ...(driversByArea.get(
      deliveryAreaId
    ) ?? []),
  ];
}

이제 모든 기사를 매번 탐색하지 않는다.

해당 지역에 저장된 기사 ID만 읽으면 된다. 반환할 후보가 k명이라면 결과를 만드는 비용은 O(k)에 가깝다.

두 방식의 차이는 다음과 같다.

방식	요청 시 탐색	추가 저장 공간
모든 기사 탐색	`O(n)`	결과 공간 중심
지역별 인덱스 사용	`O(k)`	인덱스 `O(n)`과 결과 `O(k)`
데이터베이스 지역 조회	인덱스 구조에 따라 다름	데이터베이스 인덱스 공간
캐시된 후보 목록 사용	후보 크기에 비례	캐시와 원본의 중복 저장

지역별 인덱스는 계산을 없앤 것이 아니다.

전체 기사 정보를 미리 분류해 저장함으로써 반복되는 매칭 요청의 탐색 시간을 줄인 것이다.

이처럼 시간과 공간은 자주 교환된다.

추가 공간을 사용한다
→ 반복 계산이나 탐색을 줄인다
→ 조회 시간을 줄일 수 있다
→ 대신 생성, 갱신과 삭제 책임이 생긴다

공간 복잡도를 실무에 적용하면 “얼마나 메모리를 사용하는가?” 다음에 “그 공간이 어떤 시간을 줄이는가?”를 물어야 한다.

한 번만 조회한다면 미리 만든 구조가 더 비쌀 수 있다

빠른 조회 구조가 항상 이득인 것은 아니다.

기사 목록 30명에서 후보를 한 번 찾기 위해 지역별 인덱스를 새로 만들 수 있다.

const driversByArea =
  buildDriversByArea(drivers);

const candidates =
  findCandidateDriverIds(
    driversByArea,
    deliveryAreaId
  );

인덱스를 만드는 데 전체 기사 목록을 한 번 확인하고 추가 메모리를 사용한다.

그 뒤 조회는 한 번만 실행된다.

이 상황에서는 배열을 직접 탐색하는 편이 더 단순할 수 있다.

const candidates =
  findAvailableDriverIds(
    drivers,
    deliveryAreaId
  );

미리 저장하는 방식이 유리하려면 구성 비용을 여러 번의 조회에 나누어 사용할 수 있어야 한다.

다음 질문이 필요하다.

같은 기사 목록에서 후보 조회가 몇 번 실행되는가?
기사 위치와 상태는 얼마나 자주 바뀌는가?
인덱스를 한 번 만든 뒤 얼마나 오래 재사용하는가?
인덱스를 갱신하는 비용이 조회에서 줄이는 비용보다 작은가?
기사 수가 현재 어느 정도이며 어디까지 증가하는가?
요청마다 새로 만들고 있지는 않은가?

예를 들어 기사 목록을 한 번 조회하고 후보 검색도 한 번만 한다면 단순 탐색이 적절할 수 있다.

반대로 수십만 명의 기사 상태를 기준으로 초당 수천 건의 매칭을 수행한다면 조회용 구조를 유지할 가치가 커진다.

공간을 더 사용하는 선택은 반복해서 줄일 시간이 있을 때 의미가 있다.

데이터의 생명주기가 다르면 같은 공간으로 계산해서는 안 된다

배달 매칭 서비스에는 여러 종류의 데이터가 있다.

각 데이터가 존재하는 시간도 다르다.

데이터	일반적인 생명주기
한 요청의 후보 배열	요청이 끝날 때까지
함수의 임시 `Set`	함수 실행이 끝날 때까지
서버 메모리의 지역 인덱스	프로세스가 종료될 때까지
원격 캐시의 후보 목록	정해진 만료 시간까지
기사의 최신 위치	다음 위치가 저장될 때까지
위치 이동 기록	보존 정책에 따라 수일 또는 수개월
데이터베이스 인덱스	스키마에서 제거할 때까지

다음 코드는 요청마다 모든 기사를 복사한다.

function prepareMatching(drivers) {
  const copiedDrivers = drivers.map(
    (driver) => ({ ...driver })
  );

  return buildDriversByArea(
    copiedDrivers
  );
}

요청이 끝나면 복사본과 인덱스를 모두 버린다.

동시에 요청 1,000건이 실행되면 비슷한 데이터를 1,000번 복사할 수 있다.

요청마다 필요한 작은 상태와 여러 요청이 공유할 수 있는 상태를 구분해야 한다.

const driversByArea =
  await driverIndex.load();

async function matchDelivery(input) {
  const candidateIds =
    driversByArea.get(input.areaId) ??
    [];

  return selectDriver(
    candidateIds,
    input
  );
}

이 코드는 이미 준비된 지역 인덱스를 요청 사이에서 재사용한다.

그러나 공유 상태가 되면서 새로운 문제가 생긴다.

누가 인덱스를 생성하는가?
기사 위치가 바뀌면 누가 갱신하는가?
여러 서버가 같은 인덱스를 공유하는가?
서버가 재시작되면 어떻게 복구하는가?
오래된 기사 ID는 언제 제거하는가?

짧게 사용하는 메모리는 쉽게 버릴 수 있다.

오래 유지하는 데이터는 생성보다 갱신과 제거가 더 중요한 책임이 된다.

저장 위치가 바뀌면 공간의 비용과 책임도 바뀐다

지역별 기사 인덱스를 어디에 저장할지 선택해야 한다.

같은 데이터를 저장해도 위치에 따라 성질이 달라진다.

저장 위치	장점	확인할 책임
요청 내부 메모리	단순하며 요청 사이 영향이 적다	요청마다 다시 만드는 비용
서버 프로세스 메모리	매우 빠르게 읽을 수 있다	서버별 복사본, 재시작과 동기화
원격 캐시	여러 서버가 공유할 수 있다	네트워크, 만료, 장애와 오래된 값
데이터베이스	지속성과 조회 조건을 관리하기 쉽다	인덱스 공간, 읽기·쓰기 비용과 부하
위치 검색 전용 저장소	거리 검색 기능을 활용할 수 있다	운영 복잡성, 동기화와 장애 복구

서버 메모리에 인덱스를 두면 네트워크 없이 빠르게 조회할 수 있다.

const availableDriversByArea =
  new Map();

하지만 API 서버가 20대라면 같은 인덱스가 20벌 존재할 수 있다.

기사 수를 n, 서버 수를 s라고 하면 전체 복제 공간은 단순화해서 다음처럼 증가할 수 있다.

O(s × n)

서버 한 대에서 200MB인 데이터가 20대에서는 총 4GB의 메모리를 사용할 수 있다.

각 서버의 복사본이 서로 다른 시점의 상태를 가질 가능성도 있다.

원격 캐시에 한 벌을 저장하면 중복을 줄일 수 있지만 모든 조회가 네트워크를 거친다.

const candidateIds =
  await cache.getSetMembers(
    `available-drivers:${areaId}`
  );

이 코드는 여러 서버가 같은 후보 집합을 조회하게 한다.

그러나 캐시가 느리거나 사용할 수 없을 때의 경로를 정해야 한다. 캐시 데이터가 오래되었을 때 실제 배정까지 허용할지도 결정해야 한다.

공간을 어디에 둘지는 접근 속도만으로 결정할 수 없다.

데이터를 사용하는 주체, 변경 빈도, 공유 범위, 장애 시 복구 방법과 허용할 수 있는 최신성 차이를 함께 봐야 한다.

원본 데이터와 빠른 조회를 위한 계산 데이터를 구분해야 한다

크리스의 주문에 가까운 기사를 찾기 위해 여러 형태의 데이터를 사용할 수 있다.

기사 앱이 보낸 위치 이벤트
→ 서버가 검증한 최신 위치
→ 지역별 사용 가능 기사 인덱스
→ 주문별 후보 목록
→ 최종 배정 결과

이 데이터들은 같은 사실을 서로 다른 목적으로 표현한다.

데이터	역할
위치 이벤트	기사가 특정 시점에 보낸 관측값
최신 위치	서버가 받아들인 가장 최근 위치
지역별 기사 인덱스	빠른 후보 검색을 위한 파생 데이터
후보 목록	특정 주문에 대해 계산한 임시 결과
배정 기록	실제로 주문과 기사를 연결한 상태

지역별 인덱스는 원본 위치를 바탕으로 계산한 데이터다.

후보 목록은 인덱스와 주문 조건을 바탕으로 다시 계산한 데이터다.

이 값을 모두 동일하게 신뢰해서는 안 된다.

const candidateIds =
  await driverIndex.findByArea(
    order.pickupAreaId
  );

이 결과는 빠르게 탐색 범위를 줄여주는 후보 데이터다.

인덱스가 갱신되는 사이 기사가 다른 지역으로 이동했거나 다른 주문을 수락했을 수 있다.

최종 배정에서는 저장된 최신 상태를 다시 확인해야 한다.

const assignment =
  await driverRepository.assignIfAvailable({
    driverId,
    orderId,
    assignedAt: serverNow,
  });

데이터베이스에서는 현재도 배정 가능한 기사만 변경해야 한다.

UPDATE drivers
SET
  status = 'ASSIGNED',
  current_order_id = $2,
  updated_at = $3
WHERE id = $1
  AND status = 'AVAILABLE'
RETURNING id, status, current_order_id;

이 쿼리는 변경 순간에도 기사가 AVAILABLE일 때만 성공한다.

지역 인덱스는 빠른 후보 검색에 사용한다. 실제 배정 가능 여부의 Source of Truth는 데이터베이스에 저장된 최신 기사 상태다.

공간을 더 사용해 만든 파생 데이터는 시간을 줄일 수 있다.

하지만 파생 데이터가 원본의 권한까지 대신 갖는 것은 아니다.

미리 저장한 데이터에는 갱신 비용이 생긴다

기사 한 명이 area-a에서 area-b로 이동했다고 생각해보자.

지역별 인덱스는 두 곳을 변경해야 한다.

function moveDriverInIndex({
  driverId,
  previousAreaId,
  nextAreaId,
  driversByArea,
}) {
  driversByArea
    .get(previousAreaId)
    ?.delete(driverId);

  const nextAreaDrivers =
    driversByArea.get(nextAreaId) ??
    new Set();

  nextAreaDrivers.add(driverId);

  driversByArea.set(
    nextAreaId,
    nextAreaDrivers
  );
}

이 함수는 이전 지역에서 기사 ID를 제거하고 새로운 지역에 추가한다.

조회는 빨라졌지만 위치 변경마다 인덱스를 갱신해야 한다.

기사가 배달을 수락하거나 업무를 종료할 때도 목록에서 제거해야 한다.

function removeAvailableDriver({
  driverId,
  areaId,
  driversByArea,
}) {
  driversByArea
    .get(areaId)
    ?.delete(driverId);
}

이 갱신을 놓치면 실제로 배정할 수 없는 기사가 계속 후보에 나타난다.

빠른 조회 구조 하나를 추가하면 일반적으로 다음 작업도 생긴다.

초기 데이터를 구성한다.
원본 변경을 인덱스에 반영한다.
중복 항목을 방지한다.
오래된 항목을 제거한다.
서버 재시작 뒤 다시 만든다.
갱신 실패를 복구한다.
원본과 인덱스의 차이를 점검한다.

공간을 사용하는 설계는 읽기 비용을 쓰기 비용과 관리 비용으로 옮기는 선택이기도 하다.

위치 이벤트가 순서대로 도착한다고 가정할 수 없다

기사 앱은 위치를 계속 전송한다.

네트워크 상태에 따라 먼저 생성된 이벤트가 나중에 도착할 수 있다.

다음처럼 도착 순서만 믿고 최신 위치를 덮어쓰면 문제가 생긴다.

await driverLocationRepository.update({
  driverId,
  latitude,
  longitude,
  recordedAt,
});

10시 2분의 위치가 저장된 뒤 늦게 도착한 10시 1분의 위치가 이를 덮어쓸 수 있다.

최신 위치는 더 오래된 이벤트로 되돌아가면 안 된다.

UPDATE driver_locations
SET
  latitude = $2,
  longitude = $3,
  recorded_at = $4,
  received_at = $5
WHERE driver_id = $1
  AND recorded_at < $4
RETURNING
  driver_id,
  latitude,
  longitude,
  recorded_at;

이 쿼리는 현재 저장된 위치보다 새로운 이벤트일 때만 최신 위치를 변경한다.

원본 이벤트 기록을 별도로 저장한다면 늦게 도착한 위치도 이동 기록에는 남길 수 있다.

그러나 현재 위치와 지역 인덱스에는 더 새로운 값만 반영해야 한다.

여기에서 현실의 “현재 위치”는 단순한 좌표 하나가 아니다.

코드에서는 다음 상태가 함께 필요하다.

기사 ID
위도와 경도
위치가 측정된 시각
서버가 이벤트를 받은 시각
현재 지역 ID
기사의 업무 상태
위치의 유효 기간
마지막으로 반영한 이벤트의 순서

공간 복잡도는 이 데이터를 몇 개 저장하는지만 묻지 않는다.

빠른 조회를 위해 만든 여러 표현이 어떤 순서와 규칙으로 변경되어야 일관성을 유지하는지도 함께 보게 한다.

외부에서 들어온 위치는 저장하기 전에 검증해야 한다

기사 앱이 다음 위치 데이터를 전송한다고 생각해보자.

const requestBody = {
  driverId: "driver-123",
  latitude: 37.5,
  longitude: 127.0,
  recordedAt: "2026-09-19T08:00:00Z",
};

형식상 필요한 값은 모두 있다.

하지만 외부 입력을 그대로 인덱스에 저장할 수는 없다.

다른 기사의 ID를 보낼 수 있다.
위도와 경도 범위를 벗어난 값이 들어올 수 있다.
너무 오래된 위치가 도착할 수 있다.
미래 시각을 보낼 수 있다.
한 기사가 비정상적으로 많은 위치를 전송할 수 있다.
서비스 지역 밖의 좌표가 들어올 수 있다.
한 번에 이동할 수 없는 거리만큼 좌표가 바뀔 수 있다.

인증된 세션과 검증된 좌표로 내부 명령을 만들어야 한다.

const command = {
  driverId: session.driver.id,
  latitude: parseLatitude(
    request.body.latitude
  ),
  longitude: parseLongitude(
    request.body.longitude
  ),
  recordedAt: parseRecordedAt(
    request.body.recordedAt
  ),
  receivedAt: clock.now(),
};

기사 ID는 클라이언트가 주장한 값이 아니라 인증된 세션에서 가져온다.

위도, 경도와 시각은 허용 범위를 확인한다.

if (
  command.recordedAt <
    command.receivedAt - MAX_LOCATION_AGE ||
  command.recordedAt >
    command.receivedAt + MAX_CLOCK_SKEW
) {
  throw new Error(
    "위치 측정 시각을 사용할 수 없다."
  );
}

이 코드는 지나치게 오래되었거나 비정상적으로 미래인 이벤트를 거부한다.

검증되지 않은 위치를 지역별 인덱스에 저장하면 잘못된 후보를 빠르게 반환하게 된다.

파생 데이터의 조회 속도가 아무리 빨라도 입력의 신뢰성이 보장되지 않으면 서비스에는 도움이 되지 않는다.

오래된 데이터를 제거하지 않으면 공간 사용은 계속 증가한다

기사 위치를 받을 때마다 새 항목을 메모리에 추가할 수 있다.

function recordLocation(
  locationHistory,
  event
) {
  locationHistory.push(event);
}

코드는 정상적으로 위치 기록을 보존한다.

그러나 실행 중인 서버가 모든 위치 이벤트를 계속 저장하면 메모리는 줄어들지 않는다.

기사 n명이 각각 m번 위치를 전송한다면 저장 항목은 다음처럼 증가할 수 있다.

O(n × m)

위치 이벤트가 5초마다 들어오고 서버가 며칠 동안 실행된다면 빠르게 큰 데이터가 된다.

매칭에 필요한 것이 최신 위치 하나라면 기사별 최근 값만 메모리에 유지할 수 있다.

function updateLatestLocation(
  latestLocationByDriver,
  event
) {
  const current =
    latestLocationByDriver.get(
      event.driverId
    );

  if (
    !current ||
    current.recordedAt <
      event.recordedAt
  ) {
    latestLocationByDriver.set(
      event.driverId,
      event
    );
  }
}

이 구조에는 기사당 최신 위치 하나만 남는다.

기사 수를 n이라고 하면 공간은 O(n)으로 제한된다.

이동 기록 전체가 사업상 필요하다면 지속 가능한 저장소로 보내야 한다.

await locationHistoryRepository.append(
  event
);

updateLatestLocation(
  latestLocationByDriver,
  event
);

데이터베이스나 분석 저장소에는 보존 정책에 따라 위치 기록을 저장한다.

서버 메모리에는 빠른 매칭에 필요한 최신 값만 유지한다.

같은 위치 데이터라도 목적과 생명주기에 따라 저장 위치를 나누는 것이다.

최신 위치는 실시간 매칭을 위해 짧게 사용한다.
이동 기록은 분쟁 확인이나 품질 분석을 위해 일정 기간 보존한다.
지역별 인덱스는 후보 검색을 위해 원본에서 파생한다.
주문별 후보 목록은 현재 매칭 시도 동안만 사용한다.

공간을 관리하려면 저장하는 방법뿐 아니라 버리는 조건도 설계해야 한다.

만료 시간은 메모리 절약과 데이터 의미를 함께 결정한다

기사가 앱을 종료했는데 마지막 위치가 인덱스에 남을 수 있다.

상태 변경 이벤트를 놓쳤다면 해당 기사가 계속 후보로 검색될 수도 있다.

최근 위치가 일정 시간 이상 갱신되지 않은 기사는 후보에서 제외할 수 있다.

function isLocationFresh(
  location,
  now
) {
  return (
    now - location.receivedAt <=
    30_000
  );
}

이 함수는 최근 30초 이내에 받은 위치만 유효하다고 판단한다.

30초라는 값은 단순한 메모리 설정이 아니다.

너무 짧으면 네트워크가 잠시 느린 정상 기사가 후보에서 사라진다.
너무 길면 이미 이동하거나 오프라인이 된 기사가 후보로 남는다.
만료된 항목을 제거하지 않으면 메모리는 계속 차지한다.
제거한 항목이 다시 필요하면 원본 저장소를 조회해야 한다.

만료된 기사를 주기적으로 제거할 수 있다.

function removeStaleDrivers({
  latestLocationByDriver,
  driversByArea,
  now,
}) {
  for (
    const [driverId, location]
    of latestLocationByDriver
  ) {
    if (isLocationFresh(location, now)) {
      continue;
    }

    latestLocationByDriver.delete(
      driverId
    );

    driversByArea
      .get(location.areaId)
      ?.delete(driverId);
  }
}

이 코드는 최신 위치와 지역 인덱스에서 만료된 기사를 함께 제거한다.

두 구조 중 하나만 정리하면 서로 다른 결과를 만들 수 있다.

만료 정책은 공간을 회수하는 규칙이면서 “얼마나 최근의 위치를 현재 위치라고 부를 것인가?”라는 비즈니스 규칙이다.

하나의 기사를 여러 지역에 저장하면 조회는 빨라지지만 공간이 늘어난다

주문의 픽업 지점과 정확히 같은 지역에 있는 기사만 찾으면 후보가 부족할 수 있다.

주변 지역까지 함께 조회할 수 있다.

한 가지 방법은 요청할 때 인접 지역을 계산하는 것이다.

function findNearbyCandidateIds({
  areaId,
  neighborAreaIds,
  driversByArea,
}) {
  const candidates = new Set();

  for (
    const candidateAreaId
    of [areaId, ...neighborAreaIds]
  ) {
    for (
      const driverId
      of driversByArea.get(
        candidateAreaId
      ) ?? []
    ) {
      candidates.add(driverId);
    }
  }

  return [...candidates];
}

이 코드는 조회할 때 주변 지역의 기사 목록을 합친다.

다른 방법은 기사 한 명을 미리 여러 검색 구역에 등록하는 것이다.

function indexDriverForSearchAreas({
  driver,
  searchableAreaIds,
  driversByArea,
}) {
  for (
    const areaId of searchableAreaIds
  ) {
    const driverIds =
      driversByArea.get(areaId) ??
      new Set();

    driverIds.add(driver.id);
    driversByArea.set(
      areaId,
      driverIds
    );
  }
}

이 방식은 조회 시 계산을 줄일 수 있지만 같은 기사 ID를 여러 곳에 저장한다.

기사 수를 n, 기사 한 명이 등록되는 평균 지역 수를 c라고 하면 공간은 다음과 같이 증가할 수 있다.

O(n × c)

c가 최대 4로 고정되어 있다면 증가 방식은 O(n)으로 표현할 수 있다.

그래도 실제 저장 항목은 기사당 한 개가 아니라 최대 네 개다.

검색 반경을 넓혀 c가 커지면 메모리와 갱신 비용도 함께 증가한다.

한 기사가 이동할 때 여러 지역에서 제거하고 새 지역들에 다시 추가해야 하기 때문이다.

따라서 다음을 비교해야 한다.

조회할 때 주변 지역을 합칠 것인가?
미리 여러 지역에 복제할 것인가?
매칭 요청과 위치 갱신 중 어느 쪽이 더 자주 발생하는가?
허용할 검색 반경은 얼마인가?
중복 후보를 제거할 공간은 얼마나 필요한가?
지역 경계를 변경하면 인덱스를 어떻게 다시 만드는가?

조회 속도를 높이는 복제는 저장 공간뿐 아니라 갱신 작업도 복제한다.

데이터베이스 인덱스도 공간을 사용해 탐색 시간을 줄인다

주변 기사를 데이터베이스에서 조회할 수도 있다.

SELECT
  id,
  current_area_id,
  last_location_at
FROM drivers
WHERE current_area_id = $1
  AND status = 'AVAILABLE'
  AND last_location_at > $2
LIMIT 100;

적절한 인덱스가 없다면 데이터베이스가 많은 기사 행을 확인해야 할 수 있다.

조회 조건에 맞는 인덱스를 추가할 수 있다.

CREATE INDEX
  drivers_area_status_location_idx
ON drivers (
  current_area_id,
  status,
  last_location_at
);

인덱스는 조회 범위를 빠르게 줄이는 데 사용된다.

대신 다음 비용이 생긴다.

인덱스를 저장할 디스크 공간이 필요하다.
기사 위치나 상태가 바뀔 때 인덱스도 갱신된다.
인덱스가 많을수록 쓰기 비용이 증가할 수 있다.
사용되지 않는 인덱스도 저장 공간과 관리 비용을 차지한다.
인덱스 생성과 재구성에 시간과 추가 공간이 필요하다.

형식적인 알고리즘 분석에서 공간 복잡도는 보통 실행 중 사용하는 메모리를 뜻한다.

서비스에서는 같은 사고를 데이터베이스 인덱스, 캐시와 미리 계산한 테이블에도 적용할 수 있다.

이 데이터들은 모두 추가 공간을 사용해 반복되는 조회 시간을 줄인다.

따라서 “애플리케이션 메모리를 거의 사용하지 않는다”는 말만으로 공간 비용이 작다고 결론 내릴 수 없다.

비용이 데이터베이스나 캐시로 이동했을 수 있다.

모든 데이터를 메모리에 올리지 않고 흐르게 할 수도 있다

배달 기사의 이동 기록을 분석해 지역별 활동량을 계산한다고 생각해보자.

모든 기록을 한 번에 메모리에 읽을 수 있다.

const events =
  await locationHistoryRepository.findAll();

const countsByArea = new Map();

for (const event of events) {
  const count =
    countsByArea.get(event.areaId) ?? 0;

  countsByArea.set(
    event.areaId,
    count + 1
  );
}

결과는 올바를 수 있다.

그러나 이동 기록이 수억 건이라면 전체 배열을 서버 메모리에 올리는 과정에서 한계에 도달할 수 있다.

일정한 크기의 묶음으로 처리할 수 있다.

let cursor = null;
const countsByArea = new Map();

do {
  const page =
    await locationHistoryRepository
      .findPage({
        cursor,
        limit: 1000,
      });

  for (const event of page.items) {
    const count =
      countsByArea.get(
        event.areaId
      ) ?? 0;

    countsByArea.set(
      event.areaId,
      count + 1
    );
  }

  cursor = page.nextCursor;
} while (cursor !== null);

이 코드는 이동 기록 전체가 아니라 최대 1,000개씩 메모리에 올린다.

전체 처리 시간은 여전히 기록 수에 비례한다.

하지만 입력 전체를 동시에 보관하지 않으므로 요청 중 사용하는 메모리의 상한을 낮출 수 있다.

다만 countsByArea의 크기는 지역 수에 따라 증가한다.

지역 수마저 매우 크다면 중간 집계를 데이터베이스에 저장하거나 저장소의 집계 기능을 사용할 수 있다.

SELECT
  area_id,
  COUNT(*) AS event_count
FROM driver_location_events
WHERE recorded_at >= $1
  AND recorded_at < $2
GROUP BY area_id;

어디에서 집계하든 작업은 존재한다.

중요한 것은 데이터 전체를 어느 한 프로세스의 메모리에 동시에 올릴 필요가 있는지 확인하는 것이다.

메모리 사용량은 데이터 개수만으로 정확히 알 수 없다

기사 ID 100만 개를 저장한다고 생각해보자.

문자열 하나가 20바이트처럼 보인다고 해서 전체 메모리가 정확히 20MB가 되는 것은 아니다.

실제 사용량에는 다음 요소가 포함될 수 있다.

문자열과 객체 자체의 관리 정보
Map과 Set이 유지하는 내부 저장 공간
아직 사용하지 않는 여유 공간
같은 값의 여러 복사본
런타임이 객체를 관리하는 비용
임시 배열과 직렬화 결과
메모리 회수가 실행되기 전까지 남아 있는 객체

다음 코드는 같은 기사 정보를 여러 형태로 복제한다.

const driverById = new Map();
const driversByArea = new Map();
const availableDrivers = [];

for (const driver of drivers) {
  driverById.set(driver.id, {
    ...driver,
  });

  availableDrivers.push({
    ...driver,
  });

  const areaDrivers =
    driversByArea.get(driver.areaId) ??
    [];

  areaDrivers.push({
    ...driver,
  });

  driversByArea.set(
    driver.areaId,
    areaDrivers
  );
}

기사 객체 전체가 여러 구조에 복사된다.

각 구조에서 기사 ID만 보관하고 상세 정보는 한곳에서 참조할 수 있다.

const driverById = new Map();
const driverIdsByArea = new Map();

for (const driver of drivers) {
  driverById.set(
    driver.id,
    driver
  );

  if (driver.status !== "AVAILABLE") {
    continue;
  }

  const driverIds =
    driverIdsByArea.get(
      driver.areaId
    ) ?? new Set();

  driverIds.add(driver.id);

  driverIdsByArea.set(
    driver.areaId,
    driverIds
  );
}

상세 기사 객체는 driverById에 한 번 저장한다.

지역 인덱스에는 ID만 저장한다.

복잡도는 둘 다 O(n)일 수 있지만 실제 사용량과 갱신 난이도는 다르다.

기사의 전화번호나 차량 정보가 변경되어도 여러 객체 복사본을 모두 수정할 필요가 줄어든다.

공간 복잡도 표기와 실제 메모리 측정은 함께 사용해야 한다.

공간이 부족할 때 무엇을 버릴지 미리 정해야 한다

서버 메모리나 캐시 공간은 유한하다.

지역별 인덱스에 계속 데이터를 추가하다가 한계에 도달한 뒤 임의로 삭제해서는 안 된다.

어떤 데이터를 유지할지 기준이 필요하다.

배달 매칭에서는 다음과 같은 정책을 생각할 수 있다.

최근 위치가 일정 시간 이내인 기사만 유지한다.
AVAILABLE 상태인 기사만 후보 인덱스에 둔다.
서비스 지역 밖으로 이동한 기사는 제거한다.
상세 정보 대신 기사 ID와 최소 위치 정보만 저장한다.
접근이 드문 오래된 지역 인덱스는 필요할 때 다시 만든다.
한 지역의 후보 수에 상한을 두고 가까운 기사만 유지한다.
원본 위치 기록은 메모리가 아니라 지속 가능한 저장소에 둔다.

예를 들어 지역별 후보를 최대 500명으로 제한할 수 있다.

function addCandidate({
  areaCandidates,
  driver,
  maxCandidates,
}) {
  areaCandidates.push(driver);
  areaCandidates.sort(
    (first, second) =>
      second.locationUpdatedAt -
      first.locationUpdatedAt
  );

  if (
    areaCandidates.length >
    maxCandidates
  ) {
    areaCandidates.pop();
  }
}

이 코드는 최근 위치를 보낸 기사부터 유지한다.

하지만 “최근 위치”가 실제 매칭 우선순위와 일치하는지는 별도로 확인해야 한다.

거리, 차량 종류와 현재 작업량도 중요하다면 단순히 오래된 기사를 버리는 정책이 적절하지 않을 수 있다.

제거 정책은 기술적인 메모리 관리 규칙이면서 어떤 후보를 포기할 것인지 결정하는 비즈니스 규칙이다.

메모리를 줄인 선택이 네트워크와 데이터베이스 비용을 늘릴 수 있다

서버 메모리를 절약하기 위해 지역 인덱스를 두지 않고 매번 데이터베이스에서 조회할 수 있다.

const candidates =
  await driverRepository
    .findAvailableByArea({
      areaId,
      activeAfter,
      limit: 100,
    });

애플리케이션의 장기 메모리 사용은 줄어든다.

대신 매칭 요청마다 데이터베이스 조회가 발생한다.

반대로 모든 후보를 서버 메모리에 저장하면 데이터베이스 조회를 줄일 수 있지만 다음 비용이 생긴다.

서버별 메모리 사용량
초기 데이터 적재 시간
위치 변경을 전달하는 통신
서버 간 상태 차이
재시작 후 복구 시간
메모리 부족 위험

원격 캐시에 저장하면 애플리케이션 메모리와 데이터베이스 조회를 줄일 수 있다.

그러나 캐시 비용과 네트워크 왕복이 추가된다.

공간을 줄였다는 말은 어느 위치의 공간을 줄였다는 뜻인지 밝혀야 한다.

애플리케이션 메모리 감소
≠ 전체 시스템의 저장 비용 감소

메모리에서 제거한 데이터가 데이터베이스 조회, 네트워크 응답이나 반복 계산으로 바뀔 수 있다.

서비스에서는 CPU, 메모리, 디스크, 네트워크와 운영 비용을 함께 봐야 한다.

빠른 후보 조회와 정확한 배정은 서로 다른 책임이다

지역 인덱스에서 기사 후보를 찾는 단계는 많은 기사 중 확인할 대상을 줄인다.

const candidateIds =
  await driverIndex.findNearby({
    areaId: order.pickupAreaId,
    limit: 50,
  });

이 결과는 최대 50명의 후보를 반환한다.

이후 주문 조건에 맞는 기사를 평가할 수 있다.

const rankedCandidates =
  await rankCandidates({
    candidateIds,
    pickupLocation:
      order.pickupLocation,
    requiredVehicleType:
      order.requiredVehicleType,
  });

여기에서 계산한 순위도 확정 상태는 아니다.

첫 번째 기사부터 실제 배정을 시도해야 한다.

for (
  const candidate of rankedCandidates
) {
  const assignment =
    await driverRepository
      .assignIfAvailable({
        driverId: candidate.driverId,
        orderId: order.id,
        assignedAt: serverNow,
      });

  if (assignment) {
    return assignment;
  }
}

return null;

순위가 가장 높은 기사가 이미 다른 주문을 수락했다면 다음 후보를 시도한다.

이 흐름에서 각 데이터의 책임은 다르다.

책임	적절한 위치
위치 요청 형식 검증	API 경계
기사 신원 확인	인증 계층
최신 위치 저장	데이터베이스
주변 기사 범위 축소	위치 인덱스 또는 캐시
거리와 조건 계산	매칭 서비스
최종 배정 가능 여부 확인	데이터베이스 조건부 변경
배정 중복 방지	데이터베이스 제약과 트랜잭션
오래된 후보 제거	인덱스 생명주기 관리
원본과 인덱스 차이 탐지	점검 작업과 운영 지표

공간을 추가해 만든 인덱스는 후보 검색 책임을 가진다.

최종 상태를 확정하는 책임까지 가져서는 안 된다.

실제 측정 없이 공간 절약이나 낭비를 판단할 수 없다

코드만 보고 메모리를 많이 쓸 것이라고 예상할 수는 있다.

그러나 실제로 어느 구조가 얼마나 사용하는지는 측정해야 한다.

다음과 같은 지표를 기록할 수 있다.

logger.info(
  "Driver index metrics",
  {
    activeDriverCount:
      latestLocationByDriver.size,
    indexedAreaCount:
      driverIdsByArea.size,
    indexedEntryCount:
      countIndexedEntries(
        driverIdsByArea
      ),
    staleDriverCount,
    processMemoryBytes:
      process.memoryUsage().heapUsed,
    rebuildMs,
  }
);

이 로그는 활성 기사 수, 지역 수, 실제 인덱스 항목 수와 프로세스 메모리를 함께 기록한다.

운영에서는 다음 항목을 관찰할 수 있다.

활성 기사 수
지역별 후보 수의 분포
기사 한 명당 인덱스 항목 수
서버별 메모리 사용량
메모리 회수에 걸리는 시간
캐시 사용량과 적중률
만료된 기사 수
원본에는 없지만 인덱스에 남은 기사 수
원본에는 있지만 인덱스에서 누락된 기사 수
인덱스 갱신 지연
인덱스 재구성 시간
데이터베이스 인덱스 크기
위치 갱신 쿼리 시간
후보 조회 시간
후보 조회 후 실제 배정 실패 비율

후보 조회는 빠른데 실제 배정 실패 비율이 높다면 인덱스가 오래되었을 수 있다.

메모리 사용량이 계속 증가한다면 만료된 기사가 제거되지 않거나 같은 기사가 여러 지역에 중복 등록되고 있을 수 있다.

인덱스 공간만 줄였는데 조회 시간이 급증했다면 필요한 데이터를 지나치게 제거했을 수 있다.

공간 복잡도 분석은 증가 위험을 예상한다.

실제 측정은 어떤 구조가 현재 비용을 만들고 있는지 확인한다.

공간을 설계할 때 물어봐야 할 질문

알고리즘이나 서비스에서 데이터를 미리 저장하려 할 때 다음 질문을 확인할 수 있다.

입력 크기를 나타내는 n은 현실의 어떤 데이터인가?
기사 수, 위치 이벤트 수, 지역 수와 서버 수를 구분했는가?
입력, 보조 공간과 출력 공간을 나누어 계산했는가?
결과 자체를 표현하는 데 반드시 필요한 공간은 얼마인가?
같은 객체 전체를 여러 자료구조에 복사하고 있지는 않은가?
상세 객체 대신 ID나 필요한 필드만 저장할 수 있는가?
추가 공간을 사용하면 어떤 반복 탐색이나 계산이 줄어드는가?
미리 만든 구조를 몇 번 재사용하는가?
한 번의 조회를 위해 매번 인덱스를 새로 만들고 있지는 않은가?
데이터가 변경되는 빈도와 조회되는 빈도는 각각 얼마인가?
읽기에서 줄인 비용보다 갱신 비용이 더 크지는 않은가?
데이터를 요청 메모리, 서버 메모리, 캐시와 데이터베이스 중 어디에 둘 것인가?
여러 서버가 같은 데이터를 몇 벌 보관하는가?
서버가 재시작되면 데이터를 어디에서 다시 만드는가?
공유된 데이터가 서버마다 달라져도 되는가?
파생 데이터의 원본은 무엇인가?
최종 상태의 Source of Truth는 어디에 있는가?
캐시나 인덱스 결과를 최종 상태처럼 신뢰하고 있지는 않은가?
원본이 바뀌면 파생 데이터를 누가 갱신하는가?
갱신 이벤트가 누락되거나 중복되면 어떻게 복구하는가?
순서가 뒤바뀐 위치 이벤트가 최신 상태를 덮어쓸 수 있는가?
외부 입력의 신원, 범위와 시각을 검증한 뒤 저장하는가?
데이터마다 명확한 만료 시간이나 제거 조건이 있는가?
오래된 항목을 제거할 때 연결된 모든 인덱스도 함께 정리하는가?
저장 공간이 가득 차면 어떤 데이터를 먼저 버릴 것인가?
제거 정책이 비즈니스 우선순위와 일치하는가?
전체 기록이 필요한가, 최신 값 하나만 필요한가?
큰 데이터를 한 번에 읽지 않고 묶음이나 스트림으로 처리할 수 있는가?
데이터베이스 인덱스가 사용하는 공간과 쓰기 비용을 확인했는가?
애플리케이션 메모리를 줄인 대신 네트워크나 데이터베이스 비용이 증가하지 않았는가?
객체 수뿐 아니라 객체 하나의 실제 크기와 런타임 오버헤드를 측정했는가?
평균 메모리뿐 아니라 최대 요청과 동시 요청에서의 사용량을 확인했는가?
인덱스 크기, 갱신 지연과 오래된 항목 수를 운영에서 관찰하는가?
추가한 공간이 실제 응답 시간이나 처리량을 개선했다는 측정 결과가 있는가?
현재 설계가 감당할 최대 공간과 그 한계를 넘었을 때의 동작을 설명할 수 있는가?

이 질문은 모든 데이터를 캐시하거나 모든 중간 배열을 제거하기 위한 목록이 아니다.

데이터가 작고 조회가 드물다면 매번 직접 탐색하는 방법이 가장 단순할 수 있다.

반복 조회가 많고 데이터가 크다면 인덱스나 캐시를 유지할 가치가 생긴다.

중요한 것은 추가 공간이 어떤 시간을 줄이며 그 데이터를 정확하게 유지하는 비용까지 감당할 수 있는지 설명하는 것이다.

공간은 남는 자원이 아니라 시간을 저장하는 장소다

공간 복잡도는 알고리즘이 실행되는 동안 사용하는 메모리의 증가를 분석하는 기본 도구다.

하지만 실제 서비스에서는 그 질문이 더 넓어진다.

모든 기사를 반복해서 탐색하지 않기 위해 지역별 인덱스를 저장할 수 있다.
같은 계산을 반복하지 않기 위해 결과를 캐시할 수 있다.
빠른 조회를 위해 데이터베이스 인덱스를 추가할 수 있다.
전체 이동 기록 대신 최신 위치만 메모리에 유지할 수 있다.
큰 데이터는 한 번에 올리지 않고 작은 묶음으로 처리할 수 있다.
여러 서버에 같은 데이터를 복제하면 전체 공간이 서버 수만큼 늘어날 수 있다.
빠른 조회용 데이터에는 갱신, 만료와 복구 책임이 생긴다.
파생된 후보 데이터는 최종 상태의 Source of Truth가 될 수 없다.
추가 공간을 줄이면 반복 계산, 네트워크나 저장소 조회가 늘어날 수 있다.

공간을 적게 쓰는 구현이 언제나 좋은 것은 아니다.

매칭 요청마다 기사 100만 명을 탐색하는 대신 적절한 지역 인덱스를 유지하는 편이 더 나을 수 있다.

반대로 한 번만 사용할 작은 목록을 위해 복잡한 인덱스를 만드는 것은 불필요할 수 있다.

따라서 공간에 관한 판단은 다음 순서로 이어져야 한다.

어떤 데이터가 입력 크기에 따라 증가하는지 확인한다.
출력에 필요한 공간과 선택적으로 사용하는 공간을 구분한다.
추가 공간으로 줄일 수 있는 시간을 밝힌다.
데이터를 몇 번 재사용하는지 확인한다.
책임과 생명주기에 맞는 저장 위치를 정한다.
원본 데이터와 파생 데이터를 구분한다.
갱신, 만료, 제거와 복구 방법을 설계한다.
동시 변경에서도 최종 상태를 다시 검증한다.
전체 시스템의 메모리, 디스크와 네트워크 비용을 측정한다.
서비스가 책임질 공간의 상한을 정한다.

실제 서비스에서 공간 복잡도는 단순히 메모리를 얼마나 사용하는지 계산하는 개념이 아니다. 반복 탐색과 계산을 줄이기 위해 어떤 정보를 미리 저장하고, 그 정보의 위치와 복제 수와 생명주기와 정확성을 어떻게 책임질지 결정하는 기준이다.

배달 기사 인덱스는 공간을 사용해 시간을 저장한다.

하지만 저장한 시간이 실제 가치가 되려면 인덱스를 여러 번 재사용할 수 있어야 한다. 기사 이동과 상태 변경을 정확히 반영해야 한다. 오래된 항목을 제거해야 한다. 최종 배정에서는 원본 상태를 다시 확인해야 한다.

추가 공간은 무료 자원이 아니다.

빠른 조회를 얻는 대신 생성, 갱신, 동기화, 만료와 복구의 책임을 맡는 선택이다.

vx_developer

Vision eXperience Developer

이전 포스트

평균 성능만 빠르다고 좋은 알고리즘은 아니다

다음 포스트

공간 복잡도는 메모리 사용량만 계산하는 개념이 아니다

코테보다가

같은 `O(n)` 공간이라도 무엇을 저장하는지 구분해야 한다

시간을 줄이기 위해 공간을 사용할 수 있다

한 번만 조회한다면 미리 만든 구조가 더 비쌀 수 있다

데이터의 생명주기가 다르면 같은 공간으로 계산해서는 안 된다

저장 위치가 바뀌면 공간의 비용과 책임도 바뀐다

원본 데이터와 빠른 조회를 위한 계산 데이터를 구분해야 한다

미리 저장한 데이터에는 갱신 비용이 생긴다

위치 이벤트가 순서대로 도착한다고 가정할 수 없다

외부에서 들어온 위치는 저장하기 전에 검증해야 한다

오래된 데이터를 제거하지 않으면 공간 사용은 계속 증가한다

만료 시간은 메모리 절약과 데이터 의미를 함께 결정한다

하나의 기사를 여러 지역에 저장하면 조회는 빨라지지만 공간이 늘어난다

데이터베이스 인덱스도 공간을 사용해 탐색 시간을 줄인다

모든 데이터를 메모리에 올리지 않고 흐르게 할 수도 있다

메모리 사용량은 데이터 개수만으로 정확히 알 수 없다

공간이 부족할 때 무엇을 버릴지 미리 정해야 한다

메모리를 줄인 선택이 네트워크와 데이터베이스 비용을 늘릴 수 있다

빠른 후보 조회와 정확한 배정은 서로 다른 책임이다

실제 측정 없이 공간 절약이나 낭비를 판단할 수 없다

공간을 설계할 때 물어봐야 할 질문

공간은 남는 자원이 아니라 시간을 저장하는 장소다

평균 성능만 빠르다고 좋은 알고리즘은 아니다

시간과 공간은 따로 최적화할 수 있는 대상이 아니다

0개의 댓글

공간 복잡도는 메모리 사용량만 계산하는 개념이 아니다

코테보다가

같은 O(n) 공간이라도 무엇을 저장하는지 구분해야 한다

시간을 줄이기 위해 공간을 사용할 수 있다

한 번만 조회한다면 미리 만든 구조가 더 비쌀 수 있다

데이터의 생명주기가 다르면 같은 공간으로 계산해서는 안 된다

저장 위치가 바뀌면 공간의 비용과 책임도 바뀐다

원본 데이터와 빠른 조회를 위한 계산 데이터를 구분해야 한다

미리 저장한 데이터에는 갱신 비용이 생긴다

위치 이벤트가 순서대로 도착한다고 가정할 수 없다

외부에서 들어온 위치는 저장하기 전에 검증해야 한다

오래된 데이터를 제거하지 않으면 공간 사용은 계속 증가한다

만료 시간은 메모리 절약과 데이터 의미를 함께 결정한다

하나의 기사를 여러 지역에 저장하면 조회는 빨라지지만 공간이 늘어난다

데이터베이스 인덱스도 공간을 사용해 탐색 시간을 줄인다

모든 데이터를 메모리에 올리지 않고 흐르게 할 수도 있다

메모리 사용량은 데이터 개수만으로 정확히 알 수 없다

공간이 부족할 때 무엇을 버릴지 미리 정해야 한다

메모리를 줄인 선택이 네트워크와 데이터베이스 비용을 늘릴 수 있다

빠른 후보 조회와 정확한 배정은 서로 다른 책임이다

실제 측정 없이 공간 절약이나 낭비를 판단할 수 없다

공간을 설계할 때 물어봐야 할 질문

공간은 남는 자원이 아니라 시간을 저장하는 장소다

평균 성능만 빠르다고 좋은 알고리즘은 아니다

시간과 공간은 따로 최적화할 수 있는 대상이 아니다

0개의 댓글

같은 `O(n)` 공간이라도 무엇을 저장하는지 구분해야 한다