서비스의 고유아이디를 만들기 위한 참고용 인스타그램 샤드키 만들기.

인스타그램도 기존의 DB를 사용하는 데에 있어서 용량을 늘리고 샤딩하는 문제에 대해서 전체적인 구조적 고민을 하는 경우가 있었다고 합니다.

 

심지어 DB종류를 Postgresql에서 다른 종류로 바꿔야 하는 가에 대해서 고민도 했다고 합니다.

 

하지만 결국 정해진 결론은 데이터를 샤딩하자는 결론이 나왔습니다.

 

보통 DB에서는 Data가 들어가면 그 Data에 따른 incremental number로 숫자를 생성하여 다루기 때문에 만약 정수형이 이 수를 이용해서 샤딩을 하는 경우에는 중복문제가 발생할 수 있습니다.

 

그래서 나온 논의가 고유 ID를 만들어서 샤드키로 활용하자는 것이었습니다.

 

여기서부터 샤드키를 만드는 방법이라고 생각하실 수 있는데, 그렇게 생각하는 것보다 고유한 아이디(UID)를 만드는 과정을 설명합니다.

 

사용될만한 예를 들면, 사용자의 고유의 정보를 식별해야하는 서비스를 만드는 경우에는 이 과정이 필요로 하게 됩니다.

 

고유 ID를 만드는 과정을 설명하겠습니다. 인스타그램의 예를 들어서 설명에 덫 붙이겠습니다.

 

1. 일단 ID를 만들기 전에 ID를 어떻게 사용할 것인가를 정의해야합니다.

:: 인스타그램을 예를 들면,

1) 사진을 시간 순으로 정렬을 쉽게 하기 위해서 시간 정보가 담겨있을 것

2) UUID가 쓰일 다른 용도를 고려하여 너무 크지도 않고 작지도 않은 인덱싱이 가능한 64bits 일 것.

3) 시스템은 가능한 변동하는 부분이 없어야하고, 확장성을 고려하고, 이해하기 쉬운, 신뢰할 수 있어야 한다.

 

 

고유한 ID를 생성하는 기존 솔루션을 비교해 봅니다.

 

* MongoDB – 어플리케이션 단에 자체 생성 ID

예를 들어, MongoDB에서 생성하는 자기 고유 식별자인 ObjectId는 12bytes(96bits)의 인코딩된 timestamp를 이용합니다. 다른 방법으로 UUID(128bits) 가 있습니다.

 

-장점

1. 각 어플리케이션에서 독립적으로 ID를 생성하므로, ID 생성 시에 중복이나 오류가 발생할 확률이 거의 없습니다.

2. timestamp 를 이용하면, ID는 시간으로 정렬이 가능합니다.

-단점

1. 유일한 아이디를 만드려고 한다면 ObjectId가 사용하는 방식의 최소한의 12bytes를 따르고, 거기에 덫 붙이는 방식을 사용해야하기 때문에 최소 96bits이상이 됩니다.

2. 가끔 만들어지는 ID 중에서 완전한 랜덤방식 만들어지는 패턴이 나오기도 합니다. 그래서 정렬에 사용이 불가능 합니다.

 

 

* 중앙서비스를 이용한 IDs 생성하기

Ex: 트위터의 SnowFlake , Apache Zookeeper 를 이용한 Thrift 서비스로 64bit 의 유일한 ID를 생성합니다.

 

-장점

1. SnowFlake 의 ID는 64bits 로 UUID의 절반 사이즈로 길이의 최적화.

2. time 정보를 이용하기 때문에 시간 순으로 정렬이 가능.

3. 일부 노드가 죽어도 사용할 수 있는 분산 시스템입니다.

– 단점

1. Instagram 서비스에 사용하기에는 Moving Parts(ZooKeeper, SnowFlake Servers) 이 많아서, 시스템을 더 복잡하게 만듭니다.

 

해결책

샤딩이 된 큰 규모의 시스템은 수 천개의 논리적 샤딩과 수십개의 물리적 샤딩으로 구성이 되어 있습니다.

이러한 구성으로 샤딩의 분할된 크기만큼이 아닌 적은 수의 실제 DB 장비를 가지고 관리를 할 수 있습니다.

 

각각의 ID는 다음과 같이 구성되어 있습니다.

* 41 bits 는  밀리세컨으로 이루어집니다.(41년 정도의  ID를 만들 수 있습니다.)

* 13 bits 는 논리적 샤드 ID를 표시합니다.

* 10 bits 는 Auto-Increment 순서를 1024로 나눈 나머지를 표시합니다. 

이 의미는  1024개의 ID를 각 논리적 샤드마다 생성하고, 이것들이 다시 밀리세컨 마다 생성이 된다는 뜻입니다.

 

예를 들면,  기준시간이 2011/01/01 이라고 하고 2011/09/09  오후 5:00 이라면, 해당 값은 1387263000 밀리세컨입니다. 그래서 우리의 ID의 처음 41bits 는 해당 값으로 저장됩니다.

id = 1387263000 <<(64-41)

다음으로, insert를 시도 하기 위한 샤드 ID를 구해야 합니다. 유저 ID로 샤딩을 한다고 하고, 2000 개의 논리적 샤드가 있다고 합시다.  UserID가 31341 이면, 샤드 ID는 31341 % 2000 -> 1341 이 됩니다. 나머지 13bits 는 해당 값으로 설정합니다.

Id |= 1341 <<(64-41-13)

마지막으로, auto-increment sequence( 해당 sequence 값은 각 스키마의 각 테이블마다 유일합니다) 를 가져와서 나머지 bits를 채웁니다. 해당 테이블에 이미 5,000 개의 ID가 있다고 한다면, 다음 값은 5,001 입니다. 이것을 1024로 나눈(1024로 나누면 10bit에 떨어집니다.)  나머지를 채웁니다.

id |= (5001 % 1024)

 

이것으로 RETURNING 키워드를 이용해서 어플리케이션 서버에 돌려줄  ID를 생성했습니다.

PL/PGSLQL은 다음과 같습니다.

 

CREATE OR REPLACE FUNCTION insta5.next_id(OUT result bigint) AS $$

DECLARE

our_epoch bigint := 1314220021721;

seq_id bigint;

now_millis bigint;

shard_id int := 5;

BEGIN

SELECT nextval('insta5.table_id_seq') %% 1024 INTO seq_id;

SELECT FLOOR(EXTRACT(EPOCH FROM clock_timestamp()) * 1000) INTO now_millis;

result := (now_millis - our_epoch) << 23;

result := result | (shard_id << 10);

result := result | (seq_id);

END;

$$ LANGUAGE PLPGSQL;

 

그리고 테이블은 다음과 같이 생성합니다.

CREATE TABLE insta5.our_table (

"id" bigint NOT NULL DEFAULT insta5.next_id(),

 ...rest of table schema...

)

 

 

이걸로 끝입니다. Primary Key는 우리의 어플리케이션에서 유일합니다.( 거디다가 보너스로 각각 매핑된 Shard ID도 가지고 있습니다. )

이렇게 인스타그램의 고유 사용자의 DB를 구분하는 ID를 만들었습니다.

이 정보를 토대로 서비스의 고유아이디를 만드는 방법을 고안해 보도록하겠습니다.

* Reference

인스타그램 개발자 블로그 - http://instagram-engineering.tumblr.com/post/10853187575/sharding-ids-at-instagram