이 글은 인스타그램(Instagram)의 엔지니어링 블로그에 작성된 글을 번역한 것이다. 원문은 여기.

최근 유사한 문제로 고민하다가 발견한, 많은 도움을 받을 수 있었던 글.

또 다른 번역글도 있으니 참고하시길.





Sharding & IDs at Instagram


인스타그램에는 매 초당 25개의 사진과 90개의 Like 정보가 등록된다. 우리는 이런 중요한 정보들이 메모리에 적합하게 적재되고 사용자들이 빠르게 사용할 수 있도록 만들기 위해 데이터를 샤딩(Sharding)하고 있다. 다시 말하면 데이터들을 여러 개의 작은 버킷으로 나누고 각각의 버킷은 데이터의 일부를 저장하는 형태이다.

우리의 애플리케이션 서버는 DJango로 구현되어 있으며 백엔드 데이터베이스 서버로 PostgreSQL을 사용하고 있다. 데이터를 샤딩하기로 결정한 이후 우리가 가진 첫 번째 고민은 주 데이터 저장소로서 PostgreSQL을 그대로 활용할 것인지 아니면 다른 것으로 변경할 것인지 여부를 결정하는 것이었다. 몇 가지 NoSQL 솔루션을 검토해 봤지만 현재 우리에게 가장 적합한 솔루션은 여러 대의 PostgreSQL 서버에 데이터를 샤딩하는 것이라는 결론에 도달했다.

그러나 데이터를 이들 서버에 나누어 기록하기에 앞서 우리는 데이터베이스 내에 분산될 각각의 데이터(예를 들면 우리의 시스템으로 등록되는 각 사진들)를 위한 유일한 식별자를 할당해야 하는 이슈를 해결해야만 했다. 동시에 여러 데이터베이스에 데이터가 추가되는 환경에서는 단일 데이터베이스에서 동작하는 해결책 - 예를 들면 데이터베이스의 자동 증가 기본 키 기능을 사용하는 등 - 은 올바른 해결책이 될 수 없었다. 이 블로그의 내용은 이와 같은 이슈를 우리가 어떻게 해결했는지를 설명한다.

시작하기에 앞서 우리는 시스템의 기본적인 요구 사항을 다음과 같이 정리했다.

  1. 생성된 ID는 반드시 시간 순으로 정렬이 가능해야 한다 (예를 들어 모든 사진 ID는 사진에 대한 추가 정보를 조회하지 않고도 정렬이 가능해야 한다).
  2. ID는 64비트여야 한다(인덱스의 크기를 줄이고 시스템에 적용된 Redis와 같은 더 나은 저장소를 지원할 수 있다).
  3. 우리 시스템은 새로운 시스템 컴포넌트의 도입을 최소화해야 한다. 겨우 몇 명의 엔지니어로 인스타그램의 확장성을 확보하기 위해서는 우리가 신뢰하는 간결하며 이해하기 솔루션으로 구성되어야 한다.

기존의 솔루션

이미 ID 생성 문제에 대한 해결책은 여러 가지가 존재한다. 이들 중 우리가 고려해 본 방법은 다음과 같다.

웹 애플리케이션에서 ID를 생성하는 방법

이 방법은 ID 생성을 데이터베이스가 아닌 애플리케이션에 완전히 위임하는 방식이다. 예를 들어 몽고DB의 ObjectId는 12바이트 길이의 인코딩된 타임스탬프를 첫 번째 컴포넌트로 사용한다. 또 다른 방법은 UUID를 사용하는 방법이다.

장점:
  1. 각각의 애플리케이션 스레드가 ID를 독자적으로 생성하기 때문에 ID 생성의 실패와 병목 현상을 최소화할 수 있다.
  2. ID의 첫 번째 컴포넌트로 타임스탬프를 사용하면 ID를 시간 순으로 정렬할 수 있다.
단점:
  1. 유일성을 보장하기 위해서는 통상 더 많은 저장 공간(96비트 혹은 그 이상)이 필요하다.
  2. 일부 UUID 타입은 완전히 랜덤하게 만들어져 본질적으로 정렬이 불가능하다.

독립된 서버에서 ID를 생성하는 방법

아파치 주키퍼(ZooKeeper)를 사용하는 트위터의 Snowflake와 같은 Thrift 서비스를 이용하여 64비트의 유일한 ID를 생성한다.

장점:
  1.  Snowflake의 ID는 64비트이며 UUID의 절반에 지나지 않는다.
  2. 정렬을 위해 시간을 ID의 첫 번째 컴포넌트로 사용할 수 있다.
  3. 일부 노드가 다운되더라도 사용 가능한 분산 시스템이다.
단점:
  1. 복잡도가 증가하며 시스템 아키텍처 내의 구성 요소가 증가하게 된다 (ZooKeeper, Snowflake 서버 등)

DB 티켓 서버를 활용하는 방법

이 방법은 데이터베이스의 자동 증가 기능을 이용하여 유일성을 확보하는 방법이다. 플리커(Flickr)가 이 방식을 사용하지만 두 개의 티켓 DB(하나는 홀수, 하나는 짝수를 담당)를 통해 SPOF(Single Point of Failure, 시스템 컴포넌트 중 하나가 다운됨으로서 전체 시스템이 마비되는 현상)을 해결하고 있다.

장점:
  1.  DB는 이미 친숙하며 확장에 대한 예측이 가능하다.
단점:
  1. 결과적으로 쓰기 병목이 발생할 수 있다 (플리커에서 이런 현상을 경험했지만 대규모 서비스에서는 큰 이슈가 아닐 수 있다).
  2. 관리해야 할 머신(혹은 EC2 인스턴스)이 증가한다
  3. 단일 DB를 사용하면 SPOF의 근원이 될 수 있다. 여러 DB를 사용하면 시간으로 정렬 가능한 ID의 생성을 보장할 수 없다.
이상의 방법들을 검토해 본 결과 트위터의 Snowflake가 우리의 요구사항에 가장 적합했지만 ID 서비스를 위해 시스템의 복잡도가 증가하는 것이 마음에 걸렸다. 결국 우리는 PostgreSQL을 통해 이와 유사한 컨셉의 방법을 직접 구현하기로 결정했다.

우리의 해결책

우리의 샤딩 시스템은 수천 개의 '논리적' 샤드로 구성되며 각각의 논리적 샤드는 보다 적은 수로 구성된 물리적 샤드에 매핑된다. 이렇게 함으로써 몇 대의 데이터베이스 서버만으로 샤드를 구성할 수 있었으며 향후 데이터를 새로운 버켓으로 이동할 필요없이 단순히 논리적 샤드를  다른 데이터베이스 서버로 이동하는 것만으로 샤드를 확장할 수 있게 되었다. 또한 PostreSQL의 스키마 기능을 이용하여 손쉽게 스크립팅과 관리가 가능하도록 구성하였다.

스키마(개별 테이블에 대한 SQL 스키마와 혼동하지 않기를 바란다)는 PostgreSQL이 제공하는 논리적 그룹화 기능이다. 각각의 PostreSQL DB는 여러 개의 스키마를 가질 수 있으며 각각의 스키마는 하나 이상의 테이블을 가질 수 있다. 테이블 이름은 DB가 아닌 스키마 별로 유일해야 하며 기본적으로 PostreSQL은 이 모든 것을 'public'이라는 이름의 스키마를 통해 관리한다.

앞서 이야기한 각각의 '논리적' 샤드란 우리의 시스템 내에서는 Postgres 스키마이며 샤드된 각 테이블(예를 들면 사진 데이터들)은 각 스키마에 위치하게 된다.

ID의 생성은 Postgres가 제공하는 자동 증가 기능과 내장 프로그래밍 언어인 PL/PSGSQL을 이용하여 각 샤드 내의 각 테이블에서 담당한다.

각 ID는 다음과 같이 구성된다.
  • 밀리 초 단위의 시간을 위한 41비트(41년을 사용할 수 있는 ID를 생성할 수 있다).
  • 논리적 샤드 ID를 표현하기 위한 13비트
  • 자동 증가 값을 1024로 나눈 나머지 값을 표현하기 위한 10비트. 이는 샤드 당 및 초당 1024개의 ID를 생성할 수 있음을 의미한다.
예를 들어 설명해 보자. 현재 시간이 2011년 9월 9일 오후 5시 정각이며 시스템이 2011년 1월 1일부터 가동되기 시작했다고 가정해보자. 그렇다면 현재는 시스템 가동 이후 1387263000 밀리 초가 지난 시간이며 따라서 ID의 처음 41비트는 다음과 같은 값이 채워진다.

id = 1387263000 << (64 - 41)


다음으로 추가할 데이터의 샤드 ID를 결정해야 한다. 데이터를 사용자 ID를 기준으로 샤딩하며 2000개의 논리적 샤드가 존재하고 사용자 ID가 31341이라고 가정하면 샤드 ID는 31341 % 2000 = 1341이 된다. 따라서 ID의 다음 13비트는 이 값으로 채워진다.
id |= 1341 << (64 - 41 - 13)

마지막으로 자동 증가 값(이 값은 각 스키마 내의 각 테이블마다 유일하다)을 얻어 나머지 비트를 채워야 한다. 이미 테이블에  5,000개의 ID가 생성되어 있다고 가정하면 다음 값은 5001이며 이 값을 1024로 나누어(그러면 10비트로 채우기에 적당하다) 나머지 비트를 다음과 같이 채우면 된다.
id |= (5001 % 1024)

이제 ID가 완성되었으므로 이 값을 RETURNING 키워드를 통해 애플리케이션 서버로 리턴하면 된다.

아래의 코드는 완성된 PL/PGSQL 코드이다(예제 스키마는 insta5이다).
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(),
    ...테이블의 나머지 스키마...
)

이로서 끝이다. 기본 키는 애플리케이션 내에서 완전히 유일하다(게다가 샤드 ID를 포함하고 있어 매핑이 더욱 쉬워졌다). 이 방법을 실제 서비스에 적용해 본 결과는 매우 만족스러웠다. 이같은 확장성에 대한 해결책을 마련하는데 흥미가 있다면 우리 회사에 지원해 보기 바란다.

Mike Krieger, co-founder


















Posted by 웹지니 트랙백 1 : 댓글 14