[기타] String으로 정렬하기 - 기본적인 룰, 시간, ULID

개요

안녕하세요. 요구 사항으로 특정 리스트에 대해서 시간순으로 정렬해달라는 요구사항을 받았습니다. 이를 정렬하기 위해서 어떤 데이터 타입의 형태를 사용하실건가요 ? 혹시 timestamp만 고려하고 있으시진 않으신가요 ? timestamp 정말 좋은 방법이지만 가독성이 좋지 않은건 누구나 아는 사실입니다. 혹시 String Type의 시간 표현 방법인 ISO_8601로 정렬하는건 생각해보셨나요 ? 혹시 이게 제대로 정렬될지 걱정이 들지 않으시나요 ?

저도 이와 같은 고민을 했고 여러 테스트를 진행해보았습니다. 오늘은 String 타입의 형태의 정렬에 대해서 한번 알아보도록 하겠습니다.

String의 정렬

String의 정렬은 일반적으로 시스템에 따라서 정렬 순시가 다를 수 있습니다만 기본적으로 사전순(lexicographical order)으로 정렬됩니다. 이번 포스팅에서도 String의 정렬은 사전순이라는 것으로 정하고 아래의 테스트들은 모두 사전순으로 정렬이 잘 되는지 확인하는 테스트임을 먼저 알려드립니다.

기본

먼저 기본적인 String 정렬을 한번 보도록하겠습니다. String은 각 사실 각 문자가 유니코드, 또는 UTF-8 등 에 매핑되어있습니다. 그리고 정렬은 그 값을 기준으로 정렬되게 됩니다. 아래 예제에 나온 값들은 각각 아스키 코드를 매핑해보면 'A' (65), 'B' (66), 'C' (67), 'D' (68), 'E' (69)의 유니코드 값을 가지고 있고 그것을 기반으로 정렬하게 되는 것입니다.

@Test
public void lexicographical_sorting_test() {
    List<String> before = new ArrayList<>(List.of("AA", "AB", "AC", "BA", "D"));
    Collections.sort(before);
    System.out.println(before); // [AA, AB, AC, BA, D]
}

추가적으로 아래 케이스도 인지하고 있으면 좋습니다. 아래 케이스를 보면 소문자가 대문자 뒤에 위치하게 됩니다. 소문자가 대문자 뒤에 오는 이유는 대문자가 소문자보다 코드 포인트가 앞에 위치하고 있기 때문입니다. 아래 예제를 코드 매핑해보면 'A' (65), 'B' (66), 'D' (68), 'c' (99), 'e' (101)입니다. 따라서 정렬했을 때 소문자가 대문자 뒤에있는 아래와 같은 결과를 얻게 되는것입니다.

@Test
public void lexicographical_sorting_test2() {
    List<String> before = new ArrayList<>(List.of("A", "c", "B", "e", "D"));
    Collections.sort(before);
    System.out.println(before); // [A, B, D, c, e]
}

숫자

다음으로 숫자에 대해서 정렬해보도록 하겠습니다. 일반적으로 숫자는 number type의 형식을 통해서 사용하지만 경우에 따라서 String을 통한 숫자를 사용해야할 때도 있습니다. 이런 케이스에서 아래와 같은 숫자들이 있다고 했을 때 정렬해보면 예상과는 다른 결과를 얻는 것을 알 수 있습니다. 이유는 사전적 구조에 따르면 11에서 처음 1이 2보다 코드 포인트가 더 앞에 있기 때문입니다. 한 문자씩 코드 포인트를 비교하기 때무넹 아래와 같은 결과를 얻게 되는것입니다.

@Test
public void number_sorting_test() {
    List<String> before = new ArrayList<>(List.of("1", "2", "4", "11", "5556", "12"));
    Collections.sort(before);
    System.out.println(before); // [1, 11, 12, 2, 4, 5556]
}

그렇다면 정상적으로 결과를 얻고 싶다면 어떻게 하면 좋을까요 ? 바로 zero-padding을 사용하는 것입니다. 숫자의 자리 수를 맞춰주기 위해서 앞 부분에 zero-padding을 수행하면됩니다. 앞의 예제에서 1이라면 제일 큰 수 였던 5556와의 문자길이를 맞춰주면 0001이 됩니다. 이런식으로 하여 결과를 내면 아래와 깉이 일반적으로 원하는 결과를 얻을 수 있게 됩니다.

@Test
public void number_sorting_test2() {
    List<String> before = new ArrayList<>(List.of("0001", "0002", "0004", "0011", "5556", "0012"));
    Collections.sort(before);
    System.out.println(before); // [0001, 0002, 0004, 0011, 0012, 5556]
}

중간 결론

위의 예제들을 통해서 문자열이 제대로 정렬되기 위해서는 아래의 조건을 만족해야합니다.

1. 대문자 또는 소문자중 한가지로 기술되어 있어야한다.
2. 문자열의 자리수를 맞춰야한다.

이제 위의 중간 결론을 가지고 2가지 케이스를 더 보도록 하겠습니다.

시간

String을 통해서 시간을 표현하는 ISO_8601 표준의 정렬은 사전순으로 정렬한다고 한다면 과연 시간순으로 정렬이 될까요 ? 네 정렬이 됩니다. 왜냐하면 이 표준은 위의 중간 결론의 2가지 조건을 만족하기 때문입니다. ISO_8601 표준을 자세히 알고 싶으신분은 [기타] 날짜와 시간 표현의 국제 표준인 ISO 8601에 대해서 자세히 알아보자. (RFC3339, ISO8601, JavaTime를 참조해주세요.

간단하게 보면 ISO_8601 에서 시간과 날짜를 표현하는 표현식은 2025-02-22T17:54:28.583938Z와 같이 yyyy-MM-ddThh:mm:ss.sss의 표현식을 가집니다. 모두 동일한 표현식을 가지기 때문에 이러한 표현식에 의해서 사전순으로 정렬했을 때 시간순으로 정렬될 수 있습니다.

List<String> before =
        new ArrayList<>(
                List.of(
                        Instant.now().plus(5, ChronoUnit.DAYS).toString(),
                        Instant.now().plus(5, ChronoUnit.SECONDS).toString(),
                        Instant.now().plus(5, ChronoUnit.MILLIS).toString(),
                        Instant.now().plus(5, ChronoUnit.MINUTES).toString(),
                        Instant.now().plus(5, ChronoUnit.HOURS).toString()
                )
        );
Collections.sort(before);
System.out.println(before); // [2025-02-22T17:54:28.583938Z, 2025-02-22T17:54:33.578925Z, 2025-02-22T17:59:28.578946Z, 2025-02-22T22:54:28.578952Z, 2025-02-27T17:54:28.574811Z]

하지만 주의 하셔야할점은 초의 정밀도를 동일하게 가져가야하고 timezone을 이용해서 표현한다면 동일한 timezone으로 비교해야한다는 점입니다.

Unique_ID

추가로 알아볼 방법은 Unique_ID에 대해서 알아보도록 하겠습니다. 많은 비지니스 케이스들을 살펴보면 심심찮게 시간순으롤 정렬할 수 있는 Unique_ID가 필요합니다. 시간순으로만 정렬하면 동일한 시간대에 생성된다면 중복 이슈가 발생할 수 있기 때문에 이는 요구사항을 100% 만족하지는 못할 수 있습니다. 따라서 이를 충족시킬 수 있는 몇가지 방법을 가지고 왔습니다.

ULID

ULID(Universally Unique Lexicographically Sortable Identifier)는 UUID의 대안으로, 고유성과 사전식 정렬 가능성을 모두 제공하는 식별자입니다. ULID는 2016년에 설계되었으며, 주로 데이터베이스 및 분산 시스템에서 사전식 정렬이 중요한 환경에서 사용됩니다.

ULID는 16바이트의 String 데이이터고 26자(Base32)를 이룹니다. 그리고 아래의 데이터 구성을 가집니다.

• 6Byte : 밀리초 단위의 Unix 타임스탬프.
• 10Byte : 고유성을 위해 추가된 랜덤 데이터.

뒤의 랜덤 데이터를 통해서 고유성을 가지고 앞의 6Byte를 통해서 시간순서를 가지게 되는것입니다. 변환되는 과정을 아래와 같습니다.

1. milli 초 단위의 timestamp를 Crockford’s Base32로 변환
   1. 1708687937000(10진수)를 32진수로 변환 (10진수를 32로 나누면서 나머지를 구하여 변환.)
   2. 나머지를 역순으로 정렬
   3. 10자리로 맞추기 위해 앞에 0을 추가
2. 48비트(밀리초 정수)를 Base32 문자 10개로 변환합니다.

예시는 아래와 같습니다.

# 1708687937000(10진수)를 32진수로 변환 (10진수를 32로 나누면서 나머지를 구하여 변환.)
1708687937000 ÷ 32 = 53396560531, 나머지 8 → "8"
53396560531 ÷ 32 = 1668642516, 나머지 19 → "J"
1668642516 ÷ 32 = 52145078, 나머지 20 → "K"
52145078 ÷ 32 = 1629533, 나머지 14 → "E"
1629533 ÷ 32 = 50922, 나머지 29 → "X"
50922 ÷ 32 = 1591, 나머지 10 → "A"
1591 ÷ 32 = 49, 나머지 23 → "Q"
49 ÷ 32 = 1, 나머지 17 → "H"
1 ÷ 32 = 0, 나머지 1 → "1"

# 나머지를 역순으로 정렬
"1HQAEXKJ8"

#10자리로 맞추기 위해 앞에 0을 추가
"01HABH4H2A"  (이 예제에서 나온 결과)

위 과정을 거치면 앞의 문자열은 시간이 지날수록 상대적으로 큰 코드포인트를 가지기 때문에 사전순으로 정렬했을 때 시간순으롤 정렬될 수 있습니다. Java 에서는 com.github.f4b6a3:ulid-creator 라이브러리를 사용하면 쉽게 구현해볼 수 있습니다.

List<String> ulidList = new ArrayList<>();

    // 여러 개의 ULID 생성
    ulidList.add(String.valueOf(UlidCreator.getUlid()));
    ulidList.add(String.valueOf(UlidCreator.getUlid()));
    ulidList.add(String.valueOf(UlidCreator.getUlid()));
    ulidList.add(String.valueOf(UlidCreator.getUlid()));

    System.out.println("Before Sorting:");
    ulidList.forEach(System.out::println);
    // 01JM7S0MM5BZA0D3B3C4NM6XGT
    // 01JM7S0MM82JZST3XSB1QHWCE2
    // 01JM7S0MM8K2BKJ0KPQ39GM23X
    // 01JM7S0MM8TJ59QVQJB71DV0DK


    // ULID 정렬
    Collections.sort(ulidList);

    System.out.println("\nAfter Sorting:");
    ulidList.forEach(System.out::println);
    // 01JM7S0MM5BZA0D3B3C4NM6XGT
    // 01JM7S0MM82JZST3XSB1QHWCE2
    // 01JM7S0MM8K2BKJ0KPQ39GM23X
    // 01JM7S0MM8TJ59QVQJB71DV0DK

마무리

오늘은 이렇게 String을 통해서 정렬하는 방법에 대해서 알아보았습니다.

Unique_ID의 경우 UUID의 특정 버전에 따라서 시간순으로 정렬할 수 있습니다, 그리고 스노우플레이크라고 유명한 방식이 있는데 이는 이후에 별도로 포스팅 해보도록 하겠습니다.

감사합니다.

참조

https://github.com/ulid/spec?tab=readme-ov-file

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

https://github.com/twitter-archive/snowflake/tree/snowflake-2010