인스타그램에서 ID를 만드는 방법을 직접 구현해보자

인스타그램은 서비스 시작 1년만에 1400만 명의 이용자를 모았습니다. 놀라운 점은 단 3명의 엔지니어가 이를 운영했다는 것인데요. 이번 글에서는 인스타그램에서 사용한 ID 생성 전략에 대해 알아보고 JPA를 이용하여 실제로 구현해보겠습니다.

이 글은 MySQL 8, Hibernate 6.2를 기준으로 작성되었습니다. 참고 자료는 다음과 같습니다.

• How Instagram scaled to 14 million users with only 3 engineers - Engineer’s Codex
• Sharding & IDs at Instagram - Instagram Engineering
• 데이터 베이스의 자동증가 값을 기본키로 사용할 수 없을때는? - 우아한기술블로그
• Spring Boot MySQL Database Initialization Error with Stored Procedures - Stack Overflow

인스타그램의 상황

인스타그램이 단 3명으로 1400만 명의 서비스를 운영할 수 있었던 비결은 뭘까요? 바로 대원칙 3가지를 만들어 따르는 것이었습니다. 대원칙 3가지는 다음과 같습니다.

1. 아주 간단하게 유지하라.
2. 바퀴를 재발명 하지마라.
3. 가능한 입증되고 안정적인 기술을 사용하라.

이러한 대원칙을 바탕으로 인스타그램이 지나온 발자취를 따라가보겠습니다.

인스타그램이 마주한 문제

서비스 이용자가 점점 많아짐에 따라 인스타그램에서 초당 25개 이상의 사진과 90개 이상의 좋아요가 생성되었습니다. 처리 속도를 높이기 위해 인스타그램은 데이터를 모두 메모리에 저장하기로 했습니다. 또, 이를 위해 데이터를 여러 개의 버킷으로 나누어 저장하는 데이터 샤딩을 시작했는데요.

효과적인 데이터 처리를 위해 NoSQL으로 전환을 고민하였으나 결국 기존에 사용중인 PostgreSQL을 유지하기로 결정했습니다. 하지만 AUTO_INCREMENT 기반의 기존 PK 생성 방식으로는 여러 데이터베이스를 사용할 때 PK가 중복되는 문제가 있었습니다. 그래서 인스타그램은 새로운 PK 생성 전략을 찾습니다.

PK 요구사항

또 새로 만들 PK는 식별자 역할 뿐만아니라 다음과 같은 추가 요구사항을 만족해야 했습니다.

• ID 값만 사용하여 시간 순으로 정렬할 수 있어야한다.
• Redis와 같이 저장 공간이 중요한 곳에서도 사용할 수 있도록 64bit의 크기를 갖는다.
• 3명이서 개발하기 때문에 이해하기 쉽고 간단해야한다.

인스타그램이 고려했던 솔루션들

“바퀴를 재발명 하지마라”는 대원칙을 지키기 위해 인스타그램은 잘 알려진 ID 생성 전략들을 분석했습니다. 이들의 특징과 장단점에 대해 알아보겠습니다.

DB 티켓 서버 전략도 적혀있었지만 생략하였습니다.

웹 애플리케이션 기반

첫 번째 방법은 웹 애플리케이션에서 UUID를 이용하여 ID를 생성하는 전략이었습니다. 장점은 다음과 같습니다.

• 데이터베이스에 의존하지 않고 애플리케이션 쓰레드에서 독립적으로 ID를 생성할 수 있다.

반면 단점은 다음과 같습니다.

• UUID 값은 완전 무작위이다.
• UUID를 저장하기 위해 128bit가 필요하며 시간 정보를 포함하면 더 커진다.

ID 생성 서비스

두 번째 방법은 트위터의 Snowflake와 같은 ID 생성 서비스를 이용하는 전략이었습니다. 장점은 다음과 같습니다.

• Snowflake에서 생성하는 ID의 크기는 64bit이다.
• ID에 시간 정보를 포함할 수 있다.
• 분산형 시스템으로부터 높은 가용성을 보장한다.

단점은 다음과 같습니다.

• ZooKeeper와 Snowflake 서버를 운영해야하므로 관리 포인트가 늘어난다.

인스타그램의 결정

트위터의 Snowflake가 가장 많은 요구사항을 만족했지만 관리 포인트가 늘어난다는 치명적인 단점이 있었습니다. 3명이서 서비스를 운영하기 위해선 “아주 간단하게 유지하라”를 지켜야했기 때문입니다. 그래서 인스타그램은 Snowflake의 개념을 따와 이를 PostgreSQL에서 처리하도록 새로 만들었습니다.

인스타그램의 ID 생성 전략

인스타그램은 64비트를 세 부분으로 나누어 ID를 생성하기로 설계하였습니다.

• 41비트: 서비스를 시작한 시간으로부터 흐른 밀리세컨드 시간
• 13비트: 논리적 샤드 ID
• 10비트: 자동으로 증가하는 시퀀스 값

41비트

상위 41비트는 현재 시간에서 서비스 시작 시간을 뺀 값을 나타냅니다. 41비트로 표현할 수 있는 최대 값은 2,199,023,255,552로 이는 약 70년의 시간을 표현할 수 있습니다.

예를 들어 서비스를 시작한 시간이 2023년 01월 01일 자정이고 현재 시간이 2023년 10월 3일 자정이라면 다음과 같이 계산합니다.

epoch_milli = 1696291200000 - 1672531200000 = 23760000000

계산한 값을 상위 41비트에 저장하기 위해 다음과 같이 비트 연산을 수행합니다.

id = 23760000000 << (64 - 41)

13비트

그 다음 상위 13비트는 논리적인 샤드 ID를 나타냅니다. 13비트로 표현할 수 있는 최대 값은 8192이므로 최대 8192의 논리적 샤드를 가질 수 있습니다.

샤드 ID를 결정하는 방법은 많지만 user_id와 샤드 개수의 모듈러 연산으로 구한다고 했을 때, 샤드 개수가 2,000개이고 user_id가 31341인 경우 샤드 ID는 다음과 같이 계산합니다.

shard_id = 31341 % 2000 = 1341

계산한 값을 13비트에 저장하기 위해 다음과 같이 비트 연산을 수행합니다.

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

10비트

마지막 10비트는 자동으로 증가하는 시퀀스 값을 나타냅니다. 현재 서비스에서 생성된 전체 글이 5000개일 경우 새로 생성되는 글의 시퀀스 값은 5001입니다. 이때 시퀀스 값을 10비트로 표현하기 위하여 모듈러 연산을 합니다.

seq = 5001 % 1024 = 905

계산한 값을 10비트에 저장하기 위해 다음과 같이 비트 연산을 수행합니다.

id |= 905

ID 중복의 가능성

인스타그램이 새롭게 만든 전략을 이용하면 1ms당 8192개의 샤드에 대해 1024개의 ID를 중복 없이 생성할 수 있습니다. 이는 서비스 관점에선 1초당 8,388,608,000개의 ID를, 샤드의 관점에선는 1,024,000개의 ID를 생성할 수 있기 때문에 ID의 중복의 가능성의 거의 없다고 볼 수 있습니다.

실제로 구현해보자

그럼 인스타그램 ID 생성 전략을 MySQL과 JPA를 이용하여 실제로 구현해 보겠습니다.

Sequence 만들기

ID 하위 10비트에 사용되는 값을 위해 시퀀스를 사용해야합니다. 그러나 MySQL에서는 시퀀스가 존재하지 않기 때문에 직접 구현해야합니다.

CREATE TABLE sequences
(
    name     varchar(32) PRIMARY KEY,
    next_val BIGINT NOT NULL DEFAULT 1
);

위와 같이 이름과 다음 시퀀스 값을 컬럼으로 갖는 시퀀스 테이블을 정의합니다. 이후 post에서 사용할 시퀀스를 추가합니다.

INSERT INTO sequences (name) VALUES ('post_seq');

ID를 생성하는 프로시저 만들기

다음으로 실제 비트 연산을 통해 64비트의 ID를 생성하는 프로시저를 정의합니다.

DROP PROCEDURE IF EXISTS generate_post_id;

CREATE PROCEDURE generate_post_id(IN user_id BIGINT, OUT post_id BIGINT)
BEGIN
    SET @service_start_time = UNIX_TIMESTAMP('2023-01-01 00:00:00.000');
    SET @shard_count = 1024;
    SET @sequence_name = 'post_seq';

    /* 부호(1bit) + 시간(43bit, 약 278년), + 샤드 ID (10bit)*/
    SET post_id = (
            FLOOR((UNIX_TIMESTAMP(NOW(3)) - @service_start_time) * 1000) << 20 |
            (user_id % @shard_count) << 10
        );

    /* 시퀀스 값 가져오기 (10bit) */
    SET post_id = post_id | (SELECT next_val % 1024 FROM sequences WHERE name = @sequence_name);
    UPDATE sequences SET next_val = next_val + 1 WHERE name = @sequence_name;
END;

Java에서 ID 값을 Long으로 사용할 것이기 때문에 최상위 1비트는 부호 비트가 사용합니다. 또, 단순하게 하기 위해 샤드 ID와 시퀀스 비트를 10bit로 통일하였습니다.

JPA 엔티티 정의

이제 JPA 프로젝트로 넘어와 글을 나타내는 Post 엔티티를 다음과 같이 정의합니다.

@Entity
public class Post {

		@Id
    @GenericGenerator(
        type = PostIdGenerator.class,                // 1
        name = "post_id_generator"                   // 2
    )
    @GeneratedValue(generator = "post_id_generator") // 3
    private Long id;

    @Column(name = "user_id")
    private Long userId;

		/* ... */
}

JPA에서 프로시저를 이용하여 ID를 생성하려면 커스텀 ID 생성 클래스를 별도로 정의하여 사용해야합니다. @GenericGenerator를 이용하면 사용할 클래스 정보를 설정할 수 있는데요. 코드의 각 번호는 다음과 같은 역할을 합니다.

1. PostIdGenerator.class를 커스텀 ID 생성 클래스로 사용합니다.
2. PostIdGenerator의 이름을 “post_id_generator”로 지정합니다.
3. ID를 생성할 때 “post_id_generator”라는 이름을 갖는 커스텀 ID 생성기를 사용합니다.

Hibernate 6.2 미만 버전에선 type이 아닌 strategy로 클래스를 지정해주면 됩니다.

커스텀 ID 생성기 정의

마지막으로 프로시저를 실행하여 ID를 생성하는 커스텀 ID 생성 클래스를 정의합니다.

public class PostIdGenerator implements IdentifierGenerator {

    private static final String PROCEDURE_NAME = "generate_post_id";
    private static final String PROCEDURE_PARAM_NAME = "user_id";
    private static final String PROCEDURE_RETURN_NAME = "post_id";

    @Override
    public Object generate(
        final SharedSessionContractImplementor session,
        final Object object
    ) {
        try (final ProcedureCall procedureCall = session.createStoredProcedureCall(PROCEDURE_NAME)) {
            /* 프로시저 IN 인자 변수명 설정 */
            procedureCall.registerParameter(PROCEDURE_PARAM_NAME, Long.class, ParameterMode.IN);
            /* 프로시저 OUT 리턴 변수명 설정 */
            procedureCall.registerParameter(PROCEDURE_RETURN_NAME, Long.class, ParameterMode.OUT);

            /* IN 인자 값을 Post.userId로 설정 */
            final Post post = (Post) object;
            procedureCall.setParameter(PROCEDURE_PARAM_NAME, post.getUserId());

            /* 프로시저 실행 후 반환 값을 PK 값으로 반환 */
            return procedureCall.getOutputs().getOutputParameterValue(PROCEDURE_RETURN_NAME);
        }
    }
}

프로시저에 사용할 IN, OUT 변수명을 설정하고, Post 엔티티의 userId를 프로시저의 매개변수로 전달하여 실행 후 반환 된 값을 ID로 반환합니다.

제대로 만들었을까?

열심히 만든 코드가 잘 동작하는 지 테스트를 작성하여 정상 동작 여부와 성능을 테스트해보겠습니다.

정상 동작 테스트

우선 의도대로 동작하는 지 검증하는 테스트 코드를 작성하였습니다.

@Test
@DisplayName("PK를 시간 + 샤드 + 시퀀스의 조합으로 생성한다.")
void generateInstagramId() {
    /* given */
    final long userId = 1801;
    final Post post = new Post(userId);

    /* when */
    entityManager.persist(post);

    /* then */
    final Long id = post.getId();
    final LocalDateTime createdAt = extractLocalTimeDate(id);
    assertAll(
        () -> assertThat(createdAt.isAfter(SERVICE_START_DATE_TIME)).isTrue(),
        () -> assertThat(createdAt.isBefore(LocalDateTime.now())).isTrue(),
        () -> assertThat(extractShardId(id)).isEqualTo(userId % LOGICAL_SHARD_MAX_COUNT),
        () -> assertThat(extractSequence(id)).isEqualTo(1L)
    );
    System.out.println("Generated id = " + id);
}

위 테스트 코드는 생성된 ID 값을 역으로 비트 연산하여 64비트가 시간, 샤드 ID, 시퀀스 값으로 구성되었는지 검증합니다.

성능 테스트

그렇다면 AUTO_INCREMENT 전략과 새로운 전략의 성능은 어느정도 차이날까요? ID 생성 전략이 GenerationType.IDENTITY인 엔티티를 정의하고 이를 비교해봤습니다.

@Test
@DisplayName("AUTO_INCREMENT를 사용할 때와 속도 비교")
void comparisonSpeed() {
    /* given */
    final long userId = 1801L;
    final int totalSize = 100;

    /* when */
    final long autoIncrStart = System.currentTimeMillis();
    for (int i = 0; i < totalSize; i++) {
        final PostAutoIncr post = new PostAutoIncr(userId);
        entityManager.persist(post);
        entityManager.flush();
    }
    final long autoIncrEnd = System.currentTimeMillis();

    final long instaIdGenStart = System.currentTimeMillis();
    for (int i = 0; i < totalSize; i++) {
        final Post post = new Post(userId);
        entityManager.persist(post);
        entityManager.flush();
    }
    final long instaIdGenEnd = System.currentTimeMillis();

    /* then */
    System.out.println("Elapsed instaIdGen time = " + (instaIdGenEnd - instaIdGenStart) + "ms");
    System.out.println("Elapsed autoIncr time = " + (autoIncrEnd - autoIncrStart) + "ms");
}

첫 번째 사진은 100개를 생성했을 때, 두 번째 사진은 100,000개를 생성했을 때 시간입니다. 인스타그램 ID 생성 전략이 약 3~4배 느린것을 확인할 수 있습니다.

좋은건가…?

새로운 ID 생성 전략을 적용함으로써 4배에 가까운 성능 저하가 발생했습니다. 과연 좋은걸까요? 기존의 AUTO_INCREMENT 방식은 하나의 데이터베이스에서 모든 데이터를 저장해야합니다. 그러나 새로운 방식은 샤딩을 통해 여러 데이터베이스에서 나누어 저장할 수 있습니다.

예를 들어 데이터베이스를 4대로 나누어 구축한다면 4배가 빨라지므로 AUTO_INCREMENT와 동일한 성능을 보장하면서 인스타그램 ID 생성 전략의 요구 사항을 지원하는 PK를 생성할 수 있습니다. 그러나 샤딩을 적용함으로써 애플리케이션 코드의 복잡도가 늘었으며 MySQL의 프로시저에 의존적인 코드가 되었습니다.

처음에 인스타그램의 ID 생성 전략의 아이디어를 봤을 때 모든 것을 해결하는 만능열쇠인 것처럼 보였으나 실제로 구현하니 복잡도, 성능 측면에서 아쉬운 점이 발생했습니다. 따라서 현재 우리가 처한 문제 상황에서 데이터 샤딩이 반드시 필요할까? Scale-up과 같은 다른 방법으로는 해결할 수 없을까? 와 같은 의문을 갖고상황에 맞는 해결 방법을 찾는 것이 중요하다고 생각합니다.

마무리하며

이번 글에서는 인스타그램의 ID 생성 전략을 알아보고 MySQL과 JPA를 이용하여 실제로 구현해보았습니다. 이번 글을 작성하며 정말 많은 것을 배울 수 있었는데요. 여러모로 다양한 인사이트를 깨칠 수 있었던 경험이었습니다.

특히 3명의 엔지니어로 인스타그램을 운영할 수 있었던 대원칙 3가지를 철저하게 지키는 것과 문제를 해결하기 전 요구사항 3가지를 명확하게 정의하는 모습이 인상적이었습니다. 또 훌륭한 아이디어가 있더라도 이를 구현하는 것도 쉬운 일은 아니라는 것을 느꼈고, 성능 테스트를 진행하며 역시 은탄환은 없다라는 것도 다시 한 번 느꼈습니다.

이 글에서 사용한 코드는 이곳에서 확인하실 수 있습니다.