[Infra] UUID vs Snowflake ID : 분산 시스템에서 유일한 ID를 만들어보자

 

안녕하세요. 황진성입니다.

 

 오늘은 분산 시스템에서 유일한 ID를 만드는 방법에 대해 알아보겠습니다. 다양한 방법이 있지만, Twitter(X)에서 만든 Snowflake 방식과 UUID 방식을 주로 비교해 보겠습니다. 그리고 ID 생성기를 직접 Kotlin으로 구현하고, Spring Boot, JPA와 통합해서 간단한 블로그 애플리케이션을 만들어보겠습니다.

 

개요

 개발을 하다 보면 유일한 ID를 만들어서 데이터를 관리해야 할 일이 생기기 마련입니다. 대표적으로 관계형 데이터베이스의 테이블 내 레코드 별로 고유 식별자를 가지는 경우가 있습니다. PK로써 테이블 내 고유함을 결정하는 지표가 되며, 인덱스 생성 시에도 활용합니다. 하지만 데이터와 트래픽이 많아진다면 ID 부여 방식에 대해 한 번쯤 고민해봐야 합니다.

 

이 글에서 언급하는 "ID"는 PK와 동일한 의미로 작성했습니다. 하지만 PK가 아닐 때도 있다는 점을 고려해 주세요.

 

auto_increment 잘 쓰고 있는데요?

 보통 규모가 작은 애플리케이션에서는 RDB에서 제공하는 기능인 auto increment 기능을 사용해도 충분합니다. 하지만 대용량 데이터, 대용량 트래픽이 들어오는 상황에서는 적절하지 않을 수 있습니다.

 

MySQL 기준으로 설명해 보자면, auto increment의 ID 채번 방식은 다음과 같은 장단점을 가지고 있습니다.

 

장점

1. ID 생성에 대해 따로 고민하지 않아도 됩니다. 편하게 ID 생성이 가능합니다.
2. DBMS에서 자동으로 최적화를 해줍니다.
3. 정렬된 숫자 형식이기 때문에 순서가 보장되며 ID를 기준으로 정렬이 가능합니다.

단점

1. 유일성을 보장하기 위해 1대의 DB 서버(클러스터를 구성했다면 마스터 노드)에서만 ID 채번을 진행합니다. 따라서 스케일 아웃이 필요할 때 어려움을 겪을 수 있습니다.
2. ID 생성을 오로지 DB에 의존해야 합니다. Insert가 실행된 이후에 PK를 알 수 있습니다. 즉, DB에 강한 의존이 생기게 되며 DB 서버를 한 대만 사용한다면 SPoF가 될 수 있습니다.

 

그렇다면 auto increment의 장점은 수용하고, 단점은 극복할 수 있는 ID 생성 방식이 있을까요?

 

분산 시스템 ID 생성 방법

잘 알려진 분산 시스템 ID 생성 방법으로는 아래와 같이 4가지가 존재합니다.

 

• UUID
• Snowflake ID
• Nano ID
• Ticket server (Flickr example)
• MongoDB Object ID

이 글에서는 가장 많이 사용되는 UUID, Snowflake ID, Nano ID에 대해서 조금 더 자세히 알아보겠습니다.

 

UUID

 UUID는 유일성이 보장되는 128비트의 16진수로 이루어진 숫자입니다. 분산 컴퓨팅 환경에서 고유 식별자뿐만 아니라, 트랜잭션 ID, URI 등 고유한 값을 생성해야 할 때 자주 사용됩니다.

 UUID는 중복될 가능성이 매우 낮기 때문에 충돌에 대한 걱정을 거의 하지 않아도 됩니다. 위키피디아에 나온 말에 잠깐 빌려보겠습니다. 랜덤 방식을 사용하는 UUID 4 버전의 충돌 확률, 즉 동일한 UUID가 생성될 확률을 50%로 끌어올리기 위해서는 2.71경 개의 UUID가 생성되어야 하며, 이는 초당 10억 개의 UUID를 100년 동안 만든 수준이라고 합니다. 즉, 중복될 확률이 0에 수렴됩니다.

 

https://www.javatpoint.com/java-generate-uuid

UUID는 위 사진처럼 총 5개의 부분으로 구성되어 있습니다.

• time_low (8byte) :
  • 시간의 하위 32bit
• time_mid (4byte) :
  • 시간의 중간 16bit
• time_hi_and_version (4byte) :
  • 버전 4bit + 시간의 상위 12bit
• clock_seq_hi_and_res, clock_seq_low (4byte) :
  • 레이아웃과 클럭 시퀀스 조합 (버전에 따라 다르며, 4 버전일 경우에는 랜덤)
• node (12byte) :
  • MAC주소, 네임스페이스, 이름 등을 기반으로 Node ID 생성 (버전에 따라 다르며, 4버전일 경우에는 랜덤)

 

장점

• 분산 시스템, 멀티 인스턴스 등 다양한 환경에서 유일한 ID로 활용 가능하다.
• 쉽게 사용 가능하다.

단점

• 128bit 이므로 크기가 크며, 데이터베이스 인덱스로 활용 시 공간 효율성이 좋지 않다.
• 읽고 이해하기 힘들다.
• 정렬 불가능하다.

 

 

Snowflake ID

 Snowflake ID는 유일성을 보장하는 64bit의 10진수로 이루어진 숫자입니다. 트위터(X)에서는 엄청난 양의 데이터가 매일 생산되고 소비됩니다. 매우 많은 트래픽을 처리하기 위해 분산 컴퓨팅 환경에서 서비스가 진행되는데, 각 데이터에 고유한 ID를 생성하기 위해 Snowflake ID 기법을 고안했습니다.

https://apoorvtyagi.tech/generating-unique-ids-in-a-large-scale-distributed-environment

Snowflake ID는 총 4개의 부분으로 구성되어 있습니다.

• sign (1bit) :
  
  • 음수와 양수를 구별하는 데 사용하며, 큰 용도는 없음
• timestamp (41bit) : 
  • 기원 시각(epoch) 이후로 몇 밀리초가 경과했는지 나타내는 값
• worker_id (10bit) :
  • 데이터 센터 ID 5bit + 서버 ID 5bit : 데이터 센터 max 32개 * 데이터 센터 당 서버 max 32대 = 1,024대까지 가능
  • 고유한 인스턴스 ID 10bit : 인스턴스 1,024대까지 가능
• sequence (12bit) :
  • ID를 생성할 때마다 1만큼 증가시키는 값이며, 1밀리 초가 경과할 때마다 0으로 초기화된다.

 

장점

• 64bit 크기로, GUID 표준에 비해 작은 크기를 가지고 있다.
• timestamp 기반으로 생성되기 때문에 정렬 가능하다.

단점

• timestamp 기반으로 생성되기 때문에 OS별, 인스턴스별 시간 차에 유의해야 한다.
• UUID에 비해 사용 방법이 복잡하다.
• 중앙 집중 ID 채번 방식(Zookeeper 혹은 Thrift 활용)을 사용한다면 네트워크 통신이 필요하며, 관리해야 하는 포인트가 늘어난다.

 

Nano ID

비교적 최근에 개발된 랜덤 기반 ID 생성 라이브러리입니다. UUID의 크기가 너무 커서 줄여주는 목적으로 사용됩니다.

 

UUID와 차이점

• 알파벳 대문자도 활용한다.
• 기본 21바이트이다. 가변 길이다.

 

Java/Kotlin에서는 Maven, Gradle을 통해 라이브러리를 추가해서 사용할 수 있습니다.

여기를 보면 Java에서는 SecureRandom을 사용해서 안전한 랜덤값 기반으로 ID를 생성했다고 말하고 있습니다.

 

최근에는 UUID를 대체하는 곳도 많아졌다고 합니다. 당연하게도 ID의 길이가 짧아지면 경우의 수도 줄어드니 충돌 가능성이 높아집니다. Nano ID는 사용자 용도에 맞게 길이를 자유롭게 조절이 가능합니다. 아래 링크에서 직접 테스트 가능합니다.

https://zelark.github.io/nano-id-cc/

Nano ID CC

 

---

블로그 애플리케이션을 아주 간단하게만 설계하고 개발해 보겠습니다.

 

ID 생성기 활용 - 설계하기

블로그 애플리케이션을 만드는 데, 유저(User)와 게시글(Post)이라는 도메인 2개만 존재한다고 가정해 봅시다.

 

블로그 애플리케이션을 만들기 위해 다음과 같은 점을 고려해야 할 것 같습니다.

• 유저의 ID는 굉장히 높은 고유함을 보장해야 한다.
• 게시글은 ID로 생성 시기를 대략적으로 유추 가능해야 하며, ID로 정렬 가능해야 한다.

따라서,

• 유저는 높은 고유성을 보장해야 하며, ID로 정렬해야 할 일이 없을 것 같기 때문에 UUID로 생성하겠습니다.
• 게시글은 작성 시간 기준으로 정렬해야 할 일이 생길 예정이며, ID 검색 시 인덱스에 유리한 Snowflake ID로 생성하겠습니다.

 

ID 생성기 활용 - 구현하기

개발 환경은 다음과 같습니다.
- Kotlin 1.8.22
- GraalVM JDK 17
- Spring Boot 3.1.2
- Hibernate 6.2.6

이번 포스팅에서 사용된 코드는 여기에서 볼 수 있습니다.

 

 

도메인 클래스 구현

@Table(name = "user")
@Entity
class User(
    @Id
    var id: String,

    var name: String,

    var age: Int
)

@Table(name = "post")
@Entity
class Post(
    @Id
    var id: Long,

    @Lob
    var contents: String,
)

유저는 ID, 이름, 나이 필드를 가집니다. 게시글은 ID, 내용 필드를 가집니다.

 

 

ID 생성기 구현 - UUID

@Component
class UuidGenerator {

    fun nextId() = UUID.randomUUID().toString()
}

UUID 생성기는 Java에서 제공하는 유틸 클래스를 사용합니다. `UUID.randomUUID()` 를 호출하면 랜덤 기반으로 생성되는 UUID, 즉 UUID version 4 방식으로 UUID를 생성해서 반환해 줍니다. 저는 문자열로 사용하기 위해 `toString()` 의 결과를 반환하도록 구현했습니다.

 

조금 더 다양한 버전의 UUID를 사용하고 싶다면, 잘 만들어진 오픈소스를 사용하는 것도 좋은 방법입니다.

https://github.com/f4b6a3/uuid-creator

GitHub - f4b6a3/uuid-creator: A Java library for generating Universally Unique Identifiers (UUID).

 

 

ID 생성기 구현 - Snowflake ID

@Component
class SnowflakeIdGenerator {

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

        private val maxNodeId = (1L shl NODE_ID_BITS) - 1
        private val maxSequence = (1L shl SEQUENCE_BITS) - 1

        private val DEFAULT_CUSTOM_EPOCH = defaultEpochMilli()

        private fun defaultEpochMilli(): Long {
            val initDateTime = LocalDateTime.of(2023, 8, 18, 0, 0, 0)
            return initDateTime.atZone(ZoneId.systemDefault()).toInstant().toEpochMilli()
        }
    }

    private var nodeId: Long = 0
    private var customEpoch: Long = 0

    @Volatile
    private var lastTimestamp = -1L

    @Volatile
    private var sequence = 0L

    constructor(nodeId: Long, customEpoch: Long) {
        require(!(nodeId < 0 || nodeId > maxNodeId)) {
            String.format("NodeId must be between %d and %d", 0, maxNodeId)
        }
        this.nodeId = nodeId
        this.customEpoch = customEpoch
    }

    constructor(nodeId: Long) : this(nodeId, DEFAULT_CUSTOM_EPOCH)

    constructor() {
        this.nodeId = createNodeId()
        this.customEpoch = DEFAULT_CUSTOM_EPOCH
    }

    @Synchronized
    fun nextId(): Long {
        var currentTimestamp = timestamp()

        check(currentTimestamp >= lastTimestamp) { "Invalid System Clock!" }

        if (currentTimestamp == lastTimestamp) {
            sequence = sequence + 1 and maxSequence
            if (sequence == 0L) {
                currentTimestamp = waitNextMillis(currentTimestamp)
            }
        } else {
            sequence = 0
        }
        lastTimestamp = currentTimestamp

        return (currentTimestamp shl NODE_ID_BITS + SEQUENCE_BITS or (nodeId shl SEQUENCE_BITS) or sequence)
    }

    private fun timestamp(): Long {
        return Instant.now().toEpochMilli() - customEpoch
    }

    private fun waitNextMillis(timestamp: Long): Long {
        var currentTimestamp = timestamp
        while (currentTimestamp == lastTimestamp) {
            currentTimestamp = timestamp()
        }
        return currentTimestamp
    }

    private fun createNodeId(): Long {
        var nodeId: Long
        nodeId = try {
            val sb = StringBuilder()
            val networkInterfaces = NetworkInterface.getNetworkInterfaces()
            while (networkInterfaces.hasMoreElements()) {
                val networkInterface = networkInterfaces.nextElement()
                val mac = networkInterface.getHardwareAddress()
                if (mac != null) {
                    for (macPort in mac) {
                        sb.append(String.format("%02X", macPort))
                    }
                }
            }
            sb.toString().hashCode().toLong()
        } catch (ex: Exception) {
            SecureRandom().nextInt()
        }.toLong()
        nodeId = nodeId and maxNodeId
        return nodeId
    }

    fun parse(id: Long): LongArray {
        val maskNodeId = (1L shl NODE_ID_BITS) - 1 shl SEQUENCE_BITS
        val maskSequence = (1L shl SEQUENCE_BITS) - 1
        val timestamp = (id shr NODE_ID_BITS + SEQUENCE_BITS) + customEpoch
        val nodeId = id and maskNodeId shr SEQUENCE_BITS
        val sequence = id and maskSequence
        return longArrayOf(timestamp, nodeId, sequence)
    }
}

코드 구현은 아래 프로젝트를 적극 참고했으며, 불필요한 부분은 제거하는 등 리팩토링을 조금 진행했습니다. 또한 Java 코드를 Kotlin 코드로 변환했습니다. 

 

https://github.com/callicoder/java-snowflake

GitHub - callicoder/java-snowflake: Distributed Unique ID Generator in Java inspired by Twitter Snowflake

 

서비스 레이어에서 활용

@Service
class BlogService(
    // repositories
    private val userRepository: UserRepository,
    private val postRepository: PostRepository,

    // id generators
    private val snowflakeIdGenerator: SnowflakeIdGenerator,
    private val uuidGenerator: UuidGenerator
) {

    fun saveUser(dto: UserDto) {
        val user = User(
            id = uuidGenerator.nextId(),
            name = dto.name,
            age = dto.age
        )
        userRepository.save(user)
    }

    fun savePost(dto: PostDto) {
        val post = Post(
            id = snowflakeIdGenerator.nextId(),
            contents = dto.contents
        )
        postRepository.save(post)
    }
}

유저 객체를 생성할 때는 UUID 생성기를 활용했으며, 게시글 객체를 생성할 때는 Snowflake ID 생성기를 활용했습니다.

 

한눈에 읽고 이해하기 쉽게 표현하기 위해 위와 같이 코드를 작성했습니다. 조금 개선해 보자면, 도메인 별 ID 생성 방식에 따라 인터페이스를 다르게 해서 서비스 로직에서 ID 생성까지 신경 쓰지 않도록 분리하면 더 좋은 코드가 될 것 같습니다.

 

 

맺음말

 분산 시스템 환경에서 고유한 ID를 생성하는 방법에 대해 알아봤습니다. 하지만 작은 시스템에서는 auto_increment 방법도 결코 나쁜 방법이 아닙니다. 또한 UUID나 Snowflake 방식에 의존하지 않고, 직접 여러 숫자와 문자를 조합해서 ID를 생성하는 방식도 충분히 좋을 수 있습니다. 데이터와 데이터의 고유값을 설계할 때, 어떤 방식이 최선일지 충분히 고민하는 것은 나중에 발생할 문제를 줄이는 데 큰 도움이 될 것 같습니다. 긴 글 읽어주셔서 감사합니다.

 

 

Appendix

LINE에서 수많은 메시지에 ID를 부여하는 방법

• https://speakerdeck.com/line_devday2021/scalable-multi-datacenter-id-generator-for-lines-messaging-application
• https://bistros.tistory.com/185

 

---

 

References

• https://dev.mysql.com/doc/refman/8.0/en/example-auto-increment.html
• https://www.callicoder.com/distributed-unique-id-sequence-number-generator/
• https://jeong-pro.tistory.com/251
• https://apoorvtyagi.tech/generating-unique-ids-in-a-large-scale-distributed-environment
• https://www.linkedin.com/pulse/snowflake-vs-uuid-yeshwanth-n
• https://www.javatpoint.com/java-uuid
• https://kotlinworld.com/417