백엔드 기술 복습

헷갈렸던 기술들을 복습한다.

1. 배열 vs 연결리스트

연산별 비교

연산	배열	연결리스트
인덱스 접근	O(1)	O(n)
값 탐색	O(n)	O(n)
맨 앞 삽입/삭제	O(n)	O(1)
중간 삽입/삭제 (위치를 이미 참조 중)	O(n)	O(1)
중간 삽입/삭제 (인덱스만 아는 경우)	O(n)	O(n)

마지막 줄이 자주 잘못 이야기되는 부분이다. 연결리스트의 중간 삽입이 O(1)인 것은 해당 노드의 참조를 이미 손에 들고 있을 때뿐이다. list.add(5000, x)처럼 인덱스만 아는 상태라면 head부터 5000번 따라가야 하므로 결국 O(n)이다. 순회 중 이터레이터로 삭제하는 상황이 아니라면 이 이점은 잘 발생하지 않는다.

진짜 차이는 메모리 배치

시간복잡도 표만으로는 왜 실무에서 배열 기반 자료구조를 기본으로 쓰는지 설명되지 않는다. 이유는 캐시다.

CPU는 메모리를 바이트 단위가 아니라 캐시 라인 단위(보통 64바이트) 로 읽어온다. 4바이트 int 배열을 순회하면 한 번의 메모리 접근으로 16개 원소가 캐시에 올라오고, 나머지 15번은 캐시 히트다. 게다가 하드웨어 프리페처가 순차 접근 패턴을 감지해 다음 라인을 미리 당겨온다.

연결리스트는 노드가 힙 여기저기에 흩어져 있다. 노드를 하나 따라갈 때마다 새로운 캐시 라인을 읽어야 하고, 주소가 예측 불가능하니 프리페처도 도움이 되지 않는다. 포인터 추적(pointer chasing) 은 매 단계가 메모리 지연(수십~수백 사이클)에 그대로 노출된다.

공간 오버헤드도 있다. Java LinkedList의 노드는 값 참조 외에 prev/next 참조와 객체 헤더를 함께 들고 있어, 원소 하나당 수십 바이트가 추가로 든다. 담는 데이터가 작을수록 이 비율은 커진다.

그래서

기본은 ArrayList. 크기 증가는 1.5배씩 늘리는 방식이라 분할 상환하면 추가 비용은 O(1) 이다.
큐/덱이 필요하면 LinkedList보다 ArrayDeque가 낫다. 원형 배열 기반이라 양끝 연산이 O(1)이면서 캐시 지역성도 유지된다.
연결리스트가 실제로 유리한 경우는 “순회하면서 조건에 맞는 노드를 제거”처럼 참조를 이미 들고 있는 상태의 삽입/삭제가 반복될 때 정도다.

2. 이진 탐색 트리와 B-tree

최악의 경우가 O(n)인 이유

BST 탐색 비용은 정확히는 O(n)이나 O(log n)이 아니라 O(h), 즉 트리 높이에 비례한다. 문제는 h가 삽입 순서에 따라 달라진다는 점이다.

1, 2, 3, 4, 5를 순서대로 삽입하면 새 값은 항상 현재 노드보다 커서 오른쪽 자식으로만 붙는다. 결과는 한쪽으로 완전히 치우친(skewed) 트리이고, 이는 사실상 연결리스트다. h = n이 되어 탐색이 O(n)이 된다.

O(log n)이 나오는 전제는 “매 비교마다 후보가 절반씩 줄어든다”는 것이고, 그 전제는 좌우 서브트리 크기가 비슷할 때만 성립한다. 정렬된 데이터를 그대로 넣는 것은 실무에서 드물지 않기 때문에(예: 자동 증가 ID, 타임스탬프) 이건 이론적인 걱정이 아니다.

균형 트리

AVL 트리: 모든 노드에서 좌우 높이 차를 1 이하로 유지한다. 균형이 엄격해서 탐색이 빠른 대신, 삽입/삭제 때 회전이 더 자주 일어난다. 읽기가 많은 워크로드에 맞는다.
Red-Black 트리: “루트에서 리프까지 검은 노드 수가 같다” 같은 느슨한 규칙으로 최대 높이를 2log(n+1) 이하로 묶는다. 균형이 덜 엄격한 대신 재조정 비용이 적어 쓰기가 섞인 워크로드에 유리하다. Java의 TreeMap, HashMap의 트리화된 버킷이 이 구조다.

DB 인덱스가 B-tree인 이유

메모리 자료구조와 디스크 자료구조는 최적화 대상이 다르다. 디스크(혹은 SSD)에서는 비교 횟수가 아니라 페이지 I/O 횟수가 비용을 지배한다.

이진 트리는 노드마다 자식이 둘뿐이라 원소가 100만 개면 높이가 20이고, 최악의 경우 20번의 랜덤 I/O가 필요하다. B-tree는 노드 하나를 디스크 페이지 크기(InnoDB 기본 16KB) 에 맞춰 키를 수백 개씩 담는다. 팬아웃이 수백이 되면 같은 100만 건도 높이가 3 정도로 떨어진다. 게다가 상위 레벨 노드는 버퍼 풀에 캐시되어 있어 실제 디스크 접근은 리프 한 번 수준이다.

B+tree는 여기서 한 걸음 더 나간다.

실제 데이터(혹은 PK)는 리프 노드에만 두고 내부 노드는 키만 담는다 → 팬아웃이 더 커진다
리프 노드끼리 양방향 링크드 리스트로 연결된다 → WHERE created_at BETWEEN ... 같은 범위 스캔에서 트리를 다시 타지 않고 리프를 따라 훑으면 된다

인덱스 설계에서 정렬과 범위 조건이 왜 그렇게 잘 맞아떨어지는지가 여기서 나온다.

3. 유니크 인덱스의 실제 비용

풀스캔이 아니다

유니크 제약은 내부적으로 유니크 인덱스(B-tree) 로 구현된다. 삽입 시 중복 확인은 그 인덱스를 타는 탐색이므로 O(log n) 이지, 테이블 전체를 훑는 것이 아니다.

그럼 실제 비용은 어디서 나오나

인덱스 유지 비용: 쓰기마다 B-tree에 키를 넣고, 페이지가 꽉 차면 분할(split)이 일어난다. 랜덤한 값(UUID 등)을 인덱스로 잡으면 분할과 페이지 파편화가 잦아진다.
체인지 버퍼를 못 쓴다: InnoDB는 세컨더리 인덱스 갱신을 메모리에 모아뒀다 나중에 반영하는 change buffer 최적화를 갖고 있는데, 유니크 인덱스에는 적용되지 않는다. 중복 여부를 지금 당장 확인해야 하므로 해당 페이지를 반드시 디스크에서 읽어와야 하기 때문이다. 쓰기가 많은 테이블에서 유니크 인덱스가 비싼 진짜 이유가 이것이다.
잠금: 중복 체크 과정에서 인덱스 레코드에 락이 잡힌다. 동시에 같은 키로 들어온 트랜잭션은 대기하고, 격리 수준에 따라 갭 락이 얽히면 데드락이 생길 수도 있다.

그래도 거는 게 맞는 경우

선착순 쿠폰 발급처럼 중복·초과 발급이 곧 사고인 도메인에서는 (coupon_id, member_id)에 UNIQUE를 걸어 최종 방어선으로 둔다.

애플리케이션에서 “조회해보고 없으면 INSERT”하는 방식은 조회와 삽입 사이에 다른 트랜잭션이 끼어들 수 있어 동시성 상황에서 언제든 뚫린다. Redis 카운터나 분산 락으로 앞단을 막더라도 그것들은 장애·재시도·타임아웃 상황에서 완벽하지 않다. DB 유니크 제약은 그 모든 게 실패해도 뚫리지 않는 마지막 계층이다.

중복 시 예외를 던지게 두고 애플리케이션에서 “이미 발급됨”으로 변환하거나, INSERT ... ON DUPLICATE KEY UPDATE로 흡수하는 식으로 설계한다. 성능 주장이 갈릴 때는 결국 실측한 숫자가 근거다.

4. 뮤텍스 vs 세마포어

개념

뮤텍스: 상호배제를 위한 락. 소유권이 있어서 잠근 스레드만 풀 수 있다. 동시 진입은 1개.
세마포어: 사용 가능한 자원 개수를 세는 카운터. acquire()로 감소, release()로 증가하며 0이면 대기한다. N개까지 동시 진입.

이진 세마포어와 뮤텍스는 왜 다른가

N=1인 세마포어는 겉보기 동작이 뮤텍스와 같아 보이지만 소유권 개념이 없다. 이 차이가 실제로 만드는 결과는 다음과 같다.

A가 획득한 이진 세마포어를 B가 반환할 수 있다. 뮤텍스에서는 오류다.
뮤텍스는 재진입(reentrant) 지원이 가능하다. 같은 스레드가 이미 들고 있는 락을 다시 잡을 수 있다. 세마포어는 소유자를 모르니 그대로 자기 자신을 블록시킨다.
우선순위 역전 대응이 가능하다. 낮은 우선순위 스레드가 락을 쥔 채 밀려나 높은 우선순위 스레드가 무한정 대기하는 상황에서, 뮤텍스는 소유자를 알기 때문에 소유자의 우선순위를 임시로 올려주는 우선순위 상속을 구현할 수 있다.

용도 구분

상호배제: 뮤텍스. Java에서는 synchronized, ReentrantLock.
자원 개수 제한: 세마포어. 커넥션 풀, 동시 요청 수 제한, API 호출 스로틀링.
시그널링: 세마포어. 생산자가 release(), 소비자가 acquire()하는 식으로 스레드 간 신호를 주고받는 데 쓸 수 있다. 반환 주체가 획득 주체와 달라도 되기 때문에 가능한 사용법이고, 뮤텍스로는 할 수 없다.

5. 대칭키 vs 비대칭키

두 방식

대칭키: 암호화와 복호화에 같은 키를 쓴다(AES 등). 빠르다. AES는 CPU 전용 명령어(AES-NI) 지원까지 있어 처리량이 크다. 문제는 “그 키를 상대에게 어떻게 안전하게 전달하느냐”다.
비대칭키: 공개키와 개인키 한 쌍을 쓴다(RSA, ECC 등). 공개키로 암호화한 것은 개인키로만 풀리고, 개인키로 서명한 것은 공개키로 검증된다. 대칭키보다 수백~수천 배 느리다.

또 하나 실무적인 차이로, 비대칭키는 한 번에 다룰 수 있는 데이터 크기가 키 길이에 묶여 있다. 대용량 데이터를 통째로 비대칭키로 암호화하는 방식 자체가 성립하지 않는다.

TLS는 둘을 어떻게 조합하나

핵심은 비대칭키를 데이터 암호화가 아니라 인증과 키 합의에만 쓰고, 실제 데이터는 대칭키로 처리한다는 것이다.

TLS 1.3 기준 흐름은 이렇다.

클라이언트와 서버가 ECDHE(타원곡선 Diffie-Hellman) 로 각자의 임시 공개값을 교환하고, 각자 자기 개인값과 상대 공개값을 조합해 같은 비밀값을 도출한다. 이 비밀값 자체는 네트워크에 흐르지 않는다.
서버는 인증서와, 핸드셰이크 내용에 대한 개인키 서명을 보낸다. 클라이언트는 CA 체인으로 인증서를 검증하고 서명을 확인해 “지금 이 서버가 그 인증서의 개인키를 실제로 갖고 있다”는 사실을 확인한다.
도출한 비밀값에서 대칭키를 파생시키고, 이후 모든 데이터는 AES-GCM 같은 대칭 암호로 주고받는다.

여기서 두 가지를 짚어둘 만하다.

비대칭키의 역할은 신원 인증(서명) 이고, 키 합의는 ECDHE가 맡는다. RSA 공개키로 대칭키를 직접 암호화해 보내는 방식(RSA key transport)은 TLS 1.3에서 제거됐다.
임시(ephemeral) 키를 쓰는 이유는 전방 비밀성(forward secrecy) 때문이다. 나중에 서버 개인키가 유출되더라도, 과거에 녹화해둔 트래픽은 복호화할 수 없다. 세션마다 키가 새로 만들어지고 버려지기 때문이다.

6. Kafka 컨슈머 장애 복구

리밸런싱

컨슈머 그룹은 브로커 쪽 그룹 코디네이터가 관리한다. 각 컨슈머는 백그라운드 스레드로 주기적인 하트비트를 보내고, session.timeout.ms 안에 하트비트가 끊기면 코디네이터가 그 컨슈머를 죽은 것으로 판단해 리밸런싱을 트리거한다. 담당하던 파티션은 살아 있는 다른 컨슈머에게 재할당된다.

프로세스가 살아 있어도 쫓겨날 수 있다. 한 번의 poll() 이후 다음 poll()까지 max.poll.interval.ms를 넘기면(=메시지 처리가 너무 오래 걸리면) 코디네이터는 그 컨슈머가 진행 불가 상태라고 보고 그룹에서 제외한다. 처리 시간이 긴 컨슈머에서 “멀쩡한데 계속 리밸런싱이 돈다”면 대개 이쪽이다. max.poll.records를 줄이거나 인터벌을 늘려 맞춘다.

리밸런싱 자체도 비용이다. 기본(eager) 방식은 모든 컨슈머가 일단 할당을 전부 반납한 뒤 다시 나눠 갖는 stop-the-world 형태라 그동안 소비가 멈춘다. 이를 줄이려면 바뀐 파티션만 옮기는 cooperative sticky 할당 전략을 쓰거나, 재배포처럼 잠깐 나갔다 돌아오는 경우에 대비해 group.instance.id를 부여하는 정적 멤버십으로 불필요한 리밸런싱을 막는다.

어디부터 다시 읽는가

이어받은 컨슈머는 __consumer_offsets 토픽에 커밋된 오프셋부터 다시 읽는다. 그래서 커밋 시점이 전달 보장을 결정한다.

처리 후 커밋: 처리했지만 커밋 직전에 죽으면 그 메시지를 다시 받는다 → 중복 가능 (at-least-once)
처리 전 커밋: 커밋했지만 처리 중 죽으면 그 메시지는 사라진다 → 유실 가능 (at-most-once)

기본값인 enable.auto.commit=true는 poll 시점에 이전 배치를 자동 커밋하기 때문에 경계가 모호하다. 정확한 제어가 필요하면 수동 커밋으로 바꾼다.

실무에서는 at-least-once를 택하고 컨슈머 로직을 멱등하게 만드는 쪽이 일반적이다. 메시지에 고유 키를 넣어 처리 이력을 확인하거나, DB 유니크 제약으로 중복 삽입을 흡수하거나, UPSERT로 몇 번 처리해도 같은 결과가 되게 한다.

Druid 인제스천

Druid는 컨슈머를 직접 관리하지 않고 슈퍼바이저가 인제스천 태스크의 수명주기를 관리한다. 태스크가 실패하면 슈퍼바이저가 감지해 재시작하고, 태스크가 어디까지 읽었는지는 메타데이터 저장소에 기록된 오프셋으로 판단해 그 지점부터 이어서 소비한다. 세그먼트 커밋과 오프셋 기록을 하나의 트랜잭션으로 묶기 때문에 재시작 후에도 중복 적재가 생기지 않는다.

7. 정합성 사전 모니터링

장애를 “고객 문의로 알게 되는 것”과 “시스템이 먼저 알려주는 것”의 차이를 만드는 게 대사 배치다.

대사(reconciliation) 배치

주기적으로 두 소스의 값을 비교한다. 선착순 쿠폰이라면 Redis 카운터의 발급 수 vs DB 발급 레코드 수다. 설계할 때 챙길 것들:

기준 시점을 고정한다. 두 값을 시차를 두고 읽으면 그 사이 발급된 건 때문에 항상 차이가 난다. 특정 시각까지의 데이터만 비교하도록 컷오프를 두거나, 처리 중인 건을 감안한 허용 오차를 둔다.
어느 쪽이 진실인지 정한다. 불일치를 발견했을 때 무엇을 기준으로 맞출지가 없으면 복구를 자동화할 수 없다. 보통 영속화된 DB를 진실로 두고 캐시 카운터를 재계산한다.
복구는 멱등하게. 대사 배치가 여러 번 돌아도 결과가 같아야 한다.

알림과 지표

차이가 임계치를 넘으면 Slack이나 메일로 담당자에게 알린다.
발급 성공/실패 수, 카운터 격차, 대사 배치 실행 시각 같은 지표를 Prometheus로 노출하고 Grafana에서 추적한다. 격차는 누적값(counter)이 아니라 현재 상태(gauge)로 두는 게 읽기 편하다.
알림 임계치는 절대값보다 변화율로 잡는 편이 낫다. 상시로 소소한 오차가 있는 시스템에서 절대값 기준을 걸면 알림이 계속 울리고, 그러면 아무도 안 본다.
배치가 안 도는 상황도 감지해야 한다. 마지막 성공 시각을 지표로 내보내고, 그 값이 오래됐으면 알림을 띄운다. 대사 배치 자체가 죽으면 “이상 없음”과 구분되지 않기 때문이다.

8. 헥사고날 vs 레이어드

차이는 의존성 방향

레이어드: Controller → Service → Repository로 위에서 아래로 의존한다. 단순하고 익숙하다. 대신 Repository가 JPA를 쓰면 그 엔티티가 Service를 거쳐 Controller까지 새어 나가기 쉽고, 그 상태가 되면 영속화 기술을 바꿀 때 도메인 코드까지 함께 흔들린다.
헥사고날(포트&어댑터): 도메인을 중심에 두고, 도메인은 포트(인터페이스) 만 알게 한다. DB·메시지 브로커·외부 API 같은 기술은 그 포트를 구현하는 어댑터로 바깥에 둔다. 의존성이 항상 안쪽(도메인)을 향하므로 도메인이 기술을 모른다.

포트는 방향에 따라 나뉜다. 바깥에서 도메인을 호출하는 인바운드 포트(유스케이스 인터페이스)와, 도메인이 바깥을 호출하는 아웃바운드 포트(저장소·알림 인터페이스)다. 후자에서 의존성 역전이 일어나 도메인이 인프라를 향하지 않게 된다.

얻는 것과 치르는 것

얻는 것은 테스트 용이성과 교체 가능성이다. 아웃바운드 포트를 인메모리 페이크로 갈아끼우면 DB 없이 도메인 로직을 테스트할 수 있고, 저장소를 바꿔도 어댑터만 새로 쓰면 된다.

치르는 것은 간접 계층이다. 도메인 모델과 영속화 엔티티를 분리하면 둘 사이를 오가는 매핑 코드가 계속 생기고, 인터페이스와 구현이 매번 쌍으로 늘어난다.

도메인 로직이 얇으면 이 비용이 이득보다 크다. CRUD에 가까운 기능에서는 격리할 도메인 자체가 별로 없어서, 포트와 어댑터가 사실상 Repository 인터페이스를 한 번 더 감싼 것에 그친다. 아키텍처 선택은 좋고 나쁨이 아니라 도메인 복잡도에 대한 트레이드오프다.

9. RAG 리랭킹

bi-encoder의 한계

벡터 검색은 bi-encoder 구조다. 질의와 문서를 각각 독립적으로 벡터로 인코딩하고, 코사인 유사도 같은 거리로 비교한다. 문서 벡터는 미리 계산해 인덱싱해둘 수 있어서 수백만 건에서도 밀리초 단위로 후보를 뽑는다.

대신 정밀도에 한계가 있다. 질의와 문서가 서로를 보지 못한 채 각자 하나의 벡터로 압축되기 때문에, 어느 단어가 어느 문장과 대응하는지 같은 세밀한 관계가 표현되지 않는다. 결과적으로 “주제는 비슷한데 정작 질문에 답하지 않는 문서”가 상위에 올라오곤 한다.

cross-encoder로 재정렬

cross-encoder는 질의와 문서를 하나의 입력으로 이어 붙여 모델에 넣고 관련도 점수를 직접 출력한다. 어텐션이 질의 토큰과 문서 토큰 사이를 오가므로 훨씬 정확하다.

문제는 미리 계산해둘 수 없다는 것이다. 질의가 정해져야 점수가 나오므로 (질의, 문서) 쌍마다 모델을 한 번씩 돌려야 한다. 전체 코퍼스에 적용하는 건 불가능하다.

그래서 두 단계로 나눈다.

검색: bi-encoder(+BM25 같은 키워드 검색)로 top-k 후보를 넉넉히 뽑는다. k는 보통 50~100.
리랭킹: cross-encoder로 그 k개만 재채점해 상위 5~10개를 남긴다.
생성: 남은 문서만 LLM 컨텍스트에 넣는다.

느린 모델을 후보 k개에만 적용하는 비용과 정확도의 절충이다. k를 키우면 재현율은 오르지만 리랭킹 지연이 선형으로 늘어나므로, 지연 예산을 보고 정한다.

리랭킹은 컨텍스트 길이 측면에서도 의미가 있다. LLM에 문서를 많이 넣을수록 비용이 늘고, 관련 없는 문서가 섞이면 오히려 답변 품질이 떨어진다. 상위 몇 개만 정확하게 골라 넣는 편이 낫다.