[입 개발] Global Unique Object ID 생성 방법에 대한 정리

서비스를 구성하다보면, Global Unique Object ID를 만들어야 하는 경우가 발생합니다. facebook의 facebook 포스팅에 대한 ID라든지, 트위터의 tweet id, 인스타그램의 image에 대한 id 등, 각자 자신의 목적이 있고, 이에 대해서 구현되어 있습니다.

그래서, 좀 유명한 Global Object ID 를 구성하는 방법에 대해서 정리를 해보고자 합니다.

대략 대상은 UUID, MonngoDB Object ID, 인스타그램 Object ID, 트위터의 snowflake 정도가 될 듯 합니다.

(이 글을 거의 6월에 작성 할려다가 놀고 이제서야 다시 정리하게 되네요.)

먼저 왜 Global Unique Object ID가 필요할까요? 위에서 예를 든 사이트들은 전부 scale 이 굉장히 큰 사이트들입니다. 여기서 해당 값을 쉽게 찾을 수 있는 Global Unique Object ID가 없다면, 페이스북이나 트위터의 글들이 다른 사람들과 중복되거나, 찾는데, 한참 오래 걸릴 것입니다.

가장 간단하게 Global Unique Object ID를 만드는 방법은 ID + DB등의 auto_increment 같은 방식일 것입니다. 다만 이런 방식은 아이디의 크기에 따라 사이즈가 변동되는 문제나, 서비스의 요구사항을 만족시키기 위해서 좀 더 개선된 방법을 사용하게 됩니다. 그럼 이제 기존에 사용되는 방법들에 대해서 한번 알아보도록 하겠습니다. 필요한 요구사항이 있다면 이런것들에 대해서 이해한 다음 자신만의 Global Object ID를 만들어내면 될듯 합니다.

UUID

UUID는 Universally unique identifier 의 약어로, 16-octet(128bit) 크기의 32개의 헥사로 표시되게 됩니다. OSF에서 표준화했다고 합니다. RFC 4122 를 보시면 될 것 같습니다. MIS에서 사용하는 GUIDs 나 여러 군데서 사용되고 있고, 다음과 같은 형식을 따릅니다.


550e8400-e29b-41d4-a716-446655440000

UUID를 구현하는데는 다양한 방식이 있는데, MAC address 나 HASH(md5, sha-1) 등을 이용한 방식이 유명합니다. 간단하게 구현 방식을 이야기 하자면, MAC address 자체가 unique 하기 때문에, 여기에 현재의 시간을 붙이는 방식으로 구현이 가능합니다. http://en.wikipedia.org/wiki/Universally_unique_identifier 를 참고하시면 관련 구현체들도 쉽게 찾으실 수 있습니다.

MongoDB Object ID

MongoDB 의 Object ID는 12bytes BSON type으로 되어 있고, 다음과 같은 형태로 구성이 됩니다.

mongo_objectid

여기서 Machine ID는 랜덤하게 만들어지게 됩니다. Counter 역시 최초의 시작은 랜덤하게 만들어집니다. 코드를 보면 MachineID와 Counter 는 가은 Random 함수를 이용해서 만들어지게 됩니다.( src/bson/oid.h src/bson/oid.cpp)를 보시면 됩니다.

Timestamp 와 Counter, MID, PID를 이용해서 서버간에도 중복되지 않는 unique 값을 만들 수 있습니다. 그러나 mongodb의 Object ID는 정말 재수가 없으면 machine id 와 pid가 동일하게 만들어질 수도 있습니다. MID와 Counter가 Random 기반이기 때문이지요.

Instagram 의 ID

MongoDB와 UUID가 자체적인 값을 이용한 방식이었다면 Instagram의 그것은 Database의 Auto Increment를 이용하는 방법입니다.  일단 ID가 적을수록 메모리도 덜 차지하고 유리할 것입니다. 다음과 같은 형태로 구성됩니다.

instagram_id

대부분 Timestamp + Shard ID + Increment Value 로 구성이 되는데, 이 Increment Value를 어디서 가져오는지에 따라서 대부분의 구현이 조금씩 바뀌게 됩니다. 자체적으로 만드느냐? 아니면 DB나 Redis 등의 increment Value를 가져오느냐? 등이 차이일 뿐입니다.

더 자세한 내용은 https://charsyam.wordpress.com/2011/12/04/instagram-%EC%97%90%EC%84%9C-id-%EC%83%A4%EB%94%A9%ED%95%98%EA%B8%B0/ 를 살펴보시면 좋을 듯 합니다.

Twitter –  snowflake(https://github.com/twitter/snowflake)

Snowflake 는 Twitter 에서 tweet ID를 생성하기 위해서 사용하는 Global Unique Object ID 입니다. Thrift 로 만들어져 있고, ZooKeeper 와 연동되어 있습니다. (인스타그램에서 연동하는게 많아서 사용하지 않았다고 합니다. 알아야 되는게 많아서)

snowflake_id

Snowflake 는 64bit 로 구성되어 있습니다. sequence 는 timestamp 가 동일할 때만 증가하고, 그 이외에는 0으로 셋팅되게 됩니다.  여기서 DataCenter ID는 설정에 있고, Worker ID는 InetAddress.getLocalHost()로 가져와서 ZooKeeper에 저장해두는 것으로 보입니다. ZooKeeper 에는 /snowflake-servers 에 저장되는 듯 합니다.( snowflake 도 최악의 경우에 같은 timestamp 에 같은서버에 sequence 가 12bit 이상 몰리면, 같은 id가 만들어질 가능성이 있습니다. 뭐, 이 부분은 인스타그램도 마찬가지입니다.)

(수정: snowflake 가 4096 이상이 생겨도 같은 ID를 만들지 않는다는 @GeekDani 님의 말씀에 따라서 소스를 자세히 보니  tilNextMillis에서 현재 timestamp보다 값이 커질 때까지 tilNextMillis 함수안에서 계속 timeGen을 호출하게 되어서 중복을 피합니다. @GeekDani 님께 감사를)

protected[snowflake] def nextId(): Long = synchronized {
 var timestamp = timeGen()

 if (timestamp < lastTimestamp) {
 exceptionCounter.incr(1)
 log.error("clock is moving backwards. Rejecting requests until %d.", lastTimestamp);
 throw new InvalidSystemClock("Clock moved backwards. Refusing to generate id for %d milliseconds".format(
 lastTimestamp - timestamp))
 }

 if (lastTimestamp == timestamp) {
 sequence = (sequence + 1) & sequenceMask
 if (sequence == 0) {
 timestamp = tilNextMillis(lastTimestamp)
 }
 } else {
 sequence = 0
 }

 lastTimestamp = timestamp
 ((timestamp - twepoch) << timestampLeftShift) |
 (datacenterId << datacenterIdShift) |
 (workerId << workerIdShift) |
 sequence
 }

간단한 Global Unique ID 만들기

뭐, Global Unique ID를 잘 만들려면 여러가지 고민할 필요가 많지만, 아주 간단하게 만들려면, 그냥 redis 나 memcache 등의 incr 명령을 이용해서 unique 한 id를 만들 수 있습니다. 캐시 서비스를 이용할 경우 단점은 해당 서버가 장애가 나면 increment value 가 초기화 되지 않느냐가 이슈가 되는데, 뭐 결국 timestamp + id 로 해서 문제를 간단하게 해결할 수 있습니다. 그게 아니면 persistent 한 저장소에 특정 값을 써두고, 캐시 서버가 종료가 되면, 해당 값에서 부터 시작하면 됩니다.(시작시에 값을 다시 증가시켜 두고 시작하면 됩니다. 서비스중에 해당값이 차게 되면, 다시 값을 특정 수의 배수만큼 증가시켜 두고 서비스하는 형태로도 간단하게 구현이 가능합니다.)

개인적으로는 인스타그램 처럼 최대한 간략하게 만들어주는 것이 좋을 것 같습니다 유지 보수가 쉬워야 하니까요. 다만, 정확하게 서비스의 요구사항에 맞춰서 구현하거나, 가져다 쓰는 것이 필요합니다.

Advertisements