개요

전체 데이터를 조회하는 서비스

팀 프로젝트 진행 중, 전체 데이터에서 랜덤한 데이터를 중복없이 불러오는 기능을 담당하게 됐다.

날짜순으로 정렬된 데이터에서 최신 순으로 페이지네이션 해본 경험은 있었어도, 랜덤한 데이터를 중복없이 불러오는 것을 전체 데이터상에서 불러오는 경험은 없었기 때문에 해당 기능을 구현하는데 많은 고민이 필요했다.

디비에서의 검색 성능 기능 개선을 위해선 인덱스 적용과 페이지네이션 기법이라는 게 있다는 걸 알고 있었는데,
정확하게 알고 있다곤 하기 힘들어서 이를 개선하고자 해당 개념에 대해 다시 한 번 정리해본 후, 실험을 진행해보기로 했다.

왜 굳이 랜덤하게 전체 데이터를 가져와야 하나?

이번 프로젝트는 기획 자체가 상업적인 사이트가 아니라, 유저들의 데이터를 바탕으로 생성한 3D작품을 전시하는 전시회장이다.

만약 적극적으로 데이터를 수집하는 상업적인 목적의 서비스였다면, 최신의 데이터를 기준으로 정렬하는 것이 적절하나 (상단에 노출되기 위해 적극적으로 글을 쓸 것이기 때문에),
노출 빈도는 모두에게 공평하게 돌아가야 한다고 생각했고 이로 인해서 랜덤하고 중복이 없게 데이터를 조회하는 기능이 필요해진 것이다.

DB

데이터베이스에서 효율적으로 조회하기 위해선, 데이터베이스에 데이터가 어떻게 저장이 되는 지를 먼저 알아야 한다고 생각한다.

따라서 해당 포스팅에 간략하게나마 이에 관해서 정리하려고 한다.

INDEX

데이터 저장 방식

인덱스에 대해서 알기 위해선 데이터를 저장하는 방식에 대해서 먼저 알아야 한다.
1~10000까지의 정수 값을 메모리에 저장한다고 가정해보자.

Heap

힙은 데이터가 들어오는 순서대로 뒤에 추가한다.

[7,4,2,6,...]의 순서대로 데이터가 들어오면 그대로 데이터가 쌓인다고 생각하면 된다.

따라서 추가에는 O(1)이 걸린다.

그러면 Heap에서 조회를 한다고 생각해보자.
데이터를 저장할 때 아무것도 하지 않았으므로 힙 내에서 특정 데이터를 찾기 위해선 O(N)의 시간이 소요된다.

이는 수정과 삭제도 마찬가지이고, 삭제의 경우 빈 공간이 생겨버린다는 단점이 있다.

Sorted-Heap

정렬 힙은 이진탐색을 하기 위해 데이터를 정렬해서 저장해둔다.

데이터가 들어오는 순서에 상관없이, 저장되는 데이터는 내림차순이거나 오름차순일 것이다.

이때 조회는 O(logN)으로 힙에 비해서 많이 효율적으로 변했으나,
삽입, 수정, 삭제의 경우 전체 데이터를 재정렬해줘야 한다는 단점이 있다.

이처럼 대용량의 데이터를 힙이나 정렬 힙에 모두 담기는 부담스럽기 때문에, Index라는 개념이 등장했다.

정의

Index는 책의 색인처럼, 데이터가 어느 page에 있는 지 알려주는 것이다.

파일은 disk의 단위인 block에 저장되는데, 이 block들의 모음이 바로 page이다.

이때, Index는 보통 B-트리나 B+트리같은 특수한 자료구조로 저장이 되기 때문에 특정 데이터를 Index에서 찾는 시간은 무시해도 될 정도로 빠르다.

따라서 Index를 사용하면 특정 데이터를 탐색하는데 O(1)의 시간이 소요된다고 보면 된다.

Index는 자신을 기준으로 데이터가 정렬됐는지 여부로 Clustered와 Unclustered로 나뉜다.

Clustered-Index

Clustered-Index는 데이터가 자신을 기준으로 정렬된 것을 의미한다.

1~10000의 데이터가 Clustered로 저장되었고, 한 개의 page에 20개의 데이터가 들어간다고 가정하면 다음과 같이 저장된다

page1 : 1...20
page2 : 21...40
...

Unclustered-Index

Unclustered-Index는 데이터가 자신을 기준으로 정렬되지 않았음을 의미한다.

위와 같은 예시를 들면 다음과 같이 저장된다
page1 : 5,457,4,25,57,83,...
page2 : 7,346,34,13,657,...

B-트리

몽고디비에서는 B-tree를 인덱스로 사용한다.

Cardinality

실제로 실험해보자!

조사한 이론을 바탕으로 직접 실험을 통해 최적의 인덱스를 찾아보고자 했다.

실험은 MongoDB에서 제공하는 Compass를 사용하였고,
10만개의 더미 데이터와 100만개의 더미 데이터로 15개의 데이터를 가져오는 쿼리를 각각 실험해봤다.

우리가 계획한 서비스에서는, 각 유저의 대표 갤러리만 탐색하기 때문에 100만을 넘어가는 일은 거의 없을 것이다.
따라서 실험 데이터는 최대 100만개로 충분할 것이라고 생각했다.

데이터에 대한 설명

이번 실험에서 사용하는 User의 컬럼은 두 가지이다.

• seq : 유저가 생성될 때마다 1씩 증가한다. MySQL의 Auto_increment와 비슷하게 동작한다고 보면 된다.
  이번 실험에서만 사용할 예정이고, 실제 구현에는 마지막 수정일로 대체할 것이다.

• randIdx: 0~10까지의 랜덤한 정수 값이고, 유저가 생성될 때마다 랜덤하게 주입된다.

실험 결과

쿼리 실행 시간

데이터 개수	인덱스 설정 X	{seq, randIdx}	{randIdx,seq}
100,000개	72ms	0ms	0ms
1,000,000개	494ms	0ms	0ms

인덱스를 설정한 것과, 인덱스를 설정하지 않은 쿼리의 결과가 눈에 띄게 차이가 난다.

인덱스를 설정하지 않으면 O(N)만큼의 시간이 걸리고,
인덱스를 설정하면 시간 복잡도가 확연히 줄어든다.

이때, 두 복합 인덱스의 결과가 미세하게 다른데, 그 결과는 아래와 같다.

인덱스 탐색 횟수

데이터 개수	{seq, randIdx}	{randIdx,seq}
100,000개	150번	15번
1,000,000개	168번	15번

카디널리티가 높은 컬럼을 앞에 둘 수록 확실히 인덱스를 탐색하는 횟수가 줄어들었다.