[알고리즘] LexoRank 알고리즘

LexoRank 알고리즘 개념

LexoRank는 동적인 정렬을 효율적으로 유지하기 위해 설계된 알고리즘으로, 연속적인 데이터의 순서를 유지하면서도 중간 삽입이 가능하도록 설계된 정렬 방식

 

Trello와 같은 태스크 관리 시스템에서 카드 또는 리스트의 순서를 유지하는데 사용됨

 

LexoRank 알고리즘의 필요성

기존 정렬 방식의 한계를 극복

1. 정수 기반 정렬

• 일반적으로 데이터 정렬 순서를 나타낼 때 1,2,3,4 - 와 같은 정수 값을 사용하는데, 중간에 새로운 항목을 삽입하려면 기존 데이터의 position 값을 재정렬해야 하는 문제 발생
• 대량의 데이터가 존재하는 경우 삽입 및 재정렬 시 성능 저하 문제

2. 배열의 index 활용

• 배열 기반 정렬에서는 중간 삽입이 어렵고, 대량의 데이터 재정렬이 필요함
• 만약, 배열에서 맨 앞에 값을 추가하게 된다면 모든 요소를 한 칸 씩 뒤로 밀어야 함
• Linked List 구조를 사용하면 일부 해결되지만, 데이터베이스에서 사용하기는 어려움

결론 : LexoRank 알고리즘을 통한 해결

• 순서 값을 문자열 기반으로 저장하여 중간 삽입이 가능
• 기존 데이터의 순서를 유지하면서도 새로운 요소 추가 가능
• 데이터베이스에서 대량의 삽입 작업을 수행할 때도 높은 성능 유지

LexoRank를 사용하면 좋은 상황

• 리스트의 순서를 자주 변경해야 하는 경우
• 정렬된 데이터를 빠르게 유지해야하는 경우
• 정렬 값이 너무 많은 경우 리밸런싱을 고려해야할 때

 

LexoRank 알고리즘의 동작 방식

LexoRank는 문자열을 사용하여 정렬 순서를 나타내며, 기본적으로 사전 순 비교(lexicographical order)를 활용

기본적으로 a<b<c<d< .... <z 의 방식으로 비교되며, 리스트 아이템의 위치를 조정할 때 중간 값을 생성하는 원리를 사용

1. Bucket : 순위값 고갈 시 기존 순서를 유지하며 무중단으로 재조정하기 위한 요소

• LexoRank는 데이터 정렬을 더 상세히 제어하기 위해 버킷(Bucket) 시스템을 사용
• 보통 a, b, c 등으로 버킷을 구분하며, 가장 앞의 버킷 문자는 전체 데이터의 대략적인 그룹을 결정
• ex. a000000과 b000000은 서로 다른 버킷을 의미하지만, 같은 버킷 내에서는 미세한 정렬이 가능

2. FixedKey : 모든 항목에 기본으로 부여돼 기본 순위로 사용되는 요소로, 항목 간에 빠르게 비교할 수 있는 고정 길이 키(고정된 키)

• 버킷 내부에서 기본적인 정렬을 유지하기 위한 고정된 접두사 값을 사용
• ex. a 버킷 내에서 a000000, a100000, a200000등의 값을 가질 수 있음

3. VariableKey : FixedKey 고갈 시 할당되는 가변 길이 키(가변 키)

• 기존 요소들 사이에 새로운 요소를 추가할 때, 가변적인 문자열 값을 생성하여 중간값을 만들 수 있음
• ex. a100000과 a200000사이에 새로운 값을 추가하면 a150000을 사용할 수 있음

 

LexoRank의 중간값 계산 방식
& 적용 예시

LexoRank는 두 개의 기존 순서 값(before, after)이 주어졌을 때, 이들 사이의 새로운 값을 만들어 삽입하는 방식을 사용

 

1. 처음 추가할 때

before = null
after = null
새로운 값 = "a"

 

2. 두번째 항목 추가

: 앞에 값이 a 이므로 새로운 값은 a와 z 사이의 중간 값인 m이 됨

before = "a"
after = null
새로운 값 = "m"

 

3. 첫 번째 항목과 두 번째 항목 사이에 세번째 항목 삽입(a와 m 사이에 삽입)

before = "a"
after = "m"
새로운 값 = "g"

 

4. 만약 a와 m 사이에 g를 추가한 후, 다시 a와 g 사이에 값을 추가했을 때

before = "a"
after = "g"
새로운 값 = "d"

-> 이런 방식으로 계속해서 중간 값 생성

 

5. 만약 값이 겹치는 경우 패딩 추가

:LexoRank는 중간값이 이미 존재하는 값과 겹치는 경우 뒤에 추가적인 문자를 붙여서 문제를 해결

before = "a"
after = "b"
새로운 값 = "am" (간격 확보)

 

*사용 예시

package com.example.panttegi.util;

public class LexoRank {
    public static String getMiddleRank(String before, String after) {
        if (before == null) before = "a"; // 최소값
        if (after == null) after = "zzzzzzzz"; // 최대값

        StringBuilder middle = new StringBuilder();
        int i = 0;

        while (true) {
            char beforeChar = i < before.length() ? before.charAt(i) : 'a';
            char afterChar = i < after.length() ? after.charAt(i) : 'z';

            // 동일한 문자일 경우, 그대로 중간값에 추가
            if (beforeChar == afterChar) {
                middle.append(beforeChar);
            } else {
                // 중간값 계산
                char midChar = (char)((beforeChar + afterChar) / 2);

                // 중간값이 beforeChar와 동일할 경우 처리
                if (midChar == beforeChar) {
                    middle.append(beforeChar).append('m'); // 새로운 문자 추가로 간격 확보
                } else {
                    middle.append(midChar);
                }
                break;
            }
            i++;
        }

        // 중간값 검증: 결과가 before 와 after 사이에 있는지 확인
        int safetyCounter = 100; // 최대 100회 패딩 추가 시도
        while ((middle.toString().compareTo(before) <= 0 || middle.toString().compareTo(after) >= 0) && safetyCounter > 0) {
            middle.append('m'); // 패딩 추가로 더 정밀한 위치 확보
            safetyCounter--;

            // 무한 루프 발생 시 예외 처리
            if (safetyCounter == 0) {
                return before + "m";
            }
        }

        return middle.toString();
    }
}

 

LexoRank 사용 장점

LexoRank는 정렬 유지와 변경을 쉽게 할 수 있는 정렬 알고리즘

1. O(1) 시간 복잡도로 정렬 순서 변경 가능

• 일반적인 정렬 알고리즘은 데이터를 재배열할 때 O(nlogn)의 시간이 걸리지만, LexoRank는 새로운 순서 값만 생성하면 되므로 O(1)의 시간 복잡도로 순서 변경 가능
• 기존의 sort index 방식보다 효율적

2. 동적 정렬을 빠르게 지원

• 리스트 아이템을 재정렬할 때, 전체 데이터 업데이트 없이도 새로운 값을 삽입할 수 있음
  • ex. A와 B 사이에 새로운 값을 넣어야 할 때, 기존 데이터를 이동하지 않고 새로운 중간값을 생성

3. 데이터베이스 변경이 최소화됨

• 기존 정렬을 유지하는 방식은 위치 변경 시 모든 데이터의 위치 값을 업데이트해야 하지만, LexoRank는 중간값을 생성하는 방식이므로 대부분의 경우 기존 데이터를 변경할 필요가 없음

4. 백엔드 및 프론트엔드 모두에서 일관성 유지

• LexoRank는 문자열 기반이므로, 프론트엔드와 백엔드에서 동일한 정렬 방식을 유지할 수 있음
• 사전순 정렬을 이용하므로, 데이터베이스와 애플리케이션 코드의 정렬 방식이 충돌할 가능성이 낮음

 

LexoRank 사용 시 고려해야할 점

1. LexoRank 값의 길이 증가 문제

• 값이 겹치는 경우, 추가적인 문자를 붙이는 방식(am, amm, ammm ...)을 사용하지만, 여러 번 겹치면 문자열 길이가 점점 길어짐
  • 초기에 before과 after 사이의 간격을 충분히 두는 방식을 고려(a -> m -> z 대신 a -> f -> k -> z)
  • 기존 데이터에서 LexoRank의 평균 길이를 모니터링하여, 일정 길이를 초과하면 전체 리밸런싱 수행

2. 값 충돌 및 리밸런싱(Rebalancing) 필요성

• 일정 시간이 지나면, 너무 많은 LexoRank 값이 생성되어, 서로 가까운 값들이 많아지고 새로운 값을 삽입하기 어려워짐
  • 주기적으로 정렬을 다시 계산하는 리밸런싱을 수행(전체적으로 새롭게 재정렬)

3. 문자열 비교 방식이 사전식 정렬을 따름

• LexoRank는 사전순 정렬을 기반으로 작동하므로, 일부 문자열 비교 방식과 다를 수 있음
  • 사전순 정렬을 기준으로 비교하는 로직을 정확히 이해하고, 검색&정렬 시 DB의 ORDER BY와 일관성을 유지

4. 데이터베이스 저장 시 고려 사항

• LexoRank 값이 단순 숫자가 아닌 문자열이므로, 데이터베이스에서 인덱싱 및 검색 성능에 영향이 있을 수 있음
  • VARCHAR 타입을 사용하고, 인덱스를 생성하여 조회 성능을 높임
  • 성능 분석 도구를 사용하여, LexoRank를 활용한 정렬이 빠르게 수행되는지 확인

5. LexoRank 기반의 정렬 변경 시 트랜잭션 처리

• 여러 사용자가 동시에 정렬을 변경하면 경합(Race Condition)이 발생할 수 있음
  • 낙관적 락(Optimistic Locking) 또는 분산 락(Redis 기반 락)을 적용하여 동일한 값이 동시에 수정되지 않도록 처리
  • LexoRank 값이 충돌하면 일정 시간 후 다시 재시도하도록 구현

 

LexoRank 활용 사례

• Trello(Task 관리 시스템)
• JIRA(이슈 트래킹 시스템)
• Notion(카드형 UI 정렬)
• Drag & Drop 기능이 필요한 정렬 시스템

 

결론

• LexoRank는 기존의 정수 기반 정렬 방식이 가지는 한계를 해결하고, 정렬된 데이터를 유동적으로 유지할 수 있는 효율적인 알고리즘
• 중간 삽입이 빈번하게 발생하는 애플리케이션에서 매우 유용하며, 데이터베이스 최적화에 강력한 장점 제공
• 무한한 세밀도로 정렬이 가능하지만, 무한 삽입 시 문자열이 길어질 수 있는 문제 고려

---

참고 글

https://techblog.lycorp.co.jp/ko/about-atlassian-jira-ranking-algorithm-lexorank

Jira의 이슈 정렬 방식이 Integer 방식이 아니라고?!