URL 단축 방식 - LeeEuyJoon/lilling-be GitHub Wiki
1. 개요
Lilling 은 대규모 URL 단축 서비스로,
짧은 URL을 충돌 없이, 예측 불가능하게, 그리고 가역적으로 생성하는 데 초점을 맞추고 있다.
본 문서는
긴 URL을 짧은 URL로 변환하는 과정을 설계·개선해 온 전 과정을 기술한다.
🎯 설계 목표
- 초당 약 1,000건의 쓰기 요청, 10,000건의 읽기 요청을
10년간 안정적으로 처리할 수 있는 고가용 URL Shortener 시스템 구축 - 고유성(Uniqueness), 예측 불가능성(Unpredictability),
**가역성(Reversibility)**을 모두 만족하는 단축 URL 변환 파이프라인 구현
2. Base-62 공간 계산
짧은 URL을 위해 사용되는 문자 집합은 다음과 같다.
| 항목 | 값 |
|---|---|
| 문자 집합 | 0–9, a–z, A–Z (총 62개) |
| 일일 생성량 | 1억 개 |
| 10년간 총량 | 1억 × 365 × 10 = 3,650억 개 |
| 필요한 조합 수 | ≥ 3,650억 |
이를 만족하는 최소 자릿수 n은 다음 조건을 따른다.
62^n > 365,000,000,000
- 62⁶ = 568억 → 부족
- 62⁷ = 3조 5,216억 → 충분
✅ 결론:
7자리 Base62로 10년치(3,650억 개)를 안정적으로 커버 가능.
(이론상 약 111년치까지 커버 가능)
3. 변환 로직의 발전 과정
3.1. 1단계 — 순차값 직접 변환 (Naive Sequential Encoding)
가장 단순한 구현은 순차 ID를 62진수로 변환하는 방식이었다.
| ID | Base62 | Short URL |
|---|---|---|
| 1 | 1 | https://lill.ing/1 |
| 2 | 2 | https://lill.ing/2 |
| 36 | a | https://lill.ing/a |
| 37 | b | https://lill.ing/b |
❌ 문제점
- URL 패턴이 그대로 노출됨
- 공격자가 순차적 접근으로 데이터를 예측 가능
- 보안 취약
3.2. 2단계 — 선형식 기반 스크램블링 (Linear Mapping)
순차 패턴을 숨기기 위해 선형 변환식을 이용한 스크램블링을 적용했다.
encoded_id = (A × id + B) mod M
| 항목 | 설명 |
|---|---|
id |
KGS(Key Generation Service)가 발급한 순차 정수 |
A, B |
상수 (A는 M과 서로소) |
M |
62⁷ (≈ 3.52조) |
A와 M이 서로소이면, (A × id + B) mod M은 전체 0~M-1 공간을
중복 없이 순회하므로 고유성은 수학적으로 보장된다.
(1) 작은 상수 조합 실험
- A = 13, B = 17
| ID | (A×id + B) mod M | Base62 | Short URL |
|---|---|---|---|
| 1 | 30 | U | /U |
| 2 | 43 | h | /h |
| 3 | 56 | 1E | /1E |
| 36 | 485 | 8t | /8t |
| 37 | 498 | 8E | /8E |
➡️ 결과: 단조로운 증가 패턴 일부 완화
❌ 한계: 여전히 일정한 간격의 선형 패턴 유지
(2) 대형 상수 조합 실험
- A = 56,800,235,583, B = 916,132,831
| ID | Encoded_ID | Base62 | Short URL |
|---|---|---|---|
| 1 | 57,716,368,414 | 10zzzzy | /10zzzzy |
| 2 | 114,516,603,997 | 20zzzzx | /20zzzzx |
| 3 | 171,316,839,580 | 30zzzzw | /30zzzzw |
| 36 | 2,077,789,318,449 | V0zzzU | /V0zzzU |
| 37 | 2,134,589,554,032 | W0zzzT | /W0zzzT |
➡️ 결과: 단조성은 완화되지만 규칙성은 여전히 존재
아무리 큰 상수를 사용해도 본질적 선형성은 깨지지 않는다.
3.3. 3단계 — 지수함수 기반 고려 (Exponential Function)
선형 함수의 일정한 기울기 문제를 해결하기 위해
증가율이 달라지는 **지수함수적 스크램블링(y = eˣ 형태)**을 검토하였다.
그러나 이는 이론 검토 단계에서 즉시 폐기되었다.
❌ 폐기 사유
- 출력값이 너무 빠르게 증가 → M(3.5조)을 쉽게 초과
id = 10⁹일 때 이미 10²⁰ 이상으로 폭증- 정수 도메인 내에서 안정적인
mod M매핑 불가능- 연산 복잡도 증가, 오버플로 위험 존재
➡️ 결론:
지수함수 기반 스크램블링은 실용적이지 않음 → 도입하지 않음.
3.4. 4단계 — XORShift 기반 비트 난독화 (Non-linear Bit Scrambling)
비선형성을 도입하기 위해
비트 수준에서 완전히 섞는 연산인 XORShift를 사용했다.
x ^= (x << 13);
x ^= (x >>> 7);
x ^= (x << 17);
🔍 XORShift 원리 (Marsaglia, 2003)
단순한 XOR과 Shift 연산만으로 전체 비트 공간을 완전한 순열(permutation)로 섞을 수 있다.
(13, 7, 17)조합은 Full-rank Transformation을 구성한다.
✅ 특징 요약
| 항목 | 설명 |
|---|---|
| 비선형성 확보 | 비트 수준에서 완전 혼합 |
| 가역성 | XOR은 자기 역원 → 동일 연산으로 복원 가능 |
| 속도 | 단순 비트 연산만 수행 |
⚠️ 단점 – 도메인 불일치 문제
- XORShift는 64비트 전체 공간(2⁶⁴)을 대상으로 완전 순열을 구성
- 그러나 Lilling의 도메인은 M=62⁷ (3.5조)로 훨씬 작음
mod M으로 축소 시, 충돌 발생 가능- 즉, “비트 수준 가역성”은 유지되지만 “도메인 수준 가역성”은 깨짐
➡️ 비선형성은 확보했지만,
도메인 안정성과 완전한 역변환 가능성은 손실됨.
3.5. 5단계 — Feistel Network + XORShift F 함수 (최종 채택)
최종적으로 Feistel Network를 도입하였다.
이 구조는 **“가역적인 비선형 매핑”**을 구현하기 위한 대표적인 방법이다.
(1) 설계 원리
Feistel 구조는 입력값을 좌우 두 부분으로 나누고,
비선형 함수 F를 반복 적용하면서 **양방향 복원 가능한 순열(permutation)**을 형성한다.
입력값 id → [L0, R0] 분리
L1 = R0
R1 = (L0 + F(R0)) mod m
- 각 라운드는 덧셈(
mod m) 기반 → 도메인 안정성 유지 - F(x)는 XORShift 기반 비선형 함수
- 라운드 반복 시 입력 전체가 균등하게 섞이며 비선형 분포 형성
(2) F 함수 정의
F(x):
x ^= (x << 13);
x ^= (x >>> 7);
x ^= (x << 17);
return x mod m;
- F는 비가역적이어도 무방 (Feistel이 전체 가역성을 보장)
- mod m을 통해 각 반쪽의 범위를 제한
(3) 가역성 증명
Feistel의 가역성은 다음과 같은 원리로 보장된다.
| 라운드 단계 | Forward 변환 | Inverse 변환 |
|---|---|---|
| 1 | L₁ = R₀ | R₁ = (L₀ + F(R₀)) mod m |
| 2 | R₀ = L₁ | L₀ = (R₁ - F(L₁)) mod m |
즉, 각 라운드는 단순한 덧셈과 F 함수로 구성되어 있으므로
역방향에서도 동일한 연산을 반대로 수행하면 원본을 완벽히 복원할 수 있다.
✅ 결론:
Feistel 구조는 수학적으로 가역적(perfectly reversible) 이다.
모든 입력에 대해 1:1 대응을 이루며,
어떤 라운드 수도 동일한 함수로 복원 가능하다.
(4) Cycle-walking (범위 보정)
Feistel 결과가 M을 초과할 수 있으므로,
출력값이 M 미만이 될 때까지 반복 수행한다.
이 과정을 Cycle-walking이라 하며,
대부분의 경우 한 번의 순환으로 충분하다.
(5) 결과 요약
| 항목 | 설명 |
|---|---|
| 비선형성 확보 | XORShift F 함수 적용 |
| 가역성 확보 | Feistel 구조의 수학적 역함수 존재 |
| 도메인 안정성 유지 | mod m을 통한 공간 제한 |
| 균등 분포 | 라운드 반복에 의한 엔트로피 확산 |
✅ 결론:
Feistel + XORShift F 함수 구조는
비선형성, 가역성, 도메인 안정성을 모두 만족하는 완전 순열을 형성한다.
4. 최종 변환 파이프라인
1️⃣ 순차 ID 발급 (KGS)
↓
2️⃣ Feistel Scrambling (Additive + XORShift F)
↓
3️⃣ Cycle-walking (M 범위 내 보정)
↓
4️⃣ Base62 인코딩 (7자리)
↓
5️⃣ Short URL 반환 (https://lill.ing/{code})
5. 결론
Lilling의 단축 URL 생성 로직은
“Feistel Network 기반 스크램블링” 을 구현함으로써,
3.5조 개의 ID를 충돌 없이, 예측 불가능하게, 복원 가능하게 매핑한다.
이 최종 설계는
단순한 선형 변환을 넘어 비트 수준의 난독화와 암호학적 가역성을 결합한 구조로,
대규모 URL Shortener 시스템의 근간을 형성한다.
📑 관련 작성글
고유하면서도 랜덤한 7자리 인코딩을 찾아가는 여정 // Base62, 선형식, XORShift, Feistel Cipher