MongoDB Internals

글 : 이승용

 

이번에는 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를 보여준다. 이 두 개의 B-TREE는 각기 장단점을 가지고 있다. (a)는 데이터의 삽입/삭제/검색 속도가 빠른 반면, 한 개의 데이터를 저장하기 위해 두 개의 링크 정보가 필요하다. 반면 (b)는 삭제에 따른 단편화 증상이 발생되고, 삽입되는 위치 설정과 검색이 (a)보다 느리다. 하지만, B-TREE를 구성하기 위한 링크 정보 저장공간이 (a)보다 작다는 장점을 가진다.

MongoDB에서 버켓이라는 메모리 블록을 사용하는 이유를 살펴보면, 대용량 데이터를 효율적으로 관리하기 위해 마치 해쉬^hash 기법의 메모리 구성을 응용한 것과 같다. 근접한 키 값을 가지는 데이터를 한 버켓에 배치 함으로써 B-TREE를 구성하기 위해 들어가는 링크 주소 영역을 줄일 수 있고, 또한 검색을 위한 깊이^deep를 줄일 수 있다는 장점이 있다. 하지만, 모든 데이터가 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]

글 : 이승용

 
이번에는 MongoDB 데이터 구조(1)에 이어 두번째로 MongoDB가 데이터를 저장하는 기본 단위인 레코드^record와 레코드들의 그룹핑인 익스텐트^extent 구조에 대해 알아본다. MongoDB의 익스텐드는 자료 구조 관점에서 보면 연결되어 있는 레코드들의 헤더 역할을 수행하는 것 뿐만 아니라, 레코드 데이터를 로컬 스토리지에 저장하기 위한 파일로 처리한다.[1]
 

MongoDB 레코드 구조

MongoDB는 도규멘트^document 로 구성된 데이터를 RDB의 열^row과 같은 개념으로 처리한다. 하지만, MongoDB는 NoSQL의 특징인 RDB와는 달리 스키마^schema 구조를 가지고 있지 않기 때문에 도규멘트에 저장되는 데이터 형식에 구애를 받지 않는다. 즉, RDB는 테이블에 속하는 모든 열이 같은 데이터 형식을 가지고 있어야 하지만, NoSQL은 열에 저장되는 데이터 형식이 상이하여도 문제가 발생되지 않는다.[2]

[그림 1]은 MongoDB의 레코드 구조를 보여준다. 헤더는 총 16바이트 크기를 가지며, 도큐멘트를 BSON 객체 형태로 저장하고 있다. 한가지 주의할 점은 MongoDB가 저장하는 도규멘트의 크기는 필드명을 포함하고 있다는 것이다. RDB를 개발한 사용자들이 흔히 이 점을 유념하지 않아 도규멘트 크기가 벗어나는 경우가 종종 발생하기도 한다. 만약 도큐멘트 { personal nick name :  test } 를 저장한다고 생각하면, 필드명 ‘personal nick name’이 [그림 1]의 data 영역에 같이 저장되기 때문에 1만명의 사용자 닉네임을 저장한다고 하면 ‘personal nick name’이 1만번 중복되어 저장된다. 따라서, MongoDB를 사용할 때는 필드명 설정에 신중할 필요가 있다. [표 1]은 [그림 1]의 각 필드명에 대한 설명을 보여준다.
 
[표 1] MongoDB의 레코드 구조

필드명	내용
Size	헤더를 포함하고 있는 레코드의 크기, BSON 객체의 크기는 Size 필드에서 헤더 크기인 16을 빼면 된다.
Extent Offset	해당 레코드가 속해 있는 익스텐션의 Offset 주소[3]
Next Offset	다음 레코드를 가리키는 Offset 주소
Prev Offset	이전 레코드를 가리키는 Offset 주소
bson object	도큐멘트를 구성하는 BSON 객체[4]

[표 1]에서 레코드에서 저장되어 있는 모든 위치 정보(Extent Offset, Next Offset, Prev Offset)들이 4바이트 정수형 데이터로 저장한 이유는, 동일한 익스텐트 안에 저장되는 데이터이기 때문에 익스텐트 시작 주소의 상대 주소 값을 저장하여 중복된 데이터 영역을 없애 데이터 저장 크기를 줄일 수 있기 때문이다.
 

MongoDB 익스텐트 구조

MongoDB의 익스텐드는 레코드들의 그룹을 말한다. 익스텐드는 고유한 네임스페이스를 가지고 있기 때문에, 익스텐드에 포함된 레코드는 동일한 네임스페이스에 존재하는 데이터가 된다. 즉, 이전 글의 [그림 1]과 같이 MongoDB의 컬렉션은 한 개 이상의 익스텐드로 구성된다. MongoDB는 데이터베이스.컬렉션 형태의 데이터 표기법을 가지고 있다. 예를 들어, personal 데이터베이스의 user 라는 컬렉션이 존재한다고 가정하면, 데이터 삽입을 personal.user.insert( { personal_name : ‘이승용’ } ) 과 같이 사용한다. 이때 personal.user 의 형태가 네임스페이스를 의미한다. [그림 2]는 MongoDB의 익스텐드 구조를 보여준다.

[그림 2]와 구성된 MongoDB의 익스텐트는 한 개의 네임스페이스를 가지고 있기 때문에, 한 개의 컬렉션은 여러개의 익스텐트를 가질 수 있지만, 역은 성립하지 않는다.(한 개의 익스텐트에 두 개의 컬렉션이 저장되지 않는다.)  [그림 2]의 위치 정보 – My Location, Next Extent, Prev Extent, First Record, Last Record – 들은 모두 8바이트 크기를 가지고 있다. 64비트 컴퓨터의 주소는 64비트 크기를 가지고 있기 때문에 8바이트 크기를 가진다. 그리고 size 필드가 4바이트로 규정되어 있다. MSB^{Most Significant Bit} 를 제외하면 2GB의 크기 까지 익스텐트의 크기를 지정할 수 있다. 

익스텐드는 헤더 4바이트와 데이터 172바이트로 구성되어, 총 178바이트의 크기를 가진다. 헤더에는 781231[5]이라는 값을 가지고 있으며, 16진수로 0x000BEBAF를 가진다. 익스텐드 데이터 영역에 대한 자세한 사항은 [표 2]를 보기 바란다. [표 2]에 저장된 모든 위치 정보는 8바이트 크기를 가지며, 상위 4바이트는 볼륨 정보를, 하 위4바이트는 오프셋 위치를 나타낸다.
 
[표 2] MongoDB의 익스텐드 구조

필드명	내용
Magic	4바이트 헤더이며, 정수 781231 값을 가진다.
My Location	해당 익스텐드가 저장된 위치 정보를 나타낸다.
Next Extent	다음 익스텐드를 가리키는 위치 정보
Prev Extent	이전 익스텐드를 가리키는 위치 정보
Namespace	해당 익스텐드의 네임 스페이스[6]
Size	해당 익스텐드의 크기
First Record	해당 익스텐드에 포함된 첫번째 레코드 위치 정보
Last Record	해당 익스텐드에 포함된 마지막 레코드 위치 정보

 

글 : 이승용

 

빅데이터가 소개되면서 NoSQL이 각광받게 되었으며, 그 중 MongoDB는 NoSQL에서 선두 자리를 차지하고 지속적으로 발전되고 있다.다. 오픈 소스인 MongoDB는 누구가 그 내부 구조를 살펴 볼 수 있음에도 불구하고 방대한 양 때문에 MongoDB에 대한 내부 구조에 대해 자세하게 논하지는 못하고 있다. 사실 끊임없이 업그레이드되는 프로젝트의 내부 구조를 매번 분석한다는 것도 매우 어렵다. 하지만, 필자는 이번 기회에 필자가 분석한 MongoDB의 내부 데이터 구조를 살펴봄으로써, NoSQL의 기술 트랜드가 어떠한 방식으로 발전되고 있는지 알아보고, 개선 방향에 대해서도 살펴보기로 한다. 이번에는 그 첫번째로 MongoDB에서 사용되는 데이터 구조의 용어를 기본 개념만 알아본다.

MongoDB의 데이터 구조는 크게 데이터를 저장하는 레코드^record와 인덱스를 저장하는 버켓^bucket으로 구성된다. MongoDB는 BSON 객체를 데이터 저장 단위로 사용하기 때문에, 저장하고 있는 모든 데이터를 BSON 객체의 이중연결리스트^{double linked list}구조로 구성하고, BSON 객체를 저장하는 노드를 레코드로 정의한다. 반면 인덱스는 레코드에 저장된 데이터를 빠르게 찾기 위해 b-tree 형태로 저장된 노드 구조를 가지며, b-tree 노드를 버켓이라고 정의한다.

MongoDB는 대용량 데이터를 HDD에 쉽게 저장할 수 있는 단위로 레코드들을 그룹핑^grouping하는데, 이를 익스텐드^extent라고 한다. MongoDB의 익스텐드는 자료 구조 관점에서 보면 연결되어 있는 레코드들의 헤더 역할을 수행하는 것이지만, 이 익스텐드들을 이용하여 MongoDB는 HDD에 저장될 파일과 삭제된 레코드를 관리한다.

 

 

[그림 1]은 앞에서 설명한 MongoDB의 데이터 구조가 유기적으로 수행되는 모습을 도식화한 것이다. 사용자가 하나의 데이터베이스를 만들었다면, MongoDB는 데이터베이스와 관련된 한 개의 네임스페이스^namespace를 만든다.[1] 데이터베이스 네임스페이스는 RDB의 테이블과 동일한 MongoDB의 컬렉션^collection 네임스페이스와 데이터베이스 별로 삭제된 레코드 리스트를 가지고 있는 프리 익스텐드^{Free Extent} 리스트를 가진다. 컬렉션 네임스페이스는 사용자가 insert 질의를 통해 정의한 컬렉션 명으로 구성되며, 컬렉션 생성과 동시에 _id 필드의 기본 인덱스 네임스페이스를 가지게 된다. 만약 사용자가 _id 이외의 필드를 인덱스를 구성하였다면, 생성된 인덱스 필드에 하나의 인덱스 네임스페이스가 구성되고, 필드 값은 b-tree 형태로 인덱스를 구성한다.

MongoDB는 데이터를 저장하는 레코드나 인덱스를 저장하는 버켓이나 모두 데이터를 저장하는 공간이다. MongoDB의 데이터 저장소는 메모리 맵 파일^{Memory Mapped File}을 사용한 가상 메모리를 사용한다. 가상 메모리는 시스템이 지원하는 운영체제 버전에 따라 가상 주소 공간을 할당 받게 되고 할당 받은 주소 공간을 마치 파일을 처리하는 방식으로 프로그램을 구성할 수 있다.[2]

[그림 1]과 같이 실질적인 데이터 저장 공간을 가지고 있는 레코드와 버켓은 그 크기에 맞는 가상 메모리의 주소를 가지고 있고, 사용자가 insert/update를 수행하였다면 MongoDB는 해당 레코드가 가리키는 가상 메모리 주소 공간에 데이터를 적재한다. 만약 사용자가 특정 위치의 데이터를 읽는다면, MongoDB는 해당 메모리 주소 공간에 할당된 데이터가 가상 메모리에 로딩되어 있는지 확인하고, 로딩되어 있지 않다면 파일에서 내용을 읽어 가상 메모리에 적재한다.[3]

또한 MongoDB는 백그라운드로 가상 메모리에 적재된 데이터를 HDD에 최대 2GB 단위로 파일을 구성한 볼륨^volume으로 HDD에 데이터를 적재한다. 이를 플러쉬^flush를 수행한다고 하며, 주기적으로 가상 메모리 공간에 로딩된 데이터를 HDD에 저장한다.[4]