[MongoDB] ObjectId에 대해서

지난번에 shard key를 설명한 글을 썼을 때 댓글ObjectId에 관한 얘기가 나왔었다. 그래서 sharding과 큰 연관은 없지만, 이번 기회에 ObjectId에 관해서 먼저 설명하고 가는 게 좋을 것 같아서 sharding에 관한 것은 뒤로 미루고 이번에는 ObjectId에 대해 먼저 설명하고 가도록 하겠다.

ObjectId란 무엇인가

ObjectId는 같은 document 내에서 유일함이 보장되는 12 byte binary data다. 전통적인 centralized 되어 있는 시스템이라면 한 collection 내에서 유일함을 보장하는 것을 쉽게 할 수 있다. 하지만 sharding을 하는 MongoDB에서 유일함을 보장하는 것은 기존과는 다른 솔루션이 필요하다. 그리고 이 방법을 설명하는 게 사실상 ObjectId의 모든 것을 설명하는 것이다.

왜 ObjectId를 사용하는가

전통적인 RDBMS에서 Primary key를 만들 때는 DB 서버로 data를 보내서 중복되지 않는 key를 골라서1) 그 값을 key로 저장하는 방식을 이용한다. 하지만 MongoDB와 같은 분산 database에서는 key를 서버에서 만들지 않고 클라이언트에서 만든다. 그 이유는 MongoDB가 query를 날릴 shard를 결정하는 방식을 보면 알 수 있다.

MongoDB는 자신이 필요한 shard에게만 query를 요청한다. 다시 말해서 client에 해당하는 mongos2)config server의 data를 토대로 어떤 shard가 어느 범위의 값을 가졌는지를 저장하고 있다가 query를 요청할 때 자신이 필요로 하는 shard에게만 요청한다. 따라서 shard key에 해당하는 data가 미완성인 상태로 서버에 저장하도록 요청할 수 없고, client가 ObjectId를 생성하여 값을 저장하도록 요청한다. 3)

ObjectId의 구성

ObjectId는 크게 4부분으로 구성되어 있다. ObjectId의 처음 4 byte는 시간정보를 담고 있다. 1970년 1월 1일 0시 0분 0초를 0으로 해서 4 byte의 정보를 담고 있으므로 2106년 2월 7일 6시 28분 15초까지 표현할 수 있다.

다음 3 byte는 machine 별로 다른 고유한 id를 담고 있다. 이것은 driver의 구현에 따라 다르지만 보통 mac address + ip address 혹은 hostname을 md5 hash한 값의 처음 3 byte를 따온다. 하지만 driver 별로 구현이 다르다. 같은 driver를 사용할 때 같은 머신이 같은 값을 가지는 방식 중에서 최대한 랜덤하게 분포하는 방식으로 구현된다.

다음 2 byte는 process id 정보를 담는다. 32-bit 머신에서 process id의 최댓값은 2^15이라서 2 byte로 문제없이 표현된다. 하지만 64-bit 머신에서는 최댓값이 2^22이 가능하므로 해당 범위에 들어가지 못한다. 이러면 어떻게 처리할지 문서에서 찾지 못했다. 하지만 실제로 process id가 필요한 것이 아니고 ObjectId의 유일함을 보장하기 위해 사용되는 bit들이므로 정확한 process id를 유지하고 있을 이유는 없다. 때문에 mongodb가 가지고 있는 bson 구현체에서는 process id가 2 byte보다 크면 하위 2 byte만을 pid bits에 저장하고, 상위 1 byte는 machine number에 반영하지만 드라이버에 따라서는 하위 2 byte만을 process id로 저장하고 상위 1 byte는 버리는 드라이버도 있다.

마지막 3 byte는 mongos가 생성한 값으로 inc라고 부른다. 이것도 driver 별로 구현이 다르기는 하지만 보통 random 한 숫자에서 시작하여 auto increment되는 숫자다. 일부 구현체들은 0부터 시작하는 auto increment 되는 숫자를 쓰기도 하고, 단순히 random하게 고른 숫자를 쓰기도 하는데 이렇게 사용하면 원래의 방식보다 충돌할 확률이 늘어난다.

ObjectId의 unique성

따라서 독립적으로 생성된 두 ObjectId가 같을 확률은 매우 낮다. 일단 최소 조건은 두 ObjectId가 1초 내에 생성된 ObjectId이어야 한다. 4) 그리고 같은 machine hash를 가지는 머신에서 같은 process id로 뜬 process id로 뜬 mongos에서 생성된 ObjectId이어야 한다.

같은 머신에서 생성된 ObjectId는 기본적으로 이런 조건을 만족한다. 하지만 3 byte의 inc가 같은 머신에서 생성한 ObjectId가 중복되는 것을 막아준다. 하나의 mongos에서 1초에 16,777,215개 이상의 ObjectId를 생성하는 불가능한 시나리오가 아니면 중복된 ObjectId가 중복되지 않는다. 5)

서로 다른 머신의 경우 같은 machine id와 process id를 가지는 확률은 매우 낮다. machine id로 3 byte를 사용하므로 machine id가 같을 확률은 1/16,777,215이다. 거기에 같은 inc를 가질 확률 1/16,777,215까지 더해져 실제로 machine id가 같은 mongos에서 같은 inc를 가질 확률은 천만분의 일이다. 여기에 서로 같은 process id로 process가 실행될 확률까지 더해져서 실제 확률은 더 낮아진다.

하지만 이는 어디까지 확률적인 문제고 매우 낮은 확률로 혹은 의도적으로 같은 ObjectId가 생성되는 일도 있다. 이런 경우는 shard에서 E11000 duplicated key error를 발생시키고 insert가 실패한다.


1) 보통은 auto increment를 사용한다.

2) 혹은 query router

3) 사실 shard key 이외에 data가 미완성인 상태로 요청하여 server에서 완성하도록 하는 default 같은 방식을 지원하지 않는다. MongoDB는 자신이 요청받은 data를 그대로 저장한다.

4) 혹은 1970년 이전에 생성된 ObjectId거나 2106년 이후에 생성된 ObjectId이어야 하는데 MongoDB 개발자들은 이럴 경우는 없을 거라고 가정하고 있다.

5) 이것은 어디까지나 정상적인 드라이버에서의 얘기다. 만약 위에서 말한 대로 단순히 랜덤하게 생성하는 driver라면 16,777,215개를 생성하지 않더라도 1/16,777,215의 확률로 충돌이 발생한다.

댓글

  1. 같은 머신에서 생성된 ObjectId는 기본적으로 이런 조건을 만족한다. 하지만 3 byte의 inc가 같은 머신에서 생성한 ObjectId가 중복되는 것을 막아준다. 하나의 mongos에서 1초에 4,096개 이상의 ObjectId를 생성하는 불가능한 시나리오가 아니면 중복된 ObjectId가 중복되지 않는다. 5)

    여기서 3바이트면 범위가 0~16777215 입니당

    답글삭제

댓글 쓰기

이 블로그의 인기 게시물

USB 2.0 케이블의 내부 구조

[C++] enum class - 안전하고 쓰기 쉬운 enum

Log Aggregator 비교 - Scribe, Flume, Fluentd, logstash

[Web] SpeechSynthesis - TTS API

[Python] cache 데코레이터로 최적화하기