인스타그램의 샤딩 방법과 ID에 관하여 (feat. 분산 환경에서의 고유한 ID)

안녕하세요, 오늘은 정말 1초에 정말 수많은 사진들이 업로드되는 인스타그램의 샤딩과 ID에 관한 내용에 대해서 다뤄볼까 합니다. 

 

인스타그램의 공식 엔지니어링 블로그에 소개된 글을 번역합니다. 자세한 내용은 아래의 원문을 참고해주세요.

https://instagram-engineering.com/sharding-ids-at-instagram-1cf5a71e5a5c

Sharding & IDs at Instagram

 

Sharding & IDs at Instagram

초당 25개와 90개의 좋아요보다 더 많은 양들의 데이터가 인스타그램에 저장됩니다. 우리의 모든 중요한 데이터를 메모리에 저장하고 유저가 빠르게 사용할 수 있도록, 우리는 데이터를 샤딩하기 시작했습니다. 즉, 데이터를 각각 데이터의 일부를 담고 있는 여러개의 버킷에 저장합니다.

 

우리의 애플리케이션 서버는 장고, PostgreSQL로 구동하고 있습니다. 데이터를 샤딩하기로 결정한 뒤의 우리의 첫번째 질문은 PostgreSQL을 주된 데이터 저장소로 지속시킬지 아니면 다른 무언가로 교체해야할 것인지에 대한 것이었습니다. 우리는 다른 몇가지 NoSQL 솔루션을 검토했으나, 궁극적으로 우리의 요구사항에 가장 적합한 솔루션은 PostgreSQL 서버에 데이터를 샤딩하는 방법이라고 결정했습니다.

 

그러나 각 서버 셋트에 데이터를 쓰기전에, 우리는 데이터베이스의 각 데이터의 고유 식별자를 할당하는 방법에 대한 문제를 해결해야 했습니다. (예를 들어, 시스템에 등록된 사진들). 단일 데이터베이스에서 auto-increment를 통해 작동하는 일반적인 솔루션은 더이상 작동하지 않습니다. 데이터가 여러 데이터베이스에 동시에 작성되기 때문이죠. 이 글의 나머지 부분은 해당 문제를 어떻게 해결했는지에 대해서 설명합니다.

 

우선 시작에 앞서, 우리의 시스템에 필요한 필수적인 기능들을 나열했습니다.

1. 생성된 아이디는 시간 순으로 정렬이 가능해야 합니다. (예를 들어, 사진의 ID 값으로만 정렬이 가능해야 합니다.)
2. 아이디는 이상적으로 64비트어야 합니다. (레디스와 같은 곳에서 더 적은 인덱스와 저장공간을 위해서)
3. 가능한한 시스템에서 적은 수의 새로운 "moving parts"가 도입되야 합니다. (아주 소수의 엔지니어만으로 인스타그램을 확장할 수 있었던 가장 큰 부분은, 우리가 신뢰하는 가장 간단하고 이해하기 쉬운 솔루션을 택했기 때문입니다.)

"moving parts" : 우리가(인스타그램)이 제어할 수 없는 제 3자 서비스와 같은 것을 일컫는 의미로 사용되는 것 같습니다. 즉, 우리의 제어가 가능한 영역을 벗어나는 아키텍처를 최대한 적게 유지함으로써, 소수의 인원으로 인스타그램을 확장할 수 있었다고 의미하는 것 같습니다.

 

기존 솔루션

이미 아이디 생성 문제에 대해서 많은 솔루션이 존재합니다. 우리가 고려한 몇가지 사항은 다음과 같습니다.

 

웹 애플리케이션에서 ID 생성

해당 접근 방식은 ID 생성을 전적으로 애플리케이션에 위임하는 방식입니다. (데이터베이스는 아이디 생성에 책임을 가지지 않음)

예를 들어, Mongo DB의 ObjectId는 12바이트의 길이이고 타임스탬프 값을 첫번째 구성 요소로 인코딩 합니다. 또 다른 인기있는 접근 방식은 UUID 입니다.

 

장점

• 각각의 애플리케이션 스레드는 독립적으로 ID를 생성하고, ID 생성에 실패하는 몇가지 지점들을 최소화합니다.
• 타임스탬프를 ID의 첫번째 구성요소로 사용하는 경우, ID값을 가지고 시간순 정렬이 가능해집니다.

단점

• 일반적으로 합리적인 고유성을 보장하려면 최소 96비트 혹은 그 이상의 저장 공간이 필요합니다.
• 일부 UUID 유형은 완전히 무작위이며 정렬이 불가합니다.

 

전용 서비스를 통한 ID 생성

트위터의 Snowflake는 Apache ZooKeeper를 상요하여 노드를 조정한 후 64비트의 유니크한 ID를 생성하는 서비스입니다.

 

장점

• Snowflake의 Id는 64비트 입니다. 이는 UUID 크기의 절반입니다.
• 시간을 첫번째 구성요소로 사용하여 정렬 가능한 상태를 만들 수 있습니다.
• 노드가 죽어도 살아남을 수 있는 분산처리 시스템입니다.

단점

• 우리의 아키텍처에 더 많은 복잡성과 "moving parts"(ZooKeeper, Snowflake Servers)가 추가됩니다.

 

DB 티켓 서버

데이터베이스의 auto-increment 기능을 사용하여 고유성을 강화합니다. Flickr(온라인 사진 공유 커뮤니티)가 이러한 접근 방식을 사용합니다. 하지만 SPOF를 피하기 위해서는 두개의 ticket DB를 사용합니다. (홀수, 짝수)

 

장점

• DB는 이해되기 쉽고, 예측이 가능한 확장 요소들을 가지고 있습니다.

단점

• 결국에는 쓰기시에 병목이 발생할 수 있습니다. (물론, Flickr는 대규모 규모에서도 문제가 없다고 이야기합니다.)
• DB 티켓 서버를 관리하기 위한 추가적인 2대의 머신 혹은 EC2 서버가 필요합니다.
• 단일 DB 티켓 서버를 사용하면 SPOF가 발생합니다. 여러개의 DB를 사용하면 시간이 지남에 따라 더이상 정렬 가능하다고 보장할 수 없습니다.

위의 모든 접근 방식들 중에서 트위터의 Snowflake가 가장 합리적으로 느껴졌지만, ID 서비스를 실행하는데 필요한 추가적인 복잡성이 단점이었습니다. 대신에 개념적으로 유사한 접근 방식을 가지고 PostgreSQL 내부에서 구현했습니다.

 

우리(인스타그램)의 솔루션

우리의 샤딩 시스템은 적은 수의 물리적 샤드에 매핑되는 수천개의 논리적 샤드들로 구성됩니다. 이 접근 방식을 사용하면, 데이터를 다시 re-bucket 할 필요 없이 한 데이터베이스에서 다른 데이터베이스로 논리적 샤드 세트를 이동하는 것이 가능합니다. 따라서 몇대의 데이터베이스 서버로 시작하여 결국에는 더 많은 데이터베이스로 옮기는 것이 가능해집니다.

우리는 이를 쉽게 관리할 수 있도록 Postgres의 스키마 기능을 사용했습니다.

 

스키마(개별 테이블의 SQL 스키마와 혼동X)는 Postgres의 논리적 그룹화 기능입니다. 각 Postgres의 DB에는 여러개의 스키마가 있을 수 있으며, 스키마에는 하나 이상의 테이블이 포함될 수 있습니다. 테이블 이름은 DB별로가 아닌 스키마 별로 고유해야 하며 기본적으로 Postgres는 모든 것을 "public"이라는 스키마에 배치합니다.

 

각 논리적 샤드는 우리 시스템의 Postgres 스키마이며, 샤딩된 테이블은 각 스키마내에 존재합니다.

 

Postgres의 내부 프로그래밍 언어인 PL/PGSQL을 사용하여 Postgres의 자동 증가 기능을 사용하여 각 샤드내의 테이블에 아이디 생성을 위임했습니다.

 

각 ID는 다음과 같이 구성됩니다.

• 41비트의, 밀리초 단위의 시간 (사용자 지정 epoch(시대)에 따라 41년 동안의 ID값 제공)
• 13비트의, 논리적 샤드 ID
• 10비트의, auto-incrementing 시퀀스, with 1024 모듈러. (이는 샤드당, 밀리초당 1024개의 ID를 생성할 수 있음을 의미합니다.)

예를 들어 보겠습니다. 지금이 2011년 9월 9일 오후이 5시이고, 'epoch'가 2011년 1월 1일에 시작한다고 가정해 보겠습니다. 시대가 시작된 이후 1387263000 밀리초가 지났으므로 ID를 시작하려면 다음을 입력합니다.

 

왼쪽 시프트로 41비트를 채웁니다.

# 64는 41+13+10 비트의 총합
id = 1387263000 << (64-41)

 

다음으로, 데이터가 삽입될 특정한 샤드 ID를 가져옵니다. 사용자 아이디별로 샤딩한고 논리적 샤드가 2000개 존재한다고 가정해 보겠습니다. 만약 사용자 ID가 31341 이면 31341 % 2000 -> 1341 입니다. 

 

다음의 13비트를 이 값으로 채웁니다.

# 64는 41+13+10 비트의 총합
id |= 1341 << (64-41-13)

 

마지막으로 auto increment 시퀀스(이 시퀀스는 각 스키마의 각 테이블에 고유한 값)의 다음 값을 선택하여 나머지 비트를 채웁니다. 이 테이블에 대해 이미 5,000개의 ID를 생성했다고 가정해 보겠습니다. 다음 시퀀스의 값은 5,001 입니다. 이 값을 1024로 모듈러 연산하여 채웁니다.

# 64는 41+13+10 비트의 총합
id |= (5001 % 1024)

 

이제 INSERT의 일부로 RETURNING 키워드를 사용하여 애플리케이션 서버에 반환할 수 있는 ID가 있습니다.

 

다음은 이 모든 작업을 수행하는 PL/PGSQL의 예시입니다.

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...
  )

 

이게 전부입니다! 애플리케이션 전반에 걸쳐진 고유한 기본키를 얻었습니다! (또한, 더 쉬운 매핑을 위한 샤드 ID도 포함되어 있습니다)

우리는 이 접근 방식으로 프로덕션에 적용해 왔으며 지금까지의 결과에 만족하고 있습니다.

 

 

여기까지 인스타그램이 분산된 서버에서 고유한 아이디를 생성해내기 위한 방법에 대한 글을 번역해보았습니다. 다른 매체를 통해 분산 환경에서 고유한 아이디를 만들어내는 방법을 본적이 있었는데, PostgreSQL의 내부 기능을 사용하는 방법은 신선했습니다.

 

물론, Snowflake의 접근 방식과 굉장히 유사하지만 비슷한 개념을 다른 도구로 풀어내는 방법이 인상적이었습니다.

 

읽어주셔서 감사합니다 :)