알고리즘을 처음 배울 때 O(1)은 입력 크기와 관계없이 일정한 횟수로 끝나는 작업이라고 배운다.
주문 ID를 키로 사용하는 Map에서 주문을 찾는 코드를 생각해보자.
const order = orderById.get(orderId);주문이 10개이든 100만 개이든 조회 과정이 주문 수에 비례해 길어지지 않는다.
따라서 평균적인 조회 비용을 O(1)이라고 표현할 수 있다.
입력 크기에 따라 비용이 변하는 작업과 그렇지 않은 작업을 구분하기에는 유용한 설명이다.
하지만 실제 주문 서비스에서 O(1)이라는 사실만으로 빠른 응답을 보장할 수는 없다.
Map은 언제 만들어졌는가?- 주문 100만 개를 메모리에 올리는 비용은 어디에 포함되는가?
- 주문 데이터는 같은 서버에 있는가, 네트워크 너머에 있는가?
- 데이터베이스 조회 한 번은 정말
O(1)인가? - 캐시에 값이 없으면 어디에서 다시 가져오는가?
- 캐시된 주문 상태는 최신 상태인가?
- 주문 ID를 아는 사용자가 다른 사용자의 주문을 조회할 수 있는가?
- 주문 상태가 변경되는 동안 오래된 값을 반환하지 않는가?
- 결제사나 배송사의 응답이 느리면 어떻게 되는가?
- 한 번의 조회가 큰 데이터를 반환한다면 전송 비용은 얼마인가?
한 단계로 보이는 작업 안에도 데이터 준비, 이동, 검증과 대기가 숨어 있을 수 있다.
실제 서비스에서
O(1)은 작업이 즉시 끝난다는 뜻이 아니라, 입력 데이터가 증가해도 해당 작업의 단계 수가 그 크기에 비례해 늘어나지 않는다는 뜻이다.
O(1)은 빠르다는 평가가 아니라 증가 방식에 대한 설명이다
두 작업이 모두 O(1)이라고 생각해보자.
const order = orderById.get(orderId);첫 번째 작업은 같은 프로세스의 메모리에서 값을 조회한다.
다음 작업은 결제 서비스에 주문 상태를 요청한다.
const payment =
await paymentClient.getPayment(orderId);외부 API를 한 번 호출하므로 호출 횟수만 보면 주문 수에 따라 증가하지 않는다.
하지만 실제로는 다음 과정이 필요할 수 있다.
- 연결 가능한 서버 주소를 찾는다.
- 네트워크 연결을 만든다.
- 요청을 암호화해 전송한다.
- 외부 서비스가 인증 정보를 확인한다.
- 외부 데이터베이스에서 결제를 조회한다.
- 응답을 네트워크로 다시 전송한다.
- 응답 본문을 해석한다.
두 작업은 입력 크기에 대해 상수 횟수로 표현할 수 있어도 실제 시간은 크게 다르다.
| 작업 | 복잡도 표현 | 실제 시간의 주요 원인 |
|---|---|---|
| 메모리의 객체 속성 읽기 | O(1) | CPU와 메모리 접근 |
같은 프로세스의 Map 조회 | 평균 O(1) | 해시 계산과 메모리 접근 |
| 원격 캐시 조회 | 보통 한 번의 명령 | 네트워크와 캐시 서버 부하 |
| 데이터베이스 단건 조회 | 인덱스 구조에 따라 다름 | 인덱스 탐색, 디스크와 연결 대기 |
| 외부 결제 API 호출 | 한 번의 호출 | 인터넷 지연과 외부 서비스 처리 |
| 큰 파일 다운로드 | 한 번의 요청 | 파일 크기와 전송 속도 |
복잡도에서 상수라고 부르는 비용도 실제로는 1나노초일 수도 있고 3초일 수도 있다.
O(1)은 데이터가 증가할 때 비용이 어떻게 변하는지를 설명한다. 그 비용 자체가 작은지는 측정해야 한다.
빠른 조회 앞에는 데이터를 준비하는 비용이 있다
주문을 빠르게 찾기 위해 배열을 Map으로 바꿀 수 있다.
const orderById = new Map(
orders.map((order) => [
order.id,
order,
])
);
const order = orderById.get(orderId);Map을 만든 뒤 조회는 평균적으로 O(1)이다.
하지만 Map을 만드는 과정에서는 모든 주문을 한 번 확인한다.
Map 생성: O(n)
주문 한 건 조회: 평균 O(1)주문 10개를 한 번 조회하기 위해 Map을 새로 만든다면 배열을 직접 찾는 것보다 더 많은 작업을 할 수 있다.
const order = orders.find(
(order) => order.id === orderId
);이 조회는 최악의 경우 O(n)이다.
하지만 목록이 작고 조회가 한 번뿐이라면 코드가 단순하고 충분히 빠를 수 있다.
반대로 같은 주문 목록에서 ID 조회를 수천 번 반복한다면 처음에 O(n)의 준비 비용을 부담하고 이후 조회를 줄이는 편이 적절할 수 있다.
| 사용 방식 | 고려할 수 있는 선택 |
|---|---|
| 작은 목록에서 한 번 조회 | 배열 선형 탐색 |
| 같은 목록에서 반복 조회 | Map을 한 번 만들어 재사용 |
| 주문이 자주 추가되거나 삭제됨 | Map의 갱신 비용 확인 |
| 전체 주문이 매우 많음 | 서버 메모리보다 데이터베이스 조회 |
| 여러 서버가 주문을 처리함 | 각 서버의 복사본이 오래되지 않는지 확인 |
O(1) 조회를 얻기 위해 어떤 사전 작업과 저장 공간을 부담하는지 함께 봐야 한다.
코드 한 줄 밖에 있는 데이터 흐름을 확인해야 한다
크리스가 쇼핑몰에서 자신의 주문 상태를 확인한다고 생각해보자.
서비스 내부에서는 다음 한 줄로 보일 수 있다.
const order =
await orderRepository.findById(orderId);하지만 실제 요청은 여러 단계를 통과한다.
flowchart LR
A["크리스의 브라우저"]
--> B["인터넷과 API 서버"]
--> C["인증·권한 확인"]
--> D{"캐시에 주문이 있는가?"}
D -- "있음" --> E["캐시된 주문 반환"]
D -- "없음" --> F["데이터베이스 조회"]
F --> G["응답 데이터 변환"]
G --> H["캐시 저장"]
E --> I["브라우저로 응답"]
H --> I애플리케이션 코드에서는 저장소 메서드를 한 번 호출한다.
그러나 사용자가 결과를 받기까지는 다음 비용이 더해진다.
전체 응답 시간
=
클라이언트와 서버 사이의 네트워크 시간
+ 인증과 권한 확인 시간
+ 캐시 조회 시간
+ 필요하면 데이터베이스 조회 시간
+ 응답 변환과 직렬화 시간
+ 응답 전송 시간복잡도는 각 단계가 데이터 증가에 따라 어떻게 변하는지 분석하는 데 도움이 된다.
사용자가 느끼는 속도는 이 단계들의 실제 시간이 합쳐진 결과다.
코드 한 줄의 복잡도만 보고 API 전체의 성능을 판단해서는 안 된다.
데이터베이스 조회 한 번을 무조건 O(1)이라고 부를 수 없다
다음 쿼리는 주문 ID로 한 건을 조회한다.
SELECT
id,
user_id,
status,
total_amount,
created_at
FROM orders
WHERE id = $1;애플리케이션에서는 데이터베이스 요청을 한 번 실행한다.
하지만 “쿼리를 한 번 호출한다”는 사실과 데이터베이스 내부에서 한 단계로 찾는다는 사실은 다르다.
기본 키 인덱스가 없다면 데이터베이스가 많은 주문을 확인해야 할 수 있다.
적절한 인덱스가 있다면 검색 범위를 크게 줄일 수 있다.
CREATE UNIQUE INDEX orders_id_idx
ON orders (id);많은 관계형 데이터베이스의 일반적인 트리 인덱스는 데이터가 증가할 때 탐색 단계가 천천히 늘어나는 구조를 사용한다. 개념적으로 O(log n)에 가까운 증가를 생각할 수 있다.
실제 조회 시간에는 다음 요소도 영향을 준다.
- 필요한 인덱스 페이지가 메모리에 있는가?
- 디스크를 읽어야 하는가?
- 데이터베이스 연결을 기다려야 하는가?
- 다른 작업이 같은 행이나 자원을 사용하고 있는가?
- 조회 결과가 한 행인가, 연결된 데이터를 많이 포함하는가?
- 데이터베이스가 다른 지역에 있는가?
- 인덱스가 쿼리 조건에 맞는가?
따라서 다음 표현은 조심해야 한다.
ID로 조회하니까
O(1)이고 무조건 빠르다.
더 정확하게는 다음처럼 설명할 수 있다.
애플리케이션은 ID 조회를 한 번 요청한다. 실제 데이터베이스 비용은 인덱스 구조, 저장 위치와 현재 부하에 따라 달라지므로 실행 계획과 측정 결과를 확인해야 한다.
추상화된 메서드 호출 횟수와 저장소 내부의 알고리즘을 구분해야 한다.
캐시 조회가 O(1)이어도 캐시 미스는 다른 경로를 만든다
주문 상태를 캐시에 저장할 수 있다.
const cachedOrder =
await cache.get(`order:${orderId}`);
if (cachedOrder) {
return cachedOrder;
}키로 값을 조회하는 작업은 일반적으로 데이터 개수에 따라 선형으로 늘어나지 않는다.
하지만 캐시에 값이 항상 존재하는 것은 아니다.
const cacheKey = `order:${orderId}`;
const cachedOrder =
await cache.get(cacheKey);
if (cachedOrder) {
return cachedOrder;
}
const order =
await orderRepository.findById(orderId);
await cache.set(
cacheKey,
order,
{ ttlSeconds: 30 }
);
return order;캐시가 적중하면 캐시 조회만으로 끝난다.
캐시가 비어 있으면 데이터베이스를 조회하고 결과를 다시 저장한다.
따라서 성능은 다음 값에 영향을 받는다.
- 캐시 적중률
- 캐시 서버까지의 네트워크 시간
- 값의 직렬화와 역직렬화 비용
- 캐시에 저장된 주문 객체의 크기
- 만료 시간이 너무 짧거나 긴지
- 같은 키가 만료된 순간 요청이 몰리는지
- 데이터베이스 조회가 실패했을 때의 처리
- 캐시 서버가 느리거나 사용할 수 없을 때의 처리
캐시 조회 한 번이 O(1)이라는 설명은 캐시 적중 경로만 설명할 수 있다.
실제 서비스는 적중, 미적중, 만료와 장애 경로를 모두 처리해야 한다.
빠른 캐시가 오래된 주문 상태를 반환할 수 있다
크리스가 주문을 취소했다고 생각해보자.
데이터베이스에는 CANCELLED 상태가 저장되었다.
하지만 캐시에는 이전 상태인 PAID가 남아 있을 수 있다.
const cachedOrder =
await cache.get(`order:${orderId}`);
return cachedOrder;조회는 빠르지만 잘못된 상태를 보여줄 수 있다.
주문 변경 뒤 캐시를 제거할 수 있다.
const order =
await orderRepository.cancelIfAllowed({
orderId,
userId,
cancelledAt: serverNow,
});
await cache.delete(`order:${orderId}`);
return order;데이터베이스에서 주문 취소에 성공한 뒤 관련 캐시를 제거한다.
그래도 데이터베이스 변경과 캐시 제거 사이에는 짧은 시간 차이가 생길 수 있다. 캐시 삭제가 실패할 수도 있다.
따라서 캐시를 적용하기 전에 다음 질문에 답해야 한다.
- 주문 상태가 얼마나 오래되어도 되는가?
- 결제 완료, 배송과 취소 중 어떤 상태가 특히 민감한가?
- 변경 시 캐시를 삭제할 것인가, 새 값으로 갱신할 것인가?
- 캐시 삭제에 실패하면 어떻게 복구할 것인가?
- 화면 표시와 상태 변경이 같은 최신성을 요구하는가?
주문 목록 화면은 몇 초 정도 오래된 상태를 보여줄 수 있을지도 모른다.
그러나 주문 취소 가능 여부나 환불 금액을 결정할 때는 캐시된 상태만 믿어서는 안 된다.
const result =
await orderRepository.cancelIfAllowed({
orderId,
userId: session.user.id,
cancelledAt: serverNow,
});최종 상태 변경은 데이터베이스의 최신 값을 기준으로 판단해야 한다.
캐시는 빠른 조회를 위한 계산되거나 복제된 데이터다. 주문의 최종 상태에 대한 Source of Truth는 데이터베이스다.
O(1) 조회를 얻는 것보다 어떤 결과를 어디까지 신뢰할 수 있는지 정하는 일이 먼저다.
메모리 조회는 빠르지만 여러 서버에서 같은 상태를 공유하지 않는다
한 서버의 메모리에 주문 상태를 저장할 수 있다.
const order = inMemoryOrders.get(orderId);네트워크 없이 같은 프로세스에서 값을 읽으므로 매우 빠를 수 있다.
하지만 서비스가 여러 서버에서 실행된다면 문제가 생긴다.
서버 A의 주문 상태: PAID
서버 B의 주문 상태: SHIPPED
데이터베이스 상태: CANCELLED각 서버의 메모리는 서로 다른 시점의 복사본을 가질 수 있다.
크리스의 요청이 어느 서버에 도착하는지에 따라 다른 주문 상태를 볼 수 있다.
메모리 조회를 사용할 때는 다음 책임을 결정해야 한다.
- 어떤 데이터가 서버별로 달라도 되는가?
- 상태가 변경되면 모든 서버에 어떻게 알리는가?
- 서버가 재시작되면 데이터를 어떻게 다시 만드는가?
- 새로운 서버가 추가되면 초기 데이터를 어디에서 가져오는가?
- 메모리에 없는 값은 어디에서 조회하는가?
- 오래된 상태를 어느 정도까지 허용하는가?
변하지 않는 배송 방법 목록이나 화면 표시용 설정은 서버 메모리에 두기 쉬울 수 있다.
결제, 배송과 취소처럼 계속 바뀌는 주문 상태는 서버 메모리만 Source of Truth로 사용하기 어렵다.
빠른 저장 위치를 선택하면 그 데이터의 생명주기와 동기화 책임도 함께 생긴다.
한 번의 응답이라도 데이터 크기가 크면 느릴 수 있다
주문 상세 API가 한 번의 조회로 모든 데이터를 반환한다고 생각해보자.
const order =
await orderRepository.findWithEverything(
orderId
);
return order;메서드 호출은 한 번이다.
하지만 결과에 다음 데이터가 모두 포함될 수 있다.
- 주문 상품 수천 개
- 상품별 이미지와 설명
- 결제 시도 기록 전체
- 배송 상태 변경 기록 전체
- 환불 기록과 고객 문의
- 내부 운영 로그
응답 객체가 클수록 다음 비용이 증가한다.
- 데이터베이스에서 읽을 데이터
- 서버가 만들 객체 수
- JSON 변환 시간
- 서버 메모리 사용량
- 네트워크 전송량
- 브라우저의 응답 해석 시간
- 화면 렌더링 비용
한 번의 요청이라는 이유만으로 비용이 일정하지는 않다.
필요한 필드만 조회해야 한다.
SELECT
id,
status,
total_amount,
created_at
FROM orders
WHERE id = $1
AND user_id = $2;주문 상품은 별도의 페이지 단위로 조회할 수 있다.
SELECT
product_name,
quantity,
unit_price
FROM order_items
WHERE order_id = $1
ORDER BY id
LIMIT 20;요청 횟수만 줄이는 것과 처리할 데이터 양을 줄이는 것은 서로 다른 최적화다.
O(1)처럼 보이는 단건 조회에서도 결과 크기가 입력처럼 증가할 수 있다는 점을 확인해야 한다.
외부 입력 검증과 권한 확인은 생략할 수 없는 비용이다
주문 ID를 입력받아 바로 조회할 수 있다.
const order =
await orderRepository.findById(
request.params.orderId
);
return order;코드는 짧고 조회도 한 번이다.
하지만 주문 ID는 외부에서 들어온 값이다.
다른 사용자의 주문 ID를 넣으면 그 주문까지 반환할 수 있다.
먼저 형식을 검증하고 인증된 사용자의 소유 관계를 조회 조건에 포함해야 한다.
const orderId = parseOrderId(
request.params.orderId
);
const order =
await orderRepository.findByIdForUser({
orderId,
userId: session.user.id,
});
if (!order) {
return {
ok: false,
reason: "ORDER_NOT_FOUND",
};
}이 코드는 클라이언트가 보낸 사용자 ID를 신뢰하지 않는다.
로그인 세션에서 확인한 사용자 ID를 사용하고, 주문 ID와 소유자를 함께 조건으로 조회한다.
권한이 없는 사용자에게 주문의 존재 여부를 노출하지 않기 위해 외부에는 ORDER_NOT_FOUND처럼 일반화된 결과를 반환할 수 있다.
입력 검증과 권한 확인은 응답 시간을 조금 늘릴 수 있다.
그러나 이를 제거해서 얻은 속도는 안전한 성능 개선이 아니다.
서비스 성능은 필요한 보안과 정확성을 지키는 범위 안에서 판단해야 한다.
상태 변경은 조회보다 더 많은 책임을 가진다
주문 조회는 데이터를 읽고 반환하면 끝날 수 있다.
주문 취소는 상태를 변경하므로 더 많은 조건을 확인해야 한다.
다음 코드는 주문을 읽은 뒤 상태를 변경한다.
const order =
await orderRepository.findById(orderId);
if (order.status === "PAID") {
await orderRepository.updateStatus(
orderId,
"CANCELLED"
);
}하나의 요청만 실행될 때는 동작할 수 있다.
하지만 취소 요청과 배송 시작 요청이 동시에 들어오면 두 요청이 모두 PAID 상태를 읽을 수 있다.
그 결과 배송 중인 주문을 취소하거나, 취소된 주문을 배송 상태로 변경할 수 있다.
조건 확인과 상태 변경을 하나의 작업으로 처리해야 한다.
UPDATE orders
SET
status = 'CANCELLED',
cancelled_at = $3
WHERE id = $1
AND user_id = $2
AND status = 'PAID'
RETURNING id, status, cancelled_at;이 쿼리는 변경 순간에도 주문 상태가 PAID인 경우에만 취소한다.
주문 ID로 한 행을 변경하므로 애플리케이션 코드에서는 한 번의 저장소 호출로 보인다.
하지만 정확성을 위해 데이터베이스의 최신 상태, 잠금 경쟁과 트랜잭션을 고려해야 한다.
O(1)처럼 보이는 상태 변경도 동시에 많은 요청이 같은 주문이나 자원에 집중되면 기다림이 생길 수 있다.
알고리즘의 단계 수와 공유 상태를 안전하게 변경하는 비용은 별도로 살펴봐야 한다.
같은 O(1) 작업이 반복되면 전체 비용은 선형으로 증가한다
주문 목록 100개에 대해 각각 배송 상태를 외부 서비스에서 조회한다고 생각해보자.
for (const order of orders) {
order.deliveryStatus =
await deliveryClient.getStatus(
order.deliveryId
);
}배송 상태 한 건 조회는 주문 수와 관계없이 한 번의 원격 호출이다.
그러나 주문마다 실행하므로 전체 호출 수는 주문 수에 비례한다.
주문 한 건 조회: 한 번의 호출
주문 n건 조회: O(n)번의 원격 호출각 작업이 O(1)이어도 반복문 안에서 n번 호출하면 전체는 O(n)이 된다.
원격 서비스가 여러 배송 ID를 한 번에 조회하는 기능을 제공한다면 묶어서 요청할 수 있다.
const deliveryIds = orders.map(
(order) => order.deliveryId
);
const statusByDeliveryId =
await deliveryClient.getStatuses(
deliveryIds
);이 코드는 네트워크 왕복 횟수를 줄인다.
외부 서비스 내부에서는 여전히 여러 배송 상태를 처리하지만, 연결과 요청에 반복되는 고정 비용을 줄일 수 있다.
다만 요청 하나에 너무 많은 ID를 보내면 본문 크기와 처리 시간이 커진다. 적절한 묶음 크기를 정해야 한다.
O(1) 작업이라는 표현만 보지 말고 그 작업이 전체 흐름에서 몇 번 반복되는지 확인해야 한다.
동시에 많은 O(1) 요청이 들어오면 자원이 부족해질 수 있다
주문 ID 조회 한 건은 빠를 수 있다.
하지만 할인 행사 직후 수십만 명이 동시에 주문 상태를 새로고침하면 상황이 달라진다.
개별 요청은 다음과 같이 단순할 수 있다.
const order =
await orderRepository.findByIdForUser({
orderId,
userId,
});각 요청은 주문 한 건만 찾는다.
그래도 요청이 많아지면 다음 자원이 부족해질 수 있다.
- 데이터베이스 연결
- API 서버의 동시 처리 공간
- 원격 캐시 연결
- 네트워크 대역폭
- 데이터베이스 CPU와 디스크 처리량
- 외부 결제·배송 API의 호출 한도
한 요청의 알고리즘 복잡도는 서비스 전체 처리량을 직접 설명하지 않는다.
다음 두 값을 함께 봐야 한다.
요청 한 건의 비용
× 일정 시간 동안의 요청 수주문 데이터 수가 증가하지 않더라도 요청량이 증가하면 시스템은 느려질 수 있다.
따라서 O(1) API에도 캐시, 요청 제한, 연결 풀, 타임아웃과 장애 대응이 필요할 수 있다.
해시 조회의 O(1)은 보통 평균적인 기대 비용이다
JavaScript의 Map이나 해시 테이블은 키를 이용해 저장 위치를 찾는다.
일반적으로 조회, 삽입과 삭제의 평균 비용을 O(1)로 설명한다.
하지만 키를 저장 위치로 변환하는 과정에서 여러 키가 같은 위치에 대응할 수 있다. 이를 충돌이라고 한다.
구현은 충돌한 항목을 추가로 비교해야 한다.
대부분의 정상적인 사용에서는 빠르게 처리되도록 설계되어 있지만, O(1)이라는 표기는 모든 상황에서 정확히 한 단계만 실행한다는 뜻이 아니다.
또한 실제 비용에는 다음 요소가 포함된다.
- 키의 해시 값을 계산하는 비용
- 저장 구조가 차지하는 메모리
- 데이터 증가에 따른 내부 공간 재구성
- 긴 문자열이나 복잡한 키 처리
- 메모리 접근 패턴과 런타임 구현
따라서 자료구조의 평균 복잡도와 실제 환경에서의 성능을 구분해야 한다.
작은 데이터라면 더 단순한 배열 탐색이 충분할 수 있다. 반복 조회가 많고 데이터가 크다면 해시 기반 구조가 더 적절할 수 있다.
선택은 기호 하나가 아니라 실제 입력 크기와 사용 방식으로 결정해야 한다.
빠른 실패도 전체 서비스의 성능에 포함된다
외부 배송 서비스가 응답하지 않는 상황을 생각해보자.
const status =
await deliveryClient.getStatus(
deliveryId
);정상적인 경우에는 100밀리초 안에 응답할 수 있다.
장애가 발생하면 기본 타임아웃까지 30초를 기다릴 수도 있다.
호출 횟수는 여전히 한 번이지만 사용자는 매우 오래 기다린다.
적절한 타임아웃을 설정해야 한다.
const status =
await deliveryClient.getStatus(
deliveryId,
{ timeoutMs: 1000 }
);1초 안에 응답하지 않으면 명확하게 실패 처리한다.
주문 상태 전체를 실패시키기보다 배송 정보만 일시적으로 사용할 수 없다고 표현할 수도 있다.
return {
orderStatus: order.status,
deliveryStatus:
deliveryResult.ok
? deliveryResult.status
: "TEMPORARILY_UNAVAILABLE",
};이 결과는 주문 원본 상태와 외부 배송 상태를 구분한다.
빠른 서비스란 모든 요청이 항상 성공하는 서비스만을 의미하지 않는다.
의존 서비스가 느리거나 실패했을 때 기다리는 시간을 제한하고, 핵심 기능을 어디까지 유지할지 결정한 서비스이기도 하다.
O(1) 작업도 구간별로 측정해야 한다
주문 상세 API가 느리다면 전체 시간을 한 값으로만 기록해서는 원인을 찾기 어렵다.
const startedAt = performance.now();
const order =
await orderRepository.findByIdForUser({
orderId,
userId,
});
const orderLoadedAt = performance.now();
const delivery =
await deliveryClient.getStatus(
order.deliveryId
);
const completedAt = performance.now();
logger.info("Order detail timing", {
orderQueryMs:
orderLoadedAt - startedAt,
deliveryApiMs:
completedAt - orderLoadedAt,
totalMs:
completedAt - startedAt,
});이 코드는 주문 데이터베이스 조회와 배송 API 호출 시간을 구분해 기록한다.
측정 결과는 다음처럼 나타날 수 있다.
| 구간 | 측정 시간 |
|---|---|
| 인증과 권한 확인 | 20ms |
| 원격 캐시 조회 | 8ms |
| 데이터베이스 주문 조회 | 35ms |
| 배송 API 호출 | 1,400ms |
| 응답 변환 | 5ms |
모든 단계가 단건 작업이라도 배송 API 하나가 전체 지연을 결정할 수 있다.
측정 결과에 따라 해결책이 달라진다.
- 캐시가 느리면 네트워크 위치와 연결을 확인한다.
- 데이터베이스가 느리면 실행 계획과 인덱스를 확인한다.
- 배송 API가 느리면 타임아웃, 비동기 갱신이나 저장된 최근 상태를 검토한다.
- 응답이 크면 필요한 필드와 목록 크기를 줄인다.
- 연결 대기가 길면 연결 풀과 동시 요청량을 확인한다.
복잡도는 데이터 증가에 따른 구조적 위험을 설명한다.
측정은 현재 실제로 느린 구간을 찾는다.
둘을 함께 사용해야 한다.
O(1)을 설계 판단에 사용할 때 물어봐야 할 질문
한 번의 조회나 변경을 빠르다고 판단하기 전에 다음 질문을 확인할 수 있다.
- 현재
O(1)이라고 부르는 작업은 무엇인가? - 입력 크기와 관계없이 일정한 것은 단계 수인가, 실제 시간인가?
- 조회 전에 필요한 사전 계산이나 자료구조 생성 비용은 얼마인가?
- 그 자료구조를 몇 번 재사용하는가?
- 추가로 사용하는 메모리와 저장 공간은 얼마인가?
- 데이터가 변경될 때 조회 구조를 어떻게 갱신하는가?
- 작업은 같은 프로세스의 메모리에서 끝나는가?
- 데이터베이스, 캐시나 외부 API를 네트워크로 호출하는가?
- 원격 호출의 연결, 대기와 타임아웃 비용을 고려했는가?
- 데이터베이스 내부에서 어떤 인덱스와 실행 계획을 사용하는가?
- 메서드를 한 번 호출한다는 사실을 내부 작업도 한 단계라고 오해하고 있지는 않은가?
- 캐시 적중과 미적중 경로의 비용은 각각 얼마인가?
- 캐시 미스가 동시에 몰리면 데이터베이스에 어떤 영향을 주는가?
- 캐시된 값은 어느 정도까지 오래되어도 되는가?
- 원본 데이터와 복제되거나 계산된 데이터를 구분했는가?
- 최종 판단의 Source of Truth는 어디에 있는가?
- 서버가 여러 대일 때 메모리 상태를 어떻게 동기화하는가?
- 서버 재시작과 확장 시 메모리 데이터를 어떻게 복구하는가?
- 단건 조회가 반환하는 데이터 크기는 얼마인가?
- 필요하지 않은 관계와 기록까지 함께 가져오고 있지는 않은가?
- 외부 입력의 형식과 크기를 검증했는가?
- 인증된 사용자와 데이터의 소유 관계를 확인하는가?
- 성능을 위해 권한이나 최신 상태 검증을 생략하고 있지는 않은가?
- 동시에 상태가 변경될 때 조건부 갱신이 필요한가?
O(1)작업이 반복문 안에서 몇 번 실행되는가?- 요청 한 건이 아니라 전체 요청량도 감당할 수 있는가?
- 의존 서비스가 느릴 때 타임아웃과 실패 결과가 정의되어 있는가?
- 구간별 실제 시간을 측정하고 있는가?
- 평균뿐 아니라 느린 요청의 원인도 관찰하는가?
- 더 복잡한 조회 구조가 현재 데이터 규모에서 정말 필요한가?
이 질문은 O(1)이 나쁜 복잡도라는 뜻이 아니다.
입력 증가에 강한 조회 구조는 반복적인 탐색 비용을 줄이는 중요한 도구다. 다만 그 조회를 가능하게 하는 준비 비용, 저장 위치와 최신성 책임까지 함께 고려해야 한다.
O(1)은 짧은 코드가 아니라 제한된 증가를 의미한다
O(1)은 유용한 성질이다.
주문 데이터가 증가해도 특정 ID 조회의 단계 수가 함께 선형으로 증가하지 않는다면 서비스가 성장할 때 유리할 수 있다.
그러나 실제 서비스의 속도는 복잡도 기호 하나로 결정되지 않는다.
Map을 만들기 위해 전체 데이터를 먼저 읽을 수 있다.- 데이터베이스는 인덱스를 탐색하고 디스크를 읽을 수 있다.
- 원격 캐시는 네트워크를 거친다.
- 캐시 미스는 더 느린 저장소 조회를 만든다.
- 오래된 캐시는 잘못된 주문 상태를 반환할 수 있다.
- 단건 응답도 데이터가 크면 전송과 변환이 느리다.
- 권한과 최신 상태 검증은 반드시 유지해야 한다.
- 한 번의 작업도 많은 요청이 동시에 실행하면 자원을 소진할 수 있다.
- 외부 서비스 장애는 한 번의 호출을 긴 대기로 바꿀 수 있다.
따라서 O(1)이라는 설명 뒤에는 다음 문장이 이어져야 한다.
무엇에 대해 일정하며, 그 한 번의 작업은 어디에서 실행되고, 어떤 준비와 통신과 검증을 포함하는가?
실제 서비스에서
O(1)은 값비싼 작업도 한 번이면 빠르다는 뜻이 아니다. 데이터가 증가해도 작업 단계가 같은 비율로 늘어나지 않는다는 뜻이며, 실제 성능은 그 단계의 비용, 데이터 위치, 네트워크, 캐시 상태와 정확성 요구를 함께 측정해야 판단할 수 있다.
작은 배열을 한 번 조회한다면 O(n) 탐색으로 충분할 수 있다.
같은 데이터를 반복해서 조회한다면 Map, 인덱스나 캐시를 고려할 수 있다. 그러나 더 빠른 조회 구조를 선택하는 순간 생성, 갱신, 동기화와 실패 처리의 책임도 함께 생긴다.
좋은 설계는 O(1)이라는 기호를 얻는 데서 끝나지 않는다.
그 조회가 실제 요청 흐름에서 얼마나 걸리고, 어떤 상태를 신뢰하며, 서비스가 커져도 정확성을 유지할 수 있는지 설명해야 한다.
