홈페이지 > MongoDB > The Data Structure of MongoDB (3)

The Data Structure of MongoDB (3)

Pinterest

글 : 이승용

 

이번에는 MongoDB 데이터 구조 연재 내용 중 세번째로 MongoDB의 인덱스 저장 구조에 대해 알아본다. MongoDB의 인덱스는 다른 NoSQL 보다 확장성과 유연성이 강력한 기능 중 하나이다. 하지만, 많은 장점에도 불구하고, 사용하면서 인덱스의 성능에 많은 의문점을 품은 개발자들도 많을 것이다. 이러한 의문점을 해결하는 방법은 MongoDB가 어떠한 형식으로 인덱스를 정의하고 구현하였는지 확인하는 것이 가장 좋은 해결책일 것이다. 이번 글에서는 조금이나 이러한 의문점을 해소시켜 줄 MongoDB 인덱스 구조에 대해서 알아본다.

 

MongoDB 인덱스 구조

 

모든 데이터베이스 시스템과 동일하게 MongoDB의 인덱스는 역시 B-TREE로 구현되어 있다. 일반적으로 우리는 자료구조 시간에 B-TREE의 구현에서 B-TREE 한 노드가 한 개의 데이터를 가지고 있는 방식으로 공부하였다. 하지만, B-TREE 한 노드에 한 개의 데이터를 저장하는 방식은 데이터를 저장하는 공간보다 B-TREE를 구성하는 링크가 데이터 보다 더 많은 저장공간을 차지하는 비정상적인 구조가 된다. 따라서, 실질적인 B-TREE를 이용한 데이터 관리는 MongoDB가 사용하는 방식처럼, B-TREE 노드에 한 개의 데이터가 아닌 복수개의 데이터를 저장하는 버켓BUCKET이라는 데이터 저장소를 사용한다.

[그림 1] (a)한 개의 데이터를 가지는 B-TREE (b)복수개의 데이터를 가지는 버켓 구조의 B-TREE

[그림 1] (a)한 개의 데이터를 가지는 B-TREE (b)복수개의 데이터를 가지는 버켓 구조의 B-TREE

 

[그림 1]에서 보는 것과 같이 (a)는 한 개의 데이터를 저장하고 있는 B-TREE를 보여주고 있고, (b)는 복수개의 데이터를 가지고 있는 B-TREE를 보여준다. 이 두 개의 B-TREE는 각기 장단점을 가지고 있다. (a)는 데이터의 삽입/삭제/검색 속도가 빠른 반면, 한 개의 데이터를 저장하기 위해 두 개의 링크 정보가 필요하다. 반면 (b)는 삭제에 따른 단편화 증상이 발생되고, 삽입되는 위치 설정과 검색이 (a)보다 느리다. 하지만, B-TREE를 구성하기 위한 링크 정보 저장공간이 (a)보다 작다는 장점을 가진다.

MongoDB에서 버켓이라는 메모리 블록을 사용하는 이유를 살펴보면, 대용량 데이터를 효율적으로 관리하기 위해 마치 해쉬hash 기법의 메모리 구성을 응용한 것과 같다. 근접한 키 값을 가지는 데이터를 한 버켓에 배치 함으로써 B-TREE를 구성하기 위해 들어가는 링크 주소 영역을 줄일 수 있고, 또한 검색을 위한 깊이deep를 줄일 수 있다는 장점이 있다. 하지만, 모든 데이터가 B-TREE로 구성된 것이 아니기 때문에, 버켓 안에 포함된 데이터를 검색하기 위한 순차 루프는 필요하게 된다.

[그림 2] MongoDB의 B-TREE 구조

[그림 2] MongoDB의 B-TREE 구조

 

[그림 2]는 MongoDB의 인덱스 버켓 구조를 보여준다. [그림 2]를 살펴보면 Version 0과 1이 존재하는 것을 볼 수 있다. Version 0과 1은 2010년 4월을 기준으로 이전 인덱스 구조를 Version 0로 표기하고, 이후 버전에는 Version 1 구조를 사용하고 있다. MongoDB에서 Version 0와 1 두 개의 구조를 공존하는 이유는 2010년 4월 이전에 사용되는 데이터 파일에 대한 호환성을 위해서이다.

Version 0와 1의 가장 큰 차이점은 Version 0에서 문제시 되던 인덱스의 메모리 크기와 관련 있다. Version 1은 Version 0의 B-TREE 노드의 헤더 영역과 인덱스의 데이터를 저장하기 위해 BSON 객체를 직접 쓰던 방식에서 헤더 영역의 불필요한 영역을 삭제하고, 인덱스 데이터를 BSON 객체가 아닌 데이터를 직접 저장하는 방법으로 메모리 효율성을 증가시켰다. 하지만, 버켓을 이용하는 기본 알고리즘은 변경되지 않았기 때문에, 메모리 효율성을 제외한 성능적인 이슈는 없다.

 MongoDB에서 사용하고 있는 위치 정보(Parent Bucket, Next Bucket, Record Location, PrevBucket)인 DiskLoc 구조체는 총 8바이트의 구조를 가지고 있지만, 인덱스 Version 1의 위치 정보는 7바이트로 구성한 위치 정보 구조체를 사용한다. 8바이트 DiskLoc의 상위 4바이트인 볼륨 정보를 3바이트만 사용하는 것으로, Version 1의 볼륨의 최대 크기는 16진수로 0xFFFFFF까지만 가능하다. 만약 3바이트 영역을 벗어나는 경우는 인덱스의 크기를 벗어난다고 할 수 있다.[1]

[표 1] MongoDB인덱스 버켓의 헤더 구조

필드명

Version 0 크기

Version 1 크기

 

Parent Bucket

8

7

B-TREE 노드의 부모 노드의 위치 정보

Next Bucket

8

7

B-TREE 노드의 오른쪽 노드의 위치 정보

Size

2

X

버켓의 크기로 8192 값으로 고정되어 있음. Version 0에서만 사용되는 필드

Flags

4

2

‘Packed’ 상태만 설정할 수 있으며, Packed 상태는 1의 값을 가진다.

Empty Size

4

2

버켓에서 사용하지 않는 공간의 크기

Top Size

4

2

버켓에서 사용하고 있는 공간의 크기

Keys Number

4

2

버켓에 저장된 키의 개수

[표 1]은 인덱스 버켓의 헤더 구조를 보여준다. Version 0에서는 예약 영역을 포함하여 총 40바이트의 헤더를 가지고 있고, Version 1에서는 22바이트의 크기를 가진다. 버켓의 크기는 Version 0에서는 8192바이트의 크기를 가지고 있고, Version 1에서는 8192바이트에서 16바이트를 제외한 8176바이트를 가진다.[2] 또한 Version 0는 최대 저장할 수 있는 키의 개수를 812개로 설정하고 있으며, Version 1은 1024개의 키 값을 가질 수 있도록 설정하고 있다. 최대 키 값의 개수는 한 버켓 안에 들어갈 수 있는 최대 키의 개수이다. Version 0과 Version 1의 버켓 크기가 16바이트 차이임에도 불구하고 최대 저장할 수 있는 키의 개수가 차이가 나는 이유는 BSON 객체를 직접 저장하는 방법과 데이터를 직접 저장하는 방법의 차이점에서 나타난다. 즉, BSON 객체로 키 값을 저장할 경우, BSON 객체가 포함하는 정보가 있기 때문에 BSON 객체의 헤더 정보로 인해 버켓 안에 많은 키를 저장하는 것은 힘들기 때문이다. 따라서, Version 1에서는 인덱스 정보의 효율성을 위해 BSON 객체보다 직접 데이터를 저장하는 방식을 채택하고 있다.

[표 1]의 flags 필드는 인덱스 버켓 안에 데이터 삭제로 인해 사용하지 않는 공간이 있을 경우, 이를 정리하는 옵션인 ‘Packed’를 설정할 수 있다. Packed 옵션이 설정되어 있다면, 인덱스 버켓에 사용하지 않는 공간이 있다는 것을 의미한다. 만약 버켓의 빈 공간을 재활용 할 수 있도록 재정렬하였다면 플래그의 Packed 옵션은 초기화 된다. 버켓을 이용한 B-TREE를 구현한 시스템의 단점으로 단편화 증상을 말하였다. 만약, 데이터의 삽입이 지워진 부분에 다시 삽입이 된다면(삭제된 키를 재 활용한다면) 단편화 증상이 없어질 수 있지만, 이러한 삭제 공간의 재활용은 쉽지 않다. 따라서, 일반 데이터베이스와 마찬가지로 MongoDB 역시 인덱스를 재정렬할 수 있는 기능을 가지고 있다.

[그림 2]의 Key Node는 고정된 크기의 배열과 같은 존재로 버켓 안에서 키 값이 저장된 위치와 도큐멘트의 위치, 그리고 B-TREE의 왼쪽 버켓의 위치를 저장하고 있다. [표 2]는 인덱스 버켓의 Key Node 구조를 설명한다.

[표 2] 인덱스 버켓의 Key Node 구조

필드명

Version 0 크기

Version 1 크기

 

Prev Bucket

8

7

B-TREE 노드의 왼쪽 노드의 위치 정보

Record Location

8

7

해당 키가 가리키는 도큐멘트의 위치 정보

Key Position

2

2

버켓 안에 저장된 키 값의 위치

[그림 2]의 Key Object는 실질적인 키 값(데이터)을 저장하고 있는 것으로, 가변 길이의 데이터를 저장한다.[3] MongoDB는 가변길이 키 값을 저장하기 위해 고정 크기의 Key Node를 앞에 배치하고, 그 뒤에 키 값을 저장하는 Key Object를 배치하는 방법을 사용한다. 키 값은 Version 0에서는 BSON 객체 형식으로 저장하고 있지만, Version 1에서는 보다 많은 데이터를 버켓에 저장하기 위해 BSON 객체보다 실질적인 데이터만 저장하는 방식을 사용하고, 사용하고 이를 Element Data라고 정의하고 있다. 그렇다고, Version 1에서 Version 0이 사용하던 BSON 형식을 완전히 제거한 것은 아니다. 첫 번째 바이트를 IsBSON 타입으로 설정하여 0xFF의 값을 가지면 BSON 객체로 사용하고, 0xFF가 아니면 값 데이터를 직접 저장하는 방식으로 정의하고 있다.

Version 1이 사용하는 Element Data 형식은 첫 번째 바이트를 데이터 타입으로 설정한다. 데이터 타입은 [표 3]과 같다. 데이터 타입 바이트의 하위 4비트만을 사용하며, 데이터 형식 중 가변 데이터 형식은 cstring과 cbindata로 두 가지 유형을 정의하고 있다. [그림 3]은 Element Data의 구조를 보여준다.

 [표 3] Version 1의 Key Object의 Element Data 타입

타입

길이[4]

기타

cminkey

1

1

Cnull

2

1

cdouble

4

9

cstring

6

가변

타입 바이트 이후 1바이트가 문자열 길이를 저장한다. 따라서 문자열의 크기는 256바이트를 초과할 수 없다.

cbindata

7

가변

타입 바이트 이후 1바이트가 이진 데이터의 크기를 나타내는데 최대 크기가 32바이트를 초과하지 않는다.

coid

8

13

cfalse

10

1

ctrue

11

1

cdate

12

9

cmaxkey

14

1

[그림 3] Element Data 구조

[그림 3] Element Data 구조

Element Data의 cbindata 타입은 cstring 타입과는 달리 이진 데이터 크기가 아래와 같이 정의되어 있다. [그림 3]의 size 필드의 값에서 하위 4비트를 이진 데이터 유형으로 정의하고 상위 4비트를 크기로 정의하고 있다. 크기는 상수 값 BinDataCodeToLength 배열에 정의되어 최대 32바이트 값을 가진다.
const int BinDataCodeToLength[] =
{
    0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16, 20, 24, 32
};
int binDataCodeToLength(int codeByte)
{
    return BinDataCodeToLength[codeByte >> 4];
}

하위 4비트의 이진 데이터 타입은 다음과 같이 정의되어 있다.

enum BinDataType {
  BinDataGeneral = 0,
  Function = 1,
  ByteArrayDeprecated = 2,/* use BinGeneral instead */
  bdtUUID = 3,       /* deprecated */
  newUUID = 4,       /* language-independent UUID format across all drivers */
  MD5Type = 5,
  bdtCustom = 128
};

MongoDB의 인덱스는 다른 NoSQL과 달리 많은 인덱스를 설정할 수 있는 장점과 함께 복합 인덱스와 같은 유연한 특성을 가진다. 그리고, 빠른 데이터 검색을 제공하기 때문에, MongoDB의 인덱스는 많은 사람들에게 주목 받는 기능 중의 하나이다. 하지만, MongoDB의 인덱스를 사용하기 위해서는 충분한 이해가 필요하다. 앞에서 살펴본 봐와 같이 인덱스 버켓에 키 값(데이터)을 저장하기 때문에, 도큐멘트에 저장된 데이터와 중복 저장된다는 점과 함께, 빠른 인덱스 검색을 위한 입출력 기술이 별도로 구현된 것이 아니라, 운영체제가 제공하고 있는 Page Fault를 방식을 같이 사용하기 때문에, 메모리가 부족한 시스템에서는 오히려 검색 속도를 저하시키는 단점이 되기도 한다. 최악의 경우는 인덱스와 도큐멘트가 모두 메모리에 로드 되지 않았을 경우는, 한 개의 도큐멘트를 찾기 위해 두 번의 Page Fault가 발생할 수 있다. 즉, 적은 메모리를 사용할 경우는 인덱스를 설정하지 않는 것이 오히려 검색 시간을 줄일 수 있다.

MongoDB의 인덱스를 사용할 때는 다음의 사항을 고려하자.

  • 인덱스를 메모리에 로그할 수 있을 정도의 충분한 메모리를 가지고 있는가?
  • 인덱스를 설정한 데이터만으로 질의가 가능한가?

앞에서도 논하였지만, MongoDB의 인덱스는 키 데이터를 포함한 버켓 구조이다. 따라서, 해당 키 값만으로 질의를 수행한다면, 불필요한 도큐멘트의 로드가 필요없게 되므로, 검색과 결과가 동시에 수행되기 때문에 빠른 검색을 가능하다. 하지만, 반대로 인덱스 필드를 검색하여 도큐멘트의 다른 필드를 질의하는 경우라면 두 번의 메모리 액세스가 발생한다는 점에 주의하자.

 


[1] 총 7바이트는 2진수 256이므로 72,057,594,037,927,936 크기만큼 저장이 가능하다.

[2] Version 1에서 16바이트 모자라는 8KB인 이유는 버켓이 저장되어 있는 DiskLoc 위치를 같이 저장하는 여유 공간을 설정하기 위해서이다.

[3] 문자열을 인덱스로 선택하였다면 쉽게 이해될 것이다.

[4] 길이는 타입을 나타내는 1바이트를 포함한 크기이다. cdouble의 9바이트는 타입 1바이트와 double형 8바이트를 합한 크기를 말한다.


  • Facebook
  • Twitter
  • Delicious
  • LinkedIn
  • StumbleUpon
  • Add to favorites
  • Email
  • RSS
Categories: MongoDB Tags:
  1. 아직 댓글이 없습니다.
  1. 엮인글들이 아직 없습니다.