lexicographical_order

Overview

실시간 재정렬 기능을 구현할 때, 여러 행을 업데이트해야 하는 $O(n)$ DB 쓰기는 흔한 병목 지점입니다.

이 문서는 lexicographical_order 라이브러리가 이 문제를 $O(1)$ DB 쓰기 비용으로 해결한 접근 방법과 그 과정을 설명합니다.

What's the problem?

1기획
23디자인
34개발
42배포

Reorder는 한 항목을 끌어 위치를 바꾸는 UI 패턴입니다.

항목 간 재정렬(Reordering) 기능은 현대 프론트엔드에서 흔한 기능 중 하나입니다. 노션, 지라, 피그마 같은 서비스에서 핵심 기능으로 사용되고 있죠.

아래는 일반적인 Reordering 구현 패턴을 설명하기 위한 참고용 코드입니다.

final items = [...];

ReorderableListView(
    onReorder: (int oldIndex, int newIndex) {
        final item = items.removeAt(oldIndex);
        items.insert(newIndex, item);
        render();
    }
)

$O(n)$ 의 시간복잡도를 갖지만 in-memory 연산이기에 눈에 띄는 지연 없이 동작합니다.

문제는 이 정렬 상태를 영구적으로 데이터베이스에 보관해야 할 때입니다.

An integer key trap

정수 키

하나 옮기는데 6개 수정 필요...

데이터베이스에 정렬 상태를 저장하려면 별도 정렬키 컬럼이 필요한데, 단순히 구현한다면 타입을 정수로 설정하고 [1, 2, 3]의 순차적인 값들을 갖도록 구성할 수 있습니다.

하지만 이 구현 방식은 3가지 문제점이 있습니다.

최악의 경우 $O(n)$ DB 쓰기: 아이템을 맨 첫 번째로 옮기면 모든 아이템의 키 값을 수정해야 합니다.
쓰기 증폭: DB 쓰기는 메모리 쓰기에 비해 수만 배 느립니다. 데이터 규모가 커질수록 병목이 됩니다.
실수하기 쉬운 범위 업데이트: 범위 쿼리 작성은 동등 비교(=)보다 실수하기 쉽고, 정확히 설정하지 못하면 데이터 불일치로 이어집니다. 롤백도 까다롭습니다.

What's the "solved" state?

문자열 키

하나 옮기면 딱 그것만 업데이트!

재정렬된 항목 1개당 1개의 DB 쓰기만 발생하도록 합니다.
실증적 테스트 시나리오로 정확성을 검증합니다.

Approaches

Integer keys with gaps

[1, 2, 3]이 아닌 [100, 200, 300]처럼 더 큰 Gap을 두고 키를 설정합니다. 100과 200 사이로 재정렬하면 150이라는 중간값을 할당합니다.

문제점: 150 -> 125 -> 112 -> ... 이렇게 반복하면 금방 Gap이 고갈되어 리밸런싱이 필요해집니다. 최대 $O(n)$ 의 DB 쓰기가 발생합니다.

Floating-point numbers

[1.0, 2.0, 3.0]처럼 부동소수점 타입으로 키를 설정하는 방식입니다. 정수와 달리 1.0과 2.0 사이에 1.5를, 1.0과 1.5 사이에 1.25를 할당하는 식으로 이론적으로 훨씬 많은 중간값을 표현할 수 있습니다.

유한한 정밀도: IEEE 754 double의 유효 자릿수는 약 15~17자리입니다. 동일한 위치로 반복 이동이 발생하면 결국 표현 가능한 중간값이 소진되고, 정수키 방식과 마찬가지로 리밸런싱이 필요해집니다.
동등 판정 위험: 부동소수점 연산 특성상 논리적으로 달라야 할 두 키가 같은 값으로 수렴할 수 있습니다. 이 경우 정렬 순서의 무결성이 깨집니다.

String ordering - Lexicographical comparison

문자열은 두 값 사이에 항상 새로운 중간값을 만들 수 있다는 성질을 가집니다. "a" < "b" 사이에 "an"을, 다시 "a" < "an" 사이에 "ag"를 삽입하는 식으로, 문자를 append해 무한히 세분화할 수 있습니다.

이 성질을 활용해 정렬키의 타입을 문자열로 설정합니다. 두 이웃 항목의 키 prev, next 사이로 재정렬이 발생하면 그 사이에 놓이는 새 키를 알고리즘으로 계산하고 해당 항목 1개만 업데이트합니다.

Gap 고갈 없음: 두 문자열 사이에는 항상 중간 문자열이 존재하므로 리밸런싱이 필요한 시점이 이론적으로 존재하지 않습니다.
$O(1)$ DB 쓰기: 재정렬된 항목 1개의 키만 수정하면 되므로 목록의 크기와 무관하게 단 1번의 쓰기만 발생합니다.
검증 가능한 정확성: 알고리즘의 결과를 수학적으로 증명할 수 있으며, 이를 토대로 엣지 케이스를 포함한 테스트 시나리오를 체계적으로 구성할 수 있습니다.

Decision

문자열 키 기반 접근 방법이 다른 방법들보다 우월하기 때문에 이 방법을 선택했습니다.

구현이 어렵다는 단점이 있지만, 한 번 구현해두면 다른 프로젝트에서도 두고두고 재사용할 수 있습니다.

`between`

기본적인 인터페이스로 between 함수를 제공합니다. 이 함수는 두 문자열 사이에 중간 문자열을 생성합니다.

final mid = between(prev: 'a', next: 'z');

assert(['a', 'z', mid]..sort() == ['a', mid, 'z']);

Time Complexity: 최악의 경우 $O(\max(\mathit{prev}.\mathit{length},\ \mathit{next}.\mathit{length}))$ 의 시간복잡도를 갖습니다.
Best Effort: 가능한 적은 길이의 중간 문자열을 생성하도록 시도합니다. 예를 들어 "a"와 "z" 사이에는 무수히 많은 문자열이 올 수 있으나 "a"와 "z"의 중간인 "m"을 생성합니다.

`generateOrderKey`

between만으로는 해결할 수 없는 케이스가 있습니다.

아이템이 없을 경우 가장 첫 키를 생성해야 할 때
기존 데이터셋을 이 라이브러리로 마이그레이션할 때

이를 위해 generateOrderKey 함수를 제공합니다. 이 함수는 생성할 키의 개수를 인자로 받아 그 개수만큼의 키를 생성합니다.

빈 배열일 경우 가장 첫 키를 생성합니다.

Future<Todo> createTodo(CreateTodoInput input) async {
    final orderKey = todos.isEmpty 
        ? generateOrderKey(1).first
        : between(prev: todos.last.orderKey);
    final todo = Todo(input);

    await todoRepository.create(todo);

    return todo;
}

기존 데이터셋을 이 라이브러리로 마이그레이션할 때

Future<void> migrateTodos() async {
    final todos = await todoRepository.getTodos();
    final orderKeys = generateOrderKey(todos.length);

    for (var index = 0; index < todos.length; index++) {
        final todo = todos[index];
        await todoRepository.update(todo.id, orderKey: orderKeys[index]);
    }
}

Outcomes

쓰기 병목 제거됨: 데이터 규모와 무관하게 한 번의 재정렬은 단 1번의 DB 쓰기만 발생합니다.
프로덕션에서 검증됨: 실제 상용 프로젝트에서 이 라이브러리로 재정렬 기능을 구현해 현재까지 문제없이 운영 중입니다.

Limitations

언젠가는 리밸런싱 필요: 극단적인 반복 삽입으로 키가 무한히 길어질 수 있습니다. 이 경우 결국 리밸런싱이 필요합니다.
의존성 락인: 나중에 정렬 전략을 변경하려면 전체 데이터 마이그레이션이 필요합니다.
언어 지원 제한: 공식 구현은 Dart와 Go만 존재합니다. 필요하다면 AI 도움을 받아 빠르게 포트할 수 있습니다.