자료구조의 최적화 주요 포인트

회사에 들어가기 전에는 DB보다 로직 성능에 더 신경을 썼다. 막상 와보니 서버 부하의 절반은 DB, 나머지 절반은 로직 부하였다.

지금까지 내가 겪은 다양한 부하 케이스와 성능 최적화 경험을 쭉 정리해볼까 한다. 웹 서버 성능 관련 글들을 보면 대부분 아키텍처 얘기만 있고, 서버 자체의 로직 퍼포먼스에 대한 얘기는 잘 안 보여서 아쉬웠다.

최적화의 대상: 느린 장치부터 빠른 장치 순으로

컴퓨터는 여러 저장 장치를 계층적으로 사용하며, 그 속도 차이는 엄청나다. 최적화는 결국 느린 장치의 접근을 줄이고 빠른 장치를 최대한 활용하는 것이다.

느림 4. 네트워크 -> 3. 하드디스크/SSD -> 2. RAM -> 1. 캐시 메모리 빠름

image.png image.png

1. 데이터베이스 (DB) 부하 최적화

서버가 단순히 DB 데이터만 읽고 쓰는 역할(CRUD)만 할수록, 대부분의 병목은 DB에서 발생한다.

Stored Procedure (SP) 활용

  • 상황: 특정 작업을 위해 DB 쿼리를 여러 번 호출해야 할 때.
  • 원리: 코드에서 DB를 여러 번 호출하는 것은 애플리케이션 <-> DB 간의 네트워크 통신을 반복적으로 발생시킨다. SP는 DB 단에서 직접 로직을 수행하므로 이 통신 비용을 크게 줄일 수 있다.
  • 장점:
    • 네트워크 왕복 비용 감소.
    • 긴 쿼리를 주고받는 상황에서 네트워크 패킷 크기 감소.
  • 단점:
    • SP는 코드와 별개로 DB에 존재하므로 관리 포인트가 이원화된다. 이는 결국 유지보수의 어려움으로 이어진다.

인덱싱 (Indexing)

  • 너무 기본적이고 중요한 내용이라 자세한 설명은 생략한다. (필수!)

캐시 (Cache) 도입

  • 상황: DB 부하가 너무 커서 더 이상 감당이 안 될 때.
  • 원리: DISK 접근(DB) 비용을 메모리 접근(캐시) 비용으로 대체한다.
  • 결과:
    • Redis 같은 캐시 레이어를 도입하면 stateful 서버가 된다.
    • 캐시 서버가 다운되었을 때를 대비한 롤백 방안 등을 마련해야 하는 Trade-off가 발생한다.

2. 로직 최적화

로직 최적화는 크게 두 가지 방향으로 나눌 수 있다.

  1. 병목 지점 호출 자체를 줄이기: 10번 호출하던 것을 1번만 호출하도록 구조를 개선.
  2. 코드 자체를 빠르게 만들기: 10번의 호출 자체를 더 빠르게 만든다.

예를 들어, 기존에 1개만 처리하던 스펙을 N개 처리하도록 변경할 때, 단순히 로직을 N번 반복 실행하면 부하가 발생할 수 있다. 이럴 땐 처음부터 N개를 고려한 로직으로 새로 작성하는 것이 좋다.

early return 등을 활용해 불필요한 호출을 원천 차단하는 방법도 있지만, 해당 로직과 스펙을 완벽하게 파악해야 해서 난이도가 높다.

전체 코드를 모르는 상태에서는 보통 2번 방식, 즉 코드 자체를 빠르게 만드는 것을 우선 고려하게 된다. 여기서는 자료구조 관점의 최적화를 깊게 다뤄본다.

3. 자료구조 최적화 (시간 복잡도의 함정)

주요 자료구조는 보통 세 가지로 나뉜다.

  1. 배열: vector, list 등
  2. 해시 테이블: std::unordered_map, std::unordered_set
  3. 트리 구조: std::map, std::set

자료구조를 논할 때 시간 복잡도(Big-O)만 생각해선 안된다. 반드시 아래 두 가지를 함께 고려해야 한다.

  • 캐시 메모리 효율
  • 메모리 할당/해제 비용

메모리 할당/해제는 O(1)로 퉁치기엔 생각보다 훨씬 비싼 연산이다. 시간 복잡도는 N이 아주 클 때 의미가 있지만, 실제로는 N이 커지기 전에 단일 연산 자체가 병목을 만드는 경우가 많다.

배열 vs. 링크드 리스트

  • 배열:
    • 메모리 할당/해제 비용이 가장 싸다.
    • 데이터가 메모리에 연속적으로 위치해 캐시 효율이 가장 좋다.
  • 링크드 리스트:
    • 데이터를 추가할 때마다 노드(Node) 단위로 메모리 할당이 발생한다. (비용이 비싸다)
    • 데이터가 메모리에 흩어져 있어 캐시 효율이 나쁘다.

배열의 맨 끝에 원소를 삽입하는 것과 링크드 리스트의 맨 끝에 삽입하는 것은 시간 복잡도는 둘 다 O(1)이지만, 실제 성능은 하늘과 땅 차이다.

해시 테이블 vs. 트리

  • 해시 테이블 (unordered_map):
    • 일반적으로 Key-Value 자료구조가 필요할 때 가장 먼저 권장된다.
    • 단, 전체 데이터가 캐시 안에 다 들어갈 정도로 작다면, 배열로 직접 구현해서 최적화를 쥐어짜 볼 여지가 있다.
  • 트리 (map, set):
    • 메모리 생성/해제 비용이 최악이다. 시간 복잡도를 따지기 전에 그냥 기본 성능 자체가 느리다.
    • 순회 시 정렬이 보장되어야 하는 등, 아래와 같은 매우 특수한 경우가 아니면 최후의 선택지로 남겨두는 것이 좋다.
      1. 데이터의 정렬 상태 유지가 필수일 때
      2. N이 아주 크고, 중간 삽입/삭제가 매우 빈번할 때
      3. 위 케이스에 해당하는 자료구조가 전역적으로 접근될 때

그래서 뭘 써야 하는가?

  • vector(가변 배열)를 우선적으로 고려하라.
    • reserve()로 초기 메모리를 크게 할당하면 불필요한 재할당 비용을 줄일 수 있다.
    • 무식해 보일 수 있지만, 그냥 전체 순회(Linear Scan)하는 것이 캐시 효율 덕분에 어설픈 자료구조보다 빠를 때가 많다.
    • 정렬이 필요하면, 그냥 vector를 통째로 정렬(std::sort)해서 사용하라.

경험적으로 list 자료구조를 써야겠다고 판단한 적은 한 번도 없었다. 오히려 vector의 복사 비용을 아끼려고 list로 바꿨다가 역으로 성능이 저하된 경험은 있다.

최종으로 자료구조 선택은 아래 항목들을 복합적으로 고려해서 결정해야 한다.

  • 데이터의 총량 (N)
  • 삽입: 앞/중간/뒤 중 어디에, 얼마나 자주?
  • 삭제: 앞/중간/뒤 중 어디서, 얼마나 자주?
  • 순회: 전체 순회를 얼마나 자주 하는가?
  • 접근: 단일 원소 접근을 얼마나 자주 하는가?
  • 각 연산 시 메모리 할당/해제가 발생하는가?

4. 하드웨어 레벨 최적화 (컴퓨터 구조)

그래픽스 분야처럼 하나의 함수를 수천, 수만 번씩 호출하는 환경에서는 아주 작은 비효율도 큰 성능 저하로 이어진다. 이때는 컴파일러의 최적화 결과물까지 신경 쓰며 코드를 작성해야 한다.

  • 캐시 메모리 접근 최적화:
    • False Sharing을 고려하여 구조체 크기를 캐시 라인(대체로 64 byte)에 맞추기.
    • 16 byte 미만의 작은 객체는 함수에 넘길 때 포인터보다 값 복사(pass-by-value)가 더 빠를 수 있다.
  • 메모리 접근 최소화
    • 메모리 jump 횟수 최적화 (virtual 함수 쓰지 않기 등.)
  • 분기 예측 최적화: if문으로 인한 분기 예측 실패 비용 고려하기.
  • SIMD (Single Instruction, Multiple Data): 단일 명령으로 여러 데이터를 한 번에 처리하는 기법 활용.

5. 파일 입출력 최적화

엑셀(Excel)처럼 복잡한 형식의 대용량 파일을 파싱할 때 성능 저하가 크게 발생할 수 있다.

이때 라이브러리가 제공하는 편리한 함수 대신, 파일을 Raw 데이터로 한 번에 읽어온 뒤, 필요한 부분만 직접 파싱하도록 로직을 변경하면 시간을 수십, 수백 배까지 획기적으로 줄일 수 있다.

파싱 시간이 너무 길어 업무에 영향을 주거나, 작업의 가능/불가능을 논해야 할 정도라면 시도해볼 만한 방법이다.

Posted 2025-01-12
cs