KGS (Key Generation Service) 설계 - LeeEuyJoon/lilling-be GitHub Wiki

1. 개요

Lilling 은 대규모 URL 단축 서비스로,
짧은 URL을 생성하기 위해서는 충돌 없이 고유한 ID를 효율적으로 발급하는 것이 핵심이다.

이를 위해 고유 ID 발급을 담당하는 별도의 마이크로서비스
Key Generation Service (KGS) 를 설계하였다.
KGS는 다중 App 서버 환경에서도 ID 충돌 없이, 빠르고 안정적으로 ID를 관리한다.

2. 설계 목표

목표	설명
영속성 보장	DB 기반 관리로 재시작 후에도 ID 연속성 유지
분산 환경 지원	다중 App 서버에서 동시에 ID 발급 가능
고성능 / 저지연	App 서버는 로컬 캐시에서 즉시 ID 사용
전역 고유성 확보	3.5조(=62⁷) 이하 범위 내에서 ID 중복 방지
역할 분리	KGS는 정수 ID만 발급, Base62 인코딩은 App 서버에서 수행

3. KGS 아키텍처

4. 기존 접근(`auto_increment`)의 한계

초기 구현은 DB의 auto_increment PK 를 기반으로
해당 값을 스크램블링 후 Base62로 인코딩하는 방식이었다.

그러나 이 구조는 확장성 병목(bottleneck) 을 유발했다.

단계	동작	I/O 발생
①	`INSERT`로 auto_increment ID 생성	쓰기
②	생성된 PK를 조회해 스크램블링 수행	읽기
③	스크램블링 결과를 다시 저장	쓰기

➡️ URL 한 건 생성 시 최대 3회 DB I/O 발생
→ 초당 수천~만 건 단위의 트래픽에서는 심각한 병목으로 작용한다.

또한 App 서버가 여러 대로 확장될 경우
모든 서버가 단일 DB의 auto_increment에 의존하므로
충돌 방지·부하 분산이 불가능하다.

5. KGS 도입 — Segment Allocation 방식

이 문제를 해결하기 위해
Lilling은 Segment Allocation(세그먼트 단위 ID 블록 발급) 방식을 채택했다.

원리

KGS는 DB의 id_generator 테이블을 통해 전역 시퀀스(current_max) 를 관리한다.
App 서버는 KGS로부터 ID 블록(예: 1000개 단위) 을 미리 요청해 캐시에 저장한다.
블록이 소진되면 새로운 블록을 요청한다.
KGS는 SELECT ... FOR UPDATE 트랜잭션 (Pessimistic Lock)을 통해 동시 요청을 직렬화하여 충돌을 완전히 방지한다.

예시

서버	할당 범위	다음 요청 시
App1	1 ~ 1000	3001 ~ 4000
App2	1001 ~ 2000	4001 ~ 5000
App3	2001 ~ 3000	5001 ~ 6000

이 방식으로 App 서버는 대부분의 요청을 로컬 메모리에서 즉시 처리하며,
DB 접근은 블록 재요청 시에만 발생한다.

6. 데이터 흐름

6.1. App 서버 구동 시

/api/v1/key/next-block 호출
DB에서 current_max 읽기 및 +block_size 갱신
{ start, end } 범위 응답
App 서버는 해당 범위를 캐시에 저장

6.2. 단축 URL 생성 시

캐시된 블록에서 nextId() 호출
ID를 스크램블링 후 Base62 인코딩
단축 URL 생성 완료

6.3. 블록 소진 시

자동으로 KGS에 새 블록 요청
DB의 current_max 증가
재시작 후에도 DB 상태에서 이어서 발급 가능

7. 데이터베이스 설계

컬럼명	타입	설명
`name`	VARCHAR(50)	시퀀스 이름 (예: ‘url’)
`current_max`	BIGINT	현재까지 발급된 마지막 ID

8. 결론

기존 auto_increment 기반 방식은
단일 노드 의존으로 인해 매 요청마다 불필요한 DB I/O가 발생했다.

반면 KGS는 Segment Allocation 기반의 전역 ID 발급 구조를 통해
한 번의 DB 접근으로 수천~만 개의 ID 블록을 미리 확보하고,
App 서버는 로컬 캐시에서 즉시 ID를 발급할 수 있게 되었다.