Instagram 에서 ID 샤딩하기

해당 글은 sharding & IDs at Instagram (http://instagram-engineering.tumblr.com/post/10853187575/sharding-ids-at-instagram) 이라는 글을 발 번역 한 것입니다. 오역에 주의하세요. 샤딩이라는 것은 데이터를 파티셔닝 하는 방법을 말합니다. 파티셔닝에는 Vertical 과 Horizontal 이 있는데, 샤딩은 같은 종류의 데이터를 서로 다른 곳에 저장하는 Horizontal Partitioning의 일종입니다.( 예를 들어 A라는 유저의 데이터는 1번 서버, B라는 유저의 데이터는 2번 서버로 저장하면 샤딩, 전체 유저의 프로파일 정보는 1번 서버, 포스팅은 2번 서버에 이렇게 따로 저장하는 것이 Vertical Partitioning입니다. 좀 더 자세한 설명은 http://en.wikipedia.org/wiki/Partition_(database) 를 참고하세요.)

Instagram 에서 ID 샤딩하기

Instagram에서는 초당 25개의 사진과 90개의 Likes 가 넘는 많은 데이터를 저장합니다. 고객들이 빠르게 이용할 수 있도록, 중요한 데이터들을 메모리에 적합하게 만들어야 합니다. 그래서 데이터들을 샤딩하기 시작했습니다. 다른 말로 하면, 많은 적은 크기의 버켓들을 만들고, 데이터의 일부분들을 저장해두었습니다.

우리의 애플리케이션 서버는 Django 이고, 백 엔드 데이터베이스는  PostgresSQL  를 이용합니다. 데이터를 샤딩하기로 결정한 후의 첫번째 고민은 PostgresSQL이 여전히 메인 저장소로 사용할 것인지, 아니면 다른 종류로 변경할 것인지였습니다. 다른 NoSQL 솔루션들을 평가했지만, 결국, PostgreSQL 에 데이터들을 샤딩하기로 했습니다.

데이터를 샤딩하기 전에, 우리는 어떻게 ID(ex: 각 사진 포스팅 정보들) 들을 각 서버에 할당할 것인지를 해결해야만 했습니다. 일반적인 해결책은 그냥 데이터베이스를 하나만 이용하는 것입니다. ( database에 제공하는 auto_incremental 기능을 이용합니다.)  그런데, 여러 database 에 데이터를 집어넣으면, 더 이상 제대로 동작하지 않습니다. 이 글의 나머지 부분은 어떻게 해당 이슈를 해결했는가입니다. (역자 주: 중복되지 않는 unique ID 값을 만들려는 것이 목표입니다. 보통 database에서는 auto_increment를 통해서 겹치지 않는 값을 만들 수 있는데, 여러 서버에서는 이 값들이 동일하게 되기 때문에 여러 서버에서 보면 중복되는 값이 서버 개수 만큼 생길 수 가 있습니다.)

먼저 시스템에서 필요한 기능들을 나열해 보겠습니다.

1. IDs 는 시간으로 정렬할 수 있는 형태여야 한다.( Photo ID를 예로 들어서, 사진의 추가 적인 정보를 찾지 않고도 정렬할 수 있어야 합니다.) (역자 주: 이럴려면, ID가 뭔가 시간 정보를 담고 있어야 하겠죠 ^^)

2. IDs 는 64bit 이어야 한다.( redis 등의 더 작은 인덱싱이 가능한 시스템을 위해서 )

3. 시스템은 가능한 변동하는 부분이 없어야 한다.  겨우 몇명의 엔지니어로 Instagram의 확장성을 가지기 위해서 간결하고, 이해하기 쉬운, 신뢰할 수 있는 솔루션이어야 한다.(역자 주: 뒤에 나오지만,  구성하는 컴포턴트 들이 적으면 좋겠다는 뜻입니다. twitter 의 SnowFlake 같은 경우, Apache Zookeeper 와, Thrift 서버를 추가로 구성해야 합니다.)

기존 솔루션

IDs 생성 문제에 대한 많은 기존 솔루션들이 있고, 몇가지를 고려해보았습니다.

웹 어플리케이션에서 IDs 생성하기

이 방법은 데이터베이스에 접근하지 않고, 어플리케이션에서 전적으로 ID를 생성하는 방법입니다.  MongoDB의 ObjectId는 12bytes 의 인코딩된 timestamp를 이용합니다. 다른 방법으로 UUID 가 있습니다.

-장점

1. 각 어플리케이션에서 독립적으로 ID를 생성하므로, ID 생성시에 생기는 실패나 병목지점을 최소화 할 수 있습니다.

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

-단점

1. 일반적으로 유일한 ID를 만들기 위해서는 스토리지 용량이 더 필요합니다.( 적어도 96bits 이상)

2. 몇몇 UUID는 완전 랜덤으로 만들어져서 정렬을 할 수 가 없습니다.

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

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

-장점

1. SnowFlake 의 ID는 64bits 로 UUID의 절반 사이즈입니다.

2. time 정보를 이용해서 시간으로 정렬이 가능합니다.

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

– 단점

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

DB Ticket 서버

데이터베이스의 Auto-Incrementing 기능을 이용합니다. Flickr 가 이 방법을 이용합니다. 그러나, 두 개의 ticket DB를 이용해서 SPOF를 피합니다.( 하나는 홀수로만, 하나는 짝수로만 증가하게 합니다. )(역자 주: 보통 uID가 꼭 연속적일 필요가 없기 때문에, 장애 대비용으로 홀수, 짝수로 구분해 놓고 많이 사용합니다. 또한, 짝수 서버를 홀수 서버의 slave로 설정해두고, 평소에는 홀수 내용을 저장하다가, 자기쪽으로 insert 가 직접적으로 들어왔을 때만, 짝수로 동작하게 해서 Consistency를 보장하는 방법도 가능합니다. )

-장점

1. DB는 확장 요소를 쉽게 예측가능하고, 이해하기 쉽습니다.

-단점

1.  쓰기 병목이 일어날 수 있습니다.( Flickr 에서 이 내용을 리포팅 했습니다.  그러나 Flickr 같은 큰 규모에서 이용하므로, 큰 이슈는 아닌듯합니다.

2. 두 대의 장비를( EC2 instance) 추가해야합니다.

3. 하나의 DB만 이용한다면, SPOF 가 생깁니다. 여러 개의 DB를 이용한다면,  시간으로 정렬됨을 더 이상 보장하지 않습니다.

(역자 주: 전체를 시간으로 정렬할 수 없는 이슈가 생깁니다. 홀수, 짝수일 경우, 한대의 서버가 장애가 나면, 다른 장비로 값이 계속 증가될 텐데, 장애가 복구가 되었을 때, 해당 장비의 시작값이 다른 서버보다 작기 때문입니다.)

위의 방법들을 봤을 때, 트위터의 SnowFlake 가 가장 요구사항에 근접합니다. 그러나, 한가지 복잡함이 추가되는 부분이 있습니다.  컨셉적으로는 비슷한 방법을 사용하되, 우리는 PostgresSQL 을 이용하기로 했습니다.

해결책

샤딩된 시스템은 몇몇 물리적 샤딩 시스템에 수 천개의 “논리적” 샤딩 시스템이 매핑되어있습니다.  이 방법으로, 몇 대의 데이터베이스 서버로 시작할 수 있었습니다.  어떤 데이터도 새로운 bucket에 옮길 필요없이 간단하게논리적 샤드를 하나의 데이터베이스에서 다른 데이터베이스로 옮길 수 있습니다.  Scirpt 제작과 관리를 쉽게하기 위해서 Postgres 의 스키마를  이용했습니다.

스키마(  개별 테이블의 SQL 스키마와는 혼동되지 않는 )는 Postgres 안에서 논리적 그룹 형태입니다. 각 PostgresDB는 몇 개의 스키마를 가지고, 각각은 한개 이상의 테이블을 가지고 있습니다.  테이블 명은 DB마다가 아니라 Schema 마다 유일해야 합니다. 그리고 모든 스키마는 ‘public’ 이라는 이름을 가지고 있습니다.

각각의 논리적 샤드는 Postgres 스키마 입니다. 그리고 각각의 샤딩된 테이블( Photos 에서 쓰이는 것과 비슷한) 은 각각의 스키마 안에 존재합니다.

PL/PGSQL 이라는 Postgres 프로그래밍 언어와 Auto-Increment 기능을  이용해서 ID 생성을 각 샤드내의 각각의 테이블과 연결했습니다.

 

각각의 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도 가지고 있습니다. ) 해당 방법을 제품에 적용하고 그 결과로 행복합니다. 우리가 말한 이런 스케일 문제에 관심이 있으신가요?

We’re hiring!