URL Shortener - DB 인덱스

URL Shortener란?

URL Shortener(단축 URL)은 길이가 긴 URL을 짧은 형태로 줄여서, 유저가 짧은 링크를 누르면 원본 URL로 리다이렉트되는 서비스다.
SMS을 전송하거나 SNS을 이용할 때 글자 수 제한에 걸리지 않고, 링크 공유가 쉽다는 장점이 있다.

 

중복 허용 vs 비허용

단축 URL을 설계할 때 제일 먼저 결정해야 했던 문제가 "동일한 원본 URL에 대해 동일한 단축 URL을 제공할 것인지"였다.

원본 URL의 중복을 허용하는 대표적인 서비스는 bit.ly 에서 비로그인 시 제공하는 서비스다.
아래 그림처럼 동일한 URL을 여러 번 입력할 때마다 다른 단축 URL을 제공한다.

원본 URL 중복 허용

반면에 bit.ly에서 로그인을 한 유저는 하나의 URL에 대해 하나의 단축 URL만 가질 수 있다 (원본 URL 중복 비허용)
해당 링크를 클릭했을 때 Referrer, Location, Clicks 등의 통계를 받을 수 있고, 로그인 한 유저는 이 정보를 가공해서 사용할 수 있다. (for 마케팅, 광고...)

원본 URL 중복 비허용

통계 산출 외에 중복 비허용의 장점은 데이터 저장량이 적다는 것이다. naver.com을 10만 번 요청할 때 10만 건이 아니라 1건만 쌓인다. 하지만 중복 여부 확인을 위해 추가 연산이 필요하다.

• 단축 URL 링크 클릭 : DB에 해당 데이터가 있는지 찾고, 매칭되는 원본 URL을 응답한다.
• 원본 URL 입력 : DB에 해당 데이터가 있는지 찾고, 있으면 매칭되는 단축 URL을 응답하고, 아니면 새로운 단축 URL을 생성 후 응답한다.

10만 건을 저장하기 위해 DB 저장공간을 제공할 것인지 vs 추가 연산에 따르는 CPU 부하를 감수할 것인지 사이에서 적절한 선택을 해야한다. 같은 맥락에서 DB를 설계할 때에도 DB index라는 기술을 적절하게 사용해야 한다.

 

---

DB Index

책은 키워드를 빨리 찾기 위해 목차나 색인을 제공한다. 색인이 없으면 원하는 키워드를 찾기 위해 책을 1페이지부터 읽어야 한다. 색인이 있으면 키워드를 빨리 찾을 수 있지만 책 내용이 바뀔 때마다 색인에도 작업이 필요하고 + 책에 색인을 위한 페이지가 따로 필요하다.

인덱스는 색인이다.
DB에서 데이터를 빨리 찾기 위해 인덱스가 존재한다. 인덱스가 없으면 원하는 데이터를 찾을 때 Table Full Scan이 일어난다. 인덱스가 있으면 SELECT는 빠르지만 INSERT, UPDATE, DELETE 에서 추가 연산이 필요하고 + 추가적인 데이터 용량이 필요하다.

모든 DBMS는 원하는 데이터를 쉽고 빨리 찾기 위해 나름의 다양한 인덱스를 제공한다. 저장방식과 구조, 탐색 알고리즘이 조금씩 다르긴 해도 근본적인 목적은 같다. 이 글에서는 MySQL 8.0의 기본 스토리지 엔진인 innoDB의 B+Tree 구조를 기준으로 인덱스를 설명할 것이다.

Clustered Index

innoDB의 모든 테이블에는 Clustered Index가 존재한다.

• PK(Primary Key)는 항상 Clustered Index다.
• PK가 없다면, NOT NULL 속성의 Unique Key 중 첫번 째 UK가 Clustered Index
• 후보가 없으면 innoDB 자체에서 히든 필드을 생성해 Clustered Index로 사용

이처럼 테이블에는 항상 Clustered Index가 있고, 테이블에 단 한 개만 생성할 수 있다. 데이터와 무리를 이루고(clustered) 있기 때문에, 이 인덱스로 데이터를 읽을 때 가장 속도가 빠르다. 간단한 B+Tree 구조로 확인해보자

 

• 정렬된 인덱스 트리에서 원하는 인덱스를 찾아가면 데이터 블록 안에 데이터 주소가 있다. (Key: PK, Value : 데이터 주소)
• 인덱스가 정렬된 상태에서 탐색하기 때문에 → select 속도가 빠르다.
• 인덱스가 정렬되어야 하기 때문에 → insert, update, delete 마다 인덱스를 재정렬하는 작업이 추가된다.

 

Non-Clustered Index

Clustered Index 외의 모든 인덱스를 Non-Clustered Index, innoDB에서는 Secondary Index(보조 인덱스)라고 한다.
테이블 당 여러개의 보조 인덱스가 존재할 수 있고, 데이터와 연결되어 있지 않다. (무리를 이루고 있지 않다, non-clustered)

 

• 인덱스를 타고 가면 PK가 있다. (Key: 보조 인덱스, Value: PK)
• 이 PK를 가지고 다시 오른쪽 트리를 타서 데이터 주소를 찾는다.
• 트리를 두 번 타기 때문에 PK를 이용한 검색보다는 느리지만, Table Full Scan보다 빠르다.

 

 

▼B+Tree 구조 설명

https://ducmanhphan.github.io/2020-04-12-Understanding-about-clustered-index-in-RDBMS/

 

데이터 블록(페이지)

• 디스크에 데이터를 저장하는 기본 단위를 데이터 블록(innoDB에서는 페이지라고 부른다)이라고 하고, 디스크의 모든 읽기 및 쓰기의 최소 작업 단위가 된다. 페이지 단위로 I/O를 한다는 건 하나의 레코드에서 하나의 필드만 읽고 싶을 때도 레코드가 속한 페이지 전체를 읽어야 함을 의미한다.
• 인덱스 또한 페이지 단위로 관리되고, B+Tree 구조의 노드도 페이지 단위로 구분된다.
• (위 그림에서 주황색 노드가 페이지다)

 

B+Tree

• Leaf 노드부터 데이터가 쌓이고, 노드(페이지)가 꽉 차면 형제 노드와 부모 노드가 생성된다.
• Leaf 노드에만 Value로 데이터 주소가 있다. Root와 Branch(Intermediate)의 Value는 하위 페이지 주소다. 하위 노드들의 인덱스가 어떤 페이지에 있는지를 나타낸다. 
• Leaf 노드끼리는 Double Linked List로 연결되어 있다.
• 인덱스 탐색은 생성과 반대로, Root -> Intermdiate(Branch) -> Leaf  순으로 진행된다.
• 보통 트리의 depth는 3정도, 아무리 데이터가 커도 4~5는 넘지 않는다고 한다.

 

인덱스 부여 시 write가 오래 걸리는 이유

• 페이지가 나눠지고 쪼개지면서 인덱스 재정렬이 일어나기 때문이다.
• insert : 기존 페이지에 여유가 없을 때 새로운 데이터가 입력되면, 새로운 페이지가 생기고 데이터를 옮기는 작업이 수행된다. 새 페이지 앞뒤로 링크가 연결된다. (split)
• delete : 테이블에서 데이터를 지울 땐 다른 데이터가 그 공간을 사용가능하지만, 인덱스의 경우 데이터를 지우지 않고 "인덱스 사용 안 함" flag를 부여한다. "인덱스 사용 안 함"이 많아지면 페이지가 합쳐진다. 페이지 앞뒤로 연결된 링크를 제거한다.  (merge)
• update : delete + insert

 

더 자세한 B+Tree 구조와 원리는 아래 링크들을 참고하자

인덱스 기본 원리

MySQL InnoDB Sorted Index Builds
InnoDB Page Merging and Page Splitting

 

B+Tree 외의 자료 구조들은??

DB 인덱스(INDEX) 자료구조

 

 

필드에 인덱스를 부여할 때마다 새로운 삼각형, B+Tree가 필요하고 인덱스마다 DB의 약 10%에 해당하는 저장공간이 사용된다고 한다. read가 빠르다고 모든 필드에 보조 인덱스를 걸면, write마다 인덱스를 전부 관리해야 돼서 오히려 느려진다. 또한 인덱스도 공간을 차지하기 때문에 저장공간도 고려해야 한다. 그러면 어떤 필드에 인덱스를 걸면 좋을까?

인덱스 필드를 선정할 때 기준으로 카디널리티(Cardinalilty)가 있다. '유니크한 정도'로 생각하면 된다.
(카디널리티가 높다 = 유니크함이 높다 = 중복이 적다)

• 주민등록번호, 계좌번호 : 유일하다 = 카디널리티가 높다 = 해당 인덱스로 대부분을 부분을 걸러낼 수 있다
• 성별, 학년 : 중복되는 데이터가 많다 = 카디널리티가 낮다 = 해당 인덱스로 많이 걸러내지 못한다

조회 시 선택되는 데이터가 많아질수록 full scan에 가까워지기 때문에 최대한 많은 데이터가 걸러져야 성능이 좋다. 따라서 카디널리티가 높은 필드를 인덱스로 걸고, 여러 필드로 인덱스를 잡을 때에도 카디널리티가 높은 순에서 낮은 순으로 구성하는 게 좋다.
하지만 카디널리티는 참고용으로 사용하는 하나의 지표일 뿐이다. 해당 필드에 업데이트가 얼마나 빈번하게 일어나는지, where 절에서 얼마나 자주 사용하는지, 카디널리티는 어떤지 등 여러가지를 고려해서 인덱스를 설정해야 한다.

 

 

▼ 실제 MySQL 에서 인덱스 부여에 따라 시간 비교

 

 

데이터 100만 건으로 PK 와 보조 인덱스 부여에 따라 select, insert, delete, update 시간을 비교해보자.

비교 조건을 동일하게 하기 위해 id와 choo는 동일한 값을 갖는다.

(더미 데이터 출처 : https://www.youtube.com/watch?v=JEKIuxTd_FE) 

데이터 100만 건	User1 테이블	User2 테이블	User3 테이블
PK, 보조 인덱스 여부	PK, 보조 인덱스 지정 안함	id(PK) 지정	id(PK) 지정 choo(보조 인덱스) 지정
입력 시간	7.74 sec	17.67 sec	1 min 30.17 sec
테이블 사이즈	83 MB	124 MB	184 MB
PK로 조회	0.54 sec	0.04 sec	0.03 sec
보조 인덱스로 조회 (choo)	0.54 sec	0.33 sec	0.07 sec
일반 필드로 조회 (name)	0.53 sec	0.32 sec	0.31 sec
데이터 삭제	0.56sec	0.69sec	0.69sec

 

1. 인덱스 개수가 많을수록 입력 시간이 길고, 테이블 사이즈가 크다

2. PK가 지정된 상태에서 PK로 조회할 때 가장 빠르다

3. 조회 시간은 PK, 보조 인덱스, 일반 필드 순으로 빠르다

4. 인덱스가 있으면 데이터 삭제가 느리다.

---

다시 URL Shortener로 돌아와서 인덱스를 생각해보면

• 가장 속도가 빠른 PK를 최대한 이용하자
• 단축 URL 링크 클릭 : DB에 해당 데이터가 있는지 찾고, 매칭되는 원본 URL을 응답한다.
  • 단축 URL로 조회를 하기 때문에, 단축 URL에 인덱스를 걸어주는 것이 좋다.
• 원본 URL 입력 : DB에 해당 데이터가 있는지 찾고, 있으면 매칭되는 단축 URL을 응답하고, 아니면 새로운 단축 URL을 생성 후 응답한다.
  • 하지만 원본 URL에 인덱스를 걸거나 Unique를 걸면 확인을 위해 엄청난 String Compare 비용 발생
  • 또한 DB에서 직접 원본 URL으로 조회할 때도 String Compare 비용 발생
  • 따라서 서버단에서 원본 URL을 단축 URL로 바꾸고, 원본 URL이 아니라 단축 URL로 DB를 조회하는 것이 바람직하다.

결론 : 단축 URL에 인덱스(PK)를 걸어서 [원본] [단축] 필드로 DB를 설계한다.