snowflake 기반 Id 생성 - ttasjwi/board-system GitHub Wiki

개요

• 데이터베이스에 데이터를 저장할 때 고유 식별자(PK)가 필요하다.
• PK 는 어떤 방식으로 생성하는게 좋을까?

---

자연키 vs 인공키

• 자연키 (Natural Key): 현실 세계에서 의미를 갖는 값으로 구성된 식별자
  • 예: 주민등록번호, 학번, 이메일, 전화번호 등
• 인공키 (Surrogate Key): 현실적 의미와 무관하게 데이터베이스 내부에서 인위적으로 생성한 식별자
  • 예: Auto Increment 숫자, UUID, Snowflake ID 등

---

자연키의 문제점

• 현실 변화에 취약
  • 예: 주민등록번호는 법/정책 변경으로 수집이 제한되거나 변경 가능성이 있음
  • 현실 속 식별자는 시간이 지나면서 변하거나 폐지될 수 있음
• 고유성 보장 실패 가능성
  • 처음엔 중복되지 않던 자연키가 향후 중복될 가능성도 존재 (예: 이메일 재사용, 학번 재할당 등)
• 스키마 의존성 증가
  • 자연키를 기본키로 설정하면 변경 시 관계형 데이터 구조 전체를 수정해야 할 수 있음 (외래키 제약 등)
• 결론
  • 이러한 이유로, 현실 세계와 무관한 불변의 인공키를 기본키(PK)로 사용하는 것이 일반적으로 안전하고 유연함
  • 자연키는 고유 제약조건(UNIQUE) 으로만 관리하고, 기본키로는 인공키 사용이 권장됨

---

인공키 종류

• DataBase Auto Increment 방식
  • 키 생성을 DataBase 에서 해야하므로, 애플리케이션 로직이 DataBase 의존성을 가진다. (최초에 Id 가 없는 문제)
  • 향후 데이터베이스를 물리적/논리적으로 분리해서(샤딩) 관리할 경우 PK 가 중복될 수 있어서 식별자 유일성이 보장되지 않을 수 있다.
  • 클라이언트 측에 노출하면 보안상 문제가 될 여지가 있다. (예: 가입했더니 1000번 회원 -> 전체 회원이 1000명정도 있다는 것을 유추 가능)
  • 그래도 간단하다는 장점이 있다.
  • 순차적으로 생성되므로, 중간 삽입이 되지 않아 B+ Tree 재구성, 페이지 분할 드으이
• 유니크 임의 문자열, 숫자 방식
  • UUID 또는 난수 방식으로 랜덤 데이터를 생성
  • 키 생성을 애플리케이션에서 함으로서, 애플리케이션의 데이터베이스 의존성을 끊어낼 수 있음(이 특징은 아래의 유니크 정렬 문자열, 유니크 정렬 숫자도 공유한다.)
  • 키 생성이 간단하다. (그냥 임의 데이터를 생성하면 된다.)
  • 하지만 랜덤하다는 점때문에 성능저하가 발생할 수 있다.
    • Clustered Index 는 정렬된 상태를 유지한다.
    • 데이터 중간삽입 시, 필요한 인덱스 페이지가 가득찼다면 B+ Tree 재구성 및 페이지 재분할로 디스크 I/O가 증가한다.
    • PK 를 사용한 범위 조회가 필요하다면, 디스크에서 랜덤 I/O 가 발생하기 때문에 순차 I/O 보다 성능이 저하된다.
• 유니크 정렬 문자열
  • 분산환경에 대한 PK 중복 문제 해결
  • 보안 문제 해결
  • 랜덤 데이터에 의한 성능 문제 해결
  • UUID v7, ULID 등의 알고리즘 : 일반적으로 알려진 알고리즘은 128비트를 사용한다.
  • 데이터 크기에 따라 공간 및 성능 효율이 달라진다.
    • Clustered Index 는 PK 를 기준으로 만들어진다.
    • Secondary Index 는 데이터에 접근할 수 있는 포인터를 가지고 있다. (즉, PK 를 가지고 있다.)
    • PK가 크면 클 수록, 데이터는 더 많은 공간을 차지하게 되고, 비교 연산에 의한 정렬/조회에 더 많은 비용을 소모하게 된다.
• 유니크 정렬 숫자
  • 분산환경 pk 중복 문제 해결
  • 보안 문제 해결
  • 랜덤 데이터에 의한 성능 문제 해결
  • snowflake, tsid 등
    • 64비트 사용 (BIGINT)
    • 정렬을 위해 타임스탬프를 나타내는 비트 수의 제한 문제가 있다.
      • 키 생성을 위한 시간적인 한계가 있다. (snowflake 기준 41비트)
      • 문자열 알고리즘에서도 동일한 문제가 있긴한데, 비트수가 많을 수록 이 제한은 덜 할 수 있다.
  • 유니크 정렬 문자열 방식보다 적은 공간을 사용한다.

---

snowflake 키 생성

• X(Twitter)에서 개발
• 분산 시스템에서 고유한 64비트 ID를 생성하는 알고리즘
• [1비트][41비트: 타임스탬프][10비트: 노드 ID][12비트: 시퀀스 번호]
• 분산 환경에서도 중복 없이 순차적 ID 생성하기 위한 규칙
  • 타임스탬프 : 순차성
  • 노드ID : 고유성
  • 시퀀스 번호 : 순차성, 고유성 (동일 시간, 동일 Node 에서 동시에 요청하더라도, 순차성 보장)
• 유니크, 시간 기반 순차성, 분산 환경에서의 높은 성능

/**
 * 고유 식별자 생성을 위한 클래스
 * X (구 Twitter)의 Snowflake 방식 사용
 *
 * 64비트 숫자 생성
 * 1비트(사용) + 41비트(시간) + 10비트(현재 애플리케이션의 고유 식별자 : 랜덤) + 12비트(동일 애플리케이션 동시요청시 순번)
 */
class IdGenerator private constructor() {

    companion object {
        private const val UNUSED_BITS: Int = 1
        private const val EPOCH_BITS: Int = 41
        private const val NODE_ID_BITS: Int = 10
        private const val SEQUENCE_BITS: Int = 12

        private const val MAX_NODE_ID: Long = (1L shl NODE_ID_BITS) - 1
        private const val MAX_SEQUENCE: Long = (1L shl SEQUENCE_BITS) - 1

        private val NODE_ID = RandomGenerator.getDefault().nextLong(MAX_NODE_ID + 1)

        // 2025-01-01T00:00:00+0900
        private val START_TIME_MILLIS = 1735657200000

        private var lastTimeMillis = START_TIME_MILLIS
        private var sequence = 0L

        fun create(): IdGenerator {
            return IdGenerator()
        }
    }

    @Synchronized
    fun nextId(): Long {
        // 현재 시간
        var currentTimeMillis = System.currentTimeMillis()

        // 만약 현재 시간이 lastTimeMillis보다 작다면, 시스템 클럭이 역행(rollback)된 것으로 판단하고 예외를 발생.
        if (currentTimeMillis < lastTimeMillis) {
            throw IllegalArgumentException("Invalid Time")
        }

        // 최근 아이디 발급 시점이, 지금 시각과 같을 때(같은 밀리초에서 여러 개의 ID 를 생성하는 경우)
        // 그 안에서 sequence 순번을 매김
        if (currentTimeMillis == lastTimeMillis) {
            // 순서(sequence) 를 1 증가 시키고, 혹시 최대 자리를 초과할 경우를 다시 버림 처리
            sequence = (sequence + 1) and MAX_SEQUENCE
            if (sequence == 0L) {
                currentTimeMillis = waitNextMillis(currentTimeMillis)
            }
        } else {
            sequence = 0
        }

        lastTimeMillis = currentTimeMillis


        return (((currentTimeMillis - START_TIME_MILLIS) shl (NODE_ID_BITS + SEQUENCE_BITS))
                or (NODE_ID shl SEQUENCE_BITS)
                or sequence)
    }

    /**
     * 현재 시간이 lastTimeMillis 와 같거나 그 이전일 경우, lastTimeMillis 보다 더 현재 시간이 커질 때까지 대기
     */
    private fun waitNextMillis(currentTimestamp: Long): Long {
        var currentTimestampVar = currentTimestamp
        while (currentTimestampVar <= lastTimeMillis) {
            currentTimestampVar = System.currentTimeMillis()
        }
        return currentTimestampVar
    }
}

---