들어가며
안녕하세요. LINE+ Contents Service Engineering 조직에서 백엔드 개발을 하고 있는 김한솔, 문다정, 이현동, 조강훈입니다. 저희 조직에서는 그룹 구성원의 기술 성장을 돕고 향상된 능력을 적재적소에 활용할 수 있도록 Tech Group이라는 조직 내 스터디 그룹을 운영하고 있습니다. 이 글에서는 Tech Group을 운영하면서 다뤘던 여러 주제 중 하나인 Atlassian Jira의 랭킹 알고리즘, LexoRank를 소개하려고 합니다.
LexoRank는 드래그 앤드 드롭(drag and drop) 정렬을 효과적으로 다룰 수 있는 정렬 알고리즘입니다. Atlassian에서 기존에 사용되던 다양한 드래그 앤드 드롭 정렬 방식의 단점을 보완해 개발했는데요. Atlassian에서는 Jira에서 LexoRank 알고리즘을 사용하는 방법과 기본적인 운영 메커니즘에 관한 정보만 제공할 뿐 별도로 라이브러리를 공개하지는 않았습니다.
이 때문에 많은 사용자가 다양한 LexoRank 라이브러리를 개발해 공개했는데요. 대부분의 라이브러리가 운영 중인 서비스에 바로 적용하기에는 제약 사항이 많았습니다. 이에 저희는 다양한 서비스에 효과적으로 적용할 수 있는 LexoRank 라이브러리를 직접 개발했고, 이를 사내 임직원을 위한 사내용 오픈소스로 공개했습니다.
본 글에서는 LexoRank가 무엇인지, 다른 랭킹 알고리즘과 비교해 어떤 장점이 있는지 설명하고, LexoRank 라이브러리를 개발하면서 마주한 여러 이슈와 그 해결 과정을 공유하고자 합니다. 이 글이 여러분께 유용한 인사이트를 제공하기를 바라며, 그럼 LexoRank로 딥다이브해 보겠습니다!
드래그 앤드 드롭 구현에 사용하는 기존 랭킹 알고리즘 의 종류와 한계
먼저 일반적으로 드래그 앤드 드롭 정렬을 구현하기 위해 사용하는 아래 세 가지 알고리즘이 어떻게 작동하는지 알아보고 각각 어떤 한계가 있는지 살펴보겠습니다.
- Integer 방식
- GreenHopper 방식
- Linked List 방식
이해를 돕기 위해 할 일 목록(to-do list)에서 항목을 드래그 앤드 드롭으로 정렬하는 예시를 준비했습니다.
1. Integer 방식
첫 번째로 가장 고전적인 방식인 Integer 방식입니다. 이 방식은 아래 그림과 같이 각 항목의 순서를 연속된 정수로 저장하는 방법입니다.
이 방식에는 어떤 한계가 있을까요? 예를 들어, 아래 그림과 같이 맨 아래에 위치한 Todo-E의 순서를 Todo-A와 Todo-B 사이로 변경하고 싶다고 가정해 봅시다. 이 경우 Todo-E의 순위값(order)이 5
에서 2
로 변경되며, 이후 기존 순서를 유지하기 위해 하위 항목들인 Todo-B, Todo-C, Todo-D의 순위값을 수정해야 하고, 수정하는 동안 시스템은 중단됩니다. 이런 방식은 데이터가 많은 경우 시스템의 성능 저하를 일으킬 수 있으며, 동시에 여러 사용자가 수정을 시도하면 빈번하게 충돌이 발생하기도 합니다.
2. GreenHopper 방식
이 방식은 정수 방식과 유사하지만, 각 항목 사이에 충분한 간격을 두고 순위값을 할당해서 새 항목을 중간에 삽입할 때 Todo-E외에 다른 항목의 순위값은 변경하지 않아도 됩니다. 예를 들어, Todo-E를 Todo-A와 Todo-B 사이로 옮길 때 Todo-E의 순위값을 100
으로 수정하기만 하면 됩니다.
GreenHopper 방식에도 한계는 있습니다. 아래와 같이 이미 순위값들이 밀집돼 있어 새로운 값을 부여할 여유가 없는 상황이라면, 시스템을 중단하고 순위값을 재조정(rebalancing)하는 작업이 필요하며, 이때 정수 방식과 동일한 한계에 부딪힙니다.
3. Linked List 방식
이 방식은 각 항목이 이전 항목과 다음 항목의 정보를 갖고 있는 방식입니다. 따라서 GreenHopper 방식에서 발생하는 순위값 고갈 현상은 발생하지 않습니다.
하지만 이 방식에서는 순서를 변경할 때 연결된 항목들의 이전과 다음 항목 정보를 수정하기 위한 2~4번의 수정 비용이 발생합니다. 또한 목록을 조회할 때 전체를 스캔(full scan)해야 한다는 단점이 있습니다.
이와 같이 기존 랭킹 시스템은 데이터가 많고 드래그 앤드 드롭이 빈번하게 발생하는 상황에서는 명확한 한계를 드러냅니다.
정렬 방식 | 주요 한계점 |
---|---|
Integer | 순서 변경 시 수정 범위가 큼(O(N)) |
GreenHopper | 빠른 Rank 고갈 및 재조정 시 시스템 중단 |
Linked List | 순서 변경 시 2~4번의 고정 비용 발생 및 목록 조회 시 전체 스캔 |
그럼 LexoRank 알고리즘이 무엇이고 어떻게 이와 같은 한계를 극복할 수 있는지 설명하겠습니다.
LexoRank 알고리즘 소개
LexoRank는 "lexicographical rank"의 줄임말로 문자열의 사전적 순서를 활용해 순위를 결정하는 알고리즘입니다. 예를 들어, 일반적인 숫자 정렬에서 100
은 99
보다 낮은 순위이지만, LexoRank에서는 사전적 정렬에 따라 1
이 9
보다 앞에 있으므로 100
이 99
보다 높은 순위입니다.
그럼 LexoRank의 순위값은 어떻게 구성돼 있을까요?
LexoRank의 순위값 구조 및 작동 방법
LexoRank는 세 가지 주요 요소로 구 성돼 있고, 각 요소에는 기존 랭킹 시스템의 한계를 극복하기 위한 명확한 역할이 부여돼 있습니다.
- Bucket: 순위값 고갈 시 기존 순서를 유지하며 무중단으로 재조정하기 위한 요소
- FixedKey: 모든 항목에 기본으로 부여돼 기본 순위로 사용되는 요소로, 항목 간에 빠르게 비교할 수 있는 고정 길이 키
- VariableKey: FixedKey 고갈 시 할당되는 가변 길이 키
그럼 각 요소들이 어떻게 작동하는지 예시와 함께 살펴보겠습니다. 먼저 아래와 같이 Todo-A와 Todo-B 사이에 Todo-E를 삽입하려면 Todo-E에 Todo-A와 Todo-B 두 순위값의 중간에 해당하는 0|AAAB:
를 FixedKey 값으로 할당합니다.
만약 Todo-A와 Todo-B 사이의 순위값이 고갈됐다면, Todo-A의 FixedKey(AAAA
) 뒤에 규칙에 따라 VariableKey를 추가해 Todo-A의 뒤에, Todo-B의 앞에 오는 값을 할당합니다. 예를 들어 규칙에 따른 VariableKey가 5
라면 0|AAAA:5
가 할당됩니다. 이때 LexoRank는 FixedKey와 VariableKey를 조합해 대상 항목만 변경하므로 O(1)에 순서를 정렬할 수 있습니다.
이와 같이 VariableKey를 활용해 고갈을 지연시키기는 했지만 LexoRank 역시 언젠가는 순위값이 고갈되는 상황이 옵니다. 그렇다면 LexoRank는 어떻게 순위값 고갈을 사전에 감지하고 무중단으로 재조정할까요?